Clarification on loop terminology

[Sam Parker-Haynes]

Hi!

I'm looking at the backend and the terminology used for loops is really confusing me. AFAICT, in the backend there may be two special blocks for loops but I can't say it makes any sense to me! Here's the code that is boggling my mind:

      if (block->IsLoopHeader()) {
        buffer << " (loop up to " << block->loop_end().ToInt() << ")";
      }

This seems to suggest that block->loop_end() is the first block inside the loop, is this true?! If so, I hope it's clear why this is confusing :)

cheers,

sam 

[Ben Noordhuis]

Nodes are visited in reverse post-order. Is that the source of the confusion?

[Sam Parker-Haynes]

I think it's just the way that it's written, as it was suggested to me offline that this annotation is describing a list of blocks: header -> end. If this is true then it makes far more sense! Saying 'loop up to' has certain connotations for me.

I do have other questions about the properties of loops too though:

- Does the header have exactly one predecessor outside of the loop? 

- Is loop_end guaranteed to contain a backedge to the header?

- Are other blocks allowed to have an edge back to the header?

Thanks.

[dmerc...@google.com]

Hi Sam,

> This seems to suggest that block->loop_end() is the first block inside the loop, is this true?! If so, I hope it's clear why this is confusing :)

The comment on GetLoopEndRpo explains what loop_end is:

  // In Turbofan, the `block->loop_end()` refers to the first after (outside)
  // the loop. In the relevant use cases, we retrieve the backedge block by
  // subtracting one from the rpo_number, so for Turboshaft we "fake" this by
  // adding 1 to the backedge block's rpo_number.

So, loop_end is outside of the loop.

> Does the header have exactly one predecessor outside of the loop? 

Yes.

> Is loop_end guaranteed to contain a backedge to the header?

You might need a -1, cf the comment above, but yes.

>  Are other blocks allowed to have an edge back to the header?

No.

Cheers,

Darius