[clang] Add builtin_nondeterministic_value

[ManuelJBrito]

Summary

This patch adds a builtin that returns a non deterministic value of the same type as the argument.

Example:
int x = __builtin_nondeterministic_value(x);

Which is then lowered to freeze(poison).

This is a continuation of the work done in https://reviews.llvm.org/D136737, following the provided feedback.

[erichkeane]

clang/include/clang/Basic/Builtins.def

658

Not a fan of the name in general, it doesn't really explain what is happening. Perhaps __builtin_nondeterministic_value or something?

I also wonder if others might have a better name :)

clang/lib/CodeGen/CGBuiltin.cpp

3064

Is this troublesome with some of the types that have a ConvertTypeForMem? That is, bool and bool vector types might need a different type/representation? https://clang.llvm.org/doxygen/CodeGenTypes_8cpp_source.html#l00091

clang/test/CodeGen/builtins-nondet.c

3

Add some examples for 'bool' and vector-bool as well to make sure this is doing what you want.

[shafik]

clang/include/clang/Basic/Builtins.def

658

__builtin_indeterminate_value wdyt?

clang/test/CodeGen/builtins-nondet.c

3

Does this also work for structs?

[aaron.ballman]

Be sure to add documentation for this to the language extensions page and mention the new builtin in the release notes.

clang/include/clang/Basic/Builtins.def

658

I think __builtin_unspecified_value() makes sense, as that's what you're getting back (there is a valid value, but you may get a different value on every call). I don't think indeterminate makes sense because that implies it may return trap values, and I'm guessing that's not behavior we want here (or am I wrong about that)?

Also, should this be usable within a constant expression? I would assume not; we should have a test case showing you can't use it in such a context.

658

Why does this require custom typechecking?

[erichkeane]

clang/include/clang/Basic/Builtins.def

658

Our issue last time with "unspecified" value was that this has a distinct meaning in C/C++, so we don't want to use that word.

[ManuelJBrito]

clang/include/clang/Basic/Builtins.def

658

I don't think indeterminate makes sense because that implies it may return trap values, and I'm guessing that's not behavior we want here (or am I wrong about that)?

The idea is for it to return some correct value of the same type as the argument, so no trap values.

Can we settle on __builtin_nondeterministic_value?

658

Why does this require custom typechecking?

I wasn't sure how to have the builtin take one argument of any type.

658

Also, should this be usable within a constant expression? I would assume not; we should have a test case showing you can't use it in such a context.

Can you shed a light on the implications of this? Or point me to some reference?

clang/lib/CodeGen/CGBuiltin.cpp

3064

The lowering seems to be as intended. I will add the tests.

clang/test/CodeGen/builtins-nondet.c

3

Does this also work for structs?

No, i don't think so. What would be expected IR?

[erichkeane]

clang/test/CodeGen/builtins-nondet.c

3

can freeze/posion not be of struct types? If they don't work, it should be an error to try.

[ManuelJBrito]

Add tests with bool and bool-vector

[ManuelJBrito]

Oops wrong diff, i'll update it.

[ManuelJBrito]

fixed diff

[aaron.ballman]

clang/include/clang/Basic/Builtins.def

658

Can we settle on __builtin_nondeterministic_value?

I can live with it.

Our issue last time with "unspecified" value was that this has a distinct meaning in C/C++, so we don't want to use that word.

I guess I don't see the issue; the behavior of the builtin as I understand it matches that distinct meaning in C/C++ (and English prose).

Also, should this be usable within a constant expression? I would assume not; we should have a test case showing you can't use it in such a context.

Can you shed a light on the implications of this? Or point me to some reference?

It boils down to whether you think this should be valid:

constexpr bool hoo_boy() {
  return __builtin_nondeterministic_value() == 42;
}
constexpr bool val = hoo_boy();

(among other uses of constant expressions). My intuition is that there's nothing useful you could do with this builtin in a constant expression (my example is generally always going to be false except for the times when it's true, lol), but if all we're doing is giving you *a* value, nothing says we can't generate that value at compile time so it seems possible to support.

Why does this require custom typechecking?

I wasn't sure how to have the builtin take one argument of any type.

I was thinking it can use . to specify that the function is varargs, and then SemaChecking.cpp can validate that only one argument is passed to the call, but now that I think about that.... maybe we don't want that behavior because that would induce default argument promotions which would change the type (for example, from float to double). So on reflection, I think this is fine as-is.

[ManuelJBrito]

• Change name to __builtin_nondeterministic_value
• Add struct support

[erichkeane]

clang/lib/CodeGen/CGBuiltin.cpp

3070

This gets REALLY complicated, you can't just create a store, this might end up hitting conversion operators/etc, and is subject to triviality/etc, and also probably needs to go through a constructor. I suspect you're going to prefer to just decide this isn't a valid builtin for structs instead of getting bogged down in that mess.

clang/lib/Sema/SemaChecking.cpp

17814

So I think choosing the sub-set of types here is a much better idea, allowing any of the user-defined types is going to make your codegen for this builtin a mess. IMO, just isBuiltinType + isVectorType is probably an acceptable list for now.

clang/test/CodeGen/builtins-nondeterministic-value.c

6 ↗

(On Diff #493904)

If you're going to allow this, we need tests for unions, constructors, non-trivial types, copy assignment/etc.

[ManuelJBrito]

clang/lib/CodeGen/CGBuiltin.cpp

3070

The motivation for this builtin was to match intel's definition of undefined in the lowering of intrinsics such as https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm256_castsi128_si256&expand=628&ig_expand=755, so struct support isn't critical.
So if everyone else agrees i'll drop struct support, do as you suggest and if there are use cases for nondeterministic values of other types add support for them later?

[erichkeane]

clang/lib/CodeGen/CGBuiltin.cpp

3070

I suspect I speak for all with my suggestion. I don't think Aaron/Shafik are concerned with struct support here.

[aaron.ballman]

clang/lib/CodeGen/CGBuiltin.cpp

3070

If we reject the code, we can relax that restriction in the future without breaking code, so I think it's fine to not support structures. We can add support for them later if we have a need to do so.

[xbolva00]

Please add a release note.

Thanks for this new builtin, as I was working on something very very similar - the implementation looks fine to me.

[ManuelJBrito]

• Restrict builtin to base types and vectors

[ManuelJBrito]

Can the release note and documentation update be part of this patch or should i create a new one ?

[erichkeane]

In D142388#4097136, @ManuelJBrito wrote:

Can the release note and documentation update be part of this patch or should i create a new one ?

They should be a part of this patch.

[erichkeane]

clang/lib/Sema/SemaChecking.cpp

17810

This should set the expression as invalid, shouldn't it? That way we don't end up depending on it too much.

[ManuelJBrito]

• set Invalid in type checking
• add builtin documentation
• add release note

[erichkeane]

Last set of comments, docs and release notes look fine to me. feel free to fix the last comments while committing.

clang/lib/Sema/SemaChecking.cpp

17810

17812

Diag always returns true for exactly this situation, omit the {} and return true;, and just return Diag.

[ManuelJBrito]

Thank you all for the reviews and helping me see this patch through.

[ManuelJBrito]

So this is getting some build failures:

• https://lab.llvm.org/buildbot#builders/38/builds/9446
• https://lab.llvm.org/buildbot#builders/245/builds/4189
• https://lab.llvm.org/buildbot#builders/65/builds/7949
• https://lab.llvm.org/buildbot#builders/188/builds/25538

I suspect it's because of the way different ABIs handle the vectors. I was thinking that if we have the variable be a local variable and also not returning the value can fix the tests.

Does this make sense?

[thakis]

Looks like the test fails on win: http://45.33.8.238/win/74290/step_7.txt

And Mac: http://45.33.8.238/macm1/54080/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[thakis]

Reverted in adf7ffd51ee34c3a72d3168f5aed8b946ba3d2cc for now.

[erichkeane]

In D142388#4099374, @ManuelJBrito wrote:

So this is getting some build failures:

• https://lab.llvm.org/buildbot#builders/38/builds/9446
• https://lab.llvm.org/buildbot#builders/245/builds/4189
• https://lab.llvm.org/buildbot#builders/65/builds/7949
• https://lab.llvm.org/buildbot#builders/188/builds/25538

I suspect it's because of the way different ABIs handle the vectors. I was thinking that if we have the variable be a local variable and also not returning the value can fix the tests.

Does this make sense?

Yep, thats what it looks like, ABI differences. Feel free to update this review with the new test now that you've been reverted, and I'll look to see if it seems sufficient.

[ManuelJBrito]

Fix vector tests

[erichkeane]

Other than the newline, the test change is acceptable to me. Commit when ready :)

clang/test/CodeGen/builtins-nondeterministic-value.c

61 ↗

(On Diff #494338)

We do need a newline here.

[zixuan-wu]

clang/test/CodeGen/builtins-nondeterministic-value.c

26 ↗

(On Diff #494552)

hi, @ManuelJBrito , because double is 4 alignment in CSKY target, could you please update this with capture match pattern which makes it more adaptable?

[ManuelJBrito]

clang/test/CodeGen/builtins-nondeterministic-value.c

26 ↗

(On Diff #494552)

Hi, I'll make a patch dropping the alignment since it's not relevant for what we are testing here.

[zixuan-wu]

clang/test/CodeGen/builtins-nondeterministic-value.c

26 ↗

(On Diff #494552)

Thank you!

[rsmith]

I have a concern with the name of this builtin. People are going to assume it produces a nondeterministic value, and use it for seeding random number generators and similar, and will be surprised when the value produced is actually deterministic, and, worse, might leak information on the stack that was left behind by some previous function call. Can we give this a name that doesn't suggest that it produces its value nondeterministically?

[aaron.ballman]

In D142388#4412521, @rsmith wrote:

I have a concern with the name of this builtin. People are going to assume it produces a nondeterministic value, and use it for seeding random number generators and similar, and will be surprised when the value produced is actually deterministic, and, worse, might leak information on the stack that was left behind by some previous function call. Can we give this a name that doesn't suggest that it produces its value nondeterministically?

That's a fair point; do you have a suggestion for a name? (I had suggested __builtin_unspecified_value() but perhaps that is too focused on the term of art.)

[xbolva00]

https://reviews.llvm.org/D136737 used 'builtin_unspecified_value' which could be okay. .. or builtin_undefined_value maybe?

Are we sure we want to expose this intrinsic as it can be easily misused (as mentioned, as random generator) and/or cause security issues? Maybe only allow it in system headers (original motivation in https://reviews.llvm.org/D136737)

[xbolva00]

clang/docs/LanguageExtensions.rst

3087 ↗

(On Diff #494552)

This text really sells this new builtin as a random value generator..

[rsmith]

In D142388#4414375, @aaron.ballman wrote:

In D142388#4412521, @rsmith wrote:

I have a concern with the name of this builtin. People are going to assume it produces a nondeterministic value, and use it for seeding random number generators and similar, and will be surprised when the value produced is actually deterministic, and, worse, might leak information on the stack that was left behind by some previous function call. Can we give this a name that doesn't suggest that it produces its value nondeterministically?

That's a fair point; do you have a suggestion for a name? (I had suggested __builtin_unspecified_value() but perhaps that is too focused on the term of art.)

If this means exactly what C++ means by "unspecified value" I'm OK with that, but I don't think it does with the current design; __builtin_???(bool) can seemingly return std::bit_cast<bool>('x'), which is not an unspecified value of type bool in C++-land (because it's not a value of type bool at all). On that subject: can we restrict this to types where every object representation is valid, and rule out bool and (at least some) enumerations, as well as any _BitInt(N)s with no unused bits? Either that, or mask off the "bad" bits so that it actually produces valid values? Allowing type arguments for which any use of the builtin is just immediately UB doesn't seem like a good idea.

I don't like __builtin_undefined_value because very commonly "undefined" is used to mean something else, in ways that show up in close proximity to this builtin.

__builtin_arbitrary_value works a bit better for me, but is still quite wrong / misleading, because the value is *not* arbitrary. With either that or __builtin_nondeterminstic_value, I worry that an old and famous crypto bug will be reintroduced:

int my_random_number = __builtin_nondeterministic_value();
my_random_number ^= rand();
my_random_number ^= other_junk;

... where I would expect and hope that LLVM will optimize the resulting value of my_random_number to 0 by picking the exact right "nondeterminstic" value every time :)

I think __builtin_any_value works pretty well, and emphasizes that this can really return any value. I'd also be OK with __builtin_convenient_value, to emphasize that the compiler will pick something that's convenient for it, but I prefer __builtin_any_value.

clang/docs/LanguageExtensions.rst

3087 ↗

(On Diff #494552)

How about something more like this:

`__builtin_any_value` returns an arbitrary value of the same type as the provided argument.

[...]

Description:

Each call to `__builtin_any_value` returns an arbitrary value of the type given by the argument. The returned value will be chosen in a way that is convenient for the compiler, and may for example be a value left behind in a register or on the stack from a previous operation, or a value that causes a later calculation to always produce the same result. This function will not necessarily return a meaningful value if there are bit-patterns for the given type that do not correspond to meaningful values.

(I really want this to also not say it will produce a "valid value", because the valid values for a type are not in general known to the frontend. For a pointer, for example, this can return literally any bit pattern, and most of those will not be valid in any meaningful sense.)

[aaron.ballman]

In D142388#4415349, @rsmith wrote:

I think __builtin_any_value works pretty well, and emphasizes that this can really return any value. I'd also be OK with __builtin_convenient_value, to emphasize that the compiler will pick something that's convenient for it, but I prefer __builtin_any_value.

I can get behind __builtin_any_value as the name.

@ManuelJBrito: would you be willing to make these modifications?

clang/docs/LanguageExtensions.rst

3087 ↗

(On Diff #494552)

I like this new formulation -- it makes it more clear that you can get a trap representation for the value, for example.

[ManuelJBrito]

In D142388#4425246, @aaron.ballman wrote:

In D142388#4415349, @rsmith wrote:

I think __builtin_any_value works pretty well, and emphasizes that this can really return any value. I'd also be OK with __builtin_convenient_value, to emphasize that the compiler will pick something that's convenient for it, but I prefer __builtin_any_value.

I can get behind __builtin_any_value as the name.

@ManuelJBrito: would you be willing to make these modifications?

Yes, I can change the name to __builtin_any_value .
Where do we stand in terms of further restricting the types for which we can use this? I'm a bit out of my depth in regards to all the subtleties.

clang/include/clang/Basic/Builtins.def

 BUILTIN(__builtin_unreachable, "v", "nr")
 BUILTIN(__builtin_shufflevector, "v."   , "nct")
 BUILTIN(__builtin_convertvector, "v."   , "nct")
 BUILTIN(__builtin_alloca, "v*z"   , "Fn")
 BUILTIN(__builtin_alloca_uninitialized, "v*z", "Fn")
 BUILTIN(__builtin_alloca_with_align, "v*zIz", "Fn")
 BUILTIN(__builtin_alloca_with_align_uninitialized, "v*zIz", "Fn")
 BUILTIN(__builtin_call_with_static_chain, "v.", "nt")
+BUILTIN(__builtin_nondet, "v.", "nt")
 
 BUILTIN(__builtin_elementwise_abs, "v.", "nct")
 BUILTIN(__builtin_elementwise_max, "v.", "nct")
 BUILTIN(__builtin_elementwise_min, "v.", "nct")
 BUILTIN(__builtin_elementwise_ceil, "v.", "nct")
 BUILTIN(__builtin_elementwise_cos, "v.", "nct")
 BUILTIN(__builtin_elementwise_floor, "v.", "nct")
 BUILTIN(__builtin_elementwise_roundeven, "v.", "nct")

clang/include/clang/Sema/Sema.h

bool SemaBuiltinPPCMMACall(CallExpr *TheCall, unsigned BuiltinID,
                              const char *TypeDesc);
 
   bool CheckPPCMMAType(QualType Type, SourceLocation TypeLoc);
 
   bool SemaBuiltinElementwiseMath(CallExpr *TheCall);
   bool PrepareBuiltinElementwiseMathOneArgCall(CallExpr *TheCall);
   bool PrepareBuiltinReduceMathOneArgCall(CallExpr *TheCall);
 
+  bool SemaBuiltinNonDet(CallExpr *TheCall);
+
   // Matrix builtin handling.
   ExprResult SemaBuiltinMatrixTranspose(CallExpr *TheCall,
                                         ExprResult CallResult);
   ExprResult SemaBuiltinMatrixColumnMajorLoad(CallExpr *TheCall,
                                               ExprResult CallResult);
   ExprResult SemaBuiltinMatrixColumnMajorStore(CallExpr *TheCall,
                                                ExprResult CallResult);
 

clang/lib/CodeGen/CGBuiltin.cpp

Value *Sub =
         Builder.CreateSub(llvm::ConstantInt::get(IntTy, ExpMask), AbsV);
     // V = sign bit (Sub) <=> V = (Sub < 0)
     V = Builder.CreateLShr(Sub, llvm::ConstantInt::get(IntTy, bitsize - 1));
     if (bitsize > 32)
       V = Builder.CreateTrunc(V, ConvertType(E->getType()));
     return RValue::get(V);
   }
 
+  case Builtin::BI__builtin_nondet: {
+    Value *Result = PoisonValue::get(ConvertType(E->getArg(0)->getType()));
+    Result = Builder.CreateFreeze(Result);
+    return RValue::get(Result);
+  }
+
   case Builtin::BI__builtin_elementwise_abs: {
     Value *Result;
     QualType QT = E->getArg(0)->getType();
 
     if (auto *VecTy = QT->getAs<VectorType>())
       QT = VecTy->getElementType();
     if (QT->isIntegerType())
       Result = Builder.CreateBinaryIntrinsic(
           llvm::Intrinsic::abs, EmitScalarExpr(E->getArg(0)),
           Builder.getFalse(), nullptr, "elt.abs");

clang/lib/Sema/SemaChecking.cpp

if (!TheCall->getArg(0)->isValueDependent() &&
       Diag(TheCall->getBeginLoc(), diag::warn_frame_address)
           << ((BuiltinID == Builtin::BI__builtin_return_address)
                   ? "__builtin_return_address"
                   : "__builtin_frame_address")
           << TheCall->getSourceRange();
     break;
   }
 
+  case Builtin::BI__builtin_nondet: {
+    if (SemaBuiltinNonDet(TheCall))
+      return ExprError();
+    break;
+  }
+
   // __builtin_elementwise_abs restricts the element type to signed integers or
   // floating point types only.
   case Builtin::BI__builtin_elementwise_abs: {
     if (PrepareBuiltinElementwiseMathOneArgCall(TheCall))
       return ExprError();
 
     QualType ArgTy = TheCall->getArg(0)->getType();
     QualType EltTy = ArgTy;
bool Sema::PrepareBuiltinReduceMathOneArgCall(CallExpr *TheCall) {
   ExprResult A = UsualUnaryConversions(TheCall->getArg(0));
   if (A.isInvalid())
     return true;
 
   TheCall->setArg(0, A.get());
   return false;
 }
 
+bool Sema::SemaBuiltinNonDet(CallExpr *TheCall) {
+  if (checkArgCount(*this, TheCall, 1))
+    return true;
+
+  ExprResult Arg = TheCall->getArg(0);
+  QualType TyArg = Arg.get()->getType();
+  TheCall->setType(TyArg);
+  return false;
+}
+
 ExprResult Sema::SemaBuiltinMatrixTranspose(CallExpr *TheCall,
                                             ExprResult CallResult) {
   if (checkArgCount(*this, TheCall, 1))
     return ExprError();
 
   ExprResult MatrixArg = DefaultLvalueConversion(TheCall->getArg(0));
   if (MatrixArg.isInvalid())
     return MatrixArg;

clang/test/CodeGen/builtins-nondet.c

+// RUN: %clang_cc1 %s -emit-llvm -o - | FileCheck %s
+
+typedef float float4 __attribute__((ext_vector_type(4)));
+
+int clang_nondet_i( int x ) {
+// CHECK-LABEL: entry
+// CHECK: [[A:%.*]] = alloca i32, align 4
+// CHECK: store i32 [[X:%.*]], ptr [[A]], align 4
+// CHECK: [[R:%.*]] = freeze i32 poison
+// CHECK: ret i32 [[R]]
+  return __builtin_nondet(x);
+} 
+
+float clang_nondet_f( float x ) {
+// CHECK-LABEL: entry
+// CHECK: [[A:%.*]] = alloca float, align 4
+// CHECK: store float [[X:%.*]], ptr [[A]], align 4
+// CHECK: [[R:%.*]] = freeze float poison
+// CHECK: ret float [[R]]
+  return __builtin_nondet(x);
+}
+
+double clang_nondet_d( double x ) {
+// CHECK-LABEL: entry
+// CHECK: [[A:%.*]] = alloca double, align 8
+// CHECK: store double [[X:%.*]], ptr [[A]], align 8
+// CHECK: [[R:%.*]] = freeze double poison
+// CHECK: ret double [[R]]
+  return __builtin_nondet(x);
+} 
+
+float4 clang_nondet_v( float4 x ) {
+// CHECK-LABEL: entry
+// CHECK: [[A:%.*]] = alloca <4 x float>, align 16
+// CHECK: store <4 x float> [[X:%.*]], ptr [[A]], align 16
+// CHECK: [[R:%.*]] = freeze <4 x float> poison
+// CHECK: ret <4 x float> [[R]]
+  return __builtin_nondet(x);
+} 
+