LLVM  14.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 
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.
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
llvm::LoopTraversal::TraversedMBBInfo::PrimaryPass
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVector< MBBInfo, 4 >
llvm::LoopTraversal
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::LoopTraversal::TraversedMBBInfo::TraversedMBBInfo
TraversedMBBInfo(MachineBasicBlock *BB=nullptr, bool Primary=true, bool Done=true)
Definition: LoopTraversal.h:97
llvm::LoopTraversal::traverse
TraversalOrder traverse(MachineFunction &MF)
Definition: LoopTraversal.cpp:24
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LoopTraversal::LoopTraversal
LoopTraversal()
Definition: LoopTraversal.h:101
llvm::LoopTraversal::TraversedMBBInfo::IsDone
bool IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
llvm::LoopTraversal::TraversedMBBInfo::MBB
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
SmallVector.h
llvm::LoopTraversal::TraversalOrder
SmallVector< TraversedMBBInfo, 4 > TraversalOrder
Identifies basic blocks that are part of loops and should to be visited twice and returns efficient t...
Definition: LoopTraversal.h:105
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::LoopTraversal::TraversedMBBInfo
Definition: LoopTraversal.h:87