Describe resticted form of loops in the new loop terminogy documentation

[reames]

Summary

What do folks think of the reframing?

[reames]

Thought of a cleaner way to describe it.

[reames]

Describe a few more restricted forms.

[jdoerfert]

docs/LoopTerminology.rst

152

Loops, assuming "natural loops identified by LoopInfo", can always be identified/distinguished by their header blocks regardless of the backedges. The situation is different for irreducible loops though.

Maybe I misunderstood what you wanted to say. Can you clarify, give an example?

[Meinersbur]

docs/LoopTerminology.rst

142–143

I don't get this. Where can these predicates be used? More importantly, which pass ensures the restricted/normal/canonical forms?

I'd not describe a restricted loop forms in terms of an API call. That's what the merthod documentation/doxygen is for. If you are not a frequent user of the Loop class, it is not obvious what it means when e.g. getLoopLatch() return nullptr. The naive interpretation is "there is not latch". Rather it should be described as property of the CFG).

164

No; LoopSimplifyPass must have been added before or simplifyLoop run on it manually.

[reames]

docs/LoopTerminology.rst

142–143

Paragraph A - Many passes bailout with these predicates. Mostly ensured by LoopSimplify, but other passes help too.

Paragraph B - I agree that the doxygen should have some of this, but the implications seem like possible overkill. I could be convinced that this needs to be rewritten as a comment patch though, what do others think?

152

Yep, this was a mistaken assumption on my part. I'll rephrase along the lines of https://reviews.llvm.org/D65299, once we're happy with the wording there.

164

Correct, but isn't it generally reasonable to assume that has happened by the point a loop pass runs? I'll admit, my wording was influenced by how things used to work in the old pass manager. Any suggestions on reframing?

[Meinersbur]

docs/LoopTerminology.rst

142–143

I think this is specific to pass/analysis implementations and does not belong into a document about loop terminology. Each transformation/pass should document its conditions, which may or may not include some of the ones described here.

I'd put about how to check for frequently used correctness conditions into the loop pass section of WritingAnLLVMPass, if at all. In this document, I'd describe the loop normal forms we have (LoopSimplify, LoopRotate, IndVarSimplify).

164

Loop normal forms are not implicit. It must be ensured by the pass (either by calling simplifyLoop or in the old pass manager this was possible by depending on e.g. LoopSimplify) or when adding the pass to the LoopPassManager (which might have been done already with some LoopPassManagers in the default pipeline, but this also depends on the position in the pipeline). At least to me this wording gives the impression that there is nothing to do if my pass depends on this condition.

173

Could you mention the reason why it is not a good idea to transform loops to make this hold?

docs/LoopTerminology.rst

* LoopInfo provides an interface for enumerating all top level loops
   walk the tree of sub-loops rooted in that top level loop.
 
 * 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:
 Loop Simplify Form
 ==================
 
-TBD
-
+The full generality of loops involves a lot of corner-cases which are not
+core to the transforms we generally wish to perform.  To simplify transform
+passes, we frequently restrict them to loops in what we term "Loop Simplify
+Form".  As you may be able to guess from the name, there is a LoopSimplify
+pass which attempts to normalize loops into this form.
+
+Loops in "Loop Simplify Form" are known to have the following properties:
+
+* A "preheader" block must exist.  This ensures that there is a single,
+  non-critical entry edge from outside of the loop to the loop header, and
+  thus that there is a single loop predeccesor block.
+
+* The loop must have exactly one backedge.  This also ensures there is exactly
+  one latch block.  As a result of this, two loops in loop simplify form can
+  be distinguished by their header block.  There can not exist a nested loop
+  which shares the same header if the loop contains only one backedge.
+
+* Dedicated exit blocks.  All exit blocks of the loop may only have
+  preccessors which are within the loop.  This ensures that exit blocks are
+  dominated by the loop header.  It does not guarantee that all exit blocks
+  are distinct.  That is, it allows multiple exiting edges from a single
+  loop to share an exit block,
+ 
+Note that loop simplify form makes no guarantees about the number or
+placement of exiting blocks.
+
+Also note that the component properties can be tested individually and
+it is considered best practice to use the narrowest bailout the transform
+actually requires for correctness.
 
 Loop Closed SSA (LCSSA)
 =======================
 
 TBD
 
 "More Canonical" Loops
 ======================
 
 TBD

docs/Passes.rst

 ``-loop-rotate``: Rotate Loops
 ------------------------------
 
 A simple loop rotation transformation.
 
 ``-loop-simplify``: Canonicalize natural loops
 ----------------------------------------------
 
-This pass performs several transformations to transform natural loops into a
+This pass attempts several transformations to transform natural loops into a
 simpler form, which makes subsequent analyses and transformations simpler and
-more effective.
-
-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 :ref:`LICM <passes-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 by the loop
-header).  This simplifies transformations such as store-sinking that are built
-into LICM.
-
-This pass also guarantees that loops will have exactly one backedge.
+more effective.  That form is described as
+:ref:`Loop Simplify Form <loop-simplify-form>`.
 
 Note that the :ref:`simplifycfg <passes-simplifycfg>` pass will clean up blocks
 which are split out but end up being unnecessary, so usage of this pass should
 not pessimize generated code.
 
 This pass obviously modifies the CFG, but updates loop information and
 dominator information.