TwoAddressInstructionPass.cpp revision 875357d213ab1830efa1e3e9de0fcde95df7eefc
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/TargetRegisterInfo.h" 38#include "llvm/Target/TargetInstrInfo.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Support/CommandLine.h" 41#include "llvm/Support/Compiler.h" 42#include "llvm/Support/Debug.h" 43#include "llvm/ADT/Statistic.h" 44#include "llvm/ADT/STLExtras.h" 45using namespace llvm; 46 47STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 48STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 49STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 50STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 51 52namespace { 53 static cl::opt<int> 54 SinkLimit("two-addr-sink-limit", cl::init(-1), cl::Hidden); 55} 56 57namespace { 58 struct VISIBILITY_HIDDEN TwoAddressInstructionPass 59 : public MachineFunctionPass { 60 const TargetInstrInfo *TII; 61 const TargetRegisterInfo *TRI; 62 MachineRegisterInfo *MRI; 63 LiveVariables *LV; 64 65 public: 66 static char ID; // Pass identification, replacement for typeid 67 TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {} 68 69 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 70 71 /// runOnMachineFunction - pass entry point 72 bool runOnMachineFunction(MachineFunction&); 73 74 private: 75 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, 76 unsigned Reg, 77 MachineBasicBlock::iterator OldPos); 78 }; 79 80 char TwoAddressInstructionPass::ID = 0; 81 RegisterPass<TwoAddressInstructionPass> 82 X("twoaddressinstruction", "Two-Address instruction pass"); 83} 84 85const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo(); 86 87void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const { 88 AU.addRequired<LiveVariables>(); 89 AU.addPreserved<LiveVariables>(); 90 AU.addPreservedID(MachineLoopInfoID); 91 AU.addPreservedID(MachineDominatorsID); 92 AU.addPreservedID(PHIEliminationID); 93 MachineFunctionPass::getAnalysisUsage(AU); 94} 95 96/// Sink3AddrInstruction - A two-address instruction has been converted to a 97/// three-address instruction to avoid clobbering a register. Try to sink it 98/// past the instruction that would kill the above mentioned register to 99/// reduce register pressure. 100bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, 101 MachineInstr *MI, unsigned SavedReg, 102 MachineBasicBlock::iterator OldPos) { 103 // Check if it's safe to move this instruction. 104 bool SeenStore = true; // Be conservative. 105 if (!MI->isSafeToMove(TII, SeenStore)) 106 return false; 107 108 unsigned DefReg = 0; 109 SmallSet<unsigned, 4> UseRegs; 110 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 111 const MachineOperand &MO = MI->getOperand(i); 112 if (!MO.isRegister()) 113 continue; 114 unsigned MOReg = MO.getReg(); 115 if (!MOReg) 116 continue; 117 if (MO.isUse() && MOReg != SavedReg) 118 UseRegs.insert(MO.getReg()); 119 if (!MO.isDef()) 120 continue; 121 if (MO.isImplicit()) 122 // Don't try to move it if it implicitly defines a register. 123 return false; 124 if (DefReg) 125 // For now, don't move any instructions that define multiple registers. 126 return false; 127 DefReg = MO.getReg(); 128 } 129 130 // Find the instruction that kills SavedReg. 131 MachineInstr *KillMI = NULL; 132 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), 133 UE = MRI->use_end(); UI != UE; ++UI) { 134 MachineOperand &UseMO = UI.getOperand(); 135 if (!UseMO.isKill()) 136 continue; 137 KillMI = UseMO.getParent(); 138 break; 139 } 140 if (!KillMI || KillMI->getParent() != MBB) 141 return false; 142 143 // If any of the definitions are used by another instruction between 144 // the position and the kill use, then it's not safe to sink it. 145 // FIXME: This can be sped up if there is an easy way to query whether 146 // an instruction if before or after another instruction. Then we can 147 // use MachineRegisterInfo def / use instead. 148 MachineOperand *KillMO = NULL; 149 MachineBasicBlock::iterator KillPos = KillMI; 150 ++KillPos; 151 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { 152 MachineInstr *OtherMI = I; 153 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 154 MachineOperand &MO = OtherMI->getOperand(i); 155 if (!MO.isRegister()) 156 continue; 157 unsigned MOReg = MO.getReg(); 158 if (!MOReg) 159 continue; 160 if (DefReg == MOReg) 161 return false; 162 if (MO.isKill()) { 163 if (OtherMI == KillMI && MOReg == SavedReg) 164 // Save the operand that kills the register. We want unset the kill 165 // marker is we can sink MI past it. 166 KillMO = &MO; 167 else if (UseRegs.count(MOReg)) 168 // One of the uses is killed before the destination. 169 return false; 170 } 171 } 172 } 173 174 if (SinkLimit != -1 && Num3AddrSunk == (unsigned)SinkLimit) 175 return false; 176 177 // Update kill and LV information. 178 KillMO->setIsKill(false); 179 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 180 KillMO->setIsKill(true); 181 LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg); 182 VarInfo.removeKill(KillMI); 183 VarInfo.Kills.push_back(MI); 184 185 // Move instruction to its destination. 186 MBB->remove(MI); 187 MBB->insert(KillPos, MI); 188 189 ++Num3AddrSunk; 190 return true; 191} 192 193/// runOnMachineFunction - Reduce two-address instructions to two 194/// operands. 195/// 196bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 197 DOUT << "Machine Function\n"; 198 const TargetMachine &TM = MF.getTarget(); 199 MRI = &MF.getRegInfo(); 200 TII = TM.getInstrInfo(); 201 TRI = TM.getRegisterInfo(); 202 LV = &getAnalysis<LiveVariables>(); 203 204 bool MadeChange = false; 205 206 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 207 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 208 209 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 210 mbbi != mbbe; ++mbbi) { 211 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 212 mi != me; ++mi) { 213 const TargetInstrDesc &TID = mi->getDesc(); 214 215 bool FirstTied = true; 216 for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) { 217 int ti = TID.getOperandConstraint(si, TOI::TIED_TO); 218 if (ti == -1) 219 continue; 220 221 if (FirstTied) { 222 ++NumTwoAddressInstrs; 223 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM)); 224 } 225 FirstTied = false; 226 227 assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() && 228 mi->getOperand(si).isUse() && "two address instruction invalid"); 229 230 // if the two operands are the same we just remove the use 231 // and mark the def as def&use, otherwise we have to insert a copy. 232 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 233 // rewrite: 234 // a = b op c 235 // to: 236 // a = b 237 // a = a op c 238 unsigned regA = mi->getOperand(ti).getReg(); 239 unsigned regB = mi->getOperand(si).getReg(); 240 241 assert(TargetRegisterInfo::isVirtualRegister(regA) && 242 TargetRegisterInfo::isVirtualRegister(regB) && 243 "cannot update physical register live information"); 244 245#ifndef NDEBUG 246 // First, verify that we don't have a use of a in the instruction (a = 247 // b + a for example) because our transformation will not work. This 248 // should never occur because we are in SSA form. 249 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 250 assert((int)i == ti || 251 !mi->getOperand(i).isRegister() || 252 mi->getOperand(i).getReg() != regA); 253#endif 254 255 // If this instruction is not the killing user of B, see if we can 256 // rearrange the code to make it so. Making it the killing user will 257 // allow us to coalesce A and B together, eliminating the copy we are 258 // about to insert. 259 if (!mi->killsRegister(regB)) { 260 // If this instruction is commutative, check to see if C dies. If 261 // so, swap the B and C operands. This makes the live ranges of A 262 // and C joinable. 263 // FIXME: This code also works for A := B op C instructions. 264 if (TID.isCommutable() && mi->getNumOperands() >= 3) { 265 assert(mi->getOperand(3-si).isRegister() && 266 "Not a proper commutative instruction!"); 267 unsigned regC = mi->getOperand(3-si).getReg(); 268 if (mi->killsRegister(regC)) { 269 DOUT << "2addr: COMMUTING : " << *mi; 270 MachineInstr *NewMI = TII->commuteInstruction(mi); 271 if (NewMI == 0) { 272 DOUT << "2addr: COMMUTING FAILED!\n"; 273 } else { 274 DOUT << "2addr: COMMUTED TO: " << *NewMI; 275 // If the instruction changed to commute it, update livevar. 276 if (NewMI != mi) { 277 LV->instructionChanged(mi, NewMI); // Update live variables 278 mbbi->insert(mi, NewMI); // Insert the new inst 279 mbbi->erase(mi); // Nuke the old inst. 280 mi = NewMI; 281 } 282 283 ++NumCommuted; 284 regB = regC; 285 goto InstructionRearranged; 286 } 287 } 288 } 289 290 // If this instruction is potentially convertible to a true 291 // three-address instruction, 292 if (TID.isConvertibleTo3Addr()) { 293 // FIXME: This assumes there are no more operands which are tied 294 // to another register. 295#ifndef NDEBUG 296 for (unsigned i = si+1, e = TID.getNumOperands(); i < e; ++i) 297 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 298#endif 299 300 if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) { 301 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 302 DOUT << "2addr: TO 3-ADDR: " << *New; 303 bool Sunk = Sink3AddrInstruction(mbbi, New, regB, mi); 304 mbbi->erase(mi); // Nuke the old inst. 305 if (!Sunk) mi = New; 306 ++NumConvertedTo3Addr; 307 // Done with this instruction. 308 break; 309 } 310 } 311 } 312 313 InstructionRearranged: 314 const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA); 315 TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 316 317 MachineBasicBlock::iterator prevMi = prior(mi); 318 DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM)); 319 320 // update live variables for regB 321 LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB); 322 // regB is used in this BB. 323 varInfoB.UsedBlocks[mbbi->getNumber()] = true; 324 if (LV->removeVirtualRegisterKilled(regB, mbbi, mi)) 325 LV->addVirtualRegisterKilled(regB, prevMi); 326 327 if (LV->removeVirtualRegisterDead(regB, mbbi, mi)) 328 LV->addVirtualRegisterDead(regB, prevMi); 329 330 // replace all occurences of regB with regA 331 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 332 if (mi->getOperand(i).isRegister() && 333 mi->getOperand(i).getReg() == regB) 334 mi->getOperand(i).setReg(regA); 335 } 336 } 337 338 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 339 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 340 MadeChange = true; 341 342 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM)); 343 } 344 } 345 } 346 347 return MadeChange; 348} 349