Compute a fixed point via abstract interpretation over a control flow graph (CFG) given 1) an interpretation + domain, 2) initial assignments of domain values to global variables, and 3) initial assignments of domain values to function arguments.

This is an intraprocedural analysis. To handle function calls, the transfer function for call statements must know how to supply summaries or compute an appropriate conservative approximation.

There are two results from the fixed point computation:

1) For each block in the CFG, the abstraction computed at the *entry* to the block

2) For each block in the CFG, the abstraction computed at the *exit* from the block. The Assignment for these "exit" abstractions ignores the ctx index on the blocks, since that context is for *entry* to the blocks.

3) The final abstract value for the value returned by the function

A CFG-scoped SSA temp register.

We don't care about the type params yet, hence the existential quantification. We may want to look up the instruction corresponding to a ScopedReg after analysis though, and we'll surely want to compare ScopedRegs for equality, and use them to look up values in point abstractions after analysis.

Lookup the abstract value of scoped reg in an exit assignment.

Lookup the abstract value of scoped reg -- specified by 0-based int indices -- in an exit assignment.

Turn a non paramaterized type into a parameterized type.

For when you want to use a parameterized-utils style data structure with a type that doesn't have a parameter.

The same definition as Const, but with a different Show instance.

A domain of abstract values, parameterized by a term type

The iteration strategies available for computing fixed points.

Algorithmically, the best strategies seem to be based on Weak Topological Orders (WTOs). The WTO approach also naturally supports widening (with a specified widening strategy and widening operator).

A simple worklist approach is also available.

Transfer functions for each statement type

Interpretation functions for some statement types -- e.g. interpExpr and interpExt -- receive ScopedReg arguments corresponding to the SSA tmp that the result of the interpreted statement get assigned to. Some interpretation functions that could receive this argument do not -- e.g. interpCall -- because conathan didn't have a use for that.

This abstraction contains the abstract values of each register at the program point represented by the abstraction. It also contains a map of abstractions for all of the global variables currently known.

This is a wrapper around a set of StmtIds that name allocation sites of references. We need the wrapper to correctly position the tp type parameter so that we can put them in an Assignment.

Look up the abstract value of a register at a program point

Modify the abstract value of a register at a program point

Compute a weak topological order for the CFG.

The Pointed wrapper that adds Top and Bottom elements

Construct a Pointed Domain from a pointed join function and an equality test.