lib/CodeGen/TwoAddressInstructionPass.cpp

   1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/SSARegMap.h"
  37 #include "llvm/Target/MRegisterInfo.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "Support/Debug.h"
  41 #include "Support/Statistic.h"
  42 #include "Support/STLExtras.h"
  43 using namespace llvm;
  44
  45 namespace {
  46   Statistic<> numTwoAddressInstrs("twoaddressinstruction",
  47                                   "Number of two-address instructions");
  48   Statistic<> numInstrsAdded("twoaddressinstruction",
  49                              "Number of instructions added");
  50
  51   struct TwoAddressInstructionPass : public MachineFunctionPass {
  52     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  53
  54     /// runOnMachineFunction - pass entry point
  55     bool runOnMachineFunction(MachineFunction&);
  56   };
  57
  58   RegisterPass<TwoAddressInstructionPass>
  59   X("twoaddressinstruction", "Two-Address instruction pass");
  60 };
  61
  62 const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
  63
  64 void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const {
  65   AU.addPreserved<LiveVariables>();
  66   AU.addPreservedID(PHIEliminationID);
  67   MachineFunctionPass::getAnalysisUsage(AU);
  68 }
  69
  70 /// runOnMachineFunction - Reduce two-address instructions to two
  71 /// operands.
  72 ///
  73 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
  74   DEBUG(std::cerr << "Machine Function\n");
  75   const TargetMachine &TM = MF.getTarget();
  76   const MRegisterInfo &MRI = *TM.getRegisterInfo();
  77   const TargetInstrInfo &TII = *TM.getInstrInfo();
  78   LiveVariables* LV = getAnalysisToUpdate<LiveVariables>();
  79
  80   bool MadeChange = false;
  81
  82   DEBUG(std::cerr << "********** REWRITING TWO-ADDR INSTRS **********\n");
  83   DEBUG(std::cerr << "********** Function: "
  84                   << MF.getFunction()->getName() << '\n');
  85
  86   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
  87        mbbi != mbbe; ++mbbi) {
  88     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
  89          mi != me; ++mi) {
  90       unsigned opcode = mi->getOpcode();
  91
  92       // ignore if it is not a two-address instruction
  93       if (!TII.isTwoAddrInstr(opcode))
  94         continue;
  95
  96       ++numTwoAddressInstrs;
  97       DEBUG(std::cerr << '\t'; mi->print(std::cerr, &TM));
  98       assert(mi->getOperand(1).isRegister() && mi->getOperand(1).getReg() &&
  99              mi->getOperand(1).isUse() && "two address instruction invalid");
 100
 101       // if the two operands are the same we just remove the use
 102       // and mark the def as def&use, otherwise we have to insert a copy.
 103       if (mi->getOperand(0).getReg() != mi->getOperand(1).getReg()) {
 104         // rewrite:
 105         //     a = b op c
 106         // to:
 107         //     a = b
 108         //     a = a op c
 109         unsigned regA = mi->getOperand(0).getReg();
 110         unsigned regB = mi->getOperand(1).getReg();
 111
 112         assert(MRegisterInfo::isVirtualRegister(regA) &&
 113                MRegisterInfo::isVirtualRegister(regB) &&
 114                "cannot update physical register live information");
 115
 116         // first make sure we do not have a use of a in the
 117         // instruction (a = b + a for example) because our
 118         // transformation will not work. This should never occur
 119         // because we are in SSA form.
 120 #ifndef NDEBUG
 121         for (unsigned i = 1; i != mi->getNumOperands(); ++i)
 122           assert(!mi->getOperand(i).isRegister() ||
 123                  mi->getOperand(i).getReg() != regA);
 124 #endif
 125
 126         const TargetRegisterClass* rc = MF.getSSARegMap()->getRegClass(regA);
 127         unsigned Added = MRI.copyRegToReg(*mbbi, mi, regA, regB, rc);
 128         numInstrsAdded += Added;
 129
 130         MachineBasicBlock::iterator prevMi = prior(mi);
 131         DEBUG(std::cerr << "\t\tprepend:\t"; prevMi->print(std::cerr, &TM));
 132
 133         if (LV) {
 134           // update live variables for regA
 135           assert(Added == 1 && "Cannot handle multi-instruction copies yet!");
 136           LiveVariables::VarInfo& varInfo = LV->getVarInfo(regA);
 137           varInfo.DefInst = prevMi;
 138
 139           // update live variables for regB
 140           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 141             LV->addVirtualRegisterKilled(regB, prevMi);
 142
 143           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 144             LV->addVirtualRegisterDead(regB, prevMi);
 145         }
 146
 147         // replace all occurences of regB with regA
 148         for (unsigned i = 1, e = mi->getNumOperands(); i != e; ++i) {
 149           if (mi->getOperand(i).isRegister() &&
 150               mi->getOperand(i).getReg() == regB)
 151             mi->SetMachineOperandReg(i, regA);
 152         }
 153       }
 154
 155       assert(mi->getOperand(0).isDef());
 156       mi->getOperand(0).setUse();
 157       mi->RemoveOperand(1);
 158       MadeChange = true;
 159
 160       DEBUG(std::cerr << "\t\trewrite to:\t"; mi->print(std::cerr, &TM));
 161     }
 162   }
 163
 164   return MadeChange;
 165 }