Skip to content

Instantly share code, notes, and snippets.

@lirenlin

lirenlin/gist:6172b343dbfd0d0a561a4c1b192da7ba

Created November 12, 2018 18:17
Show Gist options
  • Save lirenlin/6172b343dbfd0d0a561a4c1b192da7ba to your computer and use it in GitHub Desktop.
Save lirenlin/6172b343dbfd0d0a561a4c1b192da7ba to your computer and use it in GitHub Desktop.
Download ZIP
RPO, pre-order, post-order
Raw
gistfile1.txt
tree vs graph
in tree, every node has a single predecessor, could have multiple sucessors.
in graph, there is no limitation, multiple predecessors, multiple sucessors.
RPO in graph, ensures all predecessors are visited before the current node is visited. Topologic sorting, forward data flow analysis.
RPO is the same as pre-order in tree, but different in graph.
post-order ensures all sucessors are visited before current node is visited. This is the reverse of RPO. backward data analysis.
forward data flow analysis: reaching definition
backward data flow analysis: live variable analysis.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment