include/llvm/Analysis/LoopUnrollAnalyzer.h

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