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