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