TwoAddressInstructionPass.cpp revision ce63ffb52f249b62cdf2d250c128007b13f27e71
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/SmallSet.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(NumAggrCommuted , "Number of instructions aggressively commuted"); 53STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 54STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 55STATISTIC(NumReMats, "Number of instructions re-materialized"); 56STATISTIC(NumDeletes, "Number of dead instructions deleted"); 57 58namespace { 59 class VISIBILITY_HIDDEN TwoAddressInstructionPass 60 : public MachineFunctionPass { 61 const TargetInstrInfo *TII; 62 const TargetRegisterInfo *TRI; 63 MachineRegisterInfo *MRI; 64 LiveVariables *LV; 65 66 // DistanceMap - Keep track the distance of a MI from the start of the 67 // current basic block. 68 DenseMap<MachineInstr*, unsigned> DistanceMap; 69 70 // SrcRegMap - A map from virtual registers to physical registers which 71 // are likely targets to be coalesced to due to copies from physical 72 // registers to virtual registers. e.g. v1024 = move r0. 73 DenseMap<unsigned, unsigned> SrcRegMap; 74 75 // DstRegMap - A map from virtual registers to physical registers which 76 // are likely targets to be coalesced to due to copies to physical 77 // registers from virtual registers. e.g. r1 = move v1024. 78 DenseMap<unsigned, unsigned> DstRegMap; 79 80 bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, 81 unsigned Reg, 82 MachineBasicBlock::iterator OldPos); 83 84 bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC, 85 MachineInstr *MI, MachineInstr *DefMI, 86 MachineBasicBlock *MBB, unsigned Loc); 87 88 bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist, 89 unsigned &LastDef); 90 91 MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB, 92 unsigned Dist); 93 94 bool isProfitableToCommute(unsigned regB, unsigned regC, 95 MachineInstr *MI, MachineBasicBlock *MBB, 96 unsigned Dist); 97 98 bool CommuteInstruction(MachineBasicBlock::iterator &mi, 99 MachineFunction::iterator &mbbi, 100 unsigned RegB, unsigned RegC, unsigned Dist); 101 102 bool isProfitableToConv3Addr(unsigned RegA); 103 104 bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 105 MachineBasicBlock::iterator &nmi, 106 MachineFunction::iterator &mbbi, 107 unsigned RegB, unsigned Dist); 108 109 void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB, 110 SmallPtrSet<MachineInstr*, 8> &Processed); 111 public: 112 static char ID; // Pass identification, replacement for typeid 113 TwoAddressInstructionPass() : MachineFunctionPass(&ID) {} 114 115 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 116 AU.addPreserved<LiveVariables>(); 117 AU.addPreservedID(MachineLoopInfoID); 118 AU.addPreservedID(MachineDominatorsID); 119 if (StrongPHIElim) 120 AU.addPreservedID(StrongPHIEliminationID); 121 else 122 AU.addPreservedID(PHIEliminationID); 123 MachineFunctionPass::getAnalysisUsage(AU); 124 } 125 126 /// runOnMachineFunction - Pass entry point. 127 bool runOnMachineFunction(MachineFunction&); 128 }; 129} 130 131char TwoAddressInstructionPass::ID = 0; 132static RegisterPass<TwoAddressInstructionPass> 133X("twoaddressinstruction", "Two-Address instruction pass"); 134 135const PassInfo *const llvm::TwoAddressInstructionPassID = &X; 136 137/// Sink3AddrInstruction - A two-address instruction has been converted to a 138/// three-address instruction to avoid clobbering a register. Try to sink it 139/// past the instruction that would kill the above mentioned register to reduce 140/// register pressure. 141bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, 142 MachineInstr *MI, unsigned SavedReg, 143 MachineBasicBlock::iterator OldPos) { 144 // Check if it's safe to move this instruction. 145 bool SeenStore = true; // Be conservative. 146 if (!MI->isSafeToMove(TII, SeenStore)) 147 return false; 148 149 unsigned DefReg = 0; 150 SmallSet<unsigned, 4> UseRegs; 151 152 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 153 const MachineOperand &MO = MI->getOperand(i); 154 if (!MO.isReg()) 155 continue; 156 unsigned MOReg = MO.getReg(); 157 if (!MOReg) 158 continue; 159 if (MO.isUse() && MOReg != SavedReg) 160 UseRegs.insert(MO.getReg()); 161 if (!MO.isDef()) 162 continue; 163 if (MO.isImplicit()) 164 // Don't try to move it if it implicitly defines a register. 165 return false; 166 if (DefReg) 167 // For now, don't move any instructions that define multiple registers. 168 return false; 169 DefReg = MO.getReg(); 170 } 171 172 // Find the instruction that kills SavedReg. 173 MachineInstr *KillMI = NULL; 174 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), 175 UE = MRI->use_end(); UI != UE; ++UI) { 176 MachineOperand &UseMO = UI.getOperand(); 177 if (!UseMO.isKill()) 178 continue; 179 KillMI = UseMO.getParent(); 180 break; 181 } 182 183 if (!KillMI || KillMI->getParent() != MBB || KillMI == MI) 184 return false; 185 186 // If any of the definitions are used by another instruction between the 187 // position and the kill use, then it's not safe to sink it. 188 // 189 // FIXME: This can be sped up if there is an easy way to query whether an 190 // instruction is before or after another instruction. Then we can use 191 // MachineRegisterInfo def / use instead. 192 MachineOperand *KillMO = NULL; 193 MachineBasicBlock::iterator KillPos = KillMI; 194 ++KillPos; 195 196 unsigned NumVisited = 0; 197 for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { 198 MachineInstr *OtherMI = I; 199 if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 200 return false; 201 ++NumVisited; 202 for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 203 MachineOperand &MO = OtherMI->getOperand(i); 204 if (!MO.isReg()) 205 continue; 206 unsigned MOReg = MO.getReg(); 207 if (!MOReg) 208 continue; 209 if (DefReg == MOReg) 210 return false; 211 212 if (MO.isKill()) { 213 if (OtherMI == KillMI && MOReg == SavedReg) 214 // Save the operand that kills the register. We want to unset the kill 215 // marker if we can sink MI past it. 216 KillMO = &MO; 217 else if (UseRegs.count(MOReg)) 218 // One of the uses is killed before the destination. 219 return false; 220 } 221 } 222 } 223 224 // Update kill and LV information. 225 KillMO->setIsKill(false); 226 KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 227 KillMO->setIsKill(true); 228 229 if (LV) 230 LV->replaceKillInstruction(SavedReg, KillMI, MI); 231 232 // Move instruction to its destination. 233 MBB->remove(MI); 234 MBB->insert(KillPos, MI); 235 236 ++Num3AddrSunk; 237 return true; 238} 239 240/// isTwoAddrUse - Return true if the specified MI is using the specified 241/// register as a two-address operand. 242static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { 243 const TargetInstrDesc &TID = UseMI->getDesc(); 244 for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) { 245 MachineOperand &MO = UseMI->getOperand(i); 246 if (MO.isReg() && MO.getReg() == Reg && 247 (MO.isDef() || UseMI->isRegTiedToDefOperand(i))) 248 // Earlier use is a two-address one. 249 return true; 250 } 251 return false; 252} 253 254/// isProfitableToReMat - Return true if the heuristics determines it is likely 255/// to be profitable to re-materialize the definition of Reg rather than copy 256/// the register. 257bool 258TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, 259 const TargetRegisterClass *RC, 260 MachineInstr *MI, MachineInstr *DefMI, 261 MachineBasicBlock *MBB, unsigned Loc) { 262 bool OtherUse = false; 263 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 264 UE = MRI->use_end(); UI != UE; ++UI) { 265 MachineOperand &UseMO = UI.getOperand(); 266 MachineInstr *UseMI = UseMO.getParent(); 267 MachineBasicBlock *UseMBB = UseMI->getParent(); 268 if (UseMBB == MBB) { 269 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 270 if (DI != DistanceMap.end() && DI->second == Loc) 271 continue; // Current use. 272 OtherUse = true; 273 // There is at least one other use in the MBB that will clobber the 274 // register. 275 if (isTwoAddrUse(UseMI, Reg)) 276 return true; 277 } 278 } 279 280 // If other uses in MBB are not two-address uses, then don't remat. 281 if (OtherUse) 282 return false; 283 284 // No other uses in the same block, remat if it's defined in the same 285 // block so it does not unnecessarily extend the live range. 286 return MBB == DefMI->getParent(); 287} 288 289/// NoUseAfterLastDef - Return true if there are no intervening uses between the 290/// last instruction in the MBB that defines the specified register and the 291/// two-address instruction which is being processed. It also returns the last 292/// def location by reference 293bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg, 294 MachineBasicBlock *MBB, unsigned Dist, 295 unsigned &LastDef) { 296 LastDef = 0; 297 unsigned LastUse = Dist; 298 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 299 E = MRI->reg_end(); I != E; ++I) { 300 MachineOperand &MO = I.getOperand(); 301 MachineInstr *MI = MO.getParent(); 302 if (MI->getParent() != MBB) 303 continue; 304 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 305 if (DI == DistanceMap.end()) 306 continue; 307 if (MO.isUse() && DI->second < LastUse) 308 LastUse = DI->second; 309 if (MO.isDef() && DI->second > LastDef) 310 LastDef = DI->second; 311 } 312 313 return !(LastUse > LastDef && LastUse < Dist); 314} 315 316MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg, 317 MachineBasicBlock *MBB, 318 unsigned Dist) { 319 unsigned LastUseDist = 0; 320 MachineInstr *LastUse = 0; 321 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), 322 E = MRI->reg_end(); I != E; ++I) { 323 MachineOperand &MO = I.getOperand(); 324 MachineInstr *MI = MO.getParent(); 325 if (MI->getParent() != MBB) 326 continue; 327 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 328 if (DI == DistanceMap.end()) 329 continue; 330 if (DI->second >= Dist) 331 continue; 332 333 if (MO.isUse() && DI->second > LastUseDist) { 334 LastUse = DI->first; 335 LastUseDist = DI->second; 336 } 337 } 338 return LastUse; 339} 340 341/// isCopyToReg - Return true if the specified MI is a copy instruction or 342/// a extract_subreg instruction. It also returns the source and destination 343/// registers and whether they are physical registers by reference. 344static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 345 unsigned &SrcReg, unsigned &DstReg, 346 bool &IsSrcPhys, bool &IsDstPhys) { 347 SrcReg = 0; 348 DstReg = 0; 349 unsigned SrcSubIdx, DstSubIdx; 350 if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { 351 if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 352 DstReg = MI.getOperand(0).getReg(); 353 SrcReg = MI.getOperand(1).getReg(); 354 } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 355 DstReg = MI.getOperand(0).getReg(); 356 SrcReg = MI.getOperand(2).getReg(); 357 } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 358 DstReg = MI.getOperand(0).getReg(); 359 SrcReg = MI.getOperand(2).getReg(); 360 } 361 } 362 363 if (DstReg) { 364 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 365 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 366 return true; 367 } 368 return false; 369} 370 371/// isKilled - Test if the given register value, which is used by the given 372/// instruction, is killed by the given instruction. This looks through 373/// coalescable copies to see if the original value is potentially not killed. 374/// 375/// For example, in this code: 376/// 377/// %reg1034 = copy %reg1024 378/// %reg1035 = copy %reg1025<kill> 379/// %reg1036 = add %reg1034<kill>, %reg1035<kill> 380/// 381/// %reg1034 is not considered to be killed, since it is copied from a 382/// register which is not killed. Treating it as not killed lets the 383/// normal heuristics commute the (two-address) add, which lets 384/// coalescing eliminate the extra copy. 385/// 386static bool isKilled(MachineInstr &MI, unsigned Reg, 387 const MachineRegisterInfo *MRI, 388 const TargetInstrInfo *TII) { 389 MachineInstr *DefMI = &MI; 390 for (;;) { 391 if (!DefMI->killsRegister(Reg)) 392 return false; 393 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 394 return true; 395 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 396 // If there are multiple defs, we can't do a simple analysis, so just 397 // go with what the kill flag says. 398 if (next(Begin) != MRI->def_end()) 399 return true; 400 DefMI = &*Begin; 401 bool IsSrcPhys, IsDstPhys; 402 unsigned SrcReg, DstReg; 403 // If the def is something other than a copy, then it isn't going to 404 // be coalesced, so follow the kill flag. 405 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 406 return true; 407 Reg = SrcReg; 408 } 409} 410 411/// isTwoAddrUse - Return true if the specified MI uses the specified register 412/// as a two-address use. If so, return the destination register by reference. 413static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 414 const TargetInstrDesc &TID = MI.getDesc(); 415 unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM) 416 ? MI.getNumOperands() : TID.getNumOperands(); 417 for (unsigned i = 0; i != NumOps; ++i) { 418 const MachineOperand &MO = MI.getOperand(i); 419 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 420 continue; 421 unsigned ti; 422 if (MI.isRegTiedToDefOperand(i, &ti)) { 423 DstReg = MI.getOperand(ti).getReg(); 424 return true; 425 } 426 } 427 return false; 428} 429 430/// findOnlyInterestingUse - Given a register, if has a single in-basic block 431/// use, return the use instruction if it's a copy or a two-address use. 432static 433MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 434 MachineRegisterInfo *MRI, 435 const TargetInstrInfo *TII, 436 bool &IsCopy, 437 unsigned &DstReg, bool &IsDstPhys) { 438 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg); 439 if (UI == MRI->use_end()) 440 return 0; 441 MachineInstr &UseMI = *UI; 442 if (++UI != MRI->use_end()) 443 // More than one use. 444 return 0; 445 if (UseMI.getParent() != MBB) 446 return 0; 447 unsigned SrcReg; 448 bool IsSrcPhys; 449 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 450 IsCopy = true; 451 return &UseMI; 452 } 453 IsDstPhys = false; 454 if (isTwoAddrUse(UseMI, Reg, DstReg)) { 455 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 456 return &UseMI; 457 } 458 return 0; 459} 460 461/// getMappedReg - Return the physical register the specified virtual register 462/// might be mapped to. 463static unsigned 464getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 465 while (TargetRegisterInfo::isVirtualRegister(Reg)) { 466 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 467 if (SI == RegMap.end()) 468 return 0; 469 Reg = SI->second; 470 } 471 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 472 return Reg; 473 return 0; 474} 475 476/// regsAreCompatible - Return true if the two registers are equal or aliased. 477/// 478static bool 479regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 480 if (RegA == RegB) 481 return true; 482 if (!RegA || !RegB) 483 return false; 484 return TRI->regsOverlap(RegA, RegB); 485} 486 487 488/// isProfitableToReMat - Return true if it's potentially profitable to commute 489/// the two-address instruction that's being processed. 490bool 491TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, 492 MachineInstr *MI, MachineBasicBlock *MBB, 493 unsigned Dist) { 494 // Determine if it's profitable to commute this two address instruction. In 495 // general, we want no uses between this instruction and the definition of 496 // the two-address register. 497 // e.g. 498 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 499 // %reg1029<def> = MOV8rr %reg1028 500 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 501 // insert => %reg1030<def> = MOV8rr %reg1028 502 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 503 // In this case, it might not be possible to coalesce the second MOV8rr 504 // instruction if the first one is coalesced. So it would be profitable to 505 // commute it: 506 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 507 // %reg1029<def> = MOV8rr %reg1028 508 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 509 // insert => %reg1030<def> = MOV8rr %reg1029 510 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 511 512 if (!MI->killsRegister(regC)) 513 return false; 514 515 // Ok, we have something like: 516 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 517 // let's see if it's worth commuting it. 518 519 // Look for situations like this: 520 // %reg1024<def> = MOV r1 521 // %reg1025<def> = MOV r0 522 // %reg1026<def> = ADD %reg1024, %reg1025 523 // r0 = MOV %reg1026 524 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 525 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 526 unsigned FromRegC = getMappedReg(regC, SrcRegMap); 527 unsigned ToRegB = getMappedReg(regB, DstRegMap); 528 unsigned ToRegC = getMappedReg(regC, DstRegMap); 529 if (!regsAreCompatible(FromRegB, ToRegB, TRI) && 530 (regsAreCompatible(FromRegB, ToRegC, TRI) || 531 regsAreCompatible(FromRegC, ToRegB, TRI))) 532 return true; 533 534 // If there is a use of regC between its last def (could be livein) and this 535 // instruction, then bail. 536 unsigned LastDefC = 0; 537 if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC)) 538 return false; 539 540 // If there is a use of regB between its last def (could be livein) and this 541 // instruction, then go ahead and make this transformation. 542 unsigned LastDefB = 0; 543 if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB)) 544 return true; 545 546 // Since there are no intervening uses for both registers, then commute 547 // if the def of regC is closer. Its live interval is shorter. 548 return LastDefB && LastDefC && LastDefC > LastDefB; 549} 550 551/// CommuteInstruction - Commute a two-address instruction and update the basic 552/// block, distance map, and live variables if needed. Return true if it is 553/// successful. 554bool 555TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, 556 MachineFunction::iterator &mbbi, 557 unsigned RegB, unsigned RegC, unsigned Dist) { 558 MachineInstr *MI = mi; 559 DOUT << "2addr: COMMUTING : " << *MI; 560 MachineInstr *NewMI = TII->commuteInstruction(MI); 561 562 if (NewMI == 0) { 563 DOUT << "2addr: COMMUTING FAILED!\n"; 564 return false; 565 } 566 567 DOUT << "2addr: COMMUTED TO: " << *NewMI; 568 // If the instruction changed to commute it, update livevar. 569 if (NewMI != MI) { 570 if (LV) 571 // Update live variables 572 LV->replaceKillInstruction(RegC, MI, NewMI); 573 574 mbbi->insert(mi, NewMI); // Insert the new inst 575 mbbi->erase(mi); // Nuke the old inst. 576 mi = NewMI; 577 DistanceMap.insert(std::make_pair(NewMI, Dist)); 578 } 579 580 // Update source register map. 581 unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 582 if (FromRegC) { 583 unsigned RegA = MI->getOperand(0).getReg(); 584 SrcRegMap[RegA] = FromRegC; 585 } 586 587 return true; 588} 589 590/// isProfitableToConv3Addr - Return true if it is profitable to convert the 591/// given 2-address instruction to a 3-address one. 592bool 593TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) { 594 // Look for situations like this: 595 // %reg1024<def> = MOV r1 596 // %reg1025<def> = MOV r0 597 // %reg1026<def> = ADD %reg1024, %reg1025 598 // r2 = MOV %reg1026 599 // Turn ADD into a 3-address instruction to avoid a copy. 600 unsigned FromRegA = getMappedReg(RegA, SrcRegMap); 601 unsigned ToRegA = getMappedReg(RegA, DstRegMap); 602 return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI)); 603} 604 605/// ConvertInstTo3Addr - Convert the specified two-address instruction into a 606/// three address one. Return true if this transformation was successful. 607bool 608TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 609 MachineBasicBlock::iterator &nmi, 610 MachineFunction::iterator &mbbi, 611 unsigned RegB, unsigned Dist) { 612 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); 613 if (NewMI) { 614 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 615 DOUT << "2addr: TO 3-ADDR: " << *NewMI; 616 bool Sunk = false; 617 618 if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 619 // FIXME: Temporary workaround. If the new instruction doesn't 620 // uses RegB, convertToThreeAddress must have created more 621 // then one instruction. 622 Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi); 623 624 mbbi->erase(mi); // Nuke the old inst. 625 626 if (!Sunk) { 627 DistanceMap.insert(std::make_pair(NewMI, Dist)); 628 mi = NewMI; 629 nmi = next(mi); 630 } 631 return true; 632 } 633 634 return false; 635} 636 637/// ProcessCopy - If the specified instruction is not yet processed, process it 638/// if it's a copy. For a copy instruction, we find the physical registers the 639/// source and destination registers might be mapped to. These are kept in 640/// point-to maps used to determine future optimizations. e.g. 641/// v1024 = mov r0 642/// v1025 = mov r1 643/// v1026 = add v1024, v1025 644/// r1 = mov r1026 645/// If 'add' is a two-address instruction, v1024, v1026 are both potentially 646/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 647/// potentially joined with r1 on the output side. It's worthwhile to commute 648/// 'add' to eliminate a copy. 649void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, 650 MachineBasicBlock *MBB, 651 SmallPtrSet<MachineInstr*, 8> &Processed) { 652 if (Processed.count(MI)) 653 return; 654 655 bool IsSrcPhys, IsDstPhys; 656 unsigned SrcReg, DstReg; 657 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 658 return; 659 660 if (IsDstPhys && !IsSrcPhys) 661 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 662 else if (!IsDstPhys && IsSrcPhys) { 663 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 664 if (!isNew) 665 assert(SrcRegMap[DstReg] == SrcReg && 666 "Can't map to two src physical registers!"); 667 668 SmallVector<unsigned, 4> VirtRegPairs; 669 bool IsCopy = false; 670 unsigned NewReg = 0; 671 while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII, 672 IsCopy, NewReg, IsDstPhys)) { 673 if (IsCopy) { 674 if (!Processed.insert(UseMI)) 675 break; 676 } 677 678 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 679 if (DI != DistanceMap.end()) 680 // Earlier in the same MBB.Reached via a back edge. 681 break; 682 683 if (IsDstPhys) { 684 VirtRegPairs.push_back(NewReg); 685 break; 686 } 687 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second; 688 if (!isNew) 689 assert(SrcRegMap[NewReg] == DstReg && 690 "Can't map to two src physical registers!"); 691 VirtRegPairs.push_back(NewReg); 692 DstReg = NewReg; 693 } 694 695 if (!VirtRegPairs.empty()) { 696 unsigned ToReg = VirtRegPairs.back(); 697 VirtRegPairs.pop_back(); 698 while (!VirtRegPairs.empty()) { 699 unsigned FromReg = VirtRegPairs.back(); 700 VirtRegPairs.pop_back(); 701 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 702 if (!isNew) 703 assert(DstRegMap[FromReg] == ToReg && 704 "Can't map to two dst physical registers!"); 705 ToReg = FromReg; 706 } 707 } 708 } 709 710 Processed.insert(MI); 711} 712 713/// isSafeToDelete - If the specified instruction does not produce any side 714/// effects and all of its defs are dead, then it's safe to delete. 715static bool isSafeToDelete(MachineInstr *MI, unsigned Reg, 716 const TargetInstrInfo *TII, 717 SmallVector<unsigned, 4> &Kills) { 718 const TargetInstrDesc &TID = MI->getDesc(); 719 if (TID.mayStore() || TID.isCall()) 720 return false; 721 if (TID.isTerminator() || TID.hasUnmodeledSideEffects()) 722 return false; 723 724 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 725 MachineOperand &MO = MI->getOperand(i); 726 if (!MO.isReg()) 727 continue; 728 if (MO.isDef() && !MO.isDead()) 729 return false; 730 if (MO.isUse() && MO.getReg() != Reg && MO.isKill()) 731 Kills.push_back(MO.getReg()); 732 } 733 734 return true; 735} 736 737/// runOnMachineFunction - Reduce two-address instructions to two operands. 738/// 739bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 740 DOUT << "Machine Function\n"; 741 const TargetMachine &TM = MF.getTarget(); 742 MRI = &MF.getRegInfo(); 743 TII = TM.getInstrInfo(); 744 TRI = TM.getRegisterInfo(); 745 LV = getAnalysisIfAvailable<LiveVariables>(); 746 747 bool MadeChange = false; 748 749 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 750 DEBUG(errs() << "********** Function: " 751 << MF.getFunction()->getName() << '\n'); 752 753 // ReMatRegs - Keep track of the registers whose def's are remat'ed. 754 BitVector ReMatRegs; 755 ReMatRegs.resize(MRI->getLastVirtReg()+1); 756 757 SmallPtrSet<MachineInstr*, 8> Processed; 758 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 759 mbbi != mbbe; ++mbbi) { 760 unsigned Dist = 0; 761 DistanceMap.clear(); 762 SrcRegMap.clear(); 763 DstRegMap.clear(); 764 Processed.clear(); 765 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 766 mi != me; ) { 767 MachineBasicBlock::iterator nmi = next(mi); 768 const TargetInstrDesc &TID = mi->getDesc(); 769 bool FirstTied = true; 770 771 DistanceMap.insert(std::make_pair(mi, ++Dist)); 772 773 ProcessCopy(&*mi, &*mbbi, Processed); 774 775 unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM) 776 ? mi->getNumOperands() : TID.getNumOperands(); 777 for (unsigned si = 0; si < NumOps; ++si) { 778 unsigned ti = 0; 779 if (!mi->isRegTiedToDefOperand(si, &ti)) 780 continue; 781 782 if (FirstTied) { 783 ++NumTwoAddressInstrs; 784 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM)); 785 } 786 787 FirstTied = false; 788 789 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && 790 mi->getOperand(si).isUse() && "two address instruction invalid"); 791 792 // If the two operands are the same we just remove the use 793 // and mark the def as def&use, otherwise we have to insert a copy. 794 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 795 // Rewrite: 796 // a = b op c 797 // to: 798 // a = b 799 // a = a op c 800 unsigned regA = mi->getOperand(ti).getReg(); 801 unsigned regB = mi->getOperand(si).getReg(); 802 unsigned regASubIdx = mi->getOperand(ti).getSubReg(); 803 804 assert(TargetRegisterInfo::isVirtualRegister(regB) && 805 "cannot update physical register live information"); 806 807#ifndef NDEBUG 808 // First, verify that we don't have a use of a in the instruction (a = 809 // b + a for example) because our transformation will not work. This 810 // should never occur because we are in SSA form. 811 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 812 assert(i == ti || 813 !mi->getOperand(i).isReg() || 814 mi->getOperand(i).getReg() != regA); 815#endif 816 817 // If this instruction is not the killing user of B, see if we can 818 // rearrange the code to make it so. Making it the killing user will 819 // allow us to coalesce A and B together, eliminating the copy we are 820 // about to insert. 821 if (!isKilled(*mi, regB, MRI, TII)) { 822 // If regA is dead and the instruction can be deleted, just delete 823 // it so it doesn't clobber regB. 824 SmallVector<unsigned, 4> Kills; 825 if (mi->getOperand(ti).isDead() && 826 isSafeToDelete(mi, regB, TII, Kills)) { 827 SmallVector<std::pair<std::pair<unsigned, bool> 828 ,MachineInstr*>, 4> NewKills; 829 bool ReallySafe = true; 830 // If this instruction kills some virtual registers, we need 831 // update the kill information. If it's not possible to do so, 832 // then bail out. 833 while (!Kills.empty()) { 834 unsigned Kill = Kills.back(); 835 Kills.pop_back(); 836 if (TargetRegisterInfo::isPhysicalRegister(Kill)) { 837 ReallySafe = false; 838 break; 839 } 840 MachineInstr *LastKill = FindLastUseInMBB(Kill, &*mbbi, Dist); 841 if (LastKill) { 842 bool isModRef = LastKill->modifiesRegister(Kill); 843 NewKills.push_back(std::make_pair(std::make_pair(Kill,isModRef), 844 LastKill)); 845 } else { 846 ReallySafe = false; 847 break; 848 } 849 } 850 851 if (ReallySafe) { 852 if (LV) { 853 while (!NewKills.empty()) { 854 MachineInstr *NewKill = NewKills.back().second; 855 unsigned Kill = NewKills.back().first.first; 856 bool isDead = NewKills.back().first.second; 857 NewKills.pop_back(); 858 if (LV->removeVirtualRegisterKilled(Kill, mi)) { 859 if (isDead) 860 LV->addVirtualRegisterDead(Kill, NewKill); 861 else 862 LV->addVirtualRegisterKilled(Kill, NewKill); 863 } 864 } 865 } 866 867 // We're really going to nuke the old inst. If regB was marked 868 // as a kill we need to update its Kills list. 869 if (mi->getOperand(si).isKill()) 870 LV->removeVirtualRegisterKilled(regB, mi); 871 872 mbbi->erase(mi); // Nuke the old inst. 873 mi = nmi; 874 ++NumDeletes; 875 break; // Done with this instruction. 876 } 877 } 878 879 // If this instruction is commutative, check to see if C dies. If 880 // so, swap the B and C operands. This makes the live ranges of A 881 // and C joinable. 882 // FIXME: This code also works for A := B op C instructions. 883 unsigned SrcOp1, SrcOp2; 884 if (TID.isCommutable() && mi->getNumOperands() >= 3 && 885 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { 886 unsigned regC = 0; 887 if (si == SrcOp1) 888 regC = mi->getOperand(SrcOp2).getReg(); 889 else if (si == SrcOp2) 890 regC = mi->getOperand(SrcOp1).getReg(); 891 if (isKilled(*mi, regC, MRI, TII)) { 892 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 893 ++NumCommuted; 894 regB = regC; 895 goto InstructionRearranged; 896 } 897 } 898 } 899 900 // If this instruction is potentially convertible to a true 901 // three-address instruction, 902 if (TID.isConvertibleTo3Addr()) { 903 // FIXME: This assumes there are no more operands which are tied 904 // to another register. 905#ifndef NDEBUG 906 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) 907 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 908#endif 909 910 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 911 ++NumConvertedTo3Addr; 912 break; // Done with this instruction. 913 } 914 } 915 } 916 917 // If it's profitable to commute the instruction, do so. 918 unsigned SrcOp1, SrcOp2; 919 if (TID.isCommutable() && mi->getNumOperands() >= 3 && 920 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { 921 unsigned regC = 0; 922 if (si == SrcOp1) 923 regC = mi->getOperand(SrcOp2).getReg(); 924 else if (si == SrcOp2) 925 regC = mi->getOperand(SrcOp1).getReg(); 926 927 if (regC && isProfitableToCommute(regB, regC, mi, mbbi, Dist)) 928 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 929 ++NumAggrCommuted; 930 ++NumCommuted; 931 regB = regC; 932 goto InstructionRearranged; 933 } 934 } 935 936 // If it's profitable to convert the 2-address instruction to a 937 // 3-address one, do so. 938 if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) { 939 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 940 ++NumConvertedTo3Addr; 941 break; // Done with this instruction. 942 } 943 } 944 945 InstructionRearranged: 946 const TargetRegisterClass* rc = MRI->getRegClass(regB); 947 MachineInstr *DefMI = MRI->getVRegDef(regB); 948 // If it's safe and profitable, remat the definition instead of 949 // copying it. 950 if (DefMI && 951 DefMI->getDesc().isAsCheapAsAMove() && 952 DefMI->isSafeToReMat(TII, regB) && 953 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ 954 DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n"); 955 TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI); 956 ReMatRegs.set(regB); 957 ++NumReMats; 958 } else { 959 bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 960 (void)Emitted; 961 assert(Emitted && "Unable to issue a copy instruction!\n"); 962 } 963 964 MachineBasicBlock::iterator prevMI = prior(mi); 965 // Update DistanceMap. 966 DistanceMap.insert(std::make_pair(prevMI, Dist)); 967 DistanceMap[mi] = ++Dist; 968 969 // Update live variables for regB. 970 if (LV) { 971 if (LV->removeVirtualRegisterKilled(regB, mi)) 972 LV->addVirtualRegisterKilled(regB, prevMI); 973 974 if (LV->removeVirtualRegisterDead(regB, mi)) 975 LV->addVirtualRegisterDead(regB, prevMI); 976 } 977 978 DOUT << "\t\tprepend:\t"; DEBUG(prevMI->print(*cerr.stream(), &TM)); 979 980 // Replace all occurences of regB with regA. 981 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 982 if (mi->getOperand(i).isReg() && 983 mi->getOperand(i).getReg() == regB) 984 mi->getOperand(i).setReg(regA); 985 } 986 } 987 988 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 989 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 990 MadeChange = true; 991 992 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM)); 993 } 994 995 mi = nmi; 996 } 997 } 998 999 // Some remat'ed instructions are dead. 1000 int VReg = ReMatRegs.find_first(); 1001 while (VReg != -1) { 1002 if (MRI->use_empty(VReg)) { 1003 MachineInstr *DefMI = MRI->getVRegDef(VReg); 1004 DefMI->eraseFromParent(); 1005 } 1006 VReg = ReMatRegs.find_next(VReg); 1007 } 1008 1009 return MadeChange; 1010} 1011