[IPSCCP] Use constant range information for comparisons of parameters.

[fhahn]

Summary

For comparisons with parameters, we can use the ParamState lattice
elements which also provide constant range information. This improves
the code for PR33253 further and gets us closer to use
ValueLatticeElement for all values.

Also, as we are using the range information in the solver directly, we
do not need tryToReplaceWithConstantRange afterwards anymore.

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[mssimpso]

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

5

Hi Florian,

I'm not understanding why we end up with undef here. Can you help me out?

[mssimpso]

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

5

Ah, it's because the function becomes dead after the simplification in @caller1. Right?

[fhahn]

Removed tryToReplaceWithConstantRange. It's not needed anymore, as we use the constant range info directly in the solver.

[fhahn]

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

5

Yep. And the selects are removed, because now the range info is used directly in the solver and is used to simplify the function further.

[mssimpso]

LGTM.

[fhahn]

Slightly restructured to only call getValueState when we failed to find a value in ParamState.

[fhahn]

I had to revert this patch a while ago in rL328312 because it did a few things wrong. Most issues are fixed now, there is still one failure I need to track down. I will share the updated patches soon.

[fhahn]

I've finally had some time to come back to this change (sorry for the long delay!) and committed an updated version of this patch as rL336098.

The change to the original patch is that we have to add values to the worklist if merging in an argument changes the ParamState for it, but there has been no change in ValueState (e.g. ValueState is overdefined, but in ParamState we have a value range that changed). It would be great if could have a quick look at the committed change as a sanity check I did not miss anything.

lib/Transforms/Scalar/SCCP.cpp

if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
     }
   }
 
   markOverdefined(&I);
 }
 
 // Handle ICmpInst instruction.
 void SCCPSolver::visitCmpInst(CmpInst &I) {
-  LatticeVal V1State = getValueState(I.getOperand(0));
-  LatticeVal V2State = getValueState(I.getOperand(1));
+  ValueLatticeElement V1State = getValueState(I.getOperand(0)).toValueLattice();
+  ValueLatticeElement V2State = getValueState(I.getOperand(1)).toValueLattice();
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
-  if (V1State.isConstant() && V2State.isConstant()) {
-    Constant *C = ConstantExpr::getCompare(
-        I.getPredicate(), V1State.getConstant(), V2State.getConstant());
+  // For parameters, use ParamState which includes constant range info if
+  // available.
+  auto V1Param = ParamState.find(I.getOperand(0));
+  auto V2Param = ParamState.find(I.getOperand(1));
+  if (V1Param != ParamState.end())
+    V1State = V1Param->second;
+  if (V2Param != ParamState.end())
+    V2State = V2Param->second;
+
+  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
+  if (C) {
     if (isa<UndefValue>(C))
       return;
     return markConstant(IV, &I, C);
   }
 
   // If operands are still unknown, wait for it to resolve.
   if (!V1State.isOverdefined() && !V2State.isOverdefined())
     return;

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

 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 ; Constant range for %a is [1, 48) and for %b is [301, 1000)
 ; CHECK-LABEL: f1
-; CHECK-NOT: icmp
-; CHECK: %a.1 = select i1 false, i32 1, i32 2
-; CHECK: %b.1 = select i1 true, i32 1, i32 2
-; CHECK: %a.2 = select i1 false, i32 1, i32 2
-; CHECK: %b.2 = select i1 true, i32 1, i32 2
+; CHECK: ret i32 undef
 define internal i32 @f1(i32 %a, i32 %b) {
 entry:
   %cmp.a = icmp sgt i32 %a, 300
   %cmp.b = icmp sgt i32 %b, 300
   %cmp.a2 = icmp ugt i32 %a, 300
   %cmp.b2 = icmp ugt i32 %b, 300
 
   %a.1 = select i1 %cmp.a, i32 1, i32 2
   %b.1 = select i1 %cmp.b, i32 1, i32 2
   %a.2 = select i1 %cmp.a2, i32 1, i32 2
   %b.2 = select i1 %cmp.b2, i32 1, i32 2
   %res1 = add i32 %a.1, %b.1
   %res2 = add i32 %a.2, %b.2
   %res3 = add i32 %res1, %res2
   ret i32 %res3
 }
 
 ; Constant range for %x is [47, 302)
 ; CHECK-LABEL: f2
 ; CHECK: %cmp = icmp sgt i32 %x, 300
 ; CHECK: %res1 = select i1 %cmp, i32 1, i32 2
-; CHECK-NEXT: %res2 = select i1 true, i32 3, i32 4
-; CHECK-NEXT: %res3 = select i1 true, i32 5, i32 6
 ; CHECK-NEXT: %res4 = select i1 %cmp4, i32 3, i32 4
-; CHECK-NEXT: %res5 = select i1 true, i32 5, i32 6
+; CHECK-NEXT: %res6 = add i32 %res1, 3
+; CHECK-NEXT: %res7 = add i32 5, %res4
+; CHECK-NEXT: %res = add i32 %res6, 5
+; CHECK-NEXT: ret i32 %res
 define internal i32 @f2(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, 300
   %cmp2 = icmp ne i32 %x, 10
   %cmp3 = icmp sge i32 %x, 47
   %cmp4 = icmp ugt i32 %x, 300
   %cmp5 = icmp uge i32 %x, 47
   %res1 = select i1 %cmp, i32 1, i32 2

 }
 
 define i32 @caller1() {
 entry:
   %call1 = tail call i32 @f1(i32 1, i32 301)
   %call2 = tail call i32 @f1(i32 47, i32 999)
   %call3 = tail call i32 @f2(i32 47)
   %call4 = tail call i32 @f2(i32 301)
-  %res = add nsw i32 %call1, %call2
-  %res.1 = add nsw i32 %res, %call3
+  %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