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 | 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 | : 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. |
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 |
116 | |