1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
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 pass performs lightweight instruction simplification on loop bodies.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Transforms/Scalar/LoopInstSimplify.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/Analysis/LoopPassManager.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/Utils/Local.h"
29 #include "llvm/Transforms/Utils/LoopUtils.h"
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "loop-instsimplify"
33 
34 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
35 
36 static bool SimplifyLoopInst(Loop *L, DominatorTree *DT, LoopInfo *LI,
37                              const TargetLibraryInfo *TLI) {
38   SmallVector<BasicBlock *, 8> ExitBlocks;
39   L->getUniqueExitBlocks(ExitBlocks);
40   array_pod_sort(ExitBlocks.begin(), ExitBlocks.end());
41 
42   SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
43 
44   // The bit we are stealing from the pointer represents whether this basic
45   // block is the header of a subloop, in which case we only process its phis.
46   typedef PointerIntPair<BasicBlock *, 1> WorklistItem;
47   SmallVector<WorklistItem, 16> VisitStack;
48   SmallPtrSet<BasicBlock *, 32> Visited;
49 
50   bool Changed = false;
51   bool LocalChanged;
52   do {
53     LocalChanged = false;
54 
55     VisitStack.clear();
56     Visited.clear();
57 
58     VisitStack.push_back(WorklistItem(L->getHeader(), false));
59 
60     while (!VisitStack.empty()) {
61       WorklistItem Item = VisitStack.pop_back_val();
62       BasicBlock *BB = Item.getPointer();
63       bool IsSubloopHeader = Item.getInt();
64       const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
65 
66       // Simplify instructions in the current basic block.
67       for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
68         Instruction *I = &*BI++;
69 
70         // The first time through the loop ToSimplify is empty and we try to
71         // simplify all instructions. On later iterations ToSimplify is not
72         // empty and we only bother simplifying instructions that are in it.
73         if (!ToSimplify->empty() && !ToSimplify->count(I))
74           continue;
75 
76         // Don't bother simplifying unused instructions.
77         if (!I->use_empty()) {
78           Value *V = SimplifyInstruction(I, DL, TLI, DT);
79           if (V && LI->replacementPreservesLCSSAForm(I, V)) {
80             // Mark all uses for resimplification next time round the loop.
81             for (User *U : I->users())
82               Next->insert(cast<Instruction>(U));
83 
84             I->replaceAllUsesWith(V);
85             LocalChanged = true;
86             ++NumSimplified;
87           }
88         }
89         if (RecursivelyDeleteTriviallyDeadInstructions(I, TLI)) {
90           // RecursivelyDeleteTriviallyDeadInstruction can remove more than one
91           // instruction, so simply incrementing the iterator does not work.
92           // When instructions get deleted re-iterate instead.
93           BI = BB->begin();
94           BE = BB->end();
95           LocalChanged = true;
96         }
97 
98         if (IsSubloopHeader && !isa<PHINode>(I))
99           break;
100       }
101 
102       // Add all successors to the worklist, except for loop exit blocks and the
103       // bodies of subloops. We visit the headers of loops so that we can
104       // process
105       // their phis, but we contract the rest of the subloop body and only
106       // follow
107       // edges leading back to the original loop.
108       for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
109            ++SI) {
110         BasicBlock *SuccBB = *SI;
111         if (!Visited.insert(SuccBB).second)
112           continue;
113 
114         const Loop *SuccLoop = LI->getLoopFor(SuccBB);
115         if (SuccLoop && SuccLoop->getHeader() == SuccBB &&
116             L->contains(SuccLoop)) {
117           VisitStack.push_back(WorklistItem(SuccBB, true));
118 
119           SmallVector<BasicBlock *, 8> SubLoopExitBlocks;
120           SuccLoop->getExitBlocks(SubLoopExitBlocks);
121 
122           for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) {
123             BasicBlock *ExitBB = SubLoopExitBlocks[i];
124             if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB).second)
125               VisitStack.push_back(WorklistItem(ExitBB, false));
126           }
127 
128           continue;
129         }
130 
131         bool IsExitBlock =
132             std::binary_search(ExitBlocks.begin(), ExitBlocks.end(), SuccBB);
133         if (IsExitBlock)
134           continue;
135 
136         VisitStack.push_back(WorklistItem(SuccBB, false));
137       }
138     }
139 
140     // Place the list of instructions to simplify on the next loop iteration
141     // into ToSimplify.
142     std::swap(ToSimplify, Next);
143     Next->clear();
144 
145     Changed |= LocalChanged;
146   } while (LocalChanged);
147 
148   return Changed;
149 }
150 
151 namespace {
152 class LoopInstSimplifyLegacyPass : public LoopPass {
153 public:
154   static char ID; // Pass ID, replacement for typeid
155   LoopInstSimplifyLegacyPass() : LoopPass(ID) {
156     initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
157   }
158 
159   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
160     if (skipLoop(L))
161       return false;
162     DominatorTreeWrapperPass *DTWP =
163         getAnalysisIfAvailable<DominatorTreeWrapperPass>();
164     DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
165     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
166     const TargetLibraryInfo *TLI =
167         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
168 
169     return SimplifyLoopInst(L, DT, LI, TLI);
170   }
171 
172   void getAnalysisUsage(AnalysisUsage &AU) const override {
173     AU.addRequired<TargetLibraryInfoWrapperPass>();
174     AU.setPreservesCFG();
175     getLoopAnalysisUsage(AU);
176   }
177 };
178 }
179 
180 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L,
181                                             LoopAnalysisManager &AM) {
182   const auto &FAM =
183       AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
184   Function *F = L.getHeader()->getParent();
185 
186   // Use getCachedResult because Loop pass cannot trigger a function analysis.
187   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F);
188   auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
189   const auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(*F);
190   assert((LI && TLI) && "Analyses for Loop Inst Simplify not available");
191 
192   if (!SimplifyLoopInst(&L, DT, LI, TLI))
193     return PreservedAnalyses::all();
194 
195   return getLoopPassPreservedAnalyses();
196 }
197 
198 char LoopInstSimplifyLegacyPass::ID = 0;
199 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
200                       "Simplify instructions in loops", false, false)
201 INITIALIZE_PASS_DEPENDENCY(LoopPass)
202 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
203 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
204                     "Simplify instructions in loops", false, false)
205 
206 Pass *llvm::createLoopInstSimplifyPass() {
207   return new LoopInstSimplifyLegacyPass();
208 }
209