Index: llvm/docs/LoopTerminology.rst =================================================================== --- llvm/docs/LoopTerminology.rst +++ llvm/docs/LoopTerminology.rst @@ -291,10 +291,11 @@ 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 LCSSA. To achieve the latter, for each value that is live across the +loop boundary, single entry PHI nodes to each of the exit blocks +[#lcssa-construction]_ in order to "close" these values inside the loop. In particular, consider the following loop: .. code-block:: C @@ -336,6 +337,23 @@ 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 ? First of all, +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". Now, an +edge to an exit block is considered outside of the loop because +if we take that edge, it leads us clearly out of the loop. + +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. For LCSSA's purpose, +we consider the use happens in the latter (so as to consider the use inside). +[#point-of-use-phis]_ + +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. @@ -436,6 +454,15 @@ .. [#lcssa-construction] To insert these loop-closing PHI nodes, one has to (re-)compute dominance frontiers (if the loop has multiple exits). +.. [#point-of-use-phis] Considering the point of use of a PHI entry value + to be in the respective predecessor is a convention across the whole LLVM. + The reason is mostly practical; for example it preserves the dominance + property of SSA. Moreover, we can gain some intuition if we consider + liveness: A value is live up to the predecessor block because it + can't be used from the PHI and onwards (otherwise the PHI would not + be needed in the first place). Effectively, the PHI kills the incoming + value(s) and replaces them with a new definition. + .. [#def-use-chain] A property of SSA is that there exists a def-use chain for each definition, which is a list of all the uses of this definition. LLVM implements this property by keeping a list of all the uses of a Value 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 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;