Information taken from the Writing Loop Optimizations video and the LoopSimplify.h
Details
Diff Detail
Event Timeline
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? |
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.
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. |
llvm/docs/LoopTerminology.rst | ||
---|---|---|
152 | First of all, thanks for the explanations!
Yes, exactly!
Yes, my example was just to be sure we're talking for the same thing.
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 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. | |
152 |
Thank you, I added me as a subscriber so that if it gets accepted, I should go and change the doc. |
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.
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 |
If we change the definition of getLoopLatch(), we will have to change the definition of simplified form. |
llvm/docs/LoopTerminology.rst | ||
---|---|---|
152 |
Huh, ok.
Ok.
Indeed. |
llvm/docs/LoopTerminology.rst | ||
---|---|---|
156 | "no exit block for the loop" |
@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). |
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.
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. |
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? |
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. |
[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. |
Could you add that the LoopSimplify (-loop-simplify) pass ensures this form and is automatically added by the pass managers when scheduling a LoopPass?