[SCCP] Add range metadata to call sites with known return ranges.

[fhahn]

Summary

If we inferred a range for the function return value, we can add !range
at all call-sites of the function, if the range does not include undef.

[efriedma]

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

28

What does it mean to say the range doesn't "include undef", here?

If the argument is poison, does this introduce UB?

[fhahn]

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

28

What does it mean to say the range doesn't "include undef", here?

It is meant to refer to the 'range including undef' notion in ValueLattice. So it means that we know the result value cannot be undef, because all values merged with the return value state are known to not be undef. Reading it back it seems on its own it is not entirely clear. Please let me know if that makes sense, then I'll update the comment.

If the argument is poison, does this introduce UB?

Hm, thinking a bit more about it, I guess it could.

So for this example function, if %x would be poison, the result of the AND would also be poison, but we would add the range metadata nonetheless.
But returning a value outside of the !range is UB. So I guess we introduced extra UB because poison is outside the range. Was that the case you had in mind?

It seems like the fact that returning values outside of !range is immediate UB makes it quite tricky to synthesize !range in the presence of of poison generally.

I suppose we have 2 options here:

1. Check that the return value is guaranteed to not be poison before adding the range.
2. Adjusting the definition of !range for calls to make returning poison (= always outside the range) lead to poison, rather than immediate UB or making returning values outside the range poison directly instead.

Doing 1. in the patch should be fairly straight forward, but 2. might be more beneficial in the long term. What do you think?

[nikic]

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

28

Adjusting the definition of !range for calls to make returning poison (= always outside the range) lead to poison, rather than immediate UB or making returning values outside the range poison directly instead.

This is the direction things are moving for call attributes, though I don't think any patches are up yet. Things like nonnull will only yield poison, and immediate UB will be introduced (if desired) by the noundef attribute. Keeping that in mind, it would make sense if !range and !nonnull followed the same behavior.

[fhahn]

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

28

This is the direction things are moving for call attributes, though I don't think any patches are up yet. Things like nonnull will only yield poison, and immediate UB will be introduced (if desired) by the noundef attribute. Keeping that in mind, it would make sense if !range and !nonnull followed the same behavior.

Hm, having direct UB seems more convenient for the consumers of the metadata, as it rules out the result being poison/undef, allowing the information to be used directly. If we relax it to poison, things might get more difficult for consumers. But then, for callsites there's the noundef attribute to restore old behavior. That leaves loads, for which there would be no way to restore immediate UB I think.

[fhahn]

For now, require the call result value to not be undef or poison.

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstVisitor.h"
bool llvm::runIPSCCP(
   // actually zap their returns.  This is important because we can only do this
   // if the address of the function isn't taken.  In cases where a return is the
   // last use of a function, the order of processing functions would affect
   // whether other functions are optimizable.
   SmallVector<ReturnInst*, 8> ReturnsToZap;
 
   for (const auto &I : Solver.getTrackedRetVals()) {
     Function *F = I.first;
-    if (isOverdefined(I.second) || F->getReturnType()->isVoidTy())
+    const ValueLatticeElement &ReturnValue = I.second;
+
+    // If there is a known constant range for the return value, add !range
+    // metadata to the function's call sites.
+    if (ReturnValue.isConstantRange() &&
+        !ReturnValue.getConstantRange().isSingleElement()) {
+      // Do not add range metadata if the return value may include undef.
+      if (ReturnValue.isConstantRangeIncludingUndef())
+        continue;
+
+      auto &CR = ReturnValue.getConstantRange();
+      for (User *User : F->users()) {
+        auto *CB = dyn_cast<CallBase>(User);
+        if (!CB || CB->getCalledFunction() != F)
+          continue;
+
+        // Limit to cases where the return value is guaranteed to be neither
+        // poison nor undef. Poison will be outside any range and currently
+        // values outside of the specified range cause immediate undefined
+        // behavior.
+        if (!isGuaranteedNotToBeUndefOrPoison(CB, CB))
+          continue;
+
+        // Do not touch existing metadata for now.
+        // TODO: We should be able to take the intersection of the existing
+        // metadata and the inferred range.
+        if (CB->getMetadata(LLVMContext::MD_range))
+          continue;
+
+        LLVMContext &Context = CB->getParent()->getContext();
+        Metadata *RangeMD[] = {
+            ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())),
+            ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))};
+        CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
+      }
+      continue;
+    }
+    if (F->getReturnType()->isVoidTy())
       continue;
+    if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
       findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   for (auto F : Solver.getMRVFunctionsTracked()) {
     assert(F->getReturnType()->isStructTy() &&
            "The return type should be a struct");
     StructType *STy = cast<StructType>(F->getReturnType());
     if (Solver.isStructLatticeConstant(F, STy))
       findReturnsToZap(*F, ReturnsToZap, Solver);

llvm/test/Transforms/SCCP/ip-add-range-to-call.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -ipsccp -S %s | FileCheck %s
 
 ; Test 1.
 ; Both arguments and return value of @callee can be tracked. The inferred range
 ; can be added to call sites.
-define internal i32 @callee(i32 %x) {
+define internal noundef i32 @callee(i32 %x) {
 ; CHECK-LABEL: @callee(
 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   ret i32 %x
 }
 
 define i32 @caller1() {
 ; CHECK-LABEL: @caller1(
-; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee(i32 10)
-; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee(i32 20)
+; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee(i32 10), !range [[RANGE_10_21:![0-9]+]]
+; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee(i32 20), !range [[RANGE_10_21]]
 ; CHECK-NEXT:    [[A:%.*]] = add i32 [[C1]], [[C2]]
 ; CHECK-NEXT:    ret i32 [[A]]
 ;
   %c1 = call i32 @callee(i32 10)
   %c2 = call i32 @callee(i32 20)
   %a = add i32 %c1, %c2
   ret i32 %a
 }
 
 define i32 @caller2(i32 %x) {
 ; CHECK-LABEL: @caller2(
 ; CHECK-NEXT:    [[X_15:%.*]] = and i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[C:%.*]] = call i32 @callee(i32 [[X_15]])
+; CHECK-NEXT:    [[C:%.*]] = call i32 @callee(i32 [[X_15]]), !range [[RANGE_10_21]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %x.15 = and i32 %x, 15
   %c = call i32 @callee(i32 %x.15)
   ret i32 %c
 }
 
 ; Test 2.
 ; The return value of @callee2 can be tracked, but arguments cannot, because
 ; it is passed to @use_cb1. We cannot infer a range for the return value, no
 ; metadata should be added.
 
 declare void @use_cb1(i32 (i32)*)
 
-define internal i32 @callee2(i32 %x) {
+define internal noundef i32 @callee2(i32 %x) {
 ; CHECK-LABEL: @callee2(
 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   ret i32 %x
 }
 
 define void @caller_cb1() {
 ; CHECK-LABEL: @caller_cb1(
 ; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee2(i32 9)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee2(i32 10)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    call void @use_cb1(i32 (i32)* @callee2)
 ; CHECK-NEXT:    ret void
 ;
   %c1 = call i32 @callee2(i32 9)
   %c2 = call i32 @callee2(i32 10)
   call void @use_cb1(i32 (i32)* @callee2)
   ret void
 }
 
 ; Test 3.
 ; The return value can be tracked and it the result range ([500, 601) does not
 ; depend on the arguments, which cannot be tracked because @callee3 is passed
 ; to @use_cb2. The result range can be added to the call sites of @callee.
 
 declare void @use_cb2(i32 (i32)*)
 
-define internal i32 @callee3(i32 %x) {
+define internal noundef i32 @callee3(i32 %x) {
 ; CHECK-LABEL: @callee3(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 10
 ; CHECK-NEXT:    [[S:%.*]] = select i1 [[C]], i32 500, i32 600
 ; CHECK-NEXT:    ret i32 [[S]]
 ;
   %c = icmp eq i32 %x, 10
   %s = select i1 %c, i32 500, i32 600
   ret i32 %s
 }
 
 define void @caller_cb2() {
 ; CHECK-LABEL: @caller_cb2(
-; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee3(i32 9)
-; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee3(i32 10)
+; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee3(i32 9), !range [[RANGE_500_601:![0-9]+]]
+; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee3(i32 10), !range [[RANGE_500_601]]
 ; CHECK-NEXT:    call void @use_cb2(i32 (i32)* @callee3)
 ; CHECK-NEXT:    ret void
 ;
   %c1 = call i32 @callee3(i32 9)
   %c2 = call i32 @callee3(i32 10)
   call void @use_cb2(i32 (i32)* @callee3)
   ret void
 }
 
 ; Test 4.
 ; The return value of @callee4 can be tracked, but depends on an argument which
 ; cannot be tracked. No result range can be inferred.
 
 declare void @use_cb3(i32 (i32, i32)*)
 
-define internal i32 @callee4(i32 %x, i32 %y) {
+define internal noundef i32 @callee4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @callee4(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], 10
 ; CHECK-NEXT:    [[S:%.*]] = select i1 [[C]], i32 500, i32 [[Y:%.*]]
 ; CHECK-NEXT:    ret i32 [[S]]
 ;
   %c = icmp eq i32 %x, 10
   %s = select i1 %c, i32 500, i32 %y
   ret i32 %s
 }
 
 define void @caller_cb3() {
 ; CHECK-LABEL: @caller_cb3(
 ; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee4(i32 11, i32 30)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee4(i32 12, i32 40)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    call void @use_cb3(i32 (i32, i32)* @callee4)
 ; CHECK-NEXT:    ret void
 ;
   %c1 = call i32 @callee4(i32 11, i32 30)
   %c2 = call i32 @callee4(i32 12, i32 40)
   call void @use_cb3(i32 (i32, i32)* @callee4)
   ret void
 }
 
 ; Test 5.
 ; Range for the return value of callee5 includes undef. No range metadata
 ; should be added at call sites.
-define internal i32 @callee5(i32 %x, i32 %y) {
+define internal noundef i32 @callee5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @callee5(
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 15
 ; CHECK-NEXT:    br i1 [[C]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:

 exit:
   %res = phi i32 [ %y, %bb1 ], [ undef, %bb2]
   ret i32 %res
 }
 
 define i32 @caller5() {
 ; CHECK-LABEL: @caller5(
 ; CHECK-NEXT:    [[C1:%.*]] = call i32 @callee5(i32 10, i32 100)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    [[C2:%.*]] = call i32 @callee5(i32 20, i32 200)
+; CHECK-NOT:   !range
 ; CHECK-NEXT:    [[A:%.*]] = add i32 [[C1]], [[C2]]
 ; CHECK-NEXT:    ret i32 [[A]]
 ;
   %c1 = call i32 @callee5(i32 10, i32 100)
   %c2 = call i32 @callee5(i32 20, i32 200)
   %a = add i32 %c1, %c2
   ret i32 %a
 }
+
+; CHECK: [[RANGE_10_21]] = !{i32 0, i32 21}
+; CHECK: [[RANGE_500_601]] = !{i32 500, i32 601}