Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===-- 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);

/// 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