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