Fuzzer: Pick interesting subtypes in getSubType(HeapType) (#5573)

3 files changed, 73 insertions, 38 deletions

diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index 4eb0c3960..d761bc3bd 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -112,6 +112,10 @@ private:
   // The heap types we can pick from to generate instructions.
   std::vector<HeapType> interestingHeapTypes;
 
+  // A mapping of a heap type to the subset of interestingHeapTypes that are
+  // subtypes of it.
+  std::unordered_map<HeapType, std::vector<HeapType>> interestingHeapSubTypes;
+
   Index numAddedFunctions = 0;
 
   // RAII helper for managing the state used to create a single function.
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 7807ef768..75eb3bd21 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -16,6 +16,7 @@
 
 #include "tools/fuzzing.h"
 #include "ir/module-utils.h"
+#include "ir/subtypes.h"
 #include "ir/type-updating.h"
 #include "tools/fuzzing/heap-types.h"
 #include "tools/fuzzing/parameters.h"
@@ -265,6 +266,28 @@ void TranslateToFuzzReader::setupHeapTypes() {
       }
     }
   }
+
+  // Compute subtypes ahead of time. It is more efficient to do this all at once
+  // now, rather than lazily later.
+  SubTypes subTypes(interestingHeapTypes);
+  for (auto type : interestingHeapTypes) {
+    for (auto subType : subTypes.getStrictSubTypes(type)) {
+      interestingHeapSubTypes[type].push_back(subType);
+    }
+    // Basic types must be handled directly, since subTypes doesn't look at
+    // those.
+    if (type.isStruct()) {
+      interestingHeapSubTypes[HeapType::struct_].push_back(type);
+      interestingHeapSubTypes[HeapType::eq].push_back(type);
+      interestingHeapSubTypes[HeapType::any].push_back(type);
+    } else if (type.isArray()) {
+      interestingHeapSubTypes[HeapType::array].push_back(type);
+      interestingHeapSubTypes[HeapType::eq].push_back(type);
+      interestingHeapSubTypes[HeapType::any].push_back(type);
+    } else if (type.isSignature()) {
+      interestingHeapSubTypes[HeapType::func].push_back(type);
+    }
+  }
 }
 
 // TODO(reference-types): allow the fuzzer to create multiple tables
@@ -3278,11 +3301,10 @@ Nullability TranslateToFuzzReader::getSubType(Nullability nullability) {
 }
 
 HeapType TranslateToFuzzReader::getSubType(HeapType type) {
-  // TODO: pick from heapTypes
-  if (oneIn(2)) {
+  if (oneIn(3)) {
     return type;
   }
-  if (type.isBasic()) {
+  if (type.isBasic() && oneIn(2)) {
     switch (type.getBasic()) {
       case HeapType::func:
         // TODO: Typed function references.
@@ -3294,7 +3316,6 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
                       .add(FeatureSet::ReferenceTypes, HeapType::ext)
                       .add(FeatureSet::GC, HeapType::noext));
       case HeapType::any:
-        // TODO: nontrivial types as well.
         assert(wasm.features.hasReferenceTypes());
         assert(wasm.features.hasGC());
         return pick(HeapType::any,
@@ -3304,7 +3325,6 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
                     HeapType::array,
                     HeapType::none);
       case HeapType::eq:
-        // TODO: nontrivial types as well.
         assert(wasm.features.hasReferenceTypes());
         assert(wasm.features.hasGC());
         return pick(HeapType::eq,
@@ -3315,7 +3335,6 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
       case HeapType::i31:
         return pick(HeapType::i31, HeapType::none);
       case HeapType::struct_:
-        // TODO: nontrivial types as well.
         return pick(HeapType::struct_, HeapType::none);
       case HeapType::array:
         return pick(HeapType::array, HeapType::none);
@@ -3331,7 +3350,15 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
         break;
     }
   }
-  // TODO: nontrivial types as well.
+  // Look for an interesting subtype.
+  auto iter = interestingHeapSubTypes.find(type);
+  if (iter != interestingHeapSubTypes.end()) {
+    auto& subTypes = iter->second;
+    if (!subTypes.empty()) {
+      return pick(subTypes);
+    }
+  }
+  // Failure to do anything interesting, return the type.
   return type;
 }
 
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 04f0f6405..595dff648 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,42 +1,46 @@
 total
- [exports]      : 5       
- [funcs]        : 13      
+ [exports]      : 9       
+ [funcs]        : 21      
  [globals]      : 5       
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 20      
- [table-data]   : 0       
+ [table-data]   : 5       
  [tables]       : 1       
  [tags]         : 1       
- [total]        : 460     
- [vars]         : 23      
- ArrayNewFixed  : 1       
- AtomicCmpxchg  : 1       
- AtomicRMW      : 1       
- Binary         : 66      
- Block          : 56      
- Break          : 3       
- Call           : 15      
- Const          : 98      
- Drop           : 8       
- GlobalGet      : 26      
- GlobalSet      : 26      
+ [total]        : 738     
+ [vars]         : 16      
+ ArrayNew       : 8       
+ ArrayNewFixed  : 3       
+ Binary         : 82      
+ Block          : 89      
+ Break          : 7       
+ Call           : 25      
+ CallIndirect   : 1       
+ CallRef        : 1       
+ Const          : 168     
+ Drop           : 10      
+ GlobalGet      : 40      
+ GlobalSet      : 40      
  I31New         : 2       
- If             : 16      
- Load           : 17      
- LocalGet       : 33      
- LocalSet       : 21      
+ If             : 29      
+ Load           : 19      
+ LocalGet       : 48      
+ LocalSet       : 29      
  Loop           : 3       
- Nop            : 9       
+ MemoryCopy     : 1       
+ MemoryInit     : 2       
+ Nop            : 11      
  RefAs          : 2       
- RefFunc        : 2       
- RefNull        : 5       
- Return         : 3       
- SIMDExtract    : 1       
- Select         : 1       
+ RefFunc        : 21      
+ RefIsNull      : 1       
+ RefNull        : 6       
+ Return         : 8       
+ SIMDExtract    : 2       
+ Select         : 2       
  Store          : 1       
- StructNew      : 4       
- TupleExtract   : 2       
- TupleMake      : 4       
- Unary          : 17      
- Unreachable    : 16      
+ StructNew      : 7       
+ TupleExtract   : 5       
+ TupleMake      : 10      
+ Unary          : 31      
+ Unreachable    : 24