[LCSSA] Re-use suitable PHI if available instead creating new ones.

[fhahn]

Summary

If ExitBB already contains a phi with a constant incoming value, re-use
it instead of creating a new phi. If the incoming value of the re-used
phi node is not yet in LCSSA form it will get formed in subsequent
iterations, like for newly created ones.

This means we won't end up with multiple LCSSA phi nodes when an
existing PHI can already be re-used. This is in particular relevant for
code that needs to re-build LCSSA for some values on demand, like
SCEVExpander.

This patch ensures that only be a single LCSSA phi will be created and
re-used when expanding the same expressions multiple times.

Fixes #57000.

[efriedma]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

Is the new code to prevent creating identical PHI nodes part of the fix, or just an optimization? It isn't obviously related.

[fhahn]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

Preventing identical phis is the main part of the fix. The issue is that currently scev expansion can create different LCSSA phis when expanding the same expression (since we changed scev to look through trivial phis)

If those are then used as incoming values for phis with multiple matching predecessors we create invalid ir .

[efriedma]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

I'm sorry, I really don't follow how having multiple PHI nodes that use the value messes up the algorithm. (If someone else does, feel free to take over reviewing...)

[fhahn]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

Sorry for the confusion. Having multiple multiple phi nodes for the same values isn't a problem for the LCSSA construction algorithm itself. For the LCSSA construction algorithm the change is purely an optimization.

The bug fix is that is also addresses a problem for a user of the construction algorithm (SCEVExpander). Creating duplicated phis when expanding the same expression multiple times can cause issues with uses of the expanded expressions.

In the added test case pr57000, IndVars updates the incoming values of an LCSSA phi node with multiple incoming edges from the same block. It expands the same SCEV expression once for each edge and expanding it requires creating new LCSSA phi nodes (using the construction algorithm,). With the patch, LCSSA expansion will return a single PHI, whereas before it would create duplicated phis for each expansion, resulting in a phi node with different incoming values for edges from the same block.

I hope this helps to clarify things a bit.

[fhahn]

ping :)

[fhahn]

ping :)

[efriedma]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

Dug a bit. I think I understand: rewriteLoopExitValues calls expandCodeFor in a loop. The way that loop is written, it implicitly assumes that if it calls expandCodeFor multiple times with the same operands, it will receive the same result. (Otherwise, it ends up setting the operands of the PHI it's rewriting to invalid values.)

There are other ways you could fix that particular issue. For example, we could just avoid repeated calls to expandCodeFor in rewriteLoopExitValues, which would be both faster, and more obviously correct.

---

I'm a little concerned that the current patch could end up iterating over ExitBB->phis() repeatedly, which would be effectively O(N^2).

[fhahn]

llvm/lib/Transforms/Utils/LCSSA.cpp

176

There are other ways you could fix that particular issue. For example, we could just avoid repeated calls to expandCodeFor in rewriteLoopExitValues, which would be both faster, and more obviously correct.

Solving this closer to SCEV expansion sounds good to me! I initially thought solving this more generally in LCSSA construction may be desirable, but the potential compile-time cost doesn't make it seem worth it and I cannot think of a way to avoid a scan of all phi nodes.

I put up D134739 as an alternative which extends SCEVExpander's logic to use the previous expansion result for LCSSA phis.

[spatel]

Should this patch be abandoned since D134739 was committed?

[fhahn]

Yep, this is no longer needed.

llvm/lib/Transforms/Utils/LCSSA.cpp

while (!Worklist.empty()) {
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
       if (SSAUpdate.HasValueForBlock(ExitBB))
         continue;
+
+      PHINode *PN = nullptr;
+      // If ExitBB already contains a phi with a constant incoming value, re-use
+      // it instead of creating a new phi.
+      for (PHINode &ExistingPN : ExitBB->phis()) {
+        if (ExistingPN.hasConstantValue() == I) {
+          PN = &ExistingPN;
+          // LCSSA construction code assumes the phi to be the first in the
+          // block.
+          PN->moveBefore(&ExitBB->front());
+          break;
+        }
+      }
       Builder.SetInsertPoint(&ExitBB->front());
-      PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
-                                      I->getName() + ".lcssa");
+      if (!PN) {
+        PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
         // Get the debug location from the original instruction.
         PN->setDebugLoc(I->getDebugLoc());
 
         // 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.
+        // 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
+        for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
+          // 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)));
+          if (!L->contains(PN->getIncomingBlock(I)))
+            UsesToRewrite.push_back(&PN->getOperandUse(I));
+        }
       }
 
       AddedPHIs.push_back(PN);
 
       // Remember that this phi makes the value alive in this block.
       SSAUpdate.AddAvailableValue(ExitBB, PN);
 
       // LoopSimplify might fail to simplify some loops (e.g. when indirect

llvm/test/Transforms/IndVarSimplify/lcssa-preservation.ll

 loop1.latch:
   %res.lcssa = phi i64 [ %res, %loop2 ]
   br i1 false, label %loop1, label %exit
 
 exit:
   %res.lcssa2 = phi i64 [ %res.lcssa, %loop1.latch ]
   ret i64 %res.lcssa2
 }
+
+; Check that it does not crash because the incoming values of an LCSSA phi are
+; equal.
+define void @pr57000(i64 %a) {
+; CHECK-LABEL: @pr57000(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_1_OUTER:%.*]]
+; CHECK:       loop.1.loopexit:
+; CHECK-NEXT:    br label [[LOOP_1_OUTER]]
+; CHECK:       loop.1.outer:
+; CHECK-NEXT:    br label [[LOOP_1:%.*]]
+; CHECK:       loop.1:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i64 [[A:%.*]], 2546175499358690212
+; CHECK-NEXT:    [[CMP_EXT:%.*]] = zext i1 [[CMP]] to i8
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1]], label [[LOOP_2_HEADER_PREHEADER:%.*]]
+; CHECK:       loop.2.header.preheader:
+; CHECK-NEXT:    [[CMP_LCSSA:%.*]] = phi i1 [ [[CMP]], [[LOOP_1]] ]
+; CHECK-NEXT:    [[CMP_EXT_LCSSA:%.*]] = phi i8 [ [[CMP_EXT]], [[LOOP_1]] ]
+; CHECK-NEXT:    br label [[LOOP_2_HEADER_OUTER:%.*]]
+; CHECK:       loop.2.header.outer:
+; CHECK-NEXT:    br label [[LOOP_2_HEADER:%.*]]
+; CHECK:       loop.2.header:
+; CHECK-NEXT:    switch i8 [[CMP_EXT_LCSSA]], label [[LOOP_1_LOOPEXIT:%.*]] [
+; CHECK-NEXT:    i8 -1, label [[LOOP_2_LATCH:%.*]]
+; CHECK-NEXT:    i8 1, label [[LOOP_2_LATCH]]
+; CHECK-NEXT:    i8 4, label [[LOOP_2_HEADER]]
+; CHECK-NEXT:    ]
+; CHECK:       loop.2.latch:
+; CHECK-NEXT:    [[CMP_TRUNC_LCSSA1:%.*]] = phi i1 [ [[CMP_LCSSA]], [[LOOP_2_HEADER]] ], [ [[CMP_LCSSA]], [[LOOP_2_HEADER]] ]
+; CHECK-NEXT:    call void @use(i1 [[CMP_TRUNC_LCSSA1]])
+; CHECK-NEXT:    br label [[LOOP_2_HEADER_OUTER]]
+;
+entry:
+  br label %loop.1
+
+loop.1:
+  %p.1 = phi i1 [ 0 , %entry ], [ %p.1, %loop.1 ], [ %p.2, %loop.2.header ]
+  %cmp = icmp sle i64 %a, 2546175499358690212
+  %cmp.ext = zext i1 %cmp to i8
+  br i1 %cmp, label %loop.1, label %loop.2.header
+
+loop.2.header:
+  %p.2 = phi i1 [ %p.1, %loop.1 ], [ %p.2, %loop.2.header ], [ %cmp, %loop.2.latch ]
+  %cmp.trunc = trunc i8 %cmp.ext to i1
+  switch i8 %cmp.ext, label %loop.1 [
+  i8 -1, label %loop.2.latch
+  i8 1, label %loop.2.latch
+  i8 4, label %loop.2.header
+  ]
+
+loop.2.latch:
+  call void @use(i1 %cmp.trunc)
+  br label %loop.2.header
+}
+
+declare void @use(i1)

llvm/test/Transforms/LoopUnroll/rebuild_lcssa.ll

 ; CHECK-NEXT:    indirectbr i8* undef, [label [[INNER2_LATCH]], label [[INNER3:%.*]], label %outer_latch]
 ; CHECK:       inner2_latch:
 ; CHECK-NEXT:    [[B]] = load i32, i32* undef, align 8
 ; CHECK-NEXT:    br label [[INNER2_INDIRECT_EXIT]]
 ; CHECK:       inner3:
 ; CHECK-NEXT:    [[A_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ], [ [[A]], [[INNER2_INDIRECT_EXIT]] ]
 ; CHECK-NEXT:    br i1 true, label [[OUTER_LATCH_LOOPEXIT:%.*]], label [[INNER3]]
 ; CHECK:       outer_latch.loopexit:
-; CHECK-NEXT:    [[A_LCSSA_LCSSA2:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]
 ; CHECK-NEXT:    [[A_LCSSA_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]
 ; CHECK-NEXT:    br label [[OUTER_LATCH:%.*]]
 ; CHECK:       outer_latch:
 ; CHECK-NEXT:    br label [[OUTER]]
 ;
 entry:
   br label %outer
 

llvm/test/Transforms/LoopVectorize/create-induction-resume.ll

 ; CHECK-NEXT:    [[L1_IV_NEXT]] = add nuw nsw i32 [[L1_IV]], 1
 ; CHECK-NEXT:    [[L1_EXIT_COND:%.*]] = icmp ult i32 [[L1_IV_NEXT]], [[L1_LIMIT:%.*]]
 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
 ; CHECK-NEXT:    [[INDUCTION_IV_NEXT]] = add i32 [[INDUCTION_IV]], [[TMP2]]
 ; CHECK-NEXT:    br i1 [[L1_EXIT_COND]], label [[L1_HEADER]], label [[L1_EXIT:%.*]]
 ; CHECK:       L1.early.exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       L1.exit:
-; CHECK-NEXT:    [[INDUCTION_IV_LCSSA3:%.*]] = phi i32 [ [[INDUCTION_IV]], [[L1_BACKEDGE]] ]
 ; CHECK-NEXT:    [[INDUCTION_IV_LCSSA1:%.*]] = phi i32 [ [[INDUCTION_IV]], [[L1_BACKEDGE]] ]
 ; CHECK-NEXT:    [[L1_EXIT_VAL:%.*]] = phi i32 [ [[L1_SUM_NEXT]], [[L1_BACKEDGE]] ]
 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
 ; CHECK:       L2.header.loopexit:
 ; CHECK-NEXT:    br label [[L2_HEADER_BACKEDGE:%.*]]
 ; CHECK:       L2.header:
 ; CHECK-NEXT:    switch i32 [[L2_SWITCH:%.*]], label [[L2_HEADER_BACKEDGE]] [
 ; CHECK-NEXT:    i32 8, label [[L2_EXIT:%.*]]

llvm/test/Transforms/LoopVectorize/skeleton-lcssa-crash.ll

 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_2]], label [[OUTER_LATCH:%.*]], label [[INNER_BB:%.*]]
 ; CHECK:       inner.bb:
 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP_3_PREHEADER:%.*]], label [[INNER_LATCH:%.*]]
 ; CHECK:       loop.3.preheader:
-; CHECK-NEXT:    [[L_1_LCSSA7:%.*]] = phi ptr [ [[L_1]], [[INNER_BB]] ]
 ; CHECK-NEXT:    [[L_1_LCSSA:%.*]] = phi ptr [ [[L_1]], [[INNER_BB]] ]
 ; CHECK-NEXT:    [[L_2_LCSSA:%.*]] = phi ptr [ [[L_2]], [[INNER_BB]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[N:%.*]], 1
 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP0]], 2
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
 ; CHECK:       vector.memcheck:
 ; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, ptr [[L_2_LCSSA]], i64 2
 ; CHECK-NEXT:    [[UGLYGEP3:%.*]] = getelementptr i8, ptr [[L_1_LCSSA]], i64 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[N]], 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[TMP1]], 4
-; CHECK-NEXT:    [[UGLYGEP6:%.*]] = getelementptr i8, ptr [[L_1_LCSSA7]], i64 [[TMP2]]
+; CHECK-NEXT:    [[UGLYGEP6:%.*]] = getelementptr i8, ptr [[L_1_LCSSA]], i64 [[TMP2]]
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ult ptr [[L_2_LCSSA]], [[UGLYGEP6]]
 ; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ult ptr [[UGLYGEP3]], [[UGLYGEP]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP0]], 2
 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP0]], [[N_MOD_VF]]
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]

 ; CHECK:       loop.2:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ [[INDVAR_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_1_HEADER]] ]
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1000, [[LOOP_1_HEADER]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_2]] ]
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add i64 [[IV_1]], -1
 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_2]], label [[LOOP_3_PH:%.*]]
 ; CHECK:       loop.3.ph:
-; CHECK-NEXT:    [[INDVAR_LCSSA1:%.*]] = phi i32 [ [[INDVAR]], [[LOOP_2]] ]
 ; CHECK-NEXT:    [[INDVAR_LCSSA:%.*]] = phi i32 [ [[INDVAR]], [[LOOP_2]] ]
 ; CHECK-NEXT:    [[IV_1_LCSSA:%.*]] = phi i64 [ [[IV_1]], [[LOOP_2]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[IV_1_LCSSA]], 4294967295
-; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[INDVAR_LCSSA1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[INDVAR_LCSSA]], -1
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], 1000
-; CHECK-NEXT:    [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[TMP2]], i32 1)
-; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[TMP2]], [[SMIN2]]
+; CHECK-NEXT:    [[SMIN1:%.*]] = call i32 @llvm.smin.i32(i32 [[TMP2]], i32 1)
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[TMP2]], [[SMIN1]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[TMP3]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], 1
 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP5]], 2
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
 ; CHECK:       vector.scevcheck:
 ; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[INDVAR_LCSSA]], -1
 ; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 1000
 ; CHECK-NEXT:    [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[TMP7]], i32 1)