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?


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.