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