Module Analysis_and_optimization.Dataflow_types

type label = int

A label is a unique identifier for a node in the dataflow/dependency graph, and often corresponds to one node in the Mir.

val label_of_sexp : Sexplib0.Sexp.t -> label
val sexp_of_label : label -> Sexplib0.Sexp.t
val hash_fold_label : Ppx_hash_lib.Std.Hash.state -> label -> Ppx_hash_lib.Std.Hash.state
val hash_label : label -> Ppx_hash_lib.Std.Hash.hash_value
val compare_label : label -> label -> int
type vexpr =
  1. | VVar of string

Representation of an expression that can be assigned to. This should also be able to represent indexed variables, but we don't support that yet.

val vexpr_of_sexp : Sexplib0.Sexp.t -> vexpr
val sexp_of_vexpr : vexpr -> Sexplib0.Sexp.t
val hash_fold_vexpr : Ppx_hash_lib.Std.Hash.state -> vexpr -> Ppx_hash_lib.Std.Hash.state
val hash_vexpr : vexpr -> Ppx_hash_lib.Std.Hash.hash_value
val compare_vexpr : vexpr -> vexpr -> int
type reaching_defn = vexpr * label

A 'reaching definition' (or reaching_defn or RD) statement (v, l) says that the variable v could have been affected at the label l.

val reaching_defn_of_sexp : Sexplib0.Sexp.t -> reaching_defn
val sexp_of_reaching_defn : reaching_defn -> Sexplib0.Sexp.t
val hash_fold_reaching_defn : Ppx_hash_lib.Std.Hash.state -> reaching_defn -> Ppx_hash_lib.Std.Hash.state
val hash_reaching_defn : reaching_defn -> Ppx_hash_lib.Std.Hash.hash_value
val compare_reaching_defn : reaching_defn -> reaching_defn -> int
type source_loc =
  1. | MirNode of Middle.Location_span.t
  2. | StartOfBlock
  3. | TargetTerm of {
    1. term : Middle.Expr.Typed.t;
    2. assignment_label : label;
    }

Description of where a node in the dependency graph came from, where MirNode is the location from an Middle.loc_stmt

val source_loc_of_sexp : Sexplib0.Sexp.t -> source_loc
val sexp_of_source_loc : source_loc -> Sexplib0.Sexp.t
type 'rd_info node_info = {
  1. rd_sets : 'rd_info;
  2. possible_previous : label Core.Set.Poly.t;
  3. rhs_set : vexpr Core.Set.Poly.t;
  4. controlflow : label Core.Set.Poly.t;
  5. loc : source_loc;
}

Information to be collected about each node * rd_sets: Information about how the label effects the reaching definition sets * possible_previous: The set of nodes that could have immediately preceded this node under some execution of the program * rhs_set: The 'right hand side' set of variables that affect the value or behavior of this node * controlflow: The set of control flow nodes that are immediate parents of this node: * The most recent nested if/then or loop, * or the beginning of the function or block if there are no containing branches, * plus the set of relevant continue/return statements, * plus, for loops, any break statements they contain * loc: The location of the Mir node that this node corresponds to, or a description if there is none

val node_info_of_sexp : 'rd_info. (Sexplib0.Sexp.t -> 'rd_info) -> Sexplib0.Sexp.t -> 'rd_info node_info
val sexp_of_node_info : 'rd_info. ('rd_info -> Sexplib0.Sexp.t) -> 'rd_info node_info -> Sexplib0.Sexp.t
type node_info_update = (reaching_defn Core.Set.Poly.t -> reaching_defn Core.Set.Poly.t) node_info

A node_info, where the reaching definition information takes the form of an update function that maps from the 'entry' set to the 'exit' set, where the entry set is what's true before executing this node and the exit set is true after.

type node_info_fixedpoint = (reaching_defn Core.Set.Poly.t * reaching_defn Core.Set.Poly.t) node_info

A node_info where the reaching definition information is explicitly written as the entry and exit sets, as after finding the fixed-point solution.

val node_info_fixedpoint_of_sexp : Sexplib0.Sexp.t -> node_info_fixedpoint
val sexp_of_node_info_fixedpoint : node_info_fixedpoint -> Sexplib0.Sexp.t
type traversal_state = {
  1. label_ix : label;
  2. node_info_map : (int, node_info_update) Core.Map.Poly.t;
  3. possible_previous : label Core.Set.Poly.t;
  4. target_terms : label Core.Set.Poly.t;
  5. continues : label Core.Set.Poly.t;
  6. breaks : label Core.Set.Poly.t;
  7. returns : label Core.Set.Poly.t;
  8. rejects : label Core.Set.Poly.t;
}

The state that will be maintained throughout the traversal of the Mir * label_ix: The next label that's free to use * node_info_map: The label information that's been built so far * possible_previous: The set of nodes that could have immediately preceded this point under some execution of the program * target_terms: The set of nodes that correspond to terms added to the target variable * continues: A set of the continue nodes that have been encountered since exiting a loop * breaks: A set of the break nodes that have been encountered since exiting a loop * returns: A set of the return nodes that have been encountered

type cf_state = label

The most recently nested control flow (block start, if/then, or loop)

This isn't included in the traversal_state because it only flows downward through the tree, not across and up like everything else

type dataflow_graph = {
  1. node_info_map : (int, node_info_fixedpoint) Core.Map.Poly.t;
  2. possible_exits : label Core.Set.Poly.t;
  3. probabilistic_nodes : label Core.Set.Poly.t;
}

Everything we need to know to do dependency analysis * node_info_map: Collection of node information * possible_exits: Set of nodes that could be the last to execute under some execution * probabilistic_nodes: Set of nodes corresponding to which can only introduce probabilistic dependencies, such as target terms and reject statements, to be excluded for non-statistical dependency analysis

val dataflow_graph_of_sexp : Sexplib0.Sexp.t -> dataflow_graph
val sexp_of_dataflow_graph : dataflow_graph -> Sexplib0.Sexp.t
type prog_df_graphs = {
  1. tdatab : dataflow_graph;
  2. modelb : dataflow_graph;
  3. gqb : dataflow_graph;
}

Represents the dataflow graphs for each interesting block in the program MIR.

See Middle.prog for block descriptions.

val prog_df_graphs_of_sexp : Sexplib0.Sexp.t -> prog_df_graphs
val sexp_of_prog_df_graphs : prog_df_graphs -> Sexplib0.Sexp.t