[SCCP] Use constant ranges for PHI nodes.

[fhahn]

Summary

For PHIs with multiple incoming values, we can improve precision by
using constant ranges for integers. We can over-approximate phis
by merging the incoming values.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

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

[fhahn]

rebase after isUnknownOrConstant -> isOverdefined change.

[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

 // 7. If a conditional branch has a value that is overdefined, make all
 //    successors executable.
 void SCCPSolver::visitPHINode(PHINode &PN) {
   // If this PN returns a struct, just mark the result overdefined.
   // TODO: We could do a lot better than this if code actually uses this.
   if (PN.getType()->isStructTy())
     return (void)markOverdefined(&PN);
 
-  if (isOverdefined(getValueState(&PN))) {
-    return (void)markOverdefined(&PN);
-  }
+  if (getValueState(&PN).isOverdefined())
+    return; // Quick exit
 
   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
   // and slow us down a lot.  Just mark them overdefined.
   if (PN.getNumIncomingValues() > 64)
     return (void)markOverdefined(&PN);
 
   // Look at all of the executable operands of the PHI node.  If any of them
   // are overdefined, the PHI becomes overdefined as well.  If they are all
   // constant, and they agree with each other, the PHI becomes the identical
   // constant.  If they are constant and don't agree, the PHI is overdefined.
   // If there are no executable operands, the PHI remains unknown.
-  Constant *OperandVal = nullptr;
+  bool Changed = false;
   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     LatticeVal IV = getValueState(PN.getIncomingValue(i));
-    if (IV.isUnknownOrUndef()) continue;  // Doesn't influence PHI node.
-
     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
       continue;
 
-    if (isOverdefined(IV)) // PHI node becomes overdefined!
-      return (void)markOverdefined(&PN);
-
-    if (!OperandVal) {   // Grab the first value.
-      OperandVal = getConstant(IV);
-      continue;
-    }
-
-    // There is already a reachable operand.  If we conflict with it,
-    // then the PHI node becomes overdefined.  If we agree with it, we
-    // can continue on.
-
-    // Check to see if there are two different constants merging, if so, the PHI
-    // node is overdefined.
-    if (getConstant(IV) != OperandVal)
-      return (void)markOverdefined(&PN);
+    LatticeVal &Res = getValueState(&PN);
+    Changed |= Res.mergeIn(IV, DL);
+    if (Res.isOverdefined())
+      break;
   }
-
-  // If we exited the loop, this means that the PHI node only has constant
-  // arguments that agree with each other(and OperandVal is the constant) or
-  // OperandVal is null because there are no defined incoming arguments.  If
-  // this is the case, the PHI remains unknown.
-  if (OperandVal)
-    markConstant(&PN, OperandVal);      // Acquire operand value
+  if (Changed)
+    pushToWorkListMsg(ValueState[&PN], &PN);
 }
 
 void SCCPSolver::visitReturnInst(ReturnInst &I) {
   if (I.getNumOperands() == 0) return;  // ret void
 
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (isOverdefined(ValueState[&I]))

llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[BB1]] ], [ 2, [[BB2]] ]
 ; CHECK-NEXT:    [[D:%.*]] = sdiv i32 1, [[X:%.*]]
-; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i32 [[P]], [[D]]
-; CHECK-NEXT:    call void @use(i1 [[C_0]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[P]], [[D]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 3, [[BB1]] ], [ 2, [[BB2]] ]
 ; CHECK-NEXT:    [[D:%.*]] = sdiv i32 1, [[X:%.*]]
-; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i32 [[P]], [[D]]
-; CHECK-NEXT:    call void @use(i1 [[C_0]])
-; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[P]], [[D]]
-; CHECK-NEXT:    call void @use(i1 [[C_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   br label %bb3
 

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

entry:
   %call2 = tail call i32 @f1(i32 47, i32 999)
   %call3 = tail call i32 @f2(i32 47)
   %call4 = tail call i32 @f2(i32 301)
   %res.1 = add nsw i32 12, %call3
   %res.2 = add nsw i32 %res.1, %call4
   ret i32 %res.2
 }
 
-; x is overdefined, because constant ranges are only used for parameter
-; values.
 ; CHECK-LABEL: f3
-; CHECK: %cmp = icmp sgt i32 %x, 300
-; CHECK: %res = select i1 %cmp, i32 1, i32 2
-; CHECK: ret i32 %res
+; CHECK-LABEL: entry:
+; CHECK: ret i32 undef
 define internal i32 @f3(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, 300
   %res = select i1 %cmp, i32 1, i32 2
   ret i32 %res
 }
 
 ; The phi node could be converted in a ConstantRange.
 define i32 @caller2(i1 %cmp) {
 entry:
   br i1 %cmp, label %if.true, label %end
 
 if.true:
   br label %end
 
 end:
   %res = phi i32 [ 0, %entry], [ 1, %if.true ]
   %call1 = tail call i32 @f3(i32 %res)
-  ret i32 %call1
+  ret i32 2
 }
 
 ; CHECK-LABEL: f4
 ; CHECK: %cmp = icmp sgt i32 %x, 300
 ; CHECK: %res = select i1 %cmp, i32 1, i32 2
 ; CHECK: ret i32 %res
 define internal i32 @f4(i32 %x) {
 entry:

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

+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+define internal i32 @f1(i32 %x) {
+; CHECK-LABEL: define internal i32 @f1(
+; CHECK-NEXT:    ret i32 undef
+;
+  %cmp = icmp sgt i32 %x, 300
+  %res = select i1 %cmp, i32 1, i32 2
+  ret i32 %res
+}
+
+; %res is a constant range [0, 2) from a PHI node.
+define i32 @caller1(i1 %cmp) {
+; CHECK-LABEL: define i32 @caller1(
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br i1 %cmp, label %if.true, label %end
+
+; CHECK-LABEL: if.true:
+; CHECK-NEXT:    br label %end
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %res = phi i32 [ 0, %entry ], [ 1, %if.true ]
+; CHECK-NEXT:    %call1 = tail call i32 @f1(i32 %res)
+; CHECK-NEXT:    ret i32 2
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %res = phi i32 [ 0, %entry], [ 1, %if.true ]
+  %call1 = tail call i32 @f1(i32 %res)
+  ret i32 %call1
+}
+
+define internal i32 @f2(i32 %x, i32 %y, i32 %z, i1 %cmp.1, i1 %cmp.2) {
+; CHECK-LABEL: define internal i32 @f2(
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br i1 %cmp.1, label %if.true.1, label %end
+
+; CHECK-LABEL: if.true.1:
+; CHECK-NEXT:    br i1 %cmp.2, label %if.true.2, label %end
+
+; CHECK-LABEL: if.true.2:
+; CHECK-NEXT:    br label %end
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi i32 [ %x, %entry ], [ %y, %if.true.1 ], [ %z, %if.true.2 ]
+; CHECK-NEXT:    %c.1 = icmp sgt i32 %p, 5
+; CHECK-NEXT:    %c.2 = icmp eq i32 %p, 0
+; CHECK-NEXT:    %c.3 = icmp slt i32 %p, 0
+; CHECK-NEXT:    %v.1 = select i1 %c.1, i32 10, i32 100
+; CHECK-NEXT:    %v.2 = select i1 %c.2, i32 20, i32 200
+; CHECK-NEXT:    %v.3 = select i1 %c.3, i32 30, i32 300
+; CHECK-NEXT:    %r.1 = add i32 %v.1, %v.2
+; CHECK-NEXT:    %r.2 = add i32 %r.1, %v.3
+; CHECK-NEXT:    %r.3 = add i32 %r.2, 400
+; CHECK-NEXT:    %r.4 = add i32 %r.3, 50
+; CHECK-NEXT:    %r.5 = add i32 %r.4, 60
+; CHECK-NEXT:    %r.6 = add i32 %r.4, 700
+; CHECK-NEXT:    ret i32 %r.6
+;
+entry:
+  br i1 %cmp.1, label %if.true.1, label %end
+
+if.true.1:
+  br i1 %cmp.2, label %if.true.2, label %end
+
+if.true.2:
+  br label %end
+
+end:
+  %p = phi i32 [ %x, %entry ], [ %y, %if.true.1 ], [ %z, %if.true.2 ]
+  %c.1 = icmp sgt i32 %p, 5
+  %c.2 = icmp eq i32 %p, 0
+  %c.3 = icmp slt i32 %p, 0
+  %c.4 = icmp sgt i32 %p, 10
+  %c.5 = icmp sle i32 %p, 10
+  %c.6 = icmp sgt i32 %p, -11
+  %c.7 = icmp slt i32 %p, -11
+  %v.1 = select i1 %c.1, i32 10, i32 100
+  %v.2 = select i1 %c.2, i32 20, i32 200
+  %v.3 = select i1 %c.3, i32 30, i32 300
+  %v.4 = select i1 %c.4, i32 40, i32 400
+  %v.5 = select i1 %c.5, i32 50, i32 500
+  %v.6 = select i1 %c.6, i32 60, i32 600
+  %v.7 = select i1 %c.7, i32 70, i32 700
+  %r.1 = add i32 %v.1, %v.2
+  %r.2 = add i32 %r.1, %v.3
+  %r.3 = add i32 %r.2, %v.4
+  %r.4 = add i32 %r.3, %v.5
+  %r.5 = add i32 %r.4, %v.6
+  %r.6 = add i32 %r.4, %v.7
+  ret i32 %r.6
+}
+
+define i32 @caller2(i1 %cmp.1, i1 %cmp.2) {
+; CHECK-LABEL: define i32 @caller2(i1 %cmp.1, i1 %cmp.2) {
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br i1 %cmp.1, label %if.true, label %end
+
+; CHECK-LABEL: if.true:                                          ; preds = %entry
+; CHECK-NEXT:    br label %end
+
+; CHECK-LABEL: end:                                              ; preds = %if.true, %entry
+; CHECK-NEXT:    %p1 = phi i32 [ 0, %entry ], [ 1, %if.true ]
+; CHECK-NEXT:    %p2 = phi i32 [ 1, %entry ], [ -10, %if.true ]
+; CHECK-NEXT:    %p3 = phi i32 [ 1, %entry ], [ 10, %if.true ]
+; CHECK-NEXT:    %call1 = tail call i32 @f2(i32 %p1, i32 %p2, i32 %p3, i1 %cmp.1, i1 %cmp.2)
+; CHECK-NEXT:    ret i32 %call1
+;
+
+entry:
+  br i1 %cmp.1, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p1 = phi i32 [ 0, %entry], [ 1, %if.true ]
+  %p2 = phi i32 [ 1, %entry], [ -10, %if.true ]
+  %p3 = phi i32 [ 1, %entry], [ 10, %if.true ]
+  %call1 = tail call i32 @f2(i32 %p1, i32 %p2, i32 %p3, i1 %cmp.1, i1 %cmp.2)
+  ret i32 %call1
+}
+
+define internal i32 @f3(i32 %x, i32 %y, i1 %cmp.1) {
+; CHECK-LABEL: define internal i32 @f3(i32 %x, i32 %y, i1 %cmp.1) {
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br i1 %cmp.1, label %if.true.1, label %end
+
+; CHECK-LABEL: if.true.1:                                        ; preds = %entry
+; CHECK-NEXT:    br label %end
+
+; CHECK-LABEL: end:                                              ; preds = %if.true.1, %entry
+; CHECK-NEXT:    %p = phi i32 [ %x, %entry ], [ %y, %if.true.1 ]
+; CHECK-NEXT:    %c.1 = icmp sgt i32 %p, 5
+; CHECK-NEXT:    %c.2 = icmp eq i32 %p, 0
+; CHECK-NEXT:    %c.3 = icmp slt i32 %p, 0
+; CHECK-NEXT:    %c.4 = icmp sgt i32 %p, 10
+; CHECK-NEXT:    %c.5 = icmp sle i32 %p, 10
+; CHECK-NEXT:    %c.6 = icmp sgt i32 %p, -11
+; CHECK-NEXT:    %c.7 = icmp slt i32 %p, -11
+; CHECK-NEXT:    %v.1 = select i1 %c.1, i32 10, i32 100
+; CHECK-NEXT:    %v.2 = select i1 %c.2, i32 20, i32 200
+; CHECK-NEXT:    %v.3 = select i1 %c.3, i32 30, i32 300
+; CHECK-NEXT:    %v.4 = select i1 %c.4, i32 40, i32 400
+; CHECK-NEXT:    %v.5 = select i1 %c.5, i32 50, i32 500
+; CHECK-NEXT:    %v.6 = select i1 %c.6, i32 60, i32 600
+; CHECK-NEXT:    %v.7 = select i1 %c.7, i32 70, i32 700
+; CHECK-NEXT:    %r.1 = add i32 %v.1, %v.2
+; CHECK-NEXT:    %r.2 = add i32 %r.1, %v.3
+; CHECK-NEXT:    %r.3 = add i32 %r.2, %v.4
+; CHECK-NEXT:    %r.4 = add i32 %r.3, %v.5
+; CHECK-NEXT:    %r.5 = add i32 %r.4, %v.6
+; CHECK-NEXT:    %r.6 = add i32 %r.4, %v.7
+; CHECK-NEXT:    ret i32 %r.6
+;
+entry:
+  br i1 %cmp.1, label %if.true.1, label %end
+
+if.true.1:
+  br label %end
+
+end:
+  %p = phi i32 [ %x, %entry ], [ %y, %if.true.1 ]
+  %c.1 = icmp sgt i32 %p, 5
+  %c.2 = icmp eq i32 %p, 0
+  %c.3 = icmp slt i32 %p, 0
+  %c.4 = icmp sgt i32 %p, 10
+  %c.5 = icmp sle i32 %p, 10
+  %c.6 = icmp sgt i32 %p, -11
+  %c.7 = icmp slt i32 %p, -11
+  %v.1 = select i1 %c.1, i32 10, i32 100
+  %v.2 = select i1 %c.2, i32 20, i32 200
+  %v.3 = select i1 %c.3, i32 30, i32 300
+  %v.4 = select i1 %c.4, i32 40, i32 400
+  %v.5 = select i1 %c.5, i32 50, i32 500
+  %v.6 = select i1 %c.6, i32 60, i32 600
+  %v.7 = select i1 %c.7, i32 70, i32 700
+  %r.1 = add i32 %v.1, %v.2
+  %r.2 = add i32 %r.1, %v.3
+  %r.3 = add i32 %r.2, %v.4
+  %r.4 = add i32 %r.3, %v.5
+  %r.5 = add i32 %r.4, %v.6
+  %r.6 = add i32 %r.4, %v.7
+  ret i32 %r.6
+}
+
+define i32 @caller3(i32 %y, i1 %cmp.1) {
+; CHECK-LABEL: define i32 @caller3(i32 %y, i1 %cmp.1) {
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br i1 %cmp.1, label %if.true, label %end
+
+; CHECK-LABEL: if.true:
+; CHECK-NEXT:    br label %end
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p1 = phi i32 [ 0, %entry ], [ 5, %if.true ]
+; CHECK-NEXT:    %call1 = tail call i32 @f3(i32 %p1, i32 %y, i1 %cmp.1)
+; CHECK-NEXT:    ret i32 %call1
+;
+entry:
+  br i1 %cmp.1, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p1 = phi i32 [ 0, %entry], [ 5, %if.true ]
+  %call1 = tail call i32 @f3(i32 %p1, i32 %y, i1 %cmp.1)
+  ret i32 %call1
+}

llvm/test/Transforms/SCCP/phis.ll

+; RUN: opt < %s -sccp -S | FileCheck %s
+
+define i1 @float.1(i1 %cmp) {
+; CHECK-LABEL: define i1 @float.1(i1 %cmp) {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true]
+  %c = fcmp ueq float %p, 1.0
+  ret i1 %c
+}
+
+define i1 @float.2(i1 %cmp) {
+; CHECK-LABEL: define i1 @float.2(i1 %cmp) {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %if.true ]
+; CHECK-NEXT:    %c = fcmp ueq float %p, 1.000000e+00
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 2.0, %if.true]
+  %c = fcmp ueq float %p, 1.0
+  ret i1 %c
+}
+
+define i1 @float.3(float %f, i1 %cmp) {
+; CHECK-LABEL: define i1 @float.3(float %f, i1 %cmp)
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ %f, %if.true ]
+; CHECK-NEXT:    %c = fcmp ueq float %p, 1.000000e+00
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ %f, %if.true]
+  %c = fcmp ueq float %p, 1.0
+  ret i1 %c
+}
+
+
+define i1 @float.4_unreachable(float %f, i1 %cmp) {
+; CHECK-LABEL: define i1 @float.4_unreachable(float %f, i1 %cmp)
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+dead:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true], [ %f, %dead ]
+  %c = fcmp une float %p, 1.0
+  ret i1 %c
+}

llvm/test/Transforms/SCCP/range-and.ll

 ; CHECK-NEXT:    [[R_1:%.*]] = and i64 [[A:%.*]], 100
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[R_2:%.*]] = and i64 [[A]], 255
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R_1]], [[BB1]] ], [ [[R_2]], [[BB2]] ]
 ; CHECK-NEXT:    [[P_AND:%.*]] = and i64 [[P]], 512
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P_AND]], 256
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   %r.1 = and i64 %a, 100
   br label %bb3