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