[GVN] permit GVN of non-local loads for ASAN unless undef or alloca is produced

[nickdesaulniers]

Summary

A "non-local load" is the load of value from a pointer defined in
another basic block than the basic block of the load.

While compiling the Linux kernel with CONFIG_FORTIFY_SOURCE=y and
CONFIG_KASAN=y, we discovered a curious case where a repeated condition
check that should have been optimized out was not.

It looks like GVN's ability to process "non local loads" was simply
disabled outright in pr25924 due to an external report.

That fix was too broad IMO. While we do want ASAN (and HWASAN) to help
us spot loads that produce undef, since those are likely OOB reads, it
still would be nice when we don't have undef to allow GVN to proceed. I
think this is a better balance. It should allow us to better optimize
KASAN binaries without regressions in the sanitizer's ability to help
spot OOB access.

Another important case to check is alloca; alloca is by definition not
initialized.

Tested with the original reproducer from the mailing list, as well as
the above linux kernel configs.

See also the original fix:
commit c7810baaa676 ("Disable gvn non-local speculative loads under asan.")

Link: https://github.com/ClangBuiltLinux/linux/issues/1687
Link: https://github.com/llvm/llvm-project/issues/25924
Link: https://lists.llvm.org/pipermail/llvm-dev/2015-November/092427.html
Link: http://lists.llvm.org/pipermail/llvm-dev/attachments/20151114/1c7d8dbe/attachment.c

[nickdesaulniers]

• typo in commit message

[nickdesaulniers]

• update commit oneline

[nickdesaulniers]

• include sha of original fix in commit message

[nikic]

I don't think this is right as implemented. Imagine you have if (...) { store v, p } x = load p. GVN would convert this to something like x = phi(v, undef). With asan, we want this to report if the if is not taken. However, I believe that your checks will permit the transform, because the load folding result is not literally undef (but is still undef on one path).

[nickdesaulniers]

In D144057#4128142, @nikic wrote:

I don't think this is right as implemented. Imagine you have if (...) { store v, p } x = load p. GVN would convert this to something like x = phi(v, undef). With asan, we want this to report if the if is not taken. However, I believe that your checks will permit the transform, because the load folding result is not literally undef (but is still undef on one path).

Is this what you're imagining? https://godbolt.org/z/Pc3YezE44

Seems like ASAN already misses that? In this case, we go to replace the load with alloca, so adding a check remedies that case. But it doesn't change the fact that asan misses that C test case.

[nickdesaulniers]

• check for alloca as well

[melver]

Pinging @eugenis @fmayer @pcc who may have more recently touched ASan/HWASan.

Not an expert in GVN, but your reasoning makes sense. Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

[eugenis]

Not convinced that this is right. The original fix is for a false postive, not a false negative - i.e., we want to prevent speculation of a memory access that is not provably safe.

See https://lists.llvm.org/pipermail/llvm-dev/2015-November/092484.html. Note that the report is on heap memory, not alloca.

[nickdesaulniers]

In D144057#4168117, @eugenis wrote:

Not convinced that this is right. The original fix is for a false postive, not a false negative - i.e., we want to prevent speculation of a memory access that is not provably safe.

See https://lists.llvm.org/pipermail/llvm-dev/2015-November/092484.html. Note that the report is on heap memory, not alloca.

I tested my change against the original bug report; the artifact is still live and linked from there. It does not regress the original false positive report.

[nikic]

In D144057#4130597, @nickdesaulniers wrote:

In D144057#4128142, @nikic wrote:

I don't think this is right as implemented. Imagine you have if (...) { store v, p } x = load p. GVN would convert this to something like x = phi(v, undef). With asan, we want this to report if the if is not taken. However, I believe that your checks will permit the transform, because the load folding result is not literally undef (but is still undef on one path).

Is this what you're imagining? https://godbolt.org/z/Pc3YezE44

Seems like ASAN already misses that? In this case, we go to replace the load with alloca, so adding a check remedies that case. But it doesn't change the fact that asan misses that C test case.

In this case SROA should drop the alloca and it will never get to GVN. You want something more like this: https://godbolt.org/z/8z66K7xbh

I still don't think that this makes sense as-implemented. You are only checking the final result after SSA construction. I believe this needs to at least check all AvailableValues for isUndefValue().

llvm/lib/Transforms/Scalar/GVN.cpp

1773

I don't get the alloca check here. V is the result of the load, not the loaded pointer.

[nickdesaulniers]

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

In D144057#4175101, @nikic wrote:

You want something more like this: https://godbolt.org/z/8z66K7xbh

Does ASAN catch that case? ;)

[melver]

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

[nickdesaulniers]

In D144057#4175101, @nikic wrote:

In D144057#4130597, @nickdesaulniers wrote:

In D144057#4128142, @nikic wrote:

I don't think this is right as implemented. Imagine you have if (...) { store v, p } x = load p. GVN would convert this to something like x = phi(v, undef). With asan, we want this to report if the if is not taken. However, I believe that your checks will permit the transform, because the load folding result is not literally undef (but is still undef on one path).

Is this what you're imagining? https://godbolt.org/z/Pc3YezE44

Seems like ASAN already misses that? In this case, we go to replace the load with alloca, so adding a check remedies that case. But it doesn't change the fact that asan misses that C test case.

In this case SROA should drop the alloca and it will never get to GVN. You want something more like this: https://godbolt.org/z/8z66K7xbh

I still don't think that this makes sense as-implemented. You are only checking the final result after SSA construction. I believe this needs to at least check all AvailableValues for isUndefValue().

Something like this?

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index f36fa0bd0979..ca80c0b40557 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1781,11 +1781,14 @@ bool GVNPass::processNonLocalLoad(LoadInst *Load) {
     // If a non-local load would result in producing undef or an alloca (which
     // is not initialized), don't fold away control flow. We want the
     // sanitizers to help report this case.
-    if (isa<UndefValue>(V) || isa<AllocaInst>(V)) {
-      Function *F = Load->getParent()->getParent();
-      if (F->hasFnAttribute(Attribute::SanitizeAddress) ||
-          F->hasFnAttribute(Attribute::SanitizeHWAddress))
-        return false;
+    Function *F = Load->getParent()->getParent();
+    if (F->hasFnAttribute(Attribute::SanitizeAddress) ||
+        F->hasFnAttribute(Attribute::SanitizeHWAddress)) {
+      for (AvailableValueInBlock &AV : ValuesPerBlock) {
+        if (AV.AV.isUndefValue()) {
+          return false;
+        }
+      }
     }
 
     Load->replaceAllUsesWith(V);

That doesn't seem to work, though perhaps you envisioned something else?

In D144057#4180735, @melver wrote:

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

I've done so and the system boots. Was there supposed to be anything printed to the console? I just enabled KASAN=y, KUNIT=y, KASAN_KUNIT_TEST=y.

[pcc]

In D144057#4310913, @nickdesaulniers wrote:

In D144057#4175101, @nikic wrote:

In D144057#4130597, @nickdesaulniers wrote:

In D144057#4128142, @nikic wrote:

I don't think this is right as implemented. Imagine you have if (...) { store v, p } x = load p. GVN would convert this to something like x = phi(v, undef). With asan, we want this to report if the if is not taken. However, I believe that your checks will permit the transform, because the load folding result is not literally undef (but is still undef on one path).

Is this what you're imagining? https://godbolt.org/z/Pc3YezE44

Seems like ASAN already misses that? In this case, we go to replace the load with alloca, so adding a check remedies that case. But it doesn't change the fact that asan misses that C test case.

In this case SROA should drop the alloca and it will never get to GVN. You want something more like this: https://godbolt.org/z/8z66K7xbh

I still don't think that this makes sense as-implemented. You are only checking the final result after SSA construction. I believe this needs to at least check all AvailableValues for isUndefValue().

Something like this?

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index f36fa0bd0979..ca80c0b40557 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1781,11 +1781,14 @@ bool GVNPass::processNonLocalLoad(LoadInst *Load) {
     // If a non-local load would result in producing undef or an alloca (which
     // is not initialized), don't fold away control flow. We want the
     // sanitizers to help report this case.
-    if (isa<UndefValue>(V) || isa<AllocaInst>(V)) {
-      Function *F = Load->getParent()->getParent();
-      if (F->hasFnAttribute(Attribute::SanitizeAddress) ||
-          F->hasFnAttribute(Attribute::SanitizeHWAddress))
-        return false;
+    Function *F = Load->getParent()->getParent();
+    if (F->hasFnAttribute(Attribute::SanitizeAddress) ||
+        F->hasFnAttribute(Attribute::SanitizeHWAddress)) {
+      for (AvailableValueInBlock &AV : ValuesPerBlock) {
+        if (AV.AV.isUndefValue()) {
+          return false;
+        }
+      }
     }
 
     Load->replaceAllUsesWith(V);

That doesn't seem to work, though perhaps you envisioned something else?

In D144057#4180735, @melver wrote:

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

I've done so and the system boots. Was there supposed to be anything printed to the console? I just enabled KASAN=y, KUNIT=y, KASAN_KUNIT_TEST=y.

I think you also need to enable CONFIG_FTRACE=y or patch the kernel to have the config KASAN_KUNIT_TEST select TRACING. See https://lore.kernel.org/all/[e-mail]/

[nickdesaulniers]

In D144057#4310957, @pcc wrote:

In D144057#4180735, @melver wrote:

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

I've done so and the system boots. Was there supposed to be anything printed to the console? I just enabled KASAN=y, KUNIT=y, KASAN_KUNIT_TEST=y.

I think you also need to enable CONFIG_FTRACE=y or patch the kernel to have the config KASAN_KUNIT_TEST select TRACING. See https://lore.kernel.org/all/[e-mail]/

$ grep -rn -e FTRACE=y -e KASAN=y -e KUNIT=y -e KASAN_KUNIT .config
665:CONFIG_HAVE_KPROBES_ON_FTRACE=y
4942:CONFIG_HAVE_ARCH_KASAN=y
4947:CONFIG_KASAN=y
4954:CONFIG_KASAN_KUNIT_TEST=y
5050:CONFIG_HAVE_DYNAMIC_FTRACE=y
5069:CONFIG_FTRACE=y
5139:CONFIG_KUNIT=y

(I did have that enabled) ;)

[pcc]

In D144057#4311029, @nickdesaulniers wrote:

In D144057#4310957, @pcc wrote:

In D144057#4180735, @melver wrote:

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

I've done so and the system boots. Was there supposed to be anything printed to the console? I just enabled KASAN=y, KUNIT=y, KASAN_KUNIT_TEST=y.

I think you also need to enable CONFIG_FTRACE=y or patch the kernel to have the config KASAN_KUNIT_TEST select TRACING. See https://lore.kernel.org/all/[e-mail]/

$ grep -rn -e FTRACE=y -e KASAN=y -e KUNIT=y -e KASAN_KUNIT .config
665:CONFIG_HAVE_KPROBES_ON_FTRACE=y
4942:CONFIG_HAVE_ARCH_KASAN=y
4947:CONFIG_KASAN=y
4954:CONFIG_KASAN_KUNIT_TEST=y
5050:CONFIG_HAVE_DYNAMIC_FTRACE=y
5069:CONFIG_FTRACE=y
5139:CONFIG_KUNIT=y

(I did have that enabled) ;)

Huh, that should be enough to run the tests. You should be seeing a lot of console output spew at boot time ending in something like:

[   11.399154] ok 1 kasan

(or not ok 1 kasan if any of the tests failed). It works for me in the arm64 kernel, both master and next.

[nickdesaulniers]

In D144057#4311285, @pcc wrote:

In D144057#4311029, @nickdesaulniers wrote:

In D144057#4310957, @pcc wrote:

In D144057#4180735, @melver wrote:

In D144057#4179643, @nickdesaulniers wrote:

In D144057#4166558, @melver wrote:

Do the KASAN tests in the kernel pass (need to use -next, mainline is currently broken)? Wondering how we can double check there are no new false positives nor false negatives.

How do I run those?

Just CONFIG_KASAN_KUNIT_TEST=y should do and then boot kernel.

I've done so and the system boots. Was there supposed to be anything printed to the console? I just enabled KASAN=y, KUNIT=y, KASAN_KUNIT_TEST=y.

I think you also need to enable CONFIG_FTRACE=y or patch the kernel to have the config KASAN_KUNIT_TEST select TRACING. See https://lore.kernel.org/all/[e-mail]/

$ grep -rn -e FTRACE=y -e KASAN=y -e KUNIT=y -e KASAN_KUNIT .config
665:CONFIG_HAVE_KPROBES_ON_FTRACE=y
4942:CONFIG_HAVE_ARCH_KASAN=y
4947:CONFIG_KASAN=y
4954:CONFIG_KASAN_KUNIT_TEST=y
5050:CONFIG_HAVE_DYNAMIC_FTRACE=y
5069:CONFIG_FTRACE=y
5139:CONFIG_KUNIT=y

(I did have that enabled) ;)

Huh, that should be enough to run the tests. You should be seeing a lot of console output spew at boot time ending in something like:

[   11.399154] ok 1 kasan

(or not ok 1 kasan if any of the tests failed). It works for me in the arm64 kernel, both master and next.

Sorry, I may have been booting the wrong kernel image. With D144057 applied and the above kconfigs on x86_64, I see:

[    5.923941] # kasan: pass:44 fail:0 skip:14 total:58
[    5.926411] # Totals: pass:44 fail:0 skip:14 total:58
[    5.927858] ok 1 kasan

llvm/lib/Transforms/Scalar/GVN.cpp

return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
            << setExtraArgs() << " in favor of "
            << NV("InfavorOfValue", AvailableValue);
   });
 }
 
 /// Attempt to eliminate a load whose dependencies are
 /// non-local by performing PHI construction.
 bool GVNPass::processNonLocalLoad(LoadInst *Load) {
-  // non-local speculations are not allowed under asan.
-  if (Load->getParent()->getParent()->hasFnAttribute(
-          Attribute::SanitizeAddress) ||
-      Load->getParent()->getParent()->hasFnAttribute(
-          Attribute::SanitizeHWAddress))
-    return false;
-
   // Step 1: Find the non-local dependencies of the load.
   LoadDepVect Deps;
   MD->getNonLocalPointerDependency(Load, Deps);
 
   // If we had to process more than one hundred blocks to find the
   // dependencies, this load isn't worth worrying about.  Optimizing
   // it will be too expensive.
   unsigned NumDeps = Deps.size();
bool GVNPass::processNonLocalLoad(LoadInst *Load) {
   // If all of the instructions we depend on produce a known value for this
   // load, then it is fully redundant and we can use PHI insertion to compute
   // its value.  Insert PHIs and remove the fully redundant value now.
   if (UnavailableBlocks.empty()) {
     LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
 
     // Perform PHI construction.
     Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
+
+    // If a non-local load would result in producing undef, don't fold away
+    // control flow. We want the sanitizers to help report this case.
+    if (isa<UndefValue>(V)) {
+      Function *F = Load->getParent()->getParent();
+      if (F->hasFnAttribute(Attribute::SanitizeAddress) ||
+          F->hasFnAttribute(Attribute::SanitizeHWAddress))
+        return false;
+    }
+
     Load->replaceAllUsesWith(V);
 
     if (isa<PHINode>(V))
       V->takeName(Load);
     if (Instruction *I = dyn_cast<Instruction>(V))
       // If instruction I has debug info, then we should not update it.
       // Also, if I has a null DebugLoc, then it is still potentially incorrect
       // to propagate Load's DebugLoc because Load may not post-dominate I.

llvm/test/Transforms/GVN/no_speculative_loads_with_asan.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=gvn -S %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 declare noalias ptr @_Znam(i64) #1
 
-; Load of %i8 is an out of bounds load, which is folded to poison, which allows
+; Load of %i8 is an out of bounds load, which is folded to undef, which allows
 ; us to elide the phi.
 define i32 @TestNoAsan() {
 ; CHECK-LABEL: @TestNoAsan(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = tail call noalias ptr @_Znam(i64 2)
 ; CHECK-NEXT:    [[I1:%.*]] = getelementptr inbounds i8, ptr [[I]], i64 1
 ; CHECK-NEXT:    store i8 0, ptr [[I1]], align 1
 ; CHECK-NEXT:    store i8 0, ptr [[I]], align 1

 ; CHECK:       if.then:
 ; CHECK-NEXT:    store ptr [[NEIGH_SOCK_4]], ptr [[SA_ADDR_I]], align 8
 ; CHECK-NEXT:    br label [[WHILE_COND_I:%.*]]
 ; CHECK:       while.cond.i:
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr @node_from_ndev_ip_root_0, align 4
 ; CHECK-NEXT:    [[TOBOOL_I:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_I]], label [[WHILE_BODY_I:%.*]], label [[NODE_FROM_NDEV_IP_EXIT:%.*]]
 ; CHECK:       while.body.i:
-; CHECK-NEXT:    [[TMP2:%.*]] = load ptr, ptr [[SA_ADDR_I]], align 8
-; CHECK-NEXT:    store ptr [[TMP2]], ptr [[SA_ADDR_I_I]], align 8
-; CHECK-NEXT:    [[TMP3:%.*]] = load i16, ptr [[TMP2]], align 2
-; CHECK-NEXT:    [[TOBOOL_I_I:%.*]] = icmp ne i16 [[TMP3]], 0
+; CHECK-NEXT:    store ptr [[NEIGH_SOCK_4]], ptr [[SA_ADDR_I_I]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, ptr [[NEIGH_SOCK_4]], align 2
+; CHECK-NEXT:    [[TOBOOL_I_I:%.*]] = icmp ne i16 [[TMP2]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_I_I]], label [[IF_THEN_I_I:%.*]], label [[IF_END_I_I:%.*]]
 ; CHECK:       if.then.i.i:
-; CHECK-NEXT:    [[TMP4:%.*]] = load ptr, ptr [[SA_ADDR_I_I]], align 8
-; CHECK-NEXT:    [[TMP5:%.*]] = load i32, ptr [[TMP4]], align 4
-; CHECK-NEXT:    [[CONV_I_I:%.*]] = sext i32 [[TMP5]] to i64
-; CHECK-NEXT:    [[CALL_I_I:%.*]] = call i32 @_Z6memcmpPvS_m(ptr noundef [[TMP4]], ptr noundef @compare_netdev_and_ip_sb_0, i64 noundef [[CONV_I_I]])
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[NEIGH_SOCK_4]], align 4
+; CHECK-NEXT:    [[CONV_I_I:%.*]] = sext i32 [[TMP3]] to i64
+; CHECK-NEXT:    [[CALL_I_I:%.*]] = call i32 @_Z6memcmpPvS_m(ptr noundef [[NEIGH_SOCK_4]], ptr noundef @compare_netdev_and_ip_sb_0, i64 noundef [[CONV_I_I]])
 ; CHECK-NEXT:    store i32 [[CALL_I_I]], ptr [[RETVAL_I_I]], align 4
 ; CHECK-NEXT:    br label [[COMPARE_NETDEV_AND_IP_EXIT_I:%.*]]
 ; CHECK:       if.end.i.i:
-; CHECK-NEXT:    [[TMP6:%.*]] = load ptr, ptr @ipv6_addr_cmp_a1, align 8
-; CHECK-NEXT:    [[CALL2_I_I:%.*]] = call i32 @_Z6memcmpPvS_m(ptr noundef [[TMP6]], ptr noundef @ipv6_addr_cmp_a2, i64 noundef 4)
+; CHECK-NEXT:    [[TMP4:%.*]] = load ptr, ptr @ipv6_addr_cmp_a1, align 8
+; CHECK-NEXT:    [[CALL2_I_I:%.*]] = call i32 @_Z6memcmpPvS_m(ptr noundef [[TMP4]], ptr noundef @ipv6_addr_cmp_a2, i64 noundef 4)
 ; CHECK-NEXT:    store i32 [[CALL2_I_I]], ptr @compare_netdev_and_ip___trans_tmp_1, align 4
 ; CHECK-NEXT:    store i32 [[CALL2_I_I]], ptr [[RETVAL_I_I]], align 4
 ; CHECK-NEXT:    br label [[COMPARE_NETDEV_AND_IP_EXIT_I]]
 ; CHECK:       compare_netdev_and_ip.exit.i:
-; CHECK-NEXT:    [[TMP7:%.*]] = load i32, ptr [[RETVAL_I_I]], align 4
-; CHECK-NEXT:    store i32 [[TMP7]], ptr @node_from_ndev_ip_data, align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i32 [ [[CALL2_I_I]], [[IF_END_I_I]] ], [ [[CALL_I_I]], [[IF_THEN_I_I]] ]
+; CHECK-NEXT:    store i32 [[TMP5]], ptr @node_from_ndev_ip_data, align 4
 ; CHECK-NEXT:    br label [[WHILE_COND_I]]
 ; CHECK:       node_from_ndev_ip.exit:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %retval.i.i = alloca i32, align 4