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 23namespace llvm { 24 25class MachineBasicBlock; 26class 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. 65class LoopTraversal { 66private: 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 86public: 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 : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} 100 }; 101 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 108private: 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