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