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