Skip to content

iterative fixed-point solver for availability #19

@mnikander

Description

@mnikander
  • defined powerset lattice for {undef, live, dead} with join (union) and meet (intersection) operations
  • documented the design decision
  • wrote down the order of that lattice in the design document, together with the resulting 'state machine'
  • defined a data structure to hold the IN and OUT sets for each block
  • defined function which takes the IN powersets and runs it through a block of code to obtain the OUT powersets and report errors if there were any
  • test the block processing function, it's worth checking this one even though it's not part of the API
  • create an iterative fixed-point solver which goes through the graph, updating the IN and OUT powersets for each block. So long as the OUT powerset of the current block changes, update the successor blocks as well.
  • after the solver has converged, explicitly check the validity of every phi-node, by checking that each phi-captured variable is exactly 'live' on its respective incoming edge, otherwise report an error

When processing a block, which contains a drop statement, a variable may go from {live} in the in-set to {dead} in the out-set. Is this still a monotone operation? I need to think about the order which my powerset lattice actually defines (subset order). Every operation must preserve the order in my lattice.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions