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