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