contrib/llvm/include/llvm/CodeGen/LoopTraversal.h

   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)
 100         : MBB(BB), PrimaryPass(Primary), IsDone(Done) {}
 101   };
 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