Safe Haskell | None |
---|

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

:: 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.

:: (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`

.