contrib/llvm/include/llvm/Analysis/CFG.h

   1 //===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- 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 // This family of functions performs analyses on basic blocks, and instructions
  11 // contained within basic blocks.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_CFG_H
  16 #define LLVM_ANALYSIS_CFG_H
  17
  18 #include "llvm/IR/BasicBlock.h"
  19 #include "llvm/IR/CFG.h"
  20
  21 namespace llvm {
  22
  23 class BasicBlock;
  24 class DominatorTree;
  25 class Function;
  26 class Instruction;
  27 class LoopInfo;
  28
  29 /// Analyze the specified function to find all of the loop backedges in the
  30 /// function and return them.  This is a relatively cheap (compared to
  31 /// computing dominators and loop info) analysis.
  32 ///
  33 /// The output is added to Result, as pairs of <from,to> edge info.
  34 void FindFunctionBackedges(
  35     const Function &F,
  36     SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > &
  37         Result);
  38
  39 /// Search for the specified successor of basic block BB and return its position
  40 /// in the terminator instruction's list of successors.  It is an error to call
  41 /// this with a block that is not a successor.
  42 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ);
  43
  44 /// Return true if the specified edge is a critical edge. Critical edges are
  45 /// edges from a block with multiple successors to a block with multiple
  46 /// predecessors.
  47 ///
  48 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
  49                     bool AllowIdenticalEdges = false);
  50
  51 /// Determine whether instruction 'To' is reachable from 'From',
  52 /// returning true if uncertain.
  53 ///
  54 /// Determine whether there is a path from From to To within a single function.
  55 /// Returns false only if we can prove that once 'From' has been executed then
  56 /// 'To' can not be executed. Conservatively returns true.
  57 ///
  58 /// This function is linear with respect to the number of blocks in the CFG,
  59 /// walking down successors from From to reach To, with a fixed threshold.
  60 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of
  61 /// an entire loop of any number of blocks to be the same as the cost of a
  62 /// single block. DT reduces the cost by allowing the search to terminate when
  63 /// we find a block that dominates the block containing 'To'. DT is most useful
  64 /// on branchy code but not loops, and LI is most useful on code with loops but
  65 /// does not help on branchy code outside loops.
  66 bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
  67                             const DominatorTree *DT = nullptr,
  68                             const LoopInfo *LI = nullptr);
  69
  70 /// Determine whether block 'To' is reachable from 'From', returning
  71 /// true if uncertain.
  72 ///
  73 /// Determine whether there is a path from From to To within a single function.
  74 /// Returns false only if we can prove that once 'From' has been reached then
  75 /// 'To' can not be executed. Conservatively returns true.
  76 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
  77                             const DominatorTree *DT = nullptr,
  78                             const LoopInfo *LI = nullptr);
  79
  80 /// Determine whether there is at least one path from a block in
  81 /// 'Worklist' to 'StopBB', returning true if uncertain.
  82 ///
  83 /// Determine whether there is a path from at least one block in Worklist to
  84 /// StopBB within a single function. Returns false only if we can prove that
  85 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
  86 /// executed. Conservatively returns true.
  87 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
  88                                     BasicBlock *StopBB,
  89                                     const DominatorTree *DT = nullptr,
  90                                     const LoopInfo *LI = nullptr);
  91
  92 /// Return true if the control flow in \p RPOTraversal is irreducible.
  93 ///
  94 /// This is a generic implementation to detect CFG irreducibility based on loop
  95 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
  96 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
  97 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
  98 /// function is only recommended when loop info analysis is available. If loop
  99 /// info analysis isn't available, please, don't compute it explicitly for this
 100 /// purpose. There are more efficient ways to detect CFG irreducibility that
 101 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
 102 /// algorithm).
 103 ///
 104 /// Requirements:
 105 ///   1) GraphTraits must be implemented for NodeT type. It is used to access
 106 ///      NodeT successors.
 107 //    2) \p RPOTraversal must be a valid reverse post-order traversal of the
 108 ///      target CFG with begin()/end() iterator interfaces.
 109 ///   3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
 110 ///      analysis information of the CFG.
 111 ///
 112 /// This algorithm uses the information about reducible loop back-edges already
 113 /// computed in \p LI. When a back-edge is found during the RPO traversal, the
 114 /// algorithm checks whether the back-edge is one of the reducible back-edges in
 115 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
 116 /// below (canonical irreducible graph) loop info won't contain any loop, so the
 117 /// algorithm will return that the CFG is irreducible when checking the B <-
 118 /// -> C back-edge.
 119 ///
 120 /// (A->B, A->C, B->C, C->B, C->D)
 121 ///    A
 122 ///  /   \
 123 /// B<- ->C
 124 ///       |
 125 ///       D
 126 ///
 127 template <class NodeT, class RPOTraversalT, class LoopInfoT,
 128           class GT = GraphTraits<NodeT>>
 129 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
 130   /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
 131   /// according to LI. I.e., check if there exists a loop that contains Src and
 132   /// where Dst is the loop header.
 133   auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
 134     for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
 135       if (Lp->getHeader() == Dst)
 136         return true;
 137     }
 138     return false;
 139   };
 140
 141   SmallPtrSet<NodeT, 32> Visited;
 142   for (NodeT Node : RPOTraversal) {
 143     Visited.insert(Node);
 144     for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
 145       // Succ hasn't been visited yet
 146       if (!Visited.count(Succ))
 147         continue;
 148       // We already visited Succ, thus Node->Succ must be a backedge. Check that
 149       // the head matches what we have in the loop information. Otherwise, we
 150       // have an irreducible graph.
 151       if (!isProperBackedge(Node, Succ))
 152         return true;
 153     }
 154   }
 155
 156   return false;
 157 }
 158 } // End llvm namespace
 159
 160 #endif