[clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 5)

[jmciver]

Summary

This patch adds noundef metadata to scalar load instructions and is intended to gain implementation feedback before proceeding to adding noundef to other load types.

The intent is to apply noundef to scalar load instructions that are not of type:

• char (if the target system maps to unsigned char)
• unsigned char
• std::byte

These types are excluded because of their different indeterminate value semantics (I think this is correct, but need to ask someone).

Feedback is greatly appreciated.

[efriedma]

How much code does this break? How much does this help performance? (My instinct here is that the tradeoff is not worth it, but I'm willing to be convinced otherwise.)

[jmciver]

The regression and test-suite pass using a bootstrap build. I'll provide performance data tomorrow.

[jmciver]

The following are results from test-suite execution. LHS is a main build (17dde371e773) and the RHS is main with patch applied. The results-subset.txt is absent of unit, micro, and torture tests. Execution runtime is comprised from three runs of the main and patched version combined using the compare.py vs argument (compare the minimums of the two sets). Compilation times are acquired from a single invocation of each type of build. I will gather more compile time runs this weekend.

results-subset.txt72 KBDownload

results-full.txt666 KBDownload

[vitalybuka]

Are these patches uploaded with arc tool?

[vitalybuka]

I tried to hook this patch into MemorySanitizer and it reduces instrumented code by ~30% !

[xbolva00]

In D134410#3816918, @vitalybuka wrote:

I tried to hook this patch into MemorySanitizer and it reduces instrumented code by ~30% !

Wow, amazing results!

[vitalybuka]

In D134410#3817070, @xbolva00 wrote:

In D134410#3816918, @vitalybuka wrote:

I tried to hook this patch into MemorySanitizer and it reduces instrumented code by ~30% !

Wow, amazing results!

Also I applied this patch with D134698 and used on our large test set, expecting significant number of pre-existing reports. To my surprise I see not many of them.

[vitalybuka]

Also I applied this patch with D134698 and used on our large test set, expecting significant number of pre-existing reports. To my surprise I see not many of them.

Something wrong with my msan experiment, I'll re-evaluate size and reports tomorrow.

[jmciver]

In D134410#3816881, @vitalybuka wrote:

Are these patches uploaded with arc tool?

Yes, the patches were uploaded with arc. The size of the patch was too large to use the web interface.

[jmciver]

Decreased CPU loading during test-suite build did lower times in some instances, but not a lot.

results-subset.txt72 KBDownload

results-full.txt666 KBDownload

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary)

Resolve merge conflicts due to the adoption of the ptr type in openmp tests.

[vitalybuka]

In D134410#3817190, @vitalybuka wrote:

Also I applied this patch with D134698 and used on our large test set, expecting significant number of pre-existing reports. To my surprise I see not many of them.

Something wrong with my msan experiment, I'll re-evaluate size and reports tomorrow.

Finally I had a time to fix my msan experiment D134698
It's about 5.5% .text savings for Msan, and 10% for msan with "track origins", which is still pretty good.
For context, for msan it's usually cheaper to report uninitialized ASAP, than propagating and reporting it later. With this metadata it will happen immediately after load.

However cleanup looks scary. Msan reports maybe 20% of unique tests on our code base. Many a of them share root cause, but still many unique root causes.
On quick looks I see no false report. A lot of stuff like this https://stackoverflow.com/questions/60112841/copying-structs-with-uninitialized-members which is technically is UB.
I assume with this patch landed, many such cases may change code behavior. So we will need to update msan to have a tool to detect cases like this anyway.

[xbolva00]

I assume with this patch landed, many such cases may change code behavior. So we will need to update msan to have a tool to detect cases like this anyway.

I believe that updated msan should come first.

[vitalybuka]

In D134410#3860646, @xbolva00 wrote:

I assume with this patch landed, many such cases may change code behavior. So we will need to update msan to have a tool to detect cases like this anyway.

I believe that updated msan should come first.

Yes, we can do that.

[vitalybuka]

clang/lib/CodeGen/CGExpr.cpp

1759

Taking into account potantial risks from pre-existing UB, I believe we need clang switch to be able to shutdown this branch, similar to enable_noundef_analysis.
User with large code bases maybe need some time for transition.

I have no opinion if this should be ON or OFF by default

[jmciver]

clang/lib/CodeGen/CGExpr.cpp

1759

A flag is a good idea; I'll go ahead and add that. We can determine the default later, for now I would like to default to on to see/show the effects. Anyone feel free to let me know if you have reasoning otherwise.

For the flag name: enable_noundef_loads?

[jdoerfert]

However cleanup looks scary. Msan reports maybe 20% of unique tests on our code base. Many a of them share root cause, but still many unique root causes.
On quick looks I see no false report

While scary, this also is extremely encouraging to move forward with this.

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary)

Add flag -enable-noundef-load-analysis and rebase with main. Refactored noundef
metadata functionality into anonymous function to be used by additional patches.

[jmciver]

I'll start fixing reported test failures tomorrow.

[nikic]

I think adding this under a default-disabled flag is fine for evaluation purposes, but I have doubts that we will ever be able to enable this by default. There is a lot of code out there assuming that copying uninitialized data around is fine.

[nlopes]

In D134410#3893918, @nikic wrote:

I think adding this under a default-disabled flag is fine for evaluation purposes, but I have doubts that we will ever be able to enable this by default. There is a lot of code out there assuming that copying uninitialized data around is fine.

Well, I think that flags that are disabled by default don't exist and they are not useful.
We wanted this patch to make us switch uninitialized loads to poison at will, since they become UB. In practice, this helps us fixing bugs in SROA and etc without perf degradation.
As long as ubsan/valgrind can detect these uninitialized loads, I think we should be ok to deploy this change. We are touching memcpys yet, at least, as those may be susceptible to handling uninit memory.

[nikic]

In D134410#3894995, @nlopes wrote:

We wanted this patch to make us switch uninitialized loads to poison at will, since they become UB. In practice, this helps us fixing bugs in SROA and etc without perf degradation.

Can you elaborate on this? I don't see how this is necessary for switching uninitialized loads to poison.

As long as ubsan/valgrind can detect these uninitialized loads, I think we should be ok to deploy this change.

Valgrind cannot detect uninitialized loads, it only detects branching on uninitialized data. Valgrind works on the assembly level, and as such does not have the necessary information to tell whether a mov of uninitialized data is problematic or not.

The only sanitizer that can detect this is msan (with the patch referenced above), which is incidentally also the sanitizer that sees the least use in practice, because it is much harder to deploy than ubsan and asan.

[tschuett]

clang/lib/CodeGen/CGExpr.cpp

676

Nit: You meant static.

[tschuett]

Almost all flags are off by default. That's why they are called flags, i.e., -Weverything.

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 2)

Fix AMD-GPU, ARM, PowerPC, and new OpenMP tests.

[nlopes]

In D134410#3895077, @nikic wrote:

In D134410#3894995, @nlopes wrote:

We wanted this patch to make us switch uninitialized loads to poison at will, since they become UB. In practice, this helps us fixing bugs in SROA and etc without perf degradation.

Can you elaborate on this? I don't see how this is necessary for switching uninitialized loads to poison.

It's not mandatory, it's a simple way of achieving it as !noundef already exists.

We cannot change the default behavior of load as it would break BC. An alternative is to introduce a new !poison_on_unint for loads. Clang could use that on all loads except those for bit-fields.
Our suggestion is to jump straight to !noundef.
To fully remove undef, then we need to swtich loads to return freeze poison rather than undef on uninitialized access, but only after we are able to yield poison in the common case.

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 2)

Refactor local linkage function, applyNoundefToLoadInst, to use static rather
than an anonymous namespace as per LLVM coding standards.

[jmciver]

clang/lib/CodeGen/CGExpr.cpp

676

Thank you for bringing that to my attention. I reviewed the LLVM Coding Standards guidance on the topic.

[nikic]

In D134410#3895253, @nlopes wrote:

In D134410#3895077, @nikic wrote:

In D134410#3894995, @nlopes wrote:

We wanted this patch to make us switch uninitialized loads to poison at will, since they become UB. In practice, this helps us fixing bugs in SROA and etc without perf degradation.

Can you elaborate on this? I don't see how this is necessary for switching uninitialized loads to poison.

It's not mandatory, it's a simple way of achieving it as !noundef already exists.

We cannot change the default behavior of load as it would break BC.

FWIW, I don't agree with this. It's fine to change load semantics, as long as bitcode autoupgrade is handled correctly. I'd go even further and say that at least long term, any solution that does not have a plain load instruction return poison for uninitialized memory will be a maintenance mess.

I think the core problem that prevents us from moving in this direction is that we have no way to represent a frozen load at all (as freeze(load) will propagate poison before freezing). If I understand correctly, you're trying to solve this by making *all* loads frozen loads, and use load !noundef to allow dropping the freeze. I think this would be a very bad outcome, especially as we're going to lose that !noundef on most load speculations, and I don't think we want to be introducing freezes when speculating loads (e.g. during LICM).

I expect that the path of least resistance is going to be to support bitwise poison for load/store/phi/select and promote it to full-value poison on any other operation, allowing a freezing load to be expressed as freeze(load).

Please let me know if I completely misunderstood the scheme you have in mind...

[nlopes]

In D134410#3898563, @nikic wrote:

In D134410#3895253, @nlopes wrote:

In D134410#3895077, @nikic wrote:

In D134410#3894995, @nlopes wrote:

We wanted this patch to make us switch uninitialized loads to poison at will, since they become UB. In practice, this helps us fixing bugs in SROA and etc without perf degradation.

Can you elaborate on this? I don't see how this is necessary for switching uninitialized loads to poison.

It's not mandatory, it's a simple way of achieving it as !noundef already exists.

We cannot change the default behavior of load as it would break BC.

FWIW, I don't agree with this. It's fine to change load semantics, as long as bitcode autoupgrade is handled correctly. I'd go even further and say that at least long term, any solution that does not have a plain load instruction return poison for uninitialized memory will be a maintenance mess.

I think the core problem that prevents us from moving in this direction is that we have no way to represent a frozen load at all (as freeze(load) will propagate poison before freezing). If I understand correctly, you're trying to solve this by making *all* loads frozen loads, and use load !noundef to allow dropping the freeze. I think this would be a very bad outcome, especially as we're going to lose that !noundef on most load speculations, and I don't think we want to be introducing freezes when speculating loads (e.g. during LICM).

I expect that the path of least resistance is going to be to support bitwise poison for load/store/phi/select and promote it to full-value poison on any other operation, allowing a freezing load to be expressed as freeze(load).

Please let me know if I completely misunderstood the scheme you have in mind...

You got it right. But the load we propose is not exactly a freezing load. It only returns freeze poison for uninit memory. It doesn't freeze stored values.
If we introduce a !uninit_is_poison flag, we can drop !noundef when hoisting and add !uninit_is_poison instead (it's implied by !noundef).

The question is what's the default for uninit memory: freeze poison or poison? But I think we need both. And since we need both (unless we add a freezing load or bitwise poison), why not keep a behavior closer to the current?
A freezing load is worse as a store+load needs to be forwarded though a freeze, as the load is not a NOP anymore.

Bitwise poison would be nice, but I don't know how to make it work. To make it work with bit-fields, we would need and/or to propagate poison bit-wise as well. But then we will break optimizations that transform between those and arithmetic. Then you start wanting that add/mul/etc also propagate poison bit-wise and then I don't know how to specify that semantics. (if you want, I can forward you a proposal we wrote a few years ago, but we never managed to make sound, so it was never presented in public)

I agree that bit-wise poison for loads sounds appealing (for bit fields, load widening, etc), but without support in the rest of the IR, it's not worth much. If it becomes value-wise in the 1st operation, then I don't think we gain any expressivity.

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 2)

Refactor test matrix-type-operators.c to contain the noundef attribute. This
test will be further modified in future patches.

[jmciver]

Updating D134410: [clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 3)

The following tests have been updated:

• avx512f-builtins.c
• avx512fp16-builtins.c
• matrix-type-operators.c
• matrix-type-operators.cpp

[nikic]

In D134410#3898615, @nlopes wrote:

In D134410#3898563, @nikic wrote:

FWIW, I don't agree with this. It's fine to change load semantics, as long as bitcode autoupgrade is handled correctly. I'd go even further and say that at least long term, any solution that does not have a plain load instruction return poison for uninitialized memory will be a maintenance mess.

I think the core problem that prevents us from moving in this direction is that we have no way to represent a frozen load at all (as freeze(load) will propagate poison before freezing). If I understand correctly, you're trying to solve this by making *all* loads frozen loads, and use load !noundef to allow dropping the freeze. I think this would be a very bad outcome, especially as we're going to lose that !noundef on most load speculations, and I don't think we want to be introducing freezes when speculating loads (e.g. during LICM).

I expect that the path of least resistance is going to be to support bitwise poison for load/store/phi/select and promote it to full-value poison on any other operation, allowing a freezing load to be expressed as freeze(load).

Please let me know if I completely misunderstood the scheme you have in mind...

You got it right. But the load we propose is not exactly a freezing load. It only returns freeze poison for uninit memory. It doesn't freeze stored values.
If we introduce a !uninit_is_poison flag, we can drop !noundef when hoisting and add !uninit_is_poison instead (it's implied by !noundef).

The question is what's the default for uninit memory: freeze poison or poison? But I think we need both. And since we need both (unless we add a freezing load or bitwise poison), why not keep a behavior closer to the current?
A freezing load is worse as a store+load needs to be forwarded though a freeze, as the load is not a NOP anymore.

Bitwise poison would be nice, but I don't know how to make it work. To make it work with bit-fields, we would need and/or to propagate poison bit-wise as well. But then we will break optimizations that transform between those and arithmetic. Then you start wanting that add/mul/etc also propagate poison bit-wise and then I don't know how to specify that semantics. (if you want, I can forward you a proposal we wrote a few years ago, but we never managed to make sound, so it was never presented in public)

I agree that bit-wise poison for loads sounds appealing (for bit fields, load widening, etc), but without support in the rest of the IR, it's not worth much. If it becomes value-wise in the 1st operation, then I don't think we gain any expressivity.

I think the gain in expressiveness is that we can write something like freeze(load). For example, D138766 currently proposes to use a silly pattern like bitcast(freeze(load(<4 x i8>)) to i32) to achieve a "frozen load", because there is no other way to express it right now.

The other problem I see here is that we still need to do something about the memcpy -> load/store fold. As soon as we have poison from uninit values (either directly or via !uninit_is_poison) this will start causing miscompiles very quickly. The only way to do this right now is again with an <N x i8> vector load/store, which still optimizes terribly. This needs either load+store of integer to preserve poison, or again some form of byte type.

Something I've only recently realized is that we also run into this problem when inserting spurious load/store pairs, e.g. as done by LICM scalar promotion. If we're promoting say an i32 value to scalar that previously used a conditional store, then promotion will now introduce an unconditional load and store, which will spread poison from individual bytes. So that means that technically scalar promotion (and SimplifyCFG store speculation) also need to do some special dance to preserve poison. And without preservation of poison across load/store/phi in plain ints, this is going to be a bad optimization outcome either way: We'd have to use either a vector of i8 or a byte type for the inserted phi nodes and only cast to integer and back when manipulating the value, which would probably defeat the optimization. At that point probably best to freeze the first load (which again needs a freezing load).

(We should probably move the discussion around this patch series to discourse.)

[nlopes]

In D134410#3983684, @nikic wrote:

The other problem I see here is that we still need to do something about the memcpy -> load/store fold. As soon as we have poison from uninit values (either directly or via !uninit_is_poison) this will start causing miscompiles very quickly. The only way to do this right now is again with an <N x i8> vector load/store, which still optimizes terribly. This needs either load+store of integer to preserve poison, or again some form of byte type.

Something I've only recently realized is that we also run into this problem when inserting spurious load/store pairs, e.g. as done by LICM scalar promotion. If we're promoting say an i32 value to scalar that previously used a conditional store, then promotion will now introduce an unconditional load and store, which will spread poison from individual bytes. So that means that technically scalar promotion (and SimplifyCFG store speculation) also need to do some special dance to preserve poison. And without preservation of poison across load/store/phi in plain ints, this is going to be a bad optimization outcome either way: We'd have to use either a vector of i8 or a byte type for the inserted phi nodes and only cast to integer and back when manipulating the value, which would probably defeat the optimization. At that point probably best to freeze the first load (which again needs a freezing load).

For this stuff, I think the ideal solution is the byte type. That's the only way to do this kind of raw byte copies. Doesn't spread poison between bits nor do you need to know if you are reading a pointer or something else. Nor does it require a freeze, which is annoying.

John will submit a proposal (next week?) using poison for uninit loads. I think we have converged on something cool. Thanks for insisting on that one!

[jmciver]

As Nuno mentioned we are targeting the proposal for next week. I will update the ticket with the Discourse link once it becomes available.

[jmciver]

The Discourse proposal is available: RFC Load Instruction: Uninitialized Memory Semantics

clang/lib/CodeGen/CGExpr.cpp

 
 bool CodeGenFunction::sanitizePerformTypeCheck() const {
   return SanOpts.has(SanitizerKind::Null) ||
          SanOpts.has(SanitizerKind::Alignment) ||
          SanOpts.has(SanitizerKind::ObjectSize) ||
          SanOpts.has(SanitizerKind::Vptr);
 }
 
+static void applyNoundefToLoadInst(bool enable, const clang::QualType &Ty,
+                                   llvm::LoadInst *Load) {
+  if (enable) {
+    if (auto TyPtr = Ty.getTypePtrOrNull()) {
+      if (!(TyPtr->isSpecificBuiltinType(BuiltinType::UChar) ||
+            TyPtr->isSpecificBuiltinType(BuiltinType::Char_U) ||
+            TyPtr->isStdByteType())) {
+        Load->setMetadata(llvm::LLVMContext::MD_noundef,
+                          llvm::MDNode::get(Load->getContext(), None));
+      }
+    }
+  }
+}
+
 void CodeGenFunction::EmitTypeCheck(TypeCheckKind TCK, SourceLocation Loc,
                                     llvm::Value *Ptr, QualType Ty,
                                     CharUnits Alignment,
                                     SanitizerSet SkippedChecks,
                                     llvm::Value *ArraySize) {
   if (!sanitizePerformTypeCheck())
     return;
 
if (const auto *ClangVecTy = Ty->getAs<VectorType>()) {
     if (!CGM.getCodeGenOpts().PreserveVec3Type && VTy->getNumElements() == 3) {
 
       // Bitcast to vec4 type.
       llvm::VectorType *vec4Ty =
           llvm::FixedVectorType::get(VTy->getElementType(), 4);
       Address Cast = Builder.CreateElementBitCast(Addr, vec4Ty, "castToVec4");
       // Now load value.
       llvm::Value *V = Builder.CreateLoad(Cast, Volatile, "loadVec4");
-
       // Shuffle vector to get vec3.
       V = Builder.CreateShuffleVector(V, ArrayRef<int>{0, 1, 2}, "extractVec");
       return EmitFromMemory(V, Ty);
     }
   }
 
   // Atomic operations have to be done on integral types.
   LValue AtomicLValue =
       LValue::MakeAddr(Addr, Ty, getContext(), BaseInfo, TBAAInfo);
   if (Ty->isAtomicType() || LValueIsSuitableForInlineAtomic(AtomicLValue)) {
     return EmitAtomicLoad(AtomicLValue, Loc).getScalarVal();
   }
 
   llvm::LoadInst *Load = Builder.CreateLoad(Addr, Volatile);
   if (isNontemporal) {
     llvm::MDNode *Node = llvm::MDNode::get(
         Load->getContext(), llvm::ConstantAsMetadata::get(Builder.getInt32(1)));
     Load->setMetadata(CGM.getModule().getMDKindID("nontemporal"), Node);
   }
 
+  applyNoundefToLoadInst(CGM.getCodeGenOpts().EnableNoundefLoadAttr, Ty, Load);
+
   CGM.DecorateInstructionWithTBAA(Load, TBAAInfo);
 
   if (EmitScalarRangeCheck(Load, Ty, Loc)) {
     // In order to prevent the optimizer from throwing away the check, don't
     // attach range metadata to the load.
     // TODO: Enable range metadata for AMDGCN after issue
     // https://github.com/llvm/llvm-project/issues/58176 is fixed.
   } else if (CGM.getCodeGenOpts().OptimizationLevel > 0 &&