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

148

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

138–139

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

160

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

[reames]

docs/LoopTerminology.rst

138–139

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?

148

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.

160

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

138–139

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

160

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.

169

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
-==================
-
-TBD
-
+.. _restricted_loop_forms:
+Restricted Loop Forms
+=====================
+
+The full generality of loops involves a lot of corner-cases which are not
+core to the transforms we generally wish to perform.  Rather than a single
+catch all restriction, we have a number of fine grained predicates which
+can be uses as preconditions for loop transforms.  
+
+* getLoopPreheader() != nullptr.  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.
+
+* getLoopLatch() != nullptr. For there to be a single latch, the loop must
+  have exactly one backedge.  Two loops, each with a single backedge, 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.
+
+* hasDedicatedExits().  All exit blocks of the loop may only have
+  predecessors 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,
+
+* isLoopSimplifyForm().  Shorthand for all of the above three conditions.
+  Use of this predicate is discouraged.  It is considered best practice to
+  use the narrowest bailout the transform actually requires for correctness.
+  
+It is generally reasonable to expect the above properties hold for loops of
+interest when a LoopPass runs inside of the LoopPassManager.  Additionally,
+there are further restrictions which apply to some subset of a loops, but are
+not generally reasonable to expect for all loops of interest.
+
+* getExitingBlock() != nullptr.  Implies there is a single exiting block from
+  the loop.  This does not necessarily have to be the latch block.
+  Historically, many LLVM loop transforms were restricted to only handle loops
+  of this form, but many have been updated, and writing new ones with this
+  restriction is discouraged.
+
+* getExitingBlock() != nullptr && getLatchBlock() == getExitingBlock().
+  Implies there is a single exiting block which is also the latch.  This is
+  classic bottom tested single exit loop.
+
+* isCanonical(&).  Indicates there is an induction variable which controls
+  the (conditional) latch block and is an integer value which starts at zero
+  and advances by one on each iteration.  In practice, this is not true of
+  most loops as we do not canonicalize into this form.
 
 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.  When successful, the transform ensures the existence of a
+preheader, a single backedge, and dedicated exit blocks.  See 
+:ref:`Restricted Loop Forms <_restricted_loop_forms>` for details on each of
+these. Note that loop simplify form makes no guarantees about the number or
+placement of exiting blocks.
 
 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.