Index: llvm/docs/LoopTerminology.rst =================================================================== --- llvm/docs/LoopTerminology.rst +++ llvm/docs/LoopTerminology.rst @@ -169,11 +169,13 @@ 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 [#lcssa-construction]_. -In particular, consider the following loop: +at the end of the loop (specifically at its exit blocks) for all values +that are live across the loop boundary [#lcssa-construction]_ +in order to "close" these values inside it. In particular, consider the +following loop: .. code-block:: C @@ -214,6 +216,19 @@ After the loop optimizations are done, these extra phi nodes will be deleted by :ref:`-instcombine `. +Note that an exit block is outside of a loop, so how can such a phi "close" +the value inside the loop since it uses it outside of it ? For phi nodes, as +`mentioned in the LangRef `_: +"the use of each incoming value is deemed to occur on the edge from the +corresponding predecessor block to the current block". To that end, +formally the use truly happens at the boundary of the loop and for +the purposes of LCSSA, we consider it happens inside it. + +However, an edge doesn't actually contain any IR, so in source code, +we have to choose a convention of whether the use happens in +the current block or in the respective predecessor. +The latter is chosen (across all LLVM source code) for practical purposes. + The major benefit of this transformation is that it makes many other loop optimizations simpler. Index: llvm/lib/Analysis/LoopInfo.cpp =================================================================== --- llvm/lib/Analysis/LoopInfo.cpp +++ llvm/lib/Analysis/LoopInfo.cpp @@ -431,6 +431,10 @@ for (const Use &U : I.uses()) { const Instruction *UI = cast(U.getUser()); const BasicBlock *UserBB = UI->getParent(); + + // For practical purposes, we consider that the use in a PHI + // occurs in the respective predecessor block. For more info, + // see the `phi` doc in LangRef and the LCSSA doc. if (const PHINode *P = dyn_cast(UI)) UserBB = P->getIncomingBlock(U); Index: llvm/lib/Transforms/Utils/LCSSA.cpp =================================================================== --- llvm/lib/Transforms/Utils/LCSSA.cpp +++ llvm/lib/Transforms/Utils/LCSSA.cpp @@ -111,6 +111,10 @@ for (Use &U : I->uses()) { Instruction *User = cast(U.getUser()); BasicBlock *UserBB = User->getParent(); + + // For practical purposes, we consider that the use in a PHI + // occurs in the respective predecessor block. For more info, + // see the `phi` doc in LangRef and the LCSSA doc. if (auto *PN = dyn_cast(User)) UserBB = PN->getIncomingBlock(U); @@ -160,7 +164,12 @@ I->getName() + ".lcssa"); // Get the debug location from the original instruction. PN->setDebugLoc(I->getDebugLoc()); - // Add inputs from inside the loop for this PHI. + + // Add inputs from inside the loop for this PHI. This is valid + // because `I` dominates `ExitBB` (checked above). This implies + // that every incoming block/edge is dominated by `I` as well, + // i.e. we can add uses of `I` to those incoming edges/append to the the incoming + // blocks without violating the SSA dominance property. for (BasicBlock *Pred : PredCache.get(ExitBB)) { PN->addIncoming(I, Pred); @@ -194,15 +203,19 @@ // Rewrite all uses outside the loop in terms of the new PHIs we just // inserted. for (Use *UseToRewrite : UsesToRewrite) { - // If this use is in an exit block, rewrite to use the newly inserted PHI. - // This is required for correctness because SSAUpdate doesn't handle uses - // in the same block. It assumes the PHI we inserted is at the end of the - // block. Instruction *User = cast(UseToRewrite->getUser()); BasicBlock *UserBB = User->getParent(); + + // For practical purposes, we consider that the use in a PHI + // occurs in the respective predecessor block. For more info, + // see the `phi` doc in LangRef and the LCSSA doc. if (auto *PN = dyn_cast(User)) UserBB = PN->getIncomingBlock(*UseToRewrite); + // If this use is in an exit block, rewrite to use the newly inserted PHI. + // This is required for correctness because SSAUpdate doesn't handle uses + // in the same block. It assumes the PHI we inserted is at the end of the + // block. if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { UseToRewrite->set(&UserBB->front()); continue;