Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4473,6 +4473,10 @@ 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(Cond)) Index: test/Analysis/IVUsers/quadradic-exit-value.ll =================================================================== --- test/Analysis/IVUsers/quadradic-exit-value.ll +++ test/Analysis/IVUsers/quadradic-exit-value.ll @@ -36,7 +36,7 @@ ; 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)),+,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)),+,33554432}<%test2.loop> (post-inc with loop %test2.loop) in %f = ashr i32 %sext.us, 24 define i32 @test2() { entry: br label %test2.loop @@ -49,6 +49,34 @@ 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 Index: test/Analysis/ScalarEvolution/select.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/select.ll @@ -0,0 +1,10 @@ +; 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 +} Index: test/Transforms/LoopStrengthReduce/lsr-expand-quadratic.ll =================================================================== --- test/Transforms/LoopStrengthReduce/lsr-expand-quadratic.ll +++ test/Transforms/LoopStrengthReduce/lsr-expand-quadratic.ll @@ -30,6 +30,44 @@ 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