TwoAddressInstructionPass.cpp revision 2d9716f7bfb701d4606a993765ea233116fe3a68
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/Target/TargetOptions.h" 41#include "llvm/Support/Compiler.h" 42#include "llvm/Support/Debug.h" 43#include "llvm/ADT/BitVector.h" 44#include "llvm/ADT/DenseMap.h" 45#include "llvm/ADT/SmallPtrSet.h" 46#include "llvm/ADT/Statistic.h" 47#include "llvm/ADT/STLExtras.h" 48using namespace llvm; 49 50STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 51STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 52STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 53STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 54STATISTIC(NumReMats, "Number of instructions re-materialized"); 55 56namespace { 57 class VISIBILITY_HIDDEN TwoAddressInstructionPass 58 : public MachineFunctionPass { 59 const TargetInstrInfo *TII; 60 const TargetRegisterInfo *TRI; 61 MachineRegisterInfo *MRI; 62 LiveVariables *LV; 63 64 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, 65 unsigned Reg, 66 MachineBasicBlock::iterator OldPos); 67 68 bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC, 69 MachineInstr *MI, MachineInstr *DefMI, 70 MachineBasicBlock *MBB, unsigned Loc, 71 DenseMap<MachineInstr*, unsigned> &DistanceMap); 72 public: 73 static char ID; // Pass identification, replacement for typeid 74 TwoAddressInstructionPass() : MachineFunctionPass(&ID) {} 75 76 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 77 AU.addPreserved<LiveVariables>(); 78 AU.addPreservedID(MachineLoopInfoID); 79 AU.addPreservedID(MachineDominatorsID); 80 if (StrongPHIElim) 81 AU.addPreservedID(StrongPHIEliminationID); 82 else 83 AU.addPreservedID(PHIEliminationID); 84 MachineFunctionPass::getAnalysisUsage(AU); 85 } 86 87 /// runOnMachineFunction - Pass entry point. 88 bool runOnMachineFunction(MachineFunction&); 89 }; 90} 91 92char TwoAddressInstructionPass::ID = 0; 93static RegisterPass<TwoAddressInstructionPass> 94X("twoaddressinstruction", "Two-Address instruction pass"); 95 96const PassInfo *const llvm::TwoAddressInstructionPassID = &X; 97 98/// Sink3AddrInstruction - A two-address instruction has been converted to a 99/// three-address instruction to avoid clobbering a register. Try to sink it 100/// past the instruction that would kill the above mentioned register to reduce 101/// register pressure. 102bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, 103 MachineInstr *MI, unsigned SavedReg, 104 MachineBasicBlock::iterator OldPos) { 105 // Check if it's safe to move this instruction. 106 bool SeenStore = true; // Be conservative. 107 if (!MI->isSafeToMove(TII, SeenStore)) 108 return false; 109 110 unsigned DefReg = 0; 111 SmallSet<unsigned, 4> UseRegs; 112 113 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 114 const MachineOperand &MO = MI->getOperand(i); 115 if (!MO.isReg()) 116 continue; 117 unsigned MOReg = MO.getReg(); 118 if (!MOReg) 119 continue; 120 if (MO.isUse() && MOReg != SavedReg) 121 UseRegs.insert(MO.getReg()); 122 if (!MO.isDef()) 123 continue; 124 if (MO.isImplicit()) 125 // Don't try to move it if it implicitly defines a register. 126 return false; 127 if (DefReg) 128 // For now, don't move any instructions that define multiple registers. 129 return false; 130 DefReg = MO.getReg(); 131 } 132 133 // Find the instruction that kills SavedReg. 134 MachineInstr *KillMI = NULL; 135 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), 136 UE = MRI->use_end(); UI != UE; ++UI) { 137 MachineOperand &UseMO = UI.getOperand(); 138 if (!UseMO.isKill()) 139 continue; 140 KillMI = UseMO.getParent(); 141 break; 142 } 143 144 if (!KillMI || KillMI->getParent() != MBB) 145 return false; 146 147 // If any of the definitions are used by another instruction between the 148 // position and the kill use, then it's not safe to sink it. 149 // 150 // FIXME: This can be sped up if there is an easy way to query whether an 151 // instruction is before or after another instruction. Then we can use 152 // MachineRegisterInfo def / use instead. 153 MachineOperand *KillMO = NULL; 154 MachineBasicBlock::iterator KillPos = KillMI; 155 ++KillPos; 156 157 unsigned NumVisited = 0; 158 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { 159 MachineInstr *OtherMI = I; 160 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 161 return false; 162 ++NumVisited; 163 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 164 MachineOperand &MO = OtherMI->getOperand(i); 165 if (!MO.isReg()) 166 continue; 167 unsigned MOReg = MO.getReg(); 168 if (!MOReg) 169 continue; 170 if (DefReg == MOReg) 171 return false; 172 173 if (MO.isKill()) { 174 if (OtherMI == KillMI && MOReg == SavedReg) 175 // Save the operand that kills the register. We want to unset the kill 176 // marker if we can sink MI past it. 177 KillMO = &MO; 178 else if (UseRegs.count(MOReg)) 179 // One of the uses is killed before the destination. 180 return false; 181 } 182 } 183 } 184 185 // Update kill and LV information. 186 KillMO->setIsKill(false); 187 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 188 KillMO->setIsKill(true); 189 190 if (LV) 191 LV->replaceKillInstruction(SavedReg, KillMI, MI); 192 193 // Move instruction to its destination. 194 MBB->remove(MI); 195 MBB->insert(KillPos, MI); 196 197 ++Num3AddrSunk; 198 return true; 199} 200 201/// isTwoAddrUse - Return true if the specified MI is using the specified 202/// register as a two-address operand. 203static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { 204 const TargetInstrDesc &TID = UseMI->getDesc(); 205 for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) { 206 MachineOperand &MO = UseMI->getOperand(i); 207 if (MO.isReg() && MO.getReg() == Reg && 208 (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1)) 209 // Earlier use is a two-address one. 210 return true; 211 } 212 return false; 213} 214 215/// isProfitableToReMat - Return true if the heuristics determines it is likely 216/// to be profitable to re-materialize the definition of Reg rather than copy 217/// the register. 218bool 219TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, 220 const TargetRegisterClass *RC, 221 MachineInstr *MI, MachineInstr *DefMI, 222 MachineBasicBlock *MBB, unsigned Loc, 223 DenseMap<MachineInstr*, unsigned> &DistanceMap){ 224 bool OtherUse = false; 225 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 226 UE = MRI->use_end(); UI != UE; ++UI) { 227 MachineOperand &UseMO = UI.getOperand(); 228 if (!UseMO.isUse()) 229 continue; 230 MachineInstr *UseMI = UseMO.getParent(); 231 MachineBasicBlock *UseMBB = UseMI->getParent(); 232 if (UseMBB == MBB) { 233 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 234 if (DI != DistanceMap.end() && DI->second == Loc) 235 continue; // Current use. 236 OtherUse = true; 237 // There is at least one other use in the MBB that will clobber the 238 // register. 239 if (isTwoAddrUse(UseMI, Reg)) 240 return true; 241 } 242 } 243 244 // If other uses in MBB are not two-address uses, then don't remat. 245 if (OtherUse) 246 return false; 247 248 // No other uses in the same block, remat if it's defined in the same 249 // block so it does not unnecessarily extend the live range. 250 return MBB == DefMI->getParent(); 251} 252 253/// runOnMachineFunction - Reduce two-address instructions to two operands. 254/// 255bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 256 DOUT << "Machine Function\n"; 257 const TargetMachine &TM = MF.getTarget(); 258 MRI = &MF.getRegInfo(); 259 TII = TM.getInstrInfo(); 260 TRI = TM.getRegisterInfo(); 261 LV = getAnalysisToUpdate<LiveVariables>(); 262 263 bool MadeChange = false; 264 265 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 266 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 267 268 // ReMatRegs - Keep track of the registers whose def's are remat'ed. 269 BitVector ReMatRegs; 270 ReMatRegs.resize(MRI->getLastVirtReg()+1); 271 272 // DistanceMap - Keep track the distance of a MI from the start of the 273 // current basic block. 274 DenseMap<MachineInstr*, unsigned> DistanceMap; 275 276 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 277 mbbi != mbbe; ++mbbi) { 278 unsigned Dist = 0; 279 DistanceMap.clear(); 280 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 281 mi != me; ) { 282 MachineBasicBlock::iterator nmi = next(mi); 283 const TargetInstrDesc &TID = mi->getDesc(); 284 bool FirstTied = true; 285 286 DistanceMap.insert(std::make_pair(mi, ++Dist)); 287 for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) { 288 int ti = TID.getOperandConstraint(si, TOI::TIED_TO); 289 if (ti == -1) 290 continue; 291 292 if (FirstTied) { 293 ++NumTwoAddressInstrs; 294 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM)); 295 } 296 297 FirstTied = false; 298 299 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && 300 mi->getOperand(si).isUse() && "two address instruction invalid"); 301 302 // If the two operands are the same we just remove the use 303 // and mark the def as def&use, otherwise we have to insert a copy. 304 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 305 // Rewrite: 306 // a = b op c 307 // to: 308 // a = b 309 // a = a op c 310 unsigned regA = mi->getOperand(ti).getReg(); 311 unsigned regB = mi->getOperand(si).getReg(); 312 313 assert(TargetRegisterInfo::isVirtualRegister(regA) && 314 TargetRegisterInfo::isVirtualRegister(regB) && 315 "cannot update physical register live information"); 316 317#ifndef NDEBUG 318 // First, verify that we don't have a use of a in the instruction (a = 319 // b + a for example) because our transformation will not work. This 320 // should never occur because we are in SSA form. 321 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 322 assert((int)i == ti || 323 !mi->getOperand(i).isReg() || 324 mi->getOperand(i).getReg() != regA); 325#endif 326 327 // If this instruction is not the killing user of B, see if we can 328 // rearrange the code to make it so. Making it the killing user will 329 // allow us to coalesce A and B together, eliminating the copy we are 330 // about to insert. 331 if (!mi->killsRegister(regB)) { 332 // If this instruction is commutative, check to see if C dies. If 333 // so, swap the B and C operands. This makes the live ranges of A 334 // and C joinable. 335 // FIXME: This code also works for A := B op C instructions. 336 if (TID.isCommutable() && mi->getNumOperands() >= 3) { 337 assert(mi->getOperand(3-si).isReg() && 338 "Not a proper commutative instruction!"); 339 unsigned regC = mi->getOperand(3-si).getReg(); 340 341 if (mi->killsRegister(regC)) { 342 DOUT << "2addr: COMMUTING : " << *mi; 343 MachineInstr *NewMI = TII->commuteInstruction(mi); 344 345 if (NewMI == 0) { 346 DOUT << "2addr: COMMUTING FAILED!\n"; 347 } else { 348 DOUT << "2addr: COMMUTED TO: " << *NewMI; 349 // If the instruction changed to commute it, update livevar. 350 if (NewMI != mi) { 351 if (LV) 352 // Update live variables 353 LV->replaceKillInstruction(regC, mi, NewMI); 354 355 mbbi->insert(mi, NewMI); // Insert the new inst 356 mbbi->erase(mi); // Nuke the old inst. 357 mi = NewMI; 358 DistanceMap.insert(std::make_pair(NewMI, Dist)); 359 } 360 361 ++NumCommuted; 362 regB = regC; 363 goto InstructionRearranged; 364 } 365 } 366 } 367 368 // If this instruction is potentially convertible to a true 369 // three-address instruction, 370 if (TID.isConvertibleTo3Addr()) { 371 // FIXME: This assumes there are no more operands which are tied 372 // to another register. 373#ifndef NDEBUG 374 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) 375 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 376#endif 377 378 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); 379 if (NewMI) { 380 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 381 DOUT << "2addr: TO 3-ADDR: " << *NewMI; 382 bool Sunk = false; 383 384 if (NewMI->findRegisterUseOperand(regB, false, TRI)) 385 // FIXME: Temporary workaround. If the new instruction doesn't 386 // uses regB, convertToThreeAddress must have created more 387 // then one instruction. 388 Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi); 389 390 mbbi->erase(mi); // Nuke the old inst. 391 392 if (!Sunk) { 393 DistanceMap.insert(std::make_pair(NewMI, Dist)); 394 mi = NewMI; 395 nmi = next(mi); 396 } 397 398 ++NumConvertedTo3Addr; 399 break; // Done with this instruction. 400 } 401 } 402 } 403 404 InstructionRearranged: 405 const TargetRegisterClass* rc = MRI->getRegClass(regA); 406 MachineInstr *DefMI = MRI->getVRegDef(regB); 407 // If it's safe and profitable, remat the definition instead of 408 // copying it. 409 if (DefMI && 410 DefMI->getDesc().isAsCheapAsAMove() && 411 DefMI->isSafeToReMat(TII, regB) && 412 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){ 413 DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n"); 414 TII->reMaterialize(*mbbi, mi, regA, DefMI); 415 ReMatRegs.set(regB); 416 ++NumReMats; 417 } else { 418 TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 419 } 420 421 MachineBasicBlock::iterator prevMi = prior(mi); 422 423 // Update live variables for regB. 424 if (LV) { 425 LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB); 426 427 // regB is used in this BB. 428 varInfoB.UsedBlocks[mbbi->getNumber()] = true; 429 430 if (LV->removeVirtualRegisterKilled(regB, mi)) 431 LV->addVirtualRegisterKilled(regB, prevMi); 432 433 if (LV->removeVirtualRegisterDead(regB, mi)) 434 LV->addVirtualRegisterDead(regB, prevMi); 435 } 436 437 DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM)); 438 439 // Replace all occurences of regB with regA. 440 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 441 if (mi->getOperand(i).isReg() && 442 mi->getOperand(i).getReg() == regB) 443 mi->getOperand(i).setReg(regA); 444 } 445 } 446 447 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 448 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 449 MadeChange = true; 450 451 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM)); 452 } 453 454 mi = nmi; 455 } 456 } 457 458 // Some remat'ed instructions are dead. 459 int VReg = ReMatRegs.find_first(); 460 while (VReg != -1) { 461 if (MRI->use_empty(VReg)) { 462 MachineInstr *DefMI = MRI->getVRegDef(VReg); 463 DefMI->eraseFromParent(); 464 } 465 VReg = ReMatRegs.find_next(VReg); 466 } 467 468 return MadeChange; 469} 470