LLVM  6.0.0svn
Macros | Functions
LazyCallGraph.cpp File Reference
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>
Include dependency graph for LazyCallGraph.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "lcg"
 

Functions

static void addEdge (SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
 
static bool isKnownLibFunction (Function &F, TargetLibraryInfo &TLI)
 
template<typename SCCT , typename PostorderSequenceT , typename SCCIndexMapT , typename ComputeSourceConnectedSetCallableT , typename ComputeTargetConnectedSetCallableT >
static iterator_range< typename PostorderSequenceT::iterator > updatePostorderSequenceForEdgeInsertion (SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs, SCCIndexMapT &SCCIndices, ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet, ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet)
 Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge insertion. More...
 
static void printNode (raw_ostream &OS, LazyCallGraph::Node &N)
 
static void printSCC (raw_ostream &OS, LazyCallGraph::SCC &C)
 
static void printRefSCC (raw_ostream &OS, LazyCallGraph::RefSCC &C)
 
static void printNodeDOT (raw_ostream &OS, LazyCallGraph::Node &N)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "lcg"

Definition at line 40 of file LazyCallGraph.cpp.

Function Documentation

◆ addEdge()

static void addEdge ( SmallVectorImpl< LazyCallGraph::Edge > &  Edges,
DenseMap< LazyCallGraph::Node *, int > &  EdgeIndexMap,
LazyCallGraph::Node N,
LazyCallGraph::Edge::Kind  EK 
)
static

◆ isKnownLibFunction()

static bool isKnownLibFunction ( Function F,
TargetLibraryInfo TLI 
)
static

◆ printNode()

static void printNode ( raw_ostream OS,
LazyCallGraph::Node N 
)
static

◆ printNodeDOT()

static void printNodeDOT ( raw_ostream OS,
LazyCallGraph::Node N 
)
static

◆ printRefSCC()

static void printRefSCC ( raw_ostream OS,
LazyCallGraph::RefSCC C 
)
static

◆ printSCC()

static void printSCC ( raw_ostream OS,
LazyCallGraph::SCC C 
)
static

◆ updatePostorderSequenceForEdgeInsertion()

template<typename SCCT , typename PostorderSequenceT , typename SCCIndexMapT , typename ComputeSourceConnectedSetCallableT , typename ComputeTargetConnectedSetCallableT >
static iterator_range<typename PostorderSequenceT::iterator> updatePostorderSequenceForEdgeInsertion ( SCCT &  SourceSCC,
SCCT &  TargetSCC,
PostorderSequenceT &  SCCs,
SCCIndexMapT &  SCCIndices,
ComputeSourceConnectedSetCallableT  ComputeSourceConnectedSet,
ComputeTargetConnectedSetCallableT  ComputeTargetConnectedSet 
)
static

Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge insertion.

A postorder sequence of SCCs of a directed graph has one fundamental property: all deges in the DAG of SCCs point "up" the sequence. That is, all edges in the SCC DAG point to prior SCCs in the sequence.

This routine both updates a postorder sequence and uses that sequence to compute the set of SCCs connected into a cycle. It should only be called to insert a "downward" edge which will require changing the sequence to restore it to a postorder.

When inserting an edge from an earlier SCC to a later SCC in some postorder sequence, all of the SCCs which may be impacted are in the closed range of those two within the postorder sequence. The algorithm used here to restore the state is as follows:

1) Starting from the source SCC, construct a set of SCCs which reach the source SCC consisting of just the source SCC. Then scan toward the target SCC in postorder and for each SCC, if it has an edge to an SCC in the set, add it to the set. Otherwise, the source SCC is not a successor, move it in the postorder sequence to immediately before the source SCC, shifting the source SCC and all SCCs in the set one position toward the target SCC. Stop scanning after processing the target SCC. 2) If the source SCC is now past the target SCC in the postorder sequence, and thus the new edge will flow toward the start, we are done. 3) Otherwise, starting from the target SCC, walk all edges which reach an SCC between the source and the target, and add them to the set of connected SCCs, then recurse through them. Once a complete set of the SCCs the target connects to is known, hoist the remaining SCCs between the source and the target to be above the target. Note that there is no need to process the source SCC, it is already known to connect. 4) At this point, all of the SCCs in the closed range between the source SCC and the target SCC in the postorder sequence are connected, including the target SCC and the source SCC. Inserting the edge from the source SCC to the target SCC will form a cycle out of precisely these SCCs. Thus we can merge all of the SCCs in this closed range into a single SCC.

This process has various important properties:

  • Only mutates the SCCs when adding the edge actually changes the SCC structure.
  • Never mutates SCCs which are unaffected by the change.
  • Updates the postorder sequence to correctly satisfy the postorder constraint after the edge is inserted.
  • Only reorders SCCs in the closed postorder sequence from the source to the target, so easy to bound how much has changed even in the ordering.
  • Big-O is the number of edges in the closed postorder range of SCCs from source to target.

This helper routine, in addition to updating the postorder sequence itself will also update a map from SCCs to indices within that sequecne.

The sequence and the map must operate on pointers to the SCC type.

Two callbacks must be provided. The first computes the subset of SCCs in the postorder closed range from the source to the target which connect to the source SCC via some (transitive) set of edges. The second computes the subset of the same range which the target SCC connects to via some (transitive) set of edges. Both callbacks should populate the set argument provided.

Definition at line 444 of file LazyCallGraph.cpp.

References assert(), C, llvm::SmallPtrSetImplBase::clear(), llvm::SmallPtrSetImpl< PtrType >::count(), and llvm::make_range().

Referenced by llvm::LazyCallGraph::RefSCC::insertIncomingRefEdge(), and llvm::LazyCallGraph::RefSCC::switchInternalEdgeToCall().