Index: docs/LoopTerminology.rst =================================================================== --- docs/LoopTerminology.rst +++ docs/LoopTerminology.rst @@ -129,11 +129,39 @@ 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) ======================= Index: docs/Passes.rst =================================================================== --- docs/Passes.rst +++ docs/Passes.rst @@ -806,21 +806,10 @@ ``-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. That form is described as +:ref:`Loop Simplify Form `. 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