lib/CodeGen/TwoAddressInstructionPass.cpp

   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/Support/Compiler.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/ADT/Statistic.h"
  43 #include "llvm/ADT/STLExtras.h"
  44 using namespace llvm;
  45
  46 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  47 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  48 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  49 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  50
  51 namespace {
  52   struct VISIBILITY_HIDDEN TwoAddressInstructionPass
  53    : public MachineFunctionPass {
  54     const TargetInstrInfo *TII;
  55     const TargetRegisterInfo *TRI;
  56     MachineRegisterInfo *MRI;
  57     LiveVariables *LV;
  58
  59   public:
  60     static char ID; // Pass identification, replacement for typeid
  61     TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
  62
  63     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  64
  65     /// runOnMachineFunction - pass entry point
  66     bool runOnMachineFunction(MachineFunction&);
  67
  68   private:
  69     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  70                               unsigned Reg,
  71                               MachineBasicBlock::iterator OldPos);
  72   };
  73
  74   char TwoAddressInstructionPass::ID = 0;
  75   RegisterPass<TwoAddressInstructionPass>
  76   X("twoaddressinstruction", "Two-Address instruction pass");
  77 }
  78
  79 const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
  80
  81 void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const {
  82   AU.addRequired<LiveVariables>();
  83   AU.addPreserved<LiveVariables>();
  84   AU.addPreservedID(MachineLoopInfoID);
  85   AU.addPreservedID(MachineDominatorsID);
  86   AU.addPreservedID(PHIEliminationID);
  87   MachineFunctionPass::getAnalysisUsage(AU);
  88 }
  89
  90 /// Sink3AddrInstruction - A two-address instruction has been converted to a
  91 /// three-address instruction to avoid clobbering a register. Try to sink it
  92 /// past the instruction that would kill the above mentioned register to
  93 /// reduce register pressure.
  94 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
  95                                            MachineInstr *MI, unsigned SavedReg,
  96                                            MachineBasicBlock::iterator OldPos) {
  97   // Check if it's safe to move this instruction.
  98   bool SeenStore = true; // Be conservative.
  99   if (!MI->isSafeToMove(TII, SeenStore))
 100     return false;
 101
 102   unsigned DefReg = 0;
 103   SmallSet<unsigned, 4> UseRegs;
 104   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 105     const MachineOperand &MO = MI->getOperand(i);
 106     if (!MO.isRegister())
 107       continue;
 108     unsigned MOReg = MO.getReg();
 109     if (!MOReg)
 110       continue;
 111     if (MO.isUse() && MOReg != SavedReg)
 112       UseRegs.insert(MO.getReg());
 113     if (!MO.isDef())
 114       continue;
 115     if (MO.isImplicit())
 116       // Don't try to move it if it implicitly defines a register.
 117       return false;
 118     if (DefReg)
 119       // For now, don't move any instructions that define multiple registers.
 120       return false;
 121     DefReg = MO.getReg();
 122   }
 123
 124   // Find the instruction that kills SavedReg.
 125   MachineInstr *KillMI = NULL;
 126   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 127          UE = MRI->use_end(); UI != UE; ++UI) {
 128     MachineOperand &UseMO = UI.getOperand();
 129     if (!UseMO.isKill())
 130       continue;
 131     KillMI = UseMO.getParent();
 132     break;
 133   }
 134   if (!KillMI || KillMI->getParent() != MBB)
 135     return false;
 136
 137   // If any of the definitions are used  by another instruction between
 138   // the position and the kill use, then it's not safe to sink it.
 139   // FIXME: This can be sped up if there is an easy way to query whether
 140   // an instruction if before or after another instruction. Then we can
 141   // use MachineRegisterInfo def / use instead.
 142   MachineOperand *KillMO = NULL;
 143   MachineBasicBlock::iterator KillPos = KillMI;
 144   ++KillPos;
 145   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 146     MachineInstr *OtherMI = I;
 147     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 148       MachineOperand &MO = OtherMI->getOperand(i);
 149       if (!MO.isRegister())
 150         continue;
 151       unsigned MOReg = MO.getReg();
 152       if (!MOReg)
 153         continue;
 154       if (DefReg == MOReg)
 155         return false;
 156       if (MO.isKill()) {
 157         if (OtherMI == KillMI && MOReg == SavedReg)
 158           // Save the operand that kills the register. We want unset the kill
 159           // marker is we can sink MI past it.
 160           KillMO = &MO;
 161         else if (UseRegs.count(MOReg))
 162           // One of the uses is killed before the destination.
 163           return false;
 164       }
 165     }
 166   }
 167
 168   // Update kill and LV information.
 169   KillMO->setIsKill(false);
 170   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 171   KillMO->setIsKill(true);
 172   LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
 173   VarInfo.removeKill(KillMI);
 174   VarInfo.Kills.push_back(MI);
 175
 176   // Move instruction to its destination.
 177   MBB->remove(MI);
 178   MBB->insert(KillPos, MI);
 179
 180   ++Num3AddrSunk;
 181   return true;
 182 }
 183
 184 /// runOnMachineFunction - Reduce two-address instructions to two
 185 /// operands.
 186 ///
 187 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 188   DOUT << "Machine Function\n";
 189   const TargetMachine &TM = MF.getTarget();
 190   MRI = &MF.getRegInfo();
 191   TII = TM.getInstrInfo();
 192   TRI = TM.getRegisterInfo();
 193   LV = &getAnalysis<LiveVariables>();
 194
 195   bool MadeChange = false;
 196
 197   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 198   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 199
 200   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 201        mbbi != mbbe; ++mbbi) {
 202     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 203          mi != me; ++mi) {
 204       const TargetInstrDesc &TID = mi->getDesc();
 205
 206       bool FirstTied = true;
 207       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 208         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 209         if (ti == -1)
 210           continue;
 211
 212         if (FirstTied) {
 213           ++NumTwoAddressInstrs;
 214           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 215         }
 216         FirstTied = false;
 217
 218         assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
 219                mi->getOperand(si).isUse() && "two address instruction invalid");
 220
 221         // if the two operands are the same we just remove the use
 222         // and mark the def as def&use, otherwise we have to insert a copy.
 223         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 224           // rewrite:
 225           //     a = b op c
 226           // to:
 227           //     a = b
 228           //     a = a op c
 229           unsigned regA = mi->getOperand(ti).getReg();
 230           unsigned regB = mi->getOperand(si).getReg();
 231
 232           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 233                  TargetRegisterInfo::isVirtualRegister(regB) &&
 234                  "cannot update physical register live information");
 235
 236 #ifndef NDEBUG
 237           // First, verify that we don't have a use of a in the instruction (a =
 238           // b + a for example) because our transformation will not work. This
 239           // should never occur because we are in SSA form.
 240           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 241             assert((int)i == ti ||
 242                    !mi->getOperand(i).isRegister() ||
 243                    mi->getOperand(i).getReg() != regA);
 244 #endif
 245
 246           // If this instruction is not the killing user of B, see if we can
 247           // rearrange the code to make it so.  Making it the killing user will
 248           // allow us to coalesce A and B together, eliminating the copy we are
 249           // about to insert.
 250           if (!mi->killsRegister(regB)) {
 251             // If this instruction is commutative, check to see if C dies.  If
 252             // so, swap the B and C operands.  This makes the live ranges of A
 253             // and C joinable.
 254             // FIXME: This code also works for A := B op C instructions.
 255             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 256               assert(mi->getOperand(3-si).isRegister() &&
 257                      "Not a proper commutative instruction!");
 258               unsigned regC = mi->getOperand(3-si).getReg();
 259               if (mi->killsRegister(regC)) {
 260                 DOUT << "2addr: COMMUTING  : " << *mi;
 261                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 262                 if (NewMI == 0) {
 263                   DOUT << "2addr: COMMUTING FAILED!\n";
 264                 } else {
 265                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 266                   // If the instruction changed to commute it, update livevar.
 267                   if (NewMI != mi) {
 268                     LV->instructionChanged(mi, NewMI); // Update live variables
 269                     mbbi->insert(mi, NewMI);           // Insert the new inst
 270                     mbbi->erase(mi);                   // Nuke the old inst.
 271                     mi = NewMI;
 272                   }
 273
 274                   ++NumCommuted;
 275                   regB = regC;
 276                   goto InstructionRearranged;
 277                 }
 278               }
 279             }
 280
 281             // If this instruction is potentially convertible to a true
 282             // three-address instruction,
 283             if (TID.isConvertibleTo3Addr()) {
 284               // FIXME: This assumes there are no more operands which are tied
 285               // to another register.
 286 #ifndef NDEBUG
 287               for (unsigned i = si+1, e = TID.getNumOperands(); i < e; ++i)
 288                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 289 #endif
 290
 291               if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) {
 292                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 293                 DOUT << "2addr:         TO 3-ADDR: " << *New;
 294                 bool Sunk = false;
 295                 if (New->findRegisterUseOperand(regB, New, TRI))
 296                   // FIXME: Temporary workaround. If the new instruction doesn't
 297                   // uses regB, convertToThreeAddress must have created more
 298                   // then one instruction.
 299                   Sunk = Sink3AddrInstruction(mbbi, New, regB, mi);
 300                 mbbi->erase(mi);                 // Nuke the old inst.
 301                 if (!Sunk) mi = New;
 302                 ++NumConvertedTo3Addr;
 303                 // Done with this instruction.
 304                 break;
 305               }
 306             }
 307           }
 308
 309         InstructionRearranged:
 310           const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
 311           TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 312
 313           MachineBasicBlock::iterator prevMi = prior(mi);
 314           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 315
 316           // update live variables for regB
 317           LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 318           // regB is used in this BB.
 319           varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 320           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 321             LV->addVirtualRegisterKilled(regB, prevMi);
 322
 323           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 324             LV->addVirtualRegisterDead(regB, prevMi);
 325
 326           // replace all occurences of regB with regA
 327           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 328             if (mi->getOperand(i).isRegister() &&
 329                 mi->getOperand(i).getReg() == regB)
 330               mi->getOperand(i).setReg(regA);
 331           }
 332         }
 333
 334         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 335         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 336         MadeChange = true;
 337
 338         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 339       }
 340     }
 341   }
 342
 343   return MadeChange;
 344 }