LLVM API Documentation

TwoAddressInstructionPass.cpp

Go to the documentation of this file.
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 }