lib/CodeGen/TwoAddressInstructionPass.cpp

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