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