lib/Transforms/Scalar/EarlyCSE.cpp

   1 //===- EarlyCSE.cpp - Simple and fast CSE 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 a simple dominator tree walk that eliminates trivially
  11 // redundant instructions.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "early-cse"
  16 #include "llvm/Transforms/Scalar.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/Analysis/Dominators.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/Analysis/InstructionSimplify.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Transforms/Utils/Local.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/ADT/ScopedHashTable.h"
  26 #include "llvm/ADT/Statistic.h"
  27 using namespace llvm;
  28
  29 STATISTIC(NumSimplify, "Number of insts simplified or DCE'd");
  30 STATISTIC(NumCSE, "Number of insts CSE'd");
  31
  32 namespace {
  33   /// InstValue - Instances of this struct represent available values in the
  34   /// scoped hash table.
  35   struct InstValue {
  36     Instruction *Inst;
  37
  38     bool isSentinel() const {
  39       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
  40              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
  41     }
  42
  43     static bool canHandle(Instruction *Inst) {
  44       return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
  45              isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
  46              isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  47              isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  48              isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
  49     }
  50
  51     static InstValue get(Instruction *I) {
  52       InstValue X; X.Inst = I;
  53       assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!");
  54       return X;
  55     }
  56   };
  57 }
  58
  59 namespace llvm {
  60 // InstValue is POD.
  61 template<> struct isPodLike<InstValue> {
  62   static const bool value = true;
  63 };
  64
  65 template<> struct DenseMapInfo<InstValue> {
  66   static inline InstValue getEmptyKey() {
  67     return InstValue::get(DenseMapInfo<Instruction*>::getEmptyKey());
  68   }
  69   static inline InstValue getTombstoneKey() {
  70     return InstValue::get(DenseMapInfo<Instruction*>::getTombstoneKey());
  71   }
  72   static unsigned getHashValue(InstValue Val);
  73   static bool isEqual(InstValue LHS, InstValue RHS);
  74 };
  75 }
  76
  77 unsigned getHash(const void *V) {
  78   return DenseMapInfo<const void*>::getHashValue(V);
  79 }
  80
  81 unsigned DenseMapInfo<InstValue>::getHashValue(InstValue Val) {
  82   Instruction *Inst = Val.Inst;
  83   unsigned Res = 0;
  84   if (CastInst *CI = dyn_cast<CastInst>(Inst))
  85     Res = getHash(CI->getOperand(0)) ^ getHash(CI->getType());
  86   else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Inst))
  87     Res = getHash(BO->getOperand(0)) ^ (getHash(BO->getOperand(1)) << 1);
  88   else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
  89     Res = getHash(GEP->getOperand(0));
  90     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
  91       Res ^= getHash(GEP->getOperand(i)) << i;
  92   } else if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
  93       Res = getHash(CI->getOperand(0)) ^ (getHash(CI->getOperand(1)) << 1) ^
  94          CI->getPredicate();
  95   } else {
  96     assert((isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  97             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  98             isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst)) &&
  99            "Unhandled instruction kind");
 100     Res = getHash(Inst->getType()) << 4;
 101     for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
 102       Res ^= getHash(Inst->getOperand(i)) << i;
 103   }
 104
 105   return (Res << 1) ^ Inst->getOpcode();
 106 }
 107
 108 bool DenseMapInfo<InstValue>::isEqual(InstValue LHS, InstValue RHS) {
 109   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 110
 111   if (LHS.isSentinel() || RHS.isSentinel())
 112     return LHSI == RHSI;
 113
 114   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 115   return LHSI->isIdenticalTo(RHSI);
 116 }
 117
 118
 119 namespace {
 120
 121 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
 122 /// tree, eliminating trivially redundant instructions and using instsimplify
 123 /// to canonicalize things as it goes.  It is intended to be fast and catch
 124 /// obvious cases so that instcombine and other passes are more effective.  It
 125 /// is expected that a later pass of GVN will catch the interesting/hard
 126 /// cases.
 127 class EarlyCSE : public FunctionPass {
 128 public:
 129   const TargetData *TD;
 130   DominatorTree *DT;
 131   ScopedHashTable<InstValue, Instruction*> *AvailableValues;
 132
 133   static char ID;
 134   explicit EarlyCSE()
 135       : FunctionPass(ID) {
 136     initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
 137   }
 138
 139   bool runOnFunction(Function &F);
 140
 141 private:
 142
 143   bool processNode(DomTreeNode *Node);
 144
 145   // This transformation requires dominator postdominator info
 146   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 147     AU.addRequired<DominatorTree>();
 148     AU.setPreservesCFG();
 149   }
 150 };
 151 }
 152
 153 char EarlyCSE::ID = 0;
 154
 155 // createEarlyCSEPass - The public interface to this file.
 156 FunctionPass *llvm::createEarlyCSEPass() {
 157   return new EarlyCSE();
 158 }
 159
 160 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
 161 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 162 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
 163
 164 // FIXME: Should bump pointer allocate entries in scoped hash table.
 165
 166 bool EarlyCSE::processNode(DomTreeNode *Node) {
 167   // Define a scope in the scoped hash table.
 168   ScopedHashTableScope<InstValue, Instruction*> Scope(*AvailableValues);
 169
 170   BasicBlock *BB = Node->getBlock();
 171
 172   bool Changed = false;
 173
 174   // See if any instructions in the block can be eliminated.  If so, do it.  If
 175   // not, add them to AvailableValues.
 176   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 177     Instruction *Inst = I++;
 178
 179     // Dead instructions should just be removed.
 180     if (isInstructionTriviallyDead(Inst)) {
 181       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 182       Inst->eraseFromParent();
 183       Changed = true;
 184       ++NumSimplify;
 185       continue;
 186     }
 187
 188     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 189     // its simpler value.
 190     if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
 191       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 192       Inst->replaceAllUsesWith(V);
 193       Inst->eraseFromParent();
 194       Changed = true;
 195       ++NumSimplify;
 196       continue;
 197     }
 198
 199     // If this instruction is something that we can't value number, ignore it.
 200     if (!InstValue::canHandle(Inst))
 201       continue;
 202
 203     // See if the instruction has an available value.  If so, use it.
 204     if (Instruction *V = AvailableValues->lookup(InstValue::get(Inst))) {
 205       DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 206       Inst->replaceAllUsesWith(V);
 207       Inst->eraseFromParent();
 208       Changed = true;
 209       ++NumCSE;
 210       continue;
 211     }
 212
 213     // Otherwise, just remember that this value is available.
 214     AvailableValues->insert(InstValue::get(Inst), Inst);
 215   }
 216
 217
 218   for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
 219     Changed |= processNode(*I);
 220   return Changed;
 221 }
 222
 223
 224 bool EarlyCSE::runOnFunction(Function &F) {
 225   TD = getAnalysisIfAvailable<TargetData>();
 226   DT = &getAnalysis<DominatorTree>();
 227   ScopedHashTable<InstValue, Instruction*> AVTable;
 228   AvailableValues = &AVTable;
 229   return processNode(DT->getRootNode());
 230 }
 231