Page MenuHomePhabricator

Try to clarify loop definition around confusing sub-loop case

Authored by reames on Jul 25 2019, 2:15 PM.



As pointed out by reviewers, my own mental model here was wrong. So, let's try revising the definition to make that more clear.

Diff Detail


Event Timeline

reames created this revision.Jul 25 2019, 2:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2019, 2:15 PM
jdoerfert added inline comments.Jul 29 2019, 3:44 PM
17 ↗(On Diff #211817)

a loop is a set of basic blocks (= nodes in the control flow graph (CFG)) that form a strongly connected component (SCC). In addition, each loop has a dedicated entry/header block that dominates all other blocks within the loop. Thus, without leaving the loop, one can reach every block in the loop from the header block and the header block from every block in the loop.

(It's not a single cycle.)

31 ↗(On Diff #211817)

A sub-loop is sth. different. A loop can be made up of multiple cycles without having sub-loops.
There is no need for a "largest" cycle. Take

h: if (...) goto a; else goto b;
a: if (...) goto h; else goto end;
b: if (...) goto h; else goto end;

two cycles: h -> a -> h and h -> b -> h, neither containing the other one.

reames updated this revision to Diff 212398.Jul 30 2019, 11:42 AM

I think I've reformulated this to incorporate the review comments, let me know what you think.

jdoerfert accepted this revision.Jul 30 2019, 2:55 PM

minor comments and corrections, LGTM otherwise. Thx.

17 ↗(On Diff #211817)

My bad, I missed the "maximal" part:

In LLVM, a Loop is a maximal set of basic blocks that form a strongly connected component (SCC)

32 ↗(On Diff #212398)

Nit: "but the strongly connected component formed"

63 ↗(On Diff #212398)

Nit: "(The latter is a consequence of the block being contained within an
SCC which is part of the loop.)"

This revision is now accepted and ready to land.Jul 30 2019, 2:55 PM
This revision was automatically updated to reflect the committed changes.