TwoAddressInstructionPass.cpp revision d10fd9791c20fd8368fa0ce94b626b769c6c8ba0
1//===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/MachineRegisterInfo.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/Support/Compiler.h" 42#include "llvm/ADT/Statistic.h" 43#include "llvm/ADT/STLExtras.h" 44using namespace llvm; 45 46STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 47STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 48STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 49 50namespace { 51 struct VISIBILITY_HIDDEN TwoAddressInstructionPass 52 : public MachineFunctionPass { 53 static char ID; // Pass identification, replacement for typeid 54 TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {} 55 56 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 57 58 /// runOnMachineFunction - pass entry point 59 bool runOnMachineFunction(MachineFunction&); 60 }; 61 62 char TwoAddressInstructionPass::ID = 0; 63 RegisterPass<TwoAddressInstructionPass> 64 X("twoaddressinstruction", "Two-Address instruction pass"); 65} 66 67const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo(); 68 69void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const { 70 AU.addRequired<LiveVariables>(); 71 AU.addPreserved<LiveVariables>(); 72 AU.addPreservedID(PHIEliminationID); 73 MachineFunctionPass::getAnalysisUsage(AU); 74} 75 76/// runOnMachineFunction - Reduce two-address instructions to two 77/// operands. 78/// 79bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 80 DOUT << "Machine Function\n"; 81 const TargetMachine &TM = MF.getTarget(); 82 const TargetInstrInfo &TII = *TM.getInstrInfo(); 83 LiveVariables &LV = getAnalysis<LiveVariables>(); 84 85 bool MadeChange = false; 86 87 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 88 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 89 90 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 91 mbbi != mbbe; ++mbbi) { 92 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 93 mi != me; ++mi) { 94 const TargetInstrDescriptor *TID = mi->getInstrDescriptor(); 95 96 bool FirstTied = true; 97 for (unsigned si = 1, e = TID->numOperands; si < e; ++si) { 98 int ti = TID->getOperandConstraint(si, TOI::TIED_TO); 99 if (ti == -1) 100 continue; 101 102 if (FirstTied) { 103 ++NumTwoAddressInstrs; 104 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM)); 105 } 106 FirstTied = false; 107 108 assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() && 109 mi->getOperand(si).isUse() && "two address instruction invalid"); 110 111 // if the two operands are the same we just remove the use 112 // and mark the def as def&use, otherwise we have to insert a copy. 113 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 114 // rewrite: 115 // a = b op c 116 // to: 117 // a = b 118 // a = a op c 119 unsigned regA = mi->getOperand(ti).getReg(); 120 unsigned regB = mi->getOperand(si).getReg(); 121 122 assert(MRegisterInfo::isVirtualRegister(regA) && 123 MRegisterInfo::isVirtualRegister(regB) && 124 "cannot update physical register live information"); 125 126#ifndef NDEBUG 127 // First, verify that we don't have a use of a in the instruction (a = 128 // b + a for example) because our transformation will not work. This 129 // should never occur because we are in SSA form. 130 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 131 assert((int)i == ti || 132 !mi->getOperand(i).isRegister() || 133 mi->getOperand(i).getReg() != regA); 134#endif 135 136 // If this instruction is not the killing user of B, see if we can 137 // rearrange the code to make it so. Making it the killing user will 138 // allow us to coalesce A and B together, eliminating the copy we are 139 // about to insert. 140 if (!LV.KillsRegister(mi, regB)) { 141 // If this instruction is commutative, check to see if C dies. If 142 // so, swap the B and C operands. This makes the live ranges of A 143 // and C joinable. 144 // FIXME: This code also works for A := B op C instructions. 145 if ((TID->Flags & M_COMMUTABLE) && mi->getNumOperands() >= 3) { 146 assert(mi->getOperand(3-si).isRegister() && 147 "Not a proper commutative instruction!"); 148 unsigned regC = mi->getOperand(3-si).getReg(); 149 if (LV.KillsRegister(mi, regC)) { 150 DOUT << "2addr: COMMUTING : " << *mi; 151 MachineInstr *NewMI = TII.commuteInstruction(mi); 152 if (NewMI == 0) { 153 DOUT << "2addr: COMMUTING FAILED!\n"; 154 } else { 155 DOUT << "2addr: COMMUTED TO: " << *NewMI; 156 // If the instruction changed to commute it, update livevar. 157 if (NewMI != mi) { 158 LV.instructionChanged(mi, NewMI); // Update live variables 159 mbbi->insert(mi, NewMI); // Insert the new inst 160 mbbi->erase(mi); // Nuke the old inst. 161 mi = NewMI; 162 } 163 164 ++NumCommuted; 165 regB = regC; 166 goto InstructionRearranged; 167 } 168 } 169 } 170 171 // If this instruction is potentially convertible to a true 172 // three-address instruction, 173 if (TID->Flags & M_CONVERTIBLE_TO_3_ADDR) { 174 // FIXME: This assumes there are no more operands which are tied 175 // to another register. 176#ifndef NDEBUG 177 for (unsigned i = si+1, e = TID->numOperands; i < e; ++i) 178 assert(TID->getOperandConstraint(i, TOI::TIED_TO) == -1); 179#endif 180 181 if (MachineInstr *New = TII.convertToThreeAddress(mbbi, mi, LV)) { 182 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 183 DOUT << "2addr: TO 3-ADDR: " << *New; 184 mbbi->erase(mi); // Nuke the old inst. 185 mi = New; 186 ++NumConvertedTo3Addr; 187 // Done with this instruction. 188 break; 189 } 190 } 191 } 192 193 InstructionRearranged: 194 const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA); 195 TII.copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 196 197 MachineBasicBlock::iterator prevMi = prior(mi); 198 DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM)); 199 200 // Update live variables for regA 201 LiveVariables::VarInfo& varInfo = LV.getVarInfo(regA); 202 varInfo.DefInst = prevMi; 203 204 // update live variables for regB 205 LiveVariables::VarInfo& varInfoB = LV.getVarInfo(regB); 206 // regB is used in this BB. 207 varInfoB.UsedBlocks[mbbi->getNumber()] = true; 208 if (LV.removeVirtualRegisterKilled(regB, mbbi, mi)) 209 LV.addVirtualRegisterKilled(regB, prevMi); 210 211 if (LV.removeVirtualRegisterDead(regB, mbbi, mi)) 212 LV.addVirtualRegisterDead(regB, prevMi); 213 214 // replace all occurences of regB with regA 215 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 216 if (mi->getOperand(i).isRegister() && 217 mi->getOperand(i).getReg() == regB) 218 mi->getOperand(i).setReg(regA); 219 } 220 } 221 222 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 223 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 224 MadeChange = true; 225 226 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM)); 227 } 228 } 229 } 230 231 return MadeChange; 232} 233