LLVM API Documentation
00001 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the TwoAddress instruction pass which is used 00011 // by most register allocators. Two-Address instructions are rewritten 00012 // from: 00013 // 00014 // A = B op C 00015 // 00016 // to: 00017 // 00018 // A = B 00019 // A op= C 00020 // 00021 // Note that if a register allocator chooses to use this pass, that it 00022 // has to be capable of handling the non-SSA nature of these rewritten 00023 // virtual registers. 00024 // 00025 // It is also worth noting that the duplicate operand of the two 00026 // address instruction is removed. 00027 // 00028 //===----------------------------------------------------------------------===// 00029 00030 #define DEBUG_TYPE "twoaddrinstr" 00031 #include "llvm/CodeGen/Passes.h" 00032 #include "llvm/Function.h" 00033 #include "llvm/CodeGen/LiveVariables.h" 00034 #include "llvm/CodeGen/MachineFunctionPass.h" 00035 #include "llvm/CodeGen/MachineInstr.h" 00036 #include "llvm/CodeGen/MachineRegisterInfo.h" 00037 #include "llvm/Target/TargetRegisterInfo.h" 00038 #include "llvm/Target/TargetInstrInfo.h" 00039 #include "llvm/Target/TargetMachine.h" 00040 #include "llvm/Target/TargetOptions.h" 00041 #include "llvm/Support/Compiler.h" 00042 #include "llvm/Support/Debug.h" 00043 #include "llvm/ADT/BitVector.h" 00044 #include "llvm/ADT/DenseMap.h" 00045 #include "llvm/ADT/SmallSet.h" 00046 #include "llvm/ADT/Statistic.h" 00047 #include "llvm/ADT/STLExtras.h" 00048 using namespace llvm; 00049 00050 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 00051 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 00052 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 00053 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 00054 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 00055 STATISTIC(NumReMats, "Number of instructions re-materialized"); 00056 STATISTIC(NumDeletes, "Number of dead instructions deleted"); 00057 00058 namespace { 00059 class VISIBILITY_HIDDEN TwoAddressInstructionPass 00060 : public MachineFunctionPass { 00061 const TargetInstrInfo *TII; 00062 const TargetRegisterInfo *TRI; 00063 MachineRegisterInfo *MRI; 00064 LiveVariables *LV; 00065 00066 // DistanceMap - Keep track the distance of a MI from the start of the 00067 // current basic block. 00068 DenseMap<MachineInstr*, unsigned> DistanceMap; 00069 00070 // SrcRegMap - A map from virtual registers to physical registers which 00071 // are likely targets to be coalesced to due to copies from physical 00072 // registers to virtual registers. e.g. v1024 = move r0. 00073 DenseMap<unsigned, unsigned> SrcRegMap; 00074 00075 // DstRegMap - A map from virtual registers to physical registers which 00076 // are likely targets to be coalesced to due to copies to physical 00077 // registers from virtual registers. e.g. r1 = move v1024. 00078 DenseMap<unsigned, unsigned> DstRegMap; 00079 00080 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, 00081 unsigned Reg, 00082 MachineBasicBlock::iterator OldPos); 00083 00084 bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC, 00085 MachineInstr *MI, MachineInstr *DefMI, 00086 MachineBasicBlock *MBB, unsigned Loc); 00087 00088 bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist, 00089 unsigned &LastDef); 00090 00091 MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB, 00092 unsigned Dist); 00093 00094 bool isProfitableToCommute(unsigned regB, unsigned regC, 00095 MachineInstr *MI, MachineBasicBlock *MBB, 00096 unsigned Dist); 00097 00098 bool CommuteInstruction(MachineBasicBlock::iterator &mi, 00099 MachineFunction::iterator &mbbi, 00100 unsigned RegB, unsigned RegC, unsigned Dist); 00101 00102 bool isProfitableToConv3Addr(unsigned RegA); 00103 00104 bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 00105 MachineBasicBlock::iterator &nmi, 00106 MachineFunction::iterator &mbbi, 00107 unsigned RegB, unsigned Dist); 00108 00109 void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB, 00110 SmallPtrSet<MachineInstr*, 8> &Processed); 00111 00112 public: 00113 static char ID; // Pass identification, replacement for typeid 00114 TwoAddressInstructionPass() : MachineFunctionPass(&ID) {} 00115 00116 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00117 AU.setPreservesCFG(); 00118 AU.addPreserved<LiveVariables>(); 00119 AU.addPreservedID(MachineLoopInfoID); 00120 AU.addPreservedID(MachineDominatorsID); 00121 if (StrongPHIElim) 00122 AU.addPreservedID(StrongPHIEliminationID); 00123 else 00124 AU.addPreservedID(PHIEliminationID); 00125 MachineFunctionPass::getAnalysisUsage(AU); 00126 } 00127 00128 /// runOnMachineFunction - Pass entry point. 00129 bool runOnMachineFunction(MachineFunction&); 00130 }; 00131 } 00132 00133 char TwoAddressInstructionPass::ID = 0; 00134 static RegisterPass<TwoAddressInstructionPass> 00135 X("twoaddressinstruction", "Two-Address instruction pass"); 00136 00137 const PassInfo *const llvm::TwoAddressInstructionPassID = &X; 00138 00139 /// Sink3AddrInstruction - A two-address instruction has been converted to a 00140 /// three-address instruction to avoid clobbering a register. Try to sink it 00141 /// past the instruction that would kill the above mentioned register to reduce 00142 /// register pressure. 00143 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, 00144 MachineInstr *MI, unsigned SavedReg, 00145 MachineBasicBlock::iterator OldPos) { 00146 // Check if it's safe to move this instruction. 00147 bool SeenStore = true; // Be conservative. 00148 if (!MI->isSafeToMove(TII, SeenStore)) 00149 return false; 00150 00151 unsigned DefReg = 0; 00152 SmallSet<unsigned, 4> UseRegs; 00153 00154 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00155 const MachineOperand &MO = MI->getOperand(i); 00156 if (!MO.isReg()) 00157 continue; 00158 unsigned MOReg = MO.getReg(); 00159 if (!MOReg) 00160 continue; 00161 if (MO.isUse() && MOReg != SavedReg) 00162 UseRegs.insert(MO.getReg()); 00163 if (!MO.isDef()) 00164 continue; 00165 if (MO.isImplicit()) 00166 // Don't try to move it if it implicitly defines a register. 00167 return false; 00168 if (DefReg) 00169 // For now, don't move any instructions that define multiple registers. 00170 return false; 00171 DefReg = MO.getReg(); 00172 } 00173 00174 // Find the instruction that kills SavedReg. 00175 MachineInstr *KillMI = NULL; 00176 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), 00177 UE = MRI->use_end(); UI != UE; ++UI) { 00178 MachineOperand &UseMO = UI.getOperand(); 00179 if (!UseMO.isKill()) 00180 continue; 00181 KillMI = UseMO.getParent(); 00182 break; 00183 } 00184 00185 if (!KillMI || KillMI->getParent() != MBB || KillMI == MI) 00186 return false; 00187 00188 // If any of the definitions are used by another instruction between the 00189 // position and the kill use, then it's not safe to sink it. 00190 // 00191 // FIXME: This can be sped up if there is an easy way to query whether an 00192 // instruction is before or after another instruction. Then we can use 00193 // MachineRegisterInfo def / use instead. 00194 MachineOperand *KillMO = NULL; 00195 MachineBasicBlock::iterator KillPos = KillMI; 00196 ++KillPos; 00197 00198 unsigned NumVisited = 0; 00199 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { 00200 MachineInstr *OtherMI = I; 00201 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 00202 return false; 00203 ++NumVisited; 00204 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 00205 MachineOperand &MO = OtherMI->getOperand(i); 00206 if (!MO.isReg()) 00207 continue; 00208 unsigned MOReg = MO.getReg(); 00209 if (!MOReg) 00210 continue; 00211 if (DefReg == MOReg) 00212 return false; 00213 00214 if (MO.isKill()) { 00215 if (OtherMI == KillMI && MOReg == SavedReg) 00216 // Save the operand that kills the register. We want to unset the kill 00217 // marker if we can sink MI past it. 00218 KillMO = &MO; 00219 else if (UseRegs.count(MOReg)) 00220 // One of the uses is killed before the destination. 00221 return false; 00222 } 00223 } 00224 } 00225 00226 // Update kill and LV information. 00227 KillMO->setIsKill(false); 00228 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 00229 KillMO->setIsKill(true); 00230 00231 if (LV) 00232 LV->replaceKillInstruction(SavedReg, KillMI, MI); 00233 00234 // Move instruction to its destination. 00235 MBB->remove(MI); 00236 MBB->insert(KillPos, MI); 00237 00238 ++Num3AddrSunk; 00239 return true; 00240 } 00241 00242 /// isTwoAddrUse - Return true if the specified MI is using the specified 00243 /// register as a two-address operand. 00244 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { 00245 const TargetInstrDesc &TID = UseMI->getDesc(); 00246 for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) { 00247 MachineOperand &MO = UseMI->getOperand(i); 00248 if (MO.isReg() && MO.getReg() == Reg && 00249 (MO.isDef() || UseMI->isRegTiedToDefOperand(i))) 00250 // Earlier use is a two-address one. 00251 return true; 00252 } 00253 return false; 00254 } 00255 00256 /// isProfitableToReMat - Return true if the heuristics determines it is likely 00257 /// to be profitable to re-materialize the definition of Reg rather than copy 00258 /// the register. 00259 bool 00260 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, 00261 const TargetRegisterClass *RC, 00262 MachineInstr *MI, MachineInstr *DefMI, 00263 MachineBasicBlock *MBB, unsigned Loc) { 00264 bool OtherUse = false; 00265 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 00266 UE = MRI->use_end(); UI != UE; ++UI) { 00267 MachineOperand &UseMO = UI.getOperand(); 00268 MachineInstr *UseMI = UseMO.getParent(); 00269 MachineBasicBlock *UseMBB = UseMI->getParent(); 00270 if (UseMBB == MBB) { 00271 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 00272 if (DI != DistanceMap.end() && DI->second == Loc) 00273 continue; // Current use. 00274 OtherUse = true; 00275 // There is at least one other use in the MBB that will clobber the 00276 // register. 00277 if (isTwoAddrUse(UseMI, Reg)) 00278 return true; 00279 } 00280 } 00281 00282 // If other uses in MBB are not two-address uses, then don't remat. 00283 if (OtherUse) 00284 return false; 00285 00286 // No other uses in the same block, remat if it's defined in the same 00287 // block so it does not unnecessarily extend the live range. 00288 return MBB == DefMI->getParent(); 00289 } 00290 00291 /// NoUseAfterLastDef - Return true if there are no intervening uses between the 00292 /// last instruction in the MBB that defines the specified register and the 00293 /// two-address instruction which is being processed. It also returns the last 00294 /// def location by reference 00295 bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg, 00296 MachineBasicBlock *MBB, unsigned Dist, 00297 unsigned &LastDef) { 00298 LastDef = 0; 00299 unsigned LastUse = Dist; 00300 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 00301 E = MRI->reg_end(); I != E; ++I) { 00302 MachineOperand &MO = I.getOperand(); 00303 MachineInstr *MI = MO.getParent(); 00304 if (MI->getParent() != MBB) 00305 continue; 00306 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 00307 if (DI == DistanceMap.end()) 00308 continue; 00309 if (MO.isUse() && DI->second < LastUse) 00310 LastUse = DI->second; 00311 if (MO.isDef() && DI->second > LastDef) 00312 LastDef = DI->second; 00313 } 00314 00315 return !(LastUse > LastDef && LastUse < Dist); 00316 } 00317 00318 MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg, 00319 MachineBasicBlock *MBB, 00320 unsigned Dist) { 00321 unsigned LastUseDist = 0; 00322 MachineInstr *LastUse = 0; 00323 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 00324 E = MRI->reg_end(); I != E; ++I) { 00325 MachineOperand &MO = I.getOperand(); 00326 MachineInstr *MI = MO.getParent(); 00327 if (MI->getParent() != MBB) 00328 continue; 00329 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 00330 if (DI == DistanceMap.end()) 00331 continue; 00332 if (DI->second >= Dist) 00333 continue; 00334 00335 if (MO.isUse() && DI->second > LastUseDist) { 00336 LastUse = DI->first; 00337 LastUseDist = DI->second; 00338 } 00339 } 00340 return LastUse; 00341 } 00342 00343 /// isCopyToReg - Return true if the specified MI is a copy instruction or 00344 /// a extract_subreg instruction. It also returns the source and destination 00345 /// registers and whether they are physical registers by reference. 00346 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 00347 unsigned &SrcReg, unsigned &DstReg, 00348 bool &IsSrcPhys, bool &IsDstPhys) { 00349 SrcReg = 0; 00350 DstReg = 0; 00351 unsigned SrcSubIdx, DstSubIdx; 00352 if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { 00353 if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 00354 DstReg = MI.getOperand(0).getReg(); 00355 SrcReg = MI.getOperand(1).getReg(); 00356 } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 00357 DstReg = MI.getOperand(0).getReg(); 00358 SrcReg = MI.getOperand(2).getReg(); 00359 } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 00360 DstReg = MI.getOperand(0).getReg(); 00361 SrcReg = MI.getOperand(2).getReg(); 00362 } 00363 } 00364 00365 if (DstReg) { 00366 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 00367 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 00368 return true; 00369 } 00370 return false; 00371 } 00372 00373 /// isKilled - Test if the given register value, which is used by the given 00374 /// instruction, is killed by the given instruction. This looks through 00375 /// coalescable copies to see if the original value is potentially not killed. 00376 /// 00377 /// For example, in this code: 00378 /// 00379 /// %reg1034 = copy %reg1024 00380 /// %reg1035 = copy %reg1025<kill> 00381 /// %reg1036 = add %reg1034<kill>, %reg1035<kill> 00382 /// 00383 /// %reg1034 is not considered to be killed, since it is copied from a 00384 /// register which is not killed. Treating it as not killed lets the 00385 /// normal heuristics commute the (two-address) add, which lets 00386 /// coalescing eliminate the extra copy. 00387 /// 00388 static bool isKilled(MachineInstr &MI, unsigned Reg, 00389 const MachineRegisterInfo *MRI, 00390 const TargetInstrInfo *TII) { 00391 MachineInstr *DefMI = &MI; 00392 for (;;) { 00393 if (!DefMI->killsRegister(Reg)) 00394 return false; 00395 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 00396 return true; 00397 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 00398 // If there are multiple defs, we can't do a simple analysis, so just 00399 // go with what the kill flag says. 00400 if (next(Begin) != MRI->def_end()) 00401 return true; 00402 DefMI = &*Begin; 00403 bool IsSrcPhys, IsDstPhys; 00404 unsigned SrcReg, DstReg; 00405 // If the def is something other than a copy, then it isn't going to 00406 // be coalesced, so follow the kill flag. 00407 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 00408 return true; 00409 Reg = SrcReg; 00410 } 00411 } 00412 00413 /// isTwoAddrUse - Return true if the specified MI uses the specified register 00414 /// as a two-address use. If so, return the destination register by reference. 00415 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 00416 const TargetInstrDesc &TID = MI.getDesc(); 00417 unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM) 00418 ? MI.getNumOperands() : TID.getNumOperands(); 00419 for (unsigned i = 0; i != NumOps; ++i) { 00420 const MachineOperand &MO = MI.getOperand(i); 00421 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 00422 continue; 00423 unsigned ti; 00424 if (MI.isRegTiedToDefOperand(i, &ti)) { 00425 DstReg = MI.getOperand(ti).getReg(); 00426 return true; 00427 } 00428 } 00429 return false; 00430 } 00431 00432 /// findOnlyInterestingUse - Given a register, if has a single in-basic block 00433 /// use, return the use instruction if it's a copy or a two-address use. 00434 static 00435 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 00436 MachineRegisterInfo *MRI, 00437 const TargetInstrInfo *TII, 00438 bool &IsCopy, 00439 unsigned &DstReg, bool &IsDstPhys) { 00440 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg); 00441 if (UI == MRI->use_end()) 00442 return 0; 00443 MachineInstr &UseMI = *UI; 00444 if (++UI != MRI->use_end()) 00445 // More than one use. 00446 return 0; 00447 if (UseMI.getParent() != MBB) 00448 return 0; 00449 unsigned SrcReg; 00450 bool IsSrcPhys; 00451 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 00452 IsCopy = true; 00453 return &UseMI; 00454 } 00455 IsDstPhys = false; 00456 if (isTwoAddrUse(UseMI, Reg, DstReg)) { 00457 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 00458 return &UseMI; 00459 } 00460 return 0; 00461 } 00462 00463 /// getMappedReg - Return the physical register the specified virtual register 00464 /// might be mapped to. 00465 static unsigned 00466 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 00467 while (TargetRegisterInfo::isVirtualRegister(Reg)) { 00468 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 00469 if (SI == RegMap.end()) 00470 return 0; 00471 Reg = SI->second; 00472 } 00473 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 00474 return Reg; 00475 return 0; 00476 } 00477 00478 /// regsAreCompatible - Return true if the two registers are equal or aliased. 00479 /// 00480 static bool 00481 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 00482 if (RegA == RegB) 00483 return true; 00484 if (!RegA || !RegB) 00485 return false; 00486 return TRI->regsOverlap(RegA, RegB); 00487 } 00488 00489 00490 /// isProfitableToReMat - Return true if it's potentially profitable to commute 00491 /// the two-address instruction that's being processed. 00492 bool 00493 TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, 00494 MachineInstr *MI, MachineBasicBlock *MBB, 00495 unsigned Dist) { 00496 // Determine if it's profitable to commute this two address instruction. In 00497 // general, we want no uses between this instruction and the definition of 00498 // the two-address register. 00499 // e.g. 00500 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 00501 // %reg1029<def> = MOV8rr %reg1028 00502 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 00503 // insert => %reg1030<def> = MOV8rr %reg1028 00504 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 00505 // In this case, it might not be possible to coalesce the second MOV8rr 00506 // instruction if the first one is coalesced. So it would be profitable to 00507 // commute it: 00508 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 00509 // %reg1029<def> = MOV8rr %reg1028 00510 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 00511 // insert => %reg1030<def> = MOV8rr %reg1029 00512 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 00513 00514 if (!MI->killsRegister(regC)) 00515 return false; 00516 00517 // Ok, we have something like: 00518 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 00519 // let's see if it's worth commuting it. 00520 00521 // Look for situations like this: 00522 // %reg1024<def> = MOV r1 00523 // %reg1025<def> = MOV r0 00524 // %reg1026<def> = ADD %reg1024, %reg1025 00525 // r0 = MOV %reg1026 00526 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 00527 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 00528 unsigned FromRegC = getMappedReg(regC, SrcRegMap); 00529 unsigned ToRegB = getMappedReg(regB, DstRegMap); 00530 unsigned ToRegC = getMappedReg(regC, DstRegMap); 00531 if (!regsAreCompatible(FromRegB, ToRegB, TRI) && 00532 (regsAreCompatible(FromRegB, ToRegC, TRI) || 00533 regsAreCompatible(FromRegC, ToRegB, TRI))) 00534 return true; 00535 00536 // If there is a use of regC between its last def (could be livein) and this 00537 // instruction, then bail. 00538 unsigned LastDefC = 0; 00539 if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC)) 00540 return false; 00541 00542 // If there is a use of regB between its last def (could be livein) and this 00543 // instruction, then go ahead and make this transformation. 00544 unsigned LastDefB = 0; 00545 if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB)) 00546 return true; 00547 00548 // Since there are no intervening uses for both registers, then commute 00549 // if the def of regC is closer. Its live interval is shorter. 00550 return LastDefB && LastDefC && LastDefC > LastDefB; 00551 } 00552 00553 /// CommuteInstruction - Commute a two-address instruction and update the basic 00554 /// block, distance map, and live variables if needed. Return true if it is 00555 /// successful. 00556 bool 00557 TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, 00558 MachineFunction::iterator &mbbi, 00559 unsigned RegB, unsigned RegC, unsigned Dist) { 00560 MachineInstr *MI = mi; 00561 DOUT << "2addr: COMMUTING : " << *MI; 00562 MachineInstr *NewMI = TII->commuteInstruction(MI); 00563 00564 if (NewMI == 0) { 00565 DOUT << "2addr: COMMUTING FAILED!\n"; 00566 return false; 00567 } 00568 00569 DOUT << "2addr: COMMUTED TO: " << *NewMI; 00570 // If the instruction changed to commute it, update livevar. 00571 if (NewMI != MI) { 00572 if (LV) 00573 // Update live variables 00574 LV->replaceKillInstruction(RegC, MI, NewMI); 00575 00576 mbbi->insert(mi, NewMI); // Insert the new inst 00577 mbbi->erase(mi); // Nuke the old inst. 00578 mi = NewMI; 00579 DistanceMap.insert(std::make_pair(NewMI, Dist)); 00580 } 00581 00582 // Update source register map. 00583 unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 00584 if (FromRegC) { 00585 unsigned RegA = MI->getOperand(0).getReg(); 00586 SrcRegMap[RegA] = FromRegC; 00587 } 00588 00589 return true; 00590 } 00591 00592 /// isProfitableToConv3Addr - Return true if it is profitable to convert the 00593 /// given 2-address instruction to a 3-address one. 00594 bool 00595 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) { 00596 // Look for situations like this: 00597 // %reg1024<def> = MOV r1 00598 // %reg1025<def> = MOV r0 00599 // %reg1026<def> = ADD %reg1024, %reg1025 00600 // r2 = MOV %reg1026 00601 // Turn ADD into a 3-address instruction to avoid a copy. 00602 unsigned FromRegA = getMappedReg(RegA, SrcRegMap); 00603 unsigned ToRegA = getMappedReg(RegA, DstRegMap); 00604 return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI)); 00605 } 00606 00607 /// ConvertInstTo3Addr - Convert the specified two-address instruction into a 00608 /// three address one. Return true if this transformation was successful. 00609 bool 00610 TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 00611 MachineBasicBlock::iterator &nmi, 00612 MachineFunction::iterator &mbbi, 00613 unsigned RegB, unsigned Dist) { 00614 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); 00615 if (NewMI) { 00616 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 00617 DOUT << "2addr: TO 3-ADDR: " << *NewMI; 00618 bool Sunk = false; 00619 00620 if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 00621 // FIXME: Temporary workaround. If the new instruction doesn't 00622 // uses RegB, convertToThreeAddress must have created more 00623 // then one instruction. 00624 Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi); 00625 00626 mbbi->erase(mi); // Nuke the old inst. 00627 00628 if (!Sunk) { 00629 DistanceMap.insert(std::make_pair(NewMI, Dist)); 00630 mi = NewMI; 00631 nmi = next(mi); 00632 } 00633 return true; 00634 } 00635 00636 return false; 00637 } 00638 00639 /// ProcessCopy - If the specified instruction is not yet processed, process it 00640 /// if it's a copy. For a copy instruction, we find the physical registers the 00641 /// source and destination registers might be mapped to. These are kept in 00642 /// point-to maps used to determine future optimizations. e.g. 00643 /// v1024 = mov r0 00644 /// v1025 = mov r1 00645 /// v1026 = add v1024, v1025 00646 /// r1 = mov r1026 00647 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially 00648 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 00649 /// potentially joined with r1 on the output side. It's worthwhile to commute 00650 /// 'add' to eliminate a copy. 00651 void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, 00652 MachineBasicBlock *MBB, 00653 SmallPtrSet<MachineInstr*, 8> &Processed) { 00654 if (Processed.count(MI)) 00655 return; 00656 00657 bool IsSrcPhys, IsDstPhys; 00658 unsigned SrcReg, DstReg; 00659 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 00660 return; 00661 00662 if (IsDstPhys && !IsSrcPhys) 00663 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 00664 else if (!IsDstPhys && IsSrcPhys) { 00665 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 00666 if (!isNew) 00667 assert(SrcRegMap[DstReg] == SrcReg && 00668 "Can't map to two src physical registers!"); 00669 00670 SmallVector<unsigned, 4> VirtRegPairs; 00671 bool IsCopy = false; 00672 unsigned NewReg = 0; 00673 while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII, 00674 IsCopy, NewReg, IsDstPhys)) { 00675 if (IsCopy) { 00676 if (!Processed.insert(UseMI)) 00677 break; 00678 } 00679 00680 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 00681 if (DI != DistanceMap.end()) 00682 // Earlier in the same MBB.Reached via a back edge. 00683 break; 00684 00685 if (IsDstPhys) { 00686 VirtRegPairs.push_back(NewReg); 00687 break; 00688 } 00689 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second; 00690 if (!isNew) 00691 assert(SrcRegMap[NewReg] == DstReg && 00692 "Can't map to two src physical registers!"); 00693 VirtRegPairs.push_back(NewReg); 00694 DstReg = NewReg; 00695 } 00696 00697 if (!VirtRegPairs.empty()) { 00698 unsigned ToReg = VirtRegPairs.back(); 00699 VirtRegPairs.pop_back(); 00700 while (!VirtRegPairs.empty()) { 00701 unsigned FromReg = VirtRegPairs.back(); 00702 VirtRegPairs.pop_back(); 00703 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 00704 if (!isNew) 00705 assert(DstRegMap[FromReg] == ToReg && 00706 "Can't map to two dst physical registers!"); 00707 ToReg = FromReg; 00708 } 00709 } 00710 } 00711 00712 Processed.insert(MI); 00713 } 00714 00715 /// isSafeToDelete - If the specified instruction does not produce any side 00716 /// effects and all of its defs are dead, then it's safe to delete. 00717 static bool isSafeToDelete(MachineInstr *MI, unsigned Reg, 00718 const TargetInstrInfo *TII, 00719 SmallVector<unsigned, 4> &Kills) { 00720 const TargetInstrDesc &TID = MI->getDesc(); 00721 if (TID.mayStore() || TID.isCall()) 00722 return false; 00723 if (TID.isTerminator() || TID.hasUnmodeledSideEffects()) 00724 return false; 00725 00726 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00727 MachineOperand &MO = MI->getOperand(i); 00728 if (!MO.isReg()) 00729 continue; 00730 if (MO.isDef() && !MO.isDead()) 00731 return false; 00732 if (MO.isUse() && MO.getReg() != Reg && MO.isKill()) 00733 Kills.push_back(MO.getReg()); 00734 } 00735 00736 return true; 00737 } 00738 00739 /// runOnMachineFunction - Reduce two-address instructions to two operands. 00740 /// 00741 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 00742 DOUT << "Machine Function\n"; 00743 const TargetMachine &TM = MF.getTarget(); 00744 MRI = &MF.getRegInfo(); 00745 TII = TM.getInstrInfo(); 00746 TRI = TM.getRegisterInfo(); 00747 LV = getAnalysisIfAvailable<LiveVariables>(); 00748 00749 bool MadeChange = false; 00750 00751 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 00752 DEBUG(errs() << "********** Function: " 00753 << MF.getFunction()->getName() << '\n'); 00754 00755 // ReMatRegs - Keep track of the registers whose def's are remat'ed. 00756 BitVector ReMatRegs; 00757 ReMatRegs.resize(MRI->getLastVirtReg()+1); 00758 00759 SmallPtrSet<MachineInstr*, 8> Processed; 00760 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 00761 mbbi != mbbe; ++mbbi) { 00762 unsigned Dist = 0; 00763 DistanceMap.clear(); 00764 SrcRegMap.clear(); 00765 DstRegMap.clear(); 00766 Processed.clear(); 00767 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 00768 mi != me; ) { 00769 MachineBasicBlock::iterator nmi = next(mi); 00770 const TargetInstrDesc &TID = mi->getDesc(); 00771 bool FirstTied = true; 00772 00773 DistanceMap.insert(std::make_pair(mi, ++Dist)); 00774 00775 ProcessCopy(&*mi, &*mbbi, Processed); 00776 00777 unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM) 00778 ? mi->getNumOperands() : TID.getNumOperands(); 00779 for (unsigned si = 0; si < NumOps; ++si) { 00780 unsigned ti = 0; 00781 if (!mi->isRegTiedToDefOperand(si, &ti)) 00782 continue; 00783 00784 if (FirstTied) { 00785 ++NumTwoAddressInstrs; 00786 DOUT << '\t' << *mi; 00787 } 00788 00789 FirstTied = false; 00790 00791 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && 00792 mi->getOperand(si).isUse() && "two address instruction invalid"); 00793 00794 // If the two operands are the same we just remove the use 00795 // and mark the def as def&use, otherwise we have to insert a copy. 00796 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 00797 // Rewrite: 00798 // a = b op c 00799 // to: 00800 // a = b 00801 // a = a op c 00802 unsigned regA = mi->getOperand(ti).getReg(); 00803 unsigned regB = mi->getOperand(si).getReg(); 00804 unsigned regASubIdx = mi->getOperand(ti).getSubReg(); 00805 00806 assert(TargetRegisterInfo::isVirtualRegister(regB) && 00807 "cannot make instruction into two-address form"); 00808 00809 #ifndef NDEBUG 00810 // First, verify that we don't have a use of a in the instruction (a = 00811 // b + a for example) because our transformation will not work. This 00812 // should never occur because we are in SSA form. 00813 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 00814 assert(i == ti || 00815 !mi->getOperand(i).isReg() || 00816 mi->getOperand(i).getReg() != regA); 00817 #endif 00818 00819 // If this instruction is not the killing user of B, see if we can 00820 // rearrange the code to make it so. Making it the killing user will 00821 // allow us to coalesce A and B together, eliminating the copy we are 00822 // about to insert. 00823 if (!isKilled(*mi, regB, MRI, TII)) { 00824 // If regA is dead and the instruction can be deleted, just delete 00825 // it so it doesn't clobber regB. 00826 SmallVector<unsigned, 4> Kills; 00827 if (mi->getOperand(ti).isDead() && 00828 isSafeToDelete(mi, regB, TII, Kills)) { 00829 SmallVector<std::pair<std::pair<unsigned, bool> 00830 ,MachineInstr*>, 4> NewKills; 00831 bool ReallySafe = true; 00832 // If this instruction kills some virtual registers, we need 00833 // update the kill information. If it's not possible to do so, 00834 // then bail out. 00835 while (!Kills.empty()) { 00836 unsigned Kill = Kills.back(); 00837 Kills.pop_back(); 00838 if (TargetRegisterInfo::isPhysicalRegister(Kill)) { 00839 ReallySafe = false; 00840 break; 00841 } 00842 MachineInstr *LastKill = FindLastUseInMBB(Kill, &*mbbi, Dist); 00843 if (LastKill) { 00844 bool isModRef = LastKill->modifiesRegister(Kill); 00845 NewKills.push_back(std::make_pair(std::make_pair(Kill,isModRef), 00846 LastKill)); 00847 } else { 00848 ReallySafe = false; 00849 break; 00850 } 00851 } 00852 00853 if (ReallySafe) { 00854 if (LV) { 00855 while (!NewKills.empty()) { 00856 MachineInstr *NewKill = NewKills.back().second; 00857 unsigned Kill = NewKills.back().first.first; 00858 bool isDead = NewKills.back().first.second; 00859 NewKills.pop_back(); 00860 if (LV->removeVirtualRegisterKilled(Kill, mi)) { 00861 if (isDead) 00862 LV->addVirtualRegisterDead(Kill, NewKill); 00863 else 00864 LV->addVirtualRegisterKilled(Kill, NewKill); 00865 } 00866 } 00867 } 00868 00869 // We're really going to nuke the old inst. If regB was marked 00870 // as a kill we need to update its Kills list. 00871 if (mi->getOperand(si).isKill()) 00872 LV->removeVirtualRegisterKilled(regB, mi); 00873 00874 mbbi->erase(mi); // Nuke the old inst. 00875 mi = nmi; 00876 ++NumDeletes; 00877 break; // Done with this instruction. 00878 } 00879 } 00880 00881 // If this instruction is commutative, check to see if C dies. If 00882 // so, swap the B and C operands. This makes the live ranges of A 00883 // and C joinable. 00884 // FIXME: This code also works for A := B op C instructions. 00885 unsigned SrcOp1, SrcOp2; 00886 if (TID.isCommutable() && mi->getNumOperands() >= 3 && 00887 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { 00888 unsigned regC = 0; 00889 if (si == SrcOp1) 00890 regC = mi->getOperand(SrcOp2).getReg(); 00891 else if (si == SrcOp2) 00892 regC = mi->getOperand(SrcOp1).getReg(); 00893 if (isKilled(*mi, regC, MRI, TII)) { 00894 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 00895 ++NumCommuted; 00896 regB = regC; 00897 goto InstructionRearranged; 00898 } 00899 } 00900 } 00901 00902 // If this instruction is potentially convertible to a true 00903 // three-address instruction, 00904 if (TID.isConvertibleTo3Addr()) { 00905 // FIXME: This assumes there are no more operands which are tied 00906 // to another register. 00907 #ifndef NDEBUG 00908 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) 00909 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 00910 #endif 00911 00912 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 00913 ++NumConvertedTo3Addr; 00914 break; // Done with this instruction. 00915 } 00916 } 00917 } 00918 00919 // If it's profitable to commute the instruction, do so. 00920 unsigned SrcOp1, SrcOp2; 00921 if (TID.isCommutable() && mi->getNumOperands() >= 3 && 00922 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { 00923 unsigned regC = 0; 00924 if (si == SrcOp1) 00925 regC = mi->getOperand(SrcOp2).getReg(); 00926 else if (si == SrcOp2) 00927 regC = mi->getOperand(SrcOp1).getReg(); 00928 00929 if (regC && isProfitableToCommute(regB, regC, mi, mbbi, Dist)) 00930 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 00931 ++NumAggrCommuted; 00932 ++NumCommuted; 00933 regB = regC; 00934 goto InstructionRearranged; 00935 } 00936 } 00937 00938 // If it's profitable to convert the 2-address instruction to a 00939 // 3-address one, do so. 00940 if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) { 00941 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 00942 ++NumConvertedTo3Addr; 00943 break; // Done with this instruction. 00944 } 00945 } 00946 00947 InstructionRearranged: 00948 const TargetRegisterClass* rc = MRI->getRegClass(regB); 00949 MachineInstr *DefMI = MRI->getVRegDef(regB); 00950 // If it's safe and profitable, remat the definition instead of 00951 // copying it. 00952 if (DefMI && 00953 DefMI->getDesc().isAsCheapAsAMove() && 00954 DefMI->isSafeToReMat(TII, regB) && 00955 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ 00956 DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n"); 00957 TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI); 00958 ReMatRegs.set(regB); 00959 ++NumReMats; 00960 } else { 00961 bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 00962 (void)Emitted; 00963 assert(Emitted && "Unable to issue a copy instruction!\n"); 00964 } 00965 00966 MachineBasicBlock::iterator prevMI = prior(mi); 00967 // Update DistanceMap. 00968 DistanceMap.insert(std::make_pair(prevMI, Dist)); 00969 DistanceMap[mi] = ++Dist; 00970 00971 // Update live variables for regB. 00972 if (LV) { 00973 if (LV->removeVirtualRegisterKilled(regB, mi)) 00974 LV->addVirtualRegisterKilled(regB, prevMI); 00975 00976 if (LV->removeVirtualRegisterDead(regB, mi)) 00977 LV->addVirtualRegisterDead(regB, prevMI); 00978 } 00979 00980 DOUT << "\t\tprepend:\t" << *prevMI; 00981 00982 // Replace all occurences of regB with regA. 00983 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 00984 if (mi->getOperand(i).isReg() && 00985 mi->getOperand(i).getReg() == regB) 00986 mi->getOperand(i).setReg(regA); 00987 } 00988 } 00989 00990 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 00991 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 00992 MadeChange = true; 00993 00994 DOUT << "\t\trewrite to:\t" << *mi; 00995 } 00996 00997 mi = nmi; 00998 } 00999 } 01000 01001 // Some remat'ed instructions are dead. 01002 int VReg = ReMatRegs.find_first(); 01003 while (VReg != -1) { 01004 if (MRI->use_empty(VReg)) { 01005 MachineInstr *DefMI = MRI->getVRegDef(VReg); 01006 DefMI->eraseFromParent(); 01007 } 01008 VReg = ReMatRegs.find_next(VReg); 01009 } 01010 01011 return MadeChange; 01012 }