Index: llvm/docs/LoopTerminology.rst =================================================================== --- llvm/docs/LoopTerminology.rst +++ llvm/docs/LoopTerminology.rst @@ -161,11 +161,94 @@ has a predecessor that is outside the loop. This implies that all exit blocks are dominated by the loop header. +.. _loop-terminology-lcssa: Loop Closed SSA (LCSSA) ======================= -TBD +A program is in Loop Closed SSA Form if it is in SSA form +and all values that are defined in a loop are used only inside +this loop. +Programs written in LLVM IR are always in SSA form but not necessarily +in LCSSA. To achieve the latter, single entry PHI nodes are inserted +at the end of the loops for all values that are live across the loop boundary. +In particular, consider the following loop: + +.. code-block:: C + + c = ...; + for (...) { + if (c) + X1 = ... + else + X2 = ... + X3 = phi(X1, X2); // X3 defined + } + + ... = X3 + 4; // X3 used, i.e. live + // outside the loop + +In the inner loop, the X3 is defined inside the loop, but used +outside of it. In loop closed SSA form, this would be represented like this: + +.. code-block:: C + + c = ...; + for (...) { + if (c) + X1 = ... + else + X2 = ... + X3 = phi(X1, X2); + } + X4 = phi(X3); + + ... = X4 + 4; + +This is still valid LLVM; the extra phi nodes are purely redundant, +but all LoopPass'es are required to preserve them. +This form is ensured by the LCSSA (:ref:`-loop-simplify `) +pass and is added automatically by the LoopPassManager when +scheduling a LoopPass. +After the loop optimizations are done, these extra phi nodes +will be deleted by :ref:`-instcombine `. + +The major benefit of this transformation is that it makes many other +loop optimizations simpler. +Consider for example +:ref:`-loop-unswitch ` ing the loop above. +Because it is in LCSSA form, we know that all uses of values defined +inside of the loop are used only by PHI nodes outside of it. +This means that we can just copy the loop and hack on the loop +closed PHI nodes, like so: + +.. code-block:: C + + for (...) { + c = ...; + if (c) { + for (...) { + if (true) + X1 = ... + else + X2 = ... + X3 = phi(X1, X2); + } + } else { + for (...) { + if (false) + X1' = ... + else + X2' = ... + X3' = phi(X1', X2'); + } + } + X4 = phi(X3, X3') + +If we did not have Loop Closed SSA form, we would have had to +do deep analysis of the control flow graph to figure out where +to place the X4 phi node. With it, we just loop for these +PHIs and update them. "More Canonical" Loops ====================== Index: llvm/docs/Passes.rst =================================================================== --- llvm/docs/Passes.rst +++ llvm/docs/Passes.rst @@ -711,6 +711,8 @@ In this case, the unconditional branch at the end of the first if can be revectored to the false side of the second if. +.. _passes-lcssa: + ``-lcssa``: Loop-Closed SSA Form Pass ------------------------------------- @@ -732,7 +734,8 @@ This is still valid LLVM; the extra phi nodes are purely redundant, and will be trivially eliminated by ``InstCombine``. The major benefit of this transformation is that it makes many other loop optimizations, such as -``LoopUnswitch``\ ing, simpler. +``LoopUnswitch``\ ing, simpler. You can read more in the +:ref:`loop terminology section for the LCSSA form `. .. _passes-licm: @@ -860,6 +863,8 @@ can lead to significant performance improvements. It uses :ref:`Dependence Analysis ` for proving the transformations are safe. +.. _passes-loop-unswitch: + ``-loop-unswitch``: Unswitch loops ----------------------------------