1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===// 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 TwoAddress instruction pass which is used 11 // by most register allocators. Two-Address instructions are rewritten 12 // from: 13 // 14 // A = B op C 15 // 16 // to: 17 // 18 // A = B 19 // A op= C 20 // 21 // Note that if a register allocator chooses to use this pass, that it 22 // has to be capable of handling the non-SSA nature of these rewritten 23 // virtual registers. 24 // 25 // It is also worth noting that the duplicate operand of the two 26 // address instruction is removed. 27 // 28 //===----------------------------------------------------------------------===// 29 30 #include "llvm/CodeGen/Passes.h" 31 #include "llvm/ADT/BitVector.h" 32 #include "llvm/ADT/DenseMap.h" 33 #include "llvm/ADT/STLExtras.h" 34 #include "llvm/ADT/SmallSet.h" 35 #include "llvm/ADT/Statistic.h" 36 #include "llvm/Analysis/AliasAnalysis.h" 37 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 38 #include "llvm/CodeGen/LiveVariables.h" 39 #include "llvm/CodeGen/MachineFunctionPass.h" 40 #include "llvm/CodeGen/MachineInstr.h" 41 #include "llvm/CodeGen/MachineInstrBuilder.h" 42 #include "llvm/CodeGen/MachineRegisterInfo.h" 43 #include "llvm/IR/Function.h" 44 #include "llvm/MC/MCInstrItineraries.h" 45 #include "llvm/Support/CommandLine.h" 46 #include "llvm/Support/Debug.h" 47 #include "llvm/Support/ErrorHandling.h" 48 #include "llvm/Support/raw_ostream.h" 49 #include "llvm/Target/TargetInstrInfo.h" 50 #include "llvm/Target/TargetMachine.h" 51 #include "llvm/Target/TargetRegisterInfo.h" 52 #include "llvm/Target/TargetSubtargetInfo.h" 53 using namespace llvm; 54 55 #define DEBUG_TYPE "twoaddrinstr" 56 57 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 58 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 59 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 60 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 61 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 62 STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); 63 STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); 64 65 // Temporary flag to disable rescheduling. 66 static cl::opt<bool> 67 EnableRescheduling("twoaddr-reschedule", 68 cl::desc("Coalesce copies by rescheduling (default=true)"), 69 cl::init(true), cl::Hidden); 70 71 namespace { 72 class TwoAddressInstructionPass : public MachineFunctionPass { 73 MachineFunction *MF; 74 const TargetInstrInfo *TII; 75 const TargetRegisterInfo *TRI; 76 const InstrItineraryData *InstrItins; 77 MachineRegisterInfo *MRI; 78 LiveVariables *LV; 79 LiveIntervals *LIS; 80 AliasAnalysis *AA; 81 CodeGenOpt::Level OptLevel; 82 83 // The current basic block being processed. 84 MachineBasicBlock *MBB; 85 86 // DistanceMap - Keep track the distance of a MI from the start of the 87 // current basic block. 88 DenseMap<MachineInstr*, unsigned> DistanceMap; 89 90 // Set of already processed instructions in the current block. 91 SmallPtrSet<MachineInstr*, 8> Processed; 92 93 // SrcRegMap - A map from virtual registers to physical registers which are 94 // likely targets to be coalesced to due to copies from physical registers to 95 // virtual registers. e.g. v1024 = move r0. 96 DenseMap<unsigned, unsigned> SrcRegMap; 97 98 // DstRegMap - A map from virtual registers to physical registers which are 99 // likely targets to be coalesced to due to copies to physical registers from 100 // virtual registers. e.g. r1 = move v1024. 101 DenseMap<unsigned, unsigned> DstRegMap; 102 103 bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg, 104 MachineBasicBlock::iterator OldPos); 105 106 bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen); 107 108 bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef); 109 110 bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 111 MachineInstr *MI, unsigned Dist); 112 113 bool commuteInstruction(MachineBasicBlock::iterator &mi, 114 unsigned RegB, unsigned RegC, unsigned Dist); 115 116 bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); 117 118 bool convertInstTo3Addr(MachineBasicBlock::iterator &mi, 119 MachineBasicBlock::iterator &nmi, 120 unsigned RegA, unsigned RegB, unsigned Dist); 121 122 bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI); 123 124 bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 125 MachineBasicBlock::iterator &nmi, 126 unsigned Reg); 127 bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 128 MachineBasicBlock::iterator &nmi, 129 unsigned Reg); 130 131 bool tryInstructionTransform(MachineBasicBlock::iterator &mi, 132 MachineBasicBlock::iterator &nmi, 133 unsigned SrcIdx, unsigned DstIdx, 134 unsigned Dist, bool shouldOnlyCommute); 135 136 void scanUses(unsigned DstReg); 137 138 void processCopy(MachineInstr *MI); 139 140 typedef SmallVector<std::pair<unsigned, unsigned>, 4> TiedPairList; 141 typedef SmallDenseMap<unsigned, TiedPairList> TiedOperandMap; 142 bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&); 143 void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist); 144 void eliminateRegSequence(MachineBasicBlock::iterator&); 145 146 public: 147 static char ID; // Pass identification, replacement for typeid 148 TwoAddressInstructionPass() : MachineFunctionPass(ID) { 149 initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); 150 } 151 152 void getAnalysisUsage(AnalysisUsage &AU) const override { 153 AU.setPreservesCFG(); 154 AU.addRequired<AliasAnalysis>(); 155 AU.addPreserved<LiveVariables>(); 156 AU.addPreserved<SlotIndexes>(); 157 AU.addPreserved<LiveIntervals>(); 158 AU.addPreservedID(MachineLoopInfoID); 159 AU.addPreservedID(MachineDominatorsID); 160 MachineFunctionPass::getAnalysisUsage(AU); 161 } 162 163 /// runOnMachineFunction - Pass entry point. 164 bool runOnMachineFunction(MachineFunction&) override; 165 }; 166 } // end anonymous namespace 167 168 char TwoAddressInstructionPass::ID = 0; 169 INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", 170 "Two-Address instruction pass", false, false) 171 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 172 INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", 173 "Two-Address instruction pass", false, false) 174 175 char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; 176 177 static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS); 178 179 /// sink3AddrInstruction - A two-address instruction has been converted to a 180 /// three-address instruction to avoid clobbering a register. Try to sink it 181 /// past the instruction that would kill the above mentioned register to reduce 182 /// register pressure. 183 bool TwoAddressInstructionPass:: 184 sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, 185 MachineBasicBlock::iterator OldPos) { 186 // FIXME: Shouldn't we be trying to do this before we three-addressify the 187 // instruction? After this transformation is done, we no longer need 188 // the instruction to be in three-address form. 189 190 // Check if it's safe to move this instruction. 191 bool SeenStore = true; // Be conservative. 192 if (!MI->isSafeToMove(TII, AA, SeenStore)) 193 return false; 194 195 unsigned DefReg = 0; 196 SmallSet<unsigned, 4> UseRegs; 197 198 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 199 const MachineOperand &MO = MI->getOperand(i); 200 if (!MO.isReg()) 201 continue; 202 unsigned MOReg = MO.getReg(); 203 if (!MOReg) 204 continue; 205 if (MO.isUse() && MOReg != SavedReg) 206 UseRegs.insert(MO.getReg()); 207 if (!MO.isDef()) 208 continue; 209 if (MO.isImplicit()) 210 // Don't try to move it if it implicitly defines a register. 211 return false; 212 if (DefReg) 213 // For now, don't move any instructions that define multiple registers. 214 return false; 215 DefReg = MO.getReg(); 216 } 217 218 // Find the instruction that kills SavedReg. 219 MachineInstr *KillMI = nullptr; 220 if (LIS) { 221 LiveInterval &LI = LIS->getInterval(SavedReg); 222 assert(LI.end() != LI.begin() && 223 "Reg should not have empty live interval."); 224 225 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 226 LiveInterval::const_iterator I = LI.find(MBBEndIdx); 227 if (I != LI.end() && I->start < MBBEndIdx) 228 return false; 229 230 --I; 231 KillMI = LIS->getInstructionFromIndex(I->end); 232 } 233 if (!KillMI) { 234 for (MachineRegisterInfo::use_nodbg_iterator 235 UI = MRI->use_nodbg_begin(SavedReg), 236 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 237 MachineOperand &UseMO = *UI; 238 if (!UseMO.isKill()) 239 continue; 240 KillMI = UseMO.getParent(); 241 break; 242 } 243 } 244 245 // If we find the instruction that kills SavedReg, and it is in an 246 // appropriate location, we can try to sink the current instruction 247 // past it. 248 if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || 249 KillMI == OldPos || KillMI->isTerminator()) 250 return false; 251 252 // If any of the definitions are used by another instruction between the 253 // position and the kill use, then it's not safe to sink it. 254 // 255 // FIXME: This can be sped up if there is an easy way to query whether an 256 // instruction is before or after another instruction. Then we can use 257 // MachineRegisterInfo def / use instead. 258 MachineOperand *KillMO = nullptr; 259 MachineBasicBlock::iterator KillPos = KillMI; 260 ++KillPos; 261 262 unsigned NumVisited = 0; 263 for (MachineBasicBlock::iterator I = std::next(OldPos); I != KillPos; ++I) { 264 MachineInstr *OtherMI = I; 265 // DBG_VALUE cannot be counted against the limit. 266 if (OtherMI->isDebugValue()) 267 continue; 268 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 269 return false; 270 ++NumVisited; 271 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 272 MachineOperand &MO = OtherMI->getOperand(i); 273 if (!MO.isReg()) 274 continue; 275 unsigned MOReg = MO.getReg(); 276 if (!MOReg) 277 continue; 278 if (DefReg == MOReg) 279 return false; 280 281 if (MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS))) { 282 if (OtherMI == KillMI && MOReg == SavedReg) 283 // Save the operand that kills the register. We want to unset the kill 284 // marker if we can sink MI past it. 285 KillMO = &MO; 286 else if (UseRegs.count(MOReg)) 287 // One of the uses is killed before the destination. 288 return false; 289 } 290 } 291 } 292 assert(KillMO && "Didn't find kill"); 293 294 if (!LIS) { 295 // Update kill and LV information. 296 KillMO->setIsKill(false); 297 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 298 KillMO->setIsKill(true); 299 300 if (LV) 301 LV->replaceKillInstruction(SavedReg, KillMI, MI); 302 } 303 304 // Move instruction to its destination. 305 MBB->remove(MI); 306 MBB->insert(KillPos, MI); 307 308 if (LIS) 309 LIS->handleMove(MI); 310 311 ++Num3AddrSunk; 312 return true; 313 } 314 315 /// getSingleDef -- return the MachineInstr* if it is the single def of the Reg 316 /// in current BB. 317 static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB, 318 const MachineRegisterInfo *MRI) { 319 MachineInstr *Ret = nullptr; 320 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 321 if (DefMI.getParent() != BB || DefMI.isDebugValue()) 322 continue; 323 if (!Ret) 324 Ret = &DefMI; 325 else if (Ret != &DefMI) 326 return nullptr; 327 } 328 return Ret; 329 } 330 331 /// Check if there is a reversed copy chain from FromReg to ToReg: 332 /// %Tmp1 = copy %Tmp2; 333 /// %FromReg = copy %Tmp1; 334 /// %ToReg = add %FromReg ... 335 /// %Tmp2 = copy %ToReg; 336 /// MaxLen specifies the maximum length of the copy chain the func 337 /// can walk through. 338 bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg, 339 int Maxlen) { 340 unsigned TmpReg = FromReg; 341 for (int i = 0; i < Maxlen; i++) { 342 MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI); 343 if (!Def || !Def->isCopy()) 344 return false; 345 346 TmpReg = Def->getOperand(1).getReg(); 347 348 if (TmpReg == ToReg) 349 return true; 350 } 351 return false; 352 } 353 354 /// noUseAfterLastDef - Return true if there are no intervening uses between the 355 /// last instruction in the MBB that defines the specified register and the 356 /// two-address instruction which is being processed. It also returns the last 357 /// def location by reference 358 bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, 359 unsigned &LastDef) { 360 LastDef = 0; 361 unsigned LastUse = Dist; 362 for (MachineOperand &MO : MRI->reg_operands(Reg)) { 363 MachineInstr *MI = MO.getParent(); 364 if (MI->getParent() != MBB || MI->isDebugValue()) 365 continue; 366 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 367 if (DI == DistanceMap.end()) 368 continue; 369 if (MO.isUse() && DI->second < LastUse) 370 LastUse = DI->second; 371 if (MO.isDef() && DI->second > LastDef) 372 LastDef = DI->second; 373 } 374 375 return !(LastUse > LastDef && LastUse < Dist); 376 } 377 378 /// isCopyToReg - Return true if the specified MI is a copy instruction or 379 /// a extract_subreg instruction. It also returns the source and destination 380 /// registers and whether they are physical registers by reference. 381 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 382 unsigned &SrcReg, unsigned &DstReg, 383 bool &IsSrcPhys, bool &IsDstPhys) { 384 SrcReg = 0; 385 DstReg = 0; 386 if (MI.isCopy()) { 387 DstReg = MI.getOperand(0).getReg(); 388 SrcReg = MI.getOperand(1).getReg(); 389 } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { 390 DstReg = MI.getOperand(0).getReg(); 391 SrcReg = MI.getOperand(2).getReg(); 392 } else 393 return false; 394 395 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 396 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 397 return true; 398 } 399 400 /// isPLainlyKilled - Test if the given register value, which is used by the 401 // given instruction, is killed by the given instruction. 402 static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, 403 LiveIntervals *LIS) { 404 if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) && 405 !LIS->isNotInMIMap(MI)) { 406 // FIXME: Sometimes tryInstructionTransform() will add instructions and 407 // test whether they can be folded before keeping them. In this case it 408 // sets a kill before recursively calling tryInstructionTransform() again. 409 // If there is no interval available, we assume that this instruction is 410 // one of those. A kill flag is manually inserted on the operand so the 411 // check below will handle it. 412 LiveInterval &LI = LIS->getInterval(Reg); 413 // This is to match the kill flag version where undefs don't have kill 414 // flags. 415 if (!LI.hasAtLeastOneValue()) 416 return false; 417 418 SlotIndex useIdx = LIS->getInstructionIndex(MI); 419 LiveInterval::const_iterator I = LI.find(useIdx); 420 assert(I != LI.end() && "Reg must be live-in to use."); 421 return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx); 422 } 423 424 return MI->killsRegister(Reg); 425 } 426 427 /// isKilled - Test if the given register value, which is used by the given 428 /// instruction, is killed by the given instruction. This looks through 429 /// coalescable copies to see if the original value is potentially not killed. 430 /// 431 /// For example, in this code: 432 /// 433 /// %reg1034 = copy %reg1024 434 /// %reg1035 = copy %reg1025<kill> 435 /// %reg1036 = add %reg1034<kill>, %reg1035<kill> 436 /// 437 /// %reg1034 is not considered to be killed, since it is copied from a 438 /// register which is not killed. Treating it as not killed lets the 439 /// normal heuristics commute the (two-address) add, which lets 440 /// coalescing eliminate the extra copy. 441 /// 442 /// If allowFalsePositives is true then likely kills are treated as kills even 443 /// if it can't be proven that they are kills. 444 static bool isKilled(MachineInstr &MI, unsigned Reg, 445 const MachineRegisterInfo *MRI, 446 const TargetInstrInfo *TII, 447 LiveIntervals *LIS, 448 bool allowFalsePositives) { 449 MachineInstr *DefMI = &MI; 450 for (;;) { 451 // All uses of physical registers are likely to be kills. 452 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 453 (allowFalsePositives || MRI->hasOneUse(Reg))) 454 return true; 455 if (!isPlainlyKilled(DefMI, Reg, LIS)) 456 return false; 457 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 458 return true; 459 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 460 // If there are multiple defs, we can't do a simple analysis, so just 461 // go with what the kill flag says. 462 if (std::next(Begin) != MRI->def_end()) 463 return true; 464 DefMI = Begin->getParent(); 465 bool IsSrcPhys, IsDstPhys; 466 unsigned SrcReg, DstReg; 467 // If the def is something other than a copy, then it isn't going to 468 // be coalesced, so follow the kill flag. 469 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 470 return true; 471 Reg = SrcReg; 472 } 473 } 474 475 /// isTwoAddrUse - Return true if the specified MI uses the specified register 476 /// as a two-address use. If so, return the destination register by reference. 477 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 478 for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { 479 const MachineOperand &MO = MI.getOperand(i); 480 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 481 continue; 482 unsigned ti; 483 if (MI.isRegTiedToDefOperand(i, &ti)) { 484 DstReg = MI.getOperand(ti).getReg(); 485 return true; 486 } 487 } 488 return false; 489 } 490 491 /// findOnlyInterestingUse - Given a register, if has a single in-basic block 492 /// use, return the use instruction if it's a copy or a two-address use. 493 static 494 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 495 MachineRegisterInfo *MRI, 496 const TargetInstrInfo *TII, 497 bool &IsCopy, 498 unsigned &DstReg, bool &IsDstPhys) { 499 if (!MRI->hasOneNonDBGUse(Reg)) 500 // None or more than one use. 501 return nullptr; 502 MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg); 503 if (UseMI.getParent() != MBB) 504 return nullptr; 505 unsigned SrcReg; 506 bool IsSrcPhys; 507 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 508 IsCopy = true; 509 return &UseMI; 510 } 511 IsDstPhys = false; 512 if (isTwoAddrUse(UseMI, Reg, DstReg)) { 513 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 514 return &UseMI; 515 } 516 return nullptr; 517 } 518 519 /// getMappedReg - Return the physical register the specified virtual register 520 /// might be mapped to. 521 static unsigned 522 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 523 while (TargetRegisterInfo::isVirtualRegister(Reg)) { 524 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 525 if (SI == RegMap.end()) 526 return 0; 527 Reg = SI->second; 528 } 529 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 530 return Reg; 531 return 0; 532 } 533 534 /// regsAreCompatible - Return true if the two registers are equal or aliased. 535 /// 536 static bool 537 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 538 if (RegA == RegB) 539 return true; 540 if (!RegA || !RegB) 541 return false; 542 return TRI->regsOverlap(RegA, RegB); 543 } 544 545 546 /// isProfitableToCommute - Return true if it's potentially profitable to commute 547 /// the two-address instruction that's being processed. 548 bool 549 TwoAddressInstructionPass:: 550 isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 551 MachineInstr *MI, unsigned Dist) { 552 if (OptLevel == CodeGenOpt::None) 553 return false; 554 555 // Determine if it's profitable to commute this two address instruction. In 556 // general, we want no uses between this instruction and the definition of 557 // the two-address register. 558 // e.g. 559 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 560 // %reg1029<def> = MOV8rr %reg1028 561 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 562 // insert => %reg1030<def> = MOV8rr %reg1028 563 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 564 // In this case, it might not be possible to coalesce the second MOV8rr 565 // instruction if the first one is coalesced. So it would be profitable to 566 // commute it: 567 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 568 // %reg1029<def> = MOV8rr %reg1028 569 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 570 // insert => %reg1030<def> = MOV8rr %reg1029 571 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 572 573 if (!isPlainlyKilled(MI, regC, LIS)) 574 return false; 575 576 // Ok, we have something like: 577 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 578 // let's see if it's worth commuting it. 579 580 // Look for situations like this: 581 // %reg1024<def> = MOV r1 582 // %reg1025<def> = MOV r0 583 // %reg1026<def> = ADD %reg1024, %reg1025 584 // r0 = MOV %reg1026 585 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 586 unsigned ToRegA = getMappedReg(regA, DstRegMap); 587 if (ToRegA) { 588 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 589 unsigned FromRegC = getMappedReg(regC, SrcRegMap); 590 bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI); 591 bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI); 592 593 // Compute if any of the following are true: 594 // -RegB is not tied to a register and RegC is compatible with RegA. 595 // -RegB is tied to the wrong physical register, but RegC is. 596 // -RegB is tied to the wrong physical register, and RegC isn't tied. 597 if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) 598 return true; 599 // Don't compute if any of the following are true: 600 // -RegC is not tied to a register and RegB is compatible with RegA. 601 // -RegC is tied to the wrong physical register, but RegB is. 602 // -RegC is tied to the wrong physical register, and RegB isn't tied. 603 if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) 604 return false; 605 } 606 607 // If there is a use of regC between its last def (could be livein) and this 608 // instruction, then bail. 609 unsigned LastDefC = 0; 610 if (!noUseAfterLastDef(regC, Dist, LastDefC)) 611 return false; 612 613 // If there is a use of regB between its last def (could be livein) and this 614 // instruction, then go ahead and make this transformation. 615 unsigned LastDefB = 0; 616 if (!noUseAfterLastDef(regB, Dist, LastDefB)) 617 return true; 618 619 // Look for situation like this: 620 // %reg101 = MOV %reg100 621 // %reg102 = ... 622 // %reg103 = ADD %reg102, %reg101 623 // ... = %reg103 ... 624 // %reg100 = MOV %reg103 625 // If there is a reversed copy chain from reg101 to reg103, commute the ADD 626 // to eliminate an otherwise unavoidable copy. 627 // FIXME: 628 // We can extend the logic further: If an pair of operands in an insn has 629 // been merged, the insn could be regarded as a virtual copy, and the virtual 630 // copy could also be used to construct a copy chain. 631 // To more generally minimize register copies, ideally the logic of two addr 632 // instruction pass should be integrated with register allocation pass where 633 // interference graph is available. 634 if (isRevCopyChain(regC, regA, 3)) 635 return true; 636 637 if (isRevCopyChain(regB, regA, 3)) 638 return false; 639 640 // Since there are no intervening uses for both registers, then commute 641 // if the def of regC is closer. Its live interval is shorter. 642 return LastDefB && LastDefC && LastDefC > LastDefB; 643 } 644 645 /// commuteInstruction - Commute a two-address instruction and update the basic 646 /// block, distance map, and live variables if needed. Return true if it is 647 /// successful. 648 bool TwoAddressInstructionPass:: 649 commuteInstruction(MachineBasicBlock::iterator &mi, 650 unsigned RegB, unsigned RegC, unsigned Dist) { 651 MachineInstr *MI = mi; 652 DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); 653 MachineInstr *NewMI = TII->commuteInstruction(MI); 654 655 if (NewMI == nullptr) { 656 DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); 657 return false; 658 } 659 660 DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); 661 assert(NewMI == MI && 662 "TargetInstrInfo::commuteInstruction() should not return a new " 663 "instruction unless it was requested."); 664 665 // Update source register map. 666 unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 667 if (FromRegC) { 668 unsigned RegA = MI->getOperand(0).getReg(); 669 SrcRegMap[RegA] = FromRegC; 670 } 671 672 return true; 673 } 674 675 /// isProfitableToConv3Addr - Return true if it is profitable to convert the 676 /// given 2-address instruction to a 3-address one. 677 bool 678 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ 679 // Look for situations like this: 680 // %reg1024<def> = MOV r1 681 // %reg1025<def> = MOV r0 682 // %reg1026<def> = ADD %reg1024, %reg1025 683 // r2 = MOV %reg1026 684 // Turn ADD into a 3-address instruction to avoid a copy. 685 unsigned FromRegB = getMappedReg(RegB, SrcRegMap); 686 if (!FromRegB) 687 return false; 688 unsigned ToRegA = getMappedReg(RegA, DstRegMap); 689 return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); 690 } 691 692 /// convertInstTo3Addr - Convert the specified two-address instruction into a 693 /// three address one. Return true if this transformation was successful. 694 bool 695 TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, 696 MachineBasicBlock::iterator &nmi, 697 unsigned RegA, unsigned RegB, 698 unsigned Dist) { 699 // FIXME: Why does convertToThreeAddress() need an iterator reference? 700 MachineFunction::iterator MFI = MBB; 701 MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV); 702 assert(MBB == MFI && "convertToThreeAddress changed iterator reference"); 703 if (!NewMI) 704 return false; 705 706 DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); 707 DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); 708 bool Sunk = false; 709 710 if (LIS) 711 LIS->ReplaceMachineInstrInMaps(mi, NewMI); 712 713 if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 714 // FIXME: Temporary workaround. If the new instruction doesn't 715 // uses RegB, convertToThreeAddress must have created more 716 // then one instruction. 717 Sunk = sink3AddrInstruction(NewMI, RegB, mi); 718 719 MBB->erase(mi); // Nuke the old inst. 720 721 if (!Sunk) { 722 DistanceMap.insert(std::make_pair(NewMI, Dist)); 723 mi = NewMI; 724 nmi = std::next(mi); 725 } 726 727 // Update source and destination register maps. 728 SrcRegMap.erase(RegA); 729 DstRegMap.erase(RegB); 730 return true; 731 } 732 733 /// scanUses - Scan forward recursively for only uses, update maps if the use 734 /// is a copy or a two-address instruction. 735 void 736 TwoAddressInstructionPass::scanUses(unsigned DstReg) { 737 SmallVector<unsigned, 4> VirtRegPairs; 738 bool IsDstPhys; 739 bool IsCopy = false; 740 unsigned NewReg = 0; 741 unsigned Reg = DstReg; 742 while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, 743 NewReg, IsDstPhys)) { 744 if (IsCopy && !Processed.insert(UseMI).second) 745 break; 746 747 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 748 if (DI != DistanceMap.end()) 749 // Earlier in the same MBB.Reached via a back edge. 750 break; 751 752 if (IsDstPhys) { 753 VirtRegPairs.push_back(NewReg); 754 break; 755 } 756 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; 757 if (!isNew) 758 assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); 759 VirtRegPairs.push_back(NewReg); 760 Reg = NewReg; 761 } 762 763 if (!VirtRegPairs.empty()) { 764 unsigned ToReg = VirtRegPairs.back(); 765 VirtRegPairs.pop_back(); 766 while (!VirtRegPairs.empty()) { 767 unsigned FromReg = VirtRegPairs.back(); 768 VirtRegPairs.pop_back(); 769 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 770 if (!isNew) 771 assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); 772 ToReg = FromReg; 773 } 774 bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; 775 if (!isNew) 776 assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); 777 } 778 } 779 780 /// processCopy - If the specified instruction is not yet processed, process it 781 /// if it's a copy. For a copy instruction, we find the physical registers the 782 /// source and destination registers might be mapped to. These are kept in 783 /// point-to maps used to determine future optimizations. e.g. 784 /// v1024 = mov r0 785 /// v1025 = mov r1 786 /// v1026 = add v1024, v1025 787 /// r1 = mov r1026 788 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially 789 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 790 /// potentially joined with r1 on the output side. It's worthwhile to commute 791 /// 'add' to eliminate a copy. 792 void TwoAddressInstructionPass::processCopy(MachineInstr *MI) { 793 if (Processed.count(MI)) 794 return; 795 796 bool IsSrcPhys, IsDstPhys; 797 unsigned SrcReg, DstReg; 798 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 799 return; 800 801 if (IsDstPhys && !IsSrcPhys) 802 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 803 else if (!IsDstPhys && IsSrcPhys) { 804 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 805 if (!isNew) 806 assert(SrcRegMap[DstReg] == SrcReg && 807 "Can't map to two src physical registers!"); 808 809 scanUses(DstReg); 810 } 811 812 Processed.insert(MI); 813 return; 814 } 815 816 /// rescheduleMIBelowKill - If there is one more local instruction that reads 817 /// 'Reg' and it kills 'Reg, consider moving the instruction below the kill 818 /// instruction in order to eliminate the need for the copy. 819 bool TwoAddressInstructionPass:: 820 rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 821 MachineBasicBlock::iterator &nmi, 822 unsigned Reg) { 823 // Bail immediately if we don't have LV or LIS available. We use them to find 824 // kills efficiently. 825 if (!LV && !LIS) 826 return false; 827 828 MachineInstr *MI = &*mi; 829 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 830 if (DI == DistanceMap.end()) 831 // Must be created from unfolded load. Don't waste time trying this. 832 return false; 833 834 MachineInstr *KillMI = nullptr; 835 if (LIS) { 836 LiveInterval &LI = LIS->getInterval(Reg); 837 assert(LI.end() != LI.begin() && 838 "Reg should not have empty live interval."); 839 840 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 841 LiveInterval::const_iterator I = LI.find(MBBEndIdx); 842 if (I != LI.end() && I->start < MBBEndIdx) 843 return false; 844 845 --I; 846 KillMI = LIS->getInstructionFromIndex(I->end); 847 } else { 848 KillMI = LV->getVarInfo(Reg).findKill(MBB); 849 } 850 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 851 // Don't mess with copies, they may be coalesced later. 852 return false; 853 854 if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || 855 KillMI->isBranch() || KillMI->isTerminator()) 856 // Don't move pass calls, etc. 857 return false; 858 859 unsigned DstReg; 860 if (isTwoAddrUse(*KillMI, Reg, DstReg)) 861 return false; 862 863 bool SeenStore = true; 864 if (!MI->isSafeToMove(TII, AA, SeenStore)) 865 return false; 866 867 if (TII->getInstrLatency(InstrItins, MI) > 1) 868 // FIXME: Needs more sophisticated heuristics. 869 return false; 870 871 SmallSet<unsigned, 2> Uses; 872 SmallSet<unsigned, 2> Kills; 873 SmallSet<unsigned, 2> Defs; 874 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 875 const MachineOperand &MO = MI->getOperand(i); 876 if (!MO.isReg()) 877 continue; 878 unsigned MOReg = MO.getReg(); 879 if (!MOReg) 880 continue; 881 if (MO.isDef()) 882 Defs.insert(MOReg); 883 else { 884 Uses.insert(MOReg); 885 if (MOReg != Reg && (MO.isKill() || 886 (LIS && isPlainlyKilled(MI, MOReg, LIS)))) 887 Kills.insert(MOReg); 888 } 889 } 890 891 // Move the copies connected to MI down as well. 892 MachineBasicBlock::iterator Begin = MI; 893 MachineBasicBlock::iterator AfterMI = std::next(Begin); 894 895 MachineBasicBlock::iterator End = AfterMI; 896 while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) { 897 Defs.insert(End->getOperand(0).getReg()); 898 ++End; 899 } 900 901 // Check if the reschedule will not break depedencies. 902 unsigned NumVisited = 0; 903 MachineBasicBlock::iterator KillPos = KillMI; 904 ++KillPos; 905 for (MachineBasicBlock::iterator I = End; I != KillPos; ++I) { 906 MachineInstr *OtherMI = I; 907 // DBG_VALUE cannot be counted against the limit. 908 if (OtherMI->isDebugValue()) 909 continue; 910 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 911 return false; 912 ++NumVisited; 913 if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || 914 OtherMI->isBranch() || OtherMI->isTerminator()) 915 // Don't move pass calls, etc. 916 return false; 917 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 918 const MachineOperand &MO = OtherMI->getOperand(i); 919 if (!MO.isReg()) 920 continue; 921 unsigned MOReg = MO.getReg(); 922 if (!MOReg) 923 continue; 924 if (MO.isDef()) { 925 if (Uses.count(MOReg)) 926 // Physical register use would be clobbered. 927 return false; 928 if (!MO.isDead() && Defs.count(MOReg)) 929 // May clobber a physical register def. 930 // FIXME: This may be too conservative. It's ok if the instruction 931 // is sunken completely below the use. 932 return false; 933 } else { 934 if (Defs.count(MOReg)) 935 return false; 936 bool isKill = MO.isKill() || 937 (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)); 938 if (MOReg != Reg && 939 ((isKill && Uses.count(MOReg)) || Kills.count(MOReg))) 940 // Don't want to extend other live ranges and update kills. 941 return false; 942 if (MOReg == Reg && !isKill) 943 // We can't schedule across a use of the register in question. 944 return false; 945 // Ensure that if this is register in question, its the kill we expect. 946 assert((MOReg != Reg || OtherMI == KillMI) && 947 "Found multiple kills of a register in a basic block"); 948 } 949 } 950 } 951 952 // Move debug info as well. 953 while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue()) 954 --Begin; 955 956 nmi = End; 957 MachineBasicBlock::iterator InsertPos = KillPos; 958 if (LIS) { 959 // We have to move the copies first so that the MBB is still well-formed 960 // when calling handleMove(). 961 for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) { 962 MachineInstr *CopyMI = MBBI; 963 ++MBBI; 964 MBB->splice(InsertPos, MBB, CopyMI); 965 LIS->handleMove(CopyMI); 966 InsertPos = CopyMI; 967 } 968 End = std::next(MachineBasicBlock::iterator(MI)); 969 } 970 971 // Copies following MI may have been moved as well. 972 MBB->splice(InsertPos, MBB, Begin, End); 973 DistanceMap.erase(DI); 974 975 // Update live variables 976 if (LIS) { 977 LIS->handleMove(MI); 978 } else { 979 LV->removeVirtualRegisterKilled(Reg, KillMI); 980 LV->addVirtualRegisterKilled(Reg, MI); 981 } 982 983 DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI); 984 return true; 985 } 986 987 /// isDefTooClose - Return true if the re-scheduling will put the given 988 /// instruction too close to the defs of its register dependencies. 989 bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, 990 MachineInstr *MI) { 991 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 992 if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) 993 continue; 994 if (&DefMI == MI) 995 return true; // MI is defining something KillMI uses 996 DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI); 997 if (DDI == DistanceMap.end()) 998 return true; // Below MI 999 unsigned DefDist = DDI->second; 1000 assert(Dist > DefDist && "Visited def already?"); 1001 if (TII->getInstrLatency(InstrItins, &DefMI) > (Dist - DefDist)) 1002 return true; 1003 } 1004 return false; 1005 } 1006 1007 /// rescheduleKillAboveMI - If there is one more local instruction that reads 1008 /// 'Reg' and it kills 'Reg, consider moving the kill instruction above the 1009 /// current two-address instruction in order to eliminate the need for the 1010 /// copy. 1011 bool TwoAddressInstructionPass:: 1012 rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 1013 MachineBasicBlock::iterator &nmi, 1014 unsigned Reg) { 1015 // Bail immediately if we don't have LV or LIS available. We use them to find 1016 // kills efficiently. 1017 if (!LV && !LIS) 1018 return false; 1019 1020 MachineInstr *MI = &*mi; 1021 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 1022 if (DI == DistanceMap.end()) 1023 // Must be created from unfolded load. Don't waste time trying this. 1024 return false; 1025 1026 MachineInstr *KillMI = nullptr; 1027 if (LIS) { 1028 LiveInterval &LI = LIS->getInterval(Reg); 1029 assert(LI.end() != LI.begin() && 1030 "Reg should not have empty live interval."); 1031 1032 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 1033 LiveInterval::const_iterator I = LI.find(MBBEndIdx); 1034 if (I != LI.end() && I->start < MBBEndIdx) 1035 return false; 1036 1037 --I; 1038 KillMI = LIS->getInstructionFromIndex(I->end); 1039 } else { 1040 KillMI = LV->getVarInfo(Reg).findKill(MBB); 1041 } 1042 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 1043 // Don't mess with copies, they may be coalesced later. 1044 return false; 1045 1046 unsigned DstReg; 1047 if (isTwoAddrUse(*KillMI, Reg, DstReg)) 1048 return false; 1049 1050 bool SeenStore = true; 1051 if (!KillMI->isSafeToMove(TII, AA, SeenStore)) 1052 return false; 1053 1054 SmallSet<unsigned, 2> Uses; 1055 SmallSet<unsigned, 2> Kills; 1056 SmallSet<unsigned, 2> Defs; 1057 SmallSet<unsigned, 2> LiveDefs; 1058 for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { 1059 const MachineOperand &MO = KillMI->getOperand(i); 1060 if (!MO.isReg()) 1061 continue; 1062 unsigned MOReg = MO.getReg(); 1063 if (MO.isUse()) { 1064 if (!MOReg) 1065 continue; 1066 if (isDefTooClose(MOReg, DI->second, MI)) 1067 return false; 1068 bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS)); 1069 if (MOReg == Reg && !isKill) 1070 return false; 1071 Uses.insert(MOReg); 1072 if (isKill && MOReg != Reg) 1073 Kills.insert(MOReg); 1074 } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) { 1075 Defs.insert(MOReg); 1076 if (!MO.isDead()) 1077 LiveDefs.insert(MOReg); 1078 } 1079 } 1080 1081 // Check if the reschedule will not break depedencies. 1082 unsigned NumVisited = 0; 1083 MachineBasicBlock::iterator KillPos = KillMI; 1084 for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) { 1085 MachineInstr *OtherMI = I; 1086 // DBG_VALUE cannot be counted against the limit. 1087 if (OtherMI->isDebugValue()) 1088 continue; 1089 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 1090 return false; 1091 ++NumVisited; 1092 if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || 1093 OtherMI->isBranch() || OtherMI->isTerminator()) 1094 // Don't move pass calls, etc. 1095 return false; 1096 SmallVector<unsigned, 2> OtherDefs; 1097 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 1098 const MachineOperand &MO = OtherMI->getOperand(i); 1099 if (!MO.isReg()) 1100 continue; 1101 unsigned MOReg = MO.getReg(); 1102 if (!MOReg) 1103 continue; 1104 if (MO.isUse()) { 1105 if (Defs.count(MOReg)) 1106 // Moving KillMI can clobber the physical register if the def has 1107 // not been seen. 1108 return false; 1109 if (Kills.count(MOReg)) 1110 // Don't want to extend other live ranges and update kills. 1111 return false; 1112 if (OtherMI != MI && MOReg == Reg && 1113 !(MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)))) 1114 // We can't schedule across a use of the register in question. 1115 return false; 1116 } else { 1117 OtherDefs.push_back(MOReg); 1118 } 1119 } 1120 1121 for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { 1122 unsigned MOReg = OtherDefs[i]; 1123 if (Uses.count(MOReg)) 1124 return false; 1125 if (TargetRegisterInfo::isPhysicalRegister(MOReg) && 1126 LiveDefs.count(MOReg)) 1127 return false; 1128 // Physical register def is seen. 1129 Defs.erase(MOReg); 1130 } 1131 } 1132 1133 // Move the old kill above MI, don't forget to move debug info as well. 1134 MachineBasicBlock::iterator InsertPos = mi; 1135 while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue()) 1136 --InsertPos; 1137 MachineBasicBlock::iterator From = KillMI; 1138 MachineBasicBlock::iterator To = std::next(From); 1139 while (std::prev(From)->isDebugValue()) 1140 --From; 1141 MBB->splice(InsertPos, MBB, From, To); 1142 1143 nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. 1144 DistanceMap.erase(DI); 1145 1146 // Update live variables 1147 if (LIS) { 1148 LIS->handleMove(KillMI); 1149 } else { 1150 LV->removeVirtualRegisterKilled(Reg, KillMI); 1151 LV->addVirtualRegisterKilled(Reg, MI); 1152 } 1153 1154 DEBUG(dbgs() << "\trescheduled kill: " << *KillMI); 1155 return true; 1156 } 1157 1158 /// tryInstructionTransform - For the case where an instruction has a single 1159 /// pair of tied register operands, attempt some transformations that may 1160 /// either eliminate the tied operands or improve the opportunities for 1161 /// coalescing away the register copy. Returns true if no copy needs to be 1162 /// inserted to untie mi's operands (either because they were untied, or 1163 /// because mi was rescheduled, and will be visited again later). If the 1164 /// shouldOnlyCommute flag is true, only instruction commutation is attempted. 1165 bool TwoAddressInstructionPass:: 1166 tryInstructionTransform(MachineBasicBlock::iterator &mi, 1167 MachineBasicBlock::iterator &nmi, 1168 unsigned SrcIdx, unsigned DstIdx, 1169 unsigned Dist, bool shouldOnlyCommute) { 1170 if (OptLevel == CodeGenOpt::None) 1171 return false; 1172 1173 MachineInstr &MI = *mi; 1174 unsigned regA = MI.getOperand(DstIdx).getReg(); 1175 unsigned regB = MI.getOperand(SrcIdx).getReg(); 1176 1177 assert(TargetRegisterInfo::isVirtualRegister(regB) && 1178 "cannot make instruction into two-address form"); 1179 bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); 1180 1181 if (TargetRegisterInfo::isVirtualRegister(regA)) 1182 scanUses(regA); 1183 1184 // Check if it is profitable to commute the operands. 1185 unsigned SrcOp1, SrcOp2; 1186 unsigned regC = 0; 1187 unsigned regCIdx = ~0U; 1188 bool TryCommute = false; 1189 bool AggressiveCommute = false; 1190 if (MI.isCommutable() && MI.getNumOperands() >= 3 && 1191 TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) { 1192 if (SrcIdx == SrcOp1) 1193 regCIdx = SrcOp2; 1194 else if (SrcIdx == SrcOp2) 1195 regCIdx = SrcOp1; 1196 1197 if (regCIdx != ~0U) { 1198 regC = MI.getOperand(regCIdx).getReg(); 1199 if (!regBKilled && isKilled(MI, regC, MRI, TII, LIS, false)) 1200 // If C dies but B does not, swap the B and C operands. 1201 // This makes the live ranges of A and C joinable. 1202 TryCommute = true; 1203 else if (isProfitableToCommute(regA, regB, regC, &MI, Dist)) { 1204 TryCommute = true; 1205 AggressiveCommute = true; 1206 } 1207 } 1208 } 1209 1210 // If it's profitable to commute, try to do so. 1211 if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) { 1212 ++NumCommuted; 1213 if (AggressiveCommute) 1214 ++NumAggrCommuted; 1215 return false; 1216 } 1217 1218 if (shouldOnlyCommute) 1219 return false; 1220 1221 // If there is one more use of regB later in the same MBB, consider 1222 // re-schedule this MI below it. 1223 if (EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { 1224 ++NumReSchedDowns; 1225 return true; 1226 } 1227 1228 if (MI.isConvertibleTo3Addr()) { 1229 // This instruction is potentially convertible to a true 1230 // three-address instruction. Check if it is profitable. 1231 if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { 1232 // Try to convert it. 1233 if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) { 1234 ++NumConvertedTo3Addr; 1235 return true; // Done with this instruction. 1236 } 1237 } 1238 } 1239 1240 // If there is one more use of regB later in the same MBB, consider 1241 // re-schedule it before this MI if it's legal. 1242 if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { 1243 ++NumReSchedUps; 1244 return true; 1245 } 1246 1247 // If this is an instruction with a load folded into it, try unfolding 1248 // the load, e.g. avoid this: 1249 // movq %rdx, %rcx 1250 // addq (%rax), %rcx 1251 // in favor of this: 1252 // movq (%rax), %rcx 1253 // addq %rdx, %rcx 1254 // because it's preferable to schedule a load than a register copy. 1255 if (MI.mayLoad() && !regBKilled) { 1256 // Determine if a load can be unfolded. 1257 unsigned LoadRegIndex; 1258 unsigned NewOpc = 1259 TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 1260 /*UnfoldLoad=*/true, 1261 /*UnfoldStore=*/false, 1262 &LoadRegIndex); 1263 if (NewOpc != 0) { 1264 const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); 1265 if (UnfoldMCID.getNumDefs() == 1) { 1266 // Unfold the load. 1267 DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); 1268 const TargetRegisterClass *RC = 1269 TRI->getAllocatableClass( 1270 TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF)); 1271 unsigned Reg = MRI->createVirtualRegister(RC); 1272 SmallVector<MachineInstr *, 2> NewMIs; 1273 if (!TII->unfoldMemoryOperand(*MF, &MI, Reg, 1274 /*UnfoldLoad=*/true,/*UnfoldStore=*/false, 1275 NewMIs)) { 1276 DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1277 return false; 1278 } 1279 assert(NewMIs.size() == 2 && 1280 "Unfolded a load into multiple instructions!"); 1281 // The load was previously folded, so this is the only use. 1282 NewMIs[1]->addRegisterKilled(Reg, TRI); 1283 1284 // Tentatively insert the instructions into the block so that they 1285 // look "normal" to the transformation logic. 1286 MBB->insert(mi, NewMIs[0]); 1287 MBB->insert(mi, NewMIs[1]); 1288 1289 DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] 1290 << "2addr: NEW INST: " << *NewMIs[1]); 1291 1292 // Transform the instruction, now that it no longer has a load. 1293 unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA); 1294 unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB); 1295 MachineBasicBlock::iterator NewMI = NewMIs[1]; 1296 bool TransformResult = 1297 tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true); 1298 (void)TransformResult; 1299 assert(!TransformResult && 1300 "tryInstructionTransform() should return false."); 1301 if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) { 1302 // Success, or at least we made an improvement. Keep the unfolded 1303 // instructions and discard the original. 1304 if (LV) { 1305 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 1306 MachineOperand &MO = MI.getOperand(i); 1307 if (MO.isReg() && 1308 TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 1309 if (MO.isUse()) { 1310 if (MO.isKill()) { 1311 if (NewMIs[0]->killsRegister(MO.getReg())) 1312 LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]); 1313 else { 1314 assert(NewMIs[1]->killsRegister(MO.getReg()) && 1315 "Kill missing after load unfold!"); 1316 LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]); 1317 } 1318 } 1319 } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) { 1320 if (NewMIs[1]->registerDefIsDead(MO.getReg())) 1321 LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]); 1322 else { 1323 assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && 1324 "Dead flag missing after load unfold!"); 1325 LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]); 1326 } 1327 } 1328 } 1329 } 1330 LV->addVirtualRegisterKilled(Reg, NewMIs[1]); 1331 } 1332 1333 SmallVector<unsigned, 4> OrigRegs; 1334 if (LIS) { 1335 for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), 1336 MOE = MI.operands_end(); MOI != MOE; ++MOI) { 1337 if (MOI->isReg()) 1338 OrigRegs.push_back(MOI->getReg()); 1339 } 1340 } 1341 1342 MI.eraseFromParent(); 1343 1344 // Update LiveIntervals. 1345 if (LIS) { 1346 MachineBasicBlock::iterator Begin(NewMIs[0]); 1347 MachineBasicBlock::iterator End(NewMIs[1]); 1348 LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs); 1349 } 1350 1351 mi = NewMIs[1]; 1352 } else { 1353 // Transforming didn't eliminate the tie and didn't lead to an 1354 // improvement. Clean up the unfolded instructions and keep the 1355 // original. 1356 DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1357 NewMIs[0]->eraseFromParent(); 1358 NewMIs[1]->eraseFromParent(); 1359 } 1360 } 1361 } 1362 } 1363 1364 return false; 1365 } 1366 1367 // Collect tied operands of MI that need to be handled. 1368 // Rewrite trivial cases immediately. 1369 // Return true if any tied operands where found, including the trivial ones. 1370 bool TwoAddressInstructionPass:: 1371 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) { 1372 const MCInstrDesc &MCID = MI->getDesc(); 1373 bool AnyOps = false; 1374 unsigned NumOps = MI->getNumOperands(); 1375 1376 for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { 1377 unsigned DstIdx = 0; 1378 if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx)) 1379 continue; 1380 AnyOps = true; 1381 MachineOperand &SrcMO = MI->getOperand(SrcIdx); 1382 MachineOperand &DstMO = MI->getOperand(DstIdx); 1383 unsigned SrcReg = SrcMO.getReg(); 1384 unsigned DstReg = DstMO.getReg(); 1385 // Tied constraint already satisfied? 1386 if (SrcReg == DstReg) 1387 continue; 1388 1389 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); 1390 1391 // Deal with <undef> uses immediately - simply rewrite the src operand. 1392 if (SrcMO.isUndef() && !DstMO.getSubReg()) { 1393 // Constrain the DstReg register class if required. 1394 if (TargetRegisterInfo::isVirtualRegister(DstReg)) 1395 if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, 1396 TRI, *MF)) 1397 MRI->constrainRegClass(DstReg, RC); 1398 SrcMO.setReg(DstReg); 1399 SrcMO.setSubReg(0); 1400 DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); 1401 continue; 1402 } 1403 TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx)); 1404 } 1405 return AnyOps; 1406 } 1407 1408 // Process a list of tied MI operands that all use the same source register. 1409 // The tied pairs are of the form (SrcIdx, DstIdx). 1410 void 1411 TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, 1412 TiedPairList &TiedPairs, 1413 unsigned &Dist) { 1414 bool IsEarlyClobber = false; 1415 for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1416 const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second); 1417 IsEarlyClobber |= DstMO.isEarlyClobber(); 1418 } 1419 1420 bool RemovedKillFlag = false; 1421 bool AllUsesCopied = true; 1422 unsigned LastCopiedReg = 0; 1423 SlotIndex LastCopyIdx; 1424 unsigned RegB = 0; 1425 unsigned SubRegB = 0; 1426 for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1427 unsigned SrcIdx = TiedPairs[tpi].first; 1428 unsigned DstIdx = TiedPairs[tpi].second; 1429 1430 const MachineOperand &DstMO = MI->getOperand(DstIdx); 1431 unsigned RegA = DstMO.getReg(); 1432 1433 // Grab RegB from the instruction because it may have changed if the 1434 // instruction was commuted. 1435 RegB = MI->getOperand(SrcIdx).getReg(); 1436 SubRegB = MI->getOperand(SrcIdx).getSubReg(); 1437 1438 if (RegA == RegB) { 1439 // The register is tied to multiple destinations (or else we would 1440 // not have continued this far), but this use of the register 1441 // already matches the tied destination. Leave it. 1442 AllUsesCopied = false; 1443 continue; 1444 } 1445 LastCopiedReg = RegA; 1446 1447 assert(TargetRegisterInfo::isVirtualRegister(RegB) && 1448 "cannot make instruction into two-address form"); 1449 1450 #ifndef NDEBUG 1451 // First, verify that we don't have a use of "a" in the instruction 1452 // (a = b + a for example) because our transformation will not 1453 // work. This should never occur because we are in SSA form. 1454 for (unsigned i = 0; i != MI->getNumOperands(); ++i) 1455 assert(i == DstIdx || 1456 !MI->getOperand(i).isReg() || 1457 MI->getOperand(i).getReg() != RegA); 1458 #endif 1459 1460 // Emit a copy. 1461 MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1462 TII->get(TargetOpcode::COPY), RegA); 1463 // If this operand is folding a truncation, the truncation now moves to the 1464 // copy so that the register classes remain valid for the operands. 1465 MIB.addReg(RegB, 0, SubRegB); 1466 const TargetRegisterClass *RC = MRI->getRegClass(RegB); 1467 if (SubRegB) { 1468 if (TargetRegisterInfo::isVirtualRegister(RegA)) { 1469 assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), 1470 SubRegB) && 1471 "tied subregister must be a truncation"); 1472 // The superreg class will not be used to constrain the subreg class. 1473 RC = nullptr; 1474 } 1475 else { 1476 assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) 1477 && "tied subregister must be a truncation"); 1478 } 1479 } 1480 1481 // Update DistanceMap. 1482 MachineBasicBlock::iterator PrevMI = MI; 1483 --PrevMI; 1484 DistanceMap.insert(std::make_pair(PrevMI, Dist)); 1485 DistanceMap[MI] = ++Dist; 1486 1487 if (LIS) { 1488 LastCopyIdx = LIS->InsertMachineInstrInMaps(PrevMI).getRegSlot(); 1489 1490 if (TargetRegisterInfo::isVirtualRegister(RegA)) { 1491 LiveInterval &LI = LIS->getInterval(RegA); 1492 VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1493 SlotIndex endIdx = 1494 LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber); 1495 LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI)); 1496 } 1497 } 1498 1499 DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); 1500 1501 MachineOperand &MO = MI->getOperand(SrcIdx); 1502 assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && 1503 "inconsistent operand info for 2-reg pass"); 1504 if (MO.isKill()) { 1505 MO.setIsKill(false); 1506 RemovedKillFlag = true; 1507 } 1508 1509 // Make sure regA is a legal regclass for the SrcIdx operand. 1510 if (TargetRegisterInfo::isVirtualRegister(RegA) && 1511 TargetRegisterInfo::isVirtualRegister(RegB)) 1512 MRI->constrainRegClass(RegA, RC); 1513 MO.setReg(RegA); 1514 // The getMatchingSuper asserts guarantee that the register class projected 1515 // by SubRegB is compatible with RegA with no subregister. So regardless of 1516 // whether the dest oper writes a subreg, the source oper should not. 1517 MO.setSubReg(0); 1518 1519 // Propagate SrcRegMap. 1520 SrcRegMap[RegA] = RegB; 1521 } 1522 1523 1524 if (AllUsesCopied) { 1525 if (!IsEarlyClobber) { 1526 // Replace other (un-tied) uses of regB with LastCopiedReg. 1527 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1528 MachineOperand &MO = MI->getOperand(i); 1529 if (MO.isReg() && MO.getReg() == RegB && MO.getSubReg() == SubRegB && 1530 MO.isUse()) { 1531 if (MO.isKill()) { 1532 MO.setIsKill(false); 1533 RemovedKillFlag = true; 1534 } 1535 MO.setReg(LastCopiedReg); 1536 MO.setSubReg(0); 1537 } 1538 } 1539 } 1540 1541 // Update live variables for regB. 1542 if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(MI)) { 1543 MachineBasicBlock::iterator PrevMI = MI; 1544 --PrevMI; 1545 LV->addVirtualRegisterKilled(RegB, PrevMI); 1546 } 1547 1548 // Update LiveIntervals. 1549 if (LIS) { 1550 LiveInterval &LI = LIS->getInterval(RegB); 1551 SlotIndex MIIdx = LIS->getInstructionIndex(MI); 1552 LiveInterval::const_iterator I = LI.find(MIIdx); 1553 assert(I != LI.end() && "RegB must be live-in to use."); 1554 1555 SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber); 1556 if (I->end == UseIdx) 1557 LI.removeSegment(LastCopyIdx, UseIdx); 1558 } 1559 1560 } else if (RemovedKillFlag) { 1561 // Some tied uses of regB matched their destination registers, so 1562 // regB is still used in this instruction, but a kill flag was 1563 // removed from a different tied use of regB, so now we need to add 1564 // a kill flag to one of the remaining uses of regB. 1565 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1566 MachineOperand &MO = MI->getOperand(i); 1567 if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { 1568 MO.setIsKill(true); 1569 break; 1570 } 1571 } 1572 } 1573 } 1574 1575 /// runOnMachineFunction - Reduce two-address instructions to two operands. 1576 /// 1577 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { 1578 MF = &Func; 1579 const TargetMachine &TM = MF->getTarget(); 1580 MRI = &MF->getRegInfo(); 1581 TII = MF->getSubtarget().getInstrInfo(); 1582 TRI = MF->getSubtarget().getRegisterInfo(); 1583 InstrItins = MF->getSubtarget().getInstrItineraryData(); 1584 LV = getAnalysisIfAvailable<LiveVariables>(); 1585 LIS = getAnalysisIfAvailable<LiveIntervals>(); 1586 AA = &getAnalysis<AliasAnalysis>(); 1587 OptLevel = TM.getOptLevel(); 1588 1589 bool MadeChange = false; 1590 1591 DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 1592 DEBUG(dbgs() << "********** Function: " 1593 << MF->getName() << '\n'); 1594 1595 // This pass takes the function out of SSA form. 1596 MRI->leaveSSA(); 1597 1598 TiedOperandMap TiedOperands; 1599 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1600 MBBI != MBBE; ++MBBI) { 1601 MBB = MBBI; 1602 unsigned Dist = 0; 1603 DistanceMap.clear(); 1604 SrcRegMap.clear(); 1605 DstRegMap.clear(); 1606 Processed.clear(); 1607 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); 1608 mi != me; ) { 1609 MachineBasicBlock::iterator nmi = std::next(mi); 1610 if (mi->isDebugValue()) { 1611 mi = nmi; 1612 continue; 1613 } 1614 1615 // Expand REG_SEQUENCE instructions. This will position mi at the first 1616 // expanded instruction. 1617 if (mi->isRegSequence()) 1618 eliminateRegSequence(mi); 1619 1620 DistanceMap.insert(std::make_pair(mi, ++Dist)); 1621 1622 processCopy(&*mi); 1623 1624 // First scan through all the tied register uses in this instruction 1625 // and record a list of pairs of tied operands for each register. 1626 if (!collectTiedOperands(mi, TiedOperands)) { 1627 mi = nmi; 1628 continue; 1629 } 1630 1631 ++NumTwoAddressInstrs; 1632 MadeChange = true; 1633 DEBUG(dbgs() << '\t' << *mi); 1634 1635 // If the instruction has a single pair of tied operands, try some 1636 // transformations that may either eliminate the tied operands or 1637 // improve the opportunities for coalescing away the register copy. 1638 if (TiedOperands.size() == 1) { 1639 SmallVectorImpl<std::pair<unsigned, unsigned> > &TiedPairs 1640 = TiedOperands.begin()->second; 1641 if (TiedPairs.size() == 1) { 1642 unsigned SrcIdx = TiedPairs[0].first; 1643 unsigned DstIdx = TiedPairs[0].second; 1644 unsigned SrcReg = mi->getOperand(SrcIdx).getReg(); 1645 unsigned DstReg = mi->getOperand(DstIdx).getReg(); 1646 if (SrcReg != DstReg && 1647 tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { 1648 // The tied operands have been eliminated or shifted further down the 1649 // block to ease elimination. Continue processing with 'nmi'. 1650 TiedOperands.clear(); 1651 mi = nmi; 1652 continue; 1653 } 1654 } 1655 } 1656 1657 // Now iterate over the information collected above. 1658 for (TiedOperandMap::iterator OI = TiedOperands.begin(), 1659 OE = TiedOperands.end(); OI != OE; ++OI) { 1660 processTiedPairs(mi, OI->second, Dist); 1661 DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); 1662 } 1663 1664 // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. 1665 if (mi->isInsertSubreg()) { 1666 // From %reg = INSERT_SUBREG %reg, %subreg, subidx 1667 // To %reg:subidx = COPY %subreg 1668 unsigned SubIdx = mi->getOperand(3).getImm(); 1669 mi->RemoveOperand(3); 1670 assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); 1671 mi->getOperand(0).setSubReg(SubIdx); 1672 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef()); 1673 mi->RemoveOperand(1); 1674 mi->setDesc(TII->get(TargetOpcode::COPY)); 1675 DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); 1676 } 1677 1678 // Clear TiedOperands here instead of at the top of the loop 1679 // since most instructions do not have tied operands. 1680 TiedOperands.clear(); 1681 mi = nmi; 1682 } 1683 } 1684 1685 if (LIS) 1686 MF->verify(this, "After two-address instruction pass"); 1687 1688 return MadeChange; 1689 } 1690 1691 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. 1692 /// 1693 /// The instruction is turned into a sequence of sub-register copies: 1694 /// 1695 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 1696 /// 1697 /// Becomes: 1698 /// 1699 /// %dst:ssub0<def,undef> = COPY %v1 1700 /// %dst:ssub1<def> = COPY %v2 1701 /// 1702 void TwoAddressInstructionPass:: 1703 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) { 1704 MachineInstr *MI = MBBI; 1705 unsigned DstReg = MI->getOperand(0).getReg(); 1706 if (MI->getOperand(0).getSubReg() || 1707 TargetRegisterInfo::isPhysicalRegister(DstReg) || 1708 !(MI->getNumOperands() & 1)) { 1709 DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); 1710 llvm_unreachable(nullptr); 1711 } 1712 1713 SmallVector<unsigned, 4> OrigRegs; 1714 if (LIS) { 1715 OrigRegs.push_back(MI->getOperand(0).getReg()); 1716 for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) 1717 OrigRegs.push_back(MI->getOperand(i).getReg()); 1718 } 1719 1720 bool DefEmitted = false; 1721 for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { 1722 MachineOperand &UseMO = MI->getOperand(i); 1723 unsigned SrcReg = UseMO.getReg(); 1724 unsigned SubIdx = MI->getOperand(i+1).getImm(); 1725 // Nothing needs to be inserted for <undef> operands. 1726 if (UseMO.isUndef()) 1727 continue; 1728 1729 // Defer any kill flag to the last operand using SrcReg. Otherwise, we 1730 // might insert a COPY that uses SrcReg after is was killed. 1731 bool isKill = UseMO.isKill(); 1732 if (isKill) 1733 for (unsigned j = i + 2; j < e; j += 2) 1734 if (MI->getOperand(j).getReg() == SrcReg) { 1735 MI->getOperand(j).setIsKill(); 1736 UseMO.setIsKill(false); 1737 isKill = false; 1738 break; 1739 } 1740 1741 // Insert the sub-register copy. 1742 MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1743 TII->get(TargetOpcode::COPY)) 1744 .addReg(DstReg, RegState::Define, SubIdx) 1745 .addOperand(UseMO); 1746 1747 // The first def needs an <undef> flag because there is no live register 1748 // before it. 1749 if (!DefEmitted) { 1750 CopyMI->getOperand(0).setIsUndef(true); 1751 // Return an iterator pointing to the first inserted instr. 1752 MBBI = CopyMI; 1753 } 1754 DefEmitted = true; 1755 1756 // Update LiveVariables' kill info. 1757 if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg)) 1758 LV->replaceKillInstruction(SrcReg, MI, CopyMI); 1759 1760 DEBUG(dbgs() << "Inserted: " << *CopyMI); 1761 } 1762 1763 MachineBasicBlock::iterator EndMBBI = 1764 std::next(MachineBasicBlock::iterator(MI)); 1765 1766 if (!DefEmitted) { 1767 DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF"); 1768 MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 1769 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 1770 MI->RemoveOperand(j); 1771 } else { 1772 DEBUG(dbgs() << "Eliminated: " << *MI); 1773 MI->eraseFromParent(); 1774 } 1775 1776 // Udpate LiveIntervals. 1777 if (LIS) 1778 LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs); 1779 } 1780