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