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