2
$\begingroup$

Here is a definition of reducible flow graphs :

A flow graph is reducible if every retreating edge in any DFST for that flow graph is a back edge.

And the reasons why we care about retreating/back edges:

  1. Proper ordering of nodes during iterative algorithm assures number of passes limited by the number of “nested” back edges.
  2. Depth of nested loops upper-bounds the number of nested back edges.

With this explanation, I have more questions: why number of passes is important? why we want to know upper-bounds?

However, I still do not understand the impact of irreducibility . Why should we care about it? Will it make it harder to do loop flatten? What if we have irreducible flow graphs for program analysis?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.