1 //==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- C++ -*---------==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 /// \file Loop Traversal logic. 11 /// 12 /// This class provides the basic blocks traversal order used by passes like 13 /// ReachingDefAnalysis and ExecutionDomainFix. 14 /// It identifies basic blocks that are part of loops and should to be visited 15 /// twice and returns efficient traversal order for all the blocks. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H 20 #define LLVM_CODEGEN_LOOPTRAVERSAL_H 21 22 #include "llvm/ADT/SmallVector.h" 23 24 namespace llvm { 25 26 class MachineBasicBlock; 27 class MachineFunction; 28 29 /// This class provides the basic blocks traversal order used by passes like 30 /// ReachingDefAnalysis and ExecutionDomainFix. 31 /// It identifies basic blocks that are part of loops and should to be visited 32 /// twice and returns efficient traversal order for all the blocks. 33 /// 34 /// We want to visit every instruction in every basic block in order to update 35 /// it's execution domain or collect clearance information. However, for the 36 /// clearance calculation, we need to know clearances from all predecessors 37 /// (including any backedges), therfore we need to visit some blocks twice. 38 /// As an example, consider the following loop. 39 /// 40 /// 41 /// PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT 42 /// ^ | 43 /// +----------------------------------+ 44 /// 45 /// The iteration order this pass will return is as follows: 46 /// Optimized: PH A B C A' B' C' D 47 /// 48 /// The basic block order is constructed as follows: 49 /// Once we finish processing some block, we update the counters in MBBInfos 50 /// and re-process any successors that are now 'done'. 51 /// We call a block that is ready for its final round of processing `done` 52 /// (isBlockDone), e.g. when all predecessor information is known. 53 /// 54 /// Note that a naive traversal order would be to do two complete passes over 55 /// all basic blocks/instructions, the first for recording clearances, the 56 /// second for updating clearance based on backedges. 57 /// However, for functions without backedges, or functions with a lot of 58 /// straight-line code, and a small loop, that would be a lot of unnecessary 59 /// work (since only the BBs that are part of the loop require two passes). 60 /// 61 /// E.g., the naive iteration order for the above exmple is as follows: 62 /// Naive: PH A B C D A' B' C' D' 63 /// 64 /// In the optimized approach we avoid processing D twice, because we 65 /// can entirely process the predecessors before getting to D. 66 class LoopTraversal { 67 private: 68 struct MBBInfo { 69 /// Whether we have gotten to this block in primary processing yet. 70 bool PrimaryCompleted = false; 71 72 /// The number of predecessors for which primary processing has completed 73 unsigned IncomingProcessed = 0; 74 75 /// The value of `IncomingProcessed` at the start of primary processing 76 unsigned PrimaryIncoming = 0; 77 78 /// The number of predecessors for which all processing steps are done. 79 unsigned IncomingCompleted = 0; 80 81 MBBInfo() = default; 82 }; 83 using MBBInfoMap = SmallVector<MBBInfo, 4>; 84 /// Helps keep track if we proccessed this block and all its predecessors. 85 MBBInfoMap MBBInfos; 86 87 public: 88 struct TraversedMBBInfo { 89 /// The basic block. 90 MachineBasicBlock *MBB = nullptr; 91 92 /// True if this is the first time we process the basic block. 93 bool PrimaryPass = true; 94 95 /// True if the block that is ready for its final round of processing. 96 bool IsDone = true; 97 98 TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true, 99 bool Done = true) MBBTraversedMBBInfo100 : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} 101 }; LoopTraversal()102 LoopTraversal() {} 103 104 /// Identifies basic blocks that are part of loops and should to be 105 /// visited twice and returns efficient traversal order for all the blocks. 106 typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder; 107 TraversalOrder traverse(MachineFunction &MF); 108 109 private: 110 /// Returens true if the block is ready for its final round of processing. 111 bool isBlockDone(MachineBasicBlock *MBB); 112 }; 113 114 } // namespace llvm 115 116 #endif // LLVM_CODEGEN_LOOPTRAVERSAL_H 117