lib/CodeGen/MachineCSE.cpp

   1 //===-- MachineCSE.cpp - Machine Common Subexpression Elimination 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 pass performs global common subexpression elimination on machine
  11 // instructions using a scoped hash table based value numbering scheme. It
  12 // must be run while the machine function is still in SSA form.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "machine-cse"
  17 #include "llvm/CodeGen/Passes.h"
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Target/TargetInstrInfo.h"
  22 #include "llvm/ADT/ScopedHashTable.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Support/Debug.h"
  25
  26 using namespace llvm;
  27
  28 STATISTIC(NumCoalesces, "Number of copies coalesced");
  29 STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
  30
  31 namespace {
  32   class MachineCSE : public MachineFunctionPass {
  33     const TargetInstrInfo *TII;
  34     MachineRegisterInfo  *MRI;
  35     MachineDominatorTree *DT;
  36   public:
  37     static char ID; // Pass identification
  38     MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
  39
  40     virtual bool runOnMachineFunction(MachineFunction &MF);
  41
  42     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  43       AU.setPreservesCFG();
  44       MachineFunctionPass::getAnalysisUsage(AU);
  45       AU.addRequired<MachineDominatorTree>();
  46       AU.addPreserved<MachineDominatorTree>();
  47     }
  48
  49   private:
  50     unsigned CurrVN;
  51     ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT;
  52     SmallVector<MachineInstr*, 64> Exps;
  53
  54     bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
  55     bool ProcessBlock(MachineDomTreeNode *Node);
  56   };
  57 } // end anonymous namespace
  58
  59 char MachineCSE::ID = 0;
  60 static RegisterPass<MachineCSE>
  61 X("machine-cse", "Machine Common Subexpression Elimination");
  62
  63 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
  64
  65 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
  66                                           MachineBasicBlock *MBB) {
  67   bool Changed = false;
  68   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  69     MachineOperand &MO = MI->getOperand(i);
  70     if (!MO.isReg() || !MO.isUse())
  71       continue;
  72     unsigned Reg = MO.getReg();
  73     if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
  74       continue;
  75     if (!MRI->hasOneUse(Reg))
  76       // Only coalesce single use copies. This ensure the copy will be
  77       // deleted.
  78       continue;
  79     MachineInstr *DefMI = MRI->getVRegDef(Reg);
  80     if (DefMI->getParent() != MBB)
  81       continue;
  82     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
  83     if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
  84         TargetRegisterInfo::isVirtualRegister(SrcReg) &&
  85         !SrcSubIdx && !DstSubIdx) {
  86       MO.setReg(SrcReg);
  87       DefMI->eraseFromParent();
  88       ++NumCoalesces;
  89       Changed = true;
  90     }
  91   }
  92
  93   return Changed;
  94 }
  95
  96 static bool hasLivePhysRegDefUse(MachineInstr *MI) {
  97   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  98     MachineOperand &MO = MI->getOperand(i);
  99     if (!MO.isReg())
 100       continue;
 101     unsigned Reg = MO.getReg();
 102     if (!Reg)
 103       continue;
 104     // FIXME: This is obviously overly conservative. On x86 lots of instructions
 105     // will def EFLAGS and they are not marked dead at this point.
 106     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
 107         !(MO.isDef() && MO.isDead()))
 108       return true;
 109   }
 110   return false;
 111 }
 112
 113 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
 114   bool Changed = false;
 115
 116   ScopedHashTableScope<MachineInstr*, unsigned,
 117     MachineInstrExpressionTrait> VNTS(VNT);
 118   MachineBasicBlock *MBB = Node->getBlock();
 119   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
 120     MachineInstr *MI = &*I;
 121     ++I;
 122     bool SawStore = false;
 123     if (!MI->isSafeToMove(TII, 0, SawStore))
 124       continue;
 125     // Ignore copies or instructions that read / write physical registers
 126     // (except for dead defs of physical registers).
 127     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 128     if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
 129         MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
 130       continue;
 131
 132     bool FoundCSE = VNT.count(MI);
 133     if (!FoundCSE) {
 134       // Look for trivial copy coalescing opportunities.
 135       if (PerformTrivialCoalescing(MI, MBB))
 136         FoundCSE = VNT.count(MI);
 137     }
 138
 139     // If the instruction defines a physical register and the value *may* be
 140     // used, then it's not safe to replace it with a common subexpression.
 141     if (FoundCSE && hasLivePhysRegDefUse(MI))
 142       FoundCSE = false;
 143
 144     if (!FoundCSE) {
 145       VNT.insert(MI, CurrVN++);
 146       Exps.push_back(MI);
 147       continue;
 148     }
 149
 150     // Found a common subexpression, eliminate it.
 151     unsigned CSVN = VNT.lookup(MI);
 152     MachineInstr *CSMI = Exps[CSVN];
 153     DEBUG(dbgs() << "Examining: " << *MI);
 154     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
 155     unsigned NumDefs = MI->getDesc().getNumDefs();
 156     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
 157       MachineOperand &MO = MI->getOperand(i);
 158       if (!MO.isReg() || !MO.isDef())
 159         continue;
 160       unsigned OldReg = MO.getReg();
 161       unsigned NewReg = CSMI->getOperand(i).getReg();
 162       assert(OldReg != NewReg &&
 163              TargetRegisterInfo::isVirtualRegister(OldReg) &&
 164              TargetRegisterInfo::isVirtualRegister(NewReg) &&
 165              "Do not CSE physical register defs!");
 166       MRI->replaceRegWith(OldReg, NewReg);
 167       --NumDefs;
 168     }
 169     MI->eraseFromParent();
 170     ++NumCSEs;
 171   }
 172
 173   // Recursively call ProcessBlock with childred.
 174   const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
 175   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 176     Changed |= ProcessBlock(Children[i]);
 177
 178   return Changed;
 179 }
 180
 181 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
 182   TII = MF.getTarget().getInstrInfo();
 183   MRI = &MF.getRegInfo();
 184   DT = &getAnalysis<MachineDominatorTree>();
 185   return ProcessBlock(DT->getRootNode());
 186 }