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