/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 | 268k | 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.07M | : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} |
100 | | }; |
101 | 268k | 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 |