LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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/SSARegMap.h"
00037 #include "llvm/Target/MRegisterInfo.h"
00038 #include "llvm/Target/TargetInstrInfo.h"
00039 #include "llvm/Target/TargetMachine.h"
00040 #include "llvm/Support/Debug.h"
00041 #include "llvm/ADT/Statistic.h"
00042 #include "llvm/ADT/STLExtras.h"
00043 using namespace llvm;
00044 
00045 namespace {
00046   Statistic<> numTwoAddressInstrs("twoaddressinstruction",
00047                                   "Number of two-address instructions");
00048 
00049   struct TwoAddressInstructionPass : public MachineFunctionPass {
00050     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00051 
00052     /// runOnMachineFunction - pass entry point
00053     bool runOnMachineFunction(MachineFunction&);
00054   };
00055 
00056   RegisterPass<TwoAddressInstructionPass> 
00057   X("twoaddressinstruction", "Two-Address instruction pass");
00058 };
00059 
00060 const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
00061 
00062 void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const {
00063   AU.addPreserved<LiveVariables>();
00064   AU.addPreservedID(PHIEliminationID);
00065   MachineFunctionPass::getAnalysisUsage(AU);
00066 }
00067 
00068 /// runOnMachineFunction - Reduce two-address instructions to two
00069 /// operands.
00070 ///
00071 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
00072   DEBUG(std::cerr << "Machine Function\n");
00073   const TargetMachine &TM = MF.getTarget();
00074   const MRegisterInfo &MRI = *TM.getRegisterInfo();
00075   const TargetInstrInfo &TII = *TM.getInstrInfo();
00076   LiveVariables* LV = getAnalysisToUpdate<LiveVariables>();
00077 
00078   bool MadeChange = false;
00079 
00080   DEBUG(std::cerr << "********** REWRITING TWO-ADDR INSTRS **********\n");
00081   DEBUG(std::cerr << "********** Function: "
00082                   << MF.getFunction()->getName() << '\n');
00083 
00084   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
00085        mbbi != mbbe; ++mbbi) {
00086     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
00087          mi != me; ++mi) {
00088       unsigned opcode = mi->getOpcode();
00089 
00090       // ignore if it is not a two-address instruction
00091       if (!TII.isTwoAddrInstr(opcode))
00092         continue;
00093 
00094       ++numTwoAddressInstrs;
00095       DEBUG(std::cerr << '\t'; mi->print(std::cerr, &TM));
00096       assert(mi->getOperand(1).isRegister() && mi->getOperand(1).getReg() &&
00097              mi->getOperand(1).isUse() && "two address instruction invalid");
00098 
00099       // if the two operands are the same we just remove the use
00100       // and mark the def as def&use, otherwise we have to insert a copy.
00101       if (mi->getOperand(0).getReg() != mi->getOperand(1).getReg()) {
00102         // rewrite:
00103         //     a = b op c
00104         // to:
00105         //     a = b
00106         //     a = a op c
00107         unsigned regA = mi->getOperand(0).getReg();
00108         unsigned regB = mi->getOperand(1).getReg();
00109 
00110         assert(MRegisterInfo::isVirtualRegister(regA) &&
00111                MRegisterInfo::isVirtualRegister(regB) &&
00112                "cannot update physical register live information");
00113 
00114         // first make sure we do not have a use of a in the
00115         // instruction (a = b + a for example) because our
00116         // transformation will not work. This should never occur
00117         // because we are in SSA form.
00118 #ifndef NDEBUG
00119         for (unsigned i = 1; i != mi->getNumOperands(); ++i)
00120           assert(!mi->getOperand(i).isRegister() ||
00121                  mi->getOperand(i).getReg() != regA);
00122 #endif
00123 
00124         const TargetRegisterClass* rc = MF.getSSARegMap()->getRegClass(regA);
00125         MRI.copyRegToReg(*mbbi, mi, regA, regB, rc);
00126 
00127         MachineBasicBlock::iterator prevMi = prior(mi);
00128         DEBUG(std::cerr << "\t\tprepend:\t"; prevMi->print(std::cerr, &TM));
00129 
00130         if (LV) {
00131           // update live variables for regA
00132           LiveVariables::VarInfo& varInfo = LV->getVarInfo(regA);
00133           varInfo.DefInst = prevMi;
00134 
00135           // update live variables for regB
00136           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
00137             LV->addVirtualRegisterKilled(regB, prevMi);
00138 
00139           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
00140             LV->addVirtualRegisterDead(regB, prevMi);
00141         }
00142 
00143         // replace all occurences of regB with regA
00144         for (unsigned i = 1, e = mi->getNumOperands(); i != e; ++i) {
00145           if (mi->getOperand(i).isRegister() && 
00146               mi->getOperand(i).getReg() == regB)
00147             mi->SetMachineOperandReg(i, regA);
00148         }
00149       }
00150 
00151       assert(mi->getOperand(0).isDef());
00152       mi->getOperand(0).setUse();
00153       mi->RemoveOperand(1);
00154       MadeChange = true;
00155 
00156       DEBUG(std::cerr << "\t\trewrite to:\t"; mi->print(std::cerr, &TM));
00157     }
00158   }
00159 
00160   return MadeChange;
00161 }