[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

177–178

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

128–129

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.

177–178

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

214–220

Same comment as before applies.

[baziotis]

llvm/lib/Transforms/Utils/LCSSA.cpp

128–129

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.

177–178

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

128–129

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

177–178

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

128–129

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.

177–178

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 ↗

(On Diff #299601)

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 ↗

(On Diff #299601)

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

181

[grammar] "the the"

[baziotis]

llvm/docs/LoopTerminology.rst

175 ↗

(On Diff #299601)

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 ↗

(On Diff #299601)

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

457 ↗

(On Diff #300775)

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.

461–465 ↗

(On Diff #300775)

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 ↗

(On Diff #300775)

verb before "single" missing?

463–464 ↗

(On Diff #300775)

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

223–225 ↗

(On Diff #299601)

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.

[baziotis]

llvm/docs/LoopTerminology.rst

297 ↗

(On Diff #300775)

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

463–464 ↗

(On Diff #300775)

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?

223–225 ↗

(On Diff #299601)

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

[Meinersbur]

llvm/docs/LoopTerminology.rst

463–464 ↗

(On Diff #300775)

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

461 ↗

(On Diff #301381)

[typo] incombing

[baziotis]

Small fixes

[baziotis]

Remove unnecessary text

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();
+
+      // A PHI may already act as an LCSSA PHI (note that an LCSSA PHI
+      // is the only instruction that is outside the loop, uses a value
+      // from inside and does _not_ need a rewrite). To check that, we
+      // have to inspect its incoming blocks and not its parent block.
+      // If the incoming block for this use is inside the loop
+      // (which we check below), then this PHI acts as an LCSSA
+      // PHI; only for this use though e.g. this can exist:
+      //
+      // some.exit.block:
+      //   %x.not.lcssa = phi i32 [ %x, %inside.block ], [ %x, %outside.block]
+      //
+      // %x.not.lcssa acts as an LCSSA PHI for the first use of %x
+      // but not the second.
       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`.
       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(
                   PN->getNumIncomingValues() - 1)));
       }
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();
+
+      // A PHI may already act as an LCSSA PHI as explained in the gathering
+      // of uses to rewrite (note that here there are possibly other PHI's
+      // included when we added LCSSA PHI's in the exit blocks, after the
+      // gathering of uses)
       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) {

llvm/test/Transforms/LCSSA/test.ll

+; RUN: opt < %s -passes=lcssa,verify -S | FileCheck %s
+
+define void @foo(i1 %c) {
+entry:
+  br label %header
+
+header:
+  %x = add i32 1, 2
+  br i1 %c, label %latch, label %loop.exit
+
+latch:
+  br i1 %c, label %header, label %intermediate
+
+intermediate:
+; CHECK:    [[X_LCSSA:%.*]] = phi i32 [ %x, %latch ]
+  br label %loop.exit
+
+loop.exit:
+; CHECK:    [[X_NOT_LCSSA:%.*]] = phi i32 [ %x, %header ], [ [[X_LCSSA]], %intermediate ]
+;; %x.not.lcssa acts as a LCSSA PHI for the first use but not the second.
+  %x.not.lcssa = phi i32 [ %x, %header ], [ %x, %intermediate ]
+  ret void
+}