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