[SCCP] Use constant ranges for select, if cond is overdefined.

[fhahn]

Summary

For selects with an unknown condition, we can approximate the result by
merging the state of both options. This automatically takes care of
the case where on operand is undef.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[efriedma]

Maybe also add a testcase with a select with a ConstantExpr cond?

[fhahn]

In D71935#1830422, @efriedma wrote:

Maybe also add a testcase with a select with a ConstantExpr cond?

Add test case with ConstantExpr cond.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[fhahn]

Ping. I think all required patches should have landed over the last week or so.

Rebased.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

void SCCPSolver::visitSelectInst(SelectInst &I) {
   }
 
   // Otherwise, the condition is overdefined or a constant we can't evaluate.
   // See if we can produce something better than overdefined based on the T/F
   // value.
   LatticeVal TVal = getValueState(I.getTrueValue());
   LatticeVal FVal = getValueState(I.getFalseValue());
 
-  // select ?, C, C -> C.
-  if (isConstant(TVal) && isConstant(FVal) &&
-      getConstant(TVal) == getConstant(FVal))
-    return (void)markConstant(&I, getConstant(FVal));
-
-  if (TVal.isUnknownOrUndef())   // select ?, undef, X -> X.
-    return (void)mergeInValue(&I, FVal);
-  if (FVal.isUnknownOrUndef())   // select ?, X, undef -> X.
-    return (void)mergeInValue(&I, TVal);
-  markOverdefined(&I);
+  bool Changed = ValueState[&I].mergeIn(TVal, DL);
+  Changed |= ValueState[&I].mergeIn(FVal, DL);
+  if (Changed)
+    pushToWorkListMsg(ValueState[&I], &I);
 }
 
 // Handle Unary Operators.
 void SCCPSolver::visitUnaryOperator(Instruction &I) {
   LatticeVal V0State = getValueState(I.getOperand(0));
 
   LatticeVal &IV = ValueState[&I];
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would

llvm/test/Transforms/SCCP/ip-ranges-select.ll

 bb10:                                             ; preds = %bb8
   ret i32 10
 
 bb12:                                             ; preds = %bb8, %bb3, %bb
   ret i32 12
 }
 
 declare void @use(i32)
+
+define internal i1 @f1(i32 %x, i32 %y, i1 %cmp) {
+; CHECK-LABEL: define internal i1 @f1(i32 %x, i32 %y, i1 %cmp) {
+; CHECK-NEXT:    %sel.1 = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NEXT:    %c.2 = icmp sgt i32 %sel.1, 100
+; CHECK-NEXT:    %c.3 = icmp eq i32 %sel.1, 50
+; CHECK-NEXT:    %res.1 = add i1 false, %c.2
+; CHECK-NEXT:    %res.2 = add i1 %res.1, %c.3
+; CHECK-NEXT:    %res.3 = add i1 %res.2, false
+; CHECK-NEXT:    ret i1 %res.3
+;
+  %sel.1 = select i1 %cmp, i32 %x, i32 %y
+  %c.1 = icmp sgt i32 %sel.1, 300
+  %c.2 = icmp sgt i32 %sel.1, 100
+  %c.3 = icmp eq i32 %sel.1, 50
+  %c.4 = icmp slt i32 %sel.1, 9
+  %res.1 = add i1 %c.1, %c.2
+  %res.2 = add i1 %res.1, %c.3
+  %res.3 = add i1 %res.2, %c.4
+  ret i1 %res.3
+}
+
+define i1 @caller1(i1 %cmp) {
+; CHECK-LABEL:  define i1 @caller1(i1 %cmp) {
+; CHECK-NEXT:    %call.1 = tail call i1 @f1(i32 10, i32 100, i1 %cmp)
+; CHECK-NEXT:    %call.2 = tail call i1 @f1(i32 20, i32 200, i1 %cmp)
+; CHECK-NEXT:    %res = and i1 %call.1, %call.2
+; CHECK-NEXT:    ret i1 %res
+;
+  %call.1 = tail call i1 @f1(i32 10, i32 100, i1 %cmp)
+  %call.2 = tail call i1 @f1(i32 20, i32 200, i1 %cmp)
+  %res = and i1 %call.1, %call.2
+  ret i1 %res
+}
+
+
+define i1 @f2(i32 %x, i32 %y, i1 %cmp) {
+; CHECK-LABEL: define i1 @f2(i32 %x, i32 %y, i1 %cmp) {
+; CHECK-NEXT:    %sel.1 = select i1 %cmp, i32 %x, i32 %y
+; CHECK-NEXT:    %c.1 = icmp sgt i32 %sel.1, 300
+; CHECK-NEXT:    %c.2 = icmp sgt i32 %sel.1, 100
+; CHECK-NEXT:    %c.3 = icmp eq i32 %sel.1, 50
+; CHECK-NEXT:    %c.4 = icmp slt i32 %sel.1, 9
+; CHECK-NEXT:    %res.1 = add i1 %c.1, %c.2
+; CHECK-NEXT:    %res.2 = add i1 %res.1, %c.3
+; CHECK-NEXT:    %res.3 = add i1 %res.2, %c.4
+; CHECK-NEXT:    ret i1 %res.3
+;
+  %sel.1 = select i1 %cmp, i32 %x, i32 %y
+  %c.1 = icmp sgt i32 %sel.1, 300
+  %c.2 = icmp sgt i32 %sel.1, 100
+  %c.3 = icmp eq i32 %sel.1, 50
+  %c.4 = icmp slt i32 %sel.1, 9
+  %res.1 = add i1 %c.1, %c.2
+  %res.2 = add i1 %res.1, %c.3
+  %res.3 = add i1 %res.2, %c.4
+  ret i1 %res.3
+}
+
+define i1 @caller2(i32 %y, i1 %cmp) {
+; CHECK-LABEL:  define i1 @caller2(i32 %y, i1 %cmp) {
+; CHECK-NEXT:    %call.1 = tail call i1 @f2(i32 10, i32 %y, i1 %cmp)
+; CHECK-NEXT:    %call.2 = tail call i1 @f2(i32 20, i32 %y, i1 %cmp)
+; CHECK-NEXT:    %res = and i1 %call.1, %call.2
+; CHECK-NEXT:    ret i1 %res
+;
+  %call.1 = tail call i1 @f2(i32 10, i32 %y, i1 %cmp)
+  %call.2 = tail call i1 @f2(i32 20, i32 %y, i1 %cmp)
+  %res = and i1 %call.1, %call.2
+  ret i1 %res
+}
+
+@GV = external global i32
+
+define i32 @f3_constantexpr_cond(i32 %x, i32 %y) {
+; CHECK-LABEL: define i32 @f3_constantexpr_cond(i32 %x, i32 %y)
+; CHECK-NEXT:   %sel.1 = select i1 icmp eq (i32* bitcast (i32 (i32, i32)* @f3_constantexpr_cond to i32*), i32* @GV), i32 %x, i32 %y
+; CHECK-NEXT:   ret i32 %sel.1
+;
+  %sel.1 = select i1 icmp eq (i32* bitcast (i32 (i32, i32)* @f3_constantexpr_cond to i32*), i32* @GV), i32 %x, i32 %y
+  ret i32 %sel.1
+}
+
+define i32 @caller3(i32 %y) {
+; CHECK-LABEL:  define i32 @caller3(i32 %y) {
+; CHECK-NEXT:    %call.1 = tail call i32 @f3_constantexpr_cond(i32 10, i32 %y)
+; CHECK-NEXT:    %call.2 = tail call i32 @f3_constantexpr_cond(i32 20, i32 %y)
+; CHECK-NEXT:    %res = and i32 %call.1, %call.2
+; CHECK-NEXT:    ret i32 %res
+;
+  %call.1 = tail call i32 @f3_constantexpr_cond(i32 10, i32 %y)
+  %call.2 = tail call i32 @f3_constantexpr_cond(i32 20, i32 %y)
+  %res = and i32 %call.1, %call.2
+  ret i32 %res
+}

llvm/test/Transforms/SCCP/select.ll

-; RUN: opt < %s -sccp -S | not grep select
+; RUN: opt < %s -sccp -S | FileCheck %s
 
 define i32 @test1(i1 %C) {
+; CHECK-LABEL: define i32 @test1(
+; CHECK-NEXT:   ret i32 0
+;
   %X = select i1 %C, i32 0, i32 0    ; <i32> [#uses=1]
   ret i32 %X
 }
 
 define i32 @test2(i1 %C) {
+; CHECK-LABEL: define i32 @test2(
+; CHECK-NEXT:   ret i32 0
+;
   %X = select i1 %C, i32 0, i32 undef    ; <i32> [#uses=1]
   ret i32 %X
 }
 
+define i1 @f2(i32 %x, i1 %cmp) {
+; CHECK-LABEL: define i1 @f2(i32 %x, i1 %cmp) {
+; CHECK-NEXT:    %sel.1 = select i1 %cmp, i32 %x, i32 10
+; CHECK-NEXT:    %c.1 = icmp sgt i32 %sel.1, 300
+; CHECK-NEXT:    %c.2 = icmp sgt i32 %sel.1, 100
+; CHECK-NEXT:    %c.3 = icmp eq i32 %sel.1, 50
+; CHECK-NEXT:    %c.4 = icmp slt i32 %sel.1, 9
+; CHECK-NEXT:    %res.1 = add i1 %c.1, %c.2
+; CHECK-NEXT:    %res.2 = add i1 %res.1, %c.3
+; CHECK-NEXT:    %res.3 = add i1 %res.2, %c.4
+; CHECK-NEXT:    ret i1 %res.3
+;
+  %sel.1 = select i1 %cmp, i32 %x, i32 10
+  %c.1 = icmp sgt i32 %sel.1, 300
+  %c.2 = icmp sgt i32 %sel.1, 100
+  %c.3 = icmp eq i32 %sel.1, 50
+  %c.4 = icmp slt i32 %sel.1, 9
+  %res.1 = add i1 %c.1, %c.2
+  %res.2 = add i1 %res.1, %c.3
+  %res.3 = add i1 %res.2, %c.4
+  ret i1 %res.3
+}