[LoopTerminology] Loop Simplify Form

[baziotis]

Summary

Information taken from the Writing Loop Optimizations video and the LoopSimplify.h

[baziotis]

Rebased

[Meinersbur]

Note that there already is a draft filling out this section at D65257.

[baziotis]

In D74989#1887529, @Meinersbur wrote:

Note that there already is a draft filling out this section at D65257.

Oh thanks, I didn't know that. So, closing. Can I add any part that is not addressed in this draft? For example, rotated loops
I think aren't and personally I feel they really need doc.

[Meinersbur]

llvm/docs/LoopTerminology.rst

147–160

Could you add that the LoopSimplify (-loop-simplify) pass ensures this form and is automatically added by the pass managers when scheduling a LoopPass?

152

[serious] There can be a single latch with multiple edges to the header (e.g. a switch)

153

[typo] exits

[Meinersbur]

In D74989#1887573, @baziotis wrote:

Oh thanks, I didn't know that. So, closing. Can I add any part that is not addressed in this draft? For example, rotated loops
I think aren't and personally I feel they really need doc.

I think the author abandoned it. In the current state it looks more like a API reference.

[baziotis]

In D74989#1887597, @Meinersbur wrote:

In D74989#1887573, @baziotis wrote:

Oh thanks, I didn't know that. So, closing. Can I add any part that is not addressed in this draft? For example, rotated loops
I think aren't and personally I feel they really need doc.

I think the author abandoned it. In the current state it looks more like a API reference.

Yes, just saw the date. Ok, I'll continue with this.

llvm/docs/LoopTerminology.rst

147–160

Of course.

152

Like this?

3:
  // whatever
  switch i32 %something, label %whatever [
    i32 1, label %3
    i32 2, label %3
  ]

In that case though, isn't the doc in LoopSimplify.h wrong?
"This pass also guarantees that loops will have exactly one backedge."
Assuming that a latch is a backedge, I figured it should be the only one, what do I miss?

[fhahn]

https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops Also has some info about loop simplify form. It would be good to at least cross reference the 2 documents and/or maybe consider unifying / aligning the descriptions

[baziotis]

In D74989#1888078, @fhahn wrote:

https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops Also has some info about loop simplify form. It would be good to at least cross reference the 2 documents and/or maybe consider unifying / aligning the descriptions

Thanks Florian. This doc is taken from LoopInfo.h, from which I have taken information (check the patch summary). The one comment about the backedge is taken from there for example.
So, they're aligned as far as I'm concerned but please comment if you spot something. I left some things out from this file and those are code details. I thought that in a terminology doc,
the details about how the pass is coded and what are its difficulties make it less understandable.

[baziotis]

This comment was removed by baziotis.

[Meinersbur]

llvm/docs/LoopTerminology.rst

152

The wording should clarify that whether the simplified form implies a single backedge or a single latch (with potentially multiple edges to the header as in your example). Having a look at the implementation:

bool Loop::isLoopSimplifyForm() const {
  // Normal-form loops have a preheader, a single backedge, and all of their
  // exits have all their predecessors inside the loop.
  return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
}

/// getLoopLatch - If there is a single latch block for this loop, return it.
/// A latch block is a block that contains a branch back to the header.
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
  assert(!isInvalid() && "Loop not in a valid state!");
  BlockT *Header = getHeader();
  BlockT *Latch = nullptr;
  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
    if (contains(Pred)) {
      if (Latch)
        return nullptr;
      Latch = Pred;
    }
  }

  return Latch;
}

And from LoopSimplify:

BasicBlock *LoopLatch = L->getLoopLatch();
if (!LoopLatch) {
  ...
  LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
  if (LoopLatch)
    Changed = true;
}

That is, it requires a single backedge (which implies a single latch). Your example is not in simplified form.

My wording "There can be a single latch with multiple edges to the header (e.g. a switch)" was not meant to imply that such a case is in simplified form, but that this is possible to happen, i.e. single backedge is not equivalent to single latch.

[nikic]

llvm/docs/LoopTerminology.rst

152

See also D72519...

[baziotis]

llvm/docs/LoopTerminology.rst

152

First of all, thanks for the explanations!

That is, it requires a single backedge (which implies a single latch).

Yes, exactly!

Your example is not in simplified form.

Yes, my example was just to be sure we're talking for the same thing.

My wording "There can be a single latch with multiple edges to the header (e.g. a switch)" was not meant to imply that such a case is in simplified form

Ah, ok, my bad. That's what I figured since this is a bullet under "For a loop to be in Loop Simplify Form, it must have:".

but that this is possible to happen, i.e. single backedge is not equivalent to single latch.

But not in simplified form right?

So, honestly, I didn't understand what is wrong with that. :/ It seems that for a loop to be simplified, it must have a latch and a single backedge. Since the latch has a backedge, it must also be the only backedge.
If you may, please comment how should I change my wording.

152

See also D72519...

Thank you, I added me as a subscriber so that if it gets accepted, I should go and change the doc.

[Meinersbur]

llvm/docs/LoopTerminology.rst

152

But not in simplified form right?

If we only talk about loops that are already in simplified form, then "has single backedge" and "has single latch" are tautologies.

If you may, please comment how should I change my wording.

Change the wording to be about a single backedge (as by the comment in isLoopSimplifyForm). You might additionally mention that a single backedge implies a single latch.

The suggestion "A latch which must also be the only backedge." is already wrong because a latch is a basic block (node/vertex in graph terms), not an edge.

152

See also D72519...

If we change the definition of getLoopLatch(), we will have to change the definition of simplified form.

[baziotis]

llvm/docs/LoopTerminology.rst

152

If we only talk about loops that are already in simplified form, then "has single backedge" and "has single latch" are tautologies.

Huh, ok.

Change the wording to be about a single backedge (as by the comment in isLoopSimplifyForm). You might additionally mention that a single backedge implies a single latch.

Ok.

The suggestion "A latch which must also be the only backedge." is already wrong because a latch is a basic block (node/vertex in graph terms), not an edge.

Indeed.

[baziotis]

Addressed comments.

[baziotis]

llvm/docs/LoopTerminology.rst

156

"no exit block for the loop"
I took this from the video but I think it syntactically incorrect, right? I feel like it should be "of the loop".

[Meinersbur]

@fhahn Also asked to cross-link https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops. Could you please do so?

llvm/docs/LoopTerminology.rst

156

As a non-native speaker, both seem to be fine. A block can play a role for a loop (here: being an exit block).

[baziotis]

In D74989#1889902, @Meinersbur wrote:

@fhahn Also asked to cross-link https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops. Could you please do so?

My bad, I thought I should just be sure that the info in the 2 places is aligned. Ok, I'll put a link from each to the other.

[baziotis]

• Link from one to the other in LoopSimplify.h and LoopTerminology.rst

[baziotis]

llvm/docs/LoopTerminology.rst

152

This is an external link. I don't know if this is ok.

llvm/include/llvm/Transforms/Utils/LoopSimplify.h

11–12

Instead of putting a link, we could just put the info that this file is missing because it's little. It's the pass manager info and the implication that there's a single latch.

[Meinersbur]

llvm/docs/LoopTerminology.rst

152

It's a link to the doxygen-generated reference, not the link that @fhahn suggested. (I don't mind keeping the doxygen link)

Documentation for cross-references (preferable within Sphinx) is here.

llvm/include/llvm/Transforms/Utils/LoopSimplify.h

11–12

Whatever you think is more appropriate.

[baziotis]

llvm/docs/LoopTerminology.rst

152

I didn't get it, thanks. From what I read, @fhahn probably meant using :ref:. I think that because the -loop-simplify doc doesn't have a link to the file that implements it, it's better to link the doxygen file. Since I think, if someone reads the -loop-simplify doc without seeing the .h, they won't understand much (i.e. better just read the more abstract one in LoopTerminology.rst). What do you think?

[baziotis]

Aligned info in LoopSimplify.h with the LoopTerminology.

[Meinersbur]

llvm/docs/LoopTerminology.rst

149

"This loop is ensures ...": The canonical form is ensured, the loop is already there before LoopSimplify.

152

Nothing stops us from linking to both documents. It is just nice to the reader to cross-ref other relevant documents such as https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops

The other way around Passes.rst could also cross-link back to here.

[baziotis]

llvm/docs/LoopTerminology.rst

149

Haha yes. :)

152

Ok, good.

[baziotis]

Add cross-references.

[Meinersbur]

LGTM. Do you want me to commit for you?

[baziotis]

In D74989#1892470, @Meinersbur wrote:

LGTM. Do you want me to commit for you?

Yes, if you can :) I don't have commit permission.

[Meinersbur]

[serious] I get the following error with ninja docs-llvm-html:

[1/1] Generating html Sphinx documentation for llvm into "/home/meinersbur/build/llvm-project/release/docs/html"
FAILED: docs/CMakeFiles/docs-llvm-html
cd /home/meinersbur/build/llvm-project/release/docs && /usr/bin/sphinx-build -b html -d /home/meinersbur/build/llvm-project/release/docs/_doctrees-llvm-html -q -W /home/meinersbur/src/llvm-project/llvm/docs /home/meinersbur/build/llvm-project/release/docs/html

Warning, treated as error:
/home/meinersbur/src/llvm-project/llvm/docs/LoopTerminology.rst:149:Unknown target name: "loopinfo.h http://llvm.org/doxygen/loopsimplify_8h_source.html".

llvm/docs/LoopTerminology.rst

153

This is missing angle brackets around the link. See reference here.

[baziotis]

Fixed link

llvm/docs/LoopTerminology.rst

* Loops which become statically unreachable during optimization *must*
   be removed from LoopInfo. If this can not be done for some reason,
   then the optimization is *required* to preserve the static
   reachability of the loop.
   
 
 Loop Simplify Form
 ==================
 
-TBD
+The Loop Simplify Form is a canonical form that makes
+several analyses and transformations simpler and more effective.
+This loop is ensured by the LoopSimplify (`-loop-simplify`) pass
+and is automatically added by the pass managers when scheduling
+a LoopPass. This pass is implemented in
+`LoopInfo.h http://llvm.org/doxygen/LoopSimplify_8h_source.html`_.
+When it is successful, the loop has:
+
+* A preheader.
+* A single backedge (which implies that there is a single latch).
+* Dedicated exits. That is, no exit block for the loop
+  has a predecessor that is outside the loop. This implies
+  that all exit blocks are dominated by the loop header.
 
 
 Loop Closed SSA (LCSSA)
 =======================
 
 TBD
 
 "More Canonical" Loops
 ======================
 
 TBD

llvm/include/llvm/Transforms/Utils/LoopSimplify.h

 //===- LoopSimplify.h - Loop Canonicalization Pass --------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs several transformations to transform natural loops into a
 // simpler form, which makes subsequent analyses and transformations simpler and
-// more effective.
+// more effective. A summary of this pass is documented in
+// https://llvm.org/docs/LoopTerminology.html#loop-simplify-form
 //
 // Loop pre-header insertion guarantees that there is a single, non-critical
 // entry edge from outside of the loop to the loop header.  This simplifies a
 // number of analyses and transformations, such as LICM.
 //
 // Loop exit-block insertion guarantees that all exit blocks from the loop
 // (blocks which are outside of the loop that have predecessors inside of the
 // loop) only have predecessors from inside of the loop (and are thus dominated