[UnknownProvenance] Add LLVM-IR support for unknown_provenance

[jeroen.dobbelaere]

Summary

This adds the unknown_provenance LLVM-IR keyword, corresponding to the UnknownProvenance constant.

[jeroen.dobbelaere]

Added missing LLLexer support.

[MatzeB]

Please document this in the LLVM language reference! I for one have trouble following the discussions (since I didn't have the time to read all the C/C++ reports yet)

[xbolva00]

Where is RFC or some high level document?

[jeroen.dobbelaere]

In D111160#3107636, @MatzeB wrote:

Please document this in the LLVM language reference! I for one have trouble following the discussions (since I didn't have the time to read all the C/C++ reports yet)

The langref update is in D104268

[jeroen.dobbelaere]

In D111160#3107697, @xbolva00 wrote:

Where is RFC or some high level document?

The general Full Restrict RFC is referenced to in D68484 (Pointed to by D104268, which introduces the ptr_provenance operand and provides the langref update).

The unknown_provenance (UnknownProvenance) constant is being introduced as a clean way to indicate that a ptr_provenance is unknown.
In the original full restrict proposal, this role was served by using undef (UndefValue) as ptr_provenance operand.
For full restrict that was ok, but when we want to use ptr_provenance in a broader context having a special value results in a cleaner implementation without ambiguity.
(Especially if, at a later time, we want to make use of ptr_provenance in BasicAliasAnalysis, not just ScopedNoAliasAA).

[jeroen.dobbelaere]

In D111160#3107697, @xbolva00 wrote:

Where is RFC or some high level document?

I sent out https://lists.llvm.org/pipermail/llvm-dev/2021-November/153772.html

[lebedev.ri]

Should there be a verifier change to ensure that it is *actually* only used in the provenance operand, and not as a pure pointer,
or can it be PHI'd/select'ed from multiple variants?

[jeroen.dobbelaere]

In D111160#3139503, @lebedev.ri wrote:

Should there be a verifier change to ensure that it is *actually* only used in the provenance operand, and not as a pure pointer,
or can it be PHI'd/select'ed from multiple variants?

Yes, that definitely makes sense.
It can be PHI'd, select'ed, cast'ed. But in the end, the usage must only show up in the provenance path of load,store,llvm.ptr.provenance.

I'll look into this in the coming days.

[jeroen.dobbelaere]

Rebase to 49cb4fef02e635bf304906232214166c7531d753

[jeroen.dobbelaere]

Rebased to ffe262a198a9f9030991df6d3ddd812e74fa3523

[jeroen.dobbelaere]

In D111160#3139503, @lebedev.ri wrote:

Should there be a verifier change to ensure that it is *actually* only used in the provenance operand, and not as a pure pointer,
or can it be PHI'd/select'ed from multiple variants?

I added the verifier in D128813

[jdoerfert]

Test for the lexer/parser are missing. Positive and negative.

[jeroen.dobbelaere]

In D111160#3772453, @jdoerfert wrote:

Test for the lexer/parser are missing. Positive and negative.

At this point I think it is hard to already introduce these tests: tests that trigger reading the unknown_provenance LLVM-IR constant are available in D104269 and D128813.
A test that triggers writing the LLVM-IR unknown_provenance constant is available in D104269 (and enabled in D104270)

[jdoerfert]

To go in with the others only.

[jeroen.dobbelaere]

Rebased to ef545ef62a833152d8975ff16333b57cc41befcc (Jan 9, 2023)

[jeroen.dobbelaere]

Rebased to: 8c7cfa357280dd93d33b10bbba0fe33797e27d63 (Feb 14, 2023)

llvm/include/llvm/AsmParser/LLParser.h

namespace llvm {
   /// type can depend on later context.  This may either be a numeric reference
   /// or a symbolic (%var) reference.  This is just a discriminated union.
   struct ValID {
     enum {
       t_LocalID, t_GlobalID,           // ID in UIntVal.
       t_LocalName, t_GlobalName,       // Name in StrVal.
       t_APSInt, t_APFloat,             // Value in APSIntVal/APFloatVal.
       t_Null, t_Undef, t_Zero, t_None, t_Poison, // No value.
+      t_UnknownProvenance,             // No value.
       t_EmptyArray,                    // No value:  []
       t_Constant,                      // Value in ConstantVal.
       t_InlineAsm,                     // Value in FTy/StrVal/StrVal2/UIntVal.
       t_ConstantStruct,                // Value in ConstantStructElts.
       t_PackedConstantStruct           // Value in ConstantStructElts.
     } Kind = t_LocalID;
 
     LLLexer::LocTy Loc;

llvm/include/llvm/AsmParser/LLToken.h

enum Kind {
   kw_musttail,
   kw_notail,
   kw_target,
   kw_triple,
   kw_source_filename,
   kw_unwind,
   kw_datalayout,
   kw_volatile,
+  kw_unknown_provenance,
   kw_atomic,
   kw_unordered,
   kw_monotonic,
   kw_acquire,
   kw_release,
   kw_acq_rel,
   kw_seq_cst,
   kw_syncscope,

llvm/lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(musttail);
   KEYWORD(notail);
   KEYWORD(target);
   KEYWORD(triple);
   KEYWORD(source_filename);
   KEYWORD(unwind);
   KEYWORD(datalayout);
   KEYWORD(volatile);
+  KEYWORD(unknown_provenance);
   KEYWORD(atomic);
   KEYWORD(unordered);
   KEYWORD(monotonic);
   KEYWORD(acquire);
   KEYWORD(release);
   KEYWORD(acq_rel);
   KEYWORD(seq_cst);
   KEYWORD(syncscope);

llvm/lib/AsmParser/LLParser.cpp

case lltok::kw_true:
     ID.Kind = ValID::t_Constant;
     break;
   case lltok::kw_false:
     ID.ConstantVal = ConstantInt::getFalse(Context);
     ID.Kind = ValID::t_Constant;
     break;
   case lltok::kw_null: ID.Kind = ValID::t_Null; break;
   case lltok::kw_undef: ID.Kind = ValID::t_Undef; break;
+  case lltok::kw_unknown_provenance: ID.Kind = ValID::t_UnknownProvenance; break;
   case lltok::kw_poison: ID.Kind = ValID::t_Poison; break;
   case lltok::kw_zeroinitializer: ID.Kind = ValID::t_Zero; break;
   case lltok::kw_none: ID.Kind = ValID::t_None; break;
 
   case lltok::lbrace: {
     // ValID ::= '{' ConstVector '}'
     Lex.Lex();
     SmallVector<Constant*, 16> Elts;
case ValID::t_Null:
     V = ConstantPointerNull::get(cast<PointerType>(Ty));
     return false;
   case ValID::t_Undef:
     // FIXME: LabelTy should not be a first-class type.
     if (!Ty->isFirstClassType() || Ty->isLabelTy())
       return error(ID.Loc, "invalid type for undef constant");
     V = UndefValue::get(Ty);
     return false;
+  case ValID::t_UnknownProvenance:
+    if (!Ty->isPointerTy())
+      return error(ID.Loc, "unknown_provenance must be a pointer type");
+    V = UnknownProvenance::get(cast<PointerType>(Ty));
+    return false;
   case ValID::t_EmptyArray:
     if (!Ty->isArrayTy() || cast<ArrayType>(Ty)->getNumElements() != 0)
       return error(ID.Loc, "invalid empty array initializer");
     V = UndefValue::get(Ty);
     return false;
   case ValID::t_Zero:
     // FIXME: LabelTy should not be a first-class type.
     if (!Ty->isFirstClassType() || Ty->isLabelTy())

llvm/lib/IR/AsmWriter.cpp

if (isa<PoisonValue>(CV)) {
     return;
   }
 
   if (isa<UndefValue>(CV)) {
     Out << "undef";
     return;
   }
 
+  if (isa<UnknownProvenance>(CV)) {
+    Out << "unknown_provenance";
+    return;
+  }
+
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CV)) {
     Out << CE->getOpcodeName();
     WriteOptimizationInfo(Out, CE);
     if (CE->isCompare())
       Out << ' ' << CmpInst::getPredicateName(
                         static_cast<CmpInst::Predicate>(CE->getPredicate()));
     Out << " (";