SCEV: handle constant condition for select/branch

[mehdi_amini]

Summary

This patch builds on top of D13378 to handle constant condition.

With this patch, clang -O3 optimizes correctly providing > 1000x speedup on this artificial benchmark):

for (a=0; a<n; a++)
    for (b=0; b<n; b++)
        for (c=0; c<n; c++)
            for (d=0; d<n; d++)
                for (e=0; e<n; e++)
                    for (f=0; f<n; f++)
                        x++;

From test-suite/SingleSource/Benchmarks/Shootout/nestedloop.c

[mehdi_amini]

Add a test

[atrick]

Well, ideally the IR is canonical before SCEV, but this condition is simple enough to catch anyway. Thanks.

[mehdi_amini]

I guess if this comes up when handling loops for instance, you may not necessarily be able to easily simplify the CFG in a loop pass.

[manmanren]

lib/Analysis/ScalarEvolution.cpp

3894

Please add a period at end of the comment.

3899

Should this be simplified to
return getSCEV(CI->isOne() ? TrueValue : FalseVal);

[mehdi_amini]

Thanks Manman, I updated the revision accordingly.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

3894

Minor stylistic issue, since you'll have to rebase anyway: instead of putting the check for ConstantInt inside the if block, I'd put it before the dyn_cast<ICmpInst>. Shouldn't make any semantic difference, but it will reduce the nesting on return getSCEV(CI->isOne() ? TrueVal : FalseVal);.

[hfinkel]

In D13390#258904, @joker.eph wrote:

I guess if this comes up when handling loops for instance, you may not necessarily be able to easily simplify the CFG in a loop pass.

Do we not currently catch this in SimplifyCFG (or similar)? I don't object to this change, but we really should catch this elsewhere too.

[mehdi_amini]

We surely catch it elsewhere. The problem is loop optimization like induction variable substitution that will operate on the inner loop, exposes this case, and then move the outer loop leaving the IR in this state. To solve this with simpifycfg I'm not sure that 1) it can be ran on a subpart of the CFG (you don't want to reprocess the full function between the two loops) 2) won't mess up the loop structure/canonicalization.

It seems to me that there is a kind of tension between optimizing for the "canonical IR" and being able to handle properly "non-canonical IR" because it is hard or expensive to always guarantee that your IR is canonical. I see this change as pushing a little bit SCEV toward the second case.

Any opinion?

Note: this landed a few week ago in r249431.

[hfinkel]

In D13390#276849, @joker.eph wrote:

We surely catch it elsewhere. The problem is loop optimization like induction variable substitution that will operate on the inner loop, exposes this case, and then move the outer loop leaving the IR in this state. To solve this with simpifycfg I'm not sure that 1) it can be ran on a subpart of the CFG (you don't want to reprocess the full function between the two loops) 2) won't mess up the loop structure/canonicalization.

It seems to me that there is a kind of tension between optimizing for the "canonical IR" and being able to handle properly "non-canonical IR" because it is hard or expensive to always guarantee that your IR is canonical. I see this change as pushing a little bit SCEV toward the second case.

Any opinion?

This is certainly true; there will always be these kinds of phase ordering problems. Especially since we don't have a LoopSimplifyCFG pass ;)

Note: this landed a few week ago in r249431.

lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   return getUnknown(PN);
 }
 
 const SCEV *ScalarEvolution::createNodeForSelect(Instruction *I, Value *Cond,
                                                  Value *TrueVal,
                                                  Value *FalseVal) {
   // Try to match some simple smax or umax patterns.
   auto *ICI = dyn_cast<ICmpInst>(Cond);
-  if (!ICI)
+  if (!ICI) {
+    // If this is not an integer condition, it might still be a constant.
+    if (auto *CI = dyn_cast<ConstantInt>(Cond))
+      return getSCEV(CI->isOne() ? TrueVal : FalseVal);
     return getUnknown(I);
-
+  }
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   switch (ICI->getPredicate()) {
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
     std::swap(LHS, RHS);
   // fall through
   case ICmpInst::ICMP_SGT:

test/Analysis/ScalarEvolution/constant_condition.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define i32 @branch_true(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @branch_true
+ entry:
+  br i1 true, label %add, label %merge
+
+ add:
+  %sum = add i32 %x, %y
+  br label %merge
+
+ merge:
+  %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK:  %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT:  -->  (%x + %y) U: full-set S: full-set
+  ret i32 %v
+}
+
+define i32 @branch_false(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @branch_false
+ entry:
+  br i1 false, label %add, label %merge
+
+ add:
+  %sum = add i32 %x, %y
+  br label %merge
+
+ merge:
+  %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK:  %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT:  -->  %x U: full-set S: full-set
+  ret i32 %v
+}
+
+define i32 @select_true(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @select_true
+ entry:
+ %v = select i1 true, i32 %x, i32 %y
+; CHECK:  %v = select i1 true, i32 %x, i32 %y
+; CHECK-NEXT:  -->  %x U: full-set S: full-set
+  ret i32 %v
+}
+
+define i32 @select_false(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @select_false
+ entry:
+ %v = select i1 false, i32 %x, i32 %y
+; CHECK:  %v = select i1 false, i32 %x, i32 %y
+; CHECK-NEXT:  -->  %y U: full-set S: full-set
+  ret i32 %v
+}