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