6
$\begingroup$

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which makes sense.

Other resources (such as the "Engineering a Compiler" book) suggest to use reverse post-order (RPO) on the reversed CFG instead.

... and PO(graph) != RPO(rev(graph)) in some cases involving cycles.

My question is: which resource is right? Post-order makes sense, so why not just use that and save the CFG inversion? Why would I use RPO on reversed CFG instead?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ I had exactly the same question. Please let me know if you had the answer. Thanks. $\endgroup$ – JackWM Jan 31 '17 at 8:16
  • $\begingroup$ Seems OP has some good guess on this question, eli.thegreenplace.net/2015/… $\endgroup$ – Thomson Jan 22 '18 at 20:27
1
$\begingroup$

It is mostly due to the speed of convergence. To clarify, RPO visits as many predecessors possible before visiting a node so in case of forward data flow problems (like Dominator computation) this would help to converge faster. You can find more details in Engineering a compiler book (which you already know!)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.