Coverage Report

Created: 2019-07-24 05:18

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