[LangRef] Add integer wrapping operand bundles.

[fhahn]

Summary

This patch introduces new nuw and nsw operand bundles, to indicate
no-unsigned-wrap and no-signed-wrap for the computation of the result of
a call.

Initially, functions that want to use it need to opt-in, as there are
many cases where the bundle probably makes little sense. This mirrors
fast-math flags, which can be specified directly for calls returning
floating point values. Adding nuw/nsw as operand bundles is very
lightweight. If there are a lot of users, it might make sense to
consider adding the flags directly to calls, but I think operand bundles
allow us to make progress quickly and see how widely useful this
actually is.

Tot start with, llvm.matrix.multiply will use it, but other candidates
are the integer reduction intrinsics.

[fhahn]

Add example.

[arsenm]

I don't understand how this is easier than adding the flags to calls?

[jdoerfert]

llvm/docs/LangRef.rst

2306

[Drive By]

Should we add a reference to nuw/nsw specification (if we have one)?

I'm not sure the the description is explicit enough. `if
unsigned and/or signed overflow, respectively, occurs`, where/when?

Nit: I would say the type is spelled i1 but I don't care much.

[fhahn]

Improve wording.

In D84201#2163328, @arsenm wrote:

I don't understand how this is easier than adding the flags to calls?

The main advantages IMO of the bundle approach IMO are

1. no need to modify the IR directly, which might be quite controversial
2. adding the flags directly to calls means all calls need to pay some cost (a few extra bits somewhere)
3. the integer wrapping flags are probably much less useful for calls than the fast-math flags. The fast-math flags describe a property of the result value (e.g does not contain signed zeroes) which is useful to know when using the result of the call, whereas the wrapping flags mostly describe how the result is computed (without overflow), which is not too helpful to know about at the call site, but helpful when lowering certain intrinsics.

Hence I think the bundles are more lightweight than adding the flags directly to start with. If they prove useful for a large range of calls, it should be easy to auto-upgrade the existing uses to flags on the instruction and we would have a solid data point to argue for adding them directly to calls. Does that make sense?

llvm/docs/LangRef.rst

2306

Should we add a reference to nuw/nsw specification (if we have one)?

I don't think there is. AFAIK it is only specified in the semantics of the instructions taking nuw/nsw flags.

I'm not sure the the description is explicit enough. if unsigned and/or signed overflow, respectively, occurs, where/when?

yeah, I should have been more explicit. I changed it to

the return value of the called function is a :ref:poison value <poisonvalues> if unsigned and/or signed overflow, respectively, occurs during any computation the return value depends on in the called function (see value *dependence* as defined for :ref:poison value <poisonvalues>).

Nit: I would say the type is spelled i1 but I don't care much.

[arsenm]

In D84201#2164166, @fhahn wrote:

2. adding the flags directly to calls means all calls need to pay some cost (a few extra bits somewhere)

But calls already have fast math flags; I assume these would alias the same bits

[fhahn]

In D84201#2164274, @arsenm wrote:

In D84201#2164166, @fhahn wrote:

2. adding the flags directly to calls means all calls need to pay some cost (a few extra bits somewhere)

But calls already have fast math flags; I assume these would alias the same bits

Oh right, I guess we could do that and then it would be free in terms of size. But I think the main question is if nuw/nsw flags are best use for those bits and what makes them special, as compared to other properties for which we have bundles or call site attributes (mainly point 3) about the general usefulness of those flags.

[SjoerdMeijer]

Interesting work. Adding @efriedma, with whom I recently had a overflow discussion for intrinsic @llvm.get.active.lane.mask, and I think that this would help me.

[efriedma]

I guess there are sort of three two precedents in IR for this sort of thing:

1. fast-math flags, as mentioned earlier.
2. constant arguments; see, for example, llvm.ctlz
3. metadata; for example, !range on calls.

I don't think we've really ever used operand bundles this way.

Metadata might make more sense here.

llvm/docs/LangRef.rst

2296

if unsigned and/or signed overflow, respectively, occurs during any computation the return value depends on in the called function

I don't think a generic definition here is really useful; the semantics are really specific to the intrinsic in question.

In particular, for matrix multiplication, this definition is a but unclear. The order of the addition operations isn't defined for matrix multiplication; that matters for nsw.

[fhahn]

In D84201#2165268, @efriedma wrote:

I guess there are sort of three two precedents in IR for this sort of thing:

1. fast-math flags, as mentioned earlier.
2. constant arguments; see, for example, llvm.ctlz
3. metadata; for example, !range on calls.

I don't think we've really ever used operand bundles this way.

Metadata might make more sense here.

There are too many things to do the same thing :)

My understanding from the langref is that operand bundles basically "are like metadata, but dropping them is incorrect and will change program semantics". I guess we might actually need to drop the metadata on some changes to the call. I don't really mind whichever solution to pursue, they should all achieve the same result. So unless there are any concerns for using metadata, I'll update the patch in a day or two.

llvm/docs/LangRef.rst

2296

Agreed, it probably makes most sense to delegate that to the intrinsics that opted in. Also, it should probably be limited to intrinsics, not sure it makes sense for arbitrary functions.

llvm/docs/LangRef.rst

 A "gc-live" operand bundle is only valid on a :ref:`gc.statepoint <gc_statepoint>`
 intrinsic. The operand bundle must contain every pointer to a garbage collected
 object which potentially needs to be updated by the garbage collector.
 
 When lowered, any relocated value will be recorded in the corresponding
 :ref:`stackmap entry <statepoint-stackmap-format>`.  See the intrinsic description
 for further details.
 
+.. _ob_wrapping
+
+Integer Wrapping Operand Bundles
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+There are two operand bundles to specify integer wrapping behavior at a call
+site: ``"nuw"`` for "No Unsigned Wrap" and ``"nsw"`` for "No Signed Wrap". If
+the ``nuw`` and/or ``nsw`` bundles are present, the return value of the called
+function is a :ref:`poison value <poisonvalues>` if  unsigned and/or signed
+overflow, respectively, occurs during any computation the return value
+depends on in the called function (see value *dependence* as defined for
+:ref:`poison value <poisonvalues>`). The ``nuw`` and ``nsw`` bundles are only
+supported for calls of the following functions: ``@llvm.matrix.multiply.*``
+with integer matrix operands.
+
+The integer wrapping operand bundles take exactly one argument of type ``i1``,
+which has to be either ``true`` or ``false``. At most one of each ``"nuw"`` and
+``"nsw"`` bundle can be attached to a call. See the example below.
+
+.. code-block:: llvm
+      %r = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 true), "nsw"(i1 true) ]
+
+
 .. _moduleasm:
 
 Module-Level Inline Assembly
 ----------------------------
 
 Modules may contain "module-level inline asm" blocks, which corresponds
 to the GCC "file scope inline asm" blocks. These blocks are internally
 concatenated by LLVM and treated as a single unit, but may be separated

 The first vector argument ``%A`` corresponds to a matrix with ``<OuterRows> *
 <Inner>`` elements, and the second argument ``%B`` to a matrix with
 ``<Inner> * <OuterColumns>`` elements. Arguments ``<OuterRows>``,
 ``<Inner>`` and ``<OuterColumns>`` must be positive, constant integers. The
 returned vector must have ``<OuterRows> * <OuterColumns>`` elements.
 Vectors ``%A``, ``%B``, and the returned vector all have the same float or
 integer element type.
 
+:ref:`"Integer wrapping operand bundles" <ob_wrapping>` can be used to indicate whether ``nuw``
+and ``nsw`` should be used when '``llvm.matrix.multiply.*``' calls with integer
+matrix arguments.
 
 '``llvm.matrix.column.major.load.*``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 This is an overloaded intrinsic.
 

llvm/include/llvm/IR/LLVMContext.h

#undef LLVM_FIXED_MD_KIND
   /// LLVMContext::LLVMContext().
   enum : unsigned {
     OB_deopt = 0,         // "deopt"
     OB_funclet = 1,       // "funclet"
     OB_gc_transition = 2, // "gc-transition"
     OB_cfguardtarget = 3, // "cfguardtarget"
     OB_preallocated = 4,  // "preallocated"
     OB_gc_live = 5,       // "gc-live"
+    OB_nuw = 6,           // "nuw"
+    OB_nsw = 7,           // "nsw"
   };
 
   /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.
   /// This ID is uniqued across modules in the current LLVMContext.
   unsigned getMDKindID(StringRef Name) const;
 
   /// getMDKindNames - Populate client supplied SmallVector with the name for
   /// custom metadata IDs registered in this LLVMContext.

llvm/lib/IR/LLVMContext.cpp

assert(PreallocatedEntry->second == LLVMContext::OB_preallocated &&
          "preallocated operand bundle id drifted!");
   (void)PreallocatedEntry;
 
   auto *GCLiveEntry = pImpl->getOrInsertBundleTag("gc-live");
   assert(GCLiveEntry->second == LLVMContext::OB_gc_live &&
          "gc-transition operand bundle id drifted!");
   (void)GCLiveEntry;
 
+  auto *NUWEntry = pImpl->getOrInsertBundleTag("nuw");
+  assert(NUWEntry->second == LLVMContext::OB_nuw &&
+         "nuw operand bundle id drifted!");
+  (void)NUWEntry;
+
+  auto *NSWEntry = pImpl->getOrInsertBundleTag("nsw");
+  assert(NSWEntry->second == LLVMContext::OB_nsw &&
+         "nsw operand bundle id drifted!");
+  (void)NSWEntry;
+
   SyncScope::ID SingleThreadSSID =
       pImpl->getOrInsertSyncScopeID("singlethread");
   assert(SingleThreadSSID == SyncScope::SingleThread &&
          "singlethread synchronization scope ID drifted!");
   (void)SingleThreadSSID;
 
   SyncScope::ID SystemSSID =
       pImpl->getOrInsertSyncScopeID("");

llvm/lib/IR/Verifier.cpp

if (Function *F = Call.getCalledFunction())
     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
       visitIntrinsicCall(ID, Call);
 
   // Verify that a callsite has at most one "deopt", at most one "funclet", at
   // most one "gc-transition", at most one "cfguardtarget",
   // and at most one "preallocated" operand bundle.
   bool FoundDeoptBundle = false, FoundFuncletBundle = false,
        FoundGCTransitionBundle = false, FoundCFGuardTargetBundle = false,
-       FoundPreallocatedBundle = false, FoundGCLiveBundle = false;;
+       FoundPreallocatedBundle = false, FoundGCLiveBundle = false,
+       FoundNUWBundle = false, FoundNSWBundle = false;
   for (unsigned i = 0, e = Call.getNumOperandBundles(); i < e; ++i) {
     OperandBundleUse BU = Call.getOperandBundleAt(i);
     uint32_t Tag = BU.getTagID();
     if (Tag == LLVMContext::OB_deopt) {
       Assert(!FoundDeoptBundle, "Multiple deopt operand bundles", Call);
       FoundDeoptBundle = true;
     } else if (Tag == LLVMContext::OB_gc_transition) {
       Assert(!FoundGCTransitionBundle, "Multiple gc-transition operand bundles",
if (Tag == LLVMContext::OB_deopt) {
                  Input->getIntrinsicID() == Intrinsic::call_preallocated_setup,
              "\"preallocated\" argument must be a token from "
              "llvm.call.preallocated.setup",
              Call);
     } else if (Tag == LLVMContext::OB_gc_live) {
       Assert(!FoundGCLiveBundle, "Multiple gc-live operand bundles",
              Call);
       FoundGCLiveBundle = true;
+    } else if (Tag == LLVMContext::OB_nuw) {
+      Assert(!FoundNUWBundle, "Multiple nuw operand bundles", Call);
+      FoundNUWBundle = true;
+    } else if (Tag == LLVMContext::OB_nsw) {
+      Assert(!FoundNSWBundle, "Multiple nsw operand bundles", Call);
+      FoundNSWBundle = true;
     }
   }
 
+  // Nuw/nsw bundles are only supported for certain calls.
+  auto IsValidFunctionForWrapBundle = [&Call]() {
+    if (auto *II = dyn_cast<IntrinsicInst>(&Call))
+      return II->getIntrinsicID() == Intrinsic::matrix_multiply &&
+             II->getType()->getScalarType()->isIntegerTy();
+    return false;
+  };
+  Assert((!FoundNUWBundle && !FoundNSWBundle) || IsValidFunctionForWrapBundle(),
+         "nuw/nsw bundles not supported on the called function", Call);
+
+  // Check the arguments of nuw & nsw bundles.
+  auto VerifyWrapBundle = [this, &Call](unsigned BundleId, StringRef Name) {
+    auto Bundle = Call.getOperandBundle(BundleId);
+    if (Bundle) {
+      Assert(Bundle->Inputs.size() == 1,
+             Name + " bundle must have a single argument", Call);
+      auto OpTy = Bundle->Inputs[0]->getType();
+      Assert(OpTy->isIntegerTy() && OpTy->getIntegerBitWidth() == 1,
+             Name + " bundle operand must be an integer with bitwidth 1", Call);
+      Assert(isa<ConstantInt>(Bundle->Inputs[0]),
+             Name + " bundle operand must be a constant integer", Call);
+    }
+  };
+  VerifyWrapBundle(LLVMContext::OB_nuw, "nuw");
+  VerifyWrapBundle(LLVMContext::OB_nsw, "nsw");
+
   // Verify that each inlinable callsite of a debug-info-bearing function in a
   // debug-info-bearing function has a debug location attached to it. Failure to
   // do so causes assertion failures when the inliner sets up inline scope info.
   if (Call.getFunction()->getSubprogram() && Call.getCalledFunction() &&
       Call.getCalledFunction()->getSubprogram())
     AssertDI(Call.getDebugLoc(),
              "inlinable function call in a function with "
              "debug info must have a !dbg location",

llvm/test/Bitcode/operand-bundles-bc-analyzer.ll

 ; RUN: llvm-as < %s | llvm-bcanalyzer -dump -disable-histogram | FileCheck %s
 
 ; CHECK:  <OPERAND_BUNDLE_TAGS_BLOCK
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
+; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
+; CHECK-NEXT:    <OPERAND_BUNDLE_TAG
 ; CHECK-NEXT:  </OPERAND_BUNDLE_TAGS_BLOCK
 
 ; CHECK:   <FUNCTION_BLOCK
 ; CHECK:    <OPERAND_BUNDLE
 ; CHECK:    <OPERAND_BUNDLE
 ; CHECK-NOT: <OPERAND_BUNDLE
 ; CHECK:  </FUNCTION_BLOCK
 

llvm/test/Verifier/operand-bundles.ll

 
  entry:
   %l = load i32, i32* %ptr
   call void @g() [ "gc-transition"(i32 42, i64 100, i32 %x), "gc-transition"(float 0.0, i64 100, i32 %l) ]
   call void @g() [ "gc-transition"(i32 42, i64 120) ]  ;; The verifier should not complain about this one
   %x = add i32 42, 1
   ret void
 }
+
+declare <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32>, <4 x i32>, i32, i32, i32)
+declare <4 x float> @llvm.matrix.multiply.v4f32.v4f32.v4f32(<4 x float>, <4 x float>, i32, i32, i32)
+
+define void @f_nuw(<4 x i32> %a, i1 %c) {
+entry:
+; CHECK: Multiple nuw operand bundles
+; CHECK-NEXT: %v.1 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 true), "nuw"(i1 true) ]
+  %v.1 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 true), "nuw"(i1 true) ]
+
+; CHECK-NOT: %v.2 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 true) ]
+  %v.2 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 true) ]
+
+; CHECK: nuw bundle operand must be an integer with bitwidth 1
+; CHECK-NEXT: %v.3 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i32 10) ]
+  %v.3 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i32 10) ]
+
+; CHECK: nuw bundle must have a single argument
+; CHECK-NEXT: %v.4 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i32 10, i1 true) ]
+  %v.4 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i32 10, i1 true) ]
+
+; CHECK: nuw bundle operand must be a constant integer
+; CHECK-NEXT: %v.5 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 %c) ]
+  %v.5 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nuw"(i1 %c) ]
+
+; CHECK: nuw/nsw bundles not supported on the called function
+; CHECK-NEXT: call void @g() [ "nuw"(i1 true) ]
+  call void @g( )[ "nuw"(i1 true) ]
+
+; CHECK: nuw/nsw bundles not supported on the called function
+; CHECK-NEXT: %v.6 = call <4 x float> @llvm.matrix.multiply.v4f32.v4f32.v4f32(<4 x float> zeroinitializer, <4 x float> zeroinitializer, i32 2, i32 2, i32 2) [ "nuw"(i1 %c) ]
+  %v.6 = call <4 x float> @llvm.matrix.multiply.v4f32.v4f32.v4f32(<4 x float> zeroinitializer, <4 x float> zeroinitializer, i32 2, i32 2, i32 2) [ "nuw"(i1 %c) ]
+
+  ret void
+}
+
+define void @f_nsw(<4 x i32> %a, i1 %c) {
+entry:
+; CHECK: Multiple nsw operand bundles
+; CHECK-NEXT: %v.1 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 true), "nsw"(i1 true) ]
+  %v.1 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 true), "nsw"(i1 true) ]
+
+; CHECK-NOT: %v.2 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 true) ]
+  %v.2 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 true) ]
+
+; CHECK: nsw bundle operand must be an integer with bitwidth 1
+; CHECK-NEXT: %v.3 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i32 10) ]
+  %v.3 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i32 10) ]
+
+; CHECK: nsw bundle must have a single argument
+; CHECK-NEXT: %v.4 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i32 10, i1 true) ]
+  %v.4 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i32 10, i1 true) ]
+
+; CHECK: nsw bundle operand must be a constant integer
+; CHECK-NEXT: %v.5 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 %c) ]
+  %v.5 = call <4 x i32> @llvm.matrix.multiply.v4i32.v4i32.v4i32(<4 x i32> %a, <4 x i32> %a, i32 2, i32 2, i32 2) [ "nsw"(i1 %c) ]
+
+; CHECK: nuw/nsw bundles not supported on the called function
+; CHECK-NEXT: call void @g() [ "nsw"(i1 true) ]
+  call void @g( )[ "nsw"(i1 true) ]
+
+; CHECK: nuw/nsw bundles not supported on the called function
+; CHECK-NEXT: %v.6 = call <4 x float> @llvm.matrix.multiply.v4f32.v4f32.v4f32(<4 x float> zeroinitializer, <4 x float> zeroinitializer, i32 2, i32 2, i32 2) [ "nsw"(i1 %c) ]
+  %v.6 = call <4 x float> @llvm.matrix.multiply.v4f32.v4f32.v4f32(<4 x float> zeroinitializer, <4 x float> zeroinitializer, i32 2, i32 2, i32 2) [ "nsw"(i1 %c) ]
+
+  ret void
+}