Line data    Source code

       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      834628 :         : 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