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/Analysis/InstructionSimplify.h"
22 #include "llvm/Target/TargetData.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "llvm/Support/Debug.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");
33 /// InstValue - Instances of this struct represent available values in the
34 /// scoped hash table.
38 bool isSentinel() const {
39 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
40 Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
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);
51 static InstValue get(Instruction *I) {
52 InstValue X; X.Inst = I;
53 assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!");
61 template<> struct isPodLike<InstValue> {
62 static const bool value = true;
65 template<> struct DenseMapInfo<InstValue> {
66 static inline InstValue getEmptyKey() {
67 return InstValue::get(DenseMapInfo<Instruction*>::getEmptyKey());
69 static inline InstValue getTombstoneKey() {
70 return InstValue::get(DenseMapInfo<Instruction*>::getTombstoneKey());
72 static unsigned getHashValue(InstValue Val);
73 static bool isEqual(InstValue LHS, InstValue RHS);
77 unsigned getHash(const void *V) {
78 return DenseMapInfo<const void*>::getHashValue(V);
81 unsigned DenseMapInfo<InstValue>::getHashValue(InstValue Val) {
82 Instruction *Inst = Val.Inst;
84 if (CastInst *CI = dyn_cast<CastInst>(Inst))
85 Res = getHash(CI->getOperand(0)) ^ getHash(CI->getType());
86 else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Inst))
87 Res = getHash(BO->getOperand(0)) ^ (getHash(BO->getOperand(1)) << 1);
88 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
89 Res = getHash(CI->getOperand(0));
90 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
91 Res ^= getHash(CI->getOperand(i)) << i;
92 } else if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
93 Res = getHash(CI->getOperand(0)) ^ (getHash(CI->getOperand(1)) << 1) ^
96 assert((isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
97 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
98 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst)) &&
99 "Unhandled instruction kind");
100 Res = getHash(CI->getType()) << 4;
101 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
102 Res ^= getHash(CI->getOperand(i)) << i;
105 return (Res << 1) ^ Inst->getOpcode();
108 bool DenseMapInfo<InstValue>::isEqual(InstValue LHS, InstValue RHS) {
109 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
111 if (LHS.isSentinel() || RHS.isSentinel())
114 if (LHSI->getOpcode() != RHSI->getOpcode()) return false;
115 return LHSI->isIdenticalTo(RHSI);
121 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
122 /// tree, eliminating trivially redundant instructions and using instsimplify
123 /// to canonicalize things as it goes. It is intended to be fast and catch
124 /// obvious cases so that instcombine and other passes are more effective. It
125 /// is expected that a later pass of GVN will catch the interesting/hard
127 class EarlyCSE : public FunctionPass {
129 const TargetData *TD;
131 ScopedHashTable<InstValue, Instruction*> *AvailableValues;
136 initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
139 bool runOnFunction(Function &F);
143 bool processNode(DomTreeNode *Node);
145 // This transformation requires dominator postdominator info
146 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
147 AU.addRequired<DominatorTree>();
148 AU.setPreservesCFG();
153 char EarlyCSE::ID = 0;
155 // createEarlyCSEPass - The public interface to this file.
156 FunctionPass *llvm::createEarlyCSEPass() {
157 return new EarlyCSE();
160 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
161 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
162 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
164 // FIXME: Should bump pointer allocate entries in scoped hash table.
166 bool EarlyCSE::processNode(DomTreeNode *Node) {
167 // Define a scope in the scoped hash table.
168 ScopedHashTableScope<InstValue, Instruction*> Scope(*AvailableValues);
170 BasicBlock *BB = Node->getBlock();
172 bool Changed = false;
174 // See if any instructions in the block can be eliminated. If so, do it. If
175 // not, add them to AvailableValues.
176 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
177 Instruction *Inst = I++;
179 // Dead instructions should just be removed.
180 if (isInstructionTriviallyDead(Inst)) {
181 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
182 Inst->eraseFromParent();
188 // If the instruction can be simplified (e.g. X+0 = X) then replace it with
189 // its simpler value.
190 if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
191 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n');
192 Inst->replaceAllUsesWith(V);
193 Inst->eraseFromParent();
199 // If this instruction is something that we can't value number, ignore it.
200 if (!InstValue::canHandle(Inst))
203 // See if the instruction has an available value. If so, use it.
204 if (Instruction *V = AvailableValues->lookup(InstValue::get(Inst))) {
205 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n');
206 Inst->replaceAllUsesWith(V);
207 Inst->eraseFromParent();
213 // Otherwise, just remember that this value is available.
214 AvailableValues->insert(InstValue::get(Inst), Inst);
218 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
219 Changed |= processNode(*I);
224 bool EarlyCSE::runOnFunction(Function &F) {
225 TD = getAnalysisIfAvailable<TargetData>();
226 DT = &getAnalysis<DominatorTree>();
227 ScopedHashTable<InstValue, Instruction*> AVTable;
228 AvailableValues = &AVTable;
229 return processNode(DT->getRootNode());