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/Support/CommandLine.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/SmallPtrSet.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(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  53 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  54 STATISTIC(NumReMats,           "Number of instructions re-materialized");
  55
  56 static cl::opt<bool>
  57 EnableReMat("two-addr-remat", cl::init(false), cl::Hidden,
  58             cl::desc("Two-addr conversion should remat when possible."));
  59
  60 namespace {
  61   class VISIBILITY_HIDDEN TwoAddressInstructionPass
  62     : public MachineFunctionPass {
  63     const TargetInstrInfo *TII;
  64     const TargetRegisterInfo *TRI;
  65     MachineRegisterInfo *MRI;
  66     LiveVariables *LV;
  67
  68     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  69                               unsigned Reg,
  70                               MachineBasicBlock::iterator OldPos);
  71
  72     bool isSafeToReMat(unsigned DstReg, MachineInstr *MI);
  73     bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
  74                              MachineInstr *MI, unsigned Loc,
  75                              MachineInstr *DefMI, MachineBasicBlock *MBB,
  76                              DenseMap<MachineInstr*, unsigned> &DistanceMap);
  77   public:
  78     static char ID; // Pass identification, replacement for typeid
  79     TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
  80
  81     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  82       AU.addRequired<LiveVariables>();
  83       AU.addPreserved<LiveVariables>();
  84       AU.addPreservedID(MachineLoopInfoID);
  85       AU.addPreservedID(MachineDominatorsID);
  86       AU.addPreservedID(PHIEliminationID);
  87       MachineFunctionPass::getAnalysisUsage(AU);
  88     }
  89
  90     /// runOnMachineFunction - Pass entry point.
  91     bool runOnMachineFunction(MachineFunction&);
  92   };
  93 }
  94
  95 char TwoAddressInstructionPass::ID = 0;
  96 static RegisterPass<TwoAddressInstructionPass>
  97 X("twoaddressinstruction", "Two-Address instruction pass");
  98
  99 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
 100
 101 /// Sink3AddrInstruction - A two-address instruction has been converted to a
 102 /// three-address instruction to avoid clobbering a register. Try to sink it
 103 /// past the instruction that would kill the above mentioned register to reduce
 104 /// register pressure.
 105 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
 106                                            MachineInstr *MI, unsigned SavedReg,
 107                                            MachineBasicBlock::iterator OldPos) {
 108   // Check if it's safe to move this instruction.
 109   bool SeenStore = true; // Be conservative.
 110   if (!MI->isSafeToMove(TII, SeenStore))
 111     return false;
 112
 113   unsigned DefReg = 0;
 114   SmallSet<unsigned, 4> UseRegs;
 115
 116   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 117     const MachineOperand &MO = MI->getOperand(i);
 118     if (!MO.isRegister())
 119       continue;
 120     unsigned MOReg = MO.getReg();
 121     if (!MOReg)
 122       continue;
 123     if (MO.isUse() && MOReg != SavedReg)
 124       UseRegs.insert(MO.getReg());
 125     if (!MO.isDef())
 126       continue;
 127     if (MO.isImplicit())
 128       // Don't try to move it if it implicitly defines a register.
 129       return false;
 130     if (DefReg)
 131       // For now, don't move any instructions that define multiple registers.
 132       return false;
 133     DefReg = MO.getReg();
 134   }
 135
 136   // Find the instruction that kills SavedReg.
 137   MachineInstr *KillMI = NULL;
 138   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 139          UE = MRI->use_end(); UI != UE; ++UI) {
 140     MachineOperand &UseMO = UI.getOperand();
 141     if (!UseMO.isKill())
 142       continue;
 143     KillMI = UseMO.getParent();
 144     break;
 145   }
 146
 147   if (!KillMI || KillMI->getParent() != MBB)
 148     return false;
 149
 150   // If any of the definitions are used by another instruction between the
 151   // position and the kill use, then it's not safe to sink it.
 152   //
 153   // FIXME: This can be sped up if there is an easy way to query whether an
 154   // instruction is before or after another instruction. Then we can use
 155   // MachineRegisterInfo def / use instead.
 156   MachineOperand *KillMO = NULL;
 157   MachineBasicBlock::iterator KillPos = KillMI;
 158   ++KillPos;
 159
 160   unsigned NumVisited = 0;
 161   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 162     MachineInstr *OtherMI = I;
 163     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 164       return false;
 165     ++NumVisited;
 166     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 167       MachineOperand &MO = OtherMI->getOperand(i);
 168       if (!MO.isRegister())
 169         continue;
 170       unsigned MOReg = MO.getReg();
 171       if (!MOReg)
 172         continue;
 173       if (DefReg == MOReg)
 174         return false;
 175
 176       if (MO.isKill()) {
 177         if (OtherMI == KillMI && MOReg == SavedReg)
 178           // Save the operand that kills the register. We want to unset the kill
 179           // marker if we can sink MI past it.
 180           KillMO = &MO;
 181         else if (UseRegs.count(MOReg))
 182           // One of the uses is killed before the destination.
 183           return false;
 184       }
 185     }
 186   }
 187
 188   // Update kill and LV information.
 189   KillMO->setIsKill(false);
 190   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 191   KillMO->setIsKill(true);
 192   LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
 193   VarInfo.removeKill(KillMI);
 194   VarInfo.Kills.push_back(MI);
 195
 196   // Move instruction to its destination.
 197   MBB->remove(MI);
 198   MBB->insert(KillPos, MI);
 199
 200   ++Num3AddrSunk;
 201   return true;
 202 }
 203
 204 /// isSafeToReMat - Return true if it's safe to rematerialize the specified
 205 /// instruction which defined the specified register instead of copying it.
 206 bool
 207 TwoAddressInstructionPass::isSafeToReMat(unsigned DstReg, MachineInstr *MI) {
 208   const TargetInstrDesc &TID = MI->getDesc();
 209   if (!TID.isAsCheapAsAMove())
 210     return false;
 211   bool SawStore = false;
 212   if (!MI->isSafeToMove(TII, SawStore))
 213     return false;
 214   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 215     MachineOperand &MO = MI->getOperand(i);
 216     if (!MO.isRegister())
 217       continue;
 218     // FIXME: For now, do not remat any instruction with register operands.
 219     // Later on, we can loosen the restriction is the register operands have
 220     // not been modified between the def and use. Note, this is different from
 221     // MachineSink because the code in no longer in two-address form (at least
 222     // partially).
 223     if (MO.isUse())
 224       return false;
 225     else if (!MO.isDead() && MO.getReg() != DstReg)
 226       return false;
 227   }
 228   return true;
 229 }
 230
 231 /// isTwoAddrUse - Return true if the specified MI is using the specified
 232 /// register as a two-address operand.
 233 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
 234   const TargetInstrDesc &TID = UseMI->getDesc();
 235   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 236     MachineOperand &MO = UseMI->getOperand(i);
 237     if (MO.getReg() == Reg &&
 238         (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
 239       // Earlier use is a two-address one.
 240       return true;
 241   }
 242   return false;
 243 }
 244
 245 /// isProfitableToReMat - Return true if the heuristics determines it is likely
 246 /// to be profitable to re-materialize the definition of Reg rather than copy
 247 /// the register.
 248 bool
 249 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
 250                                 const TargetRegisterClass *RC,
 251                                 MachineInstr *MI, unsigned Loc,
 252                                 MachineInstr *DefMI, MachineBasicBlock *MBB,
 253                                 DenseMap<MachineInstr*, unsigned> &DistanceMap) {
 254   if (DefMI->getParent() != MBB)
 255     return true;
 256   // If earlier uses in MBB are not two-address uses, then don't remat.
 257   bool OtherUse = false;
 258   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 259          UE = MRI->use_end(); UI != UE; ++UI) {
 260     MachineOperand &UseMO = UI.getOperand();
 261     if (!UseMO.isUse())
 262       continue;
 263     MachineInstr *UseMI = UseMO.getParent();
 264     if (UseMI->getParent() != MBB)
 265       continue;
 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   return !OtherUse;
 276 }
 277
 278 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 279 ///
 280 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 281   DOUT << "Machine Function\n";
 282   const TargetMachine &TM = MF.getTarget();
 283   MRI = &MF.getRegInfo();
 284   TII = TM.getInstrInfo();
 285   TRI = TM.getRegisterInfo();
 286   LV = &getAnalysis<LiveVariables>();
 287
 288   bool MadeChange = false;
 289
 290   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 291   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 292
 293   // ReMatRegs - Keep track of the registers whose def's are remat'ed.
 294   BitVector ReMatRegs;
 295   ReMatRegs.resize(MRI->getLastVirtReg()+1);
 296
 297   // DistanceMap - Keep track the distance of a MI from the start of the
 298   // current basic block.
 299   DenseMap<MachineInstr*, unsigned> DistanceMap;
 300
 301   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 302        mbbi != mbbe; ++mbbi) {
 303     unsigned Dist = 0;
 304     DistanceMap.clear();
 305     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 306          mi != me; ) {
 307       MachineBasicBlock::iterator nmi = next(mi);
 308       const TargetInstrDesc &TID = mi->getDesc();
 309       bool FirstTied = true;
 310
 311       DistanceMap.insert(std::make_pair(mi, ++Dist));
 312       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 313         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 314         if (ti == -1)
 315           continue;
 316
 317         if (FirstTied) {
 318           ++NumTwoAddressInstrs;
 319           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 320         }
 321
 322         FirstTied = false;
 323
 324         assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
 325                mi->getOperand(si).isUse() && "two address instruction invalid");
 326
 327         // If the two operands are the same we just remove the use
 328         // and mark the def as def&use, otherwise we have to insert a copy.
 329         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 330           // Rewrite:
 331           //     a = b op c
 332           // to:
 333           //     a = b
 334           //     a = a op c
 335           unsigned regA = mi->getOperand(ti).getReg();
 336           unsigned regB = mi->getOperand(si).getReg();
 337
 338           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 339                  TargetRegisterInfo::isVirtualRegister(regB) &&
 340                  "cannot update physical register live information");
 341
 342 #ifndef NDEBUG
 343           // First, verify that we don't have a use of a in the instruction (a =
 344           // b + a for example) because our transformation will not work. This
 345           // should never occur because we are in SSA form.
 346           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 347             assert((int)i == ti ||
 348                    !mi->getOperand(i).isRegister() ||
 349                    mi->getOperand(i).getReg() != regA);
 350 #endif
 351
 352           // If this instruction is not the killing user of B, see if we can
 353           // rearrange the code to make it so.  Making it the killing user will
 354           // allow us to coalesce A and B together, eliminating the copy we are
 355           // about to insert.
 356           if (!mi->killsRegister(regB)) {
 357             // If this instruction is commutative, check to see if C dies.  If
 358             // so, swap the B and C operands.  This makes the live ranges of A
 359             // and C joinable.
 360             // FIXME: This code also works for A := B op C instructions.
 361             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 362               assert(mi->getOperand(3-si).isRegister() &&
 363                      "Not a proper commutative instruction!");
 364               unsigned regC = mi->getOperand(3-si).getReg();
 365
 366               if (mi->killsRegister(regC)) {
 367                 DOUT << "2addr: COMMUTING  : " << *mi;
 368                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 369
 370                 if (NewMI == 0) {
 371                   DOUT << "2addr: COMMUTING FAILED!\n";
 372                 } else {
 373                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 374                   // If the instruction changed to commute it, update livevar.
 375                   if (NewMI != mi) {
 376                     LV->instructionChanged(mi, NewMI); // Update live variables
 377                     mbbi->insert(mi, NewMI);           // Insert the new inst
 378                     mbbi->erase(mi);                   // Nuke the old inst.
 379                     mi = NewMI;
 380                     DistanceMap.insert(std::make_pair(NewMI, Dist));
 381                   }
 382
 383                   ++NumCommuted;
 384                   regB = regC;
 385                   goto InstructionRearranged;
 386                 }
 387               }
 388             }
 389
 390             // If this instruction is potentially convertible to a true
 391             // three-address instruction,
 392             if (TID.isConvertibleTo3Addr()) {
 393               // FIXME: This assumes there are no more operands which are tied
 394               // to another register.
 395 #ifndef NDEBUG
 396               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 397                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 398 #endif
 399
 400               MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, *LV);
 401               if (NewMI) {
 402                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 403                 DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
 404                 bool Sunk = false;
 405
 406                 if (NewMI->findRegisterUseOperand(regB, false, TRI))
 407                   // FIXME: Temporary workaround. If the new instruction doesn't
 408                   // uses regB, convertToThreeAddress must have created more
 409                   // then one instruction.
 410                   Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
 411
 412                 mbbi->erase(mi); // Nuke the old inst.
 413
 414                 if (!Sunk) {
 415                   DistanceMap.insert(std::make_pair(NewMI, Dist));
 416                   mi = NewMI;
 417                   nmi = next(mi);
 418                 }
 419
 420                 ++NumConvertedTo3Addr;
 421                 break; // Done with this instruction.
 422               }
 423             }
 424           }
 425
 426         InstructionRearranged:
 427           const TargetRegisterClass* rc = MRI->getRegClass(regA);
 428           MachineInstr *DefMI = MRI->getVRegDef(regB);
 429           // If it's safe and profitable, remat the definition instead of
 430           // copying it.
 431           if (EnableReMat && DefMI &&
 432               isSafeToReMat(regB, DefMI) &&
 433               isProfitableToReMat(regB, rc, mi, Dist, DefMI, mbbi,DistanceMap)){
 434             DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
 435             TII->reMaterialize(*mbbi, mi, regA, DefMI);
 436             ReMatRegs.set(regB);
 437             ++NumReMats;
 438           } else {
 439             TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 440           }
 441
 442           MachineBasicBlock::iterator prevMi = prior(mi);
 443           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 444
 445           // Update live variables for regB.
 446           LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 447
 448           // regB is used in this BB.
 449           varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 450
 451           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 452             LV->addVirtualRegisterKilled(regB, prevMi);
 453
 454           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 455             LV->addVirtualRegisterDead(regB, prevMi);
 456
 457           // Replace all occurences of regB with regA.
 458           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 459             if (mi->getOperand(i).isRegister() &&
 460                 mi->getOperand(i).getReg() == regB)
 461               mi->getOperand(i).setReg(regA);
 462           }
 463         }
 464
 465         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 466         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 467         MadeChange = true;
 468
 469         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 470       }
 471
 472       mi = nmi;
 473     }
 474   }
 475
 476   if (EnableReMat) {
 477     // Some remat'ed instructions are dead.
 478     int VReg = ReMatRegs.find_first();
 479     while (VReg != -1) {
 480       if (MRI->use_empty(VReg)) {
 481         MachineInstr *DefMI = MRI->getVRegDef(VReg);
 482         DefMI->eraseFromParent();
 483       }
 484       VReg = ReMatRegs.find_next(VReg);
 485     }
 486
 487   }
 488
 489   return MadeChange;
 490 }