EarlyCSE.cpp revision 82dcd5edd22f017b74ebe98acc07b3a7191e7ff1
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 32namespace { 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 59namespace llvm { 60// InstValue is POD. 61template<> struct isPodLike<InstValue> { 62 static const bool value = true; 63}; 64 65template<> 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 77unsigned getHash(const void *V) { 78 return DenseMapInfo<const void*>::getHashValue(V); 79} 80 81unsigned 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 113bool 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 124namespace { 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. 132class EarlyCSE : public FunctionPass { 133public: 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 150private: 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 162char EarlyCSE::ID = 0; 163 164// createEarlyCSEPass - The public interface to this file. 165FunctionPass *llvm::createEarlyCSEPass() { 166 return new EarlyCSE(); 167} 168 169INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false) 170INITIALIZE_PASS_DEPENDENCY(DominatorTree) 171INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false) 172 173bool 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 232bool 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 240