1//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs lightweight instruction simplification on loop bodies.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Scalar/LoopInstSimplify.h"
14#include "llvm/ADT/PointerIntPair.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/LoopInfo.h"
22#include "llvm/Analysis/LoopIterator.h"
23#include "llvm/Analysis/LoopPass.h"
24#include "llvm/Analysis/MemorySSA.h"
25#include "llvm/Analysis/MemorySSAUpdater.h"
26#include "llvm/Analysis/TargetLibraryInfo.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/CFG.h"
29#include "llvm/IR/DataLayout.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Instruction.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Module.h"
34#include "llvm/IR/PassManager.h"
35#include "llvm/IR/User.h"
36#include "llvm/InitializePasses.h"
37#include "llvm/Pass.h"
38#include "llvm/Support/Casting.h"
39#include "llvm/Transforms/Scalar.h"
40#include "llvm/Transforms/Utils/Local.h"
41#include "llvm/Transforms/Utils/LoopUtils.h"
42#include <algorithm>
43#include <utility>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "loop-instsimplify"
48
49STATISTIC(NumSimplified, "Number of redundant instructions simplified");
50
51static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
52                             AssumptionCache &AC, const TargetLibraryInfo &TLI,
53                             MemorySSAUpdater *MSSAU) {
54  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
55  SimplifyQuery SQ(DL, &TLI, &DT, &AC);
56
57  // On the first pass over the loop body we try to simplify every instruction.
58  // On subsequent passes, we can restrict this to only simplifying instructions
59  // where the inputs have been updated. We end up needing two sets: one
60  // containing the instructions we are simplifying in *this* pass, and one for
61  // the instructions we will want to simplify in the *next* pass. We use
62  // pointers so we can swap between two stably allocated sets.
63  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
64
65  // Track the PHI nodes that have already been visited during each iteration so
66  // that we can identify when it is necessary to iterate.
67  SmallPtrSet<PHINode *, 4> VisitedPHIs;
68
69  // While simplifying we may discover dead code or cause code to become dead.
70  // Keep track of all such instructions and we will delete them at the end.
71  SmallVector<Instruction *, 8> DeadInsts;
72
73  // First we want to create an RPO traversal of the loop body. By processing in
74  // RPO we can ensure that definitions are processed prior to uses (for non PHI
75  // uses) in all cases. This ensures we maximize the simplifications in each
76  // iteration over the loop and minimizes the possible causes for continuing to
77  // iterate.
78  LoopBlocksRPO RPOT(&L);
79  RPOT.perform(&LI);
80  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
81
82  bool Changed = false;
83  for (;;) {
84    if (MSSAU && VerifyMemorySSA)
85      MSSA->verifyMemorySSA();
86    for (BasicBlock *BB : RPOT) {
87      for (Instruction &I : *BB) {
88        if (auto *PI = dyn_cast<PHINode>(&I))
89          VisitedPHIs.insert(PI);
90
91        if (I.use_empty()) {
92          if (isInstructionTriviallyDead(&I, &TLI))
93            DeadInsts.push_back(&I);
94          continue;
95        }
96
97        // We special case the first iteration which we can detect due to the
98        // empty `ToSimplify` set.
99        bool IsFirstIteration = ToSimplify->empty();
100
101        if (!IsFirstIteration && !ToSimplify->count(&I))
102          continue;
103
104        Value *V = SimplifyInstruction(&I, SQ.getWithInstruction(&I));
105        if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
106          continue;
107
108        for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
109             UI != UE;) {
110          Use &U = *UI++;
111          auto *UserI = cast<Instruction>(U.getUser());
112          U.set(V);
113
114          // If the instruction is used by a PHI node we have already processed
115          // we'll need to iterate on the loop body to converge, so add it to
116          // the next set.
117          if (auto *UserPI = dyn_cast<PHINode>(UserI))
118            if (VisitedPHIs.count(UserPI)) {
119              Next->insert(UserPI);
120              continue;
121            }
122
123          // If we are only simplifying targeted instructions and the user is an
124          // instruction in the loop body, add it to our set of targeted
125          // instructions. Because we process defs before uses (outside of PHIs)
126          // we won't have visited it yet.
127          //
128          // We also skip any uses outside of the loop being simplified. Those
129          // should always be PHI nodes due to LCSSA form, and we don't want to
130          // try to simplify those away.
131          assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
132                 "Uses outside the loop should be PHI nodes due to LCSSA!");
133          if (!IsFirstIteration && L.contains(UserI))
134            ToSimplify->insert(UserI);
135        }
136
137        if (MSSAU)
138          if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
139            if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
140              if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
141                MA->replaceAllUsesWith(ReplacementMA);
142
143        assert(I.use_empty() && "Should always have replaced all uses!");
144        if (isInstructionTriviallyDead(&I, &TLI))
145          DeadInsts.push_back(&I);
146        ++NumSimplified;
147        Changed = true;
148      }
149    }
150
151    // Delete any dead instructions found thus far now that we've finished an
152    // iteration over all instructions in all the loop blocks.
153    if (!DeadInsts.empty()) {
154      Changed = true;
155      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
156    }
157
158    if (MSSAU && VerifyMemorySSA)
159      MSSA->verifyMemorySSA();
160
161    // If we never found a PHI that needs to be simplified in the next
162    // iteration, we're done.
163    if (Next->empty())
164      break;
165
166    // Otherwise, put the next set in place for the next iteration and reset it
167    // and the visited PHIs for that iteration.
168    std::swap(Next, ToSimplify);
169    Next->clear();
170    VisitedPHIs.clear();
171    DeadInsts.clear();
172  }
173
174  return Changed;
175}
176
177namespace {
178
179class LoopInstSimplifyLegacyPass : public LoopPass {
180public:
181  static char ID; // Pass ID, replacement for typeid
182
183  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
184    initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
185  }
186
187  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
188    if (skipLoop(L))
189      return false;
190    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
191    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
192    AssumptionCache &AC =
193        getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
194            *L->getHeader()->getParent());
195    const TargetLibraryInfo &TLI =
196        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
197            *L->getHeader()->getParent());
198    MemorySSA *MSSA = nullptr;
199    Optional<MemorySSAUpdater> MSSAU;
200    if (EnableMSSALoopDependency) {
201      MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
202      MSSAU = MemorySSAUpdater(MSSA);
203    }
204
205    return simplifyLoopInst(*L, DT, LI, AC, TLI,
206                            MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
207  }
208
209  void getAnalysisUsage(AnalysisUsage &AU) const override {
210    AU.addRequired<AssumptionCacheTracker>();
211    AU.addRequired<DominatorTreeWrapperPass>();
212    AU.addRequired<TargetLibraryInfoWrapperPass>();
213    AU.setPreservesCFG();
214    if (EnableMSSALoopDependency) {
215      AU.addRequired<MemorySSAWrapperPass>();
216      AU.addPreserved<MemorySSAWrapperPass>();
217    }
218    getLoopAnalysisUsage(AU);
219  }
220};
221
222} // end anonymous namespace
223
224PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
225                                            LoopStandardAnalysisResults &AR,
226                                            LPMUpdater &) {
227  Optional<MemorySSAUpdater> MSSAU;
228  if (AR.MSSA) {
229    MSSAU = MemorySSAUpdater(AR.MSSA);
230    if (VerifyMemorySSA)
231      AR.MSSA->verifyMemorySSA();
232  }
233  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
234                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
235    return PreservedAnalyses::all();
236
237  auto PA = getLoopPassPreservedAnalyses();
238  PA.preserveSet<CFGAnalyses>();
239  if (AR.MSSA)
240    PA.preserve<MemorySSAAnalysis>();
241  return PA;
242}
243
244char LoopInstSimplifyLegacyPass::ID = 0;
245
246INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
247                      "Simplify instructions in loops", false, false)
248INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
249INITIALIZE_PASS_DEPENDENCY(LoopPass)
250INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
251INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
252INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
253                    "Simplify instructions in loops", false, false)
254
255Pass *llvm::createLoopInstSimplifyPass() {
256  return new LoopInstSimplifyLegacyPass();
257}
258