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