1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification 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 lightweight instruction simplification on loop bodies.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Scalar/LoopInstSimplify.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/AssumptionCache.h"
18 #include "llvm/Analysis/InstructionSimplify.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Analysis/LoopPass.h"
21 #include "llvm/Analysis/ScalarEvolution.h"
22 #include "llvm/Analysis/TargetLibraryInfo.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Transforms/Scalar.h"
28 #include "llvm/Transforms/Scalar/LoopPassManager.h"
29 #include "llvm/Transforms/Utils/Local.h"
30 #include "llvm/Transforms/Utils/LoopUtils.h"
33 #define DEBUG_TYPE "loop-instsimplify"
35 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
37 static bool SimplifyLoopInst(Loop *L, DominatorTree *DT, LoopInfo *LI,
39 const TargetLibraryInfo *TLI) {
40 SmallVector<BasicBlock *, 8> ExitBlocks;
41 L->getUniqueExitBlocks(ExitBlocks);
42 array_pod_sort(ExitBlocks.begin(), ExitBlocks.end());
44 SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
46 // The bit we are stealing from the pointer represents whether this basic
47 // block is the header of a subloop, in which case we only process its phis.
48 typedef PointerIntPair<BasicBlock *, 1> WorklistItem;
49 SmallVector<WorklistItem, 16> VisitStack;
50 SmallPtrSet<BasicBlock *, 32> Visited;
60 VisitStack.push_back(WorklistItem(L->getHeader(), false));
62 while (!VisitStack.empty()) {
63 WorklistItem Item = VisitStack.pop_back_val();
64 BasicBlock *BB = Item.getPointer();
65 bool IsSubloopHeader = Item.getInt();
66 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
68 // Simplify instructions in the current basic block.
69 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
70 Instruction *I = &*BI++;
72 // The first time through the loop ToSimplify is empty and we try to
73 // simplify all instructions. On later iterations ToSimplify is not
74 // empty and we only bother simplifying instructions that are in it.
75 if (!ToSimplify->empty() && !ToSimplify->count(I))
78 // Don't bother simplifying unused instructions.
79 if (!I->use_empty()) {
80 Value *V = SimplifyInstruction(I, DL, TLI, DT, AC);
81 if (V && LI->replacementPreservesLCSSAForm(I, V)) {
82 // Mark all uses for resimplification next time round the loop.
83 for (User *U : I->users())
84 Next->insert(cast<Instruction>(U));
86 I->replaceAllUsesWith(V);
91 if (RecursivelyDeleteTriviallyDeadInstructions(I, TLI)) {
92 // RecursivelyDeleteTriviallyDeadInstruction can remove more than one
93 // instruction, so simply incrementing the iterator does not work.
94 // When instructions get deleted re-iterate instead.
100 if (IsSubloopHeader && !isa<PHINode>(I))
104 // Add all successors to the worklist, except for loop exit blocks and the
105 // bodies of subloops. We visit the headers of loops so that we can
107 // their phis, but we contract the rest of the subloop body and only
109 // edges leading back to the original loop.
110 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
112 BasicBlock *SuccBB = *SI;
113 if (!Visited.insert(SuccBB).second)
116 const Loop *SuccLoop = LI->getLoopFor(SuccBB);
117 if (SuccLoop && SuccLoop->getHeader() == SuccBB &&
118 L->contains(SuccLoop)) {
119 VisitStack.push_back(WorklistItem(SuccBB, true));
121 SmallVector<BasicBlock *, 8> SubLoopExitBlocks;
122 SuccLoop->getExitBlocks(SubLoopExitBlocks);
124 for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) {
125 BasicBlock *ExitBB = SubLoopExitBlocks[i];
126 if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB).second)
127 VisitStack.push_back(WorklistItem(ExitBB, false));
134 std::binary_search(ExitBlocks.begin(), ExitBlocks.end(), SuccBB);
138 VisitStack.push_back(WorklistItem(SuccBB, false));
142 // Place the list of instructions to simplify on the next loop iteration
144 std::swap(ToSimplify, Next);
147 Changed |= LocalChanged;
148 } while (LocalChanged);
154 class LoopInstSimplifyLegacyPass : public LoopPass {
156 static char ID; // Pass ID, replacement for typeid
157 LoopInstSimplifyLegacyPass() : LoopPass(ID) {
158 initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
161 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
164 DominatorTreeWrapperPass *DTWP =
165 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
166 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
167 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
168 AssumptionCache *AC =
169 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
170 *L->getHeader()->getParent());
171 const TargetLibraryInfo *TLI =
172 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
174 return SimplifyLoopInst(L, DT, LI, AC, TLI);
177 void getAnalysisUsage(AnalysisUsage &AU) const override {
178 AU.addRequired<AssumptionCacheTracker>();
179 AU.addRequired<TargetLibraryInfoWrapperPass>();
180 AU.setPreservesCFG();
181 getLoopAnalysisUsage(AU);
186 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
187 LoopStandardAnalysisResults &AR,
189 if (!SimplifyLoopInst(&L, &AR.DT, &AR.LI, &AR.AC, &AR.TLI))
190 return PreservedAnalyses::all();
192 return getLoopPassPreservedAnalyses();
195 char LoopInstSimplifyLegacyPass::ID = 0;
196 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
197 "Simplify instructions in loops", false, false)
198 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
199 INITIALIZE_PASS_DEPENDENCY(LoopPass)
200 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
201 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
202 "Simplify instructions in loops", false, false)
204 Pass *llvm::createLoopInstSimplifyPass() {
205 return new LoopInstSimplifyLegacyPass();