LLVM  10.0.0svn
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 
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.
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  };
83  /// Helps keep track if we proccessed this block and all its predecessors.
84  MBBInfoMap MBBInfos;
85 
86 public:
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  };
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.
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SmallVector< TraversedMBBInfo, 4 > TraversalOrder
Identifies basic blocks that are part of loops and should to be visited twice and returns efficient t...
TraversalOrder traverse(MachineFunction &MF)
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
TraversedMBBInfo(MachineBasicBlock *BB=nullptr, bool Primary=true, bool Done=true)
Definition: LoopTraversal.h:97