[RLEV] Pick a correct insert point when incoming instruction is itself a phi node

[reames]

Summary

This fixes https://github.com/llvm/llvm-project/issues/57336. It was exposed by a recent SCEV change, but appears to have been a long standing issue.

Note that the whole insert into the loop instead of a split exit edge is slightly contrived to begin with; it's there solely because IndVarSimplify preserves the CFG.

[uabelho]

Thanks, I've verified that this solves the problem I saw in
https://github.com/llvm/llvm-project/issues/57336
as well as my original unreduced reproducer.

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Any reason we don't just use PN->getIncomingBlock(i)->getTerminator() as the insertion point? That seems like a more obvious place to materialize an edge value.

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll

188

Can you please return the value from the function? The problem is a bit hard to understand if the RLEV results gets optimized away.

[reames]

Address review comment.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

I'd been trying for a minimal fix. Do you mind if we land this, and then do a follow up change as you suggest? It'll cause significant test diffs which I think obscure the (rather narrow) impact of the fix.

[nikic]

LG

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Sure

[reames]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Went to do this in a follow up, and realized it's more complicated than it sounds.

Since a loop can have multiple exiting blocks which share a single exit block, there is no single source for the exiting edge. Instead, we'd have to either a) duplicate the expansion or b) find a common dominating point. The current code effectively does the later, and leaves the decision on whether to duplicate in order to sink to later code.

(Remember: SCEV expander reuses expressions, so expanding the same expression at the same point multiple times only results in one expansion.)

It's not entirely clear to me we *should* do running RLEV when we can't sink, but it's definitely not a straight forward NFC any more.

Unless you feel strongly about this, I'm not going to follow up further.

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Oh, that makes sense. It's fine to leave it as is then.

What we should be able to do is require that the loop has dedicated exits (which is part of loop simplify, and as such a prerequisite for indvars anyway), in which case placing the expansion in the exit and replacing the lcssa phi node should be fine (right?)

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Eh, ignore my last comment, that's just wrong. Dedicated exits don't forbid having multiple incoming edges from the same loop.

[reames]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

I think this should work. That would imply the multiple entry phi handling in this code is redundant and could be simplified away as well.

[reames]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1400

Amusingly, I made the same mistake in my response.

[yrouban]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1398–1400

Would it be better to fix SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *IP, bool Root) so it fixed IP in the same way? It would fix all its users.

[reames]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1398–1400

No. any routine given an insertion point should use it. It might make sense to add an *assert* that the insertion point is sane, but mutating the insertion point explicitly would be quite confusing.

[yrouban]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1398–1400

Ok, but in this particular case the insertion point can be adjusted by hoisting in SCEVExpander::expand(). In other words the insertion point passed as argument is not final.

llvm/lib/Transforms/Utils/LoopUtils.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
 
         // Note that we must not perform expansions until after
         // we query *all* the costs, because if we perform temporary expansion
         // inbetween, one that we might not intend to keep, said expansion
         // *may* affect cost calculation of the the next SCEV's we'll query,
         // and next SCEV may errneously get smaller cost.
 
         // Collect all the candidate PHINodes to be rewritten.
-        RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost);
+        Instruction *InsertPt =
+          (isa<PHINode>(Inst) || isa<LandingPadInst>(Inst)) ?
+          &*Inst->getParent()->getFirstInsertionPt() : Inst;
+        RewritePhiSet.emplace_back(PN, i, ExitValue, InsertPt, HighCost);
       }
     }
   }
 
   // TODO: evaluate whether it is beneficial to change how we calculate
   // high-cost: if we have SCEV 'A' which we know we will expand, should we
   // calculate the cost of other SCEV's after expanding SCEV 'A', thus
   // potentially giving cost bonus to those other SCEV's?

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll

 loop:
   %indvar = add i32 %phi_indvar, 1
   br label %header
 
 exit:
   ret i32 %phi_indvar
 }
 
+define i16 @pr57336(i16 %end, i16 %m) mustprogress {
+; CHECK-LABEL: @pr57336(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INC8:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[INC8]], 1
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[INC8]], [[M:%.*]]
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i16 [[MUL]], [[END:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[CRIT_EDGE:%.*]], label [[FOR_BODY]]
+; CHECK:       crit_edge:
+; CHECK-NEXT:    [[TMP0:%.*]] = call i16 @llvm.smax.i16(i16 [[END]], i16 -1)
+; CHECK-NEXT:    [[SMAX:%.*]] = add nsw i16 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i16 [[SMAX]], 0
+; CHECK-NEXT:    [[UMIN:%.*]] = zext i1 [[TMP1]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i16 [[SMAX]], [[UMIN]]
+; CHECK-NEXT:    [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[M]], i16 1)
+; CHECK-NEXT:    [[TMP3:%.*]] = udiv i16 [[TMP2]], [[UMAX]]
+; CHECK-NEXT:    [[TMP4:%.*]] = add i16 [[TMP3]], [[UMIN]]
+; CHECK-NEXT:    ret i16 [[TMP4]]
+;
+entry:
+  br label %for.body
+
+for.body:
+  %inc8 = phi i16 [ %inc, %for.body ], [ 0, %entry ]
+  %inc137 = phi i32 [ %inc1, %for.body ], [ 0, %entry ]
+  %inc1 = add nsw i32 %inc137, 1
+  %inc = add nsw i16 %inc8, 1
+  %mul = mul nsw i16 %m, %inc8
+  %cmp.not = icmp slt i16 %end, %mul
+  br i1 %cmp.not, label %crit_edge, label %for.body
+
+crit_edge:
+  %inc137.lcssa = phi i32 [ %inc137, %for.body ]
+  %conv = trunc i32 %inc137.lcssa to i16
+  ret i16 %conv
+}