TwoAddressInstructionPass.cpp revision 8c2403631b9c83b6bb80ef61a7f6d5a34975e6a9
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 = A op C 20// 21//===----------------------------------------------------------------------===// 22 23#define DEBUG_TYPE "twoaddrinstr" 24#include "llvm/Function.h" 25#include "llvm/CodeGen/LiveVariables.h" 26#include "llvm/CodeGen/MachineFrameInfo.h" 27#include "llvm/CodeGen/MachineFunctionPass.h" 28#include "llvm/CodeGen/MachineInstr.h" 29#include "llvm/CodeGen/Passes.h" 30#include "llvm/CodeGen/SSARegMap.h" 31#include "llvm/Target/MRegisterInfo.h" 32#include "llvm/Target/TargetInstrInfo.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Target/TargetRegInfo.h" 35#include "Support/Debug.h" 36#include "Support/Statistic.h" 37#include "Support/STLExtras.h" 38#include <iostream> 39 40using namespace llvm; 41 42namespace { 43 class TwoAddressInstructionPass : public MachineFunctionPass 44 { 45 private: 46 MachineFunction* mf_; 47 const TargetMachine* tm_; 48 const MRegisterInfo* mri_; 49 LiveVariables* lv_; 50 51 public: 52 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 53 54 private: 55 /// runOnMachineFunction - pass entry point 56 bool runOnMachineFunction(MachineFunction&); 57 }; 58 59 RegisterPass<TwoAddressInstructionPass> X( 60 "twoaddressinstruction", "Two-Address instruction pass"); 61 62 Statistic<> numTwoAddressInstrs("twoaddressinstruction", 63 "Number of two-address instructions"); 64 Statistic<> numInstrsAdded("twoaddressinstruction", 65 "Number of instructions added"); 66}; 67 68const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo(); 69 70void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const 71{ 72 AU.addPreserved<LiveVariables>(); 73 AU.addRequired<LiveVariables>(); 74 AU.addPreservedID(PHIEliminationID); 75 AU.addRequiredID(PHIEliminationID); 76 MachineFunctionPass::getAnalysisUsage(AU); 77} 78 79/// runOnMachineFunction - Reduce two-address instructions to two 80/// operands 81/// 82bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &fn) { 83 DEBUG(std::cerr << "Machine Function\n"); 84 mf_ = &fn; 85 tm_ = &fn.getTarget(); 86 mri_ = tm_->getRegisterInfo(); 87 lv_ = &getAnalysis<LiveVariables>(); 88 89 const TargetInstrInfo& tii = tm_->getInstrInfo(); 90 91 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 92 mbbi != mbbe; ++mbbi) { 93 for (MachineBasicBlock::iterator mii = mbbi->begin(); 94 mii != mbbi->end(); ++mii) { 95 MachineInstr* mi = *mii; 96 97 unsigned opcode = mi->getOpcode(); 98 // ignore if it is not a two-address instruction 99 if (!tii.isTwoAddrInstr(opcode)) 100 continue; 101 102 ++numTwoAddressInstrs; 103 104 DEBUG(std::cerr << "\tinstruction: "; mi->print(std::cerr, *tm_)); 105 106 // we have nothing to do if the two operands are the same 107 if (mi->getOperand(0).getAllocatedRegNum() == 108 mi->getOperand(1).getAllocatedRegNum()) 109 continue; 110 111 assert(mi->getOperand(1).isRegister() && 112 mi->getOperand(1).getAllocatedRegNum() && 113 mi->getOperand(1).isUse() && 114 "two address instruction invalid"); 115 116 // rewrite: 117 // a = b op c 118 // to: 119 // a = b 120 // a = a op c 121 unsigned regA = mi->getOperand(0).getAllocatedRegNum(); 122 unsigned regB = mi->getOperand(1).getAllocatedRegNum(); 123 bool regAisPhysical = regA < MRegisterInfo::FirstVirtualRegister; 124 bool regBisPhysical = regB < MRegisterInfo::FirstVirtualRegister; 125 126 // first make sure we do not have a use of a in the 127 // instruction (a = b + a for example) because our 128 // transofrmation will not work. This should never occur 129 // because of SSA. 130 for (unsigned i = 1; i < mi->getNumOperands(); ++i) { 131 assert(!mi->getOperand(i).isRegister() || 132 mi->getOperand(i).getAllocatedRegNum() != (int)regA); 133 } 134 135 const TargetRegisterClass* rc = regAisPhysical ? 136 mri_->getRegClass(regA) : 137 mf_->getSSARegMap()->getRegClass(regA); 138 139 numInstrsAdded += mri_->copyRegToReg(*mbbi, mii, regA, regB, rc); 140 141 MachineInstr* prevMi = *(mii - 1); 142 DEBUG(std::cerr << "\t\tadded instruction: "; 143 prevMi->print(std::cerr, *tm_)); 144 145 // update live variables for regA 146 if (regAisPhysical) { 147 lv_->HandlePhysRegDef(regA, prevMi); 148 } 149 else { 150 LiveVariables::VarInfo& varInfo = lv_->getVarInfo(regA); 151 varInfo.DefInst = prevMi; 152 } 153 154 // update live variables for regB 155 if (regBisPhysical) { 156 lv_->HandlePhysRegUse(regB, prevMi); 157 } 158 else { 159 if (lv_->removeVirtualRegisterKilled(regB, &*mbbi, mi)) 160 lv_->addVirtualRegisterKilled(regB, &*mbbi, prevMi); 161 162 if (lv_->removeVirtualRegisterDead(regB, &*mbbi, mi)) 163 lv_->addVirtualRegisterDead(regB, &*mbbi, prevMi); 164 } 165 166 // replace all occurences of regB with regA 167 for (unsigned i = 1; i < mi->getNumOperands(); ++i) { 168 if (mi->getOperand(i).isRegister() && 169 mi->getOperand(i).getReg() == regB) 170 mi->SetMachineOperandReg(i, regA); 171 } 172 DEBUG(std::cerr << "\t\tmodified original to: "; 173 mi->print(std::cerr, *tm_)); 174 assert(mi->getOperand(0).getAllocatedRegNum() == 175 mi->getOperand(1).getAllocatedRegNum()); 176 } 177 } 178 179 return numInstrsAdded != 0; 180} 181