Line data    Source code

       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         108 : 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        6774 :   UnrolledInstAnalyzer(unsigned Iteration,
      50             :                        DenseMap<Value *, Constant *> &SimplifiedValues,
      51             :                        ScalarEvolution &SE, const Loop *L)
      52        6774 :       : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
      53        6774 :       IterationNumber = SE.getConstant(APInt(64, Iteration));
      54        6774 :   }
      55             : 
      56             :   // Allow access to the initial visit method.
      57             :   using Base::visit;
      58             : 
      59             : private:
      60             :   /// 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             :   /// SCEV expression corresponding to number of currently simulated
      69             :   /// iteration.
      70             :   const SCEV *IterationNumber;
      71             : 
      72             :   /// 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       40637 :   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