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