Safe Haskell	None

LLVM.Analysis.CallGraph

Contents

Types
Constructor
Accessors
Visualization

Description

This module defines a call graph and related functions. The call graph is a static view of the calls between functions in a Module. The nodes of the graph are global functions and the edges are calls made to other functions.

This call graph attempts to provide as much information as possible about calls through function pointers. Direct calls have a single outgoing edge. Indirect calls that can be augmented with information from a points-to analysis can induce many IndirectCall edges.

For now, all indirect calls also induce an UnknownCall edge, under the assumption that externally-obtained function pointers may also be called somehow. This restriction will eventually be lifted and indirect calls that can be identified as completely internal will not have the UnknownCall edge. The preconditions for this will be:

The Module must have an entry point (otherwise it is a library)
The function pointer must not be able to alias the result of a dlopen or similar call

Again, the more sophisticated callgraph is still pending.

Synopsis

Types

data CallGraph Source

An opaque wrapper for the callgraph. The nodes are functions and the edges are calls between them.

type CG = SparseDigraph CallNode CallEdge Source

A type synonym for the underlying graph

data CallEdge Source

Constructors

DirectCall	A static call to a known function
IndirectCall	A possible call to a known function through a function pointer
UnknownCall	A possible call to an unknown function through a function pointer

Instances

Eq CallEdge
Ord CallEdge
Show CallEdge
Labellable CallEdge
Hashable CallEdge

data CallNode Source

The nodes are actually a wrapper type:

Constructors

DefinedFunction Function	An actual function defined in this `Module`
ExtFunction ExternalFunction	An externally-defined function with a declaration in the `Module`
UnknownFunction	A function called indirectly that may not have any definition or declaration within the `Module`

Instances

Eq CallNode
Show CallNode
Labellable CallNode

Constructor

mkCallGraph Source

Arguments

:: PointsToAnalysis a
=> Module
-> a	A points-to analysis (to resolve function pointers)
-> [Function]	The entry points to the `Module`
-> CallGraph

Build a call graph for the given Module using a pre-computed points-to analysis. The String parameter identifies the program entry point.

FIXME: entryPoint is not respected.

FIXME: Function pointers can be bitcasted - be sure to respect those when adding indirect edges.

Accessors

callGraphRepr :: CallGraph -> CG Source

Convert the CallGraph to a graph ADT that can be traversed, manipulated, or easily displayed with graphviz.

For now, this representation is not guaranteed to remain stable.

callValueTargets :: CallGraph -> Value -> [Value]Source

Given the value called by a Call or Invoke instruction, return all of the possible Functions or ExternalFunctions that it could be.

callSiteTargets :: CallGraph -> Instruction -> [Value]Source

Given a Call or Invoke instruction, return the list of possible callees. All returned Values will be either Functions or ExternalFunctions.

Passing a non-call/invoke instruction will trigger a noisy pattern matching failure.

callGraphFunctions :: CallGraph -> [Function]Source

Get all of the functions defined in this module from the CallGraph

functionCallees :: CallGraph -> Function -> [Value]Source

allFunctionCallees :: CallGraph -> Function -> [Value]Source

functionCallers :: CallGraph -> Function -> [Value]Source

allFunctionCallers :: CallGraph -> Function -> [Value]Source

Visualization

cgGraphvizRepr :: CallGraph -> DotGraph Int Source