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 instructions simplified or DCE'd");
30 STATISTIC(NumCSE, "Number of instructions CSE'd");
31 STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
32 STATISTIC(NumCSECall, "Number of call instructions CSE'd");
34 static unsigned getHash(const void *V) {
35 return DenseMapInfo<const void*>::getHashValue(V);
38 //===----------------------------------------------------------------------===//
40 //===----------------------------------------------------------------------===//
43 /// SimpleValue - Instances of this struct represent available values in the
44 /// scoped hash table.
48 SimpleValue(Instruction *I) : Inst(I) {
49 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
52 bool isSentinel() const {
53 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
54 Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
57 static bool canHandle(Instruction *Inst) {
58 return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
59 isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
60 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
61 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
62 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
68 // SimpleValue is POD.
69 template<> struct isPodLike<SimpleValue> {
70 static const bool value = true;
73 template<> struct DenseMapInfo<SimpleValue> {
74 static inline SimpleValue getEmptyKey() {
75 return DenseMapInfo<Instruction*>::getEmptyKey();
77 static inline SimpleValue getTombstoneKey() {
78 return DenseMapInfo<Instruction*>::getTombstoneKey();
80 static unsigned getHashValue(SimpleValue Val);
81 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
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);
127 //===----------------------------------------------------------------------===//
129 //===----------------------------------------------------------------------===//
132 /// CallValue - Instances of this struct represent available call values in
133 /// the scoped hash table.
137 CallValue(Instruction *I) : Inst(I) {
138 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
141 bool isSentinel() const {
142 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() ||
143 Inst == DenseMapInfo<Instruction*>::getTombstoneKey();
146 static bool canHandle(Instruction *Inst) {
147 if (CallInst *CI = dyn_cast<CallInst>(Inst))
148 return CI->onlyReadsMemory();
156 template<> struct isPodLike<CallValue> {
157 static const bool value = true;
160 template<> struct DenseMapInfo<CallValue> {
161 static inline CallValue getEmptyKey() {
162 return DenseMapInfo<Instruction*>::getEmptyKey();
164 static inline CallValue getTombstoneKey() {
165 return DenseMapInfo<Instruction*>::getTombstoneKey();
167 static unsigned getHashValue(CallValue Val);
168 static bool isEqual(CallValue LHS, CallValue RHS);
171 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
172 Instruction *Inst = Val.Inst;
173 // Hash in all of the operands as pointers.
175 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
176 Res ^= getHash(Inst->getOperand(i)) << i;
177 // Mix in the opcode.
178 return (Res << 1) ^ Inst->getOpcode();
181 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
182 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
183 if (LHS.isSentinel() || RHS.isSentinel())
185 return LHSI->isIdenticalTo(RHSI);
189 //===----------------------------------------------------------------------===//
191 //===----------------------------------------------------------------------===//
195 /// EarlyCSE - This pass does a simple depth-first walk over the dominator
196 /// tree, eliminating trivially redundant instructions and using instsimplify
197 /// to canonicalize things as it goes. It is intended to be fast and catch
198 /// obvious cases so that instcombine and other passes are more effective. It
199 /// is expected that a later pass of GVN will catch the interesting/hard
201 class EarlyCSE : public FunctionPass {
203 const TargetData *TD;
205 typedef RecyclingAllocator<BumpPtrAllocator,
206 ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy;
207 typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>,
208 AllocatorTy> ScopedHTType;
210 /// AvailableValues - This scoped hash table contains the current values of
211 /// all of our simple scalar expressions. As we walk down the domtree, we
212 /// look to see if instructions are in this: if so, we replace them with what
213 /// we find, otherwise we insert them so that dominated values can succeed in
215 ScopedHTType *AvailableValues;
217 /// AvailableLoads - This scoped hash table contains the current values
218 /// of loads. This allows us to get efficient access to dominating loads when
219 /// we have a fully redundant load. In addition to the most recent load, we
220 /// keep track of a generation count of the read, which is compared against
221 /// the current generation count. The current generation count is
222 /// incremented after every possibly writing memory operation, which ensures
223 /// that we only CSE loads with other loads that have no intervening store.
224 typedef RecyclingAllocator<BumpPtrAllocator,
225 ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator;
226 typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>,
227 DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType;
228 LoadHTType *AvailableLoads;
230 /// AvailableCalls - This scoped hash table contains the current values
231 /// of read-only call values. It uses the same generation count as loads.
232 typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType;
233 CallHTType *AvailableCalls;
235 /// CurrentGeneration - This is the current generation of the memory value.
236 unsigned CurrentGeneration;
239 explicit EarlyCSE() : FunctionPass(ID) {
240 initializeEarlyCSEPass(*PassRegistry::getPassRegistry());
243 bool runOnFunction(Function &F);
247 bool processNode(DomTreeNode *Node);
249 // This transformation requires dominator postdominator info
250 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
251 AU.addRequired<DominatorTree>();
252 AU.setPreservesCFG();
257 char EarlyCSE::ID = 0;
259 // createEarlyCSEPass - The public interface to this file.
260 FunctionPass *llvm::createEarlyCSEPass() {
261 return new EarlyCSE();
264 INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false)
265 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
266 INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false)
268 bool EarlyCSE::processNode(DomTreeNode *Node) {
269 // Define a scope in the scoped hash table. When we are done processing this
270 // domtree node and recurse back up to our parent domtree node, this will pop
271 // off all the values we install.
272 ScopedHTType::ScopeTy Scope(*AvailableValues);
274 // Define a scope for the load values so that anything we add will get
275 // popped when we recurse back up to our parent domtree node.
276 LoadHTType::ScopeTy LoadScope(*AvailableLoads);
278 // Define a scope for the call values so that anything we add will get
279 // popped when we recurse back up to our parent domtree node.
280 CallHTType::ScopeTy CallScope(*AvailableCalls);
282 BasicBlock *BB = Node->getBlock();
284 // If this block has a single predecessor, then the predecessor is the parent
285 // of the domtree node and all of the live out memory values are still current
286 // in this block. If this block has multiple predecessors, then they could
287 // have invalidated the live-out memory values of our parent value. For now,
288 // just be conservative and invalidate memory if this block has multiple
290 if (BB->getSinglePredecessor() == 0)
293 bool Changed = false;
295 // See if any instructions in the block can be eliminated. If so, do it. If
296 // not, add them to AvailableValues.
297 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
298 Instruction *Inst = I++;
300 // Dead instructions should just be removed.
301 if (isInstructionTriviallyDead(Inst)) {
302 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
303 Inst->eraseFromParent();
309 // If the instruction can be simplified (e.g. X+0 = X) then replace it with
310 // its simpler value.
311 if (Value *V = SimplifyInstruction(Inst, TD, DT)) {
312 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n');
313 Inst->replaceAllUsesWith(V);
314 Inst->eraseFromParent();
320 // If this is a simple instruction that we can value number, process it.
321 if (SimpleValue::canHandle(Inst)) {
322 // See if the instruction has an available value. If so, use it.
323 if (Value *V = AvailableValues->lookup(Inst)) {
324 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n');
325 Inst->replaceAllUsesWith(V);
326 Inst->eraseFromParent();
332 // Otherwise, just remember that this value is available.
333 AvailableValues->insert(Inst, Inst);
337 // If this is a non-volatile load, process it.
338 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
339 // Ignore volatile loads.
340 if (LI->isVolatile()) continue;
342 // If we have an available version of this load, and if it is the right
343 // generation, replace this instruction.
344 std::pair<Value*, unsigned> InVal =
345 AvailableLoads->lookup(Inst->getOperand(0));
346 if (InVal.first != 0 && InVal.second == CurrentGeneration) {
347 DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << " to: "
348 << *InVal.first << '\n');
349 if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
350 Inst->eraseFromParent();
356 // Otherwise, remember that we have this instruction.
357 AvailableLoads->insert(Inst->getOperand(0),
358 std::pair<Value*, unsigned>(Inst, CurrentGeneration));
362 // If this is a read-only call, process it.
363 if (CallValue::canHandle(Inst)) {
364 // If we have an available version of this call, and if it is the right
365 // generation, replace this instruction.
366 std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst);
367 if (InVal.first != 0 && InVal.second == CurrentGeneration) {
368 DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << " to: "
369 << *InVal.first << '\n');
370 if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first);
371 Inst->eraseFromParent();
377 // Otherwise, remember that we have this instruction.
378 AvailableCalls->insert(Inst,
379 std::pair<Value*, unsigned>(Inst, CurrentGeneration));
383 // Okay, this isn't something we can CSE at all. Check to see if it is
384 // something that could modify memory. If so, our available memory values
385 // cannot be used so bump the generation count.
386 if (Inst->mayWriteToMemory()) {
389 // Okay, we just invalidated anything we knew about loaded values. Try to
390 // salvage *something* by remembering that the stored value is a live
391 // version of the pointer. It is safe to forward from volatile stores to
392 // non-volatile loads, so we don't have to check for volatility of the
394 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
395 AvailableLoads->insert(SI->getPointerOperand(),
396 std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
401 unsigned LiveOutGeneration = CurrentGeneration;
402 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) {
403 Changed |= processNode(*I);
404 // Pop any generation changes off the stack from the recursive walk.
405 CurrentGeneration = LiveOutGeneration;
411 bool EarlyCSE::runOnFunction(Function &F) {
412 TD = getAnalysisIfAvailable<TargetData>();
413 DT = &getAnalysis<DominatorTree>();
415 // Tables that the pass uses when walking the domtree.
416 ScopedHTType AVTable;
417 AvailableValues = &AVTable;
418 LoadHTType LoadTable;
419 AvailableLoads = &LoadTable;
420 CallHTType CallTable;
421 AvailableCalls = &CallTable;
423 CurrentGeneration = 0;
424 return processNode(DT->getRootNode());