[SCCP] Use range metadata for loads and calls

[nikic]

Summary

When all else fails, use range metadata to constrain the result of loads and calls. It should also be possible to use !nonnull, but that would require some general support for inequalities in SCCP first.

[fhahn]

LGTM, thanks.

It should also be possible to use !nonnull

using ValueLattice::getNot/markNotConstant should possibly just work? For icmps we use ValueLattice's helpers, they should be able to deal with it, unless we bail out for pointers somewhere in SCCP.

llvm/lib/Transforms/Scalar/SCCP.cpp

1107

I think we have something similar in LVI. Might be good to move the common logic to ValueLattice

1121

For volatile loads, I think we could still use the range info if present? We are just not allowed to remove the volatile operation, right?

[nikic]

llvm/lib/Transforms/Scalar/SCCP.cpp

1121

This would be safe. I briefly tried this, but found that SCCP would zap the volatile load, because it only uses isSafeToRemove() to determine whether instructions can be dropped. We would have to replace that with something stronger, like isInstructionTriviallyDead(). Do you think that would be worthwhile?

llvm/lib/Transforms/Scalar/SCCP.cpp

void SCCPSolver::visitStoreInst(StoreInst &SI) {
 
   // Get the value we are storing into the global, then merge it.
   mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
                ValueLatticeElement::MergeOptions().setCheckWiden(false));
   if (I->second.isOverdefined())
     TrackedGlobals.erase(I);      // No need to keep tracking this!
 }
 
+static ValueLatticeElement getValueFromMetadata(const Instruction *I) {
+  if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
+    if (I->getType()->isIntegerTy())
+      return ValueLatticeElement::getRange(
+          getConstantRangeFromMetadata(*Ranges));
+  // TODO: Also handle MD_nonnull.
+  return ValueLatticeElement::getOverdefined();
+}
+
 // 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())
+  // If this load is of a struct or the load is volatile, just mark the result
+  // as overdefined.
+  if (I.getType()->isStructTy() || I.isVolatile())
     return (void)markOverdefined(&I);
 
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   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];
 
-  if (!isConstant(PtrVal) || I.isVolatile())
-    return (void)markOverdefined(IV, &I);
-
+  if (isConstant(PtrVal)) {
     Constant *Ptr = getConstant(PtrVal);
 
     // load null is undefined.
     if (isa<ConstantPointerNull>(Ptr)) {
       if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
         return (void)markOverdefined(IV, &I);
       else
         return;
     }
 
     // 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, getMaxWidenStepsOpts());
           return;
         }
       }
     }
 
     // Transform load from a constant into a constant if possible.
     if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
       if (isa<UndefValue>(C))
         return;
       return (void)markConstant(IV, &I, C);
     }
+  }
 
-  // Otherwise we cannot say for certain what value this load will produce.
-  // Bail out.
-  markOverdefined(IV, &I);
+  // Fall back to metadata.
+  mergeInValue(&I, getValueFromMetadata(&I));
 }
 
 void SCCPSolver::visitCallBase(CallBase &CB) {
   handleCallResult(CB);
   handleCallArguments(CB);
 }
 
 void SCCPSolver::handleCallOverdefined(CallBase &CB) {
   Function *F = CB.getCalledFunction();
 
   // Void return and not tracking callee, just bail.
   if (CB.getType()->isVoidTy())
     return;
 
+  // Always mark struct return as overdefined.
+  if (CB.getType()->isStructTy())
+    return (void)markOverdefined(&CB);
+
   // Otherwise, if we have a single return value case, and if the function is
   // a declaration, maybe we can constant fold it.
-  if (F && F->isDeclaration() && !CB.getType()->isStructTy() &&
-      canConstantFoldCallTo(&CB, F)) {
+  if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
     SmallVector<Constant *, 8> Operands;
     for (auto AI = CB.arg_begin(), E = CB.arg_end(); AI != E; ++AI) {
       if (AI->get()->getType()->isStructTy())
         return markOverdefined(&CB); // Can't handle struct args.
       ValueLatticeElement State = getValueState(*AI);
 
       if (State.isUnknownOrUndef())
         return; // Operands are not resolved yet.
if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
     if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F))) {
       // call -> undef.
       if (isa<UndefValue>(C))
         return;
       return (void)markConstant(&CB, C);
     }
   }
 
-  // Otherwise, we don't know anything about this call, mark it overdefined.
-  return (void)markOverdefined(&CB);
+  // Fall back to metadata.
+  mergeInValue(&CB, getValueFromMetadata(&CB));
 }
 
 void SCCPSolver::handleCallArguments(CallBase &CB) {
   Function *F = CB.getCalledFunction();
   // If this is a local function that doesn't have its address taken, mark its
   // entry block executable and merge in the actual arguments to the call into
   // the formal arguments of the function.
   if (!TrackingIncomingArguments.empty() &&

llvm/test/Transforms/SCCP/metadata.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 declare void @use(i1)
 declare i32 @get_i32()
 
 define void @load_range(i32* %p) {
 ; CHECK-LABEL: @load_range(
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4, !range !0
-; CHECK-NEXT:    [[C1:%.*]] = icmp ult i32 [[V]], 10
-; CHECK-NEXT:    call void @use(i1 [[C1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[V]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C2]])
-; CHECK-NEXT:    [[C3:%.*]] = icmp ugt i32 [[V]], 9
-; CHECK-NEXT:    call void @use(i1 [[C3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C4:%.*]] = icmp ugt i32 [[V]], 8
 ; CHECK-NEXT:    call void @use(i1 [[C4]])
 ; CHECK-NEXT:    ret void
 ;
   %v = load i32, i32* %p, !range !{i32 0, i32 10}
   %c1 = icmp ult i32 %v, 10
   call void @use(i1 %c1)
   %c2 = icmp ult i32 %v, 9
   call void @use(i1 %c2)
   %c3 = icmp ugt i32 %v, 9
   call void @use(i1 %c3)
   %c4 = icmp ugt i32 %v, 8
   call void @use(i1 %c4)
   ret void
 }
 
+define i32 @load_range_single(i32* %p) {
+; CHECK-LABEL: @load_range_single(
+; CHECK-NEXT:    ret i32 0
+;
+  %v = load i32, i32* %p, !range !{i32 0, i32 1}
+  ret i32 %v
+}
+
+define i32 @load_range_single_volatile(i32* %p) {
+; CHECK-LABEL: @load_range_single_volatile(
+; CHECK-NEXT:    [[V:%.*]] = load volatile i32, i32* [[P:%.*]], align 4, !range !1
+; CHECK-NEXT:    ret i32 [[V]]
+;
+  %v = load volatile i32, i32* %p, !range !{i32 0, i32 1}
+  ret i32 %v
+}
+
 define void @load_nonnull(i32** %p) {
 ; CHECK-LABEL: @load_nonnull(
-; CHECK-NEXT:    [[V:%.*]] = load i32*, i32** [[P:%.*]], align 8, !nonnull !1
+; CHECK-NEXT:    [[V:%.*]] = load i32*, i32** [[P:%.*]], align 8, !nonnull !2
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32* [[V]], null
 ; CHECK-NEXT:    call void @use(i1 [[C1]])
 ; CHECK-NEXT:    ret void
 ;
   %v = load i32*, i32** %p, !nonnull !{}
   %c1 = icmp ne i32* %v, null
   call void @use(i1 %c1)
   ret void
 }
 
 define void @call_range(i32* %p) {
 ; CHECK-LABEL: @call_range(
 ; CHECK-NEXT:    [[V:%.*]] = call i32 @get_i32(), !range !0
-; CHECK-NEXT:    [[C1:%.*]] = icmp ult i32 [[V]], 10
-; CHECK-NEXT:    call void @use(i1 [[C1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[V]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C2]])
-; CHECK-NEXT:    [[C3:%.*]] = icmp ugt i32 [[V]], 9
-; CHECK-NEXT:    call void @use(i1 [[C3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C4:%.*]] = icmp ugt i32 [[V]], 8
 ; CHECK-NEXT:    call void @use(i1 [[C4]])
 ; CHECK-NEXT:    ret void
 ;
   %v = call i32 @get_i32(), !range !{i32 0, i32 10}
   %c1 = icmp ult i32 %v, 10
   call void @use(i1 %c1)
   %c2 = icmp ult i32 %v, 9
   call void @use(i1 %c2)
   %c3 = icmp ugt i32 %v, 9
   call void @use(i1 %c3)
   %c4 = icmp ugt i32 %v, 8
   call void @use(i1 %c4)
   ret void
 }
 
 define internal i1 @ip_cmp_range(i32 %v) {
 ; CHECK-LABEL: @ip_cmp_range(
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[V:%.*]], 10
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 undef
 ;
   %c = icmp ult i32 %v, 10
   ret i1 %c
 }
 
 define i1 @ip_load_range(i32* %p) {
 ; CHECK-LABEL: @ip_load_range(
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4, !range !0
 ; CHECK-NEXT:    [[C:%.*]] = call i1 @ip_cmp_range(i32 [[V]])
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
   %v = load i32, i32* %p, !range !{i32 0, i32 10}
   %c = call i1 @ip_cmp_range(i32 %v)
   ret i1 %c
 }