Home | History | Annotate | Download | only in Scalar 
      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 }
    222