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