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