[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

299

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 ..."

344–346

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

299

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.

344–346

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

456

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.

460–464

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

297

verb before "single" missing?

344–346

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.

462–463

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

297

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

344–346

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

462–463

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

462–463

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

460

[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 LCSSA. To achieve the latter, for each value that is live across the
+loop boundary, single entry PHI nodes are inserted 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
 
     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>`.
 
-The major benefit of this transformation is that it makes many other
-loop optimizations simpler.
+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 <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". 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).
+Actually, the latter is chosen across all LLVM source
+code [#point-of-use-phis]_.
+
+The major benefit of LCSSA 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).
 
 Then, consider for example
 :ref:`-loop-unswitch <passes-loop-unswitch>` ing the loop above.

 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).
 
+.. [#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. It is also just an overapproximation of the actual
+  number of uses; the incoming block could branch to another block in which
+  case the value is not actually used but there are no side-effects (it might
+  increase its live range which is not relevant in LCSSA though).
+  Furthermore, we can gain some intuition if we consider liveness:
+  A PHI is *usually* inserted in the current block because the value can't
+  be used from this point and onwards (i.e. the current block is a dominance
+  frontier). It doesn't make sense to consider that the value is used in
+  the current block (because of the PHI) since the value stops being live
+  before the PHI. In some sense the PHI definition just "replaces" the original
+  value definition and doesn't actually use it. It should be stressed that
+  this analogy is only used as an example and does not pose any strict
+  requirements. For example, the value might dominate the current block
+  but we can still insert a PHI (as we do with LCSSA PHI nodes) *and*
+  use the original value afterwards (in which case the two live ranges overlap,
+  although in LCSSA (the whole point is that) we never do that).
+
+
 .. [#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
 ======================
 

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 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) {