Coverage Report

Created: 2019-02-20 07:29

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/IntervalPartition.h
Line
Count
Source (jump to first uncovered line)
1
//===- IntervalPartition.h - Interval partition Calculation -----*- 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 contains the declaration of the IntervalPartition class, which
10
// calculates and represents the interval partition of a function, or a
11
// preexisting interval partition.
12
//
13
// In this way, the interval partition may be used to reduce a flow graph down
14
// to its degenerate single node interval partition (unless it is irreducible).
15
//
16
// TODO: The IntervalPartition class should take a bool parameter that tells
17
// whether it should add the "tails" of an interval to an interval itself or if
18
// they should be represented as distinct intervals.
19
//
20
//===----------------------------------------------------------------------===//
21
22
#ifndef LLVM_ANALYSIS_INTERVALPARTITION_H
23
#define LLVM_ANALYSIS_INTERVALPARTITION_H
24
25
#include "llvm/Pass.h"
26
#include <map>
27
#include <vector>
28
29
namespace llvm {
30
31
class BasicBlock;
32
class Interval;
33
34
//===----------------------------------------------------------------------===//
35
//
36
// IntervalPartition - This class builds and holds an "interval partition" for
37
// a function.  This partition divides the control flow graph into a set of
38
// maximal intervals, as defined with the properties above.  Intuitively, an
39
// interval is a (possibly nonexistent) loop with a "tail" of non-looping
40
// nodes following it.
41
//
42
class IntervalPartition : public FunctionPass {
43
  using IntervalMapTy = std::map<BasicBlock *, Interval *>;
44
  IntervalMapTy IntervalMap;
45
46
  using IntervalListTy = std::vector<Interval *>;
47
  Interval *RootInterval = nullptr;
48
  std::vector<Interval *> Intervals;
49
50
public:
51
  static char ID; // Pass identification, replacement for typeid
52
53
0
  IntervalPartition() : FunctionPass(ID) {
54
0
    initializeIntervalPartitionPass(*PassRegistry::getPassRegistry());
55
0
  }
56
57
  // run - Calculate the interval partition for this function
58
  bool runOnFunction(Function &F) override;
59
60
  // IntervalPartition ctor - Build a reduced interval partition from an
61
  // existing interval graph.  This takes an additional boolean parameter to
62
  // distinguish it from a copy constructor.  Always pass in false for now.
63
  IntervalPartition(IntervalPartition &I, bool);
64
65
  // print - Show contents in human readable format...
66
  void print(raw_ostream &O, const Module* = nullptr) const override;
67
68
  // getRootInterval() - Return the root interval that contains the starting
69
  // block of the function.
70
0
  inline Interval *getRootInterval() { return RootInterval; }
71
72
  // isDegeneratePartition() - Returns true if the interval partition contains
73
  // a single interval, and thus cannot be simplified anymore.
74
0
  bool isDegeneratePartition() { return Intervals.size() == 1; }
75
76
  // TODO: isIrreducible - look for triangle graph.
77
78
  // getBlockInterval - Return the interval that a basic block exists in.
79
0
  inline Interval *getBlockInterval(BasicBlock *BB) {
80
0
    IntervalMapTy::iterator I = IntervalMap.find(BB);
81
0
    return I != IntervalMap.end() ? I->second : nullptr;
82
0
  }
83
84
  // getAnalysisUsage - Implement the Pass API
85
0
  void getAnalysisUsage(AnalysisUsage &AU) const override {
86
0
    AU.setPreservesAll();
87
0
  }
88
89
  // Interface to Intervals vector...
90
0
  const std::vector<Interval*> &getIntervals() const { return Intervals; }
91
92
  // releaseMemory - Reset state back to before function was analyzed
93
  void releaseMemory() override;
94
95
private:
96
  // addIntervalToPartition - Add an interval to the internal list of intervals,
97
  // and then add mappings from all of the basic blocks in the interval to the
98
  // interval itself (in the IntervalMap).
99
  void addIntervalToPartition(Interval *I);
100
101
  // updatePredecessors - Interval generation only sets the successor fields of
102
  // the interval data structures.  After interval generation is complete,
103
  // run through all of the intervals and propagate successor info as
104
  // predecessor info.
105
  void updatePredecessors(Interval *Int);
106
};
107
108
} // end namespace llvm
109
110
#endif // LLVM_ANALYSIS_INTERVALPARTITION_H