[WebAssembly] Add avgr_u intrinsics and require nuw in patterns

[tlively]

Summary

The vector pattern (a + b + 1) / 2 was previously selected to an
avgr_u instruction regardless of nuw flags, but this is incorrect in
the case where either addition may have an unsigned wrap. This CL
changes the existing pattern to require both adds to have nuw flags
and adds builtin functions and intrinsics for the avgr_u instructions
because the corrected pattern is not representable in C.

[merge_guards_bot]

Unit tests: pass. 60989 tests passed, 0 failed and 727 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

clang/include/clang/Basic/BuiltinsWebAssembly.def

 TARGET_BUILTIN(__builtin_wasm_add_saturate_s_i16x8, "V8sV8sV8s", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_add_saturate_u_i16x8, "V8sV8sV8s", "nc", "simd128")
 
 TARGET_BUILTIN(__builtin_wasm_sub_saturate_s_i8x16, "V16cV16cV16c", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_sub_saturate_u_i8x16, "V16cV16cV16c", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_sub_saturate_s_i16x8, "V8sV8sV8s", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_sub_saturate_u_i16x8, "V8sV8sV8s", "nc", "simd128")
 
+TARGET_BUILTIN(__builtin_wasm_avgr_u_i8x16, "V16cV16cV16c", "nc", "unimplemented-simd128")
+TARGET_BUILTIN(__builtin_wasm_avgr_u_i16x8, "V8sV8sV8s", "nc", "unimplemented-simd128")
+
 TARGET_BUILTIN(__builtin_wasm_bitselect, "V4iV4iV4iV4i", "nc", "simd128")
 
 TARGET_BUILTIN(__builtin_wasm_any_true_i8x16, "iV16c", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_any_true_i16x8, "iV8s", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_any_true_i32x4, "iV4i", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_any_true_i64x2, "iV2LLi", "nc", "unimplemented-simd128")
 TARGET_BUILTIN(__builtin_wasm_all_true_i8x16, "iV16c", "nc", "simd128")
 TARGET_BUILTIN(__builtin_wasm_all_true_i16x8, "iV8s", "nc", "simd128")

clang/lib/CodeGen/CGBuiltin.cpp

case WebAssembly::BI__builtin_wasm_sub_saturate_u_i16x8: {
     default:
       llvm_unreachable("unexpected builtin ID");
     }
     Value *LHS = EmitScalarExpr(E->getArg(0));
     Value *RHS = EmitScalarExpr(E->getArg(1));
     Function *Callee = CGM.getIntrinsic(IntNo, ConvertType(E->getType()));
     return Builder.CreateCall(Callee, {LHS, RHS});
   }
+  case WebAssembly::BI__builtin_wasm_avgr_u_i8x16:
+  case WebAssembly::BI__builtin_wasm_avgr_u_i16x8: {
+    Value *LHS = EmitScalarExpr(E->getArg(0));
+    Value *RHS = EmitScalarExpr(E->getArg(1));
+    Function *Callee = CGM.getIntrinsic(Intrinsic::wasm_avgr_unsigned,
+                                        ConvertType(E->getType()));
+    return Builder.CreateCall(Callee, {LHS, RHS});
+  }
   case WebAssembly::BI__builtin_wasm_bitselect: {
     Value *V1 = EmitScalarExpr(E->getArg(0));
     Value *V2 = EmitScalarExpr(E->getArg(1));
     Value *C = EmitScalarExpr(E->getArg(2));
     Function *Callee = CGM.getIntrinsic(Intrinsic::wasm_bitselect,
                                      ConvertType(E->getType()));
     return Builder.CreateCall(Callee, {V1, V2, C});
   }

clang/test/CodeGen/builtins-wasm.c

 typedef unsigned char u8x16 __attribute((vector_size(16)));
 typedef unsigned short u16x8 __attribute((vector_size(16)));
 typedef unsigned int u32x4 __attribute((vector_size(16)));
 typedef unsigned long long u64x2 __attribute((vector_size(16)));
 typedef float f32x4 __attribute((vector_size(16)));
 typedef double f64x2 __attribute((vector_size(16)));
 
 __SIZE_TYPE__ memory_size(void) {
   return __builtin_wasm_memory_size(0);
   // WEBASSEMBLY32: call {{i.*}} @llvm.wasm.memory.size.i32(i32 0)
   // WEBASSEMBLY64: call {{i.*}} @llvm.wasm.memory.size.i64(i32 0)
 }
 
 __SIZE_TYPE__ memory_grow(__SIZE_TYPE__ delta) {
   return __builtin_wasm_memory_grow(0, delta);
   // WEBASSEMBLY32: call i32 @llvm.wasm.memory.grow.i32(i32 0, i32 %{{.*}})
   // WEBASSEMBLY64: call i64 @llvm.wasm.memory.grow.i64(i32 0, i64 %{{.*}})
 }
 
 void memory_init(void *dest, int offset, int size) {
   __builtin_wasm_memory_init(3, 0, dest, offset, size);
   // WEBASSEMBLY32: call void @llvm.wasm.memory.init(i32 3, i32 0, i8* %{{.*}}, i32 %{{.*}}, i32 %{{.*}})
   // WEBASSEMBLY64: call void @llvm.wasm.memory.init(i32 3, i32 0, i8* %{{.*}}, i32 %{{.*}}, i32 %{{.*}})
 }
 
 void data_drop() {
   __builtin_wasm_data_drop(3);
   // WEBASSEMBLY32: call void @llvm.wasm.data.drop(i32 3)
   // WEBASSEMBLY64: call void @llvm.wasm.data.drop(i32 3)
 }
 
 __SIZE_TYPE__ tls_size() {
   return __builtin_wasm_tls_size();
   // WEBASSEMBLY32: call i32 @llvm.wasm.tls.size.i32()
   // WEBASSEMBLY64: call i64 @llvm.wasm.tls.size.i64()
 }
 
 __SIZE_TYPE__ tls_align() {
   return __builtin_wasm_tls_align();
   // WEBASSEMBLY32: call i32 @llvm.wasm.tls.align.i32()
   // WEBASSEMBLY64: call i64 @llvm.wasm.tls.align.i64()
 }
 
 void *tls_base() {
   return __builtin_wasm_tls_base();
   // WEBASSEMBLY: call i8* @llvm.wasm.tls.base()
 }
 
 void throw(void *obj) {
   return __builtin_wasm_throw(0, obj);
   // WEBASSEMBLY32: call void @llvm.wasm.throw(i32 0, i8* %{{.*}})
   // WEBASSEMBLY64: call void @llvm.wasm.throw(i32 0, i8* %{{.*}})
 }
 
 void rethrow_in_catch(void) {
   return __builtin_wasm_rethrow_in_catch();
   // WEBASSEMBLY32: call void @llvm.wasm.rethrow.in.catch()
   // WEBASSEMBLY64: call void @llvm.wasm.rethrow.in.catch()
 }
 
 int atomic_wait_i32(int *addr, int expected, long long timeout) {
   return __builtin_wasm_atomic_wait_i32(addr, expected, timeout);
   // WEBASSEMBLY32: call i32 @llvm.wasm.atomic.wait.i32(i32* %{{.*}}, i32 %{{.*}}, i64 %{{.*}})
   // WEBASSEMBLY64: call i32 @llvm.wasm.atomic.wait.i32(i32* %{{.*}}, i32 %{{.*}}, i64 %{{.*}})
 }
 
 int atomic_wait_i64(long long *addr, long long expected, long long timeout) {
   return __builtin_wasm_atomic_wait_i64(addr, expected, timeout);
   // WEBASSEMBLY32: call i32 @llvm.wasm.atomic.wait.i64(i64* %{{.*}}, i64 %{{.*}}, i64 %{{.*}})
   // WEBASSEMBLY64: call i32 @llvm.wasm.atomic.wait.i64(i64* %{{.*}}, i64 %{{.*}}, i64 %{{.*}})
 }
 
 unsigned int atomic_notify(int *addr, unsigned int count) {
   return __builtin_wasm_atomic_notify(addr, count);
   // WEBASSEMBLY32: call i32 @llvm.wasm.atomic.notify(i32* %{{.*}}, i32 %{{.*}})
   // WEBASSEMBLY64: call i32 @llvm.wasm.atomic.notify(i32* %{{.*}}, i32 %{{.*}})
 }
 
 int trunc_s_i32_f32(float f) {
   return __builtin_wasm_trunc_s_i32_f32(f);
   // WEBASSEMBLY: call i32 @llvm.wasm.trunc.signed.i32.f32(float %f)
   // WEBASSEMBLY-NEXT: ret
 }
 
 int trunc_u_i32_f32(float f) {
   return __builtin_wasm_trunc_u_i32_f32(f);
   // WEBASSEMBLY: call i32 @llvm.wasm.trunc.unsigned.i32.f32(float %f)
   // WEBASSEMBLY-NEXT: ret
 }
 
 int trunc_s_i32_f64(double f) {
   return __builtin_wasm_trunc_s_i32_f64(f);
   // WEBASSEMBLY: call i32 @llvm.wasm.trunc.signed.i32.f64(double %f)
   // WEBASSEMBLY-NEXT: ret
 }
 
 int trunc_u_i32_f64(double f) {
   return __builtin_wasm_trunc_u_i32_f64(f);
   // WEBASSEMBLY: call i32 @llvm.wasm.trunc.unsigned.i32.f64(double %f)
   // WEBASSEMBLY-NEXT: ret
 }
 
 long long trunc_s_i64_f32(float f) {
   return __builtin_wasm_trunc_s_i64_f32(f);
   // WEBASSEMBLY: call i64 @llvm.wasm.trunc.signed.i64.f32(float %f)
   // WEBASSEMBLY-NEXT: ret
 }
 
 long long trunc_u_i64_f32(float f) {
   return __builtin_wasm_trunc_u_i64_f32(f);
   // WEBASSEMBLY: call i64 @llvm.wasm.trunc.unsigned.i64.f32(float %f)
   // WEBASSEMBLY-NEXT: ret

 
 i16x8 sub_saturate_u_i16x8(i16x8 x, i16x8 y) {
   return __builtin_wasm_sub_saturate_u_i16x8(x, y);
   // WEBASSEMBLY: call <8 x i16> @llvm.wasm.sub.saturate.unsigned.v8i16(
   // WEBASSEMBLY-SAME: <8 x i16> %x, <8 x i16> %y)
   // WEBASSEMBLY-NEXT: ret
 }
 
+i8x16 avgr_u_i8x16(i8x16 x, i8x16 y) {
+  return __builtin_wasm_avgr_u_i8x16(x, y);
+  // WEBASSEMBLY: call <16 x i8> @llvm.wasm.avgr.unsigned.v16i8(
+  // WEBASSEMBLY-SAME: <16 x i8> %x, <16 x i8> %y)
+  // WEBASSEMBLY-NEXT: ret
+}
+
+i16x8 avgr_u_i16x8(i16x8 x, i16x8 y) {
+  return __builtin_wasm_avgr_u_i16x8(x, y);
+  // WEBASSEMBLY: call <8 x i16> @llvm.wasm.avgr.unsigned.v8i16(
+  // WEBASSEMBLY-SAME: <8 x i16> %x, <8 x i16> %y)
+  // WEBASSEMBLY-NEXT: ret
+}
+
 i32x4 dot_i16x8_s(i16x8 x, i16x8 y) {
   return __builtin_wasm_dot_s_i32x4_i16x8(x, y);
   // WEBASSEMBLY: call <4 x i32> @llvm.wasm.dot(<8 x i16> %x, <8 x i16> %y)
   // WEBASSEMBLY-NEXT: ret
 }
 
 i32x4 bitselect(i32x4 x, i32x4 y, i32x4 c) {
   return __builtin_wasm_bitselect(x, y, c);

llvm/include/llvm/IR/IntrinsicsWebAssembly.td

 def int_wasm_sub_saturate_signed :
   Intrinsic<[llvm_anyvector_ty],
             [LLVMMatchType<0>, LLVMMatchType<0>],
             [IntrNoMem, IntrSpeculatable]>;
 def int_wasm_sub_saturate_unsigned :
   Intrinsic<[llvm_anyvector_ty],
             [LLVMMatchType<0>, LLVMMatchType<0>],
             [IntrNoMem, IntrSpeculatable]>;
+def int_wasm_avgr_unsigned :
+  Intrinsic<[llvm_anyvector_ty],
+            [LLVMMatchType<0>, LLVMMatchType<0>],
+            [IntrNoMem, IntrSpeculatable]>;
 
 def int_wasm_bitselect :
   Intrinsic<[llvm_anyvector_ty],
             [LLVMMatchType<0>, LLVMMatchType<0>, LLVMMatchType<0>],
             [IntrNoMem, IntrSpeculatable]>;
 def int_wasm_anytrue :
   Intrinsic<[llvm_i32_ty],
             [llvm_anyvector_ty],

llvm/lib/Target/WebAssembly/WebAssemblyInstrSIMD.td

 let isCommutable = 1 in {
 defm MIN_S : SIMDBinaryIntNoI64x2<smin, "min_s", 94>;
 defm MIN_U : SIMDBinaryIntNoI64x2<umin, "min_u", 95>;
 defm MAX_S : SIMDBinaryIntNoI64x2<smax, "max_s", 96>;
 defm MAX_U : SIMDBinaryIntNoI64x2<umax, "max_u", 97>;
 } // isCommutable = 1
 
 // Integer unsigned rounding average: avgr_u
-def avgr_u_v16i8 :
-  PatFrag<(ops node:$lhs, node:$rhs),
-          (srl
-            (add (add node:$lhs, node:$rhs), (splat16 (i32 1))),
-            (v16i8 (splat16 (i32 1)))
-          )>;
-def avgr_u_v8i16 :
-  PatFrag<(ops node:$lhs, node:$rhs),
-          (srl
-            (add (add node:$lhs, node:$rhs), (splat8 (i32 1))),
-            (v8i16 (splat8 (i32 1)))
-          )>;
-
 let isCommutable = 1, Predicates = [HasUnimplementedSIMD128] in {
-defm AVGR_U : SIMDBinary<v16i8, "i8x16", avgr_u_v16i8, "avgr_u", 217>;
-defm AVGR_U : SIMDBinary<v8i16, "i16x8", avgr_u_v8i16, "avgr_u", 218>;
+defm AVGR_U : SIMDBinary<v16i8, "i8x16", int_wasm_avgr_unsigned, "avgr_u", 217>;
+defm AVGR_U : SIMDBinary<v8i16, "i16x8", int_wasm_avgr_unsigned, "avgr_u", 218>;
 }
 
+def add_nuw : PatFrag<(ops node:$lhs, node:$rhs),
+                      (add node:$lhs, node:$rhs),
+                      "return N->getFlags().hasNoUnsignedWrap();">;
+
+foreach nodes = [[v16i8, splat16], [v8i16, splat8]] in
+def : Pat<(srl
+            (add_nuw
+              (add_nuw (nodes[0] V128:$lhs), (nodes[0] V128:$rhs)),
+              (nodes[1] (i32 1))
+            ),
+            (nodes[0] (nodes[1] (i32 1)))
+          ),
+          (!cast<NI>("AVGR_U_"#nodes[0]) V128:$lhs, V128:$rhs)>;
+
 // Widening dot product: i32x4.dot_i16x8_s
 let isCommutable = 1 in
 defm DOT : SIMD_I<(outs V128:$dst), (ins V128:$lhs, V128:$rhs), (outs), (ins),
                   [(set V128:$dst, (int_wasm_dot V128:$lhs, V128:$rhs))],
                   "i32x4.dot_i16x8_s\t$dst, $lhs, $rhs", "i32x4.dot_i16x8_s",
                   219>;
 
 //===----------------------------------------------------------------------===//

llvm/test/CodeGen/WebAssembly/simd-arith.ll

 }
 
 ; CHECK-LABEL: avgr_u_v16i8:
 ; NO-SIMD128-NOT: i8x16
 ; SIMD128-NEXT: .functype avgr_u_v16i8 (v128, v128) -> (v128){{$}}
 ; SIMD128-NEXT: i8x16.avgr_u $push[[R:[0-9]+]]=, $0, $1{{$}}
 ; SIMD128-NEXT: return $pop[[R]]{{$}}
 define <16 x i8> @avgr_u_v16i8(<16 x i8> %x, <16 x i8> %y) {
+  %a = add nuw <16 x i8> %x, %y
+  %b = add nuw <16 x i8> %a, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1,
+                              i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
+  %c = udiv <16 x i8> %b, <i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2,
+                           i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2>
+  ret <16 x i8> %c
+}
+
+; CHECK-LABEL: avgr_u_v16i8_wrap:
+; NO-SIMD128-NOT: i8x16
+; SIMD128-NEXT: .functype avgr_u_v16i8_wrap (v128, v128) -> (v128){{$}}
+; SIMD128-NOT: i8x16.avgr_u
+define <16 x i8> @avgr_u_v16i8_wrap(<16 x i8> %x, <16 x i8> %y) {
   %a = add <16 x i8> %x, %y
   %b = add <16 x i8> %a, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1,
                           i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
   %c = udiv <16 x i8> %b, <i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2,
                            i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2>
   ret <16 x i8> %c
 }
 

 }
 
 ; CHECK-LABEL: avgr_u_v8i16:
 ; NO-SIMD128-NOT: i16x8
 ; SIMD128-NEXT: .functype avgr_u_v8i16 (v128, v128) -> (v128){{$}}
 ; SIMD128-NEXT: i16x8.avgr_u $push[[R:[0-9]+]]=, $0, $1{{$}}
 ; SIMD128-NEXT: return $pop[[R]]{{$}}
 define <8 x i16> @avgr_u_v8i16(<8 x i16> %x, <8 x i16> %y) {
+  %a = add nuw <8 x i16> %x, %y
+  %b = add nuw <8 x i16> %a, <i16 1, i16 1, i16 1, i16 1, i16 1, i16 1, i16 1, i16 1>
+  %c = udiv <8 x i16> %b, <i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2>
+  ret <8 x i16> %c
+}
+
+; CHECK-LABEL: avgr_u_v8i16_wrap:
+; NO-SIMD128-NOT: i16x8
+; SIMD128-NEXT: .functype avgr_u_v8i16_wrap (v128, v128) -> (v128){{$}}
+; SIMD128-NOT: i16x8.avgr_u
+define <8 x i16> @avgr_u_v8i16_wrap(<8 x i16> %x, <8 x i16> %y) {
   %a = add <8 x i16> %x, %y
   %b = add <8 x i16> %a, <i16 1, i16 1, i16 1, i16 1, i16 1, i16 1, i16 1, i16 1>
   %c = udiv <8 x i16> %b, <i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2, i16 2>
   ret <8 x i16> %c
 }
 
 ; CHECK-LABEL: neg_v8i16:
 ; NO-SIMD128-NOT: i16x8

llvm/test/CodeGen/WebAssembly/simd-intrinsics.ll

 declare <16 x i8> @llvm.wasm.sub.saturate.unsigned.v16i8(<16 x i8>, <16 x i8>)
 define <16 x i8> @sub_sat_u_v16i8(<16 x i8> %x, <16 x i8> %y) {
   %a = call <16 x i8> @llvm.wasm.sub.saturate.unsigned.v16i8(
     <16 x i8> %x, <16 x i8> %y
   )
   ret <16 x i8> %a
 }
 
+; CHECK-LABEL: avgr_u_v16i8:
+; SIMD128-NEXT: .functype avgr_u_v16i8 (v128, v128) -> (v128){{$}}
+; SIMD128-NEXT: i8x16.avgr_u $push[[R:[0-9]+]]=, $0, $1{{$}}
+; SIMD128-NEXT: return $pop[[R]]{{$}}
+declare <16 x i8> @llvm.wasm.avgr.unsigned.v16i8(<16 x i8>, <16 x i8>)
+define <16 x i8> @avgr_u_v16i8(<16 x i8> %x, <16 x i8> %y) {
+  %a = call <16 x i8> @llvm.wasm.avgr.unsigned.v16i8(<16 x i8> %x, <16 x i8> %y)
+  ret <16 x i8> %a
+}
+
 ; CHECK-LABEL: any_v16i8:
 ; SIMD128-NEXT: .functype any_v16i8 (v128) -> (i32){{$}}
 ; SIMD128-NEXT: i8x16.any_true $push[[R:[0-9]+]]=, $0{{$}}
 ; SIMD128-NEXT: return $pop[[R]]{{$}}
 declare i32 @llvm.wasm.anytrue.v16i8(<16 x i8>)
 define i32 @any_v16i8(<16 x i8> %x) {
   %a = call i32 @llvm.wasm.anytrue.v16i8(<16 x i8> %x)
   ret i32 %a

 declare <8 x i16> @llvm.wasm.sub.saturate.unsigned.v8i16(<8 x i16>, <8 x i16>)
 define <8 x i16> @sub_sat_u_v8i16(<8 x i16> %x, <8 x i16> %y) {
   %a = call <8 x i16> @llvm.wasm.sub.saturate.unsigned.v8i16(
     <8 x i16> %x, <8 x i16> %y
   )
   ret <8 x i16> %a
 }
 
+; CHECK-LABEL: avgr_u_v8i16:
+; SIMD128-NEXT: .functype avgr_u_v8i16 (v128, v128) -> (v128){{$}}
+; SIMD128-NEXT: i16x8.avgr_u $push[[R:[0-9]+]]=, $0, $1{{$}}
+; SIMD128-NEXT: return $pop[[R]]{{$}}
+declare <8 x i16> @llvm.wasm.avgr.unsigned.v8i16(<8 x i16>, <8 x i16>)
+define <8 x i16> @avgr_u_v8i16(<8 x i16> %x, <8 x i16> %y) {
+  %a = call <8 x i16> @llvm.wasm.avgr.unsigned.v8i16(<8 x i16> %x, <8 x i16> %y)
+  ret <8 x i16> %a
+}
+
 ; CHECK-LABEL: any_v8i16:
 ; SIMD128-NEXT: .functype any_v8i16 (v128) -> (i32){{$}}
 ; SIMD128-NEXT: i16x8.any_true $push[[R:[0-9]+]]=, $0{{$}}
 ; SIMD128-NEXT: return $pop[[R]]{{$}}
 declare i32 @llvm.wasm.anytrue.v8i16(<8 x i16>)
 define i32 @any_v8i16(<8 x i16> %x) {
   %a = call i32 @llvm.wasm.anytrue.v8i16(<8 x i16> %x)
   ret i32 %a