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