[Local] Use most generic range if K does not dominate J or K doesn't have a !noundef

[StephenFan]

Summary

Since D141386 has changed the return value of !range from IUB to poison,
metadata !range shouldn't be preserved even if K dominates J.

If this patch was accepted, I plan to adjust metadata !nonnull as well.
BTW, I found that metadata !noundef is not handled in combineMetadata,
is this intentional?

[nikic]

BTW, I found that metadata !noundef is not handled in combineMetadata, is this intentional?

No. I think we should actually fix this first, and then retain the !range of the first load if !noundef is also set. This will make sure that there are no performance regressions from this change.

[nikic]

The !noundef preservation fixes have landed, so I think this patch can now be adjusted to keep the metadata if !noundef is present on the dominating load.

[StephenFan]

Keep the metadata if J has !noundef

[nikic]

Could you please also add tests for the !noundef case? (Preferably one with the first load noundef and one with the second. I'm not sure you're checking the right one currently.)

[StephenFan]

Rebase and add test for load with !noundef

[StephenFan]

[StephenFan]

llvm/test/Transforms/GVN/range.ll

109

Now, this case is combined into the most generic range. But I think it is unnecessary.
Before transforming, there are 4 cases:

1. Both are satisfied. Return a well-defined value.
2. Both are violated. IUB.
3. !0 is violated and !1 is satisfied. IUB.
4. !0 is satisfied and !1 is violated. Return a poison value.

If we don't combine them into the most generic range and just retain !0.

1. Both are satisfied. Return a well-defined value.
2. Both are violated. IUB.
3. !0 is violated and !1 is satisfied. IUB.
4. !0 is satisfied and !1 is violated. Return a well-defined value.

The only difference is case 4. We transform returning a poison value to returning a well-defined value. But it is safe.

In summary, I think we don't need to combine them into the most generic range for this case, just retaining it is enough.
Do you agree with me @nikic?

[nikic]

llvm/test/Transforms/GVN/range.ll

109

Right, this is why I said you're checking noundef on the wrong instruction. It needs to be on K, not J. You can see in the case below that range !0 is retained, even though that one should actually use the generic range.

llvm/test/Transforms/JumpThreading/thread-loads.ll

330

Probably better to add !noundef here, otherwise this doesn't really match the code comment anymore.

[StephenFan]

llvm/test/Transforms/GVN/range.ll

121

@nikic Why do we need to use the generic range here?

1. Both are satisfied. Return a well-defined value.
2. Both are violated, IUB
3. !0 is satisified, !1 is violated. IUB.
4. !0 is violated, !1 is satisified. return a poison value.

If we retain !0:

1. Both are satisfied. Return a well-defined value.
2. Both are violated. Return a poison value.
3. !0 is satisfied, !1 is violated. Return a well-defined value
4. !0 is violated, !1 is satisfied. Return a poison value.

The differences are in case 2 and case 3. In case 2, transforming from IUB to return a poison value is safe. In case 3, transforming from IUB to return a poison value is also safe. Or do I misunderstand something?

[nikic]

llvm/test/Transforms/GVN/range.ll

121

You need to assume that the example is simplified, and what actually happens is that %a is never used (dynamically dead). In that case if !0 is violated but !1 is satisfied, this would return a poison value for %b, which is incorrect.

It's okay in this specific code sample (where both values are fed into the same operation), but this is not the point of these tests.

[StephenFan]

Use most generic range if K don't have a !noundef

[StephenFan]

Update title.

[nikic]

LGTM

llvm/lib/Transforms/Utils/Local.cpp

switch (Kind) {
       case LLVMContext::MD_mem_parallel_loop_access:
         K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
         break;
       case LLVMContext::MD_access_group:
         K->setMetadata(LLVMContext::MD_access_group,
                        intersectAccessGroups(K, J));
         break;
       case LLVMContext::MD_range:
-
-        // If K does move, use most generic range. Otherwise keep the range of
-        // K.
-        if (DoesKMove)
-          // FIXME: If K does move, we should drop the range info and nonnull.
-          //        Currently this function is used with DoesKMove in passes
-          //        doing hoisting/sinking and the current behavior of using the
-          //        most generic range is correct in those cases.
+        if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
           K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
         break;
       case LLVMContext::MD_fpmath:
         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
         break;
       case LLVMContext::MD_invariant_load:
         // Only set the !invariant.load if it is present in both instructions.
         K->setMetadata(Kind, JMD);

llvm/test/Transforms/GVN/range.ll

;
   %b = load i32, ptr %p, !range !0
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test2(ptr %p) {
 ; CHECK-LABEL: define i32 @test2
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test3(ptr %p) {
 ; CHECK-LABEL: define i32 @test3
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p, !range !1
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test4(ptr %p) {
 ; CHECK-LABEL: define i32 @test4
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p, !range !2
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test5(ptr %p) {
 ; CHECK-LABEL: define i32 @test5
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG3:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !3
   %b = load i32, ptr %p, !range !4
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test6(ptr %p) {
 ; CHECK-LABEL: define i32 @test6
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG4:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !5
   %b = load i32, ptr %p, !range !6
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test7(ptr %p) {
 ; CHECK-LABEL: define i32 @test7
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG3:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG5:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !7
   %b = load i32, ptr %p, !range !8
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test8(ptr %p) {
 ; CHECK-LABEL: define i32 @test8
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG4:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !9
   %b = load i32, ptr %p, !range !10
   %c = add i32 %a, %b
   ret i32 %c
 }
 
+define i32 @load_noundef_load(ptr %p) {
+; CHECK-LABEL: define i32 @load_noundef_load
+; CHECK-SAME: (ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]], !noundef !6
+; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %a = load i32, ptr %p, !range !0, !noundef !11
+  %b = load i32, ptr %p, !range !1
+  %c = add i32 %a, %b
+  ret i32 %c
+}
+
+define i32 @load_load_noundef(ptr %p) {
+; CHECK-LABEL: define i32 @load_load_noundef
+; CHECK-SAME: (ptr [[P:%.*]]) {
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1]]
+; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %a = load i32, ptr %p, !range !0
+  %b = load i32, ptr %p, !range !1, !noundef !11
+  %c = add i32 %a, %b
+  ret i32 %c
+}
 
 !0 = !{i32 0, i32 2}
 !1 = !{i32 3, i32 5}
 !2 = !{i32 2, i32 5}
 !3 = !{i32 -5, i32 -2}
 !4 = !{i32 1, i32 5}
 !5 = !{i32 10, i32 1}
 !6 = !{i32 12, i32 16}
 !7 = !{i32 1, i32 2, i32 3, i32 4}
 !8 = !{i32 5, i32 1}
 !9 = !{i32 1, i32 5}
 !10 = !{i32 5, i32 1}
+!11 = !{}
 ;.
 ; CHECK: [[RNG0]] = !{i32 0, i32 2}
-; CHECK: [[RNG1]] = !{i32 -5, i32 -2}
-; CHECK: [[RNG2]] = !{i32 10, i32 1}
-; CHECK: [[RNG3]] = !{i32 1, i32 2, i32 3, i32 4}
-; CHECK: [[RNG4]] = !{i32 1, i32 5}
+; CHECK: [[RNG1]] = !{i32 0, i32 2, i32 3, i32 5}
+; CHECK: [[RNG2]] = !{i32 0, i32 5}
+; CHECK: [[RNG3]] = !{i32 -5, i32 -2, i32 1, i32 5}
+; CHECK: [[RNG4]] = !{i32 10, i32 1}
+; CHECK: [[RNG5]] = !{i32 3, i32 4, i32 5, i32 2}
+; CHECK: [[META6:![0-9]+]] = !{}
 ;.

llvm/test/Transforms/JumpThreading/thread-loads.ll

 }
 
 ; Make sure we merge the aliasing metadata. We keep the range metadata for the
 ; first load, as it dominates the second load. Hence we can eliminate the
 ; branch.
 define void @test8(ptr, ptr, ptr) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  ret2:
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[TMP0:%.*]], align 4, !range [[RNG4:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[TMP0:%.*]], align 4, !range [[RNG4:![0-9]+]], !noundef !5
 ; CHECK-NEXT:    store i32 [[A]], ptr [[TMP1:%.*]], align 4
 ; CHECK-NEXT:    [[XXX:%.*]] = tail call i32 (...) @f1() #[[ATTR0]]
 ; CHECK-NEXT:    ret void
 ;
-  %a = load i32, ptr %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10
+  %a = load i32, ptr %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10, !noundef !11
   %b = load i32, ptr %0, !range !5
   store i32 %a, ptr %1
   %c = icmp eq i32 %b, 8
   br i1 %c, label %ret1, label %ret2
 
 ret1:
   ret void
 

 !3 = !{!"int", !1}
 !4 = !{ i32 0, i32 1 }
 !5 = !{ i32 8, i32 10 }
 !6 = !{!6}
 !7 = !{!7, !6}
 !8 = !{!8, !6}
 !9 = !{!7}
 !10 = !{!8}
+!11 = !{}

llvm/test/Transforms/NewGVN/range.ll

;
   %b = load i32, ptr %p, !range !0
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test2(ptr %p) {
 ; CHECK-LABEL: define i32 @test2
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test3(ptr %p) {
 ; CHECK-LABEL: define i32 @test3
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p, !range !1
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test4(ptr %p) {
 ; CHECK-LABEL: define i32 @test4
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !0
   %b = load i32, ptr %p, !range !2
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test5(ptr %p) {
 ; CHECK-LABEL: define i32 @test5
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG3:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !3
   %b = load i32, ptr %p, !range !4
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test6(ptr %p) {
 ; CHECK-LABEL: define i32 @test6
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG4:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !5
   %b = load i32, ptr %p, !range !6
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test7(ptr %p) {
 ; CHECK-LABEL: define i32 @test7
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG3:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG5:![0-9]+]]
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !7
   %b = load i32, ptr %p, !range !8
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 define i32 @test8(ptr %p) {
 ; CHECK-LABEL: define i32 @test8
 ; CHECK-SAME: (ptr [[P:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG4:![0-9]+]]
+; CHECK-NEXT:    [[A:%.*]] = load i32, ptr [[P]], align 4
 ; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[A]]
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %a = load i32, ptr %p, !range !9
   %b = load i32, ptr %p, !range !10
   %c = add i32 %a, %b
   ret i32 %c
 }
 
 
 !0 = !{i32 0, i32 2}
 !1 = !{i32 3, i32 5}
 !2 = !{i32 2, i32 5}
 !3 = !{i32 -5, i32 -2}
 !4 = !{i32 1, i32 5}
 !5 = !{i32 10, i32 1}
 !6 = !{i32 12, i32 16}
 !7 = !{i32 1, i32 2, i32 3, i32 4}
 !8 = !{i32 5, i32 1}
 !9 = !{i32 1, i32 5}
 !10 = !{i32 5, i32 1}
 ;.
 ; CHECK: [[RNG0]] = !{i32 0, i32 2}
-; CHECK: [[RNG1]] = !{i32 -5, i32 -2}
-; CHECK: [[RNG2]] = !{i32 10, i32 1}
-; CHECK: [[RNG3]] = !{i32 1, i32 2, i32 3, i32 4}
-; CHECK: [[RNG4]] = !{i32 1, i32 5}
+; CHECK: [[RNG1]] = !{i32 0, i32 2, i32 3, i32 5}
+; CHECK: [[RNG2]] = !{i32 0, i32 5}
+; CHECK: [[RNG3]] = !{i32 -5, i32 -2, i32 1, i32 5}
+; CHECK: [[RNG4]] = !{i32 10, i32 1}
+; CHECK: [[RNG5]] = !{i32 3, i32 4, i32 5, i32 2}
 ;.