Add an Intrinsics mechanism, and a call.without.effects intrinsic (#4126)

An "intrinsic" is modeled as a call to an import. We could also add new
IR things for them, but that would take more work and lead to less
clear errors in other tools if they try to read a binary using such a
nonstandard extension.

A first intrinsic is added here, call.without.effects This is basically the same
as call_ref except that the optimizer is free to assume the call has no
side effects. Consequently, if the result is not used then it can be optimized
out (as even if it is not used then side effects could have kept it around).
Likewise, the lack of side effects allows more reordering and other
things.

A lowering pass for intrinsics is provided. Rather than automatically
lower them to normal wasm at the end of optimizations, the user must
call that pass explicitly. A typical workflow might be

-O --intrinsic-lowering -O

That optimizes with the intrinsic present - perhaps removing calls
thanks to it - then lowers it into normal wasm - it turns into a call_ref -
and then optimizes further, which would turns the call_ref into a
direct call, potentially inline, etc.

9 files changed, 212 insertions, 2 deletions

diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt
index c17a48ac0..f598f3d72 100644
--- a/src/ir/CMakeLists.txt
+++ b/src/ir/CMakeLists.txt
@@ -2,6 +2,7 @@ FILE(GLOB ir_HEADERS *.h)
 set(ir_SOURCES
   ExpressionAnalyzer.cpp
   ExpressionManipulator.cpp
+  intrinsics.cpp
   names.cpp
   properties.cpp
   LocalGraph.cpp
diff --git a/src/ir/effects.h b/src/ir/effects.h
index ad8f68efa..ee45d8205 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -17,6 +17,7 @@
 #ifndef wasm_ir_effects_h
 #define wasm_ir_effects_h
 
+#include "ir/intrinsics.h"
 #include "pass.h"
 #include "wasm-traversal.h"
 
@@ -31,7 +32,7 @@ public:
                  Expression* ast = nullptr)
     : ignoreImplicitTraps(passOptions.ignoreImplicitTraps),
       trapsNeverHappen(passOptions.trapsNeverHappen),
-      debugInfo(passOptions.debugInfo), module(&module),
+      debugInfo(passOptions.debugInfo), module(module),
       features(module.features) {
     if (ast) {
       walk(ast);
@@ -41,7 +42,7 @@ public:
   bool ignoreImplicitTraps;
   bool trapsNeverHappen;
   bool debugInfo;
-  Module* module;
+  Module& module;
   FeatureSet features;
 
   // Walk an expression and all its children.
@@ -393,6 +394,11 @@ private:
     }
 
     void visitCall(Call* curr) {
+      // call.without.effects has no effects.
+      if (Intrinsics(parent.module).isCallWithoutEffects(curr)) {
+        return;
+      }
+
       parent.calls = true;
       // When EH is enabled, any call can throw.
       if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
diff --git a/src/ir/intrinsics.cpp b/src/ir/intrinsics.cpp
new file mode 100644
index 000000000..c2318cabf
--- /dev/null
+++ b/src/ir/intrinsics.cpp
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ir/intrinsics.h"
+#include "wasm-builder.h"
+
+namespace wasm {
+
+static Name BinaryenIntrinsics("binaryen-intrinsics"),
+  CallWithoutEffects("call.without.effects");
+
+bool Intrinsics::isCallWithoutEffects(Function* func) {
+  return func->module == BinaryenIntrinsics && func->base == CallWithoutEffects;
+}
+
+Call* Intrinsics::isCallWithoutEffects(Expression* curr) {
+  if (auto* call = curr->dynCast<Call>()) {
+    // The target function may not exist if the module is still being
+    // constructed.
+    if (auto* func = module.getFunctionOrNull(call->target)) {
+      if (isCallWithoutEffects(func)) {
+        return call;
+      }
+    }
+  }
+  return nullptr;
+}
+
+} // namespace wasm
diff --git a/src/ir/intrinsics.h b/src/ir/intrinsics.h
new file mode 100644
index 000000000..9a1356029
--- /dev/null
+++ b/src/ir/intrinsics.h
@@ -0,0 +1,95 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_ir_intrinsics_h
+#define wasm_ir_intrinsics_h
+
+#include "pass.h"
+#include "wasm-traversal.h"
+
+//
+// See the README.md for background on intrinsic functions.
+//
+// Intrinsics can be recognized by Intrinsics::isFoo() methods, that check if a
+// function is a particular intrinsic, or if a call to a function is so. The
+// latter returns nullptr if the input is not that intrinsic, and otherwise the
+// intrinsic itself cast to a Call*.
+//
+
+namespace wasm {
+
+class Intrinsics {
+  Module& module;
+
+public:
+  Intrinsics(Module& module) : module(module) {}
+
+  //
+  // Check if an instruction is the call.without.effects intrinsic.
+  //
+  //   (import "binaryen-intrinsics" "call.without.effects"
+  //     (func (..params..) (param $target funcref) (..results..)))
+  //
+  // call.without.effects can take any parameters, and in addition a funcref,
+  // and return any result.
+  //
+  // Precise semantics:
+  //
+  //  * The optimizer will assume this instruction has no side effects.
+  //  * Final lowering turns a call.without.effects into a call of the given
+  //    function with the given parameters. (This will either be a direct call,
+  //    or a call_ref; note that either way, the function reference that appears
+  //    here must have the proper type - if not, you will get an error.)
+  //
+  // call.without.effects is useful to be able to get rid of an unused result
+  // that has side effects. For example,
+  //
+  //  (drop (call $get-something))
+  //
+  // cannot be removed, as a call has side effects. But if a code generator
+  // knows that it is fine to not make the call given that the result is
+  // dropped (perhaps the side effects are to initialize a global cache, for
+  // example) then instead of emitting
+  //
+  //   (call $get-something)
+  //
+  // it can emit
+  //
+  //   (call $call.without.effects (ref.func $get-something))
+  //
+  // which will have this behavior in the optimizer if it is dropped:
+  //
+  //  (drop (call $call.without.effects (ref.func $get-something)))
+  //     =>
+  //  (drop (ref.func $get-something))
+  //
+  // Later optimizations can remove the dropped ref.func. Or, if the result is
+  // actually used,
+  //
+  //  (local.set $x (call $call.without.effects (ref.func $get-something)))
+  //     =>
+  //  (local.set $x (call $get-something))
+  //
+  // Later passes will then turn that into a direct call and further optimize
+  // things.
+  //
+  bool isCallWithoutEffects(Function* func);
+  Call* isCallWithoutEffects(Expression* curr);
+};
+
+} // namespace wasm
+
+#endif // wasm_ir_intrinsics_h
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index b61b895ef..a49ae8980 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -35,6 +35,7 @@ set(passes_SOURCES
   Inlining.cpp
   InstrumentLocals.cpp
   InstrumentMemory.cpp
+  Intrinsics.cpp
   LegalizeJSInterface.cpp
   LimitSegments.cpp
   LocalCSE.cpp
diff --git a/src/passes/Intrinsics.cpp b/src/passes/Intrinsics.cpp
new file mode 100644
index 000000000..1b5a50bbb
--- /dev/null
+++ b/src/passes/Intrinsics.cpp
@@ -0,0 +1,50 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ir/intrinsics.h"
+#include "pass.h"
+#include "wasm-builder.h"
+#include "wasm.h"
+
+namespace wasm {
+
+struct IntrinsicLowering : public WalkerPass<PostWalker<IntrinsicLowering>> {
+  bool isFunctionParallel() override { return true; }
+
+  Pass* create() override { return new IntrinsicLowering; }
+
+  void visitCall(Call* curr) {
+    if (Intrinsics(*getModule()).isCallWithoutEffects(curr)) {
+      // Turn into a call, by using the final operand as the function to call.
+      auto& operands = curr->operands;
+      auto* target = operands.back();
+      operands.pop_back();
+      // We could rely on later optimizations here, but at least ensure we emit
+      // a direct call when we can, to avoid a performance cliff if the user
+      // forgets to optimize.
+      Builder builder(*getModule());
+      if (auto* refFunc = target->dynCast<RefFunc>()) {
+        replaceCurrent(builder.makeCall(refFunc->func, operands, curr->type));
+      } else {
+        replaceCurrent(builder.makeCallRef(target, operands, curr->type));
+      }
+    }
+  }
+};
+
+Pass* createIntrinsicLoweringPass() { return new IntrinsicLowering(); }
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 878ecb3cb..5f53a1d78 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -164,6 +164,9 @@ void PassRegistry::registerPasses() {
   registerPass("inlining-optimizing",
                "inline functions and optimizes where we inlined",
                createInliningOptimizingPass);
+  registerPass("intrinsic-lowering",
+               "lower away binaryen intrinsics",
+               createIntrinsicLoweringPass);
   registerPass("legalize-js-interface",
                "legalizes i64 types on the import/export boundary",
                createLegalizeJSInterfacePass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 715e5c443..47b246bd4 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -62,6 +62,7 @@ Pass* createLimitSegmentsPass();
 Pass* createLocalCSEPass();
 Pass* createLocalSubtypingPass();
 Pass* createLogExecutionPass();
+Pass* createIntrinsicLoweringPass();
 Pass* createInstrumentLocalsPass();
 Pass* createInstrumentMemoryPass();
 Pass* createLoopInvariantCodeMotionPass();
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index eaeea7f1a..0de417ed7 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -21,6 +21,7 @@
 
 #include "ir/features.h"
 #include "ir/global-utils.h"
+#include "ir/intrinsics.h"
 #include "ir/module-utils.h"
 #include "ir/stack-utils.h"
 #include "ir/utils.h"
@@ -2705,6 +2706,16 @@ static void validateImports(Module& module, ValidationInfo& info) {
                              "Imported function must not have i64 results");
       }
     }
+
+    if (Intrinsics(module).isCallWithoutEffects(curr)) {
+      auto lastParam = curr->getParams();
+      if (lastParam.isTuple()) {
+        lastParam = lastParam.getTuple().types.back();
+      }
+      info.shouldBeTrue(lastParam.isFunction(),
+                        curr->name,
+                        "call.if.used's last param must be a function");
+    }
   });
   ModuleUtils::iterImportedGlobals(module, [&](Global* curr) {
     if (!module.features.hasMutableGlobals()) {