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