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