TwoAddressInstructionPass.cpp revision 6ed0e20eb2dee4b08d33917ba569ad448aa0f047
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 || KillMI == MI) 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 } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 330 DstReg = MI.getOperand(0).getReg(); 331 SrcReg = MI.getOperand(2).getReg(); 332 } 333 } 334 335 if (DstReg) { 336 IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 337 IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 338 return true; 339 } 340 return false; 341} 342 343/// isKilled - Test if the given register value, which is used by the given 344/// instruction, is killed by the given instruction. This looks through 345/// coalescable copies to see if the original value is potentially not killed. 346/// 347/// For example, in this code: 348/// 349/// %reg1034 = copy %reg1024 350/// %reg1035 = copy %reg1025<kill> 351/// %reg1036 = add %reg1034<kill>, %reg1035<kill> 352/// 353/// %reg1034 is not considered to be killed, since it is copied from a 354/// register which is not killed. Treating it as not killed lets the 355/// normal heuristics commute the (two-address) add, which lets 356/// coalescing eliminate the extra copy. 357/// 358static bool isKilled(MachineInstr &MI, unsigned Reg, 359 const MachineRegisterInfo *MRI, 360 const TargetInstrInfo *TII) { 361 MachineInstr *DefMI = &MI; 362 for (;;) { 363 if (!DefMI->killsRegister(Reg)) 364 return false; 365 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 366 return true; 367 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 368 // If there are multiple defs, we can't do a simple analysis, so just 369 // go with what the kill flag says. 370 if (next(Begin) != MRI->def_end()) 371 return true; 372 DefMI = &*Begin; 373 bool IsSrcPhys, IsDstPhys; 374 unsigned SrcReg, DstReg; 375 // If the def is something other than a copy, then it isn't going to 376 // be coalesced, so follow the kill flag. 377 if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 378 return true; 379 Reg = SrcReg; 380 } 381} 382 383/// isTwoAddrUse - Return true if the specified MI uses the specified register 384/// as a two-address use. If so, return the destination register by reference. 385static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 386 const TargetInstrDesc &TID = MI.getDesc(); 387 unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM) 388 ? MI.getNumOperands() : TID.getNumOperands(); 389 for (unsigned i = 0; i != NumOps; ++i) { 390 const MachineOperand &MO = MI.getOperand(i); 391 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 392 continue; 393 unsigned ti; 394 if (MI.isRegTiedToDefOperand(i, &ti)) { 395 DstReg = MI.getOperand(ti).getReg(); 396 return true; 397 } 398 } 399 return false; 400} 401 402/// findOnlyInterestingUse - Given a register, if has a single in-basic block 403/// use, return the use instruction if it's a copy or a two-address use. 404static 405MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 406 MachineRegisterInfo *MRI, 407 const TargetInstrInfo *TII, 408 bool &isCopy, 409 unsigned &DstReg, bool &IsDstPhys) { 410 MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg); 411 if (UI == MRI->use_end()) 412 return 0; 413 MachineInstr &UseMI = *UI; 414 if (++UI != MRI->use_end()) 415 // More than one use. 416 return 0; 417 if (UseMI.getParent() != MBB) 418 return 0; 419 unsigned SrcReg; 420 bool IsSrcPhys; 421 if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 422 return &UseMI; 423 IsDstPhys = false; 424 if (isTwoAddrUse(UseMI, Reg, DstReg)) 425 return &UseMI; 426 return 0; 427} 428 429/// getMappedReg - Return the physical register the specified virtual register 430/// might be mapped to. 431static unsigned 432getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 433 while (TargetRegisterInfo::isVirtualRegister(Reg)) { 434 DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 435 if (SI == RegMap.end()) 436 return 0; 437 Reg = SI->second; 438 } 439 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 440 return Reg; 441 return 0; 442} 443 444/// regsAreCompatible - Return true if the two registers are equal or aliased. 445/// 446static bool 447regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 448 if (RegA == RegB) 449 return true; 450 if (!RegA || !RegB) 451 return false; 452 return TRI->regsOverlap(RegA, RegB); 453} 454 455 456/// isProfitableToReMat - Return true if it's potentially profitable to commute 457/// the two-address instruction that's being processed. 458bool 459TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, 460 MachineInstr *MI, MachineBasicBlock *MBB, 461 unsigned Dist) { 462 // Determine if it's profitable to commute this two address instruction. In 463 // general, we want no uses between this instruction and the definition of 464 // the two-address register. 465 // e.g. 466 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 467 // %reg1029<def> = MOV8rr %reg1028 468 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 469 // insert => %reg1030<def> = MOV8rr %reg1028 470 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 471 // In this case, it might not be possible to coalesce the second MOV8rr 472 // instruction if the first one is coalesced. So it would be profitable to 473 // commute it: 474 // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 475 // %reg1029<def> = MOV8rr %reg1028 476 // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 477 // insert => %reg1030<def> = MOV8rr %reg1029 478 // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 479 480 if (!MI->killsRegister(regC)) 481 return false; 482 483 // Ok, we have something like: 484 // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 485 // let's see if it's worth commuting it. 486 487 // Look for situations like this: 488 // %reg1024<def> = MOV r1 489 // %reg1025<def> = MOV r0 490 // %reg1026<def> = ADD %reg1024, %reg1025 491 // r0 = MOV %reg1026 492 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 493 unsigned FromRegB = getMappedReg(regB, SrcRegMap); 494 unsigned FromRegC = getMappedReg(regC, SrcRegMap); 495 unsigned ToRegB = getMappedReg(regB, DstRegMap); 496 unsigned ToRegC = getMappedReg(regC, DstRegMap); 497 if (!regsAreCompatible(FromRegB, ToRegB, TRI) && 498 (regsAreCompatible(FromRegB, ToRegC, TRI) || 499 regsAreCompatible(FromRegC, ToRegB, TRI))) 500 return true; 501 502 // If there is a use of regC between its last def (could be livein) and this 503 // instruction, then bail. 504 unsigned LastDefC = 0; 505 if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC)) 506 return false; 507 508 // If there is a use of regB between its last def (could be livein) and this 509 // instruction, then go ahead and make this transformation. 510 unsigned LastDefB = 0; 511 if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB)) 512 return true; 513 514 // Since there are no intervening uses for both registers, then commute 515 // if the def of regC is closer. Its live interval is shorter. 516 return LastDefB && LastDefC && LastDefC > LastDefB; 517} 518 519/// CommuteInstruction - Commute a two-address instruction and update the basic 520/// block, distance map, and live variables if needed. Return true if it is 521/// successful. 522bool 523TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, 524 MachineFunction::iterator &mbbi, 525 unsigned RegB, unsigned RegC, unsigned Dist) { 526 MachineInstr *MI = mi; 527 DOUT << "2addr: COMMUTING : " << *MI; 528 MachineInstr *NewMI = TII->commuteInstruction(MI); 529 530 if (NewMI == 0) { 531 DOUT << "2addr: COMMUTING FAILED!\n"; 532 return false; 533 } 534 535 DOUT << "2addr: COMMUTED TO: " << *NewMI; 536 // If the instruction changed to commute it, update livevar. 537 if (NewMI != MI) { 538 if (LV) 539 // Update live variables 540 LV->replaceKillInstruction(RegC, MI, NewMI); 541 542 mbbi->insert(mi, NewMI); // Insert the new inst 543 mbbi->erase(mi); // Nuke the old inst. 544 mi = NewMI; 545 DistanceMap.insert(std::make_pair(NewMI, Dist)); 546 } 547 548 // Update source register map. 549 unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 550 if (FromRegC) { 551 unsigned RegA = MI->getOperand(0).getReg(); 552 SrcRegMap[RegA] = FromRegC; 553 } 554 555 return true; 556} 557 558/// isProfitableToConv3Addr - Return true if it is profitable to convert the 559/// given 2-address instruction to a 3-address one. 560bool 561TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) { 562 // Look for situations like this: 563 // %reg1024<def> = MOV r1 564 // %reg1025<def> = MOV r0 565 // %reg1026<def> = ADD %reg1024, %reg1025 566 // r2 = MOV %reg1026 567 // Turn ADD into a 3-address instruction to avoid a copy. 568 unsigned FromRegA = getMappedReg(RegA, SrcRegMap); 569 unsigned ToRegA = getMappedReg(RegA, DstRegMap); 570 return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI)); 571} 572 573/// ConvertInstTo3Addr - Convert the specified two-address instruction into a 574/// three address one. Return true if this transformation was successful. 575bool 576TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, 577 MachineBasicBlock::iterator &nmi, 578 MachineFunction::iterator &mbbi, 579 unsigned RegB, unsigned Dist) { 580 MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); 581 if (NewMI) { 582 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi; 583 DOUT << "2addr: TO 3-ADDR: " << *NewMI; 584 bool Sunk = false; 585 586 if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 587 // FIXME: Temporary workaround. If the new instruction doesn't 588 // uses RegB, convertToThreeAddress must have created more 589 // then one instruction. 590 Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi); 591 592 mbbi->erase(mi); // Nuke the old inst. 593 594 if (!Sunk) { 595 DistanceMap.insert(std::make_pair(NewMI, Dist)); 596 mi = NewMI; 597 nmi = next(mi); 598 } 599 return true; 600 } 601 602 return false; 603} 604 605/// ProcessCopy - If the specified instruction is not yet processed, process it 606/// if it's a copy. For a copy instruction, we find the physical registers the 607/// source and destination registers might be mapped to. These are kept in 608/// point-to maps used to determine future optimizations. e.g. 609/// v1024 = mov r0 610/// v1025 = mov r1 611/// v1026 = add v1024, v1025 612/// r1 = mov r1026 613/// If 'add' is a two-address instruction, v1024, v1026 are both potentially 614/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 615/// potentially joined with r1 on the output side. It's worthwhile to commute 616/// 'add' to eliminate a copy. 617void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, 618 MachineBasicBlock *MBB, 619 SmallPtrSet<MachineInstr*, 8> &Processed) { 620 if (Processed.count(MI)) 621 return; 622 623 bool IsSrcPhys, IsDstPhys; 624 unsigned SrcReg, DstReg; 625 if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 626 return; 627 628 if (IsDstPhys && !IsSrcPhys) 629 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 630 else if (!IsDstPhys && IsSrcPhys) { 631 bool isNew = 632 SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 633 isNew = isNew; // Silence compiler warning. 634 assert(isNew && "Can't map to two src physical registers!"); 635 636 SmallVector<unsigned, 4> VirtRegPairs; 637 bool isCopy = false; 638 unsigned NewReg = 0; 639 while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII, 640 isCopy, NewReg, IsDstPhys)) { 641 if (isCopy) { 642 if (Processed.insert(UseMI)) 643 break; 644 } 645 646 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 647 if (DI != DistanceMap.end()) 648 // Earlier in the same MBB.Reached via a back edge. 649 break; 650 651 if (IsDstPhys) { 652 VirtRegPairs.push_back(NewReg); 653 break; 654 } 655 bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second; 656 isNew = isNew; // Silence compiler warning. 657 assert(isNew && "Can't map to two src physical registers!"); 658 VirtRegPairs.push_back(NewReg); 659 DstReg = NewReg; 660 } 661 662 if (!VirtRegPairs.empty()) { 663 unsigned ToReg = VirtRegPairs.back(); 664 VirtRegPairs.pop_back(); 665 while (!VirtRegPairs.empty()) { 666 unsigned FromReg = VirtRegPairs.back(); 667 VirtRegPairs.pop_back(); 668 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 669 isNew = isNew; // Silence compiler warning. 670 assert(isNew && "Can't map to two dst physical registers!"); 671 ToReg = FromReg; 672 } 673 } 674 } 675 676 Processed.insert(MI); 677} 678 679/// isSafeToDelete - If the specified instruction does not produce any side 680/// effects and all of its defs are dead, then it's safe to delete. 681static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) { 682 const TargetInstrDesc &TID = MI->getDesc(); 683 if (TID.mayStore() || TID.isCall()) 684 return false; 685 if (TID.isTerminator() || TID.hasUnmodeledSideEffects()) 686 return false; 687 688 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 689 MachineOperand &MO = MI->getOperand(i); 690 if (!MO.isReg() || !MO.isDef()) 691 continue; 692 if (!MO.isDead()) 693 return false; 694 } 695 696 return true; 697} 698 699/// runOnMachineFunction - Reduce two-address instructions to two operands. 700/// 701bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { 702 DOUT << "Machine Function\n"; 703 const TargetMachine &TM = MF.getTarget(); 704 MRI = &MF.getRegInfo(); 705 TII = TM.getInstrInfo(); 706 TRI = TM.getRegisterInfo(); 707 LV = getAnalysisIfAvailable<LiveVariables>(); 708 709 bool MadeChange = false; 710 711 DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n"; 712 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 713 714 // ReMatRegs - Keep track of the registers whose def's are remat'ed. 715 BitVector ReMatRegs; 716 ReMatRegs.resize(MRI->getLastVirtReg()+1); 717 718 SmallPtrSet<MachineInstr*, 8> Processed; 719 for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); 720 mbbi != mbbe; ++mbbi) { 721 unsigned Dist = 0; 722 DistanceMap.clear(); 723 SrcRegMap.clear(); 724 DstRegMap.clear(); 725 Processed.clear(); 726 for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); 727 mi != me; ) { 728 MachineBasicBlock::iterator nmi = next(mi); 729 const TargetInstrDesc &TID = mi->getDesc(); 730 bool FirstTied = true; 731 732 DistanceMap.insert(std::make_pair(mi, ++Dist)); 733 734 ProcessCopy(&*mi, &*mbbi, Processed); 735 736 unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM) 737 ? mi->getNumOperands() : TID.getNumOperands(); 738 for (unsigned si = 0; si < NumOps; ++si) { 739 unsigned ti = 0; 740 if (!mi->isRegTiedToDefOperand(si, &ti)) 741 continue; 742 743 if (FirstTied) { 744 ++NumTwoAddressInstrs; 745 DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM)); 746 } 747 748 FirstTied = false; 749 750 assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && 751 mi->getOperand(si).isUse() && "two address instruction invalid"); 752 753 // If the two operands are the same we just remove the use 754 // and mark the def as def&use, otherwise we have to insert a copy. 755 if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { 756 // Rewrite: 757 // a = b op c 758 // to: 759 // a = b 760 // a = a op c 761 unsigned regA = mi->getOperand(ti).getReg(); 762 unsigned regB = mi->getOperand(si).getReg(); 763 764 assert(TargetRegisterInfo::isVirtualRegister(regB) && 765 "cannot update physical register live information"); 766 767#ifndef NDEBUG 768 // First, verify that we don't have a use of a in the instruction (a = 769 // b + a for example) because our transformation will not work. This 770 // should never occur because we are in SSA form. 771 for (unsigned i = 0; i != mi->getNumOperands(); ++i) 772 assert(i == ti || 773 !mi->getOperand(i).isReg() || 774 mi->getOperand(i).getReg() != regA); 775#endif 776 777 // If this instruction is not the killing user of B, see if we can 778 // rearrange the code to make it so. Making it the killing user will 779 // allow us to coalesce A and B together, eliminating the copy we are 780 // about to insert. 781 if (!isKilled(*mi, regB, MRI, TII)) { 782 // If regA is dead and the instruction can be deleted, just delete 783 // it so it doesn't clobber regB. 784 if (mi->getOperand(ti).isDead() && isSafeToDelete(mi, TII)) { 785 mbbi->erase(mi); // Nuke the old inst. 786 mi = nmi; 787 ++NumDeletes; 788 break; // Done with this instruction. 789 } 790 791 // If this instruction is commutative, check to see if C dies. If 792 // so, swap the B and C operands. This makes the live ranges of A 793 // and C joinable. 794 // FIXME: This code also works for A := B op C instructions. 795 if (TID.isCommutable() && mi->getNumOperands() >= 3) { 796 assert(mi->getOperand(3-si).isReg() && 797 "Not a proper commutative instruction!"); 798 unsigned regC = mi->getOperand(3-si).getReg(); 799 if (isKilled(*mi, regC, MRI, TII)) { 800 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 801 ++NumCommuted; 802 regB = regC; 803 goto InstructionRearranged; 804 } 805 } 806 } 807 808 // If this instruction is potentially convertible to a true 809 // three-address instruction, 810 if (TID.isConvertibleTo3Addr()) { 811 // FIXME: This assumes there are no more operands which are tied 812 // to another register. 813#ifndef NDEBUG 814 for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) 815 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); 816#endif 817 818 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 819 ++NumConvertedTo3Addr; 820 break; // Done with this instruction. 821 } 822 } 823 } 824 825 // If it's profitable to commute the instruction, do so. 826 if (TID.isCommutable() && mi->getNumOperands() >= 3) { 827 unsigned regC = mi->getOperand(3-si).getReg(); 828 if (isProfitableToCommute(regB, regC, mi, mbbi, Dist)) 829 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { 830 ++NumAggrCommuted; 831 ++NumCommuted; 832 regB = regC; 833 goto InstructionRearranged; 834 } 835 } 836 837 // If it's profitable to convert the 2-address instruction to a 838 // 3-address one, do so. 839 if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) { 840 if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { 841 ++NumConvertedTo3Addr; 842 break; // Done with this instruction. 843 } 844 } 845 846 InstructionRearranged: 847 const TargetRegisterClass* rc = MRI->getRegClass(regB); 848 MachineInstr *DefMI = MRI->getVRegDef(regB); 849 // If it's safe and profitable, remat the definition instead of 850 // copying it. 851 if (DefMI && 852 DefMI->getDesc().isAsCheapAsAMove() && 853 DefMI->isSafeToReMat(TII, regB) && 854 isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ 855 DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n"); 856 TII->reMaterialize(*mbbi, mi, regA, DefMI); 857 ReMatRegs.set(regB); 858 ++NumReMats; 859 } else { 860 bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); 861 assert(Emitted && "Unable to issue a copy instruction!\n"); 862 } 863 864 MachineBasicBlock::iterator prevMI = prior(mi); 865 // Update DistanceMap. 866 DistanceMap.insert(std::make_pair(prevMI, Dist)); 867 DistanceMap[mi] = ++Dist; 868 869 // Update live variables for regB. 870 if (LV) { 871 LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB); 872 873 // regB is used in this BB. 874 varInfoB.UsedBlocks[mbbi->getNumber()] = true; 875 876 if (LV->removeVirtualRegisterKilled(regB, mi)) 877 LV->addVirtualRegisterKilled(regB, prevMI); 878 879 if (LV->removeVirtualRegisterDead(regB, mi)) 880 LV->addVirtualRegisterDead(regB, prevMI); 881 } 882 883 DOUT << "\t\tprepend:\t"; DEBUG(prevMI->print(*cerr.stream(), &TM)); 884 885 // Replace all occurences of regB with regA. 886 for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { 887 if (mi->getOperand(i).isReg() && 888 mi->getOperand(i).getReg() == regB) 889 mi->getOperand(i).setReg(regA); 890 } 891 } 892 893 assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); 894 mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); 895 MadeChange = true; 896 897 DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM)); 898 } 899 900 mi = nmi; 901 } 902 } 903 904 // Some remat'ed instructions are dead. 905 int VReg = ReMatRegs.find_first(); 906 while (VReg != -1) { 907 if (MRI->use_empty(VReg)) { 908 MachineInstr *DefMI = MRI->getVRegDef(VReg); 909 DefMI->eraseFromParent(); 910 } 911 VReg = ReMatRegs.find_next(VReg); 912 } 913 914 return MadeChange; 915} 916