llvm/CodeGen/LoopTraversal.h

0001 //==------ llvm/CodeGen/LoopTraversal.h - Loop Traversal -*- C++ -*---------==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 /// \file Loop Traversal logic.
0010 ///
0011 /// This class provides the basic blocks traversal order used by passes like
0012 /// ReachingDefAnalysis and ExecutionDomainFix.
0013 /// It identifies basic blocks that are part of loops and should to be visited
0014 /// twice and returns efficient traversal order for all the blocks.
0015 //
0016 //===----------------------------------------------------------------------===//
0017
0018 #ifndef LLVM_CODEGEN_LOOPTRAVERSAL_H
0019 #define LLVM_CODEGEN_LOOPTRAVERSAL_H
0020
0021 #include "llvm/ADT/SmallVector.h"
0022
0023 namespace llvm {
0024
0025 class MachineBasicBlock;
0026 class MachineFunction;
0027
0028 /// This class provides the basic blocks traversal order used by passes like
0029 /// ReachingDefAnalysis and ExecutionDomainFix.
0030 /// It identifies basic blocks that are part of loops and should to be visited
0031 /// twice and returns efficient traversal order for all the blocks.
0032 ///
0033 /// We want to visit every instruction in every basic block in order to update
0034 /// it's execution domain or collect clearance information. However, for the
0035 /// clearance calculation, we need to know clearances from all predecessors
0036 /// (including any backedges), therfore we need to visit some blocks twice.
0037 /// As an example, consider the following loop.
0038 ///
0039 ///
0040 ///    PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
0041 ///          ^                                  |
0042 ///          +----------------------------------+
0043 ///
0044 /// The iteration order this pass will return is as follows:
0045 /// Optimized: PH A B C A' B' C' D
0046 ///
0047 /// The basic block order is constructed as follows:
0048 /// Once we finish processing some block, we update the counters in MBBInfos
0049 /// and re-process any successors that are now 'done'.
0050 /// We call a block that is ready for its final round of processing `done`
0051 /// (isBlockDone), e.g. when all predecessor information is known.
0052 ///
0053 /// Note that a naive traversal order would be to do two complete passes over
0054 /// all basic blocks/instructions, the first for recording clearances, the
0055 /// second for updating clearance based on backedges.
0056 /// However, for functions without backedges, or functions with a lot of
0057 /// straight-line code, and a small loop, that would be a lot of unnecessary
0058 /// work (since only the BBs that are part of the loop require two passes).
0059 ///
0060 /// E.g., the naive iteration order for the above exmple is as follows:
0061 /// Naive: PH A B C D A' B' C' D'
0062 ///
0063 /// In the optimized approach we avoid processing D twice, because we
0064 /// can entirely process the predecessors before getting to D.
0065 class LoopTraversal {
0066 private:
0067   struct MBBInfo {
0068     /// Whether we have gotten to this block in primary processing yet.
0069     bool PrimaryCompleted = false;
0070
0071     /// The number of predecessors for which primary processing has completed
0072     unsigned IncomingProcessed = 0;
0073
0074     /// The value of `IncomingProcessed` at the start of primary processing
0075     unsigned PrimaryIncoming = 0;
0076
0077     /// The number of predecessors for which all processing steps are done.
0078     unsigned IncomingCompleted = 0;
0079
0080     MBBInfo() = default;
0081   };
0082   using MBBInfoMap = SmallVector<MBBInfo, 4>;
0083   /// Helps keep track if we proccessed this block and all its predecessors.
0084   MBBInfoMap MBBInfos;
0085
0086 public:
0087   struct TraversedMBBInfo {
0088     /// The basic block.
0089     MachineBasicBlock *MBB = nullptr;
0090
0091     /// True if this is the first time we process the basic block.
0092     bool PrimaryPass = true;
0093
0094     /// True if the block that is ready for its final round of processing.
0095     bool IsDone = true;
0096
0097     TraversedMBBInfo(MachineBasicBlock *BB = nullptr, bool Primary = true,
0098                      bool Done = true)
0099         : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
0100   };
0101   LoopTraversal() = default;
0102
0103   /// Identifies basic blocks that are part of loops and should to be
0104   ///  visited twice and returns efficient traversal order for all the blocks.
0105   typedef SmallVector<TraversedMBBInfo, 4> TraversalOrder;
0106   TraversalOrder traverse(MachineFunction &MF);
0107
0108 private:
0109   /// Returens true if the block is ready for its final round of processing.
0110   bool isBlockDone(MachineBasicBlock *MBB);
0111 };
0112
0113 } // namespace llvm
0114
0115 #endif // LLVM_CODEGEN_LOOPTRAVERSAL_H