LCOV - code coverage report
Current view: top level - include/llvm/Analysis - CFG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 10 10 100.0 %
Date: 2018-07-13 00:08:38 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13