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