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