Coverage Report

Created: 2018-07-18 22:01

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/LoopTraversal.h
Line
Count
Source
1
//==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- 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
/// \file Loop Traversal logic.
11
///
12
/// This class provides the basic blocks traversal order used by passes like
13
/// ReachingDefAnalysis and ExecutionDomainFix.
14
/// It identifies basic blocks that are part of loops and should to be visited
15
/// twice and returns efficient traversal order for all the blocks.
16
//
17
//===----------------------------------------------------------------------===//
18
19
#ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H
20
#define LLVM_CODEGEN_LOOPTRAVERSAL_H
21
22
#include "llvm/ADT/SmallVector.h"
23
24
namespace llvm {
25
26
class MachineBasicBlock;
27
class MachineFunction;
28
29
/// This class provides the basic blocks traversal order used by passes like
30
/// ReachingDefAnalysis and ExecutionDomainFix.
31
/// It identifies basic blocks that are part of loops and should to be visited
32
/// twice and returns efficient traversal order for all the blocks.
33
///
34
/// We want to visit every instruction in every basic block in order to update
35
/// it's execution domain or collect clearance information. However, for the
36
/// clearance calculation, we need to know clearances from all predecessors
37
/// (including any backedges), therfore we need to visit some blocks twice.
38
/// As an example, consider the following loop.
39
///
40
///
41
///    PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
42
///          ^                                  |
43
///          +----------------------------------+
44
///
45
/// The iteration order this pass will return is as follows:
46
/// Optimized: PH A B C A' B' C' D
47
///
48
/// The basic block order is constructed as follows:
49
/// Once we finish processing some block, we update the counters in MBBInfos
50
/// and re-process any successors that are now 'done'.
51
/// We call a block that is ready for its final round of processing `done`
52
/// (isBlockDone), e.g. when all predecessor information is known.
53
///
54
/// Note that a naive traversal order would be to do two complete passes over
55
/// all basic blocks/instructions, the first for recording clearances, the
56
/// second for updating clearance based on backedges.
57
/// However, for functions without backedges, or functions with a lot of
58
/// straight-line code, and a small loop, that would be a lot of unnecessary
59
/// work (since only the BBs that are part of the loop require two passes).
60
///
61
/// E.g., the naive iteration order for the above exmple is as follows:
62
/// Naive: PH A B C D A' B' C' D'
63
///
64
/// In the optimized approach we avoid processing D twice, because we
65
/// can entirely process the predecessors before getting to D.
66
class LoopTraversal {
67
private:
68
  struct MBBInfo {
69
    /// Whether we have gotten to this block in primary processing yet.
70
    bool PrimaryCompleted = false;
71
72
    /// The number of predecessors for which primary processing has completed
73
    unsigned IncomingProcessed = 0;
74
75
    /// The value of `IncomingProcessed` at the start of primary processing
76
    unsigned PrimaryIncoming = 0;
77
78
    /// The number of predecessors for which all processing steps are done.
79
    unsigned IncomingCompleted = 0;
80
81
256k
    MBBInfo() = default;
82
  };
83
  using MBBInfoMap = SmallVector<MBBInfo, 4>;
84
  /// Helps keep track if we proccessed this block and all its predecessors.
85
  MBBInfoMap MBBInfos;
86
87
public:
88
  struct TraversedMBBInfo {
89
    /// The basic block.
90
    MachineBasicBlock *MBB = nullptr;
91
92
    /// True if this is the first time we process the basic block.
93
    bool PrimaryPass = true;
94
95
    /// True if the block that is ready for its final round of processing.
96
    bool IsDone = true;
97
98
    TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true,
99
                     bool Done = true)
100
1.07M
        : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
101
  };
102
256k
  LoopTraversal() {}
103
104
  /// Identifies basic blocks that are part of loops and should to be
105
  ///  visited twice and returns efficient traversal order for all the blocks.
106
  typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder;
107
  TraversalOrder traverse(MachineFunction &MF);
108
109
private:
110
  /// Returens true if the block is ready for its final round of processing.
111
  bool isBlockDone(MachineBasicBlock *MBB);
112
};
113
114
} // namespace llvm
115
116
#endif // LLVM_CODEGEN_LOOPTRAVERSAL_H