[SCEV] Select between two equal values

[mkazantsev]

Summary

SCEV of expressions like 'select %cond, %X, %X' should be evaluated as SCEV of '%X'.

[sanjoy]

I'm not convinced SCEV is the best place to handle this -- by the time IR hits SCEV select A, B, B should already have been simplified to B. We do not handle "simple" patterns like br (xor C, true), label A, label B for the same reason.

If you *must* do this (and I'm not yet convinced that we must), I'd instead call SimplifyInstruction at a higher level (at createSCEV perhaps).

[mkazantsev]

Okay.

lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   // If it's not a loop phi, we can't handle it yet.
   return getUnknown(PN);
 }
 
 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
                                                       Value *Cond,
                                                       Value *TrueVal,
                                                       Value *FalseVal) {
+  // If the value does not depend on the condition, go down to it.
+  if (TrueVal == FalseVal)
+    return getSCEV(TrueVal);
+
   // Handle "constant" branch or select. This can occur for instance when a
   // loop pass transforms an inner loop and moves on to process the outer loop.
   if (auto *CI = dyn_cast<ConstantInt>(Cond))
     return getSCEV(CI->isOne() ? TrueVal : FalseVal);
 
   // Try to match some simple smax or umax patterns.
   auto *ICI = dyn_cast<ICmpInst>(Cond);
   if (!ICI)

test/Analysis/IVUsers/quadradic-exit-value.ll

 }
 
 ; PR15470: LSR miscompile. The test2 function should return '1'.
 ;
 ; SCEV does not know how to denormalize chained recurrences, so make
 ; sure they aren't marked as post-inc users.
 ;
 ; CHECK-LABEL: IV Users for loop %test2.loop
-; CHECK-NO-LCSSA: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us))<nuw><nsw>,+,33554432}<%test2.loop> (post-inc with loop %test2.loop) in    %f = ashr i32 %sext.us, 24
+; CHECK-NO-LCSSA: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us))<nsw>,+,33554432}<%test2.loop> (post-inc with loop %test2.loop) in    %f = ashr i32 %sext.us, 24
 define i32 @test2() {
 entry:
   br label %test2.loop
 
 test2.loop:
   %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test2.loop ]
   %inc11.us = add nsw i32 %inc1115.us, 1
   %cmp.us = icmp slt i32 %inc11.us, 2
   br i1 %cmp.us, label %test2.loop, label %for.end
 
 for.end:
   %tobool.us = icmp eq i32 %inc1115.us, 0
+  %sub.us = select i1 %tobool.us, i32 0, i32 1
+  %mul.us = shl i32 %inc1115.us, 24
+  %sub.cond.us = sub nsw i32 %inc1115.us, %sub.us
+  %sext.us = mul i32 %mul.us, %sub.cond.us
+  %f = ashr i32 %sext.us, 24
+  br label %exit
+
+exit:
+  ret i32 %f
+}
+
+; Demonstrate that if we select between two equal values, SCEV is able to
+; recognize a quadratic recurrence.
+;
+; CHECK-LABEL: IV Users for loop %test3.loop
+; CHECK-NO-LCSSA: %sext.us = {0,+,16777216,+,33554432}<%test3.loop> (post-inc with loop %test3.loop) in    %f = ashr i32 %sext.us, 24
+define i32 @test3() {
+entry:
+  br label %test3.loop
+
+test3.loop:
+  %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test3.loop ]
+  %inc11.us = add nsw i32 %inc1115.us, 1
+  %cmp.us = icmp slt i32 %inc11.us, 2
+  br i1 %cmp.us, label %test3.loop, label %for.end
+
+for.end:
+  %tobool.us = icmp eq i32 %inc1115.us, 0
   %sub.us = select i1 %tobool.us, i32 0, i32 0
   %mul.us = shl i32 %inc1115.us, 24
   %sub.cond.us = sub nsw i32 %inc1115.us, %sub.us
   %sext.us = mul i32 %mul.us, %sub.cond.us
   %f = ashr i32 %sext.us, 24
   br label %exit
 
 exit:
   ret i32 %f
 }

test/Analysis/ScalarEvolution/select.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+; Check that select between two equal values is recognized as this value.
+; CHECK-LABEL: @test_01
+; CHECK:        %s = select i1 %cond, i32 777, i32 777
+; CHECK-NEXT:    -->  777 U: [777,778) S: [777,778)
+define void @test_01(i1 %cond) {
+  %s = select i1 %cond, i32 777, i32 777
+  ret void
+}

test/Transforms/LoopStrengthReduce/lsr-expand-quadratic.ll

 test2.loop:
   %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test2.loop ]
   %inc11.us = add nsw i32 %inc1115.us, 1
   %cmp.us = icmp slt i32 %inc11.us, 2
   br i1 %cmp.us, label %test2.loop, label %for.end
 
 for.end:
   %tobool.us = icmp eq i32 %inc1115.us, 0
+  %sub.us = select i1 %tobool.us, i32 0, i32 1
+  %mul.us = shl i32 %inc1115.us, 24
+  %sub.cond.us = sub nsw i32 %inc1115.us, %sub.us
+  %sext.us = mul i32 %mul.us, %sub.cond.us
+  %f = ashr i32 %sext.us, 24
+  br label %exit
+
+exit:
+  ret i32 %f
+}
+
+; Demonstrate that if we select between two equal values, we can detect this
+; as a quadratic recurrence.
+;
+; CHECK-LABEL: @test3
+; CHECK-LABEL: test3.loop:
+; CHECK:  %lsr.iv1 = phi i32 [ %lsr.iv.next2, %test3.loop ], [ 16777216, %entry ]
+; CHECK:  %lsr.iv = phi i32 [ %lsr.iv.next, %test3.loop ], [ -16777216, %entry ]
+; CHECK:  %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test3.loop ]
+; CHECK:  %inc11.us = add nsw i32 %inc1115.us, 1
+; CHECK:  %lsr.iv.next = add nsw i32 %lsr.iv, 33554432
+; CHECK:  %lsr.iv.next2 = add i32 %lsr.iv1, %lsr.iv
+;
+; CHECK-LABEL: for.end:
+; CHECK:  %f = ashr i32 %lsr.iv.next2, 24
+; CHECK: ret i32 %f
+define i32 @test3() {
+entry:
+  br label %test3.loop
+
+test3.loop:
+  %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test3.loop ]
+  %inc11.us = add nsw i32 %inc1115.us, 1
+  %cmp.us = icmp slt i32 %inc11.us, 2
+  br i1 %cmp.us, label %test3.loop, label %for.end
+
+for.end:
+  %tobool.us = icmp eq i32 %inc1115.us, 0
   %sub.us = select i1 %tobool.us, i32 0, i32 0
   %mul.us = shl i32 %inc1115.us, 24
   %sub.cond.us = sub nsw i32 %inc1115.us, %sub.us
   %sext.us = mul i32 %mul.us, %sub.cond.us
   %f = ashr i32 %sext.us, 24
   br label %exit
 
 exit:
   ret i32 %f
 }