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; ) {
 204       MachineBasicBlock::iterator nmi = next(mi);
 205       const TargetInstrDesc &TID = mi->getDesc();
 206
 207       bool FirstTied = true;
 208       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 209         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 210         if (ti == -1)
 211           continue;
 212
 213         if (FirstTied) {
 214           ++NumTwoAddressInstrs;
 215           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 216         }
 217         FirstTied = false;
 218
 219         assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
 220                mi->getOperand(si).isUse() && "two address instruction invalid");
 221
 222         // if the two operands are the same we just remove the use
 223         // and mark the def as def&use, otherwise we have to insert a copy.
 224         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 225           // rewrite:
 226           //     a = b op c
 227           // to:
 228           //     a = b
 229           //     a = a op c
 230           unsigned regA = mi->getOperand(ti).getReg();
 231           unsigned regB = mi->getOperand(si).getReg();
 232
 233           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 234                  TargetRegisterInfo::isVirtualRegister(regB) &&
 235                  "cannot update physical register live information");
 236
 237 #ifndef NDEBUG
 238           // First, verify that we don't have a use of a in the instruction (a =
 239           // b + a for example) because our transformation will not work. This
 240           // should never occur because we are in SSA form.
 241           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 242             assert((int)i == ti ||
 243                    !mi->getOperand(i).isRegister() ||
 244                    mi->getOperand(i).getReg() != regA);
 245 #endif
 246
 247           // If this instruction is not the killing user of B, see if we can
 248           // rearrange the code to make it so.  Making it the killing user will
 249           // allow us to coalesce A and B together, eliminating the copy we are
 250           // about to insert.
 251           if (!mi->killsRegister(regB)) {
 252             // If this instruction is commutative, check to see if C dies.  If
 253             // so, swap the B and C operands.  This makes the live ranges of A
 254             // and C joinable.
 255             // FIXME: This code also works for A := B op C instructions.
 256             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 257               assert(mi->getOperand(3-si).isRegister() &&
 258                      "Not a proper commutative instruction!");
 259               unsigned regC = mi->getOperand(3-si).getReg();
 260               if (mi->killsRegister(regC)) {
 261                 DOUT << "2addr: COMMUTING  : " << *mi;
 262                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 263                 if (NewMI == 0) {
 264                   DOUT << "2addr: COMMUTING FAILED!\n";
 265                 } else {
 266                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 267                   // If the instruction changed to commute it, update livevar.
 268                   if (NewMI != mi) {
 269                     LV->instructionChanged(mi, NewMI); // Update live variables
 270                     mbbi->insert(mi, NewMI);           // Insert the new inst
 271                     mbbi->erase(mi);                   // Nuke the old inst.
 272                     mi = NewMI;
 273                   }
 274
 275                   ++NumCommuted;
 276                   regB = regC;
 277                   goto InstructionRearranged;
 278                 }
 279               }
 280             }
 281
 282             // If this instruction is potentially convertible to a true
 283             // three-address instruction,
 284             if (TID.isConvertibleTo3Addr()) {
 285               // FIXME: This assumes there are no more operands which are tied
 286               // to another register.
 287 #ifndef NDEBUG
 288               for (unsigned i = si+1, e = TID.getNumOperands(); i < e; ++i)
 289                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 290 #endif
 291
 292               if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) {
 293                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 294                 DOUT << "2addr:         TO 3-ADDR: " << *New;
 295                 bool Sunk = false;
 296                 if (New->findRegisterUseOperand(regB, false, TRI))
 297                   // FIXME: Temporary workaround. If the new instruction doesn't
 298                   // uses regB, convertToThreeAddress must have created more
 299                   // then one instruction.
 300                   Sunk = Sink3AddrInstruction(mbbi, New, regB, mi);
 301                 mbbi->erase(mi);                 // Nuke the old inst.
 302                 if (!Sunk) {
 303                   mi = New;
 304                   nmi = next(mi);
 305                 }
 306                 ++NumConvertedTo3Addr;
 307                 // Done with this instruction.
 308                 break;
 309               }
 310             }
 311           }
 312
 313         InstructionRearranged:
 314           const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
 315           TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 316
 317           MachineBasicBlock::iterator prevMi = prior(mi);
 318           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 319
 320           // update live variables for regB
 321           LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 322           // regB is used in this BB.
 323           varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 324           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 325             LV->addVirtualRegisterKilled(regB, prevMi);
 326
 327           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 328             LV->addVirtualRegisterDead(regB, prevMi);
 329
 330           // replace all occurences of regB with regA
 331           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 332             if (mi->getOperand(i).isRegister() &&
 333                 mi->getOperand(i).getReg() == regB)
 334               mi->getOperand(i).setReg(regA);
 335           }
 336         }
 337
 338         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 339         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 340         MadeChange = true;
 341
 342         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 343       }
 344       mi = nmi;
 345     }
 346   }
 347
 348   return MadeChange;
 349 }