LLVM 20.0.0git
LoopTraversal.h
Go to the documentation of this file.
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
22
23namespace llvm {
24
25class MachineBasicBlock;
26class 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.
66private:
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 MBBInfo() = default;
81 };
83 /// Helps keep track if we proccessed this block and all its predecessors.
84 MBBInfoMap MBBInfos;
85
86public:
88 /// The basic block.
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 : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
100 };
101 LoopTraversal() = default;
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.
107
108private:
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
MachineBasicBlock & MBB
This file defines the SmallVector class.
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
LoopTraversal()=default
TraversalOrder traverse(MachineFunction &MF)
SmallVector< TraversedMBBInfo, 4 > TraversalOrder
Identifies basic blocks that are part of loops and should to be visited twice and returns efficient t...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Done
Definition: Threading.h:61
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
bool IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
TraversedMBBInfo(MachineBasicBlock *BB=nullptr, bool Primary=true, bool Done=true)
Definition: LoopTraversal.h:97
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92