[SCCP] Support ranges for loads and stores.

[fhahn]

Summary

Integer ranges can be used for loaded/stored values. Note that widening
can be disabled for loads/stores, as we only rely on instructions that
cause continued increases to ranges to be widened (like binary
operators).

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void SCCPSolver::visitStoreInst(StoreInst &SI) {
 
   GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
   auto I = TrackedGlobals.find(GV);
   if (I == TrackedGlobals.end())
     return;
 
   // Get the value we are storing into the global, then merge it.
   mergeInValue(I->second, GV, getValueState(SI.getOperand(0)));
-  if (isOverdefined(I->second))
+  if (I->second.isOverdefined())
     TrackedGlobals.erase(I);      // No need to keep tracking this!
 }
 
 // Handle load instructions.  If the operand is a constant pointer to a constant
 // global, we can replace the load with the loaded constant value!
 void SCCPSolver::visitLoadInst(LoadInst &I) {
   // If this load is of a struct, just mark the result overdefined.
   if (I.getType()->isStructTy())
     return (void)markOverdefined(&I);
 
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
-  if (isOverdefined(ValueState[&I]))
+  if (ValueState[&I].isOverdefined())
     return (void)markOverdefined(&I);
 
   ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
   if (PtrVal.isUnknownOrUndef())
     return; // The pointer is not resolved yet!
 
   ValueLatticeElement &IV = ValueState[&I];
 
void SCCPSolver::visitLoadInst(LoadInst &I) {
   }
 
   // Transform load (constant global) into the value loaded.
   if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
     if (!TrackedGlobals.empty()) {
       // If we are tracking this global, merge in the known value for it.
       auto It = TrackedGlobals.find(GV);
       if (It != TrackedGlobals.end()) {
-        mergeInValue(IV, &I, It->second);
+        mergeInValue(IV, &I, It->second,
+                     ValueLatticeElement::MergeOptions().setCheckWiden(false));
         return;
       }
     }
   }
 
   // Transform load from a constant into a constant if possible.
   if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
     if (isa<UndefValue>(C))

llvm/test/Transforms/SCCP/load-store-range.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 declare void @use(i1)
 
 @G = internal global i32 0
 
 define void @test1a() {
 ; CHECK-LABEL: @test1a(
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* @G
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i32 [[X]], 123
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[X]], 20
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    ret void
 ;
   %X = load i32, i32* @G
   %t.1 = icmp ne i32 %X, 124
   call void @use(i1 %t.1)
   %t.2 = icmp ult i32 %X, 124

 }
 
 
 @H = internal global i32 0
 
 define void @test2a() {
 ; CHECK-LABEL: @test2a(
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* @H
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i32 [[X]], 123
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[X]], 20
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    ret void
 ;
   %X = load i32, i32* @H
   %t.1 = icmp ne i32 %X, 124
   call void @use(i1 %t.1)
   %t.2 = icmp ult i32 %X, 124

 }
 
 
 @I = internal global i32 0
 
 define void @test3a() {
 ; CHECK-LABEL: @test3a(
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* @I
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[X]], 124
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i32 [[X]], 123
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[X]], 20
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    ret void
 ;
   %X = load i32, i32* @I
   %t.1 = icmp ne i32 %X, 124
   call void @use(i1 %t.1)
   %t.2 = icmp ult i32 %X, 124

llvm/test/Transforms/SCCP/resolvedundefsin-tracked-fn.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @pcount, align 4
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[DIV]], [[SUB19]]
 ; CHECK-NEXT:    [[CMP20:%.*]] = icmp sgt i32 [[TMP2]], [[MUL]]
 ; CHECK-NEXT:    br i1 [[CMP20]], label [[IF_THEN22:%.*]], label [[IF_END24:%.*]]
 ; CHECK:       if.then22:
 ; CHECK-NEXT:    store i32 [[MUL]], i32* @pcount, align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end24:
-; CHECK-NEXT:    [[CMP25474:%.*]] = icmp sgt i32 [[TMP2]], 0
-; CHECK-NEXT:    br i1 [[CMP25474]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
-; CHECK:       for.body:
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    br label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %if.end16
 
 if.end16:                                         ; preds = %entry
   %0 = load i32, i32* @contextsize, align 4