LLVM API Documentation
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 }