[Attributor] fix AAValueConstantRange and IntegerRangeState implementation

[okura]

Summary

The current deduction of AAValueConstantRange is (maybe mistakenly) too conservative.
The following are the revised points:

1. unionKnown in IntegerRangeState ... I think we should not take union with a given range for assumed range.
2. AAValueConstantRangeFloating::initialize
   • Although we handle CallBase case in updateImpl, we give up in initialize in the case.
   • Propagate known states for cast instructions.

[okura]

llvm/test/Transforms/Attributor/range.ll

2

An assumed range for the argument %depth of @rec in this test grows one by one during iterations. So we need a very big number of iterations to reach a fixpoint and I have difficulty in using attributor-max-iterations-verify option here.

[uenoku]

Why can't we take a union of assumed range?

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

6964

I'm not sure this propagation is necessary in initialize but at least, we need TrackDpencdence = false here.

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

6964

For example, we can get [0,2) as a known range for %a instead of [0,inf) in the following case. And this propagation is needed for a value simplification in the case of @potential_test3 in potential.ll.

%a = zext i1 %bool to i32

but at least, we need TrackDpencdence = false here.

I'll fix that.

[jdoerfert]

This patch addresses three unrelated things and we need to split it, assuming all points need to be addressed.

llvm/include/llvm/Transforms/IPO/Attributor.h

1956

This looks dangerous as we might end up with a known range that is not subsumed in the assumed range.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

6964

Why wouldn't that information be propagated during the update? Could you explain where it is lost?

[okura]

llvm/include/llvm/Transforms/IPO/Attributor.h

1956

I'm not sure why a known range should be subsumed in the assumed range. Isn't it the other way around? For example, a known range and assumed range are initialized with full and empty respectively, and the assumed range is subsumed in the known range.
The following is another example. Let us assume the two returned values have the same state <full / [0,1)>. I think a clamped state for the returned position should be <full / [0,1)>. However, the clamped state is <full / full> with the current implementation.

i32 @foo(){
  ...
  ret i32 %bar
  ...
  ret i32 %baz
}

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

6964

Why wouldn't that information be propagated during the update?

I thought this propagation in initialize is sufficient but I noticed that a known range would be better during the update. I'll move this into updateImpl.

Could you explain where it is lost?

The dependency type in calculateCastInst is now REQUIRED. So If the operand's AA becomes invalid first, the known range is never propagated.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

6964

Adding deps in initialize is problematic. Because initialize will not be called if the dependent attribute gets changed, only the updateAA will be called. In this instance you are only using the known information, it is not as big of a deal here but we should have the 'TrackDpencdence = false` here anyways.

Aside from this
Doing this kind of propagation in initialize can be problematic in CGSCC pass since we call initialize on AAs that belong to functions other than functions that are in the SCC. I will send a patch that makes sure we don't manifest that information real soon. We should look at how this would effect the changes in the tests.

[kuter]

Hi can you try this on top of D86081

[okura]

In D86018#2221526, @kuter wrote:

Hi can you try this on top of D86081

As I mentioned above, I will move this propagation into updateImpl. Therefore, I think the problem that you are concerned about will not occur.

[kuter]

In D86018#2222956, @okura wrote:

In D86018#2221526, @kuter wrote:

Hi can you try this on top of D86081

As I mentioned above, I will move this propagation into updateImpl. Therefore, I think the problem that you are concerned about will not occur.

Sorry, I did not see the comment above.

[uenoku]

llvm/include/llvm/Transforms/IPO/Attributor.h

1956

I think @okura is correct. I don't remember but it looks I mistakenly implemented ;)

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

1956

I'll trust you then. Make it a standalone commit though please.

[okura]

This was split into some patches.

llvm/include/llvm/Transforms/IPO/Attributor.h

struct IntegerRangeState : public AbstractState {
   void unionAssumed(const IntegerRangeState &R) {
     unionAssumed(R.getAssumed());
   }
 
   /// Unite known range with the passed state.
   void unionKnown(const ConstantRange &R) {
     // Don't loose a known range.
     Known = Known.unionWith(R);
-    Assumed = Assumed.unionWith(Known);
   }
 
   /// See IntegerRangeState::unionKnown(..).
   void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); }
 
   /// Intersect known range with the passed state.
   void intersectKnown(const ConstantRange &R) {
     Assumed = Assumed.intersectWith(R);

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

void initialize(Attributor &A) override {
 
     if (isa<UndefValue>(&V)) {
       // Collapse the undef state to 0.
       unionAssumed(ConstantRange(APInt(getBitWidth(), 0)));
       indicateOptimisticFixpoint();
       return;
     }
 
-    if (isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<CastInst>(&V))
+    if (isa<CallBase>(&V))
       return;
+
+    if (isa<BinaryOperator>(&V) || isa<CmpInst>(&V))
+      return;
+
+    // Propagate known state for cast instructions.
+    if (CastInst *CI = dyn_cast<CastInst>(&V)) {
+      Value &OpV = *CI->getOperand(0);
+      if (!OpV.getType()->isIntegerTy())
+        return;
+      auto &OpAA =
+          A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(OpV));
+      intersectKnown(
+          OpAA.getKnown().castOp(CI->getOpcode(), getState().getBitWidth()));
+      return;
+    }
+
     // If it is a load instruction with range metadata, use it.
     if (LoadInst *LI = dyn_cast<LoadInst>(&V))
       if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) {
         intersectKnown(getConstantRangeFromMetadata(*RangeMD));
         return;
       }
 
     // We can work with PHI and select instruction as we traverse their operands

llvm/test/Transforms/Attributor/potential.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes --check-attributes
 ; RUN: opt -attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=10 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
-; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
 ; RUN: opt -attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM
 ; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM
 ;
 ; Test for multiple potential values
 ;
 ; potential-test 1
 ; bool iszero(int c) { return c == 0; }
 ; bool potential_test1(bool c) { return iszero(c ? 1 : -1); }

 ; potential values of argument of g are {0,1}
 ; potential value of returned value of g is 1
 ; then returned value of g can be simplified
 ;
 ; int zero_or_one(int c) { return c < 2; }
 ; int potential_test3() { return zero_or_one(iszero(0))+zero_or_one(iszero(1)); }
 
 define internal i32 @iszero3(i32 %c) {
-; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn
-; IS__TUNIT____-LABEL: define {{[^@]+}}@iszero3
-; IS__TUNIT____-SAME: (i32 [[C:%.*]])
-; IS__TUNIT____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
-; IS__TUNIT____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
-; IS__TUNIT____-NEXT:    ret i32 [[RET]]
-;
 ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
 ; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero3
 ; IS__CGSCC____-SAME: (i32 [[C:%.*]])
 ; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
 ; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
 ; IS__CGSCC____-NEXT:    ret i32 [[RET]]
 ;
   %cmp = icmp eq i32 %c, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 define internal i32 @less_than_two(i32 %c) {
-; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn
-; IS__TUNIT____-LABEL: define {{[^@]+}}@less_than_two
-; IS__TUNIT____-SAME: (i32 [[C:%.*]])
-; IS__TUNIT____-NEXT:    [[CMP:%.*]] = icmp slt i32 [[C]], 2
-; IS__TUNIT____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
-; IS__TUNIT____-NEXT:    ret i32 [[RET]]
-;
 ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
 ; IS__CGSCC____-LABEL: define {{[^@]+}}@less_than_two
 ; IS__CGSCC____-SAME: (i32 [[C:%.*]])
 ; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp slt i32 [[C]], 2
 ; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
 ; IS__CGSCC____-NEXT:    ret i32 [[RET]]
 ;
   %cmp = icmp slt i32 %c, 2
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 define i32 @potential_test3() {
-; IS__TUNIT_OPM: Function Attrs: nofree nosync nounwind readnone willreturn
-; IS__TUNIT_OPM-LABEL: define {{[^@]+}}@potential_test3()
-; IS__TUNIT_OPM-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0)
-; IS__TUNIT_OPM-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]])
-; IS__TUNIT_OPM-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1)
-; IS__TUNIT_OPM-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]])
-; IS__TUNIT_OPM-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]
-; IS__TUNIT_OPM-NEXT:    ret i32 [[RET]]
-;
-; IS__TUNIT_NPM: Function Attrs: nofree nosync nounwind readnone willreturn
-; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@potential_test3()
-; IS__TUNIT_NPM-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0) [[ATTR0:#.*]], [[RNG0:!range !.*]]
-; IS__TUNIT_NPM-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) [[ATTR0]], [[RNG0]]
-; IS__TUNIT_NPM-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1) [[ATTR0]], [[RNG0]]
-; IS__TUNIT_NPM-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) [[ATTR0]], [[RNG0]]
-; IS__TUNIT_NPM-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]
-; IS__TUNIT_NPM-NEXT:    ret i32 [[RET]]
+; IS__TUNIT____: Function Attrs: nofree nosync nounwind readnone willreturn
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test3()
+; IS__TUNIT____-NEXT:    ret i32 2
 ;
 ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
 ; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test3()
 ; IS__CGSCC____-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0)
 ; IS__CGSCC____-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]])
 ; IS__CGSCC____-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1)
 ; IS__CGSCC____-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]])
 ; IS__CGSCC____-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]

llvm/test/Transforms/Attributor/range.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes --check-attributes
-; RUN: opt -attributor -enable-new-pm=0 -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=17 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
-; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=17 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
+; RUN: opt -attributor -enable-new-pm=0 -attributor-manifest-internal -attributor-annotate-decl-cs -attributor-max-iterations=17 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-annotate-decl-cs -attributor-max-iterations=17 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
 ; RUN: opt -attributor-cgscc -enable-new-pm=0 -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM
 ; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM
 
 ; FIXME: CGSCC is not looking at callees and calleers even though it could be allowed.
 
 define i32 @test0(i32* %p) {
 ; IS__TUNIT____: Function Attrs: argmemonly nofree nosync nounwind readonly willreturn
 ; IS__TUNIT____-LABEL: define {{[^@]+}}@test0

llvm/test/Transforms/Attributor/willreturn.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes --check-attributes
-; RUN: opt -attributor -enable-new-pm=0 -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
-; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
+; RUN: opt -attributor -enable-new-pm=0 -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
 ; RUN: opt -attributor-cgscc -enable-new-pm=0 -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM
 ; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM
 
 target datalayout = "e-m:e-i54:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for the "willreturn" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.