llvm/lib/Transforms/Scalar/LoopInstSimplify.cpp

   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/STLExtras.h"
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/Analysis/AssumptionCache.h"
  19 #include "llvm/Analysis/InstructionSimplify.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/LoopIterator.h"
  22 #include "llvm/Analysis/LoopPass.h"
  23 #include "llvm/Analysis/MemorySSA.h"
  24 #include "llvm/Analysis/MemorySSAUpdater.h"
  25 #include "llvm/Analysis/TargetLibraryInfo.h"
  26 #include "llvm/IR/BasicBlock.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/Instruction.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/IR/PassManager.h"
  32 #include "llvm/Support/Casting.h"
  33 #include "llvm/Transforms/Scalar.h"
  34 #include "llvm/Transforms/Utils/Local.h"
  35 #include "llvm/Transforms/Utils/LoopUtils.h"
  36 #include <optional>
  37 #include <utility>
  38
  39 using namespace llvm;
  40
  41 #define DEBUG_TYPE "loop-instsimplify"
  42
  43 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
  44
  45 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
  46                              AssumptionCache &AC, const TargetLibraryInfo &TLI,
  47                              MemorySSAUpdater *MSSAU) {
  48   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
  49   SimplifyQuery SQ(DL, &TLI, &DT, &AC);
  50
  51   // On the first pass over the loop body we try to simplify every instruction.
  52   // On subsequent passes, we can restrict this to only simplifying instructions
  53   // where the inputs have been updated. We end up needing two sets: one
  54   // containing the instructions we are simplifying in *this* pass, and one for
  55   // the instructions we will want to simplify in the *next* pass. We use
  56   // pointers so we can swap between two stably allocated sets.
  57   SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
  58
  59   // Track the PHI nodes that have already been visited during each iteration so
  60   // that we can identify when it is necessary to iterate.
  61   SmallPtrSet<PHINode *, 4> VisitedPHIs;
  62
  63   // While simplifying we may discover dead code or cause code to become dead.
  64   // Keep track of all such instructions and we will delete them at the end.
  65   SmallVector<WeakTrackingVH, 8> DeadInsts;
  66
  67   // First we want to create an RPO traversal of the loop body. By processing in
  68   // RPO we can ensure that definitions are processed prior to uses (for non PHI
  69   // uses) in all cases. This ensures we maximize the simplifications in each
  70   // iteration over the loop and minimizes the possible causes for continuing to
  71   // iterate.
  72   LoopBlocksRPO RPOT(&L);
  73   RPOT.perform(&LI);
  74   MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
  75
  76   bool Changed = false;
  77   for (;;) {
  78     if (MSSAU && VerifyMemorySSA)
  79       MSSA->verifyMemorySSA();
  80     for (BasicBlock *BB : RPOT) {
  81       for (Instruction &I : *BB) {
  82         if (auto *PI = dyn_cast<PHINode>(&I))
  83           VisitedPHIs.insert(PI);
  84
  85         if (I.use_empty()) {
  86           if (isInstructionTriviallyDead(&I, &TLI))
  87             DeadInsts.push_back(&I);
  88           continue;
  89         }
  90
  91         // We special case the first iteration which we can detect due to the
  92         // empty `ToSimplify` set.
  93         bool IsFirstIteration = ToSimplify->empty();
  94
  95         if (!IsFirstIteration && !ToSimplify->count(&I))
  96           continue;
  97
  98         Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I));
  99         if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
 100           continue;
 101
 102         for (Use &U : llvm::make_early_inc_range(I.uses())) {
 103           auto *UserI = cast<Instruction>(U.getUser());
 104           U.set(V);
 105
 106           // Do not bother dealing with unreachable code.
 107           if (!DT.isReachableFromEntry(UserI->getParent()))
 108             continue;
 109
 110           // If the instruction is used by a PHI node we have already processed
 111           // we'll need to iterate on the loop body to converge, so add it to
 112           // the next set.
 113           if (auto *UserPI = dyn_cast<PHINode>(UserI))
 114             if (VisitedPHIs.count(UserPI)) {
 115               Next->insert(UserPI);
 116               continue;
 117             }
 118
 119           // If we are only simplifying targeted instructions and the user is an
 120           // instruction in the loop body, add it to our set of targeted
 121           // instructions. Because we process defs before uses (outside of PHIs)
 122           // we won't have visited it yet.
 123           //
 124           // We also skip any uses outside of the loop being simplified. Those
 125           // should always be PHI nodes due to LCSSA form, and we don't want to
 126           // try to simplify those away.
 127           assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
 128                  "Uses outside the loop should be PHI nodes due to LCSSA!");
 129           if (!IsFirstIteration && L.contains(UserI))
 130             ToSimplify->insert(UserI);
 131         }
 132
 133         if (MSSAU)
 134           if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
 135             if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
 136               if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
 137                 MA->replaceAllUsesWith(ReplacementMA);
 138
 139         assert(I.use_empty() && "Should always have replaced all uses!");
 140         if (isInstructionTriviallyDead(&I, &TLI))
 141           DeadInsts.push_back(&I);
 142         ++NumSimplified;
 143         Changed = true;
 144       }
 145     }
 146
 147     // Delete any dead instructions found thus far now that we've finished an
 148     // iteration over all instructions in all the loop blocks.
 149     if (!DeadInsts.empty()) {
 150       Changed = true;
 151       RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
 152     }
 153
 154     if (MSSAU && VerifyMemorySSA)
 155       MSSA->verifyMemorySSA();
 156
 157     // If we never found a PHI that needs to be simplified in the next
 158     // iteration, we're done.
 159     if (Next->empty())
 160       break;
 161
 162     // Otherwise, put the next set in place for the next iteration and reset it
 163     // and the visited PHIs for that iteration.
 164     std::swap(Next, ToSimplify);
 165     Next->clear();
 166     VisitedPHIs.clear();
 167     DeadInsts.clear();
 168   }
 169
 170   return Changed;
 171 }
 172
 173 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
 174                                             LoopStandardAnalysisResults &AR,
 175                                             LPMUpdater &) {
 176   std::optional<MemorySSAUpdater> MSSAU;
 177   if (AR.MSSA) {
 178     MSSAU = MemorySSAUpdater(AR.MSSA);
 179     if (VerifyMemorySSA)
 180       AR.MSSA->verifyMemorySSA();
 181   }
 182   if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
 183                         MSSAU ? &*MSSAU : nullptr))
 184     return PreservedAnalyses::all();
 185
 186   auto PA = getLoopPassPreservedAnalyses();
 187   PA.preserveSet<CFGAnalyses>();
 188   if (AR.MSSA)
 189     PA.preserve<MemorySSAAnalysis>();
 190   return PA;
 191 }