Improvements to DOMTree

[sushant94]

Dominator tree construction was one of the first analysis implemented in radeco. This needs some love. As such, it is works but is inconsistent with the other analysis API in radeco. A refactor is needed.

Since DOMTree is not currently used anywhere in radeco, we can afford to make breaking changes (and probably do this when needed).

NOTE: petgraph has recently added dominator tree construction to its set of graph algorithms. It might be worthwhile to look into this and ride off their analysis instead of reimplementing/refactoring this inside radeco.

[shakram02]

I'm working on this for the moment, I'm going to remove InternalIndex and replace that with a function that maps a node_id which is of type graph::NodeIndex to its dfs traversal index, is that fine ? the api will provide the following for each noce

• Immediate Dominator
• Dominators
• Dominance frontier
• Index conversion, probably in both directions NodeIndex <-> dfs_index or the 2 sides of the old InternalIndex if I've mistaken the names

[sushant94]

@shakram02 Did you checkout the dominator tree support in petgraph? It'd be nice if we could reuse this rather than rewrite.

[sushant94]

Also, about the InternalIndex thing, as far as I remember, it was implemented this way cause petgraphs node indexing was not 'stable'. Now, petgraph has a new stable_graph (I made this change for the main SSA tree), so using that would make more sense rather than having another index.

Feel free to correct me if I'm wrong. DOMTree was probably the first analysis I wrote ;)

[shakram02]

whoa that must've been a long time ago, yea I check petgraph's dominator tree, I'll create a PR, it passes all the tests, but maybe you want to review the api