More reducer improvements (#1533)

*    Add a helper class to iterate over all a node's children, and use that when attempting to replace a node with its children.
*    If a child has a different type than the parent, try to replace the parent with a conversion + the child (for example, a call may receive two f32 inputs and return an i32; we can try to replace the call with one of those f32s and a conversion to an i32).
*    When possible, try to replace the function body with a child even if the child has a different type, by changing the function return value.

1 files changed, 92 insertions, 45 deletions

diff --git a/src/tools/wasm-reduce.cpp b/src/tools/wasm-reduce.cpp
index 7b7ff9da3..0dfb97907 100644
--- a/src/tools/wasm-reduce.cpp
+++ b/src/tools/wasm-reduce.cpp
@@ -35,7 +35,9 @@
 #include "wasm-io.h"
 #include "wasm-builder.h"
 #include "ir/branch-utils.h"
+#include "ir/iteration.h"
 #include "ir/literal-utils.h"
+#include "ir/properties.h"
 #include "wasm-validator.h"
 #ifdef _WIN32
 #ifndef NOMINMAX
@@ -403,8 +405,9 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
   // don't need to duplicate work that they do
 
   void visitExpression(Expression* curr) {
+    // type-based reductions
     if (curr->type == none) {
-      if (tryToReduceCurrentToNone()) return;
+      if (tryToReduceCurrentToNop()) return;
     } else if (isConcreteType(curr->type)) {
       if (tryToReduceCurrentToConst()) return;
     } else {
@@ -419,8 +422,6 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
           return;
         }
       }
-      if (tryToReplaceCurrent(iff->ifTrue)) return;
-      if (iff->ifFalse && tryToReplaceCurrent(iff->ifFalse)) return;
       handleCondition(iff->condition);
     } else if (auto* br = curr->dynCast<Break>()) {
       handleCondition(br->condition);
@@ -428,26 +429,6 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
       handleCondition(select->condition);
     } else if (auto* sw = curr->dynCast<Switch>()) {
       handleCondition(sw->condition);
-    } else if (auto* set = curr->dynCast<SetLocal>()) {
-      if (set->isTee()) {
-        // maybe we don't need the set
-        tryToReplaceCurrent(set->value);
-      }
-    } else if (auto* unary = curr->dynCast<Unary>()) {
-      // maybe we can pass through
-      tryToReplaceCurrent(unary->value);
-    } else if (auto* binary = curr->dynCast<Binary>()) {
-      // maybe we can pass through
-      if (!tryToReplaceCurrent(binary->left)) {
-        tryToReplaceCurrent(binary->right);
-      }
-    } else if (auto* call = curr->dynCast<Call>()) {
-      handleCall(call);
-    } else if (auto* call = curr->dynCast<CallImport>()) {
-      handleCall(call);
-    } else if (auto* call = curr->dynCast<CallIndirect>()) {
-      if (tryToReplaceCurrent(call->target)) return;
-      handleCall(call);
     } else if (auto* block = curr->dynCast<Block>()) {
       if (!shouldTryToReduce()) return;
       // replace a singleton
@@ -479,24 +460,66 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
         }
         i++;
       }
+      return; // nothing more to do
     } else if (auto* loop = curr->dynCast<Loop>()) {
       if (shouldTryToReduce() && !BranchUtils::BranchSeeker::hasNamed(loop, loop->name)) {
         tryToReplaceCurrent(loop->body);
       }
-    } else if (auto* rmw = curr->dynCast<AtomicRMW>()) {
-      if (tryToReplaceCurrent(rmw->ptr)) return;
-      if (tryToReplaceCurrent(rmw->value)) return;
-    } else if (auto* cmpx = curr->dynCast<AtomicCmpxchg>()) {
-      if (tryToReplaceCurrent(cmpx->ptr)) return;
-      if (tryToReplaceCurrent(cmpx->expected)) return;
-      if (tryToReplaceCurrent(cmpx->replacement)) return;
-    } else if (auto* wait = curr->dynCast<AtomicWait>()) {
-      if (tryToReplaceCurrent(wait->ptr)) return;
-      if (tryToReplaceCurrent(wait->expected)) return;
-      if (tryToReplaceCurrent(wait->timeout)) return;
-    } else if (auto* wake = curr->dynCast<AtomicWake>()) {
-      if (tryToReplaceCurrent(wake->ptr)) return;
-      if (tryToReplaceCurrent(wake->wakeCount)) return;
+      return; // nothing more to do
+    }
+    // Finally, try to replace with a child.
+    for (auto* child : ChildIterator(curr)) {
+      if (tryToReplaceCurrent(child)) return;
+    }
+    // If that didn't work, try to replace with a child + a unary conversion
+    if (isConcreteType(curr->type) &&
+        !curr->is<Unary>()) { // but not if it's already unary
+      for (auto* child : ChildIterator(curr)) {
+        if (child->type == curr->type) continue; // already tried
+        if (!isConcreteType(child->type)) continue; // no conversion
+        Expression* fixed;
+        switch (curr->type) {
+          case i32: {
+            switch (child->type) {
+              case i64: fixed = builder->makeUnary(WrapInt64, child); break;
+              case f32: fixed = builder->makeUnary(TruncSFloat32ToInt32, child); break;
+              case f64: fixed = builder->makeUnary(TruncSFloat64ToInt32, child); break;
+              default: WASM_UNREACHABLE();
+            }
+            break;
+          }
+          case i64: {
+            switch (child->type) {
+              case i32: fixed = builder->makeUnary(ExtendSInt32, child); break;
+              case f32: fixed = builder->makeUnary(TruncSFloat32ToInt64, child); break;
+              case f64: fixed = builder->makeUnary(TruncSFloat64ToInt64, child); break;
+              default: WASM_UNREACHABLE();
+            }
+            break;
+          }
+          case f32: {
+            switch (child->type) {
+              case i32: fixed = builder->makeUnary(ConvertSInt32ToFloat32, child); break;
+              case i64: fixed = builder->makeUnary(ConvertSInt64ToFloat32, child); break;
+              case f64: fixed = builder->makeUnary(DemoteFloat64, child); break;
+              default: WASM_UNREACHABLE();
+            }
+            break;
+          }
+          case f64: {
+            switch (child->type) {
+              case i32: fixed = builder->makeUnary(ConvertSInt32ToFloat64, child); break;
+              case i64: fixed = builder->makeUnary(ConvertSInt64ToFloat64, child); break;
+              case f32: fixed = builder->makeUnary(PromoteFloat32, child); break;
+              default: WASM_UNREACHABLE();
+            }
+            break;
+          }
+          default: WASM_UNREACHABLE();
+        }
+        assert(fixed->type == curr->type);
+        if (tryToReplaceCurrent(fixed)) return;
+      }
     }
   }
 
@@ -649,6 +672,37 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
         skip = std::min(size_t(factor), 2 * skip);
       }
     }
+    // If we are left with a single function that is not exported or used in
+    // a table, that is useful as then we can change the return type.
+    if (module->functions.size() == 1 && module->exports.empty() && module->table.segments.empty()) {
+      auto* func = module->functions[0].get();
+      // We can't remove something that might have breaks to it.
+      if (!Properties::isNamedControlFlow(func->body)) {
+        auto funcType = func->type;
+        auto funcResult = func->result;
+        auto* funcBody = func->body;
+        for (auto* child : ChildIterator(func->body)) {
+          if (!(isConcreteType(child->type) || child->type == none)) {
+            continue; // not something a function can return
+          }
+          // Try to replace the body with the child, fixing up the function
+          // to accept it.
+          func->type = Name();
+          func->result = child->type;
+          func->body = child;
+          if (writeAndTestReduction()) {
+            // great, we succeeded!
+            std::cerr << "|    altered function result type\n";
+            noteReduction(1);
+            break;
+          }
+          // Undo.
+          func->type = funcType;
+          func->result = funcResult;
+          func->body = funcBody;
+        }
+      }
+    }
   }
 
   bool tryToRemoveFunctions(std::vector<Name> names) {
@@ -729,14 +783,7 @@ struct Reducer : public WalkerPass<PostWalker<Reducer, UnifiedExpressionVisitor<
     }
   }
 
-  template<typename T>
-  void handleCall(T* call) {
-    for (auto* op : call->operands) {
-      if (tryToReplaceCurrent(op)) return;
-    }
-  }
-
-  bool tryToReduceCurrentToNone() {
+  bool tryToReduceCurrentToNop() {
     auto* curr = getCurrent();
     if (curr->is<Nop>()) return false;
     // try to replace with a trivial value