Coverage Report

Created: 2019-07-24 05:18

/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
// 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
10.8k
      : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
52
10.8k
      IterationNumber = SE.getConstant(APInt(64, Iteration));
53
10.8k
  }
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
469k
  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