Module Analysis_and_optimization.Dependence_analysis

~~~~~ TODO ~~~~~ * The interfaces are currently messed up. I think part of the solution is to change the signature of reaching_definitions_mfp in Monotone_framework, which currently requires the full program but shouldn't need the full program. As it stands, stmt_map_dependency_graph does not include data dependencies at all, since it can't use reaching deps, and prog_dependency graph only builds the graph for log_prob, but the user isn't guaranteed to be using the same labeling scheme. * Currently, dependencies on global or uninitialized data are written as depending on node '0'. This should probably be option or some type that indicates global dependence. * Indexed variables are currently handled as monoliths * No probabilistic dependency, I'll do that elsewhere *

type node_dep_info = {
  1. predecessors : Dataflow_types.label Core.Set.Poly.t;
  2. parents : Dataflow_types.label Core.Set.Poly.t;
  3. reaching_defn_entry : Dataflow_types.reaching_defn Core.Set.Poly.t;
  4. reaching_defn_exit : Dataflow_types.reaching_defn Core.Set.Poly.t;
  5. meta : Middle.Location_span.t;
}

Sufficient information about each node to build the dependency graph.

Label dependence doesn't need the exit RD set, but variable dependence does.

val node_immediate_dependencies : (Dataflow_types.label, (Middle.Expr.Typed.t, Dataflow_types.label) Middle.Stmt.Fixed.Pattern.t * node_dep_info) Core.Map.Poly.t -> ?blockers:Dataflow_types.vexpr Core.Set.Poly.t -> Dataflow_types.label -> Dataflow_types.label Core.Set.Poly.t

Given dependency information for each node, find the 'immediate' dependencies of a node, where 'immediate' means the first-degree control flow parents and the reachable definitions of RHS variables.

Given dependency information for each node, find all of the dependencies of a single node.

val node_vars_dependencies : (Dataflow_types.label, (Middle.Expr.Typed.t, Dataflow_types.label) Middle.Stmt.Fixed.Pattern.t * node_dep_info) Core.Map.Poly.t -> ?blockers:Dataflow_types.vexpr Core.Set.Poly.t -> Dataflow_types.vexpr Core.Set.Poly.t -> Dataflow_types.label -> Dataflow_types.label Core.Set.Poly.t

Given dependency information for each node, find all of the dependencies of a set of variables at single node.

'blockers' are variables which will not be traversed.

Build the dependency information for each node in the log_prob section of a program

Build the dependency information for each node in the log_prob section of a program

val all_node_dependencies : (Dataflow_types.label, (Middle.Expr.Typed.t, Dataflow_types.label) Middle.Stmt.Fixed.Pattern.t * node_dep_info) Core.Map.Poly.t -> (Dataflow_types.label, Dataflow_types.label Core.Set.Poly.t) Core.Map.Poly.t

Given dependency information for each node, find all of the dependencies of all nodes, effectively building the dependency graph.

This is more efficient than calling node_dependencies on each node individually.

val log_prob_dependency_graph : Middle.Program.Typed.t -> (Dataflow_types.label, Dataflow_types.label Core.Set.Poly.t) Core.Map.Poly.t

Build the dependency graph for the log_prob section of a program, where labels correspond to the labels built by statement_map.

val reaching_defn_lookup : Dataflow_types.reaching_defn Core.Set.Poly.t -> Dataflow_types.vexpr -> Dataflow_types.label Core.Set.Poly.t
val mir_uninitialized_variables : Middle.Program.Typed.t -> (Middle.Location_span.t * string) Core.Set.Poly.t

Produce a list of uninitialized variables and their label locations, from the flowgraph starting at the given statement