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/Support/RecyclingAllocator.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
  84   // Hash in all of the operands as pointers.
  85   unsigned Res = 0;
  86   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
  87     Res ^= getHash(Inst->getOperand(i)) << i;
  88
  89   if (CastInst *CI = dyn_cast<CastInst>(Inst))
  90     Res ^= getHash(CI->getType());
  91   else if (CmpInst *CI = dyn_cast<CmpInst>(Inst))
  92     Res ^= CI->getPredicate();
  93   else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) {
  94     for (ExtractValueInst::idx_iterator I = EVI->idx_begin(),
  95          E = EVI->idx_end(); I != E; ++I)
  96       Res ^= *I;
  97   } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) {
  98     for (InsertValueInst::idx_iterator I = IVI->idx_begin(),
  99          E = IVI->idx_end(); I != E; ++I)
 100       Res ^= *I;
 101   } else {
 102     // nothing extra to hash in.
 103     assert((isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
 104             isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
 105             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) &&
 106            "Invalid/unknown instruction");
 107   }
 108
 109   // Mix in the opcode.
 110   return (Res << 1) ^ Inst->getOpcode();
 111 }
 112
 113 bool DenseMapInfo<InstValue>::isEqual(InstValue LHS, InstValue RHS) {
 114   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 115
 116   if (LHS.isSentinel() || RHS.isSentinel())
 117     return LHSI == RHSI;
 118
 119   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 120   return LHSI->isIdenticalTo(RHSI);
 121 }
 122
 123
 124 namespace {
 125
 126 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
 127 /// tree, eliminating trivially redundant instructions and using instsimplify
 128 /// to canonicalize things as it goes.  It is intended to be fast and catch
 129 /// obvious cases so that instcombine and other passes are more effective.  It
 130 /// is expected that a later pass of GVN will catch the interesting/hard
 131 /// cases.
 132 class EarlyCSE : public FunctionPass {
 133 public:
 134   const TargetData *TD;
 135   DominatorTree *DT;
 136   typedef RecyclingAllocator<BumpPtrAllocator,
 137                       ScopedHashTableVal<InstValue, Instruction*> > AllocatorTy;
 138   typedef ScopedHashTable<InstValue, Instruction*, DenseMapInfo<InstValue>,
 139                           AllocatorTy> ScopedHTType;
 140   ScopedHTType *AvailableValues;
 141
 142   static char ID;
 143   explicit EarlyCSE()
 144       : FunctionPass(ID) {
 145     initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
 146   }
 147
 148   bool runOnFunction(Function &F);
 149
 150 private:
 151
 152   bool processNode(DomTreeNode *Node);
 153
 154   // This transformation requires dominator postdominator info
 155   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 156     AU.addRequired<DominatorTree>();
 157     AU.setPreservesCFG();
 158   }
 159 };
 160 }
 161
 162 char EarlyCSE::ID = 0;
 163
 164 // createEarlyCSEPass - The public interface to this file.
 165 FunctionPass *llvm::createEarlyCSEPass() {
 166   return new EarlyCSE();
 167 }
 168
 169 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
 170 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 171 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
 172
 173 bool EarlyCSE::processNode(DomTreeNode *Node) {
 174   // Define a scope in the scoped hash table.
 175   ScopedHashTableScope<InstValue, Instruction*, DenseMapInfo<InstValue>,
 176                        AllocatorTy> Scope(*AvailableValues);
 177
 178   BasicBlock *BB = Node->getBlock();
 179
 180   bool Changed = false;
 181
 182   // See if any instructions in the block can be eliminated.  If so, do it.  If
 183   // not, add them to AvailableValues.
 184   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 185     Instruction *Inst = I++;
 186
 187     // Dead instructions should just be removed.
 188     if (isInstructionTriviallyDead(Inst)) {
 189       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 190       Inst->eraseFromParent();
 191       Changed = true;
 192       ++NumSimplify;
 193       continue;
 194     }
 195
 196     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 197     // its simpler value.
 198     if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
 199       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 200       Inst->replaceAllUsesWith(V);
 201       Inst->eraseFromParent();
 202       Changed = true;
 203       ++NumSimplify;
 204       continue;
 205     }
 206
 207     // If this instruction is something that we can't value number, ignore it.
 208     if (!InstValue::canHandle(Inst))
 209       continue;
 210
 211     // See if the instruction has an available value.  If so, use it.
 212     if (Instruction *V = AvailableValues->lookup(InstValue::get(Inst))) {
 213       DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 214       Inst->replaceAllUsesWith(V);
 215       Inst->eraseFromParent();
 216       Changed = true;
 217       ++NumCSE;
 218       continue;
 219     }
 220
 221     // Otherwise, just remember that this value is available.
 222     AvailableValues->insert(InstValue::get(Inst), Inst);
 223   }
 224
 225
 226   for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
 227     Changed |= processNode(*I);
 228   return Changed;
 229 }
 230
 231
 232 bool EarlyCSE::runOnFunction(Function &F) {
 233   TD = getAnalysisIfAvailable<TargetData>();
 234   DT = &getAnalysis<DominatorTree>();
 235   ScopedHTType AVTable;
 236   AvailableValues = &AVTable;
 237   return processNode(DT->getRootNode());
 238 }
 239