181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky//===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- C++ -*-===// 281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// The LLVM Compiler Infrastructure 481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// This file is distributed under the University of Illinois Open Source 681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// License. See LICENSE.TXT for details. 781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky//===----------------------------------------------------------------------===// 981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 1081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// This family of functions performs analyses on basic blocks, and instructions 1181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// contained within basic blocks. 1281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky// 1381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky//===----------------------------------------------------------------------===// 1481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 1581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#ifndef LLVM_ANALYSIS_CFG_H 1681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#define LLVM_ANALYSIS_CFG_H 1781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 1881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/IR/BasicBlock.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 2081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 2181e480463d8bb57776d03cebfd083762909023f1Nick Lewyckynamespace llvm { 2281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 2381e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass BasicBlock; 2481e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass DominatorTree; 2581e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass Function; 2681e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass Instruction; 2781e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass LoopInfo; 2881e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyclass TerminatorInst; 2981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 3081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Analyze the specified function to find all of the loop backedges in the 3181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// function and return them. This is a relatively cheap (compared to 3281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// computing dominators and loop info) analysis. 3381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// 3481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// The output is added to Result, as pairs of <from,to> edge info. 3581e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyvoid FindFunctionBackedges( 3681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky const Function &F, 3781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > & 3881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky Result); 3981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 4081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Search for the specified successor of basic block BB and return its position 4181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// in the terminator instruction's list of successors. It is an error to call 4281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// this with a block that is not a successor. 4381e480463d8bb57776d03cebfd083762909023f1Nick Lewyckyunsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ); 4481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 4581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Return true if the specified edge is a critical edge. Critical edges are 4681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// edges from a block with multiple successors to a block with multiple 4781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// predecessors. 4881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// 4981e480463d8bb57776d03cebfd083762909023f1Nick Lewyckybool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, 5081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky bool AllowIdenticalEdges = false); 5181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 5272dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// \brief Determine whether instruction 'To' is reachable from 'From', 5372dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// returning true if uncertain. 5472dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// 5581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Determine whether there is a path from From to To within a single function. 5681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Returns false only if we can prove that once 'From' has been executed then 5781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// 'To' can not be executed. Conservatively returns true. 5881e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// 5981e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// This function is linear with respect to the number of blocks in the CFG, 6081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// walking down successors from From to reach To, with a fixed threshold. 6181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// Using DT or LI allows us to answer more quickly. LI reduces the cost of 6281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// an entire loop of any number of blocsk to be the same as the cost of a 6381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// single block. DT reduces the cost by allowing the search to terminate when 6481e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// we find a block that dominates the block containing 'To'. DT is most useful 6581e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// on branchy code but not loops, and LI is most useful on code with loops but 6681e480463d8bb57776d03cebfd083762909023f1Nick Lewycky/// does not help on branchy code outside loops. 6781e480463d8bb57776d03cebfd083762909023f1Nick Lewyckybool isPotentiallyReachable(const Instruction *From, const Instruction *To, 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DominatorTree *DT = nullptr, 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const LoopInfo *LI = nullptr); 7081e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 7172dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// \brief Determine whether block 'To' is reachable from 'From', returning 7272dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// true if uncertain. 7372dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// 7472dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// Determine whether there is a path from From to To within a single function. 7572dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// Returns false only if we can prove that once 'From' has been reached then 7672dba254ae65b06062106910a70d46f21e19d55aNick Lewycky/// 'To' can not be executed. Conservatively returns true. 7772dba254ae65b06062106910a70d46f21e19d55aNick Lewyckybool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To, 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DominatorTree *DT = nullptr, 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const LoopInfo *LI = nullptr); 8072dba254ae65b06062106910a70d46f21e19d55aNick Lewycky 8181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky} // End llvm namespace 8281e480463d8bb57776d03cebfd083762909023f1Nick Lewycky 8381e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#endif 84