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