Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h
Line
Count
Source
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
10.8k
      : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
53
10.8k
      IterationNumber = SE.getConstant(APInt(64, Iteration));
54
10.8k
  }
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
467k
  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