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]
39namespace llvm {
40class 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
48public:
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
59private:
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
96