[AA] Add a tbaa-fence intrinsic.

[davidtgoldblatt]

Summary

This can be used to opt out of TBAA for particular pointers without
breaking out the big hammer of asm volatile("" : : "r"(ptr) : "memory").
The underlying motivation is to allow the implementation of C++23's
start_lifetime_as.

We name this a TBAA-fence instead of something more generic to make it
clear that other alias analyses are allowed to see through the fence.
Additionally, the intrinsic returns a "safe-to-use" pointer rather than
a semantic guarantee of being a completely opaque ArgMemOnly intrinsic.
This enables some optimization opportunities: it lets us track uses more
precisely, so we could (e.g.) strip TBAA metadata from associated loads
and stores to enable store-to-load forwarding where beneficial. More
immediately, we don't need the stronger guarantees for
start_lifetime_as, so there's no reason to provide it out of the gate.

[davidtgoldblatt]

Reword.

[nikic]

Could you please add a LangRef entry for the new intrinsic? I don't really get what it does / how it is supposed to interact with TBAA.

[jeroen.dobbelaere]

What exactly are the wanted semantics for such a fence ? And how would it be used ?
Once a pointer is stored into memory, you loose the fence dependency and tbaa does not look into that.

Assume following code:

int bar (int *p, short *q) {
  *p =42;
  *q =99;
  return *p;
}
int foo(int * p) {
   short * q = (short *)tbaa_fence(p);
   return bar(p, q);
}

This will still return 42

[efriedma]

Would we want to use this intrinsic as part of the code generation for C++ new expressions? See https://github.com/llvm/llvm-project/issues/54878 .

[davidtgoldblatt]

Add LangRef entry.

[davidtgoldblatt]

Added a LangRef entry that I hope clarifies things.

In D147020#4232988, @jeroen.dobbelaere wrote:

What exactly are the wanted semantics for such a fence ? And how would it be used ?
Once a pointer is stored into memory, you loose the fence dependency and tbaa does not look into that.

Assume following code:

int bar (int *p, short *q) {
  *p =42;
  *q =99;
  return *p;
}
int foo(int * p) {
   short * q = (short *)tbaa_fence(p);
   return bar(p, q);
}

This will still return 42

The fence only applies between loads/stores before the fence and those based on its result (that is; in the newly written-down semantics that only existed in my head before now. Sorry, should have had documentation to start with). So, the optimization you're describing still being allowed matches those semantics. This is fine for the goal of letting us implement start_lifetime_as -- there's still C++-level UB when bar tries to read a short from an address that contains an int.

Would we want to use this intrinsic as part of the code generation for C++ new expressions? See https://github.com/llvm/llvm-project/issues/54878 .

Hmm, I think this is a plausible fix but I'm not sufficiently confident in my understanding of all the subtleties of LICM to say for sure.

[nikic]

(I don't have the necessary C++ background to review this.)

[jeroen.dobbelaere]

TBAA typically only looks at the metadata to make an alias decision. When adding the need to follow the pointer path, it is easy to proof that there is a llvm.,tbaa.fence in the pointer path. It is hard to proof that there is not. A fence dependency could be hidden by a store/load of the pointer into memory. Make this requirement too hard might make TBAA analysis useless. Making it not hard enough, might make the fence useless.

[davidtgoldblatt]

This doesn't necessitate any changes to TBAA (i.e. it doesn't have to try to identify the "source" of a pointer to know if it comes from a fence or not). Instead, what prevents incorrect behavior is that, since llvm.tbaa.fence's memory effects are opaque (well, aside from being ArgMemOnly), the subsequent operation can't be reordered or eliminated. In this case, TBAA will still report NoAlias if asked about the two operations; but that result doesn't matter because you can't optimize based on that fact with a fence in between them (since the fence could, as far as the optimizer is concerned, do arbitrary loads and stores to the region of memory).

This intrinsic would work just as well for these purposes if it returned void and we got rid of the constraints about the subsequent accesses happening via the result of the call (and was truly just an opaque memory fence). I'd be happy to make that change if it'd be less confusing.

The only thing we get from having this return a value is the option to implement some optimizations later on; for example, in certain cases we can turn "store, fence, load" into a bitcast, letting us get rid of the fence's effects entirely.

[davidtgoldblatt]

Rewrite the LangRef entry. This makes the operation of the fence clearer (it doesn't really change the behavior of TBAA at all; instead it just prevents any other optimization pass from being able to make use of TBAA for the given pointer).

[davidtgoldblatt]

I'm also happy to just strengthen this to a pointer-specific fence (that returns void), that acts otherwise just like asm volatile("" : : "r"(ptr) : "memory") if that would make this more palatable. The only optimization I have in mind for the pointer-returning version is something to allow folding "store/fence/load" to a bitcast, which I don't think is important enough to be worth spending a lot of time on.

[efriedma]

I don't think returning the pointer is actually helpful. Passes dealing with memory aliasing will be walking backwards using something like MemorySSA, not pointer def-use lists, so they'll find it anyway if it's relevant.

Maybe the fence should have a size argument, to indicate the size of the object being allocated? (It's currently not clear exactly what bytes are affected.)

I think we do need to settle the question of whether "new" also needs to call this fence... if it does, we need to measure the compile-time/performance impact on existing code, and if it doesn't, we'll likely end up with two overlapping solutions for very similar issues.

llvm/lib/CodeGen/CodeGenPrepare.cpp

2357 ↗

(On Diff #510981)

This is killing off the fence too early; we have to keep the fence around as long as we have TBAA data, and that still exists at least though ISel. (Not sure off the top of my head if we encode TBAA into MachineInstrs.)

[davidtgoldblatt]

Just return void instead of an opaque pointer, take a size argument, drop early CodeGenPrepare lowering.

[davidtgoldblatt]

I think we do need to settle the question of whether "new" also needs to call this fence... if it does, we need to measure the compile-time/performance impact on existing code, and if it doesn't, we'll likely end up with two overlapping solutions for very similar issues.

I'm happy to run some tests; any particular benchmark you'd like to see? llvm-test-suite doesn't really use placement-new (which I think is the only place where this would be needed?).

I think that two similar-ish solutions may actually be correct; there's a real semantic difference: after a placement new, any prior stores to the memory is dead, while after a tbaa_fence, they're not. So this will necessarily be an over-conservative solution to fix the placement-new/tbaa issues.

[efriedma]

For perf, maybe bootstrap LLVM? I think LLVM itself uses placement new in a number of places...

I hadn't really considered the memory being dead after placement new, but the only optimization that would really open up is dead store elimination, I think? Not sure how important that is; we currently don't do that optimization anyway.

[cor3ntin]

I think @hubert.reinterpretcast may have opinions on is PR.

llvm/docs/LangRef.rst

 The ``name:`` field is the label identifier. The ``file:`` field is the
 :ref:`DIFile` the label is present in. The ``line:`` field is the source line
 within the file where the label is declared.
 
 .. code-block:: text
 
   !2 = !DILabel(scope: !0, name: "foo", file: !1, line: 7)
 
+.. _tbaa_metadata:
+
 '``tbaa``' Metadata
 ^^^^^^^^^^^^^^^^^^^
 
 In LLVM IR, memory does not have types, so LLVM's own type system is not
 suitable for doing type based alias analysis (TBAA). Instead, metadata is
 added to the IR to describe a type system of a higher level language. This
 can be used to implement C/C++ strict type aliasing rules, but it can also
 be used to implement custom alias analysis behavior for other languages.

 
 The '``llvm.fptrunc.round``' intrinsic casts a ``value`` from a larger
 :ref:`floating-point <t_floating>` type to a smaller :ref:`floating-point
 <t_floating>` type.
 This intrinsic is assumed to execute in the default :ref:`floating-point
 environment <floatenv>` *except* for the rounding mode.
 This intrinsic is not supported on all targets. Some targets may not support
 all rounding modes.
+
+
+'``llvm.tbaa.fence``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+::
+
+      declare void @llvm.tbaa.fence(ptr <ptr>, i64 <len>)
+
+Overview:
+"""""""""
+
+The '``llvm.tbaa.fence``' prevents NoAlias responses from type-based alias
+analysis from resulting in the reordering or elision of memory operations to the
+``<len>`` bytes starting at ``<ptr>``.
+
+Arguments:
+""""""""""
+
+The first argument to the intrinsic is a pointer to be fenced, and the second is
+the number of bytes.
+
+Semantics:
+""""""""""
+
+Does nothing, but in an opaque manner that forces optimization passes to treat
+the builtin as potentially reading from or writing to the given memory. This
+prevents stores from being elided or loads from being folded away, even if the
+associated :ref:`TBAA metadata<tbaa_metadata>` would otherwise justify such an
+outcome. Optimization passes are permitted to remove or ignore the fence if they
+can prove that TBAA will not return a NoAlias result when evaluating operations
+to the pointed-to storage before the fence and those after it.

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
     case Intrinsic::coro_end:
     case Intrinsic::coro_frame:
     case Intrinsic::coro_size:
     case Intrinsic::coro_align:
     case Intrinsic::coro_suspend:
     case Intrinsic::coro_subfn_addr:
     case Intrinsic::threadlocal_address:
     case Intrinsic::experimental_widenable_condition:
+    case Intrinsic::tbaa_fence:
       // These intrinsics don't actually represent code after lowering.
       return 0;
     }
     return 1;
   }
 
   InstructionCost getCallInstrCost(Function *F, Type *RetTy,
                                    ArrayRef<Type *> Tys,

llvm/include/llvm/IR/Intrinsics.td

def int_launder_invariant_group : DefaultAttrsIntrinsic<[llvm_anyptr_ty],
                                             [LLVMMatchType<0>],
                                             [IntrInaccessibleMemOnly, IntrSpeculatable, IntrWillReturn]>;
 
 
 def int_strip_invariant_group : DefaultAttrsIntrinsic<[llvm_anyptr_ty],
                                           [LLVMMatchType<0>],
                                           [IntrSpeculatable, IntrNoMem, IntrWillReturn]>;
 
+def int_tbaa_fence : DefaultAttrsIntrinsic<[],
+                                    [llvm_ptr_ty, llvm_i64_ty],
+                                    [IntrArgMemOnly, IntrWillReturn,
+                                    NoCapture<ArgIndex<0>>]>;
+
 //===------------------------ Stackmap Intrinsics -------------------------===//
 //
 def int_experimental_stackmap : DefaultAttrsIntrinsic<[],
                                   [llvm_i64_ty, llvm_i32_ty, llvm_vararg_ty],
                                   [Throws]>;
 def int_experimental_patchpoint_void : Intrinsic<[],
                                                  [llvm_i64_ty, llvm_i32_ty,
                                                   llvm_ptr_ty, llvm_i32_ty,

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::clear_cache:
     if (const char *FunctionName = TLI.getClearCacheBuiltinName())
       lowerCallToExternalSymbol(I, FunctionName);
     return;
   case Intrinsic::donothing:
   case Intrinsic::seh_try_begin:
   case Intrinsic::seh_scope_begin:
   case Intrinsic::seh_try_end:
   case Intrinsic::seh_scope_end:
+  case Intrinsic::tbaa_fence:
     // ignore
     return;
   case Intrinsic::experimental_stackmap:
     visitStackmap(I);
     return;
   case Intrinsic::experimental_patchpoint_void:
   case Intrinsic::experimental_patchpoint_i64:
     visitPatchpoint(I);

llvm/test/Analysis/TypeBasedAliasAnalysis/tbaa-fence.ll

+; RUN: opt < %s -aa-pipeline=tbaa  -passes=aa-eval -evaluate-aa-metadata \
+; RUN:          -print-no-aliases -print-modref -disable-output 2>&1 | FileCheck %s
+
+declare void @llvm.tbaa.fence(ptr, i64 %len)
+
+define void @simple(ptr %p) {
+entry:
+  ; CHECK-LABEL: simple
+  ; CHECK: NoAlias:   %x = load i8, ptr %p, align 1, !tbaa !3 <->   store i8 1, ptr %p, align 1, !tbaa !0
+  ; CHECK: Both ModRef:  Ptr: i8* %p     <->  call void @llvm.tbaa.fence(ptr %p, i64 1)
+  store i8 1, ptr %p, !tbaa !3
+  call void @llvm.tbaa.fence(ptr %p, i64 1)
+  %x = load i8, ptr %p, !tbaa !4
+  ret void
+}
+
+!0 = !{!"root"}
+!1 = !{!"type1", !0, i64 0}
+!2 = !{!"type2", !0, i64 0}
+!3 = !{!1, !1, i64 0, i64 0}
+!4 = !{!2, !2, i64 0, i64 0}

llvm/test/CodeGen/Generic/tbaa-fence.ll

+; RUN: llc < %s
+
+declare void @llvm.tbaa.fence(ptr, i64 %len)
+
+define void @call_fence(ptr %p, i64 %len) {
+  call void @llvm.tbaa.fence(ptr %p, i64 %len)
+  ret void
+}