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/Target/TargetLibraryInfo.h"
  23 #include "llvm/Transforms/Utils/Local.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/RecyclingAllocator.h"
  26 #include "llvm/ADT/ScopedHashTable.h"
  27 #include "llvm/ADT/Statistic.h"
  28 using namespace llvm;
  29
  30 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
  31 STATISTIC(NumCSE,      "Number of instructions CSE'd");
  32 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
  33 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
  34 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
  35
  36 static unsigned getHash(const void *V) {
  37   return DenseMapInfo<const void*>::getHashValue(V);
  38 }
  39
  40 //===----------------------------------------------------------------------===//
  41 // SimpleValue
  42 //===----------------------------------------------------------------------===//
  43
  44 namespace {
  45   /// SimpleValue - Instances of this struct represent available values in the
  46   /// scoped hash table.
  47   struct SimpleValue {
  48     Instruction *Inst;
  49
  50     SimpleValue(Instruction *I) : Inst(I) {
  51       assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
  52     }
  53
  54     bool isSentinel() const {
  55       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
  56              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
  57     }
  58
  59     static bool canHandle(Instruction *Inst) {
  60       // This can only handle non-void readnone functions.
  61       if (CallInst *CI = dyn_cast<CallInst>(Inst))
  62         return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
  63       return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
  64              isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
  65              isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
  66              isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
  67              isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
  68     }
  69   };
  70 }
  71
  72 namespace llvm {
  73 // SimpleValue is POD.
  74 template<> struct isPodLike<SimpleValue> {
  75   static const bool value = true;
  76 };
  77
  78 template<> struct DenseMapInfo<SimpleValue> {
  79   static inline SimpleValue getEmptyKey() {
  80     return DenseMapInfo<Instruction*>::getEmptyKey();
  81   }
  82   static inline SimpleValue getTombstoneKey() {
  83     return DenseMapInfo<Instruction*>::getTombstoneKey();
  84   }
  85   static unsigned getHashValue(SimpleValue Val);
  86   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
  87 };
  88 }
  89
  90 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
  91   Instruction *Inst = Val.Inst;
  92
  93   // Hash in all of the operands as pointers.
  94   unsigned Res = 0;
  95   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
  96     Res ^= getHash(Inst->getOperand(i)) << (i & 0xF);
  97
  98   if (CastInst *CI = dyn_cast<CastInst>(Inst))
  99     Res ^= getHash(CI->getType());
 100   else if (CmpInst *CI = dyn_cast<CmpInst>(Inst))
 101     Res ^= CI->getPredicate();
 102   else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) {
 103     for (ExtractValueInst::idx_iterator I = EVI->idx_begin(),
 104          E = EVI->idx_end(); I != E; ++I)
 105       Res ^= *I;
 106   } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) {
 107     for (InsertValueInst::idx_iterator I = IVI->idx_begin(),
 108          E = IVI->idx_end(); I != E; ++I)
 109       Res ^= *I;
 110   } else {
 111     // nothing extra to hash in.
 112     assert((isa<CallInst>(Inst) ||
 113             isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
 114             isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
 115             isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) &&
 116            "Invalid/unknown instruction");
 117   }
 118
 119   // Mix in the opcode.
 120   return (Res << 1) ^ Inst->getOpcode();
 121 }
 122
 123 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
 124   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 125
 126   if (LHS.isSentinel() || RHS.isSentinel())
 127     return LHSI == RHSI;
 128
 129   if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
 130   return LHSI->isIdenticalTo(RHSI);
 131 }
 132
 133 //===----------------------------------------------------------------------===//
 134 // CallValue
 135 //===----------------------------------------------------------------------===//
 136
 137 namespace {
 138   /// CallValue - Instances of this struct represent available call values in
 139   /// the scoped hash table.
 140   struct CallValue {
 141     Instruction *Inst;
 142
 143     CallValue(Instruction *I) : Inst(I) {
 144       assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
 145     }
 146
 147     bool isSentinel() const {
 148       return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
 149              Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
 150     }
 151
 152     static bool canHandle(Instruction *Inst) {
 153       // Don't value number anything that returns void.
 154       if (Inst->getType()->isVoidTy())
 155         return false;
 156
 157       CallInst *CI = dyn_cast<CallInst>(Inst);
 158       if (CI == 0 || !CI->onlyReadsMemory())
 159         return false;
 160       return true;
 161     }
 162   };
 163 }
 164
 165 namespace llvm {
 166   // CallValue is POD.
 167   template<> struct isPodLike<CallValue> {
 168     static const bool value = true;
 169   };
 170
 171   template<> struct DenseMapInfo<CallValue> {
 172     static inline CallValue getEmptyKey() {
 173       return DenseMapInfo<Instruction*>::getEmptyKey();
 174     }
 175     static inline CallValue getTombstoneKey() {
 176       return DenseMapInfo<Instruction*>::getTombstoneKey();
 177     }
 178     static unsigned getHashValue(CallValue Val);
 179     static bool isEqual(CallValue LHS, CallValue RHS);
 180   };
 181 }
 182 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
 183   Instruction *Inst = Val.Inst;
 184   // Hash in all of the operands as pointers.
 185   unsigned Res = 0;
 186   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) {
 187     assert(!Inst->getOperand(i)->getType()->isMetadataTy() &&
 188            "Cannot value number calls with metadata operands");
 189     Res ^= getHash(Inst->getOperand(i)) << (i & 0xF);
 190   }
 191
 192   // Mix in the opcode.
 193   return (Res << 1) ^ Inst->getOpcode();
 194 }
 195
 196 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
 197   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 198   if (LHS.isSentinel() || RHS.isSentinel())
 199     return LHSI == RHSI;
 200   return LHSI->isIdenticalTo(RHSI);
 201 }
 202
 203
 204 //===----------------------------------------------------------------------===//
 205 // EarlyCSE pass.
 206 //===----------------------------------------------------------------------===//
 207
 208 namespace {
 209
 210 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
 211 /// tree, eliminating trivially redundant instructions and using instsimplify
 212 /// to canonicalize things as it goes.  It is intended to be fast and catch
 213 /// obvious cases so that instcombine and other passes are more effective.  It
 214 /// is expected that a later pass of GVN will catch the interesting/hard
 215 /// cases.
 216 class EarlyCSE : public FunctionPass {
 217 public:
 218   const TargetData *TD;
 219   const TargetLibraryInfo *TLI;
 220   DominatorTree *DT;
 221   typedef RecyclingAllocator<BumpPtrAllocator,
 222                       ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
 223   typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
 224                           AllocatorTy> ScopedHTType;
 225
 226   /// AvailableValues - This scoped hash table contains the current values of
 227   /// all of our simple scalar expressions.  As we walk down the domtree, we
 228   /// look to see if instructions are in this: if so, we replace them with what
 229   /// we find, otherwise we insert them so that dominated values can succeed in
 230   /// their lookup.
 231   ScopedHTType *AvailableValues;
 232
 233   /// AvailableLoads - This scoped hash table contains the current values
 234   /// of loads.  This allows us to get efficient access to dominating loads when
 235   /// we have a fully redundant load.  In addition to the most recent load, we
 236   /// keep track of a generation count of the read, which is compared against
 237   /// the current generation count.  The current generation count is
 238   /// incremented after every possibly writing memory operation, which ensures
 239   /// that we only CSE loads with other loads that have no intervening store.
 240   typedef RecyclingAllocator<BumpPtrAllocator,
 241     ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator;
 242   typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>,
 243                           DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType;
 244   LoadHTType *AvailableLoads;
 245
 246   /// AvailableCalls - This scoped hash table contains the current values
 247   /// of read-only call values.  It uses the same generation count as loads.
 248   typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType;
 249   CallHTType *AvailableCalls;
 250
 251   /// CurrentGeneration - This is the current generation of the memory value.
 252   unsigned CurrentGeneration;
 253
 254   static char ID;
 255   explicit EarlyCSE() : FunctionPass(ID) {
 256     initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
 257   }
 258
 259   bool runOnFunction(Function &F);
 260
 261 private:
 262
 263   bool processNode(DomTreeNode *Node);
 264
 265   // This transformation requires dominator postdominator info
 266   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 267     AU.addRequired<DominatorTree>();
 268     AU.addRequired<TargetLibraryInfo>();
 269     AU.setPreservesCFG();
 270   }
 271 };
 272 }
 273
 274 char EarlyCSE::ID = 0;
 275
 276 // createEarlyCSEPass - The public interface to this file.
 277 FunctionPass *llvm::createEarlyCSEPass() {
 278   return new EarlyCSE();
 279 }
 280
 281 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
 282 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 283 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 284 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
 285
 286 bool EarlyCSE::processNode(DomTreeNode *Node) {
 287   // Define a scope in the scoped hash table.  When we are done processing this
 288   // domtree node and recurse back up to our parent domtree node, this will pop
 289   // off all the values we install.
 290   ScopedHTType::ScopeTy Scope(*AvailableValues);
 291
 292   // Define a scope for the load values so that anything we add will get
 293   // popped when we recurse back up to our parent domtree node.
 294   LoadHTType::ScopeTy LoadScope(*AvailableLoads);
 295
 296   // Define a scope for the call values so that anything we add will get
 297   // popped when we recurse back up to our parent domtree node.
 298   CallHTType::ScopeTy CallScope(*AvailableCalls);
 299
 300   BasicBlock *BB = Node->getBlock();
 301
 302   // If this block has a single predecessor, then the predecessor is the parent
 303   // of the domtree node and all of the live out memory values are still current
 304   // in this block.  If this block has multiple predecessors, then they could
 305   // have invalidated the live-out memory values of our parent value.  For now,
 306   // just be conservative and invalidate memory if this block has multiple
 307   // predecessors.
 308   if (BB->getSinglePredecessor() == 0)
 309     ++CurrentGeneration;
 310
 311   /// LastStore - Keep track of the last non-volatile store that we saw... for
 312   /// as long as there in no instruction that reads memory.  If we see a store
 313   /// to the same location, we delete the dead store.  This zaps trivial dead
 314   /// stores which can occur in bitfield code among other things.
 315   StoreInst *LastStore = 0;
 316
 317   bool Changed = false;
 318
 319   // See if any instructions in the block can be eliminated.  If so, do it.  If
 320   // not, add them to AvailableValues.
 321   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 322     Instruction *Inst = I++;
 323
 324     // Dead instructions should just be removed.
 325     if (isInstructionTriviallyDead(Inst)) {
 326       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
 327       Inst->eraseFromParent();
 328       Changed = true;
 329       ++NumSimplify;
 330       continue;
 331     }
 332
 333     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
 334     // its simpler value.
 335     if (Value *V = SimplifyInstruction(Inst, TD, TLI, DT)) {
 336       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
 337       Inst->replaceAllUsesWith(V);
 338       Inst->eraseFromParent();
 339       Changed = true;
 340       ++NumSimplify;
 341       continue;
 342     }
 343
 344     // If this is a simple instruction that we can value number, process it.
 345     if (SimpleValue::canHandle(Inst)) {
 346       // See if the instruction has an available value.  If so, use it.
 347       if (Value *V = AvailableValues->lookup(Inst)) {
 348         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
 349         Inst->replaceAllUsesWith(V);
 350         Inst->eraseFromParent();
 351         Changed = true;
 352         ++NumCSE;
 353         continue;
 354       }
 355
 356       // Otherwise, just remember that this value is available.
 357       AvailableValues->insert(Inst, Inst);
 358       continue;
 359     }
 360
 361     // If this is a non-volatile load, process it.
 362     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 363       // Ignore volatile loads.
 364       if (!LI->isSimple()) {
 365         LastStore = 0;
 366         continue;
 367       }
 368
 369       // If we have an available version of this load, and if it is the right
 370       // generation, replace this instruction.
 371       std::pair<Value*, unsigned> InVal =
 372         AvailableLoads->lookup(Inst->getOperand(0));
 373       if (InVal.first != 0 && InVal.second == CurrentGeneration) {
 374         DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << "  to: "
 375               << *InVal.first << '\n');
 376         if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
 377         Inst->eraseFromParent();
 378         Changed = true;
 379         ++NumCSELoad;
 380         continue;
 381       }
 382
 383       // Otherwise, remember that we have this instruction.
 384       AvailableLoads->insert(Inst->getOperand(0),
 385                           std::pair<Value*, unsigned>(Inst, CurrentGeneration));
 386       LastStore = 0;
 387       continue;
 388     }
 389
 390     // If this instruction may read from memory, forget LastStore.
 391     if (Inst->mayReadFromMemory())
 392       LastStore = 0;
 393
 394     // If this is a read-only call, process it.
 395     if (CallValue::canHandle(Inst)) {
 396       // If we have an available version of this call, and if it is the right
 397       // generation, replace this instruction.
 398       std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst);
 399       if (InVal.first != 0 && InVal.second == CurrentGeneration) {
 400         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << "  to: "
 401                      << *InVal.first << '\n');
 402         if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
 403         Inst->eraseFromParent();
 404         Changed = true;
 405         ++NumCSECall;
 406         continue;
 407       }
 408
 409       // Otherwise, remember that we have this instruction.
 410       AvailableCalls->insert(Inst,
 411                          std::pair<Value*, unsigned>(Inst, CurrentGeneration));
 412       continue;
 413     }
 414
 415     // Okay, this isn't something we can CSE at all.  Check to see if it is
 416     // something that could modify memory.  If so, our available memory values
 417     // cannot be used so bump the generation count.
 418     if (Inst->mayWriteToMemory()) {
 419       ++CurrentGeneration;
 420
 421       if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 422         // We do a trivial form of DSE if there are two stores to the same
 423         // location with no intervening loads.  Delete the earlier store.
 424         if (LastStore &&
 425             LastStore->getPointerOperand() == SI->getPointerOperand()) {
 426           DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << "  due to: "
 427                        << *Inst << '\n');
 428           LastStore->eraseFromParent();
 429           Changed = true;
 430           ++NumDSE;
 431           LastStore = 0;
 432           continue;
 433         }
 434
 435         // Okay, we just invalidated anything we knew about loaded values.  Try
 436         // to salvage *something* by remembering that the stored value is a live
 437         // version of the pointer.  It is safe to forward from volatile stores
 438         // to non-volatile loads, so we don't have to check for volatility of
 439         // the store.
 440         AvailableLoads->insert(SI->getPointerOperand(),
 441          std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
 442
 443         // Remember that this was the last store we saw for DSE.
 444         if (SI->isSimple())
 445           LastStore = SI;
 446       }
 447     }
 448   }
 449
 450   unsigned LiveOutGeneration = CurrentGeneration;
 451   for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
 452     Changed |= processNode(*I);
 453     // Pop any generation changes off the stack from the recursive walk.
 454     CurrentGeneration = LiveOutGeneration;
 455   }
 456   return Changed;
 457 }
 458
 459
 460 bool EarlyCSE::runOnFunction(Function &F) {
 461   TD = getAnalysisIfAvailable<TargetData>();
 462   TLI = &getAnalysis<TargetLibraryInfo>();
 463   DT = &getAnalysis<DominatorTree>();
 464
 465   // Tables that the pass uses when walking the domtree.
 466   ScopedHTType AVTable;
 467   AvailableValues = &AVTable;
 468   LoadHTType LoadTable;
 469   AvailableLoads = &LoadTable;
 470   CallHTType CallTable;
 471   AvailableCalls = &CallTable;
 472
 473   CurrentGeneration = 0;
 474   return processNode(DT->getRootNode());
 475 }