Index: docs/LoopTerminology.rst =================================================================== --- docs/LoopTerminology.rst +++ docs/LoopTerminology.rst @@ -129,11 +129,53 @@ 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) ======================= Index: docs/Passes.rst =================================================================== --- docs/Passes.rst +++ docs/Passes.rst @@ -806,21 +806,13 @@ ``-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 `. - -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 ` pass will clean up blocks which are split out but end up being unnecessary, so usage of this pass should