[Strings] Fix effects of string.compare and add fuzzing (#6547)

We added string.compare late in the spec process, and forgot to add effects for it.
Unlike string.eq, it can trap.

Also use makeTrappingRefUse in recent fuzzer string generation places that I
forgot, which should reduce the amount of traps in fuzzer output.

5 files changed, 153 insertions, 45 deletions

diff --git a/src/ir/effects.h b/src/ir/effects.h
index 3ecb54641..ef9aceb37 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -989,7 +989,14 @@ private:
       // traps when an input is null.
       parent.implicitTrap = true;
     }
-    void visitStringEq(StringEq* curr) {}
+    void visitStringEq(StringEq* curr) {
+      if (curr->op == StringEqCompare) {
+        // traps when either input is null.
+        if (curr->left->type.isNullable() || curr->right->type.isNullable()) {
+          parent.implicitTrap = true;
+        }
+      }
+    }
     void visitStringAs(StringAs* curr) {
       // traps when ref is null.
       parent.implicitTrap = true;
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index dc17f7c91..c60744dea 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -327,6 +327,7 @@ private:
   Expression* makeStringNewArray();
   Expression* makeStringNewCodePoint();
   Expression* makeStringConcat();
+  Expression* makeStringEq(Type type);
   Expression* makeStringEncode(Type type);
 
   // Similar to makeBasic/CompoundRef, but indicates that this value will be
@@ -398,7 +399,7 @@ private:
   Nullability getSuperType(Nullability nullability);
   HeapType getSuperType(HeapType type);
   Type getSuperType(Type type);
-  Type getArrayTypeForString();
+  HeapType getArrayTypeForString();
 
   // Utilities
   Name getTargetName(Expression* target);
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 541b58b0f..add0494ea 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1368,7 +1368,8 @@ Expression* TranslateToFuzzReader::_makeConcrete(Type type) {
                 &Self::makeI31Get);
     options.add(FeatureSet::ReferenceTypes | FeatureSet::GC |
                   FeatureSet::Strings,
-                &Self::makeStringEncode);
+                &Self::makeStringEncode,
+                &Self::makeStringEq);
   }
   if (type.isTuple()) {
     options.add(FeatureSet::Multivalue, &Self::makeTupleMake);
@@ -2755,7 +2756,7 @@ Expression* TranslateToFuzzReader::makeCompoundRef(Type type) {
 }
 
 Expression* TranslateToFuzzReader::makeStringNewArray() {
-  auto* array = make(getArrayTypeForString());
+  auto* array = makeTrappingRefUse(getArrayTypeForString());
   auto* start = make(Type::i32);
   auto* end = make(Type::i32);
   return builder.makeStringNew(StringNewWTF16Array, array, start, end, false);
@@ -2812,11 +2813,26 @@ Expression* TranslateToFuzzReader::makeStringConst() {
 }
 
 Expression* TranslateToFuzzReader::makeStringConcat() {
-  auto* left = make(Type(HeapType::string, getNullability()));
-  auto* right = make(Type(HeapType::string, getNullability()));
+  auto* left = makeTrappingRefUse(HeapType::string);
+  auto* right = makeTrappingRefUse(HeapType::string);
   return builder.makeStringConcat(left, right);
 }
 
+Expression* TranslateToFuzzReader::makeStringEq(Type type) {
+  assert(type == Type::i32);
+
+  if (oneIn(2)) {
+    auto* left = make(Type(HeapType::string, getNullability()));
+    auto* right = make(Type(HeapType::string, getNullability()));
+    return builder.makeStringEq(StringEqEqual, left, right);
+  }
+
+  // string.compare may trap if the either input is null.
+  auto* left = makeTrappingRefUse(HeapType::string);
+  auto* right = makeTrappingRefUse(HeapType::string);
+  return builder.makeStringEq(StringEqCompare, left, right);
+}
+
 Expression* TranslateToFuzzReader::makeTrappingRefUse(HeapType type) {
   auto percent = upTo(100);
   // Only give a low probability to emit a nullable reference.
@@ -3920,8 +3936,8 @@ Expression* TranslateToFuzzReader::makeArrayBulkMemoryOp(Type type) {
 Expression* TranslateToFuzzReader::makeStringEncode(Type type) {
   assert(type == Type::i32);
 
-  auto* ref = make(Type(HeapType::string, getNullability()));
-  auto* array = make(getArrayTypeForString());
+  auto* ref = makeTrappingRefUse(HeapType::string);
+  auto* array = makeTrappingRefUse(getArrayTypeForString());
   auto* start = make(Type::i32);
 
   // Only rarely emit without a bounds check, which might trap. See related
@@ -4307,12 +4323,10 @@ Type TranslateToFuzzReader::getSuperType(Type type) {
   return superType;
 }
 
-Type TranslateToFuzzReader::getArrayTypeForString() {
+HeapType TranslateToFuzzReader::getArrayTypeForString() {
   // Emit an array that can be used with JS-style strings, containing 16-bit
   // elements. For now, this must be a mutable type as that is all V8 accepts.
-  auto arrayHeapType = HeapType(Array(Field(Field::PackedType::i16, Mutable)));
-  auto nullability = getNullability();
-  return Type(arrayHeapType, nullability);
+  return HeapType(Array(Field(Field::PackedType::i16, Mutable)));
 }
 
 Name TranslateToFuzzReader::getTargetName(Expression* target) {
diff --git a/test/lit/passes/vacuum-strings.wast b/test/lit/passes/vacuum-strings.wast
new file mode 100644
index 000000000..6925d52e6
--- /dev/null
+++ b/test/lit/passes/vacuum-strings.wast
@@ -0,0 +1,84 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; RUN: wasm-opt %s --vacuum -all -S -o - | filecheck %s
+
+(module
+  ;; CHECK:      (func $compare (type $0)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (string.compare
+  ;; CHECK-NEXT:    (string.const "hello")
+  ;; CHECK-NEXT:    (ref.null none)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (string.compare
+  ;; CHECK-NEXT:    (ref.null none)
+  ;; CHECK-NEXT:    (string.const "world")
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (string.compare
+  ;; CHECK-NEXT:    (ref.null none)
+  ;; CHECK-NEXT:    (ref.null none)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $compare
+    ;; We cannot vacuum away compares that might trap.
+    (drop
+      (string.compare
+        (string.const "hello")
+        (string.const "world")
+      )
+    )
+    (drop
+      (string.compare
+        (string.const "hello")
+        (ref.null none)
+      )
+    )
+    (drop
+      (string.compare
+        (ref.null none)
+        (string.const "world")
+      )
+    )
+    (drop
+      (string.compare
+        (ref.null none)
+        (ref.null none)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $eq (type $0)
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $eq
+    ;; Equals, however, never traps so all these can be removed.
+    (drop
+      (string.eq
+        (string.const "hello")
+        (string.const "world")
+      )
+    )
+    (drop
+      (string.eq
+        (string.const "hello")
+        (ref.null none)
+      )
+    )
+    (drop
+      (string.eq
+        (ref.null none)
+        (string.const "world")
+      )
+    )
+    (drop
+      (string.eq
+        (ref.null none)
+        (ref.null none)
+      )
+    )
+  )
+)
+
diff --git a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
index 648cb053b..20b145a95 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,43 +1,45 @@
 total
- [exports]      : 7       
- [funcs]        : 12      
+ [exports]      : 4       
+ [funcs]        : 6       
  [globals]      : 14      
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 20      
- [table-data]   : 6       
+ [table-data]   : 1       
  [tables]       : 1       
  [tags]         : 1       
- [total]        : 493     
- [vars]         : 31      
- ArrayNew       : 1       
- ArrayNewFixed  : 1       
- Binary         : 61      
- Block          : 59      
- Break          : 2       
- Call           : 29      
- CallRef        : 1       
- Const          : 101     
- Drop           : 10      
+ [total]        : 533     
+ [vars]         : 24      
+ ArrayNew       : 11      
+ ArrayNewFixed  : 2       
+ AtomicFence    : 1       
+ Binary         : 79      
+ Block          : 57      
+ Break          : 6       
+ Call           : 8       
+ Const          : 137     
+ Drop           : 1       
  GlobalGet      : 28      
- GlobalSet      : 26      
- I31Get         : 1       
- If             : 17      
- Load           : 16      
- LocalGet       : 36      
- LocalSet       : 29      
- Loop           : 2       
- Nop            : 5       
+ GlobalSet      : 28      
+ If             : 15      
+ Load           : 17      
+ LocalGet       : 40      
+ LocalSet       : 23      
+ Loop           : 9       
+ Nop            : 4       
  RefAs          : 1       
- RefCast        : 2       
- RefFunc        : 8       
- RefI31         : 4       
- RefNull        : 4       
- Return         : 3       
- SIMDExtract    : 1       
- StringConst    : 1       
- StructNew      : 5       
- TupleExtract   : 1       
- TupleMake      : 7       
- Unary          : 16      
+ RefFunc        : 2       
+ RefI31         : 2       
+ RefIsNull      : 1       
+ RefNull        : 5       
+ Return         : 2       
+ SIMDExtract    : 2       
+ Select         : 1       
+ Store          : 2       
+ StringConst    : 4       
+ StringEq       : 1       
+ StructGet      : 1       
+ StructNew      : 9       
+ TupleMake      : 4       
+ Unary          : 15      
  Unreachable    : 15