Module Automata.DataflowSource

Multi-pass dataflow analysis on the DFA.

Computes liveness, definedness, register allocation, and priority chains via fixpoint iteration. The analysis proceeds in passes: 1. Reachability of branches from accepting states 2. Mark reachable transitions (usage tracking) 3. Dead-code analysis and unreachable clause warnings 4. Priority splits (which positions can distinguish clause precedence) 5. Priority chain construction via Order_chain 6. Accepted-before computation (for pruning priority changes) 7. Liveness analysis (which captures are needed at each state) 8. Definedness analysis (which captures have been produced) 9. Variable class computation (for register allocation) 10. Register allocation (naive greedy by variable class)

A pairing of source and target order chain elements for a transition.

Sourcetype 'n _var_classes = {
  1. domain : 'n Fix.Indexing.cardinal;
  2. mutable classes : 'n var Utils.Misc.indexset list;
}
Sourcetype var_classes =
  1. | V : 'n _var_classes -> var_classes
Sourcetype ('g, 'r, 'dfa) t = {
  1. pairings : ('dfa, (('g, 'r) Spec.branch Fix.Indexing.index * chain) list list) Fix.Indexing.vector;
    (*

    For each state and each outgoing transition, the priority chain pairings between source and target order chain elements.

    *)
  2. accepts : ('dfa, (('g, 'r) Spec.branch Fix.Indexing.index * priority) list) Fix.Indexing.vector;
    (*

    For each state, the list of accepted branches with their priorities.

    *)
  3. liveness : ('dfa, Regexp.Capture.set array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the set of captures that are live (needed) from this point onward.

    *)
  4. defined : ('dfa, Regexp.Capture.set array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the set of captures that have been defined along some path to this state.

    *)
  5. classes : ('dfa, var_classes) Fix.Indexing.vector;
    (*

    For each state, the variable classes used for register allocation.

    *)
  6. registers : ('dfa, Lrgrep_support.Register.t Regexp.Capture.map array) Fix.Indexing.vector;
    (*

    For each state and each kernel position, the mapping from captures to allocated registers.

    *)
  7. register_count : int;
    (*

    Total number of registers allocated across all states.

    *)
  8. accepted_before : ('dfa, ('g, 'r) Spec.branch Utils.Misc.indexset) Fix.Indexing.vector;
    (*

    For each state, the set of branches that have been accepted on some path to this state. Used for pruning priority remappings.

    *)
}

Results of the dataflow analysis.

Sourceval liveness : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Regexp.Capture.set) Fix.Indexing.Vector.t
Sourceval defined : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Regexp.Capture.set) Fix.Indexing.Vector.t
Sourceval registers : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> ('n, Lrgrep_support.Register.t Regexp.Capture.map) Fix.Indexing.Vector.t
Sourceval classes : ('g, 'r, 'dfa) t -> ('g, 'r, 'dfa, 'n) DFA.state -> 'n var Utils.Misc.indexset list
Sourcetype ('g, 'r, 'dfa, 'tgt) rev_mapping =
  1. | Rev_mapping : ('g, 'r, 'dfa, 'src) DFA.state * ('src, 'tgt) DFA.mapping -> ('g, 'r, 'dfa, 'tgt) rev_mapping

Reverse mapping: from a target state back to a source state and the associated kernel mapping. Used for backward dataflow analysis.

Sourcetype ('g, 'r, 'dfa) packed_rev_mapping =
  1. | Rev_packed : ('g, 'r, 'dfa, 'n) rev_mapping list -> ('g, 'r, 'dfa) packed_rev_mapping

Packed list of reverse mappings for a DFA state.

Sourceval dump : 'a Kernel__Info.grammar -> ('a, 'b, 'c) DFA.t -> ('a, 'b, 'c) t -> Stdlib.out_channel -> unit
Sourceval reverse_transitions : ('a, 'b, 'c) DFA.t -> ('c, ('a, 'b, 'c) packed_rev_mapping) Fix.Indexing.Vector.t

Reverse the DFA transition graph for backward analysis.

Sourceval make : ('g, 'r) Spec.branches -> ('g, 'r, 'dfa) DFA.t -> ('g, 'r, 'dfa) t

Run the full dataflow analysis pipeline on a DFA.

Executes 10 passes: reachability, usage marking, dead-code analysis, priority splits, priority chain construction, accepted-before, liveness, definedness, variable classes, and register allocation. Returns the complete analysis results.