[IR] Introduce load assume operand bundle

[aeubanks]

Summary

This is a new assume operand bundle which allows us to assume that a
load from a pointer at a specific location in the IR will always be some
value.

The name of the bundle is "load". The first operand is the pointer and
the second operand is the value that a load at the assume location would
produce.

This is useful for exposing the vtable value of a C++ object after its
constructor without having to insert a load into the instruction stream.

[aeubanks]

happy to change the name if there's a better alternative

[jdoerfert]

This is useful for exposing the vtable value of a C++ object after its constructor without having to insert a load into the instruction stream.

Why is an assume better than a load?

[aeubanks]

In D112016#3071078, @jdoerfert wrote:

This is useful for exposing the vtable value of a C++ object after its constructor without having to insert a load into the instruction stream.

Why is an assume better than a load?

Adding an extra load will affect cost modelling, e.g. inliner thresholds, and other various ad-hoc cost heuristics. assumes are free.

[nikic]

As long as the load is speculatable, it should count as an ephemeral value and be considered as free by the inliner at least.

[jdoerfert]

In D112016#3071082, @aeubanks wrote:

In D112016#3071078, @jdoerfert wrote:

This is useful for exposing the vtable value of a C++ object after its constructor without having to insert a load into the instruction stream.

Why is an assume better than a load?

Adding an extra load will affect cost modelling, e.g. inliner thresholds, and other various ad-hoc cost heuristics. assumes are free.

I really want to get to the outlined assumes function model but I guess this is an OK first step.

• outlined model ---

call @llvm.assume(i1 true) ["assume_fn"(void (i32*, i32) @__assume_equal, i32* %P, i32 %V]

define void @__assume_equal(i32* %P, i32 %V) {
  %L = load i32* %P
  %cmp = icmp eq i32 %L, %V
  call @llvm.assume(i1 %cmp)
}

because it is way more flexible. We can use it to encode
__builtin_assume(foobar() == barfoo());
without risking side-effects to leak or cause regressions,
as another example.

[aeubanks]

In D112016#3071101, @jdoerfert wrote:

In D112016#3071082, @aeubanks wrote:

In D112016#3071078, @jdoerfert wrote:

This is useful for exposing the vtable value of a C++ object after its constructor without having to insert a load into the instruction stream.

Why is an assume better than a load?

Adding an extra load will affect cost modelling, e.g. inliner thresholds, and other various ad-hoc cost heuristics. assumes are free.

I really want to get to the outlined assumes function model but I guess this is an OK first step.

• outlined model ---

call @llvm.assume(i1 true) ["assume_fn"(void (i32*, i32) @__assume_equal, i32* %P, i32 %V]

define void @__assume_equal(i32* %P, i32 %V) {
  %L = load i32* %P
  %cmp = icmp eq i32 %L, %V
  call @llvm.assume(i1 %cmp)
}

because it is way more flexible. We can use it to encode
__builtin_assume(foobar() == barfoo());
without risking side-effects to leak or cause regressions,
as another example.

Makes sense, and I'm happy to modify this to use that if we ever get there.

[aeubanks]

In D112016#3071099, @nikic wrote:

As long as the load is speculatable, it should count as an ephemeral value and be considered as free by the inliner at least.

I'm not seeing that:

$ cat /tmp/a.ll
declare i8 @f(i8* %p)
declare void @llvm.assume(i1)

declare void @constructor(i8*)
declare void @foo(i8*)

define i8 @g1(i8* %p) {
        call void @constructor(i8* %p)
        %i = load i8, i8* %p
        %c = icmp eq i8 %i, 2
        call void @llvm.assume(i1 %c)
        %r = call i8 @f(i8* %p)
        ret i8 %r
}

define i8 @wrapper1(i8* %p) {
        %r = call i8 @g1(i8* %p)
        ret i8 %r
}

define i8 @g2(i8* %p) {
        call void @constructor(i8* %p)
        call void @llvm.assume(i1 true) ["load"(i8* %p, i8 2)]
        %r = call i8 @f(i8* %p)
        ret i8 %r
}

define i8 @wrapper2(i8* %p) {
        %r = call i8 @g2(i8* %p)
        ret i8 %r
}

$ ./build/rel/bin/opt -passes='print<inline-cost>' -disable-output /tmp/a.ll
      Analyzing call of g1... (caller:wrapper1)
define i8 @g1(i8* %p) {
; cost before = -35, cost after = 0, threshold before = 674, threshold after = 674, cost delta = 35
  call void @constructor(i8* %p)
; cost before = 0, cost after = 5, threshold before = 674, threshold after = 674, cost delta = 5
  %i = load i8, i8* %p, align 1
; No analysis for the instruction
  %c = icmp eq i8 %i, 2
; No analysis for the instruction
  call void @llvm.assume(i1 %c)
; cost before = 5, cost after = 40, threshold before = 674, threshold after = 674, cost delta = 35
  %r = call i8 @f(i8* %p)
; cost before = 40, cost after = 40, threshold before = 674, threshold after = 674, cost delta = 0
  ret i8 %r
}
      NumConstantArgs: 0
      NumConstantOffsetPtrArgs: 1
      NumAllocaArgs: 0
      NumConstantPtrCmps: 0
      NumConstantPtrDiffs: 0
      NumInstructionsSimplified: 1
      NumInstructions: 4
      SROACostSavings: 0
      SROACostSavingsLost: 0
      LoadEliminationCost: 0
      ContainsNoDuplicateCall: 0
      Cost: 40
      Threshold: 337
      Analyzing call of g2... (caller:wrapper2)
define i8 @g2(i8* %p) {
; cost before = -35, cost after = 0, threshold before = 674, threshold after = 674, cost delta = 35
  call void @constructor(i8* %p)
; No analysis for the instruction
  call void @llvm.assume(i1 true) [ "load"(i8* %p, i8 2) ]
; cost before = 0, cost after = 35, threshold before = 674, threshold after = 674, cost delta = 35
  %r = call i8 @f(i8* %p)
; cost before = 35, cost after = 35, threshold before = 674, threshold after = 674, cost delta = 0
  ret i8 %r
}
      NumConstantArgs: 0
      NumConstantOffsetPtrArgs: 1
      NumAllocaArgs: 0
      NumConstantPtrCmps: 0
      NumConstantPtrDiffs: 0
      NumInstructionsSimplified: 1
      NumInstructions: 3
      SROACostSavings: 0
      SROACostSavingsLost: 0
      LoadEliminationCost: 0
      ContainsNoDuplicateCall: 0
      Cost: 35
      Threshold: 337

[rnk]

In D112016#3070842, @aeubanks wrote:

happy to change the name if there's a better alternative

To bikeshed a bit, how about "load_eq"? Meaning, "a load of op1 is equal to op2".

[nikic]

In D112016#3071380, @aeubanks wrote:

In D112016#3071099, @nikic wrote:

As long as the load is speculatable, it should count as an ephemeral value and be considered as free by the inliner at least.

I'm not seeing that: [...]

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

[jdoerfert]

In D112016#3072158, @nikic wrote:

In D112016#3071380, @aeubanks wrote:

In D112016#3071099, @nikic wrote:

As long as the load is speculatable, it should count as an ephemeral value and be considered as free by the inliner at least.

I'm not seeing that: [...]

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

I think side-effect free is sufficient, though, haven't thought long about it. (When you say deref(1) you mean deref(sizeof(access)), right?)

[fhahn]

In D112016#3073235, @jdoerfert wrote:

In D112016#3072158, @nikic wrote:

In D112016#3071380, @aeubanks wrote:

In D112016#3071099, @nikic wrote:

As long as the load is speculatable, it should count as an ephemeral value and be considered as free by the inliner at least.

I'm not seeing that: [...]

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

I think side-effect free is sufficient, though, haven't thought long about it. (When you say deref(1) you mean deref(sizeof(access)), right?)

I agree that side-effect-free should be sufficient to ignore them here as well. looks like there are a couple of places that define their own checks for ephemeral values, so it might be a good start to consolidate them

[nikic]

In D112016#3073235, @jdoerfert wrote:

In D112016#3072158, @nikic wrote:

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

I think side-effect free is sufficient, though, haven't thought long about it. (When you say deref(1) you mean deref(sizeof(access)), right?)

Right, this was referring to @aeubanks' particular example, which happened to use access size 1.

I gave this a try (https://gist.github.com/nikic/531267d972ce71edf3896e25bc50456a) and it seems to work fine (i.e. no test failures). The precise condition would be wouldInstructionBeTriviallyDead(), which we can approximate by !mayHaveSideEffect() && !isTerminator().

[jdoerfert]

In D112016#3073705, @nikic wrote:

In D112016#3073235, @jdoerfert wrote:

In D112016#3072158, @nikic wrote:

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

I think side-effect free is sufficient, though, haven't thought long about it. (When you say deref(1) you mean deref(sizeof(access)), right?)

Right, this was referring to @aeubanks' particular example, which happened to use access size 1.

I gave this a try (https://gist.github.com/nikic/531267d972ce71edf3896e25bc50456a) and it seems to work fine (i.e. no test failures). The precise condition would be wouldInstructionBeTriviallyDead(), which we can approximate by !mayHaveSideEffect() && !isTerminator().

It seems we want to do that for sure, which means we can (probably should) hold of with this patch for now, right?

[aeubanks]

In D112016#3073861, @jdoerfert wrote:

In D112016#3073705, @nikic wrote:

In D112016#3073235, @jdoerfert wrote:

In D112016#3072158, @nikic wrote:

Thus the "as long as the load is speculatable" caveat. It works if you add a dereferenceable(1) attribute. Though now that I think about this, I have no idea why speculatability is even a requirement for ephemeral values -- shouldn't side-effect freedom be sufficient? In that case your example would work without the dereferenceable(1).

I think side-effect free is sufficient, though, haven't thought long about it. (When you say deref(1) you mean deref(sizeof(access)), right?)

Right, this was referring to @aeubanks' particular example, which happened to use access size 1.

I gave this a try (https://gist.github.com/nikic/531267d972ce71edf3896e25bc50456a) and it seems to work fine (i.e. no test failures). The precise condition would be wouldInstructionBeTriviallyDead(), which we can approximate by !mayHaveSideEffect() && !isTerminator().

It seems we want to do that for sure, which means we can (probably should) hold of with this patch for now, right?

there are still many places that don't use ephemerality to count instructions, e.g. the ThinLTO instruction import limit, so I think this still has value
unless you think it'd make more sense to update all the other places, like the ThinLTO instruction import limit, to also use this sort of cost modelling

[rnk]

Aside from the cost modeling, I think there is value in having a more compact representation for this concept. It is nice to be able to turn four instructions (cast, load, icmp, assume) into one (assume). OK, maybe opaque pointers will remove the cast, but the point stands. This feature also has applications besides C++ devirtualization, so I think it's worth the added maintenance cost.

[Prazek]

In D112016#3071407, @rnk wrote:

In D112016#3070842, @aeubanks wrote:

happy to change the name if there's a better alternative

To bikeshed a bit, how about "load_eq"? Meaning, "a load of op1 is equal to op2".

Or "loads" (like "loads" value from a pointer), but I think "load_eq" also is a bit more descriptive.
I actually thought adding this feature will require more engineering, well done.

[aeubanks]

"load" -> "load_eq"

[jdoerfert]

Works for me, others should chime in.

[nikic]

This will require changes to AA and access modelling. Normally assumes are inaccessiblememonly, but in this case the assume also reads the location of the pointer. In particular, you can not hoist or sink a store of the location across the assume, as it may invalidate the assumption. Thankfully we do have the tools to model this, because operand bundles can change AA behavior. You'd have to adjust the handling of assume in hasReadingOperandBundles() to count as an accessible memory read for load_eq operand bundles. BasicAA could then restrict it to just the passed location. However, there are also other places that explicitly skip over assume intrinsics on the assumption that they do not access accessible memory. An obvious example is MemorySSA, which does not create memory accesses for assumes (but would need to create them for load_eq), but I remember similar code existing in a few other places as well.

Generally I'd like to see the followup patches that are needed to make this actually work. A simple load+icmp assume will "just work", but this new operand bundle will need explicit support (beyond the AA modelling, hopefully only in GVN and nowhere else?)

llvm/docs/LangRef.rst

 necessarily during) the execution of the callee.
 
 .. _assume_opbundles:
 
 Assume Operand Bundles
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Operand bundles on an :ref:`llvm.assume <int_assume>` allows representing
-assumptions that a :ref:`parameter attribute <paramattrs>` or a
-:ref:`function attribute <fnattrs>` holds for a certain value at a certain
-location. Operand bundles enable assumptions that are either hard or impossible
-to represent as a boolean argument of an :ref:`llvm.assume <int_assume>`.
+various assumptions. This is most commonly used to represent assumptions that a
+:ref:`parameter attribute <paramattrs>` or a :ref:`function attribute <fnattrs>`
+holds for a certain value at a certain location. Operand bundles enable
+assumptions that are either hard or impossible to represent as a boolean
+argument of an :ref:`llvm.assume <int_assume>`.
 
 An assume operand bundle has the form:
 
 ::
 
-      "<tag>"([ <holds for value> [, <attribute argument>] ])
+      "<tag>"([ <holds for value> [, <arguments>] ])
 
-* The tag of the operand bundle is usually the name of attribute that can be
-  assumed to hold. It can also be `ignore`, this tag doesn't contain any
-  information and should be ignored.
-* The first argument if present is the value for which the attribute hold.
+* The tag of the operand bundle can be the name of attribute that can be
+  assumed to hold.
+
+  * The first argument if present is the value for which the attribute holds.
   * The second argument if present is an argument of the attribute.
 
+* The tag can be `load_eq`, meaning that the value pointed to by the pointer
+  argument is known to be a certain value.
+
+  * The first argument is the pointer argument.
+  * The second argument is the value that the pointer argument is known to point
+    to.
+
+* The tag can be `ignore`, meaning this tag doesn't contain any
+  information and should be ignored.
+
 If there are no arguments the attribute is a property of the call location.
 
 If the represented attribute expects a constant argument, the argument provided
 to the operand bundle should be a constant as well.
 
 For example:
 
 .. code-block:: llvm

llvm/lib/IR/Verifier.cpp

void Verifier::visitIntrinsicCall(Intrinsic::ID ID, CallBase &Call) {
   }
 
   switch (ID) {
   default:
     break;
   case Intrinsic::assume: {
     for (auto &Elem : Call.bundle_op_infos()) {
       Assert(Elem.Tag->getKey() == "ignore" ||
+                 Elem.Tag->getKey() == "load_eq" ||
                  Attribute::isExistingAttribute(Elem.Tag->getKey()),
              "tags must be valid attribute names", Call);
+      unsigned ArgCount = Elem.End - Elem.Begin;
+      if (Elem.Tag->getKey() == "load_eq") {
+        Assert(ArgCount == 2, "load_eq assume should have 2 arguments", Call);
+        auto *PTy =
+            dyn_cast<PointerType>(Call.getOperand(Elem.Begin)->getType());
+        Assert(PTy, "load_eq assume's first argument should be a pointer",
+               Call);
+        auto *VTy = Call.getOperand(Elem.Begin + 1)->getType();
+        Assert(
+            PTy->isOpaqueOrPointeeTypeMatches(VTy),
+            "load_eq assume's first argument should be a pointer to the second "
+            "argument's type",
+            Call);
+      } else {
         Attribute::AttrKind Kind =
             Attribute::getAttrKindFromName(Elem.Tag->getKey());
-      unsigned ArgCount = Elem.End - Elem.Begin;
         if (Kind == Attribute::Alignment) {
           Assert(ArgCount <= 3 && ArgCount >= 2,
                  "alignment assumptions should have 2 or 3 arguments", Call);
           Assert(Call.getOperand(Elem.Begin)->getType()->isPointerTy(),
                  "first argument should be a pointer", Call);
           Assert(Call.getOperand(Elem.Begin + 1)->getType()->isIntegerTy(),
                  "second argument should be an integer", Call);
           if (ArgCount == 3)
             Assert(Call.getOperand(Elem.Begin + 2)->getType()->isIntegerTy(),
                    "third argument should be an integer if present", Call);
           return;
         }
         Assert(ArgCount <= 2, "too many arguments", Call);
         if (Kind == Attribute::None)
           break;
         if (Attribute::isIntAttrKind(Kind)) {
           Assert(ArgCount == 2, "this attribute should have 2 arguments", Call);
           Assert(isa<ConstantInt>(Call.getOperand(Elem.Begin + 1)),
-               "the second argument should be a constant integral value", Call);
+                 "the second argument should be a constant integral value",
+                 Call);
         } else if (Attribute::canUseAsParamAttr(Kind)) {
           Assert((ArgCount) == 1, "this attribute should have one argument",
                  Call);
         } else if (Attribute::canUseAsFnAttr(Kind)) {
           Assert((ArgCount) == 0, "this attribute has no argument", Call);
         }
       }
+    }
     break;
   }
   case Intrinsic::coro_id: {
     auto *InfoArg = Call.getArgOperand(3)->stripPointerCasts();
     if (isa<ConstantPointerNull>(InfoArg))
       break;
     auto *GV = dyn_cast<GlobalVariable>(InfoArg);
     Assert(GV && GV->isConstant() && GV->hasDefinitiveInitializer(),

llvm/test/Verifier/assume-bundles.ll

; CHECK: this attribute should have one argument
   call void @llvm.assume(i1 true) ["noalias"()]
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32 4)]
 ; CHECK: alignment assumptions should have 2 or 3 arguments
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32 4, i32 4)]
 ; CHECK: second argument should be an integer
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32* %P2)]
 ; CHECK: third argument should be an integer if present
   call void @llvm.assume(i1 true) ["align"(i32* %P, i32 %P1, i32* %P2)]
+; CHECK: load_eq assume should have 2 arguments
+  call void @llvm.assume(i1 true) ["load_eq"(i32* %P)]
+; CHECK: load_eq assume's first argument should be a pointer
+  call void @llvm.assume(i1 true) ["load_eq"(i32 %P1, i32 %P1)]
+; CHECK: load_eq assume's first argument should be a pointer to the second argument's type
+  call void @llvm.assume(i1 true) ["load_eq"(i32* %P, i16 2)]
   ret void
 }