[LCSSA] Doc for special treatment of PHIs

[baziotis]

Summary

Add comment and doc that the point of use in PHI nodes is special.

[baziotis]

llvm/lib/Transforms/Utils/LCSSA.cpp

167–173

Ah, I just saw that. Do you want me to put it in a separate diff ?

[Meinersbur]

The additional test might be useful though.

llvm/lib/Transforms/Utils/LCSSA.cpp

118–119

This is not specific to LCSSA, but a general rule: The point of use of an incoming value is its incoming block. That is, the definition (the I) must dominate UserBB (and not be basic block where the PHI is located). As a consequence, a use of the PHI in the exit block of the loop is inside the loop.

This becomes more obvious by MLIR's basic block arguments: the basic block that branches to the destination specifies the arguments for the "PHI" basic block parameters.

This additional comment makes it more complicated and special than it is.

167–173

What does the comment addition intend to explain? Technically, not the ExitBB must be dominated by I, but its predecessors.

208–214

Same comment as before applies.

[baziotis]

llvm/lib/Transforms/Utils/LCSSA.cpp

118–119

Most of what you said arises, IIUC, from the dominance property of SSA and makes sense. In particular:
"If x is used in the ith entry of a PHI in a block B, then the ith predecessor of B should dominate B" (I have seen this being
stated as every predecessor of B..., which complicates the understanding).

But I didn't understand that this implies: "The point of use of an incoming value is its incoming block."
I have never come across this anywhere and now I specifically searched for it and I couldn't find it. Is there any reference ?
If someone doesn't know about that, such code is confusing.
I'd also like to add a small mention in the LCSSA doc.

167–173

True, but it's implied from the fact that I dominates ExitBB (which we know is true at this point because we can check above
and see that ExitBB's are picked based on that).
This comment intends to explain "why can I add from every predecessor?" or "why is I defined in all the predecessors?". That's not
as tricky as the other one, I could just remove it.

[Meinersbur]

Some resources that might help:

https://reviews.llvm.org/D18443
https://lists.llvm.org/pipermail/llvm-dev/2016-February/095964.html
https://github.com/llvm/llvm-project/commit/ff379b69b2f82c9ca9b955b0458bb1aba85b9b85
https://llvm.org/docs/LangRef.html#id311

llvm/lib/Transforms/Utils/LCSSA.cpp

118–119

But I didn't understand that this implies: "The point of use of an incoming value is its incoming block."

My statement is somewhat incorrect, the "use" of a value by a PHI is its incoming edge:

https://llvm.org/docs/LangRef.html#phi-instruction

For the purposes of the SSA form, the use of each incoming value is deemed to occur on the edge from the corresponding predecessor block to the current block.

For practical purposes (e.g. to check dominance requirements), it is easier to view the incoming block as where the use occurs, as edges do not contain code itself.

This is a common technique, not just for LCSSA, such as in:
https://github.com/llvm/llvm-project/blob/c565f09f4b0d908f51aaf4a841285f39ef93bc8c/llvm/lib/Analysis/LoopInfo.cpp#L434
https://github.com/llvm/llvm-project/blob/c565f09f4b0d908f51aaf4a841285f39ef93bc8c/llvm/lib/CodeGen/CodeGenPrepare.cpp#L1173
https://github.com/llvm/llvm-project/blob/4aa97e3dacf3bdf5636fbf89dd8c64f1e4648065/polly/lib/Support/ScopHelper.cpp#L665

167–173

To be useful, the comment should elaborate more on that.

That ExitBB is dominated by I is checked at the beginning of the loop (line #166). 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 requirement.

I think you want and answer to the "This implies ..." part?

[baziotis]

Some resources that might help:

Thanks, I totally missed that it is in the langref. Off-topic: In the cases targeted by that diff / fix to the verifier, I think it is also interesting to consider that PHI's are evaluated in parallel upon entry to a BB.

llvm/lib/Transforms/Utils/LCSSA.cpp

118–119

Thanks for the feedback, so this is not something imposed by SSA, just something that happens to be useful. Good.
I think it's better to shorten the comment and I'll move some of it in the LCSSA doc.

167–173

I'm not sure whether it should be that verbose to be useful (e.g. I had never read LCSSA and that part was quite clear when I realized that I dominates ExitBB). No problem though, I'm adding it.

[baziotis]

Shortened comments and moved a more detailed explanation in loop terminology/LCSSA doc.

[Meinersbur]

llvm/docs/LoopTerminology.rst

175

specifically at its exit blocks

This wording is somewhat imprecise (where is 'at'? an exit block is after the loop), Suggestion: "PHI nodes with just a single incoming value/block are added into each of the loop's exit blocks ..."

223–225

The edge is clearly outside the loop, since when the control-flow uses it, it will not be looping anymore.

Treating the exiting block as user moves the use into the loop. For the purpose of LCSSA, this is exactly be what we want, since ensures all values that are defined in a loop are also only used in the loop. Could you move that part to the following paragraph to separate its from the strict formalism?

llvm/lib/Transforms/Utils/LCSSA.cpp

171

[grammar] "the the"

[baziotis]

llvm/docs/LoopTerminology.rst

175

Ok, let's remove "at the end of the loop". FWIW, I tried to avoid details here because an exit block can have multiple predecessors and some of them might be outside the loop. And this is still the start of the explanation.

223–225

Hmm, it seems to me that this will throw people off. It is easy to think "if the edge is considered outside how do you consider the use inside?" Let's assume that we answer that with "it works for LCSSA's purpose". But then "this is used all over LLVM, not just LCSSA". The whole reasoning seems flawed and like a hack. I'll retry anyway.

(Note that this part of the paragraph tries to answer what the start of the paragraph questions; if I move it, I'll have to rewrite all of it, which I'll do).

[baziotis]

Addressed comments.

[baziotis]

llvm/docs/LoopTerminology.rst

332

Hopefully the combination of this footnote with the last changes is a good result. First of all, it's not the place of the LCSSA doc to explain why the rest of LLVM uses this convention, yet I think this footnote adds value. Second, now the text above I think is clear in what happens with the usages in PHIs: both definition is referenced and convention is explained. Please let me know what you think.

336–340

This comment about liveness helps me very much understand this convention, I hope I have understood it's on point.

[Meinersbur]

llvm/docs/LoopTerminology.rst

175

verb before "single" missing?

223–225

Note that treating the use to occur in the incoming block just "overapproximates" the number of uses. The incoming block could branch to a different block. In that case the incoming value hasn't been uses, but there is no side-effect(*).

(*) Theoretically it could extend the lifetime of that value, but we do not compute lifetimes in LCSSA.

338–339

Mmmh, more precisely, the dominance frontier will not allow uses of the value past it, unless it is passed on by a PHI node. Mem2Reg tries to minimize the number of PHIs, only adding them at dominance frontiers, but is not strictly required to (I am not sure whether the current implementation does). With LCSSA, we intentionally add PHIs even though we are not crossing a dominance frontier.

I.e. it's not the PHI that kills a value and it is structurally valid (although optimizable) to use PHI as well as the incoming value as long as the dominance requirement is fulfilled. That is, both lifetimes may overlap (however if crossing a loop, that would obviously not be LCSSA normal form anymore).

[baziotis]

llvm/docs/LoopTerminology.rst

175

Yeah thanks. Actually the best place is probably after "PHI nodes" i.e. "PHI nodes are inserted"

223–225

Oh that's another very helpful way to think about this, thanks!

338–339

Yes, I totally agree! Yes formally one is allowed to re-use the value if it dominates the block, but if e.g. a human was hand-writing the
code, they wouldn't probably use both values: Either they'd use the value because it dominates or they'd need to put a PHI (which
would kill in their head the previous value). Even if they put an artificial PHI for some reason (e.g. LCSSA), they would still probably
not use the previous value, but instead the PHI.

Bottom-line, intuitively, the human would consider the value "live" and / or "used" up to the predecessor block, which is why IMHO this analogy is helpful for intuition.

That said, if you like the analogy, I still have to rewrite that somehow, on the one hand avoiding much formal details (because the goal of this is intuition) OTOH without writing incorrect things since this is now incorrect. How does that sound?

[Meinersbur]

llvm/docs/LoopTerminology.rst

338–339

The analogy is ok, when made clear that this is not a strict requirement, but just a goal/intention/idealization.

[baziotis]

That might be too big of a footnote and it might even be more suitable to be added in the phi doc in the LangRef. Nevertheless, it feels complete and valuable now :)

[Meinersbur]

LGTM

llvm/docs/LoopTerminology.rst

336

[typo] incombing

[baziotis]

Small fixes

[baziotis]

Remove unnecessary text

llvm/docs/LoopTerminology.rst

 .. _loop-terminology-lcssa:
 
 Loop Closed SSA (LCSSA)
 =======================
 
 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
 
     c = ...;
     for (...) {
       if (c)
         X1 = ...
       else

 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:`-lcssa <passes-lcssa>`)
 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 <passes-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 <https://llvm.org/docs/LangRef.html#id311>`_:
+"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.
 
 First of all, a simple observation is that if one needs to see all
 the outside users, they can just iterate over all the (loop closing)
 PHI nodes in the exit blocks (the alternative would be to
 scan the def-use chain [#def-use-chain]_ of all instructions in the loop).
 

 and which of these two llvm::Instructions you pass to it disambiguates
 the context / scope / relative loop.
 
 .. rubric:: Footnotes
 
 .. [#lcssa-construction] To insert these loop-closing PHI nodes, one has to
   (re-)compute dominance frontiers (if the loop has multiple exits).
 
 .. [#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
   in an internal data structure.
 
 "More Canonical" Loops
 ======================
 
 .. _loop-terminology-loop-rotate:
 
 Rotated Loops
 -------------
 
 Loops are rotated by the LoopRotate (:ref:`loop-rotate <passes-loop-rotate>`)
 pass, which converts loops into do/while style loops and is
 implemented in
 `LoopRotation.h <https://llvm.org/doxygen/LoopRotation_8h_source.html>`_.  Example:

llvm/lib/Analysis/LoopInfo.cpp

for (const Instruction &I : BB) {
     // optimizations, so for the purposes of considered LCSSA form, we
     // can ignore them.
     if (I.getType()->isTokenTy())
       continue;
 
     for (const Use &U : I.uses()) {
       const Instruction *UI = cast<Instruction>(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<PHINode>(UI))
         UserBB = P->getIncomingBlock(U);
 
       // Check the current block, as a fast-path, before checking whether
       // the use is anywhere in the loop.  Most values are used in the same
       // block they are defined in.  Also, blocks not reachable from the
       // entry are special; uses in them don't need to go through PHIs.
       if (UserBB != &BB && !L.contains(UserBB) &&

llvm/lib/Transforms/Utils/LCSSA.cpp

while (!Worklist.empty()) {
     const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];
 
     if (ExitBlocks.empty())
       continue;
 
     for (Use &U : I->uses()) {
       Instruction *User = cast<Instruction>(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<PHINode>(User))
         UserBB = PN->getIncomingBlock(U);
 
       if (InstBB != UserBB && !L->contains(UserBB))
         UsesToRewrite.push_back(&U);
     }
 
     // If there are no uses outside the loop, exit with no change.
     if (UsesToRewrite.empty())
       continue;
for (BasicBlock *ExitBB : ExitBlocks) {
       // If we already inserted something for this BB, don't reprocess it.
       if (SSAUpdate.HasValueForBlock(ExitBB))
         continue;
       Builder.SetInsertPoint(&ExitBB->front());
       PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
                                       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);
 
         // If the exit block has a predecessor not within the loop, arrange for
         // the incoming value use corresponding to that predecessor to be
         // rewritten in terms of a different LCSSA PHI.
         if (!L->contains(Pred))
           UsesToRewrite.push_back(
               &PN->getOperandUse(PN->getOperandNumForIncomingValue(
for (BasicBlock *ExitBB : ExitBlocks) {
       if (auto *OtherLoop = LI.getLoopFor(ExitBB))
         if (!L->contains(OtherLoop))
           PostProcessPHIs.push_back(PN);
     }
 
     // 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<Instruction>(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<PHINode>(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<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
         UseToRewrite->set(&UserBB->front());
         continue;
       }
 
       // If we added a single PHI, it must dominate all uses and we can directly
       // rename it.
       if (AddedPHIs.size() == 1) {