Hoopl: improve postorder calculation

Authored by michalt on Mar 3 2018, 10:31 AM.


  • Fix the naming and comments to indicate that we are calculating *reverse* postorder (and not the standard postorder).
  • Rewrite the calculation to avoid CPS code. I found it fairly difficult to understand and the new one seems faster (according to nofib, decreases compiler allocations by 0.2%)
  • Remove LabelsPtr, which seems unnecessary and could be *really* confusing. For instance, previously: postorder_dfs_from <block with label X> and postorder_dfs_from <label X> would actually mean quite different things (and give different results).
  • Change the Dataflow module to always use entry of the graph for reverse postorder calculation. This should be the only change in behavior of this commit.

    Previously, if the caller provided initial facts for some of the labels, we would use those labels for our postorder calculation. However, I don't think that's correct in general - if the initial facts did not contain the entry of the graph, we would never analyze the blocks reachable from the entry but unreachable from the labels provided with the initial facts. It seems that the only analysis that used this was proc-point analysis, which I think would always include the entry block (so I don't think there's any bug due to this).

Signed-off-by: Michal Terepeta <michal.terepeta@gmail.com>

Test Plan


Diff Detail

rGHC Glasgow Haskell Compiler
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.
michalt created this revision.Mar 3 2018, 10:31 AM
michalt updated this revision to Diff 15630.Mar 3 2018, 10:32 AM
  • Remove trailing whitespace
simonmar accepted this revision.Mar 5 2018, 2:55 AM

Looks nice, I was always a bit confused by how the original code worked, but this new version is a lot easier to understand. And there's a test too! Fantastic.

This revision is now accepted and ready to land.Mar 5 2018, 2:55 AM
This revision was automatically updated to reflect the committed changes.