EIC code displayed by LXR master/​include/​llvm/​Analysis/​CFG.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:11

 //===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This family of functions performs analyses on basic blocks, and instructions
 // contained within basic blocks.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CFG_H
 #define LLVM_ANALYSIS_CFG_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include <utility>
 
 namespace llvm {
 
 class BasicBlock;
 class DominatorTree;
 class Function;
 class Instruction;
 class LoopInfo;
 template <typename T> class SmallVectorImpl;
 
 /// Analyze the specified function to find all of the loop backedges in the
 /// function and return them.  This is a relatively cheap (compared to
 /// computing dominators and loop info) analysis.
 ///
 /// The output is added to Result, as pairs of <from,to> edge info.
 void FindFunctionBackedges(
     const Function &F,
     SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > &
         Result);
 
 /// Search for the specified successor of basic block BB and return its position
 /// in the terminator instruction's list of successors.  It is an error to call
 /// this with a block that is not a successor.
 unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ);
 
 /// Return true if the specified edge is a critical edge. Critical edges are
 /// edges from a block with multiple successors to a block with multiple
 /// predecessors.
 ///
 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
                     bool AllowIdenticalEdges = false);
 bool isCriticalEdge(const Instruction *TI, const BasicBlock *Succ,
                     bool AllowIdenticalEdges = false);
 
 /// Determine whether instruction 'To' is reachable from 'From', without passing
 /// through any blocks in ExclusionSet, returning true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been executed then
 /// 'To' can not be executed. Conservatively returns true.
 ///
 /// This function is linear with respect to the number of blocks in the CFG,
 /// walking down successors from From to reach To, with a fixed threshold.
 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of
 /// an entire loop of any number of blocks to be the same as the cost of a
 /// single block. DT reduces the cost by allowing the search to terminate when
 /// we find a block that dominates the block containing 'To'. DT is most useful
 /// on branchy code but not loops, and LI is most useful on code with loops but
 /// does not help on branchy code outside loops.
 bool isPotentiallyReachable(
     const Instruction *From, const Instruction *To,
     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
     const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Determine whether block 'To' is reachable from 'From', returning
 /// true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been reached then
 /// 'To' can not be executed. Conservatively returns true.
 bool isPotentiallyReachable(
     const BasicBlock *From, const BasicBlock *To,
     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
     const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Determine whether there is at least one path from a block in
 /// 'Worklist' to 'StopBB' without passing through any blocks in
 /// 'ExclusionSet', returning true if uncertain.
 ///
 /// Determine whether there is a path from at least one block in Worklist to
 /// StopBB within a single function without passing through any of the blocks
 /// in 'ExclusionSet'. Returns false only if we can prove that once any block
 /// in 'Worklist' has been reached then 'StopBB' can not be executed.
 /// Conservatively returns true.
 bool isPotentiallyReachableFromMany(
     SmallVectorImpl<BasicBlock *> &Worklist, const BasicBlock *StopBB,
     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
     const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Determine whether there is a potentially a path from at least one block in
 /// 'Worklist' to at least one block in 'StopSet' within a single function
 /// without passing through any of the blocks in 'ExclusionSet'. Returns false
 /// only if we can prove that once any block in 'Worklist' has been reached then
 /// no blocks in 'StopSet' can be executed without passing through any blocks in
 /// 'ExclusionSet'. Conservatively returns true.
 bool isManyPotentiallyReachableFromMany(
     SmallVectorImpl<BasicBlock *> &Worklist,
     const SmallPtrSetImpl<const BasicBlock *> &StopSet,
     const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
     const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Return true if the control flow in \p RPOTraversal is irreducible.
 ///
 /// This is a generic implementation to detect CFG irreducibility based on loop
 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
 /// function is only recommended when loop info analysis is available. If loop
 /// info analysis isn't available, please, don't compute it explicitly for this
 /// purpose. There are more efficient ways to detect CFG irreducibility that
 /// don't require recomputing loop info analysis (e.g., T1/T2 or Tarjan's
 /// algorithm).
 ///
 /// Requirements:
 ///   1) GraphTraits must be implemented for NodeT type. It is used to access
 ///      NodeT successors.
 //    2) \p RPOTraversal must be a valid reverse post-order traversal of the
 ///      target CFG with begin()/end() iterator interfaces.
 ///   3) \p LI must be a valid LoopInfoBase that contains up-to-date loop
 ///      analysis information of the CFG.
 ///
 /// This algorithm uses the information about reducible loop back-edges already
 /// computed in \p LI. When a back-edge is found during the RPO traversal, the
 /// algorithm checks whether the back-edge is one of the reducible back-edges in
 /// loop info. If it isn't, the CFG is irreducible. For example, for the CFG
 /// below (canonical irreducible graph) loop info won't contain any loop, so the
 /// algorithm will return that the CFG is irreducible when checking the B <-
 /// -> C back-edge.
 ///
 /// (A->B, A->C, B->C, C->B, C->D)
 ///    A
 ///  /   \
 /// B<- ->C
 ///       |
 ///       D
 ///
 template <class NodeT, class RPOTraversalT, class LoopInfoT,
           class GT = GraphTraits<NodeT>>
 bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI) {
   /// Check whether the edge (\p Src, \p Dst) is a reducible loop backedge
   /// according to LI. I.e., check if there exists a loop that contains Src and
   /// where Dst is the loop header.
   auto isProperBackedge = [&](NodeT Src, NodeT Dst) {
     for (const auto *Lp = LI.getLoopFor(Src); Lp; Lp = Lp->getParentLoop()) {
       if (Lp->getHeader() == Dst)
         return true;
     }
     return false;
   };
 
   SmallPtrSet<NodeT, 32> Visited;
   for (NodeT Node : RPOTraversal) {
     Visited.insert(Node);
     for (NodeT Succ : make_range(GT::child_begin(Node), GT::child_end(Node))) {
       // Succ hasn't been visited yet
       if (!Visited.count(Succ))
         continue;
       // We already visited Succ, thus Node->Succ must be a backedge. Check that
       // the head matches what we have in the loop information. Otherwise, we
       // have an irreducible graph.
       if (!isProperBackedge(Node, Succ))
         return true;
     }
   }
 
   return false;
 }
 } // End llvm namespace
 
 #endif

This page was automatically generated by the 2.3.7 LXR engine. The LXR team