TwoAddressInstructionPass.cpp revision d163917fd834376aee17d5c37f6d47cafed09087
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/Target/TargetRegisterInfo.h" 38#include "llvm/Target/TargetInstrInfo.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Target/TargetOptions.h" 41#include "llvm/Support/Compiler.h" 42#include "llvm/Support/Debug.h" 43#include "llvm/ADT/BitVector.h" 44#include "llvm/ADT/DenseMap.h" 45#include "llvm/ADT/SmallSet.h" 46#include "llvm/ADT/Statistic.h" 47#include "llvm/ADT/STLExtras.h" 48using namespace llvm; 49 50STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 51STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 52STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 53STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 54STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 55STATISTIC(NumReMats, "Number of instructions re-materialized"); 56STATISTIC(NumDeletes, "Number of dead instructions deleted"); 57 58namespace { 59 class VISIBILITY_HIDDEN TwoAddressInstructionPass 60 : public MachineFunctionPass { 61 const TargetInstrInfo *TII; 62 const TargetRegisterInfo *TRI; 63 MachineRegisterInfo *MRI; 64 LiveVariables *LV; 65 66 // DistanceMap - Keep track the distance of a MI from the start of the 67 // current basic block. 68 DenseMap<MachineInstr*, unsigned> DistanceMap; 69 70 // SrcRegMap - A map from virtual registers to physical registers which 71 // are likely targets to be coalesced to due to copies from physical 72 // registers to virtual registers. e.g. v1024 = move r0. 73 DenseMap<unsigned, unsigned> SrcRegMap; 74 75 // DstRegMap - A map from virtual registers to physical registers which 76 // are likely targets to be coalesced to due to copies to physical 77 // registers from virtual registers. e.g. r1 = move v1024. 78 DenseMap<unsigned, unsigned> DstRegMap; 79 80 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, 81 unsigned Reg, 82 MachineBasicBlock::iterator OldPos); 83 84 bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC, 85 MachineInstr *MI, MachineInstr *DefMI, 86 MachineBasicBlock *MBB, unsigned Loc); 87 88 bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist, 89 unsigned &LastDef); 90 91 MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB, 92 unsigned Dist); 93 94 bool isProfitableToCommute(unsigned regB, unsigned regC, 95 MachineInstr *MI, MachineBasicBlock *MBB, 96 unsigned Dist); 97 98 bool CommuteInstruction(MachineBasicBlock::iterator &mi, 99 MachineFunction::iterator &mbbi, 100 unsigned RegB, unsigned RegC, unsigned Dist); 101 102 bool isProfitableToConv3Addr(unsigned RegA); 103 104 bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 105 MachineBasicBlock::iterator &nmi, 106 MachineFunction::iterator &mbbi, 107 unsigned RegB, unsigned Dist); 108 109 typedef std::pair<std::pair<unsigned, bool>, MachineInstr*> NewKill; 110 bool canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills, 111 SmallVector<NewKill, 4> &NewKills, 112 MachineBasicBlock *MBB, unsigned Dist); 113 bool DeleteUnusedInstr(MachineBasicBlock::iterator &mi, 114 MachineBasicBlock::iterator &nmi, 115 MachineFunction::iterator &mbbi, 116 unsigned regB, unsigned regBIdx, unsigned Dist); 117 118 void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB, 119 SmallPtrSet<MachineInstr*, 8> &Processed); 120 121 public: 122 static char ID; // Pass identification, replacement for typeid 123 TwoAddressInstructionPass() : MachineFunctionPass(&ID) {} 124 125 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 126 AU.setPreservesCFG(); 127 AU.addPreserved<LiveVariables>(); 128 AU.addPreservedID(MachineLoopInfoID); 129 AU.addPreservedID(MachineDominatorsID); 130 if (StrongPHIElim) 131 AU.addPreservedID(StrongPHIEliminationID); 132 else 133 AU.addPreservedID(PHIEliminationID); 134 MachineFunctionPass::getAnalysisUsage(AU); 135 } 136 137 /// runOnMachineFunction - Pass entry point. 138 bool runOnMachineFunction(MachineFunction&); 139 }; 140} 141 142char TwoAddressInstructionPass::ID = 0; 143static RegisterPass<TwoAddressInstructionPass> 144X("twoaddressinstruction", "Two-Address instruction pass"); 145 146const PassInfo *const llvm::TwoAddressInstructionPassID = &X; 147 148/// Sink3AddrInstruction - A two-address instruction has been converted to a 149/// three-address instruction to avoid clobbering a register. Try to sink it 150/// past the instruction that would kill the above mentioned register to reduce 151/// register pressure. 152bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, 153 MachineInstr *MI, unsigned SavedReg, 154 MachineBasicBlock::iterator OldPos) { 155 // Check if it's safe to move this instruction. 156 bool SeenStore = true; // Be conservative. 157 if (!MI->isSafeToMove(TII, SeenStore)) 158 return false; 159 160 unsigned DefReg = 0; 161 SmallSet<unsigned, 4> UseRegs; 162 163 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 164 const MachineOperand &MO = MI->getOperand(i); 165 if (!MO.isReg()) 166 continue; 167 unsigned MOReg = MO.getReg(); 168 if (!MOReg) 169 continue; 170 if (MO.isUse() && MOReg != SavedReg) 171 UseRegs.insert(MO.getReg()); 172 if (!MO.isDef()) 173 continue; 174 if (MO.isImplicit()) 175 // Don't try to move it if it implicitly defines a register. 176 return false; 177 if (DefReg) 178 // For now, don't move any instructions that define multiple registers. 179 return false; 180 DefReg = MO.getReg(); 181 } 182 183 // Find the instruction that kills SavedReg. 184 MachineInstr *KillMI = NULL; 185 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), 186 UE = MRI->use_end(); UI != UE; ++UI) { 187 MachineOperand &UseMO = UI.getOperand(); 188 if (!UseMO.isKill()) 189 continue; 190 KillMI = UseMO.getParent(); 191 break; 192 } 193 194 if (!KillMI || KillMI->getParent() != MBB || KillMI == MI) 195 return false; 196 197 // If any of the definitions are used by another instruction between the 198 // position and the kill use, then it's not safe to sink it. 199 // 200 // FIXME: This can be sped up if there is an easy way to query whether an 201 // instruction is before or after another instruction. Then we can use 202 // MachineRegisterInfo def / use instead. 203 MachineOperand *KillMO = NULL; 204 MachineBasicBlock::iterator KillPos = KillMI; 205 ++KillPos; 206 207 unsigned NumVisited = 0; 208 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { 209 MachineInstr *OtherMI = I; 210 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 211 return false; 212 ++NumVisited; 213 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 214 MachineOperand &MO = OtherMI->getOperand(i); 215 if (!MO.isReg()) 216 continue; 217 unsigned MOReg = MO.getReg(); 218 if (!MOReg) 219 continue; 220 if (DefReg == MOReg) 221 return false; 222 223 if (MO.isKill()) { 224 if (OtherMI == KillMI && MOReg == SavedReg) 225 // Save the operand that kills the register. We want to unset the kill 226 // marker if we can sink MI past it. 227 KillMO = &MO; 228 else if (UseRegs.count(MOReg)) 229 // One of the uses is killed before the destination. 230 return false; 231 } 232 } 233 } 234 235 // Update kill and LV information. 236 KillMO->setIsKill(false); 237 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 238 KillMO->setIsKill(true); 239 240 if (LV) 241 LV->replaceKillInstruction(SavedReg, KillMI, MI); 242 243 // Move instruction to its destination. 244 MBB->remove(MI); 245 MBB->insert(KillPos, MI); 246 247 ++Num3AddrSunk; 248 return true; 249} 250 251/// isTwoAddrUse - Return true if the specified MI is using the specified 252/// register as a two-address operand. 253static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { 254 const TargetInstrDesc &TID = UseMI->getDesc(); 255 for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) { 256 MachineOperand &MO = UseMI->getOperand(i); 257 if (MO.isReg() && MO.getReg() == Reg && 258 (MO.isDef() || UseMI->isRegTiedToDefOperand(i))) 259 // Earlier use is a two-address one. 260 return true; 261 } 262 return false; 263} 264 265/// isProfitableToReMat - Return true if the heuristics determines it is likely 266/// to be profitable to re-materialize the definition of Reg rather than copy 267/// the register. 268bool 269TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, 270 const TargetRegisterClass *RC, 271 MachineInstr *MI, MachineInstr *DefMI, 272 MachineBasicBlock *MBB, unsigned Loc) { 273 bool OtherUse = false; 274 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 275 UE = MRI->use_end(); UI != UE; ++UI) { 276 MachineOperand &UseMO = UI.getOperand(); 277 MachineInstr *UseMI = UseMO.getParent(); 278 MachineBasicBlock *UseMBB = UseMI->getParent(); 279 if (UseMBB == MBB) { 280 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 281 if (DI != DistanceMap.end() && DI->second == Loc) 282 continue; // Current use. 283 OtherUse = true; 284 // There is at least one other use in the MBB that will clobber the 285 // register. 286 if (isTwoAddrUse(UseMI, Reg)) 287 return true; 288 } 289 } 290 291 // If other uses in MBB are not two-address uses, then don't remat. 292 if (OtherUse) 293 return false; 294 295 // No other uses in the same block, remat if it's defined in the same 296 // block so it does not unnecessarily extend the live range. 297 return MBB == DefMI->getParent(); 298} 299 300/// NoUseAfterLastDef - Return true if there are no intervening uses between the 301/// last instruction in the MBB that defines the specified register and the 302/// two-address instruction which is being processed. It also returns the last 303/// def location by reference 304bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg, 305 MachineBasicBlock *MBB, unsigned Dist, 306 unsigned &LastDef) { 307 LastDef = 0; 308 unsigned LastUse = Dist; 309 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 310 E = MRI->reg_end(); I != E; ++I) { 311 MachineOperand &MO = I.getOperand(); 312 MachineInstr *MI = MO.getParent(); 313 if (MI->getParent() != MBB) 314 continue; 315 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 316 if (DI == DistanceMap.end()) 317 continue; 318 if (MO.isUse() && DI->second < LastUse) 319 LastUse = DI->second; 320 if (MO.isDef() && DI->second > LastDef) 321 LastDef = DI->second; 322 } 323 324 return !(LastUse > LastDef && LastUse < Dist); 325} 326 327MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg, 328 MachineBasicBlock *MBB, 329 unsigned Dist) { 330 unsigned LastUseDist = 0; 331 MachineInstr *LastUse = 0; 332 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 333 E = MRI->reg_end(); I != E; ++I) { 334 MachineOperand &MO = I.getOperand(); 335 MachineInstr *MI = MO.getParent(); 336 if (MI->getParent() != MBB) 337 continue; 338 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 339 if (DI == DistanceMap.end()) 340 continue; 341 if (DI->second >= Dist) 342 continue; 343 344 if (MO.isUse() && DI->second > LastUseDist) { 345 LastUse = DI->first; 346 LastUseDist = DI->second; 347 } 348 } 349 return LastUse; 350} 351 352/// isCopyToReg - Return true if the specified MI is a copy instruction or 353/// a extract_subreg instruction. It also returns the source and destination 354/// registers and whether they are physical registers by reference. 355static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 356 unsigned &SrcReg, unsigned &DstReg, 357 bool &IsSrcPhys, bool &IsDstPhys) { 358 SrcReg = 0; 359 DstReg = 0; 360 unsigned SrcSubIdx, DstSubIdx; 361 if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { 362 if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 363 DstReg = MI.getOperand(0).getReg(); 364 SrcReg = MI.getOperand(1).getReg(); 365 } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 366 DstReg = MI.getOperand(0).getReg(); 367 SrcReg = MI.getOperand(2).getReg(); 368 } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 369 DstReg = MI.getOperand(0).getReg(); 370 SrcReg = MI.getOperand(2).getReg(); 371 } 372 } 373 374 if (DstReg) { 375 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 376 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 377 return true; 378 } 379 return false; 380} 381 382/// isKilled - Test if the given register value, which is used by the given 383/// instruction, is killed by the given instruction. This looks through 384/// coalescable copies to see if the original value is potentially not killed. 385/// 386/// For example, in this code: 387/// 388/// %reg1034 = copy %reg1024 389/// %reg1035 = copy %reg1025<kill> 390/// %reg1036 = add %reg1034<kill>, %reg1035<kill> 391/// 392/// %reg1034 is not considered to be killed, since it is copied from a 393/// register which is not killed. Treating it as not killed lets the 394/// normal heuristics commute the (two-address) add, which lets 395/// coalescing eliminate the extra copy. 396/// 397static bool isKilled(MachineInstr &MI, unsigned Reg, 398 const MachineRegisterInfo *MRI, 399 const TargetInstrInfo *TII) { 400 MachineInstr *DefMI = &MI; 401 for (;;) { 402 if (!DefMI->killsRegister(Reg)) 403 return false; 404 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 405 return true; 406 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 407 // If there are multiple defs, we can't do a simple analysis, so just 408 // go with what the kill flag says. 409 if (next(Begin) != MRI->def_end()) 410 return true; 411 DefMI = &*Begin; 412 bool IsSrcPhys, IsDstPhys; 413 unsigned SrcReg, DstReg; 414 // If the def is something other than a copy, then it isn't going to 415 // be coalesced, so follow the kill flag. 416 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 417 return true; 418 Reg = SrcReg; 419 } 420} 421 422/// isTwoAddrUse - Return true if the specified MI uses the specified register 423/// as a two-address use. If so, return the destination register by reference. 424static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 425 const TargetInstrDesc &TID = MI.getDesc(); 426 unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM) 427 ? MI.getNumOperands() : TID.getNumOperands(); 428 for (unsigned i = 0; i != NumOps; ++i) { 429 const MachineOperand &MO = MI.getOperand(i); 430 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 431 continue; 432 unsigned ti; 433 if (MI.isRegTiedToDefOperand(i, &ti)) { 434 DstReg = MI.getOperand(ti).getReg(); 435 return true; 436 } 437 } 438 return false; 439} 440 441/// findOnlyInterestingUse - Given a register, if has a single in-basic block 442/// use, return the use instruction if it's a copy or a two-address use. 443static 444MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 445 MachineRegisterInfo *MRI, 446 const TargetInstrInfo *TII, 447 bool &IsCopy, 448 unsigned &DstReg, bool &IsDstPhys) { 449 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg); 450 if (UI == MRI->use_end()) 451 return 0; 452 MachineInstr &UseMI = *UI; 453 if (++UI != MRI->use_end()) 454 // More than one use. 455 return 0; 456 if (UseMI.getParent() != MBB) 457 return 0; 458 unsigned SrcReg; 459 bool IsSrcPhys; 460 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 461 IsCopy = true; 462 return &UseMI; 463 } 464 IsDstPhys = false; 465 if (isTwoAddrUse(UseMI, Reg, DstReg)) { 466 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 467 return &UseMI; 468 } 469 return 0; 470} 471 472/// getMappedReg - Return the physical register the specified virtual register 473/// might be mapped to. 474static unsigned 475getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 476 while (TargetRegisterInfo::isVirtualRegister(Reg)) { 477 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 478 if (SI == RegMap.end()) 479 return 0; 480 Reg = SI->second; 481 } 482 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 483 return Reg; 484 return 0; 485} 486 487/// regsAreCompatible - Return true if the two registers are equal or aliased. 488/// 489static bool 490regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 491 if (RegA == RegB) 492 return true; 493 if (!RegA || !RegB) 494 return false; 495 return TRI->regsOverlap(RegA, RegB); 496} 497 498 499/// isProfitableToReMat - Return true if it's potentially profitable to commute 500/// the two-address instruction that's being processed. 501bool 502TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, 503 MachineInstr *MI, MachineBasicBlock *MBB, 504 unsigned Dist) { 505 // Determine if it's profitable to commute this two address instruction. In 506 // general, we want no uses between this instruction and the definition of 507 // the two-address register. 508 // e.g. 509 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 510 // %reg1029<def> = MOV8rr %reg1028 511 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 512 // insert => %reg1030<def> = MOV8rr %reg1028 513 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 514 // In this case, it might not be possible to coalesce the second MOV8rr 515 // instruction if the first one is coalesced. So it would be profitable to 516 // commute it: 517 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 518 // %reg1029<def> = MOV8rr %reg1028 519 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 520 // insert => %reg1030<def> = MOV8rr %reg1029 521 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 522 523 if (!MI->killsRegister(regC)) 524 return false; 525 526 // Ok, we have something like: 527 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 528 // let's see if it's worth commuting it. 529 530 // Look for situations like this: 531 // %reg1024<def> = MOV r1 532 // %reg1025<def> = MOV r0 533 // %reg1026<def> = ADD %reg1024, %reg1025 534 // r0 = MOV %reg1026 535 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 536 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 537 unsigned FromRegC = getMappedReg(regC, SrcRegMap); 538 unsigned ToRegB = getMappedReg(regB, DstRegMap); 539 unsigned ToRegC = getMappedReg(regC, DstRegMap); 540 if (!regsAreCompatible(FromRegB, ToRegB, TRI) && 541 (regsAreCompatible(FromRegB, ToRegC, TRI) || 542 regsAreCompatible(FromRegC, ToRegB, TRI))) 543 return true; 544 545 // If there is a use of regC between its last def (could be livein) and this 546 // instruction, then bail. 547 unsigned LastDefC = 0; 548 if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC)) 549 return false; 550 551 // If there is a use of regB between its last def (could be livein) and this 552 // instruction, then go ahead and make this transformation. 553 unsigned LastDefB = 0; 554 if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB)) 555 return true; 556 557 // Since there are no intervening uses for both registers, then commute 558 // if the def of regC is closer. Its live interval is shorter. 559 return LastDefB && LastDefC && LastDefC > LastDefB; 560} 561 562/// CommuteInstruction - Commute a two-address instruction and update the basic 563/// block, distance map, and live variables if needed. Return true if it is 564/// successful. 565bool 566TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, 567 MachineFunction::iterator &mbbi, 568 unsigned RegB, unsigned RegC, unsigned Dist) { 569 MachineInstr *MI = mi; 570 DEBUG(errs() << "2addr: COMMUTING : " << *MI); 571 MachineInstr *NewMI = TII->commuteInstruction(MI); 572 573 if (NewMI == 0) { 574 DEBUG(errs() << "2addr: COMMUTING FAILED!\n"); 575 return false; 576 } 577 578 DEBUG(errs() << "2addr: COMMUTED TO: " << *NewMI); 579 // If the instruction changed to commute it, update livevar. 580 if (NewMI != MI) { 581 if (LV) 582 // Update live variables 583 LV->replaceKillInstruction(RegC, MI, NewMI); 584 585 mbbi->insert(mi, NewMI); // Insert the new inst 586 mbbi->erase(mi); // Nuke the old inst. 587 mi = NewMI; 588 DistanceMap.insert(std::make_pair(NewMI, Dist)); 589 } 590 591 // Update source register map. 592 unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 593 if (FromRegC) { 594 unsigned RegA = MI->getOperand(0).getReg(); 595 SrcRegMap[RegA] = FromRegC; 596 } 597 598 return true; 599} 600 601/// isProfitableToConv3Addr - Return true if it is profitable to convert the 602/// given 2-address instruction to a 3-address one. 603bool 604TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) { 605 // Look for situations like this: 606 // %reg1024<def> = MOV r1 607 // %reg1025<def> = MOV r0 608 // %reg1026<def> = ADD %reg1024, %reg1025 609 // r2 = MOV %reg1026 610 // Turn ADD into a 3-address instruction to avoid a copy. 611 unsigned FromRegA = getMappedReg(RegA, SrcRegMap); 612 unsigned ToRegA = getMappedReg(RegA, DstRegMap); 613 return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI)); 614} 615 616/// ConvertInstTo3Addr - Convert the specified two-address instruction into a 617/// three address one. Return true if this transformation was successful. 618bool 619TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 620 MachineBasicBlock::iterator &nmi, 621 MachineFunction::iterator &mbbi, 622 unsigned RegB, unsigned Dist) { 623 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); 624 if (NewMI) { 625 DEBUG(errs() << "2addr: CONVERTING 2-ADDR: " << *mi); 626 DEBUG(errs() << "2addr: TO 3-ADDR: " << *NewMI); 627 bool Sunk = false; 628 629 if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 630 // FIXME: Temporary workaround. If the new instruction doesn't 631 // uses RegB, convertToThreeAddress must have created more 632 // then one instruction. 633 Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi); 634 635 mbbi->erase(mi); // Nuke the old inst. 636 637 if (!Sunk) { 638 DistanceMap.insert(std::make_pair(NewMI, Dist)); 639 mi = NewMI; 640 nmi = next(mi); 641 } 642 return true; 643 } 644 645 return false; 646} 647 648/// ProcessCopy - If the specified instruction is not yet processed, process it 649/// if it's a copy. For a copy instruction, we find the physical registers the 650/// source and destination registers might be mapped to. These are kept in 651/// point-to maps used to determine future optimizations. e.g. 652/// v1024 = mov r0 653/// v1025 = mov r1 654/// v1026 = add v1024, v1025 655/// r1 = mov r1026 656/// If 'add' is a two-address instruction, v1024, v1026 are both potentially 657/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 658/// potentially joined with r1 on the output side. It's worthwhile to commute 659/// 'add' to eliminate a copy. 660void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, 661 MachineBasicBlock *MBB, 662 SmallPtrSet<MachineInstr*, 8> &Processed) { 663 if (Processed.count(MI)) 664 return; 665 666 bool IsSrcPhys, IsDstPhys; 667 unsigned SrcReg, DstReg; 668 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 669 return; 670 671 if (IsDstPhys && !IsSrcPhys) 672 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 673 else if (!IsDstPhys && IsSrcPhys) { 674 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 675 if (!isNew) 676 assert(SrcRegMap[DstReg] == SrcReg && 677 "Can't map to two src physical registers!"); 678 679 SmallVector<unsigned, 4> VirtRegPairs; 680 bool IsCopy = false; 681 unsigned NewReg = 0; 682 while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII, 683 IsCopy, NewReg, IsDstPhys)) { 684 if (IsCopy) { 685 if (!Processed.insert(UseMI)) 686 break; 687 } 688 689 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 690 if (DI != DistanceMap.end()) 691 // Earlier in the same MBB.Reached via a back edge. 692 break; 693 694 if (IsDstPhys) { 695 VirtRegPairs.push_back(NewReg); 696 break; 697 } 698 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second; 699 if (!isNew) 700 assert(SrcRegMap[NewReg] == DstReg && 701 "Can't map to two src physical registers!"); 702 VirtRegPairs.push_back(NewReg); 703 DstReg = NewReg; 704 } 705 706 if (!VirtRegPairs.empty()) { 707 unsigned ToReg = VirtRegPairs.back(); 708 VirtRegPairs.pop_back(); 709 while (!VirtRegPairs.empty()) { 710 unsigned FromReg = VirtRegPairs.back(); 711 VirtRegPairs.pop_back(); 712 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 713 if (!isNew) 714 assert(DstRegMap[FromReg] == ToReg && 715 "Can't map to two dst physical registers!"); 716 ToReg = FromReg; 717 } 718 } 719 } 720 721 Processed.insert(MI); 722} 723 724/// isSafeToDelete - If the specified instruction does not produce any side 725/// effects and all of its defs are dead, then it's safe to delete. 726static bool isSafeToDelete(MachineInstr *MI, unsigned Reg, 727 const TargetInstrInfo *TII, 728 SmallVector<unsigned, 4> &Kills) { 729 const TargetInstrDesc &TID = MI->getDesc(); 730 if (TID.mayStore() || TID.isCall()) 731 return false; 732 if (TID.isTerminator() || TID.hasUnmodeledSideEffects()) 733 return false; 734 735 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 736 MachineOperand &MO = MI->getOperand(i); 737 if (!MO.isReg()) 738 continue; 739 if (MO.isDef() && !MO.isDead()) 740 return false; 741 if (MO.isUse() && MO.getReg() != Reg && MO.isKill()) 742 Kills.push_back(MO.getReg()); 743 } 744 745 return true; 746} 747 748/// canUpdateDeletedKills - Check if all the registers listed in Kills are 749/// killed by instructions in MBB preceding the current instruction at 750/// position Dist. If so, return true and record information about the 751/// preceding kills in NewKills. 752bool TwoAddressInstructionPass:: 753canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills, 754 SmallVector<NewKill, 4> &NewKills, 755 MachineBasicBlock *MBB, unsigned Dist) { 756 while (!Kills.empty()) { 757 unsigned Kill = Kills.back(); 758 Kills.pop_back(); 759 if (TargetRegisterInfo::isPhysicalRegister(Kill)) 760 return false; 761 762 MachineInstr *LastKill = FindLastUseInMBB(Kill, MBB, Dist); 763 if (!LastKill) 764 return false; 765 766 bool isModRef = LastKill->modifiesRegister(Kill); 767 NewKills.push_back(std::make_pair(std::make_pair(Kill, isModRef), 768 LastKill)); 769 } 770 return true; 771} 772 773/// DeleteUnusedInstr - If an instruction with a tied register operand can 774/// be safely deleted, just delete it. 775bool 776TwoAddressInstructionPass::DeleteUnusedInstr(MachineBasicBlock::iterator &mi, 777 MachineBasicBlock::iterator &nmi, 778 MachineFunction::iterator &mbbi, 779 unsigned regB, unsigned regBIdx, 780 unsigned Dist) { 781 // Check if the instruction has no side effects and if all its defs are dead. 782 SmallVector<unsigned, 4> Kills; 783 if (!isSafeToDelete(mi, regB, TII, Kills)) 784 return false; 785 786 // If this instruction kills some virtual registers, we need to 787 // update the kill information. If it's not possible to do so, 788 // then bail out. 789 SmallVector<NewKill, 4> NewKills; 790 if (!canUpdateDeletedKills(Kills, NewKills, &*mbbi, Dist)) 791 return false; 792 793 if (LV) { 794 while (!NewKills.empty()) { 795 MachineInstr *NewKill = NewKills.back().second; 796 unsigned Kill = NewKills.back().first.first; 797 bool isDead = NewKills.back().first.second; 798 NewKills.pop_back(); 799 if (LV->removeVirtualRegisterKilled(Kill, mi)) { 800 if (isDead) 801 LV->addVirtualRegisterDead(Kill, NewKill); 802 else 803 LV->addVirtualRegisterKilled(Kill, NewKill); 804 } 805 } 806 807 // If regB was marked as a kill, update its Kills list. 808 if (mi->getOperand(regBIdx).isKill()) 809 LV->removeVirtualRegisterKilled(regB, mi); 810 } 811 812 mbbi->erase(mi); // Nuke the old inst. 813 mi = nmi; 814 return true; 815} 816 817/// runOnMachineFunction - Reduce two-address instructions to two operands. 818/// 819bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 820 DEBUG(errs() << "Machine Function\n"); 821 const TargetMachine &TM = MF.getTarget(); 822 MRI = &MF.getRegInfo(); 823 TII = TM.getInstrInfo(); 824 TRI = TM.getRegisterInfo(); 825 LV = getAnalysisIfAvailable<LiveVariables>(); 826 827 bool MadeChange = false; 828 829 DEBUG(errs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 830 DEBUG(errs() << "********** Function: " 831 << MF.getFunction()->getName() << '\n'); 832 833 // ReMatRegs - Keep track of the registers whose def's are remat'ed. 834 BitVector ReMatRegs; 835 ReMatRegs.resize(MRI->getLastVirtReg()+1); 836 837 SmallPtrSet<MachineInstr*, 8> Processed; 838 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 839 mbbi != mbbe; ++mbbi) { 840 unsigned Dist = 0; 841 DistanceMap.clear(); 842 SrcRegMap.clear(); 843 DstRegMap.clear(); 844 Processed.clear(); 845 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 846 mi != me; ) { 847 MachineBasicBlock::iterator nmi = next(mi); 848 const TargetInstrDesc &TID = mi->getDesc(); 849 bool FirstTied = true; 850 851 DistanceMap.insert(std::make_pair(mi, ++Dist)); 852 853 ProcessCopy(&*mi, &*mbbi, Processed); 854 855 unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM) 856 ? mi->getNumOperands() : TID.getNumOperands(); 857 for (unsigned si = 0; si < NumOps; ++si) { 858 unsigned ti = 0; 859 if (!mi->isRegTiedToDefOperand(si, &ti)) 860 continue; 861 862 if (FirstTied) { 863 ++NumTwoAddressInstrs; 864 DEBUG(errs() << '\t' << *mi); 865 } 866 867 FirstTied = false; 868 869 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && 870 mi->getOperand(si).isUse() && "two address instruction invalid"); 871 872 // If the two operands are the same, nothing needs to be done. 873 if (mi->getOperand(ti).getReg() == mi->getOperand(si).getReg()) 874 continue; 875 876 // Rewrite: 877 // a = b op c 878 // to: 879 // a = b 880 // a = a op c 881 unsigned regA = mi->getOperand(ti).getReg(); 882 unsigned regB = mi->getOperand(si).getReg(); 883 unsigned regASubIdx = mi->getOperand(ti).getSubReg(); 884 885 assert(TargetRegisterInfo::isVirtualRegister(regB) && 886 "cannot make instruction into two-address form"); 887 888#ifndef NDEBUG 889 // First, verify that we don't have a use of a in the instruction (a = 890 // b + a for example) because our transformation will not work. This 891 // should never occur because we are in SSA form. 892 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 893 assert(i == ti || 894 !mi->getOperand(i).isReg() || 895 mi->getOperand(i).getReg() != regA); 896#endif 897 898 // If regA is dead and the instruction can be deleted, just delete 899 // it so it doesn't clobber regB. 900 bool regBKilled = isKilled(*mi, regB, MRI, TII); 901 if (!regBKilled && mi->getOperand(ti).isDead() && 902 DeleteUnusedInstr(mi, nmi, mbbi, regB, si, Dist)) { 903 ++NumDeletes; 904 break; // Done with this instruction. 905 } 906 907 // Check if it is profitable to commute the operands. 908 unsigned SrcOp1, SrcOp2; 909 unsigned regC = 0; 910 bool TryCommute = false; 911 bool AggressiveCommute = false; 912 if (TID.isCommutable() && mi->getNumOperands() >= 3 && 913 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { 914 if (si == SrcOp1) 915 regC = mi->getOperand(SrcOp2).getReg(); 916 else if (si == SrcOp2) 917 regC = mi->getOperand(SrcOp1).getReg(); 918 919 if (regC) { 920 if (!regBKilled && isKilled(*mi, regC, MRI, TII)) 921 // If C dies but B does not, swap the B and C operands. 922 // This makes the live ranges of A and C joinable. 923 TryCommute = true; 924 else if (isProfitableToCommute(regB, regC, mi, mbbi, Dist)) { 925 TryCommute = true; 926 AggressiveCommute = true; 927 } 928 } 929 } 930 931 // If it's profitable to commute, try to do so. 932 if (TryCommute && CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 933 ++NumCommuted; 934 if (AggressiveCommute) 935 ++NumAggrCommuted; 936 regB = regC; 937 } else if (TID.isConvertibleTo3Addr()) { 938 // This instruction is potentially convertible to a true 939 // three-address instruction. Check if it is profitable. 940 if (!regBKilled || isProfitableToConv3Addr(regA)) { 941 // FIXME: This assumes there are no more operands which are tied 942 // to another register. 943#ifndef NDEBUG 944 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) 945 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 946#endif 947 // Try to convert it. 948 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 949 ++NumConvertedTo3Addr; 950 break; // Done with this instruction. 951 } 952 } 953 } 954 955 const TargetRegisterClass* rc = MRI->getRegClass(regB); 956 MachineInstr *DefMI = MRI->getVRegDef(regB); 957 // If it's safe and profitable, remat the definition instead of 958 // copying it. 959 if (DefMI && 960 DefMI->getDesc().isAsCheapAsAMove() && 961 DefMI->isSafeToReMat(TII, regB) && 962 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ 963 DEBUG(errs() << "2addr: REMATTING : " << *DefMI << "\n"); 964 TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI); 965 ReMatRegs.set(regB); 966 ++NumReMats; 967 } else { 968 bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 969 (void)Emitted; 970 assert(Emitted && "Unable to issue a copy instruction!\n"); 971 } 972 973 MachineBasicBlock::iterator prevMI = prior(mi); 974 // Update DistanceMap. 975 DistanceMap.insert(std::make_pair(prevMI, Dist)); 976 DistanceMap[mi] = ++Dist; 977 978 // Scan the operands to find: (1) the use operand that kills regB (if 979 // any); (2) whether the kill operand is being replaced by regA on 980 // this iteration; and (3) the first use of regB that is not being 981 // replaced on this iteration. A use of regB will not replaced if it 982 // is tied to a different destination register and will be handled on 983 // a later iteration. 984 MachineOperand *KillMO = NULL; 985 MachineOperand *FirstKeptMO = NULL; 986 bool KillMOKept = false; 987 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 988 MachineOperand &MO = mi->getOperand(i); 989 if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { 990 991 // Check if this operand is tied to a different destination. 992 bool isKept = false; 993 unsigned dsti = 0; 994 if (mi->isRegTiedToDefOperand(i, &dsti) && dsti != ti) { 995 isKept = true; 996 if (!FirstKeptMO) 997 FirstKeptMO = &MO; 998 } 999 1000 if (MO.isKill()) { 1001 KillMO = &MO; 1002 KillMOKept = isKept; 1003 } 1004 } 1005 } 1006 1007 // Update live variables for regB. 1008 if (KillMO) { 1009 if (!FirstKeptMO) { 1010 // All uses of regB are being replaced; move the kill to prevMI. 1011 KillMO->setIsKill(false); 1012 if (LV && LV->getVarInfo(regB).removeKill(mi)) 1013 LV->addVirtualRegisterKilled(regB, prevMI); 1014 } else { 1015 if (!KillMOKept) { 1016 // The kill marker is on an operand being replaced, but there 1017 // are other uses of regB remaining. Move the kill marker to 1018 // one of them. 1019 KillMO->setIsKill(false); 1020 FirstKeptMO->setIsKill(true); 1021 } 1022 } 1023 } 1024 1025 DEBUG(errs() << "\t\tprepend:\t" << *prevMI); 1026 1027 // Replace uses of regB with regA. 1028 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 1029 MachineOperand &MO = mi->getOperand(i); 1030 if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { 1031 1032 // Skip operands that are tied to other register definitions. 1033 unsigned dsti = 0; 1034 if (mi->isRegTiedToDefOperand(i, &dsti) && dsti != ti) 1035 continue; 1036 1037 MO.setReg(regA); 1038 } 1039 } 1040 1041 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 1042 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 1043 MadeChange = true; 1044 1045 DEBUG(errs() << "\t\trewrite to:\t" << *mi); 1046 } 1047 1048 mi = nmi; 1049 } 1050 } 1051 1052 // Some remat'ed instructions are dead. 1053 int VReg = ReMatRegs.find_first(); 1054 while (VReg != -1) { 1055 if (MRI->use_empty(VReg)) { 1056 MachineInstr *DefMI = MRI->getVRegDef(VReg); 1057 DefMI->eraseFromParent(); 1058 } 1059 VReg = ReMatRegs.find_next(VReg); 1060 } 1061 1062 return MadeChange; 1063} 1064