• Michal Terepeta's avatar
    Hoopl: improve postorder calculation · bbcea13a
    Michal Terepeta authored
    - 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's avatarMichal Terepeta <michal.terepeta@gmail.com>
    
    Test Plan: ./validate
    
    Reviewers: bgamari, simonmar
    
    Reviewed By: simonmar
    
    Subscribers: rwbarton, thomie, carter
    
    Differential Revision: https://phabricator.haskell.org/D4464
    bbcea13a
Graph.hs 6.76 KB