contrib/llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h

   1 //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===//
   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 file implements UnrolledInstAnalyzer class. It's used for predicting
  11 // potential effects that loop unrolling might have, such as enabling constant
  12 // propagation and other optimizations.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
  17 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
  18
  19 #include "llvm/Analysis/InstructionSimplify.h"
  20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  21 #include "llvm/IR/InstVisitor.h"
  22
  23 // This class is used to get an estimate of the optimization effects that we
  24 // could get from complete loop unrolling. It comes from the fact that some
  25 // loads might be replaced with concrete constant values and that could trigger
  26 // a chain of instruction simplifications.
  27 //
  28 // E.g. we might have:
  29 //   int a[] = {0, 1, 0};
  30 //   v = 0;
  31 //   for (i = 0; i < 3; i ++)
  32 //     v += b[i]*a[i];
  33 // If we completely unroll the loop, we would get:
  34 //   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
  35 // Which then will be simplified to:
  36 //   v = b[0]* 0 + b[1]* 1 + b[2]* 0
  37 // And finally:
  38 //   v = b[1]
  39 namespace llvm {
  40 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
  41   typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
  42   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
  43   struct SimplifiedAddress {
  44     Value *Base = nullptr;
  45     ConstantInt *Offset = nullptr;
  46   };
  47
  48 public:
  49   UnrolledInstAnalyzer(unsigned Iteration,
  50                        DenseMap<Value *, Constant *> &SimplifiedValues,
  51                        ScalarEvolution &SE, const Loop *L)
  52       : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
  53       IterationNumber = SE.getConstant(APInt(64, Iteration));
  54   }
  55
  56   // Allow access to the initial visit method.
  57   using Base::visit;
  58
  59 private:
  60   /// \brief A cache of pointer bases and constant-folded offsets corresponding
  61   /// to GEP (or derived from GEP) instructions.
  62   ///
  63   /// In order to find the base pointer one needs to perform non-trivial
  64   /// traversal of the corresponding SCEV expression, so it's good to have the
  65   /// results saved.
  66   DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
  67
  68   /// \brief SCEV expression corresponding to number of currently simulated
  69   /// iteration.
  70   const SCEV *IterationNumber;
  71
  72   /// \brief A Value->Constant map for keeping values that we managed to
  73   /// constant-fold on the given iteration.
  74   ///
  75   /// While we walk the loop instructions, we build up and maintain a mapping
  76   /// of simplified values specific to this iteration.  The idea is to propagate
  77   /// any special information we have about loads that can be replaced with
  78   /// constants after complete unrolling, and account for likely simplifications
  79   /// post-unrolling.
  80   DenseMap<Value *, Constant *> &SimplifiedValues;
  81
  82   ScalarEvolution &SE;
  83   const Loop *L;
  84
  85   bool simplifyInstWithSCEV(Instruction *I);
  86
  87   bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
  88   bool visitBinaryOperator(BinaryOperator &I);
  89   bool visitLoad(LoadInst &I);
  90   bool visitCastInst(CastInst &I);
  91   bool visitCmpInst(CmpInst &I);
  92   bool visitPHINode(PHINode &PN);
  93 };
  94 }
  95 #endif