/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/SimplifyInstructions.cpp
Line | Count | Source |
1 | | //===------ SimplifyInstructions.cpp - Remove redundant instructions ------===// |
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 is a utility pass used for testing the InstructionSimplify analysis. |
11 | | // The analysis is applied to every instruction, and if it simplifies then the |
12 | | // instruction is replaced by the simplification. If you are looking for a pass |
13 | | // that performs serious instruction folding, use the instcombine pass instead. |
14 | | // |
15 | | //===----------------------------------------------------------------------===// |
16 | | |
17 | | #include "llvm/Transforms/Utils/SimplifyInstructions.h" |
18 | | #include "llvm/ADT/DepthFirstIterator.h" |
19 | | #include "llvm/ADT/SmallPtrSet.h" |
20 | | #include "llvm/ADT/Statistic.h" |
21 | | #include "llvm/Analysis/AssumptionCache.h" |
22 | | #include "llvm/Analysis/InstructionSimplify.h" |
23 | | #include "llvm/Analysis/OptimizationDiagnosticInfo.h" |
24 | | #include "llvm/Analysis/TargetLibraryInfo.h" |
25 | | #include "llvm/IR/DataLayout.h" |
26 | | #include "llvm/IR/Dominators.h" |
27 | | #include "llvm/IR/Function.h" |
28 | | #include "llvm/IR/Type.h" |
29 | | #include "llvm/Pass.h" |
30 | | #include "llvm/Transforms/Scalar.h" |
31 | | #include "llvm/Transforms/Utils/Local.h" |
32 | | using namespace llvm; |
33 | | |
34 | | #define DEBUG_TYPE "instsimplify" |
35 | | |
36 | | STATISTIC(NumSimplified, "Number of redundant instructions removed"); |
37 | | |
38 | | static bool runImpl(Function &F, const SimplifyQuery &SQ, |
39 | 462k | OptimizationRemarkEmitter *ORE) { |
40 | 462k | SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; |
41 | 462k | bool Changed = false; |
42 | 462k | |
43 | 517k | do { |
44 | 5.56M | for (BasicBlock *BB : depth_first(&F.getEntryBlock())) { |
45 | 5.56M | // Here be subtlety: the iterator must be incremented before the loop |
46 | 5.56M | // body (not sure why), so a range-for loop won't work here. |
47 | 35.0M | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE35.0M ;) { |
48 | 29.5M | Instruction *I = &*BI++; |
49 | 29.5M | // The first time through the loop ToSimplify is empty and we try to |
50 | 29.5M | // simplify all instructions. On later iterations ToSimplify is not |
51 | 29.5M | // empty and we only bother simplifying instructions that are in it. |
52 | 29.5M | if (!ToSimplify->empty() && 29.5M !ToSimplify->count(I)10.0M ) |
53 | 9.82M | continue; |
54 | 19.6M | |
55 | 19.6M | // Don't waste time simplifying unused instructions. |
56 | 19.6M | if (19.6M !I->use_empty()19.6M ) { |
57 | 13.1M | if (Value *V13.1M = SimplifyInstruction(I, SQ, ORE)) { |
58 | 188k | // Mark all uses for resimplification next time round the loop. |
59 | 188k | for (User *U : I->users()) |
60 | 270k | Next->insert(cast<Instruction>(U)); |
61 | 188k | I->replaceAllUsesWith(V); |
62 | 188k | ++NumSimplified; |
63 | 188k | Changed = true; |
64 | 188k | } |
65 | 13.1M | } |
66 | 19.6M | if (RecursivelyDeleteTriviallyDeadInstructions(I, SQ.TLI)19.6M ) { |
67 | 188k | // RecursivelyDeleteTriviallyDeadInstruction can remove more than one |
68 | 188k | // instruction, so simply incrementing the iterator does not work. |
69 | 188k | // When instructions get deleted re-iterate instead. |
70 | 188k | BI = BB->begin(); |
71 | 188k | BE = BB->end(); |
72 | 188k | Changed = true; |
73 | 188k | } |
74 | 29.5M | } |
75 | 5.56M | } |
76 | 517k | |
77 | 517k | // Place the list of instructions to simplify on the next loop iteration |
78 | 517k | // into ToSimplify. |
79 | 517k | std::swap(ToSimplify, Next); |
80 | 517k | Next->clear(); |
81 | 517k | } while (!ToSimplify->empty()); |
82 | 462k | |
83 | 462k | return Changed; |
84 | 462k | } |
85 | | |
86 | | namespace { |
87 | | struct InstSimplifier : public FunctionPass { |
88 | | static char ID; // Pass identification, replacement for typeid |
89 | 17.3k | InstSimplifier() : FunctionPass(ID) { |
90 | 17.3k | initializeInstSimplifierPass(*PassRegistry::getPassRegistry()); |
91 | 17.3k | } |
92 | | |
93 | 17.3k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
94 | 17.3k | AU.setPreservesCFG(); |
95 | 17.3k | AU.addRequired<DominatorTreeWrapperPass>(); |
96 | 17.3k | AU.addRequired<AssumptionCacheTracker>(); |
97 | 17.3k | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
98 | 17.3k | AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); |
99 | 17.3k | } |
100 | | |
101 | | /// runOnFunction - Remove instructions that simplify. |
102 | 462k | bool runOnFunction(Function &F) override { |
103 | 462k | if (skipFunction(F)) |
104 | 75 | return false; |
105 | 462k | |
106 | 462k | const DominatorTree *DT = |
107 | 462k | &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
108 | 462k | const TargetLibraryInfo *TLI = |
109 | 462k | &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); |
110 | 462k | AssumptionCache *AC = |
111 | 462k | &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); |
112 | 462k | OptimizationRemarkEmitter *ORE = |
113 | 462k | &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); |
114 | 462k | const DataLayout &DL = F.getParent()->getDataLayout(); |
115 | 462k | const SimplifyQuery SQ(DL, TLI, DT, AC); |
116 | 462k | return runImpl(F, SQ, ORE); |
117 | 462k | } |
118 | | }; |
119 | | } |
120 | | |
121 | | char InstSimplifier::ID = 0; |
122 | 24.9k | INITIALIZE_PASS_BEGIN24.9k (InstSimplifier, "instsimplify",
|
123 | 24.9k | "Remove redundant instructions", false, false) |
124 | 24.9k | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) |
125 | 24.9k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
126 | 24.9k | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
127 | 24.9k | INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) |
128 | 24.9k | INITIALIZE_PASS_END(InstSimplifier, "instsimplify", |
129 | | "Remove redundant instructions", false, false) |
130 | | char &llvm::InstructionSimplifierID = InstSimplifier::ID; |
131 | | |
132 | | // Public interface to the simplify instructions pass. |
133 | 17.2k | FunctionPass *llvm::createInstructionSimplifierPass() { |
134 | 17.2k | return new InstSimplifier(); |
135 | 17.2k | } |
136 | | |
137 | | PreservedAnalyses InstSimplifierPass::run(Function &F, |
138 | 107 | FunctionAnalysisManager &AM) { |
139 | 107 | auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
140 | 107 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); |
141 | 107 | auto &AC = AM.getResult<AssumptionAnalysis>(F); |
142 | 107 | auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); |
143 | 107 | const DataLayout &DL = F.getParent()->getDataLayout(); |
144 | 107 | const SimplifyQuery SQ(DL, &TLI, &DT, &AC); |
145 | 107 | bool Changed = runImpl(F, SQ, &ORE); |
146 | 107 | if (!Changed) |
147 | 73 | return PreservedAnalyses::all(); |
148 | 34 | |
149 | 34 | PreservedAnalyses PA; |
150 | 34 | PA.preserveSet<CFGAnalyses>(); |
151 | 34 | return PA; |
152 | 34 | } |