Check if an SCC is a Loop

Hi everyone,

Recently we needed to know whether an SCC is a loop in a patch:

First of all, do you think this is a useful addition to the SCC interface?

If yes, yhe solution that we ended up doing is:

  • Get LoopInfo for the function.
  • Given an SCC, take one random block of it. Then, call getLoopFor() with that block.
    If we don’t get a loop back, then this SCC is definitely not a loop.
  • Otherwise, we compare the size of the SCC with that of the loop and there are 3 cases:
  • They’re equal: this SCC is a loop.
  • The SCC is smaller: This SCC is not a loop because getLoopFor() gives the innermost loop. So, if this is smaller, it is an SCC inside a loop.
  • The SCC is bigger: In that case, we can’t decide since let’s say the SCC has blocks A, B, C. And the loop has blocks A, B. But blocks A, B, C might also make a loop. However, since getLoopFor() gives us the innermost loop, it will give us A, B. So, in that case, use getParentLoop() repeatedly and repeat the procedure for the parent loops.

Do you think there’s a better way ? I was thinking that maybe there was a more straightforward way by trying to verify whether the criteria for a loop are satisfied (i.e. there’s a block that dominates all the other blocks).

Stefanos Baziotis