1336809Sdim//==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- C++ -*---------==// 2336809Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336809Sdim// 7336809Sdim//===----------------------------------------------------------------------===// 8336809Sdim// 9336809Sdim/// \file Loop Traversal logic. 10336809Sdim/// 11336809Sdim/// This class provides the basic blocks traversal order used by passes like 12336809Sdim/// ReachingDefAnalysis and ExecutionDomainFix. 13336809Sdim/// It identifies basic blocks that are part of loops and should to be visited 14336809Sdim/// twice and returns efficient traversal order for all the blocks. 15336809Sdim// 16336809Sdim//===----------------------------------------------------------------------===// 17336809Sdim 18336809Sdim#ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H 19336809Sdim#define LLVM_CODEGEN_LOOPTRAVERSAL_H 20336809Sdim 21336809Sdim#include "llvm/ADT/SmallVector.h" 22336809Sdim 23336809Sdimnamespace llvm { 24336809Sdim 25336809Sdimclass MachineBasicBlock; 26336809Sdimclass MachineFunction; 27336809Sdim 28336809Sdim/// This class provides the basic blocks traversal order used by passes like 29336809Sdim/// ReachingDefAnalysis and ExecutionDomainFix. 30336809Sdim/// It identifies basic blocks that are part of loops and should to be visited 31336809Sdim/// twice and returns efficient traversal order for all the blocks. 32336809Sdim/// 33336809Sdim/// We want to visit every instruction in every basic block in order to update 34336809Sdim/// it's execution domain or collect clearance information. However, for the 35336809Sdim/// clearance calculation, we need to know clearances from all predecessors 36336809Sdim/// (including any backedges), therfore we need to visit some blocks twice. 37336809Sdim/// As an example, consider the following loop. 38336809Sdim/// 39336809Sdim/// 40336809Sdim/// PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT 41336809Sdim/// ^ | 42336809Sdim/// +----------------------------------+ 43336809Sdim/// 44336809Sdim/// The iteration order this pass will return is as follows: 45336809Sdim/// Optimized: PH A B C A' B' C' D 46336809Sdim/// 47336809Sdim/// The basic block order is constructed as follows: 48336809Sdim/// Once we finish processing some block, we update the counters in MBBInfos 49336809Sdim/// and re-process any successors that are now 'done'. 50336809Sdim/// We call a block that is ready for its final round of processing `done` 51336809Sdim/// (isBlockDone), e.g. when all predecessor information is known. 52336809Sdim/// 53336809Sdim/// Note that a naive traversal order would be to do two complete passes over 54336809Sdim/// all basic blocks/instructions, the first for recording clearances, the 55336809Sdim/// second for updating clearance based on backedges. 56336809Sdim/// However, for functions without backedges, or functions with a lot of 57336809Sdim/// straight-line code, and a small loop, that would be a lot of unnecessary 58336809Sdim/// work (since only the BBs that are part of the loop require two passes). 59336809Sdim/// 60336809Sdim/// E.g., the naive iteration order for the above exmple is as follows: 61336809Sdim/// Naive: PH A B C D A' B' C' D' 62336809Sdim/// 63336809Sdim/// In the optimized approach we avoid processing D twice, because we 64336809Sdim/// can entirely process the predecessors before getting to D. 65336809Sdimclass LoopTraversal { 66336809Sdimprivate: 67336809Sdim struct MBBInfo { 68336809Sdim /// Whether we have gotten to this block in primary processing yet. 69336809Sdim bool PrimaryCompleted = false; 70336809Sdim 71336809Sdim /// The number of predecessors for which primary processing has completed 72336809Sdim unsigned IncomingProcessed = 0; 73336809Sdim 74336809Sdim /// The value of `IncomingProcessed` at the start of primary processing 75336809Sdim unsigned PrimaryIncoming = 0; 76336809Sdim 77336809Sdim /// The number of predecessors for which all processing steps are done. 78336809Sdim unsigned IncomingCompleted = 0; 79336809Sdim 80336809Sdim MBBInfo() = default; 81336809Sdim }; 82336809Sdim using MBBInfoMap = SmallVector<MBBInfo, 4>; 83336809Sdim /// Helps keep track if we proccessed this block and all its predecessors. 84336809Sdim MBBInfoMap MBBInfos; 85336809Sdim 86336809Sdimpublic: 87336809Sdim struct TraversedMBBInfo { 88336809Sdim /// The basic block. 89336809Sdim MachineBasicBlock *MBB = nullptr; 90336809Sdim 91336809Sdim /// True if this is the first time we process the basic block. 92336809Sdim bool PrimaryPass = true; 93336809Sdim 94336809Sdim /// True if the block that is ready for its final round of processing. 95336809Sdim bool IsDone = true; 96336809Sdim 97336809Sdim TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true, 98336809Sdim bool Done = true) 99336809Sdim : MBB(BB), PrimaryPass(Primary), IsDone(Done) {} 100336809Sdim }; 101336809Sdim LoopTraversal() {} 102336809Sdim 103336809Sdim /// Identifies basic blocks that are part of loops and should to be 104336809Sdim /// visited twice and returns efficient traversal order for all the blocks. 105336809Sdim typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder; 106336809Sdim TraversalOrder traverse(MachineFunction &MF); 107336809Sdim 108336809Sdimprivate: 109336809Sdim /// Returens true if the block is ready for its final round of processing. 110336809Sdim bool isBlockDone(MachineBasicBlock *MBB); 111336809Sdim}; 112336809Sdim 113336809Sdim} // namespace llvm 114336809Sdim 115336809Sdim#endif // LLVM_CODEGEN_LOOPTRAVERSAL_H 116