[IR] Add NoUndef attribute to Intrinsics.td

[aqjune]

Summary

This patch adds NoUndef to Intrinsics.td.
The attribute is attached to llvm.assume's operand, because llvm.assume(undef)
is UB.
It is attached to pointer operands of several memory accessing intrinsics
as well.

This change makes ValueTracking::getGuaranteedNonPoisonOps' intrinsic check
unnecessary, so it is removed.

[jdoerfert]

llvm/include/llvm/IR/Intrinsics.td

557

This is the old nonnull discussion all over again. I don't think you can do this here. Do it when we know the size is not 0. Same below.

[aqjune]

Exclude memset/memcpy/memmove

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

557

I think we can make it more explicit by updating LangRef and saying that undef or poison can be given when the size is zero. I'll make a patch for that.

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

557

I became to think that it has to be UB, because it makes expanding memset/memcpy to a loop unsound. For example:

memset(p, 255, 0)
->
q = p+0
while (p != q) { *p = 255; ++p; }

If p is undef/poison, p != q is also undef/poison, so the target has branch on undef/poison, which is UB.
In order to support this, memset(undef, 255, 0) should be UB too. LowerMemIntrinsics.cpp does this transformation.

This does not happen when p was null or dangling pointer (which is weaker than undef/poison); pointer comparison does not produce poison in these case.
The original thread http://lists.llvm.org/pipermail/llvm-dev/2017-July/115665.html states the cases that are only about null/dangling pointers.

I'll see whether it is okay to be UB by running Alive2.

[jdoerfert]

llvm/include/llvm/IR/Intrinsics.td

557

I am hesitant to argue there is an implementation for which this is UB so we make it UB.

memset(p, c, size) {
  while (size > 0) {
    p[size--] = c;
  }
}

is UB free for size 0.

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

557

Found that actually LowerMemIntrinsics.cpp was also checking the size rather than comparing & incrementing pointers (llvm/test/CodeGen/NVPTX/lower-aggr-copies.ll ) . So it was UB-safe.
Though, I wonder why it isn't directly emitting the increment-of-pointer version, which seems to be more efficient. Another concern is the safety of LSR that seems to be related with this as well.

I'm fine with removing noundef from memset/cpy/move (which is the current version).

[aqjune]

Made a LangRef patch for memset/cpy/move: D86643

[jdoerfert]

LGTM. Maybe add a test for noundef on the assume arg as well.

[efriedma]

llvm/include/llvm/IR/Intrinsics.td

1353

Do masked load/store/gather/scatter have the same problem as memcpy/memmove? In particular, it seems a bit weird that a masked store with an all-false mask has undefined behavior if the pointer argument is undef.

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

1353

In case of masked store/load, I followed Memory sanitizer's behavior.
MemorySanitizerVisitor's handleMaskedStore and handleMaskedLoad calls insertShadowCheck for the pointer, which checks whether the pointer is undefined IIUC.
The same thing happens for normal load/stores, but not for memcpy/memset.

[efriedma]

llvm/include/llvm/IR/Intrinsics.td

1353

I suspect msan's behavior isn't what we want; a completely masked load/store is sort of an edge case, though.

I'm more concerned about gather/scatter; it's much more likely we'll end up with undef vector lanes there.

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

1353

For gather/scatter, I agree the pointer vector may contain undef elements.
Maybe it was a bit naive to add noundefs to them. To be conservative, I'll make a patch that removes noundefs from these masked intrinsics.

[aqjune]

llvm/include/llvm/IR/Intrinsics.td

1353

(being conservative means that masked_load and masked_store are to be updated as well.)

llvm/include/llvm/IR/Intrinsics.td

 }
 
 // NoAlias - The specified argument pointer is not aliasing other "noalias" pointer
 // arguments of the intrinsic wrt. the intrinsic scope.
 class NoAlias<AttrIndex idx> : IntrinsicProperty {
   int ArgNo = idx.Value;
 }
 
+// NoUndef - The specified argument is neither undef nor poison.
+class NoUndef<AttrIndex idx> : IntrinsicProperty {
+  int ArgNo = idx.Value;
+}
+
 class Align<AttrIndex idx, int align> : IntrinsicProperty {
   int ArgNo = idx.Value;
   int Align = align;
 }
 
 // Returned - The specified argument is always the return value of the
 // intrinsic.
 class Returned<AttrIndex idx> : IntrinsicProperty {
: Intrinsic<[], [ llvm_anyptr_ty, llvm_i32_ty, llvm_i32_ty, llvm_i32_ty ],
                  ReadOnly<ArgIndex<0>>, NoCapture<ArgIndex<0>>,
                  ImmArg<ArgIndex<1>>, ImmArg<ArgIndex<2>>]>;
 def int_pcmarker      : Intrinsic<[], [llvm_i32_ty]>;
 
 def int_readcyclecounter : Intrinsic<[llvm_i64_ty]>;
 
 // The assume intrinsic is marked as arbitrarily writing so that proper
 // control dependencies will be maintained.
-def int_assume        : Intrinsic<[], [llvm_i1_ty], [IntrWillReturn]>;
+def int_assume        : Intrinsic<[], [llvm_i1_ty], [IntrWillReturn,
+                                                     NoUndef<ArgIndex<0>>]>;
 
 // Stack Protector Intrinsic - The stackprotector intrinsic writes the stack
 // guard to the correct place on the stack frame.
 def int_stackprotector : Intrinsic<[], [llvm_ptr_ty, llvm_ptrptr_ty], []>;
 def int_stackguard : Intrinsic<[llvm_ptr_ty], [], []>;
 
 // A counter increment for instrumentation based profiling.
 def int_instrprof_increment : Intrinsic<[],

 //
 
 def int_memcpy  : Intrinsic<[],
                             [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty,
                              llvm_i1_ty],
                             [IntrArgMemOnly, IntrWillReturn,
                              NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
                              NoAlias<ArgIndex<0>>, NoAlias<ArgIndex<1>>,
+                             NoUndef<ArgIndex<0>>, NoUndef<ArgIndex<1>>,
                              WriteOnly<ArgIndex<0>>, ReadOnly<ArgIndex<1>>,
                              ImmArg<ArgIndex<3>>]>;
 
 // Memcpy semantic that is guaranteed to be inlined.
 // In particular this means that the generated code is not allowed to call any
 // external function.
 // The third argument (specifying the size) must be a constant.
 def int_memcpy_inline
     : Intrinsic<[],
       [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty, llvm_i1_ty],
       [IntrArgMemOnly, IntrWillReturn,
        NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
        NoAlias<ArgIndex<0>>, NoAlias<ArgIndex<1>>,
+       NoUndef<ArgIndex<0>>, NoUndef<ArgIndex<1>>,
        WriteOnly<ArgIndex<0>>, ReadOnly<ArgIndex<1>>,
        ImmArg<ArgIndex<2>>, ImmArg<ArgIndex<3>>]>;
 
 def int_memmove : Intrinsic<[],
                             [llvm_anyptr_ty, llvm_anyptr_ty, llvm_anyint_ty,
                              llvm_i1_ty],
                             [IntrArgMemOnly, IntrWillReturn,
                              NoCapture<ArgIndex<0>>, NoCapture<ArgIndex<1>>,
+                             NoUndef<ArgIndex<0>>, NoUndef<ArgIndex<1>>,
                              ReadOnly<ArgIndex<1>>, ImmArg<ArgIndex<3>>]>;
 def int_memset  : Intrinsic<[],
                             [llvm_anyptr_ty, llvm_i8_ty, llvm_anyint_ty,
                              llvm_i1_ty],
                             [IntrWriteMem, IntrArgMemOnly, IntrWillReturn,
-                             NoCapture<ArgIndex<0>>, WriteOnly<ArgIndex<0>>,
-                             ImmArg<ArgIndex<3>>]>;
+                             NoCapture<ArgIndex<0>>, NoUndef<ArgIndex<0>>,
+                             WriteOnly<ArgIndex<0>>, ImmArg<ArgIndex<3>>]>;
 
 // FIXME: Add version of these floating point intrinsics which allow non-default
 // rounding modes and FP exception handling.
 
 let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn] in {
   def int_fma  : Intrinsic<[llvm_anyfloat_ty],
                            [LLVMMatchType<0>, LLVMMatchType<0>,
                             LLVMMatchType<0>]>;
Intrinsic<[llvm_anyvector_ty],
             [IntrNoMem, IntrNoSync, IntrWillReturn]>;
 
 //===-------------------------- Masked Intrinsics -------------------------===//
 //
 def int_masked_store : Intrinsic<[], [llvm_anyvector_ty,
                                       LLVMAnyPointerType<LLVMMatchType<0>>,
                                       llvm_i32_ty,
                                       LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>],
-                                 [IntrArgMemOnly, IntrWillReturn, ImmArg<ArgIndex<2>>]>;
+                                 [IntrArgMemOnly, IntrWillReturn,
+                                  NoUndef<ArgIndex<1>>, ImmArg<ArgIndex<2>>]>;
 
 def int_masked_load  : Intrinsic<[llvm_anyvector_ty],
                                  [LLVMAnyPointerType<LLVMMatchType<0>>, llvm_i32_ty,
                                   LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>, LLVMMatchType<0>],
                                  [IntrReadMem, IntrArgMemOnly, IntrWillReturn,
-                                  ImmArg<ArgIndex<1>>]>;
+                                  NoUndef<ArgIndex<0>>, ImmArg<ArgIndex<1>>]>;
 
 def int_masked_gather: Intrinsic<[llvm_anyvector_ty],
                                  [LLVMVectorOfAnyPointersToElt<0>, llvm_i32_ty,
                                   LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>,
                                   LLVMMatchType<0>],
                                  [IntrReadMem, IntrWillReturn,
-                                  ImmArg<ArgIndex<1>>]>;
+                                  NoUndef<ArgIndex<0>>, ImmArg<ArgIndex<1>>]>;
 
 def int_masked_scatter: Intrinsic<[],
                                   [llvm_anyvector_ty,
                                    LLVMVectorOfAnyPointersToElt<0>, llvm_i32_ty,
                                    LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>],
-                                  [IntrWillReturn, ImmArg<ArgIndex<2>>]>;
+                                  [IntrWillReturn, NoUndef<ArgIndex<1>>,
+                                   ImmArg<ArgIndex<2>>]>;
 
 def int_masked_expandload: Intrinsic<[llvm_anyvector_ty],
                                      [LLVMPointerToElt<0>,
                                       LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>,
                                       LLVMMatchType<0>],
                                      [IntrReadMem, IntrWillReturn]>;
 
 def int_masked_compressstore: Intrinsic<[],

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
switch (I->getOpcode()) {
     case Instruction::SDiv:
     case Instruction::URem:
     case Instruction::SRem:
       Operands.insert(I->getOperand(1));
       break;
 
     case Instruction::Call:
     case Instruction::Invoke: {
-      if (auto *II = dyn_cast<IntrinsicInst>(I)) {
-        switch (II->getIntrinsicID()) {
-        case Intrinsic::assume:
-          Operands.insert(II->getArgOperand(0));
-          break;
-        default:
-          break;
-        }
-      }
-
       const CallBase *CB = cast<CallBase>(I);
       if (CB->isIndirectCall())
         Operands.insert(CB->getCalledOperand());
       for (unsigned i = 0; i < CB->arg_size(); ++i) {
         if (CB->paramHasAttr(i, Attribute::NoUndef))
           Operands.insert(CB->getArgOperand(i));
       }
       break;

llvm/test/Bitcode/upgrade-memory-intrinsics.ll

 ; CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p1, i8* %p2, i64 50, i1 false)
 ; CHECK: call void @llvm.memmove.p0i8.p0i8.i64(i8* %p2, i8* %p3, i64 1000, i1 false)
   call void @llvm.memset.p0i8.i64(i8* %p1, i8 55, i64 100, i32 0, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p1, i8* %p2, i64 50, i32 0, i1 false)
   call void @llvm.memmove.p0i8.p0i8.i64(i8* %p2, i8* %p3, i64 1000, i32 0, i1 false)
   ret void
 }
 
-; CHECK: declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg)
-; CHECK: declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
-; CHECK: declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i1 immarg)
+; CHECK: declare void @llvm.memset.p0i8.i64(i8* nocapture noundef writeonly, i8, i64, i1 immarg)
+; CHECK: declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture noundef writeonly, i8* noalias nocapture noundef readonly, i64, i1 immarg)
+; CHECK: declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture noundef, i8* nocapture noundef readonly, i64, i1 immarg)
 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly , i8* nocapture readonly, i64, i32, i1)
 declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1)
 

llvm/test/Transforms/Attributor/norecurse.ll

 ; CHECK: Function Attrs
 ; CHECK-NEXT: declare i32 @k()
 declare i32 @k() readnone
 
 define void @intrinsic(i8* %dest, i8* %src, i32 %len) {
 ; CHECK: Function Attrs: argmemonly nosync nounwind willreturn
 ; CHECK-LABEL: define {{[^@]+}}@intrinsic
 ; CHECK-SAME: (i8* nocapture writeonly [[DEST:%.*]], i8* nocapture readonly [[SRC:%.*]], i32 [[LEN:%.*]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* noalias nocapture writeonly [[DEST]], i8* noalias nocapture readonly [[SRC]], i32 [[LEN]], i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* noalias nocapture noundef writeonly [[DEST]], i8* noalias nocapture noundef readonly [[SRC]], i32 [[LEN]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 false)
   ret void
 }
 
 ; CHECK: Function Attrs
 ; CHECK-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32

llvm/test/Transforms/Attributor/nosync.ll

 ; TEST 14 - negative, checking volatile intrinsics.
 
 ; It is odd to add nocapture but a result of the llvm.memcpy nocapture.
 ;
 define i32 @memcpy_volatile(i8* %ptr1, i8* %ptr2) {
 ; CHECK: Function Attrs: argmemonly nounwind willreturn
 ; CHECK-LABEL: define {{[^@]+}}@memcpy_volatile
 ; CHECK-SAME: (i8* nocapture writeonly [[PTR1:%.*]], i8* nocapture readonly [[PTR2:%.*]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* noalias nocapture writeonly [[PTR1]], i8* noalias nocapture readonly [[PTR2]], i32 8, i1 true)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i32(i8* noalias nocapture noundef writeonly [[PTR1]], i8* noalias nocapture noundef readonly [[PTR2]], i32 8, i1 true)
 ; CHECK-NEXT:    ret i32 4
 ;
   call void @llvm.memcpy(i8* %ptr1, i8* %ptr2, i32 8, i1 1)
   ret i32 4
 }
 
 ; TEST 15 - positive, non-volatile intrinsic.
 
 ; It is odd to add nocapture but a result of the llvm.memset nocapture.
 ;
 define i32 @memset_non_volatile(i8* %ptr1, i8 %val) {
 ; CHECK: Function Attrs: argmemonly nosync nounwind willreturn writeonly
 ; CHECK-LABEL: define {{[^@]+}}@memset_non_volatile
 ; CHECK-SAME: (i8* nocapture writeonly [[PTR1:%.*]], i8 [[VAL:%.*]])
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* nocapture writeonly [[PTR1]], i8 [[VAL]], i32 8, i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i32(i8* nocapture noundef writeonly [[PTR1]], i8 [[VAL]], i32 8, i1 false)
 ; CHECK-NEXT:    ret i32 4
 ;
   call void @llvm.memset(i8* %ptr1, i8 %val, i32 8, i1 0)
   ret i32 4
 }
 
 ; TEST 16 - negative, inline assembly.
 

llvm/utils/TableGen/CodeGenIntrinsics.h

 //===- CodeGenIntrinsic.h - Intrinsic Class Wrapper ------------*- C++ -*--===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
struct CodeGenIntrinsic {
   bool hasSideEffects;
 
   // True if the intrinsic is marked as speculatable.
   bool isSpeculatable;
 
   enum ArgAttrKind {
     NoCapture,
     NoAlias,
+    NoUndef,
     Returned,
     ReadOnly,
     WriteOnly,
     ReadNone,
     ImmArg,
     Alignment
   };
 

llvm/utils/TableGen/CodeGenTarget.cpp

 //===- CodeGenTarget.cpp - CodeGen Target Class Wrapper -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
for (unsigned i = 0, e = PropList->size(); i != e; ++i) {
     else if (Property->getName() == "IntrHasSideEffects")
       hasSideEffects = true;
     else if (Property->isSubClassOf("NoCapture")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");
       ArgumentAttributes.emplace_back(ArgNo, NoCapture, 0);
     } else if (Property->isSubClassOf("NoAlias")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");
       ArgumentAttributes.emplace_back(ArgNo, NoAlias, 0);
+    } else if (Property->isSubClassOf("NoUndef")) {
+      unsigned ArgNo = Property->getValueAsInt("ArgNo");
+      ArgumentAttributes.emplace_back(ArgNo, NoUndef, 0);
     } else if (Property->isSubClassOf("Returned")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");
       ArgumentAttributes.emplace_back(ArgNo, Returned, 0);
     } else if (Property->isSubClassOf("ReadOnly")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");
       ArgumentAttributes.emplace_back(ArgNo, ReadOnly, 0);
     } else if (Property->isSubClassOf("WriteOnly")) {
       unsigned ArgNo = Property->getValueAsInt("ArgNo");

llvm/utils/TableGen/IntrinsicEmitter.cpp

 //===- IntrinsicEmitter.cpp - Generate intrinsic information --------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (ae) {
             addComma = true;
             break;
           case CodeGenIntrinsic::NoAlias:
             if (addComma)
               OS << ",";
             OS << "Attribute::NoAlias";
             addComma = true;
             break;
+          case CodeGenIntrinsic::NoUndef:
+            if (addComma)
+              OS << ",";
+            OS << "Attribute::NoUndef";
+            addComma = true;
+            break;
           case CodeGenIntrinsic::Returned:
             if (addComma)
               OS << ",";
             OS << "Attribute::Returned";
             addComma = true;
             break;
           case CodeGenIntrinsic::ReadOnly:
             if (addComma)