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) MBBTraversedMBBInfo99 : 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