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 STATISTIC(NumCSEMem,   "Number of load and call insts CSE'd");
  32
  33 static unsigned getHash(const void *V) {
  34   return DenseMapInfo<const void*>::getHashValue(V);
  35 }
  36
  37 //===----------------------------------------------------------------------===//
  38 // SimpleValue
  39 //===----------------------------------------------------------------------===//
  40
  41 namespace {
  42   /// SimpleValue - Instances of this struct represent available values in the
  43   /// scoped hash table.
  44   struct SimpleValue {
  45     Instruction *Inst;
  46
  47     bool isSentinel() const {
  48       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
  49              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
  50     }
  51
  52     static bool canHandle(Instruction *Inst) {
  53       return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
  54              isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
  55              isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  56              isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  57              isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
  58     }
  59
  60     static SimpleValue get(Instruction *I) {
  61       SimpleValue X; X.Inst = I;
  62       assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!");
  63       return X;
  64     }
  65   };
  66 }
  67
  68 namespace llvm {
  69 // SimpleValue is POD.
  70 template<> struct isPodLike<SimpleValue> {
  71   static const bool value = true;
  72 };
  73
  74 template<> struct DenseMapInfo<SimpleValue> {
  75   static inline SimpleValue getEmptyKey() {
  76     return SimpleValue::get(DenseMapInfo<Instruction*>::getEmptyKey());
  77   }
  78   static inline SimpleValue getTombstoneKey() {
  79     return SimpleValue::get(DenseMapInfo<Instruction*>::getTombstoneKey());
  80   }
  81   static unsigned getHashValue(SimpleValue Val);
  82   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
  83 };
  84 }
  85
  86 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
  87   Instruction *Inst = Val.Inst;
  88
  89   // Hash in all of the operands as pointers.
  90   unsigned Res = 0;
  91   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
  92     Res ^= getHash(Inst->getOperand(i)) << i;
  93
  94   if (CastInst *CI = dyn_cast<CastInst>(Inst))
  95     Res ^= getHash(CI->getType());
  96   else if (CmpInst *CI = dyn_cast<CmpInst>(Inst))
  97     Res ^= CI->getPredicate();
  98   else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) {
  99     for (ExtractValueInst::idx_iterator I = EVI->idx_begin(),
 100          E = EVI->idx_end(); I != E; ++I)
 101       Res ^= *I;
 102   } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) {
 103     for (InsertValueInst::idx_iterator I = IVI->idx_begin(),
 104          E = IVI->idx_end(); I != E; ++I)
 105       Res ^= *I;
 106   } else {
 107     // nothing extra to hash in.
 108     assert((isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
 109             isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
 110             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) &&
 111            "Invalid/unknown instruction");
 112   }
 113
 114   // Mix in the opcode.
 115   return (Res << 1) ^ Inst->getOpcode();
 116 }
 117
 118 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
 119   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 120
 121   if (LHS.isSentinel() || RHS.isSentinel())
 122     return LHSI == RHSI;
 123
 124   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 125   return LHSI->isIdenticalTo(RHSI);
 126 }
 127
 128 //===----------------------------------------------------------------------===//
 129 // MemoryValue
 130 //===----------------------------------------------------------------------===//
 131
 132 namespace {
 133   /// MemoryValue - Instances of this struct represent available load and call
 134   /// values in the scoped hash table.
 135   struct MemoryValue {
 136     Instruction *Inst;
 137
 138     bool isSentinel() const {
 139       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
 140              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
 141     }
 142
 143     static bool canHandle(Instruction *Inst) {
 144       if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
 145         return !LI->isVolatile();
 146       if (CallInst *CI = dyn_cast<CallInst>(Inst))
 147         return CI->onlyReadsMemory();
 148       return false;
 149     }
 150
 151     static MemoryValue get(Instruction *I) {
 152       MemoryValue X; X.Inst = I;
 153       assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!");
 154       return X;
 155     }
 156   };
 157 }
 158
 159 namespace llvm {
 160   // MemoryValue is POD.
 161   template<> struct isPodLike<MemoryValue> {
 162     static const bool value = true;
 163   };
 164
 165   template<> struct DenseMapInfo<MemoryValue> {
 166     static inline MemoryValue getEmptyKey() {
 167       return MemoryValue::get(DenseMapInfo<Instruction*>::getEmptyKey());
 168     }
 169     static inline MemoryValue getTombstoneKey() {
 170       return MemoryValue::get(DenseMapInfo<Instruction*>::getTombstoneKey());
 171     }
 172     static unsigned getHashValue(MemoryValue Val);
 173     static bool isEqual(MemoryValue LHS, MemoryValue RHS);
 174   };
 175 }
 176 unsigned DenseMapInfo<MemoryValue>::getHashValue(MemoryValue Val) {
 177   Instruction *Inst = Val.Inst;
 178   // Hash in all of the operands as pointers.
 179   unsigned Res = 0;
 180   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
 181     Res ^= getHash(Inst->getOperand(i)) << i;
 182   // Mix in the opcode.
 183   return (Res << 1) ^ Inst->getOpcode();
 184 }
 185
 186 bool DenseMapInfo<MemoryValue>::isEqual(MemoryValue LHS, MemoryValue RHS) {
 187   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 188
 189   if (LHS.isSentinel() || RHS.isSentinel())
 190     return LHSI == RHSI;
 191
 192   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 193   return LHSI->isIdenticalTo(RHSI);
 194 }
 195
 196
 197 //===----------------------------------------------------------------------===//
 198 // EarlyCSE pass.
 199 //===----------------------------------------------------------------------===//
 200
 201 namespace {
 202
 203 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
 204 /// tree, eliminating trivially redundant instructions and using instsimplify
 205 /// to canonicalize things as it goes.  It is intended to be fast and catch
 206 /// obvious cases so that instcombine and other passes are more effective.  It
 207 /// is expected that a later pass of GVN will catch the interesting/hard
 208 /// cases.
 209 class EarlyCSE : public FunctionPass {
 210 public:
 211   const TargetData *TD;
 212   DominatorTree *DT;
 213   typedef RecyclingAllocator<BumpPtrAllocator,
 214                       ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
 215   typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
 216                           AllocatorTy> ScopedHTType;
 217
 218   /// AvailableValues - This scoped hash table contains the current values of
 219   /// all of our simple scalar expressions.  As we walk down the domtree, we
 220   /// look to see if instructions are in this: if so, we replace them with what
 221   /// we find, otherwise we insert them so that dominated values can succeed in
 222   /// their lookup.
 223   ScopedHTType *AvailableValues;
 224
 225   typedef ScopedHashTable<MemoryValue, std::pair<Value*, unsigned> > MemHTType;
 226   /// AvailableMemValues - This scoped hash table contains the current values of
 227   /// loads and other read-only memory values.  This allows us to get efficient
 228   /// access to dominating loads we we find a fully redundant load.  In addition
 229   /// to the most recent load, we keep track of a generation count of the read,
 230   /// which is compared against the current generation count.  The current
 231   /// generation count is  incremented after every possibly writing memory
 232   /// operation, which ensures that we only CSE loads with other loads that have
 233   /// no intervening store.
 234   MemHTType *AvailableMemValues;
 235
 236   /// CurrentGeneration - This is the current generation of the memory value.
 237   unsigned CurrentGeneration;
 238
 239   static char ID;
 240   explicit EarlyCSE() : FunctionPass(ID) {
 241     initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
 242   }
 243
 244   bool runOnFunction(Function &F);
 245
 246 private:
 247
 248   bool processNode(DomTreeNode *Node);
 249
 250   // This transformation requires dominator postdominator info
 251   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 252     AU.addRequired<DominatorTree>();
 253     AU.setPreservesCFG();
 254   }
 255 };
 256 }
 257
 258 char EarlyCSE::ID = 0;
 259
 260 // createEarlyCSEPass - The public interface to this file.
 261 FunctionPass *llvm::createEarlyCSEPass() {
 262   return new EarlyCSE();
 263 }
 264
 265 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
 266 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 267 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
 268
 269 bool EarlyCSE::processNode(DomTreeNode *Node) {
 270   // Define a scope in the scoped hash table.  When we are done processing this
 271   // domtree node and recurse back up to our parent domtree node, this will pop
 272   // off all the values we install.
 273   ScopedHTType::ScopeTy Scope(*AvailableValues);
 274
 275   // Define a scope for the memory values so that anything we add will get
 276   // popped when we recurse back up to our parent domtree node.
 277   MemHTType::ScopeTy MemScope(*AvailableMemValues);
 278
 279   BasicBlock *BB = Node->getBlock();
 280
 281   // If this block has a single predecessor, then the predecessor is the parent
 282   // of the domtree node and all of the live out memory values are still current
 283   // in this block.  If this block has multiple predecessors, then they could
 284   // have invalidated the live-out memory values of our parent value.  For now,
 285   // just be conservative and invalidate memory if this block has multiple
 286   // predecessors.
 287   if (BB->getSinglePredecessor() == 0)
 288     ++CurrentGeneration;
 289
 290   bool Changed = false;
 291
 292   // See if any instructions in the block can be eliminated.  If so, do it.  If
 293   // not, add them to AvailableValues.
 294   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 295     Instruction *Inst = I++;
 296
 297     // Dead instructions should just be removed.
 298     if (isInstructionTriviallyDead(Inst)) {
 299       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 300       Inst->eraseFromParent();
 301       Changed = true;
 302       ++NumSimplify;
 303       continue;
 304     }
 305
 306     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 307     // its simpler value.
 308     if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
 309       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 310       Inst->replaceAllUsesWith(V);
 311       Inst->eraseFromParent();
 312       Changed = true;
 313       ++NumSimplify;
 314       continue;
 315     }
 316
 317     // If this is a simple instruction that we can value number, process it.
 318     if (SimpleValue::canHandle(Inst)) {
 319       // See if the instruction has an available value.  If so, use it.
 320       if (Value *V = AvailableValues->lookup(SimpleValue::get(Inst))) {
 321         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 322         Inst->replaceAllUsesWith(V);
 323         Inst->eraseFromParent();
 324         Changed = true;
 325         ++NumCSE;
 326         continue;
 327       }
 328
 329       // Otherwise, just remember that this value is available.
 330       AvailableValues->insert(SimpleValue::get(Inst), Inst);
 331       continue;
 332     }
 333
 334     // If this is a read-only memory value, process it.
 335     if (MemoryValue::canHandle(Inst)) {
 336       // If we have an available version of this value, and if it is the right
 337       // generation, replace this instruction.
 338       std::pair<Value*, unsigned> InVal =
 339         AvailableMemValues->lookup(MemoryValue::get(Inst));
 340       if (InVal.first != 0 && InVal.second == CurrentGeneration) {
 341         DEBUG(dbgs() << "EarlyCSE CSE MEM: " << *Inst << "  to: "
 342                      << *InVal.first << '\n');
 343         if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
 344         Inst->eraseFromParent();
 345         Changed = true;
 346         ++NumCSEMem;
 347         continue;
 348       }
 349
 350       // Otherwise, remember that we have this instruction.
 351       AvailableMemValues->insert(MemoryValue::get(Inst),
 352                          std::pair<Value*, unsigned>(Inst, CurrentGeneration));
 353       continue;
 354     }
 355
 356     // Okay, this isn't something we can CSE at all.  Check to see if it is
 357     // something that could modify memory.  If so, our available memory values
 358     // cannot be used so bump the generation count.
 359     if (Inst->mayWriteToMemory())
 360       ++CurrentGeneration;
 361   }
 362
 363   unsigned LiveOutGeneration = CurrentGeneration;
 364   for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 365     Changed |= processNode(*I);
 366     // Pop any generation changes off the stack from the recursive walk.
 367     CurrentGeneration = LiveOutGeneration;
 368   }
 369   return Changed;
 370 }
 371
 372
 373 bool EarlyCSE::runOnFunction(Function &F) {
 374   TD = getAnalysisIfAvailable<TargetData>();
 375   DT = &getAnalysis<DominatorTree>();
 376   ScopedHTType AVTable;
 377   AvailableValues = &AVTable;
 378
 379   MemHTType MemTable;
 380   AvailableMemValues = &MemTable;
 381
 382   CurrentGeneration = 0;
 383   return processNode(DT->getRootNode());
 384 }