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 llvm {
  32   template<> struct DenseMapInfo<MachineInstr*> {
  33     static inline MachineInstr *getEmptyKey() {
  34       return 0;
  35     }
  36
  37     static inline MachineInstr *getTombstoneKey() {
  38       return reinterpret_cast<MachineInstr*>(-1);
  39     }
  40
  41     static unsigned getHashValue(const MachineInstr* const &MI) {
  42       unsigned Hash = MI->getOpcode() * 37;
  43       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  44         const MachineOperand &MO = MI->getOperand(i);
  45         uint64_t Key = (uint64_t)MO.getType() << 32;
  46         switch (MO.getType()) {
  47         default: break;
  48         case MachineOperand::MO_Register:
  49           if (MO.isDef() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
  50             continue;  // Skip virtual register defs.
  51           Key |= MO.getReg();
  52           break;
  53         case MachineOperand::MO_Immediate:
  54           Key |= MO.getImm();
  55           break;
  56         case MachineOperand::MO_FrameIndex:
  57         case MachineOperand::MO_ConstantPoolIndex:
  58         case MachineOperand::MO_JumpTableIndex:
  59           Key |= MO.getIndex();
  60           break;
  61         case MachineOperand::MO_MachineBasicBlock:
  62           Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
  63           break;
  64         case MachineOperand::MO_GlobalAddress:
  65           Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
  66           break;
  67         case MachineOperand::MO_BlockAddress:
  68           Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
  69           break;
  70         }
  71         Key += ~(Key << 32);
  72         Key ^= (Key >> 22);
  73         Key += ~(Key << 13);
  74         Key ^= (Key >> 8);
  75         Key += (Key << 3);
  76         Key ^= (Key >> 15);
  77         Key += ~(Key << 27);
  78         Key ^= (Key >> 31);
  79         Hash = (unsigned)Key + Hash * 37;
  80       }
  81       return Hash;
  82     }
  83
  84     static bool isEqual(const MachineInstr* const &LHS,
  85                         const MachineInstr* const &RHS) {
  86       if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
  87           LHS == getEmptyKey() || LHS == getTombstoneKey())
  88         return LHS == RHS;
  89       return LHS->isIdenticalTo(RHS, MachineInstr::IgnoreVRegDefs);
  90     }
  91   };
  92 } // end llvm namespace
  93
  94 namespace {
  95   class MachineCSE : public MachineFunctionPass {
  96     const TargetInstrInfo *TII;
  97     MachineRegisterInfo  *MRI;
  98     MachineDominatorTree *DT;
  99   public:
 100     static char ID; // Pass identification
 101     MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
 102
 103     virtual bool runOnMachineFunction(MachineFunction &MF);
 104
 105     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106       AU.setPreservesCFG();
 107       MachineFunctionPass::getAnalysisUsage(AU);
 108       AU.addRequired<MachineDominatorTree>();
 109       AU.addPreserved<MachineDominatorTree>();
 110     }
 111
 112   private:
 113     unsigned CurrVN;
 114     ScopedHashTable<MachineInstr*, unsigned> VNT;
 115     SmallVector<MachineInstr*, 64> Exps;
 116
 117     bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
 118     bool ProcessBlock(MachineDomTreeNode *Node);
 119   };
 120 } // end anonymous namespace
 121
 122 char MachineCSE::ID = 0;
 123 static RegisterPass<MachineCSE>
 124 X("machine-cse", "Machine Common Subexpression Elimination");
 125
 126 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
 127
 128 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
 129                                           MachineBasicBlock *MBB) {
 130   bool Changed = false;
 131   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 132     MachineOperand &MO = MI->getOperand(i);
 133     if (!MO.isReg() || !MO.isUse())
 134       continue;
 135     unsigned Reg = MO.getReg();
 136     if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
 137       continue;
 138     if (!MRI->hasOneUse(Reg))
 139       // Only coalesce single use copies. This ensure the copy will be
 140       // deleted.
 141       continue;
 142     MachineInstr *DefMI = MRI->getVRegDef(Reg);
 143     if (DefMI->getParent() != MBB)
 144       continue;
 145     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 146     if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
 147         TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 148         !SrcSubIdx && !DstSubIdx) {
 149       MO.setReg(SrcReg);
 150       DefMI->eraseFromParent();
 151       ++NumCoalesces;
 152       Changed = true;
 153     }
 154   }
 155
 156   return Changed;
 157 }
 158
 159 static bool hasLivePhysRegDefUse(MachineInstr *MI) {
 160   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 161     MachineOperand &MO = MI->getOperand(i);
 162     if (!MO.isReg())
 163       continue;
 164     unsigned Reg = MO.getReg();
 165     if (!Reg)
 166       continue;
 167     // FIXME: This is obviously overly conservative. On x86 lots of instructions
 168     // will def EFLAGS and they are not marked dead at this point.
 169     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
 170         !(MO.isDef() && MO.isDead()))
 171       return true;
 172   }
 173   return false;
 174 }
 175
 176 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
 177   bool Changed = false;
 178
 179   ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT);
 180   MachineBasicBlock *MBB = Node->getBlock();
 181   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
 182     MachineInstr *MI = &*I;
 183     ++I;
 184     bool SawStore = false;
 185     if (!MI->isSafeToMove(TII, 0, SawStore))
 186       continue;
 187     // Ignore copies or instructions that read / write physical registers
 188     // (except for dead defs of physical registers).
 189     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 190     if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
 191         MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
 192       continue;
 193     if (hasLivePhysRegDefUse(MI))
 194       continue;
 195
 196     bool FoundCSE = VNT.count(MI);
 197     if (!FoundCSE) {
 198       // Look for trivial copy coalescing opportunities.
 199       if (PerformTrivialCoalescing(MI, MBB))
 200         FoundCSE = VNT.count(MI);
 201     }
 202
 203     if (!FoundCSE) {
 204       VNT.insert(MI, CurrVN++);
 205       Exps.push_back(MI);
 206       continue;
 207     }
 208
 209     // Found a common subexpression, eliminate it.
 210     unsigned CSVN = VNT.lookup(MI);
 211     MachineInstr *CSMI = Exps[CSVN];
 212     DEBUG(dbgs() << "Examining: " << *MI);
 213     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
 214     unsigned NumDefs = MI->getDesc().getNumDefs();
 215     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
 216       MachineOperand &MO = MI->getOperand(i);
 217       if (!MO.isReg() || !MO.isDef())
 218         continue;
 219       unsigned OldReg = MO.getReg();
 220       unsigned NewReg = CSMI->getOperand(i).getReg();
 221       assert(OldReg != NewReg &&
 222              TargetRegisterInfo::isVirtualRegister(OldReg) &&
 223              TargetRegisterInfo::isVirtualRegister(NewReg) &&
 224              "Do not CSE physical register defs!");
 225       MRI->replaceRegWith(OldReg, NewReg);
 226       --NumDefs;
 227     }
 228     MI->eraseFromParent();
 229     ++NumCSEs;
 230   }
 231
 232   // Recursively call ProcessBlock with childred.
 233   const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
 234   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 235     Changed |= ProcessBlock(Children[i]);
 236
 237   return Changed;
 238 }
 239
 240 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
 241   TII = MF.getTarget().getInstrInfo();
 242   MRI = &MF.getRegInfo();
 243   DT = &getAnalysis<MachineDominatorTree>();
 244   return ProcessBlock(DT->getRootNode());
 245 }