include/llvm/CodeGen/LoopTraversal.h

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