This is an archive of the discontinued LLVM Phabricator instance.

[LoopTerminology] Loop Simplify Form
ClosedPublic

Authored by baziotis on Feb 21 2020, 3:13 PM.

Diff Detail

Event Timeline

baziotis created this revision.Feb 21 2020, 3:13 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2020, 3:13 PM

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

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 added inline comments.Feb 21 2020, 3:47 PM
llvm/docs/LoopTerminology.rst
147–149

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

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 marked 2 inline comments as done.Feb 21 2020, 4:09 PM

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–149

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 added a subscriber: fhahn.Feb 22 2020, 12:48 PM

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 added a comment.EditedFeb 22 2020, 1:11 PM

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.

This comment was removed by baziotis.
Meinersbur added inline comments.Feb 22 2020, 5:58 PM
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 added a subscriber: nikic.Feb 23 2020, 1:10 AM
nikic added inline comments.
llvm/docs/LoopTerminology.rst
152

See also D72519...

baziotis marked 2 inline comments as done.Feb 23 2020, 3:02 AM
baziotis added inline comments.
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 added inline comments.Feb 23 2020, 3:49 PM
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 marked an inline comment as done.Feb 23 2020, 4:03 PM
baziotis added inline comments.
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 updated this revision to Diff 246130.Feb 23 2020, 4:14 PM
baziotis edited the summary of this revision. (Show Details)

Addressed comments.

baziotis marked an inline comment as done.Feb 23 2020, 4:16 PM
baziotis added inline comments.
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 accepted this revision.Feb 24 2020, 11:45 AM
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).

This revision is now accepted and ready to land.Feb 24 2020, 11:45 AM

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 updated this revision to Diff 246322.Feb 24 2020, 3:00 PM
  • Link from one to the other in LoopSimplify.h and LoopTerminology.rst
baziotis marked 2 inline comments as done.Feb 24 2020, 3:02 PM
baziotis added inline comments.
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 ↗(On Diff #246322)

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 added inline comments.Feb 24 2020, 4:22 PM
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 ↗(On Diff #246322)

Whatever you think is more appropriate.

baziotis marked an inline comment as done.Feb 25 2020, 4:49 AM
baziotis added inline comments.
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 updated this revision to Diff 246416.Feb 25 2020, 4:50 AM

Aligned info in LoopSimplify.h with the LoopTerminology.

Meinersbur added inline comments.Feb 25 2020, 10:18 AM
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 marked 2 inline comments as done.Feb 25 2020, 12:20 PM
baziotis added inline comments.
llvm/docs/LoopTerminology.rst
149

Haha yes. :)

152

Ok, good.

baziotis updated this revision to Diff 246554.Feb 25 2020, 1:09 PM

Add cross-references.

Meinersbur accepted this revision.Feb 25 2020, 3:41 PM

LGTM. Do you want me to commit for you?

LGTM. Do you want me to commit for you?

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

Meinersbur requested changes to this revision.Feb 25 2020, 7:40 PM

[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.

This revision now requires changes to proceed.Feb 25 2020, 7:40 PM
baziotis updated this revision to Diff 246649.Feb 26 2020, 1:44 AM
baziotis marked an inline comment as done.

Fixed link

Meinersbur accepted this revision.Feb 26 2020, 6:34 PM
This revision is now accepted and ready to land.Feb 26 2020, 6:34 PM
This revision was automatically updated to reflect the committed changes.