contrib/llvm/lib/Transforms/Scalar/LoopInstSimplify.cpp

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