RegisterCoalescer.cpp revision 1d4673228143965fafbcb679417f5a9be53d0a2a
1//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the generic RegisterCoalescer interface which 11// is used as the common interface used by all clients and 12// implementations of register coalescing. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "regalloc" 17#include "RegisterCoalescer.h" 18#include "llvm/ADT/OwningPtr.h" 19#include "llvm/ADT/STLExtras.h" 20#include "llvm/ADT/SmallSet.h" 21#include "llvm/ADT/Statistic.h" 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/CodeGen/LiveIntervalAnalysis.h" 24#include "llvm/CodeGen/LiveRangeEdit.h" 25#include "llvm/CodeGen/MachineFrameInfo.h" 26#include "llvm/CodeGen/MachineInstr.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineRegisterInfo.h" 29#include "llvm/CodeGen/Passes.h" 30#include "llvm/CodeGen/RegisterClassInfo.h" 31#include "llvm/CodeGen/VirtRegMap.h" 32#include "llvm/IR/Value.h" 33#include "llvm/Pass.h" 34#include "llvm/Support/CommandLine.h" 35#include "llvm/Support/Debug.h" 36#include "llvm/Support/ErrorHandling.h" 37#include "llvm/Support/raw_ostream.h" 38#include "llvm/Target/TargetInstrInfo.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Target/TargetOptions.h" 41#include "llvm/Target/TargetRegisterInfo.h" 42#include "llvm/Target/TargetSubtargetInfo.h" 43#include <algorithm> 44#include <cmath> 45using namespace llvm; 46 47STATISTIC(numJoins , "Number of interval joins performed"); 48STATISTIC(numCrossRCs , "Number of cross class joins performed"); 49STATISTIC(numCommutes , "Number of instruction commuting performed"); 50STATISTIC(numExtends , "Number of copies extended"); 51STATISTIC(NumReMats , "Number of instructions re-materialized"); 52STATISTIC(NumInflated , "Number of register classes inflated"); 53STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 54STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 55 56static cl::opt<bool> 57EnableJoining("join-liveintervals", 58 cl::desc("Coalesce copies (default=true)"), 59 cl::init(true)); 60 61// Temporary flag to test critical edge unsplitting. 62static cl::opt<bool> 63EnableJoinSplits("join-splitedges", 64 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); 65 66// Temporary flag to test global copy optimization. 67static cl::opt<cl::boolOrDefault> 68EnableGlobalCopies("join-globalcopies", 69 cl::desc("Coalesce copies that span blocks (default=subtarget)"), 70 cl::init(cl::BOU_UNSET), cl::Hidden); 71 72static cl::opt<bool> 73VerifyCoalescing("verify-coalescing", 74 cl::desc("Verify machine instrs before and after register coalescing"), 75 cl::Hidden); 76 77namespace { 78 class RegisterCoalescer : public MachineFunctionPass, 79 private LiveRangeEdit::Delegate { 80 MachineFunction* MF; 81 MachineRegisterInfo* MRI; 82 const TargetMachine* TM; 83 const TargetRegisterInfo* TRI; 84 const TargetInstrInfo* TII; 85 LiveIntervals *LIS; 86 const MachineLoopInfo* Loops; 87 AliasAnalysis *AA; 88 RegisterClassInfo RegClassInfo; 89 90 /// \brief True if the coalescer should aggressively coalesce global copies 91 /// in favor of keeping local copies. 92 bool JoinGlobalCopies; 93 94 /// \brief True if the coalescer should aggressively coalesce fall-thru 95 /// blocks exclusively containing copies. 96 bool JoinSplitEdges; 97 98 /// WorkList - Copy instructions yet to be coalesced. 99 SmallVector<MachineInstr*, 8> WorkList; 100 SmallVector<MachineInstr*, 8> LocalWorkList; 101 102 /// ErasedInstrs - Set of instruction pointers that have been erased, and 103 /// that may be present in WorkList. 104 SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 105 106 /// Dead instructions that are about to be deleted. 107 SmallVector<MachineInstr*, 8> DeadDefs; 108 109 /// Virtual registers to be considered for register class inflation. 110 SmallVector<unsigned, 8> InflateRegs; 111 112 /// Recursively eliminate dead defs in DeadDefs. 113 void eliminateDeadDefs(); 114 115 /// LiveRangeEdit callback. 116 void LRE_WillEraseInstruction(MachineInstr *MI); 117 118 /// coalesceLocals - coalesce the LocalWorkList. 119 void coalesceLocals(); 120 121 /// joinAllIntervals - join compatible live intervals 122 void joinAllIntervals(); 123 124 /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 125 /// copies that cannot yet be coalesced into WorkList. 126 void copyCoalesceInMBB(MachineBasicBlock *MBB); 127 128 /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return 129 /// true if any progress was made. 130 bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 131 132 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 133 /// which are the src/dst of the copy instruction CopyMI. This returns 134 /// true if the copy was successfully coalesced away. If it is not 135 /// currently possible to coalesce this interval, but it may be possible if 136 /// other things get coalesced, then it returns true by reference in 137 /// 'Again'. 138 bool joinCopy(MachineInstr *TheCopy, bool &Again); 139 140 /// joinIntervals - Attempt to join these two intervals. On failure, this 141 /// returns false. The output "SrcInt" will not have been modified, so we 142 /// can use this information below to update aliases. 143 bool joinIntervals(CoalescerPair &CP); 144 145 /// Attempt joining two virtual registers. Return true on success. 146 bool joinVirtRegs(CoalescerPair &CP); 147 148 /// Attempt joining with a reserved physreg. 149 bool joinReservedPhysReg(CoalescerPair &CP); 150 151 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 152 /// the source value number is defined by a copy from the destination reg 153 /// see if we can merge these two destination reg valno# into a single 154 /// value number, eliminating a copy. 155 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 156 157 /// hasOtherReachingDefs - Return true if there are definitions of IntB 158 /// other than BValNo val# that can reach uses of AValno val# of IntA. 159 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 160 VNInfo *AValNo, VNInfo *BValNo); 161 162 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 163 /// If the source value number is defined by a commutable instruction and 164 /// its other operand is coalesced to the copy dest register, see if we 165 /// can transform the copy into a noop by commuting the definition. 166 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 167 168 /// reMaterializeTrivialDef - If the source of a copy is defined by a 169 /// trivial computation, replace the copy by rematerialize the definition. 170 bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI); 171 172 /// canJoinPhys - Return true if a physreg copy should be joined. 173 bool canJoinPhys(const CoalescerPair &CP); 174 175 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 176 /// update the subregister number if it is not zero. If DstReg is a 177 /// physical register and the existing subregister number of the def / use 178 /// being updated is not zero, make sure to set it to the correct physical 179 /// subregister. 180 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 181 182 /// eliminateUndefCopy - Handle copies of undef values. 183 bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 184 185 public: 186 static char ID; // Class identification, replacement for typeinfo 187 RegisterCoalescer() : MachineFunctionPass(ID) { 188 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 189 } 190 191 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 192 193 virtual void releaseMemory(); 194 195 /// runOnMachineFunction - pass entry point 196 virtual bool runOnMachineFunction(MachineFunction&); 197 198 /// print - Implement the dump method. 199 virtual void print(raw_ostream &O, const Module* = 0) const; 200 }; 201} /// end anonymous namespace 202 203char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 204 205INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 206 "Simple Register Coalescing", false, false) 207INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 208INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 209INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 210INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 211INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 212 "Simple Register Coalescing", false, false) 213 214char RegisterCoalescer::ID = 0; 215 216static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 217 unsigned &Src, unsigned &Dst, 218 unsigned &SrcSub, unsigned &DstSub) { 219 if (MI->isCopy()) { 220 Dst = MI->getOperand(0).getReg(); 221 DstSub = MI->getOperand(0).getSubReg(); 222 Src = MI->getOperand(1).getReg(); 223 SrcSub = MI->getOperand(1).getSubReg(); 224 } else if (MI->isSubregToReg()) { 225 Dst = MI->getOperand(0).getReg(); 226 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 227 MI->getOperand(3).getImm()); 228 Src = MI->getOperand(2).getReg(); 229 SrcSub = MI->getOperand(2).getSubReg(); 230 } else 231 return false; 232 return true; 233} 234 235// Return true if this block should be vacated by the coalescer to eliminate 236// branches. The important cases to handle in the coalescer are critical edges 237// split during phi elimination which contain only copies. Simple blocks that 238// contain non-branches should also be vacated, but this can be handled by an 239// earlier pass similar to early if-conversion. 240static bool isSplitEdge(const MachineBasicBlock *MBB) { 241 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 242 return false; 243 244 for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end(); 245 MII != E; ++MII) { 246 if (!MII->isCopyLike() && !MII->isUnconditionalBranch()) 247 return false; 248 } 249 return true; 250} 251 252bool CoalescerPair::setRegisters(const MachineInstr *MI) { 253 SrcReg = DstReg = 0; 254 SrcIdx = DstIdx = 0; 255 NewRC = 0; 256 Flipped = CrossClass = false; 257 258 unsigned Src, Dst, SrcSub, DstSub; 259 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 260 return false; 261 Partial = SrcSub || DstSub; 262 263 // If one register is a physreg, it must be Dst. 264 if (TargetRegisterInfo::isPhysicalRegister(Src)) { 265 if (TargetRegisterInfo::isPhysicalRegister(Dst)) 266 return false; 267 std::swap(Src, Dst); 268 std::swap(SrcSub, DstSub); 269 Flipped = true; 270 } 271 272 const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 273 274 if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 275 // Eliminate DstSub on a physreg. 276 if (DstSub) { 277 Dst = TRI.getSubReg(Dst, DstSub); 278 if (!Dst) return false; 279 DstSub = 0; 280 } 281 282 // Eliminate SrcSub by picking a corresponding Dst superregister. 283 if (SrcSub) { 284 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 285 if (!Dst) return false; 286 SrcSub = 0; 287 } else if (!MRI.getRegClass(Src)->contains(Dst)) { 288 return false; 289 } 290 } else { 291 // Both registers are virtual. 292 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 293 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 294 295 // Both registers have subreg indices. 296 if (SrcSub && DstSub) { 297 // Copies between different sub-registers are never coalescable. 298 if (Src == Dst && SrcSub != DstSub) 299 return false; 300 301 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 302 SrcIdx, DstIdx); 303 if (!NewRC) 304 return false; 305 } else if (DstSub) { 306 // SrcReg will be merged with a sub-register of DstReg. 307 SrcIdx = DstSub; 308 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 309 } else if (SrcSub) { 310 // DstReg will be merged with a sub-register of SrcReg. 311 DstIdx = SrcSub; 312 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 313 } else { 314 // This is a straight copy without sub-registers. 315 NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 316 } 317 318 // The combined constraint may be impossible to satisfy. 319 if (!NewRC) 320 return false; 321 322 // Prefer SrcReg to be a sub-register of DstReg. 323 // FIXME: Coalescer should support subregs symmetrically. 324 if (DstIdx && !SrcIdx) { 325 std::swap(Src, Dst); 326 std::swap(SrcIdx, DstIdx); 327 Flipped = !Flipped; 328 } 329 330 CrossClass = NewRC != DstRC || NewRC != SrcRC; 331 } 332 // Check our invariants 333 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 334 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 335 "Cannot have a physical SubIdx"); 336 SrcReg = Src; 337 DstReg = Dst; 338 return true; 339} 340 341bool CoalescerPair::flip() { 342 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 343 return false; 344 std::swap(SrcReg, DstReg); 345 std::swap(SrcIdx, DstIdx); 346 Flipped = !Flipped; 347 return true; 348} 349 350bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 351 if (!MI) 352 return false; 353 unsigned Src, Dst, SrcSub, DstSub; 354 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 355 return false; 356 357 // Find the virtual register that is SrcReg. 358 if (Dst == SrcReg) { 359 std::swap(Src, Dst); 360 std::swap(SrcSub, DstSub); 361 } else if (Src != SrcReg) { 362 return false; 363 } 364 365 // Now check that Dst matches DstReg. 366 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 367 if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 368 return false; 369 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 370 // DstSub could be set for a physreg from INSERT_SUBREG. 371 if (DstSub) 372 Dst = TRI.getSubReg(Dst, DstSub); 373 // Full copy of Src. 374 if (!SrcSub) 375 return DstReg == Dst; 376 // This is a partial register copy. Check that the parts match. 377 return TRI.getSubReg(DstReg, SrcSub) == Dst; 378 } else { 379 // DstReg is virtual. 380 if (DstReg != Dst) 381 return false; 382 // Registers match, do the subregisters line up? 383 return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 384 TRI.composeSubRegIndices(DstIdx, DstSub); 385 } 386} 387 388void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 389 AU.setPreservesCFG(); 390 AU.addRequired<AliasAnalysis>(); 391 AU.addRequired<LiveIntervals>(); 392 AU.addPreserved<LiveIntervals>(); 393 AU.addPreserved<SlotIndexes>(); 394 AU.addRequired<MachineLoopInfo>(); 395 AU.addPreserved<MachineLoopInfo>(); 396 AU.addPreservedID(MachineDominatorsID); 397 MachineFunctionPass::getAnalysisUsage(AU); 398} 399 400void RegisterCoalescer::eliminateDeadDefs() { 401 SmallVector<LiveInterval*, 8> NewRegs; 402 LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 403} 404 405// Callback from eliminateDeadDefs(). 406void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 407 // MI may be in WorkList. Make sure we don't visit it. 408 ErasedInstrs.insert(MI); 409} 410 411/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 412/// being the source and IntB being the dest, thus this defines a value number 413/// in IntB. If the source value number (in IntA) is defined by a copy from B, 414/// see if we can merge these two pieces of B into a single value number, 415/// eliminating a copy. For example: 416/// 417/// A3 = B0 418/// ... 419/// B1 = A3 <- this copy 420/// 421/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 422/// value number to be replaced with B0 (which simplifies the B liveinterval). 423/// 424/// This returns true if an interval was modified. 425/// 426bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 427 MachineInstr *CopyMI) { 428 assert(!CP.isPartial() && "This doesn't work for partial copies."); 429 assert(!CP.isPhys() && "This doesn't work for physreg copies."); 430 431 LiveInterval &IntA = 432 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 433 LiveInterval &IntB = 434 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 435 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 436 437 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 438 // the example above. 439 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 440 if (BLR == IntB.end()) return false; 441 VNInfo *BValNo = BLR->valno; 442 443 // Get the location that B is defined at. Two options: either this value has 444 // an unknown definition point or it is defined at CopyIdx. If unknown, we 445 // can't process it. 446 if (BValNo->def != CopyIdx) return false; 447 448 // AValNo is the value number in A that defines the copy, A3 in the example. 449 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 450 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 451 // The live range might not exist after fun with physreg coalescing. 452 if (ALR == IntA.end()) return false; 453 VNInfo *AValNo = ALR->valno; 454 455 // If AValNo is defined as a copy from IntB, we can potentially process this. 456 // Get the instruction that defines this value number. 457 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 458 // Don't allow any partial copies, even if isCoalescable() allows them. 459 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 460 return false; 461 462 // Get the LiveRange in IntB that this value number starts with. 463 LiveInterval::iterator ValLR = 464 IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 465 if (ValLR == IntB.end()) 466 return false; 467 468 // Make sure that the end of the live range is inside the same block as 469 // CopyMI. 470 MachineInstr *ValLREndInst = 471 LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 472 if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 473 return false; 474 475 // Okay, we now know that ValLR ends in the same block that the CopyMI 476 // live-range starts. If there are no intervening live ranges between them in 477 // IntB, we can merge them. 478 if (ValLR+1 != BLR) return false; 479 480 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 481 482 SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 483 // We are about to delete CopyMI, so need to remove it as the 'instruction 484 // that defines this value #'. Update the valnum with the new defining 485 // instruction #. 486 BValNo->def = FillerStart; 487 488 // Okay, we can merge them. We need to insert a new liverange: 489 // [ValLR.end, BLR.begin) of either value number, then we merge the 490 // two value numbers. 491 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 492 493 // Okay, merge "B1" into the same value number as "B0". 494 if (BValNo != ValLR->valno) 495 IntB.MergeValueNumberInto(BValNo, ValLR->valno); 496 DEBUG(dbgs() << " result = " << IntB << '\n'); 497 498 // If the source instruction was killing the source register before the 499 // merge, unset the isKill marker given the live range has been extended. 500 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 501 if (UIdx != -1) { 502 ValLREndInst->getOperand(UIdx).setIsKill(false); 503 } 504 505 // Rewrite the copy. If the copy instruction was killing the destination 506 // register before the merge, find the last use and trim the live range. That 507 // will also add the isKill marker. 508 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 509 if (ALR->end == CopyIdx) 510 LIS->shrinkToUses(&IntA); 511 512 ++numExtends; 513 return true; 514} 515 516/// hasOtherReachingDefs - Return true if there are definitions of IntB 517/// other than BValNo val# that can reach uses of AValno val# of IntA. 518bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 519 LiveInterval &IntB, 520 VNInfo *AValNo, 521 VNInfo *BValNo) { 522 // If AValNo has PHI kills, conservatively assume that IntB defs can reach 523 // the PHI values. 524 if (LIS->hasPHIKill(IntA, AValNo)) 525 return true; 526 527 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 528 AI != AE; ++AI) { 529 if (AI->valno != AValNo) continue; 530 LiveInterval::Ranges::iterator BI = 531 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 532 if (BI != IntB.ranges.begin()) 533 --BI; 534 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 535 if (BI->valno == BValNo) 536 continue; 537 if (BI->start <= AI->start && BI->end > AI->start) 538 return true; 539 if (BI->start > AI->start && BI->start < AI->end) 540 return true; 541 } 542 } 543 return false; 544} 545 546/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 547/// IntA being the source and IntB being the dest, thus this defines a value 548/// number in IntB. If the source value number (in IntA) is defined by a 549/// commutable instruction and its other operand is coalesced to the copy dest 550/// register, see if we can transform the copy into a noop by commuting the 551/// definition. For example, 552/// 553/// A3 = op A2 B0<kill> 554/// ... 555/// B1 = A3 <- this copy 556/// ... 557/// = op A3 <- more uses 558/// 559/// ==> 560/// 561/// B2 = op B0 A2<kill> 562/// ... 563/// B1 = B2 <- now an identify copy 564/// ... 565/// = op B2 <- more uses 566/// 567/// This returns true if an interval was modified. 568/// 569bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 570 MachineInstr *CopyMI) { 571 assert (!CP.isPhys()); 572 573 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 574 575 LiveInterval &IntA = 576 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 577 LiveInterval &IntB = 578 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 579 580 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 581 // the example above. 582 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 583 if (!BValNo || BValNo->def != CopyIdx) 584 return false; 585 586 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 587 588 // AValNo is the value number in A that defines the copy, A3 in the example. 589 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 590 assert(AValNo && "COPY source not live"); 591 if (AValNo->isPHIDef() || AValNo->isUnused()) 592 return false; 593 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 594 if (!DefMI) 595 return false; 596 if (!DefMI->isCommutable()) 597 return false; 598 // If DefMI is a two-address instruction then commuting it will change the 599 // destination register. 600 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 601 assert(DefIdx != -1); 602 unsigned UseOpIdx; 603 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 604 return false; 605 unsigned Op1, Op2, NewDstIdx; 606 if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 607 return false; 608 if (Op1 == UseOpIdx) 609 NewDstIdx = Op2; 610 else if (Op2 == UseOpIdx) 611 NewDstIdx = Op1; 612 else 613 return false; 614 615 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 616 unsigned NewReg = NewDstMO.getReg(); 617 if (NewReg != IntB.reg || !LiveRangeQuery(IntB, AValNo->def).isKill()) 618 return false; 619 620 // Make sure there are no other definitions of IntB that would reach the 621 // uses which the new definition can reach. 622 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 623 return false; 624 625 // If some of the uses of IntA.reg is already coalesced away, return false. 626 // It's not possible to determine whether it's safe to perform the coalescing. 627 for (MachineRegisterInfo::use_nodbg_iterator UI = 628 MRI->use_nodbg_begin(IntA.reg), 629 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 630 MachineInstr *UseMI = &*UI; 631 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 632 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 633 if (ULR == IntA.end() || ULR->valno != AValNo) 634 continue; 635 // If this use is tied to a def, we can't rewrite the register. 636 if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 637 return false; 638 } 639 640 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 641 << *DefMI); 642 643 // At this point we have decided that it is legal to do this 644 // transformation. Start by commuting the instruction. 645 MachineBasicBlock *MBB = DefMI->getParent(); 646 MachineInstr *NewMI = TII->commuteInstruction(DefMI); 647 if (!NewMI) 648 return false; 649 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 650 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 651 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 652 return false; 653 if (NewMI != DefMI) { 654 LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 655 MachineBasicBlock::iterator Pos = DefMI; 656 MBB->insert(Pos, NewMI); 657 MBB->erase(DefMI); 658 } 659 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 660 NewMI->getOperand(OpIdx).setIsKill(); 661 662 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 663 // A = or A, B 664 // ... 665 // B = A 666 // ... 667 // C = A<kill> 668 // ... 669 // = B 670 671 // Update uses of IntA of the specific Val# with IntB. 672 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 673 UE = MRI->use_end(); UI != UE;) { 674 MachineOperand &UseMO = UI.getOperand(); 675 MachineInstr *UseMI = &*UI; 676 ++UI; 677 if (UseMI->isDebugValue()) { 678 // FIXME These don't have an instruction index. Not clear we have enough 679 // info to decide whether to do this replacement or not. For now do it. 680 UseMO.setReg(NewReg); 681 continue; 682 } 683 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 684 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 685 if (ULR == IntA.end() || ULR->valno != AValNo) 686 continue; 687 // Kill flags are no longer accurate. They are recomputed after RA. 688 UseMO.setIsKill(false); 689 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 690 UseMO.substPhysReg(NewReg, *TRI); 691 else 692 UseMO.setReg(NewReg); 693 if (UseMI == CopyMI) 694 continue; 695 if (!UseMI->isCopy()) 696 continue; 697 if (UseMI->getOperand(0).getReg() != IntB.reg || 698 UseMI->getOperand(0).getSubReg()) 699 continue; 700 701 // This copy will become a noop. If it's defining a new val#, merge it into 702 // BValNo. 703 SlotIndex DefIdx = UseIdx.getRegSlot(); 704 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 705 if (!DVNI) 706 continue; 707 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 708 assert(DVNI->def == DefIdx); 709 BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 710 ErasedInstrs.insert(UseMI); 711 LIS->RemoveMachineInstrFromMaps(UseMI); 712 UseMI->eraseFromParent(); 713 } 714 715 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 716 // is updated. 717 VNInfo *ValNo = BValNo; 718 ValNo->def = AValNo->def; 719 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 720 AI != AE; ++AI) { 721 if (AI->valno != AValNo) continue; 722 IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 723 } 724 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 725 726 IntA.removeValNo(AValNo); 727 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 728 ++numCommutes; 729 return true; 730} 731 732/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 733/// computation, replace the copy by rematerialize the definition. 734bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, 735 MachineInstr *CopyMI) { 736 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg(); 737 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg(); 738 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 739 return false; 740 741 LiveInterval &SrcInt = LIS->getInterval(SrcReg); 742 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 743 LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 744 assert(SrcLR != SrcInt.end() && "Live range not found!"); 745 VNInfo *ValNo = SrcLR->valno; 746 if (ValNo->isPHIDef() || ValNo->isUnused()) 747 return false; 748 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 749 if (!DefMI) 750 return false; 751 assert(DefMI && "Defining instruction disappeared"); 752 if (!DefMI->isAsCheapAsAMove()) 753 return false; 754 if (!TII->isTriviallyReMaterializable(DefMI, AA)) 755 return false; 756 bool SawStore = false; 757 if (!DefMI->isSafeToMove(TII, AA, SawStore)) 758 return false; 759 const MCInstrDesc &MCID = DefMI->getDesc(); 760 if (MCID.getNumDefs() != 1) 761 return false; 762 // Only support subregister destinations when the def is read-undef. 763 MachineOperand &DstOperand = CopyMI->getOperand(0); 764 if (DstOperand.getSubReg() && !DstOperand.isUndef()) 765 return false; 766 if (!DefMI->isImplicitDef()) { 767 // Make sure the copy destination register class fits the instruction 768 // definition register class. The mismatch can happen as a result of earlier 769 // extract_subreg, insert_subreg, subreg_to_reg coalescing. 770 const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 771 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 772 if (MRI->getRegClass(DstReg) != RC) 773 return false; 774 } else if (!RC->contains(DstReg)) 775 return false; 776 } 777 778 MachineBasicBlock *MBB = CopyMI->getParent(); 779 MachineBasicBlock::iterator MII = 780 llvm::next(MachineBasicBlock::iterator(CopyMI)); 781 TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 782 MachineInstr *NewMI = prior(MII); 783 784 // The original DefMI may have been a subregister def, but the full register 785 // class of its destination matches the destination of CopyMI, and CopyMI is 786 // either a full register def or is read-undef. Therefore we can clear the 787 // subregister index on the rematerialized instruction. 788 NewMI->getOperand(0).setSubReg(0); 789 790 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 791 // We need to remember these so we can add intervals once we insert 792 // NewMI into SlotIndexes. 793 SmallVector<unsigned, 4> NewMIImplDefs; 794 for (unsigned i = NewMI->getDesc().getNumOperands(), 795 e = NewMI->getNumOperands(); i != e; ++i) { 796 MachineOperand &MO = NewMI->getOperand(i); 797 if (MO.isReg()) { 798 assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 799 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 800 NewMIImplDefs.push_back(MO.getReg()); 801 } 802 } 803 804 // CopyMI may have implicit operands, transfer them over to the newly 805 // rematerialized instruction. And update implicit def interval valnos. 806 for (unsigned i = CopyMI->getDesc().getNumOperands(), 807 e = CopyMI->getNumOperands(); i != e; ++i) { 808 MachineOperand &MO = CopyMI->getOperand(i); 809 if (MO.isReg()) { 810 assert(MO.isImplicit() && "No explicit operands after implict operands."); 811 // Discard VReg implicit defs. 812 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 813 NewMI->addOperand(MO); 814 } 815 } 816 } 817 818 LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 819 820 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 821 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 822 unsigned Reg = NewMIImplDefs[i]; 823 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 824 if (LiveInterval *LI = LIS->getCachedRegUnit(*Units)) 825 LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 826 } 827 828 CopyMI->eraseFromParent(); 829 ErasedInstrs.insert(CopyMI); 830 DEBUG(dbgs() << "Remat: " << *NewMI); 831 ++NumReMats; 832 833 // The source interval can become smaller because we removed a use. 834 LIS->shrinkToUses(&SrcInt, &DeadDefs); 835 if (!DeadDefs.empty()) 836 eliminateDeadDefs(); 837 838 return true; 839} 840 841/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 842/// values, it only removes local variables. When we have a copy like: 843/// 844/// %vreg1 = COPY %vreg2<undef> 845/// 846/// We delete the copy and remove the corresponding value number from %vreg1. 847/// Any uses of that value number are marked as <undef>. 848bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 849 const CoalescerPair &CP) { 850 SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 851 LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 852 if (SrcInt->liveAt(Idx)) 853 return false; 854 LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 855 if (DstInt->liveAt(Idx)) 856 return false; 857 858 // No intervals are live-in to CopyMI - it is undef. 859 if (CP.isFlipped()) 860 DstInt = SrcInt; 861 SrcInt = 0; 862 863 VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 864 assert(DeadVNI && "No value defined in DstInt"); 865 DstInt->removeValNo(DeadVNI); 866 867 // Find new undef uses. 868 for (MachineRegisterInfo::reg_nodbg_iterator 869 I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 870 I != E; ++I) { 871 MachineOperand &MO = I.getOperand(); 872 if (MO.isDef() || MO.isUndef()) 873 continue; 874 MachineInstr *MI = MO.getParent(); 875 SlotIndex Idx = LIS->getInstructionIndex(MI); 876 if (DstInt->liveAt(Idx)) 877 continue; 878 MO.setIsUndef(true); 879 DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 880 } 881 return true; 882} 883 884/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 885/// update the subregister number if it is not zero. If DstReg is a 886/// physical register and the existing subregister number of the def / use 887/// being updated is not zero, make sure to set it to the correct physical 888/// subregister. 889void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 890 unsigned DstReg, 891 unsigned SubIdx) { 892 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 893 LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 894 895 SmallPtrSet<MachineInstr*, 8> Visited; 896 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 897 MachineInstr *UseMI = I.skipInstruction();) { 898 // Each instruction can only be rewritten once because sub-register 899 // composition is not always idempotent. When SrcReg != DstReg, rewriting 900 // the UseMI operands removes them from the SrcReg use-def chain, but when 901 // SrcReg is DstReg we could encounter UseMI twice if it has multiple 902 // operands mentioning the virtual register. 903 if (SrcReg == DstReg && !Visited.insert(UseMI)) 904 continue; 905 906 SmallVector<unsigned,8> Ops; 907 bool Reads, Writes; 908 tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 909 910 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 911 // because SrcReg is a sub-register. 912 if (DstInt && !Reads && SubIdx) 913 Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 914 915 // Replace SrcReg with DstReg in all UseMI operands. 916 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 917 MachineOperand &MO = UseMI->getOperand(Ops[i]); 918 919 // Adjust <undef> flags in case of sub-register joins. We don't want to 920 // turn a full def into a read-modify-write sub-register def and vice 921 // versa. 922 if (SubIdx && MO.isDef()) 923 MO.setIsUndef(!Reads); 924 925 if (DstIsPhys) 926 MO.substPhysReg(DstReg, *TRI); 927 else 928 MO.substVirtReg(DstReg, SubIdx, *TRI); 929 } 930 931 DEBUG({ 932 dbgs() << "\t\tupdated: "; 933 if (!UseMI->isDebugValue()) 934 dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 935 dbgs() << *UseMI; 936 }); 937 } 938} 939 940/// canJoinPhys - Return true if a copy involving a physreg should be joined. 941bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { 942 /// Always join simple intervals that are defined by a single copy from a 943 /// reserved register. This doesn't increase register pressure, so it is 944 /// always beneficial. 945 if (!MRI->isReserved(CP.getDstReg())) { 946 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 947 return false; 948 } 949 950 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 951 if (CP.isFlipped() && JoinVInt.containsOneValue()) 952 return true; 953 954 DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 955 return false; 956} 957 958/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 959/// which are the src/dst of the copy instruction CopyMI. This returns true 960/// if the copy was successfully coalesced away. If it is not currently 961/// possible to coalesce this interval, but it may be possible if other 962/// things get coalesced, then it returns true by reference in 'Again'. 963bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 964 965 Again = false; 966 DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 967 968 CoalescerPair CP(*TRI); 969 if (!CP.setRegisters(CopyMI)) { 970 DEBUG(dbgs() << "\tNot coalescable.\n"); 971 return false; 972 } 973 974 // Dead code elimination. This really should be handled by MachineDCE, but 975 // sometimes dead copies slip through, and we can't generate invalid live 976 // ranges. 977 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 978 DEBUG(dbgs() << "\tCopy is dead.\n"); 979 DeadDefs.push_back(CopyMI); 980 eliminateDeadDefs(); 981 return true; 982 } 983 984 // Eliminate undefs. 985 if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 986 DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 987 LIS->RemoveMachineInstrFromMaps(CopyMI); 988 CopyMI->eraseFromParent(); 989 return false; // Not coalescable. 990 } 991 992 // Coalesced copies are normally removed immediately, but transformations 993 // like removeCopyByCommutingDef() can inadvertently create identity copies. 994 // When that happens, just join the values and remove the copy. 995 if (CP.getSrcReg() == CP.getDstReg()) { 996 LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 997 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 998 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 999 if (VNInfo *DefVNI = LRQ.valueDefined()) { 1000 VNInfo *ReadVNI = LRQ.valueIn(); 1001 assert(ReadVNI && "No value before copy and no <undef> flag."); 1002 assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 1003 LI.MergeValueNumberInto(DefVNI, ReadVNI); 1004 DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 1005 } 1006 LIS->RemoveMachineInstrFromMaps(CopyMI); 1007 CopyMI->eraseFromParent(); 1008 return true; 1009 } 1010 1011 // Enforce policies. 1012 if (CP.isPhys()) { 1013 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1014 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1015 << '\n'); 1016 if (!canJoinPhys(CP)) { 1017 // Before giving up coalescing, if definition of source is defined by 1018 // trivial computation, try rematerializing it. 1019 if (reMaterializeTrivialDef(CP, CopyMI)) 1020 return true; 1021 return false; 1022 } 1023 } else { 1024 DEBUG({ 1025 dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1026 << " with "; 1027 if (CP.getDstIdx() && CP.getSrcIdx()) 1028 dbgs() << PrintReg(CP.getDstReg()) << " in " 1029 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1030 << PrintReg(CP.getSrcReg()) << " in " 1031 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1032 else 1033 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1034 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1035 }); 1036 1037 // When possible, let DstReg be the larger interval. 1038 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1039 LIS->getInterval(CP.getDstReg()).ranges.size()) 1040 CP.flip(); 1041 } 1042 1043 // Okay, attempt to join these two intervals. On failure, this returns false. 1044 // Otherwise, if one of the intervals being joined is a physreg, this method 1045 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1046 // been modified, so we can use this information below to update aliases. 1047 if (!joinIntervals(CP)) { 1048 // Coalescing failed. 1049 1050 // If definition of source is defined by trivial computation, try 1051 // rematerializing it. 1052 if (reMaterializeTrivialDef(CP, CopyMI)) 1053 return true; 1054 1055 // If we can eliminate the copy without merging the live ranges, do so now. 1056 if (!CP.isPartial() && !CP.isPhys()) { 1057 if (adjustCopiesBackFrom(CP, CopyMI) || 1058 removeCopyByCommutingDef(CP, CopyMI)) { 1059 LIS->RemoveMachineInstrFromMaps(CopyMI); 1060 CopyMI->eraseFromParent(); 1061 DEBUG(dbgs() << "\tTrivial!\n"); 1062 return true; 1063 } 1064 } 1065 1066 // Otherwise, we are unable to join the intervals. 1067 DEBUG(dbgs() << "\tInterference!\n"); 1068 Again = true; // May be possible to coalesce later. 1069 return false; 1070 } 1071 1072 // Coalescing to a virtual register that is of a sub-register class of the 1073 // other. Make sure the resulting register is set to the right register class. 1074 if (CP.isCrossClass()) { 1075 ++numCrossRCs; 1076 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1077 } 1078 1079 // Removing sub-register copies can ease the register class constraints. 1080 // Make sure we attempt to inflate the register class of DstReg. 1081 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1082 InflateRegs.push_back(CP.getDstReg()); 1083 1084 // CopyMI has been erased by joinIntervals at this point. Remove it from 1085 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1086 // to the work list. This keeps ErasedInstrs from growing needlessly. 1087 ErasedInstrs.erase(CopyMI); 1088 1089 // Rewrite all SrcReg operands to DstReg. 1090 // Also update DstReg operands to include DstIdx if it is set. 1091 if (CP.getDstIdx()) 1092 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1093 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1094 1095 // SrcReg is guaranteed to be the register whose live interval that is 1096 // being merged. 1097 LIS->removeInterval(CP.getSrcReg()); 1098 1099 // Update regalloc hint. 1100 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1101 1102 DEBUG({ 1103 dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI); 1104 if (!CP.isPhys()) 1105 dbgs() << LIS->getInterval(CP.getDstReg()); 1106 dbgs() << '\n'; 1107 }); 1108 1109 ++numJoins; 1110 return true; 1111} 1112 1113/// Attempt joining with a reserved physreg. 1114bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1115 assert(CP.isPhys() && "Must be a physreg copy"); 1116 assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 1117 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1118 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1119 << '\n'); 1120 1121 assert(CP.isFlipped() && RHS.containsOneValue() && 1122 "Invalid join with reserved register"); 1123 1124 // Optimization for reserved registers like ESP. We can only merge with a 1125 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1126 // The live range of the reserved register will look like a set of dead defs 1127 // - we don't properly track the live range of reserved registers. 1128 1129 // Deny any overlapping intervals. This depends on all the reserved 1130 // register live ranges to look like dead defs. 1131 for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1132 if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1133 DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1134 return false; 1135 } 1136 1137 // Skip any value computations, we are not adding new values to the 1138 // reserved register. Also skip merging the live ranges, the reserved 1139 // register live range doesn't need to be accurate as long as all the 1140 // defs are there. 1141 1142 // Delete the identity copy. 1143 MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1144 LIS->RemoveMachineInstrFromMaps(CopyMI); 1145 CopyMI->eraseFromParent(); 1146 1147 // We don't track kills for reserved registers. 1148 MRI->clearKillFlags(CP.getSrcReg()); 1149 1150 return true; 1151} 1152 1153//===----------------------------------------------------------------------===// 1154// Interference checking and interval joining 1155//===----------------------------------------------------------------------===// 1156// 1157// In the easiest case, the two live ranges being joined are disjoint, and 1158// there is no interference to consider. It is quite common, though, to have 1159// overlapping live ranges, and we need to check if the interference can be 1160// resolved. 1161// 1162// The live range of a single SSA value forms a sub-tree of the dominator tree. 1163// This means that two SSA values overlap if and only if the def of one value 1164// is contained in the live range of the other value. As a special case, the 1165// overlapping values can be defined at the same index. 1166// 1167// The interference from an overlapping def can be resolved in these cases: 1168// 1169// 1. Coalescable copies. The value is defined by a copy that would become an 1170// identity copy after joining SrcReg and DstReg. The copy instruction will 1171// be removed, and the value will be merged with the source value. 1172// 1173// There can be several copies back and forth, causing many values to be 1174// merged into one. We compute a list of ultimate values in the joined live 1175// range as well as a mappings from the old value numbers. 1176// 1177// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1178// predecessors have a live out value. It doesn't cause real interference, 1179// and can be merged into the value it overlaps. Like a coalescable copy, it 1180// can be erased after joining. 1181// 1182// 3. Copy of external value. The overlapping def may be a copy of a value that 1183// is already in the other register. This is like a coalescable copy, but 1184// the live range of the source register must be trimmed after erasing the 1185// copy instruction: 1186// 1187// %src = COPY %ext 1188// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1189// 1190// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1191// defining one lane at a time: 1192// 1193// %dst:ssub0<def,read-undef> = FOO 1194// %src = BAR 1195// %dst:ssub1<def> = COPY %src 1196// 1197// The live range of %src overlaps the %dst value defined by FOO, but 1198// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1199// which was undef anyway. 1200// 1201// The value mapping is more complicated in this case. The final live range 1202// will have different value numbers for both FOO and BAR, but there is no 1203// simple mapping from old to new values. It may even be necessary to add 1204// new PHI values. 1205// 1206// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1207// is live, but never read. This can happen because we don't compute 1208// individual live ranges per lane. 1209// 1210// %dst<def> = FOO 1211// %src = BAR 1212// %dst:ssub1<def> = COPY %src 1213// 1214// This kind of interference is only resolved locally. If the clobbered 1215// lane value escapes the block, the join is aborted. 1216 1217namespace { 1218/// Track information about values in a single virtual register about to be 1219/// joined. Objects of this class are always created in pairs - one for each 1220/// side of the CoalescerPair. 1221class JoinVals { 1222 LiveInterval &LI; 1223 1224 // Location of this register in the final joined register. 1225 // Either CP.DstIdx or CP.SrcIdx. 1226 unsigned SubIdx; 1227 1228 // Values that will be present in the final live range. 1229 SmallVectorImpl<VNInfo*> &NewVNInfo; 1230 1231 const CoalescerPair &CP; 1232 LiveIntervals *LIS; 1233 SlotIndexes *Indexes; 1234 const TargetRegisterInfo *TRI; 1235 1236 // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1237 // This is suitable for passing to LiveInterval::join(). 1238 SmallVector<int, 8> Assignments; 1239 1240 // Conflict resolution for overlapping values. 1241 enum ConflictResolution { 1242 // No overlap, simply keep this value. 1243 CR_Keep, 1244 1245 // Merge this value into OtherVNI and erase the defining instruction. 1246 // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1247 // values. 1248 CR_Erase, 1249 1250 // Merge this value into OtherVNI but keep the defining instruction. 1251 // This is for the special case where OtherVNI is defined by the same 1252 // instruction. 1253 CR_Merge, 1254 1255 // Keep this value, and have it replace OtherVNI where possible. This 1256 // complicates value mapping since OtherVNI maps to two different values 1257 // before and after this def. 1258 // Used when clobbering undefined or dead lanes. 1259 CR_Replace, 1260 1261 // Unresolved conflict. Visit later when all values have been mapped. 1262 CR_Unresolved, 1263 1264 // Unresolvable conflict. Abort the join. 1265 CR_Impossible 1266 }; 1267 1268 // Per-value info for LI. The lane bit masks are all relative to the final 1269 // joined register, so they can be compared directly between SrcReg and 1270 // DstReg. 1271 struct Val { 1272 ConflictResolution Resolution; 1273 1274 // Lanes written by this def, 0 for unanalyzed values. 1275 unsigned WriteLanes; 1276 1277 // Lanes with defined values in this register. Other lanes are undef and 1278 // safe to clobber. 1279 unsigned ValidLanes; 1280 1281 // Value in LI being redefined by this def. 1282 VNInfo *RedefVNI; 1283 1284 // Value in the other live range that overlaps this def, if any. 1285 VNInfo *OtherVNI; 1286 1287 // Is this value an IMPLICIT_DEF that can be erased? 1288 // 1289 // IMPLICIT_DEF values should only exist at the end of a basic block that 1290 // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1291 // safely erased if they are overlapping a live value in the other live 1292 // interval. 1293 // 1294 // Weird control flow graphs and incomplete PHI handling in 1295 // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1296 // longer live ranges. Such IMPLICIT_DEF values should be treated like 1297 // normal values. 1298 bool ErasableImplicitDef; 1299 1300 // True when the live range of this value will be pruned because of an 1301 // overlapping CR_Replace value in the other live range. 1302 bool Pruned; 1303 1304 // True once Pruned above has been computed. 1305 bool PrunedComputed; 1306 1307 Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1308 RedefVNI(0), OtherVNI(0), ErasableImplicitDef(false), 1309 Pruned(false), PrunedComputed(false) {} 1310 1311 bool isAnalyzed() const { return WriteLanes != 0; } 1312 }; 1313 1314 // One entry per value number in LI. 1315 SmallVector<Val, 8> Vals; 1316 1317 unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1318 VNInfo *stripCopies(VNInfo *VNI); 1319 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1320 void computeAssignment(unsigned ValNo, JoinVals &Other); 1321 bool taintExtent(unsigned, unsigned, JoinVals&, 1322 SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1323 bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 1324 bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1325 1326public: 1327 JoinVals(LiveInterval &li, unsigned subIdx, 1328 SmallVectorImpl<VNInfo*> &newVNInfo, 1329 const CoalescerPair &cp, 1330 LiveIntervals *lis, 1331 const TargetRegisterInfo *tri) 1332 : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1333 Indexes(LIS->getSlotIndexes()), TRI(tri), 1334 Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1335 {} 1336 1337 /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1338 /// Returns false if any conflicts were impossible to resolve. 1339 bool mapValues(JoinVals &Other); 1340 1341 /// Try to resolve conflicts that require all values to be mapped. 1342 /// Returns false if any conflicts were impossible to resolve. 1343 bool resolveConflicts(JoinVals &Other); 1344 1345 /// Prune the live range of values in Other.LI where they would conflict with 1346 /// CR_Replace values in LI. Collect end points for restoring the live range 1347 /// after joining. 1348 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 1349 1350 /// Erase any machine instructions that have been coalesced away. 1351 /// Add erased instructions to ErasedInstrs. 1352 /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1353 /// the erased instrs. 1354 void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1355 SmallVectorImpl<unsigned> &ShrinkRegs); 1356 1357 /// Get the value assignments suitable for passing to LiveInterval::join. 1358 const int *getAssignments() const { return Assignments.data(); } 1359}; 1360} // end anonymous namespace 1361 1362/// Compute the bitmask of lanes actually written by DefMI. 1363/// Set Redef if there are any partial register definitions that depend on the 1364/// previous value of the register. 1365unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1366 unsigned L = 0; 1367 for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1368 if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1369 continue; 1370 L |= TRI->getSubRegIndexLaneMask( 1371 TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1372 if (MO->readsReg()) 1373 Redef = true; 1374 } 1375 return L; 1376} 1377 1378/// Find the ultimate value that VNI was copied from. 1379VNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1380 while (!VNI->isPHIDef()) { 1381 MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1382 assert(MI && "No defining instruction"); 1383 if (!MI->isFullCopy()) 1384 break; 1385 unsigned Reg = MI->getOperand(1).getReg(); 1386 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1387 break; 1388 LiveRangeQuery LRQ(LIS->getInterval(Reg), VNI->def); 1389 if (!LRQ.valueIn()) 1390 break; 1391 VNI = LRQ.valueIn(); 1392 } 1393 return VNI; 1394} 1395 1396/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1397/// Return a conflict resolution when possible, but leave the hard cases as 1398/// CR_Unresolved. 1399/// Recursively calls computeAssignment() on this and Other, guaranteeing that 1400/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1401/// The recursion always goes upwards in the dominator tree, making loops 1402/// impossible. 1403JoinVals::ConflictResolution 1404JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1405 Val &V = Vals[ValNo]; 1406 assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1407 VNInfo *VNI = LI.getValNumInfo(ValNo); 1408 if (VNI->isUnused()) { 1409 V.WriteLanes = ~0u; 1410 return CR_Keep; 1411 } 1412 1413 // Get the instruction defining this value, compute the lanes written. 1414 const MachineInstr *DefMI = 0; 1415 if (VNI->isPHIDef()) { 1416 // Conservatively assume that all lanes in a PHI are valid. 1417 V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1418 } else { 1419 DefMI = Indexes->getInstructionFromIndex(VNI->def); 1420 bool Redef = false; 1421 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1422 1423 // If this is a read-modify-write instruction, there may be more valid 1424 // lanes than the ones written by this instruction. 1425 // This only covers partial redef operands. DefMI may have normal use 1426 // operands reading the register. They don't contribute valid lanes. 1427 // 1428 // This adds ssub1 to the set of valid lanes in %src: 1429 // 1430 // %src:ssub1<def> = FOO 1431 // 1432 // This leaves only ssub1 valid, making any other lanes undef: 1433 // 1434 // %src:ssub1<def,read-undef> = FOO %src:ssub2 1435 // 1436 // The <read-undef> flag on the def operand means that old lane values are 1437 // not important. 1438 if (Redef) { 1439 V.RedefVNI = LiveRangeQuery(LI, VNI->def).valueIn(); 1440 assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1441 computeAssignment(V.RedefVNI->id, Other); 1442 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1443 } 1444 1445 // An IMPLICIT_DEF writes undef values. 1446 if (DefMI->isImplicitDef()) { 1447 // We normally expect IMPLICIT_DEF values to be live only until the end 1448 // of their block. If the value is really live longer and gets pruned in 1449 // another block, this flag is cleared again. 1450 V.ErasableImplicitDef = true; 1451 V.ValidLanes &= ~V.WriteLanes; 1452 } 1453 } 1454 1455 // Find the value in Other that overlaps VNI->def, if any. 1456 LiveRangeQuery OtherLRQ(Other.LI, VNI->def); 1457 1458 // It is possible that both values are defined by the same instruction, or 1459 // the values are PHIs defined in the same block. When that happens, the two 1460 // values should be merged into one, but not into any preceding value. 1461 // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1462 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1463 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1464 1465 // One value stays, the other is merged. Keep the earlier one, or the first 1466 // one we see. 1467 if (OtherVNI->def < VNI->def) 1468 Other.computeAssignment(OtherVNI->id, *this); 1469 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1470 // This is an early-clobber def overlapping a live-in value in the other 1471 // register. Not mergeable. 1472 V.OtherVNI = OtherLRQ.valueIn(); 1473 return CR_Impossible; 1474 } 1475 V.OtherVNI = OtherVNI; 1476 Val &OtherV = Other.Vals[OtherVNI->id]; 1477 // Keep this value, check for conflicts when analyzing OtherVNI. 1478 if (!OtherV.isAnalyzed()) 1479 return CR_Keep; 1480 // Both sides have been analyzed now. 1481 // Allow overlapping PHI values. Any real interference would show up in a 1482 // predecessor, the PHI itself can't introduce any conflicts. 1483 if (VNI->isPHIDef()) 1484 return CR_Merge; 1485 if (V.ValidLanes & OtherV.ValidLanes) 1486 // Overlapping lanes can't be resolved. 1487 return CR_Impossible; 1488 else 1489 return CR_Merge; 1490 } 1491 1492 // No simultaneous def. Is Other live at the def? 1493 V.OtherVNI = OtherLRQ.valueIn(); 1494 if (!V.OtherVNI) 1495 // No overlap, no conflict. 1496 return CR_Keep; 1497 1498 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1499 1500 // We have overlapping values, or possibly a kill of Other. 1501 // Recursively compute assignments up the dominator tree. 1502 Other.computeAssignment(V.OtherVNI->id, *this); 1503 Val &OtherV = Other.Vals[V.OtherVNI->id]; 1504 1505 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 1506 // This shouldn't normally happen, but ProcessImplicitDefs can leave such 1507 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 1508 // technically. 1509 // 1510 // WHen it happens, treat that IMPLICIT_DEF as a normal value, and don't try 1511 // to erase the IMPLICIT_DEF instruction. 1512 if (OtherV.ErasableImplicitDef && DefMI && 1513 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 1514 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 1515 << " extends into BB#" << DefMI->getParent()->getNumber() 1516 << ", keeping it.\n"); 1517 OtherV.ErasableImplicitDef = false; 1518 } 1519 1520 // Allow overlapping PHI values. Any real interference would show up in a 1521 // predecessor, the PHI itself can't introduce any conflicts. 1522 if (VNI->isPHIDef()) 1523 return CR_Replace; 1524 1525 // Check for simple erasable conflicts. 1526 if (DefMI->isImplicitDef()) 1527 return CR_Erase; 1528 1529 // Include the non-conflict where DefMI is a coalescable copy that kills 1530 // OtherVNI. We still want the copy erased and value numbers merged. 1531 if (CP.isCoalescable(DefMI)) { 1532 // Some of the lanes copied from OtherVNI may be undef, making them undef 1533 // here too. 1534 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1535 return CR_Erase; 1536 } 1537 1538 // This may not be a real conflict if DefMI simply kills Other and defines 1539 // VNI. 1540 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1541 return CR_Keep; 1542 1543 // Handle the case where VNI and OtherVNI can be proven to be identical: 1544 // 1545 // %other = COPY %ext 1546 // %this = COPY %ext <-- Erase this copy 1547 // 1548 if (DefMI->isFullCopy() && !CP.isPartial() && 1549 stripCopies(VNI) == stripCopies(V.OtherVNI)) 1550 return CR_Erase; 1551 1552 // If the lanes written by this instruction were all undef in OtherVNI, it is 1553 // still safe to join the live ranges. This can't be done with a simple value 1554 // mapping, though - OtherVNI will map to multiple values: 1555 // 1556 // 1 %dst:ssub0 = FOO <-- OtherVNI 1557 // 2 %src = BAR <-- VNI 1558 // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 1559 // 4 BAZ %dst<kill> 1560 // 5 QUUX %src<kill> 1561 // 1562 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 1563 // handles this complex value mapping. 1564 if ((V.WriteLanes & OtherV.ValidLanes) == 0) 1565 return CR_Replace; 1566 1567 // If the other live range is killed by DefMI and the live ranges are still 1568 // overlapping, it must be because we're looking at an early clobber def: 1569 // 1570 // %dst<def,early-clobber> = ASM %src<kill> 1571 // 1572 // In this case, it is illegal to merge the two live ranges since the early 1573 // clobber def would clobber %src before it was read. 1574 if (OtherLRQ.isKill()) { 1575 // This case where the def doesn't overlap the kill is handled above. 1576 assert(VNI->def.isEarlyClobber() && 1577 "Only early clobber defs can overlap a kill"); 1578 return CR_Impossible; 1579 } 1580 1581 // VNI is clobbering live lanes in OtherVNI, but there is still the 1582 // possibility that no instructions actually read the clobbered lanes. 1583 // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1584 // Otherwise Other.LI wouldn't be live here. 1585 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1586 return CR_Impossible; 1587 1588 // We need to verify that no instructions are reading the clobbered lanes. To 1589 // save compile time, we'll only check that locally. Don't allow the tainted 1590 // value to escape the basic block. 1591 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1592 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1593 return CR_Impossible; 1594 1595 // There are still some things that could go wrong besides clobbered lanes 1596 // being read, for example OtherVNI may be only partially redefined in MBB, 1597 // and some clobbered lanes could escape the block. Save this analysis for 1598 // resolveConflicts() when all values have been mapped. We need to know 1599 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1600 // that now - the recursive analyzeValue() calls must go upwards in the 1601 // dominator tree. 1602 return CR_Unresolved; 1603} 1604 1605/// Compute the value assignment for ValNo in LI. 1606/// This may be called recursively by analyzeValue(), but never for a ValNo on 1607/// the stack. 1608void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1609 Val &V = Vals[ValNo]; 1610 if (V.isAnalyzed()) { 1611 // Recursion should always move up the dominator tree, so ValNo is not 1612 // supposed to reappear before it has been assigned. 1613 assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1614 return; 1615 } 1616 switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1617 case CR_Erase: 1618 case CR_Merge: 1619 // Merge this ValNo into OtherVNI. 1620 assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1621 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1622 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1623 DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1624 << LI.getValNumInfo(ValNo)->def << " into " 1625 << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1626 << V.OtherVNI->def << " --> @" 1627 << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1628 break; 1629 case CR_Replace: 1630 case CR_Unresolved: 1631 // The other value is going to be pruned if this join is successful. 1632 assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 1633 Other.Vals[V.OtherVNI->id].Pruned = true; 1634 // Fall through. 1635 default: 1636 // This value number needs to go in the final joined live range. 1637 Assignments[ValNo] = NewVNInfo.size(); 1638 NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1639 break; 1640 } 1641} 1642 1643bool JoinVals::mapValues(JoinVals &Other) { 1644 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1645 computeAssignment(i, Other); 1646 if (Vals[i].Resolution == CR_Impossible) { 1647 DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1648 << '@' << LI.getValNumInfo(i)->def << '\n'); 1649 return false; 1650 } 1651 } 1652 return true; 1653} 1654 1655/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1656/// the extent of the tainted lanes in the block. 1657/// 1658/// Multiple values in Other.LI can be affected since partial redefinitions can 1659/// preserve previously tainted lanes. 1660/// 1661/// 1 %dst = VLOAD <-- Define all lanes in %dst 1662/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1663/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1664/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1665/// 1666/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1667/// entry to TaintedVals. 1668/// 1669/// Returns false if the tainted lanes extend beyond the basic block. 1670bool JoinVals:: 1671taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1672 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1673 VNInfo *VNI = LI.getValNumInfo(ValNo); 1674 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1675 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1676 1677 // Scan Other.LI from VNI.def to MBBEnd. 1678 LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1679 assert(OtherI != Other.LI.end() && "No conflict?"); 1680 do { 1681 // OtherI is pointing to a tainted value. Abort the join if the tainted 1682 // lanes escape the block. 1683 SlotIndex End = OtherI->end; 1684 if (End >= MBBEnd) { 1685 DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1686 << OtherI->valno->id << '@' << OtherI->start << '\n'); 1687 return false; 1688 } 1689 DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1690 << OtherI->valno->id << '@' << OtherI->start 1691 << " to " << End << '\n'); 1692 // A dead def is not a problem. 1693 if (End.isDead()) 1694 break; 1695 TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1696 1697 // Check for another def in the MBB. 1698 if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1699 break; 1700 1701 // Lanes written by the new def are no longer tainted. 1702 const Val &OV = Other.Vals[OtherI->valno->id]; 1703 TaintedLanes &= ~OV.WriteLanes; 1704 if (!OV.RedefVNI) 1705 break; 1706 } while (TaintedLanes); 1707 return true; 1708} 1709 1710/// Return true if MI uses any of the given Lanes from Reg. 1711/// This does not include partial redefinitions of Reg. 1712bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1713 unsigned Lanes) { 1714 if (MI->isDebugValue()) 1715 return false; 1716 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1717 if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1718 continue; 1719 if (!MO->readsReg()) 1720 continue; 1721 if (Lanes & TRI->getSubRegIndexLaneMask( 1722 TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1723 return true; 1724 } 1725 return false; 1726} 1727 1728bool JoinVals::resolveConflicts(JoinVals &Other) { 1729 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1730 Val &V = Vals[i]; 1731 assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1732 if (V.Resolution != CR_Unresolved) 1733 continue; 1734 DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1735 << '@' << LI.getValNumInfo(i)->def << '\n'); 1736 ++NumLaneConflicts; 1737 assert(V.OtherVNI && "Inconsistent conflict resolution."); 1738 VNInfo *VNI = LI.getValNumInfo(i); 1739 const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1740 1741 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1742 // join, those lanes will be tainted with a wrong value. Get the extent of 1743 // the tainted lanes. 1744 unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1745 SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1746 if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1747 // Tainted lanes would extend beyond the basic block. 1748 return false; 1749 1750 assert(!TaintExtent.empty() && "There should be at least one conflict."); 1751 1752 // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1753 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1754 MachineBasicBlock::iterator MI = MBB->begin(); 1755 if (!VNI->isPHIDef()) { 1756 MI = Indexes->getInstructionFromIndex(VNI->def); 1757 // No need to check the instruction defining VNI for reads. 1758 ++MI; 1759 } 1760 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1761 "Interference ends on VNI->def. Should have been handled earlier"); 1762 MachineInstr *LastMI = 1763 Indexes->getInstructionFromIndex(TaintExtent.front().first); 1764 assert(LastMI && "Range must end at a proper instruction"); 1765 unsigned TaintNum = 0; 1766 for(;;) { 1767 assert(MI != MBB->end() && "Bad LastMI"); 1768 if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1769 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1770 return false; 1771 } 1772 // LastMI is the last instruction to use the current value. 1773 if (&*MI == LastMI) { 1774 if (++TaintNum == TaintExtent.size()) 1775 break; 1776 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1777 assert(LastMI && "Range must end at a proper instruction"); 1778 TaintedLanes = TaintExtent[TaintNum].second; 1779 } 1780 ++MI; 1781 } 1782 1783 // The tainted lanes are unused. 1784 V.Resolution = CR_Replace; 1785 ++NumLaneResolves; 1786 } 1787 return true; 1788} 1789 1790// Determine if ValNo is a copy of a value number in LI or Other.LI that will 1791// be pruned: 1792// 1793// %dst = COPY %src 1794// %src = COPY %dst <-- This value to be pruned. 1795// %dst = COPY %src <-- This value is a copy of a pruned value. 1796// 1797bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 1798 Val &V = Vals[ValNo]; 1799 if (V.Pruned || V.PrunedComputed) 1800 return V.Pruned; 1801 1802 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 1803 return V.Pruned; 1804 1805 // Follow copies up the dominator tree and check if any intermediate value 1806 // has been pruned. 1807 V.PrunedComputed = true; 1808 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 1809 return V.Pruned; 1810} 1811 1812void JoinVals::pruneValues(JoinVals &Other, 1813 SmallVectorImpl<SlotIndex> &EndPoints) { 1814 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1815 SlotIndex Def = LI.getValNumInfo(i)->def; 1816 switch (Vals[i].Resolution) { 1817 case CR_Keep: 1818 break; 1819 case CR_Replace: { 1820 // This value takes precedence over the value in Other.LI. 1821 LIS->pruneValue(&Other.LI, Def, &EndPoints); 1822 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1823 // instructions are only inserted to provide a live-out value for PHI 1824 // predecessors, so the instruction should simply go away once its value 1825 // has been replaced. 1826 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1827 bool EraseImpDef = OtherV.ErasableImplicitDef && 1828 OtherV.Resolution == CR_Keep; 1829 if (!Def.isBlock()) { 1830 // Remove <def,read-undef> flags. This def is now a partial redef. 1831 // Also remove <def,dead> flags since the joined live range will 1832 // continue past this instruction. 1833 for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 1834 MO.isValid(); ++MO) 1835 if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1836 MO->setIsUndef(EraseImpDef); 1837 MO->setIsDead(false); 1838 } 1839 // This value will reach instructions below, but we need to make sure 1840 // the live range also reaches the instruction at Def. 1841 if (!EraseImpDef) 1842 EndPoints.push_back(Def); 1843 } 1844 DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 1845 << ": " << Other.LI << '\n'); 1846 break; 1847 } 1848 case CR_Erase: 1849 case CR_Merge: 1850 if (isPrunedValue(i, Other)) { 1851 // This value is ultimately a copy of a pruned value in LI or Other.LI. 1852 // We can no longer trust the value mapping computed by 1853 // computeAssignment(), the value that was originally copied could have 1854 // been replaced. 1855 LIS->pruneValue(&LI, Def, &EndPoints); 1856 DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 1857 << Def << ": " << LI << '\n'); 1858 } 1859 break; 1860 case CR_Unresolved: 1861 case CR_Impossible: 1862 llvm_unreachable("Unresolved conflicts"); 1863 } 1864 } 1865} 1866 1867void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1868 SmallVectorImpl<unsigned> &ShrinkRegs) { 1869 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1870 // Get the def location before markUnused() below invalidates it. 1871 SlotIndex Def = LI.getValNumInfo(i)->def; 1872 switch (Vals[i].Resolution) { 1873 case CR_Keep: 1874 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1875 // longer. The IMPLICIT_DEF instructions are only inserted by 1876 // PHIElimination to guarantee that all PHI predecessors have a value. 1877 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 1878 break; 1879 // Remove value number i from LI. Note that this VNInfo is still present 1880 // in NewVNInfo, so it will appear as an unused value number in the final 1881 // joined interval. 1882 LI.getValNumInfo(i)->markUnused(); 1883 LI.removeValNo(LI.getValNumInfo(i)); 1884 DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1885 // FALL THROUGH. 1886 1887 case CR_Erase: { 1888 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1889 assert(MI && "No instruction to erase"); 1890 if (MI->isCopy()) { 1891 unsigned Reg = MI->getOperand(1).getReg(); 1892 if (TargetRegisterInfo::isVirtualRegister(Reg) && 1893 Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1894 ShrinkRegs.push_back(Reg); 1895 } 1896 ErasedInstrs.insert(MI); 1897 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1898 LIS->RemoveMachineInstrFromMaps(MI); 1899 MI->eraseFromParent(); 1900 break; 1901 } 1902 default: 1903 break; 1904 } 1905 } 1906} 1907 1908bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1909 SmallVector<VNInfo*, 16> NewVNInfo; 1910 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1911 LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1912 JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1913 JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1914 1915 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1916 << "\n\t\tLHS = " << PrintReg(CP.getDstReg()) << ' ' << LHS 1917 << '\n'); 1918 1919 // First compute NewVNInfo and the simple value mappings. 1920 // Detect impossible conflicts early. 1921 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1922 return false; 1923 1924 // Some conflicts can only be resolved after all values have been mapped. 1925 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1926 return false; 1927 1928 // All clear, the live ranges can be merged. 1929 1930 // The merging algorithm in LiveInterval::join() can't handle conflicting 1931 // value mappings, so we need to remove any live ranges that overlap a 1932 // CR_Replace resolution. Collect a set of end points that can be used to 1933 // restore the live range after joining. 1934 SmallVector<SlotIndex, 8> EndPoints; 1935 LHSVals.pruneValues(RHSVals, EndPoints); 1936 RHSVals.pruneValues(LHSVals, EndPoints); 1937 1938 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 1939 // registers to require trimming. 1940 SmallVector<unsigned, 8> ShrinkRegs; 1941 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1942 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1943 while (!ShrinkRegs.empty()) 1944 LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 1945 1946 // Join RHS into LHS. 1947 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo, 1948 MRI); 1949 1950 // Kill flags are going to be wrong if the live ranges were overlapping. 1951 // Eventually, we should simply clear all kill flags when computing live 1952 // ranges. They are reinserted after register allocation. 1953 MRI->clearKillFlags(LHS.reg); 1954 MRI->clearKillFlags(RHS.reg); 1955 1956 if (EndPoints.empty()) 1957 return true; 1958 1959 // Recompute the parts of the live range we had to remove because of 1960 // CR_Replace conflicts. 1961 DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 1962 << " points: " << LHS << '\n'); 1963 LIS->extendToIndices(&LHS, EndPoints); 1964 return true; 1965} 1966 1967/// joinIntervals - Attempt to join these two intervals. On failure, this 1968/// returns false. 1969bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 1970 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 1971} 1972 1973namespace { 1974// Information concerning MBB coalescing priority. 1975struct MBBPriorityInfo { 1976 MachineBasicBlock *MBB; 1977 unsigned Depth; 1978 bool IsSplit; 1979 1980 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 1981 : MBB(mbb), Depth(depth), IsSplit(issplit) {} 1982}; 1983} 1984 1985// C-style comparator that sorts first based on the loop depth of the basic 1986// block (the unsigned), and then on the MBB number. 1987// 1988// EnableGlobalCopies assumes that the primary sort key is loop depth. 1989static int compareMBBPriority(const void *L, const void *R) { 1990 const MBBPriorityInfo *LHS = static_cast<const MBBPriorityInfo*>(L); 1991 const MBBPriorityInfo *RHS = static_cast<const MBBPriorityInfo*>(R); 1992 // Deeper loops first 1993 if (LHS->Depth != RHS->Depth) 1994 return LHS->Depth > RHS->Depth ? -1 : 1; 1995 1996 // Try to unsplit critical edges next. 1997 if (LHS->IsSplit != RHS->IsSplit) 1998 return LHS->IsSplit ? -1 : 1; 1999 2000 // Prefer blocks that are more connected in the CFG. This takes care of 2001 // the most difficult copies first while intervals are short. 2002 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); 2003 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); 2004 if (cl != cr) 2005 return cl > cr ? -1 : 1; 2006 2007 // As a last resort, sort by block number. 2008 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; 2009} 2010 2011/// \returns true if the given copy uses or defines a local live range. 2012static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 2013 if (!Copy->isCopy()) 2014 return false; 2015 2016 unsigned SrcReg = Copy->getOperand(1).getReg(); 2017 unsigned DstReg = Copy->getOperand(0).getReg(); 2018 if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 2019 || TargetRegisterInfo::isPhysicalRegister(DstReg)) 2020 return false; 2021 2022 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 2023 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 2024} 2025 2026// Try joining WorkList copies starting from index From. 2027// Null out any successful joins. 2028bool RegisterCoalescer:: 2029copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2030 bool Progress = false; 2031 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2032 if (!CurrList[i]) 2033 continue; 2034 // Skip instruction pointers that have already been erased, for example by 2035 // dead code elimination. 2036 if (ErasedInstrs.erase(CurrList[i])) { 2037 CurrList[i] = 0; 2038 continue; 2039 } 2040 bool Again = false; 2041 bool Success = joinCopy(CurrList[i], Again); 2042 Progress |= Success; 2043 if (Success || !Again) 2044 CurrList[i] = 0; 2045 } 2046 return Progress; 2047} 2048 2049void 2050RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 2051 DEBUG(dbgs() << MBB->getName() << ":\n"); 2052 2053 // Collect all copy-like instructions in MBB. Don't start coalescing anything 2054 // yet, it might invalidate the iterator. 2055 const unsigned PrevSize = WorkList.size(); 2056 if (JoinGlobalCopies) { 2057 // Coalesce copies bottom-up to coalesce local defs before local uses. They 2058 // are not inherently easier to resolve, but slightly preferable until we 2059 // have local live range splitting. In particular this is required by 2060 // cmp+jmp macro fusion. 2061 for (MachineBasicBlock::reverse_iterator 2062 MII = MBB->rbegin(), E = MBB->rend(); MII != E; ++MII) { 2063 if (!MII->isCopyLike()) 2064 continue; 2065 if (isLocalCopy(&(*MII), LIS)) 2066 LocalWorkList.push_back(&(*MII)); 2067 else 2068 WorkList.push_back(&(*MII)); 2069 } 2070 } 2071 else { 2072 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2073 MII != E; ++MII) 2074 if (MII->isCopyLike()) 2075 WorkList.push_back(MII); 2076 } 2077 // Try coalescing the collected copies immediately, and remove the nulls. 2078 // This prevents the WorkList from getting too large since most copies are 2079 // joinable on the first attempt. 2080 MutableArrayRef<MachineInstr*> 2081 CurrList(WorkList.begin() + PrevSize, WorkList.end()); 2082 if (copyCoalesceWorkList(CurrList)) 2083 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 2084 (MachineInstr*)0), WorkList.end()); 2085} 2086 2087void RegisterCoalescer::coalesceLocals() { 2088 copyCoalesceWorkList(LocalWorkList); 2089 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 2090 if (LocalWorkList[j]) 2091 WorkList.push_back(LocalWorkList[j]); 2092 } 2093 LocalWorkList.clear(); 2094} 2095 2096void RegisterCoalescer::joinAllIntervals() { 2097 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 2098 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 2099 2100 std::vector<MBBPriorityInfo> MBBs; 2101 MBBs.reserve(MF->size()); 2102 for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 2103 MachineBasicBlock *MBB = I; 2104 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 2105 JoinSplitEdges && isSplitEdge(MBB))); 2106 } 2107 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); 2108 2109 // Coalesce intervals in MBB priority order. 2110 unsigned CurrDepth = UINT_MAX; 2111 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 2112 // Try coalescing the collected local copies for deeper loops. 2113 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { 2114 coalesceLocals(); 2115 CurrDepth = MBBs[i].Depth; 2116 } 2117 copyCoalesceInMBB(MBBs[i].MBB); 2118 } 2119 coalesceLocals(); 2120 2121 // Joining intervals can allow other intervals to be joined. Iteratively join 2122 // until we make no progress. 2123 while (copyCoalesceWorkList(WorkList)) 2124 /* empty */ ; 2125} 2126 2127void RegisterCoalescer::releaseMemory() { 2128 ErasedInstrs.clear(); 2129 WorkList.clear(); 2130 DeadDefs.clear(); 2131 InflateRegs.clear(); 2132} 2133 2134bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 2135 MF = &fn; 2136 MRI = &fn.getRegInfo(); 2137 TM = &fn.getTarget(); 2138 TRI = TM->getRegisterInfo(); 2139 TII = TM->getInstrInfo(); 2140 LIS = &getAnalysis<LiveIntervals>(); 2141 AA = &getAnalysis<AliasAnalysis>(); 2142 Loops = &getAnalysis<MachineLoopInfo>(); 2143 2144 const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 2145 if (EnableGlobalCopies == cl::BOU_UNSET) 2146 JoinGlobalCopies = ST.enableMachineScheduler(); 2147 else 2148 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 2149 2150 // The MachineScheduler does not currently require JoinSplitEdges. This will 2151 // either be enabled unconditionally or replaced by a more general live range 2152 // splitting optimization. 2153 JoinSplitEdges = EnableJoinSplits; 2154 2155 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 2156 << "********** Function: " << MF->getName() << '\n'); 2157 2158 if (VerifyCoalescing) 2159 MF->verify(this, "Before register coalescing"); 2160 2161 RegClassInfo.runOnMachineFunction(fn); 2162 2163 // Join (coalesce) intervals if requested. 2164 if (EnableJoining) 2165 joinAllIntervals(); 2166 2167 // After deleting a lot of copies, register classes may be less constrained. 2168 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 2169 // DPR inflation. 2170 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 2171 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 2172 InflateRegs.end()); 2173 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 2174 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 2175 unsigned Reg = InflateRegs[i]; 2176 if (MRI->reg_nodbg_empty(Reg)) 2177 continue; 2178 if (MRI->recomputeRegClass(Reg, *TM)) { 2179 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 2180 << MRI->getRegClass(Reg)->getName() << '\n'); 2181 ++NumInflated; 2182 } 2183 } 2184 2185 DEBUG(dump()); 2186 if (VerifyCoalescing) 2187 MF->verify(this, "After register coalescing"); 2188 return true; 2189} 2190 2191/// print - Implement the dump method. 2192void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 2193 LIS->print(O, m); 2194} 2195