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