LLVM  10.0.0svn
LoopUnrollAnalyzer.h
Go to the documentation of this file.
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 
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> {
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
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
Base class for instruction visitors.
Definition: InstVisitor.h:80
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The main scalar evolution driver.
An instruction for reading from memory.
Definition: Instructions.h:169
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:439
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:89
UnrolledInstAnalyzer(unsigned Iteration, DenseMap< Value *, Constant *> &SimplifiedValues, ScalarEvolution &SE, const Loop *L)
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
Class for arbitrary precision integers.
Definition: APInt.h:69
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:74