| Safe Haskell | None |
|---|
LLVM.Analysis.CallGraphSCCTraversal
Contents
Description
This module provides a framework for analyzing LLVM Modules bottom-up with regard to the call graph. The analysis starts at the leaves and propagates summary information up the call graph. Strongly-connected components (hence the SCC in the module name) are analyzed until a fixed-point is reached.
Analysis functions can be either pure or monadic; the adaptors take summary functions of various shapes and convert them into a form suitable for the traversal engine.
The traversal also processes independent strongly-connected components in parallel with as many cores as the process has been allocated.
- callGraphSCCTraversal :: FuncLike funcLike => CallGraph -> ([funcLike] -> summary -> summary) -> summary -> summary
- parallelCallGraphSCCTraversal :: (NFData summary, Monoid summary, FuncLike funcLike) => CallGraph -> ([funcLike] -> summary -> summary) -> summary -> summary
- data ComposableAnalysis compSumm funcLike
- callGraphAnalysis :: (FuncLike funcLike, Eq summary) => (funcLike -> summary -> summary) -> [funcLike] -> summary -> summary
- callGraphAnalysisM :: (FuncLike funcLike, Eq summary, Monad m) => (m summary -> summary) -> (funcLike -> summary -> m summary) -> [funcLike] -> summary -> summary
- callGraphComposeAnalysis :: (FuncLike funcLike, Monoid compSumm, Eq compSumm) => [ComposableAnalysis compSumm funcLike] -> [funcLike] -> compSumm -> compSumm
- composableAnalysis :: (NFData summary, Monoid summary, Eq summary, FuncLike funcLike) => (funcLike -> summary -> summary) -> Lens' compSumm summary -> ComposableAnalysis compSumm funcLike
- composableDependencyAnalysis :: (NFData summary, Monoid summary, Eq summary, FuncLike funcLike) => (deps -> funcLike -> summary -> summary) -> Lens' compSumm summary -> Getter compSumm deps -> ComposableAnalysis compSumm funcLike
- composableAnalysisM :: (NFData summary, Monoid summary, Eq summary, Monad m, FuncLike funcLike) => (m summary -> summary) -> (funcLike -> summary -> m summary) -> Lens' compSumm summary -> ComposableAnalysis compSumm funcLike
- composableDependencyAnalysisM :: (NFData summary, Monoid summary, Eq summary, Monad m, FuncLike funcLike) => (m summary -> summary) -> (deps -> funcLike -> summary -> m summary) -> Lens' compSumm summary -> Getter compSumm deps -> ComposableAnalysis compSumm funcLike
Traversals
Arguments
| :: FuncLike funcLike | |
| => CallGraph | The callgraph |
| -> ([funcLike] -> summary -> summary) | A function to process a strongly-connected component |
| -> summary | An initial summary value |
| -> summary |
Traverse the callgraph bottom-up with an accumulator function.
callGraphSCCTraversal cg f seed
This example applies the folding function f over each
strongly-connected component in the callgraph bottom-up with a
starting seed. Each strongly-connected component is processed as
a unit. The final accumulated value (based on seed) is returned.
The function f is responsible for approximating the analysis
value for the SCC in whatever way makes sense for the analysis.
parallelCallGraphSCCTraversal :: (NFData summary, Monoid summary, FuncLike funcLike) => CallGraph -> ([funcLike] -> summary -> summary) -> summary -> summarySource
Just like callGraphSCCTraversal, except strongly-connected
components are analyzed in parallel. Each component is analyzed as
soon as possible after its dependencies have been analyzed.
Types
data ComposableAnalysis compSumm funcLike Source
An abstract representation of a composable analysis. Construct
these with the smart constructors composableAnalysis,
composableDependencyAnalysis, composableAnalysisM, and
composableDependencyAnalysisM.
Use callGraphComposeAnalysis to convert a list of these into a
summary function for use with the call graph traversals.
Adaptors
callGraphAnalysis :: (FuncLike funcLike, Eq summary) => (funcLike -> summary -> summary) -> [funcLike] -> summary -> summarySource
Make a call-graph SCC summary function from a pure summary function. The function is applied to each function in the SCC in an arbitrary order. It returns the resulting summary obtained by repeated evaluation until a fixed-point is reached.
Arguments
| :: (FuncLike funcLike, Eq summary, Monad m) | |
| => (m summary -> summary) | A function to unwrap a monadic result from the summary |
| -> (funcLike -> summary -> m summary) | Summary function |
| -> [funcLike] -> summary -> summary |
Make a call-graph SCC summary function from a basic monadic summary function and a function to evaluate the function in its monad and unwrap the monadic value.
The monadic equivalent of callGraphAnalysis.
callGraphComposeAnalysis :: (FuncLike funcLike, Monoid compSumm, Eq compSumm) => [ComposableAnalysis compSumm funcLike] -> [funcLike] -> compSumm -> compSummSource
Compose a list of analyses into a pure summary function for use in a callGraphSCCTraversal. The advantage of using a composable analysis is that it only traverses the call graph once. At each SCC, all analyses are applied until their fixed-point is reached.
This makes it easier to share intermediate values (like CFGs) between analyses without having to recompute them or store them on the side.
The input analyses are processed *in order* (left-to-right). This means that analyses with dependencies should come *after* the analyses they depend on in the list. This is not currently statically enforced - your dependency summaries will just be missing information you might have expected if you get the order wrong.
composableAnalysis :: (NFData summary, Monoid summary, Eq summary, FuncLike funcLike) => (funcLike -> summary -> summary) -> Lens' compSumm summary -> ComposableAnalysis compSumm funcLikeSource
Create a pure composable analysis from a summary function and a Lens that accesses the summary for this function (given the composite summary). The lens is used to access the current state of this analysis and to update the state for this analysis after it is run.
composableDependencyAnalysis :: (NFData summary, Monoid summary, Eq summary, FuncLike funcLike) => (deps -> funcLike -> summary -> summary) -> Lens' compSumm summary -> Getter compSumm deps -> ComposableAnalysis compSumm funcLikeSource
Like composableAnalysis, but with an extra lens that is used to
extract *dependency* information from the composite summary, which
is then fed into this summary function.
The intended use is that some analysis will have a dependency on an earlier analysis summary. The lens is used to extract the relevant part of the composite summary. A dependency on multiple earlier analysis summaries can be expressed by providing a lens that extracts a *tuple* containing all relevant analyses.
composableAnalysisM :: (NFData summary, Monoid summary, Eq summary, Monad m, FuncLike funcLike) => (m summary -> summary) -> (funcLike -> summary -> m summary) -> Lens' compSumm summary -> ComposableAnalysis compSumm funcLikeSource
A monadic version of composableAnalysis. The first argument
here is a function to unwrap a monadic value (something like
runIdentity or runReader).
composableDependencyAnalysisM :: (NFData summary, Monoid summary, Eq summary, Monad m, FuncLike funcLike) => (m summary -> summary) -> (deps -> funcLike -> summary -> m summary) -> Lens' compSumm summary -> Getter compSumm deps -> ComposableAnalysis compSumm funcLikeSource
A monadic version of composableDependencyAnalysis.