1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs a simple dominator tree walk that eliminates trivially
11 // redundant instructions.
13 //===----------------------------------------------------------------------===//
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"
29 STATISTIC(NumSimplify, "Number of insts simplified or DCE'd");
30 STATISTIC(NumCSE, "Number of insts CSE'd");
32 //===----------------------------------------------------------------------===//
34 //===----------------------------------------------------------------------===//
37 /// SimpleValue - Instances of this struct represent available values in the
38 /// scoped hash table.
42 bool isSentinel() const {
43 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
44 Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
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);
55 static SimpleValue get(Instruction *I) {
56 SimpleValue X; X.Inst = I;
57 assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!");
64 // SimpleValue is POD.
65 template<> struct isPodLike<SimpleValue> {
66 static const bool value = true;
69 template<> struct DenseMapInfo<SimpleValue> {
70 static inline SimpleValue getEmptyKey() {
71 return SimpleValue::get(DenseMapInfo<Instruction*>::getEmptyKey());
73 static inline SimpleValue getTombstoneKey() {
74 return SimpleValue::get(DenseMapInfo<Instruction*>::getTombstoneKey());
76 static unsigned getHashValue(SimpleValue Val);
77 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
81 unsigned getHash(const void *V) {
82 return DenseMapInfo<const void*>::getHashValue(V);
85 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
86 Instruction *Inst = Val.Inst;
88 // Hash in all of the operands as pointers.
90 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
91 Res ^= getHash(Inst->getOperand(i)) << i;
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)
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)
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");
113 // Mix in the opcode.
114 return (Res << 1) ^ Inst->getOpcode();
117 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
118 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
120 if (LHS.isSentinel() || RHS.isSentinel())
123 if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
124 return LHSI->isIdenticalTo(RHSI);
128 //===----------------------------------------------------------------------===//
130 //===----------------------------------------------------------------------===//
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
140 class EarlyCSE : public FunctionPass {
142 const TargetData *TD;
144 typedef RecyclingAllocator<BumpPtrAllocator,
145 ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
146 typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
147 AllocatorTy> ScopedHTType;
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
154 ScopedHTType *AvailableValues;
157 explicit EarlyCSE() : FunctionPass(ID) {
158 initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
161 bool runOnFunction(Function &F);
165 bool processNode(DomTreeNode *Node);
167 // This transformation requires dominator postdominator info
168 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
169 AU.addRequired<DominatorTree>();
170 AU.setPreservesCFG();
175 char EarlyCSE::ID = 0;
177 // createEarlyCSEPass - The public interface to this file.
178 FunctionPass *llvm::createEarlyCSEPass() {
179 return new EarlyCSE();
182 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
183 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
184 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
186 bool 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);
193 BasicBlock *BB = Node->getBlock();
195 bool Changed = false;
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++;
202 // Dead instructions should just be removed.
203 if (isInstructionTriviallyDead(Inst)) {
204 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
205 Inst->eraseFromParent();
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();
222 // If this instruction is something that we can't value number, ignore it.
223 if (!SimpleValue::canHandle(Inst))
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();
236 // Otherwise, just remember that this value is available.
237 AvailableValues->insert(SimpleValue::get(Inst), Inst);
241 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
242 Changed |= processNode(*I);
247 bool EarlyCSE::runOnFunction(Function &F) {
248 TD = getAnalysisIfAvailable<TargetData>();
249 DT = &getAnalysis<DominatorTree>();
250 ScopedHTType AVTable;
251 AvailableValues = &AVTable;
253 return processNode(DT->getRootNode());