Add pass to instrument loads / stores. (#959)

* Add pass to instrument loads / stores

* Simplify instrumentation.

* Document.

8 files changed, 639 insertions, 0 deletions

diff --git a/src/asmjs/shared-constants.cpp b/src/asmjs/shared-constants.cpp
index d704c8009..02e80d36b 100644
--- a/src/asmjs/shared-constants.cpp
+++ b/src/asmjs/shared-constants.cpp
@@ -55,6 +55,7 @@ cashew::IString GLOBAL("global"),
                 USE_ASM("use asm"),
                 BUFFER("buffer"),
                 ENV("env"),
+                INSTRUMENT("instrument"),
                 MATH_IMUL("Math_imul"),
                 MATH_CLZ32("Math_clz32"),
                 MATH_CTZ32("Math_ctz32"),
diff --git a/src/asmjs/shared-constants.h b/src/asmjs/shared-constants.h
index 7b48c3df5..f13023778 100644
--- a/src/asmjs/shared-constants.h
+++ b/src/asmjs/shared-constants.h
@@ -58,6 +58,7 @@ extern cashew::IString GLOBAL,
                 USE_ASM,
                 BUFFER,
                 ENV,
+                INSTRUMENT,
                 MATH_IMUL,
                 MATH_CLZ32,
                 MATH_CTZ32,
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 75e634c16..637f40d94 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -9,6 +9,7 @@ SET(passes_SOURCES
   LegalizeJSInterface.cpp
   LocalCSE.cpp
   LogExecution.cpp
+  InstrumentMemory.cpp
   MemoryPacking.cpp
   MergeBlocks.cpp
   Metrics.cpp
diff --git a/src/passes/InstrumentMemory.cpp b/src/passes/InstrumentMemory.cpp
new file mode 100644
index 000000000..536031064
--- /dev/null
+++ b/src/passes/InstrumentMemory.cpp
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Instruments the build with code to intercept all memory reads and writes.
+// This can be useful in building tools that analyze memory access behaviour.
+//
+// The instrumentation is performed by calling an FFI with an ID for each
+// memory access site. Load / store IDs share the same index space. The
+// instrumentation wraps the evaluation of the address operand, therefore
+// it executes before the load / store is executed. Note that Instrumentation
+// code must return tha address argument.
+//
+// Loads: load(id, bytes, offset, address) => address
+//
+//  Before:
+//   (i32.load8_s align=1 offset=2 (i32.const 3))
+//
+//  After:
+//   (i32.load8_s align=1 offset=2
+//    (call $load
+//     (i32.const n) // ID
+//     (i32.const 1) // bytes
+//     (i32.const 2) // offset
+//     (i32.const 3) // address
+//    )
+//   )
+//
+// Stores: store(id, bytes, offset, address) => address
+//
+//  Before:
+//   (i32.store8 align=1 offset=2 (i32.const 3) (i32.const 4))
+//
+//  After:
+//   (i32.store16 align=1 offset=2
+//    (call $store
+//     (i32.const n) // ID
+//     (i32.const 1) // bytes
+//     (i32.const 2) // offset
+//     (i32.const 3) // address
+//    )
+//    (i32.const 4)
+//   )
+
+#include <wasm.h>
+#include <wasm-builder.h>
+#include <pass.h>
+#include "shared-constants.h"
+#include "asmjs/shared-constants.h"
+#include "asm_v_wasm.h"
+
+namespace wasm {
+
+Name load("load");
+Name store("store");
+
+struct InstrumentMemory : public WalkerPass<PostWalker<InstrumentMemory>> {
+  void visitLoad(Load* curr) {
+    makeLoadCall(curr);
+  }
+  void visitStore(Store* curr) {
+    makeStoreCall(curr);
+  }
+  void addImport(Module *curr, Name name, std::string sig) {
+    auto import = new Import;
+    import->name = name;
+    import->module = INSTRUMENT;
+    import->base = name;
+    import->functionType = ensureFunctionType(sig, curr)->name;
+    import->kind = ExternalKind::Function;
+    curr->addImport(import);
+  }
+
+  void visitModule(Module *curr) {
+    addImport(curr, load,  "iiiii");
+    addImport(curr, store,  "iiiii");
+  }
+
+private:
+  std::atomic<Index> id;
+  Expression* makeLoadCall(Load* curr) {
+    Builder builder(*getModule());
+    curr->ptr = builder.makeCallImport(load,
+      { builder.makeConst(Literal(int32_t(id.fetch_add(1)))),
+        builder.makeConst(Literal(int32_t(curr->bytes))),
+        builder.makeConst(Literal(int32_t(curr->offset.addr))),
+        curr->ptr},
+      i32
+    );
+    return curr;
+  }
+
+  Expression* makeStoreCall(Store* curr) {
+    Builder builder(*getModule());
+    curr->ptr = builder.makeCallImport(store,
+      { builder.makeConst(Literal(int32_t(id.fetch_add(1)))),
+        builder.makeConst(Literal(int32_t(curr->bytes))),
+        builder.makeConst(Literal(int32_t(curr->offset.addr))),
+        curr->ptr },
+      i32
+    );
+    return curr;
+  }
+};
+
+Pass *createInstrumentMemoryPass() {
+  return new InstrumentMemory();
+}
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 8da42f9cd..51e76cdf7 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -74,6 +74,7 @@ void PassRegistry::registerPasses() {
   registerPass("legalize-js-interface", "legalizes i64 types on the import/export boundary", createLegalizeJSInterfacePass);
   registerPass("local-cse", "common subexpression elimination inside basic blocks", createLocalCSEPass);
   registerPass("log-execution", "instrument the build with logging of where execution goes", createLogExecutionPass);
+  registerPass("instrument-memory", "instrument the build with code to intercept all loads and stores", createInstrumentMemoryPass);
   registerPass("memory-packing", "packs memory into separate segments, skipping zeros", createMemoryPackingPass);
   registerPass("merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
   registerPass("metrics", "reports metrics", createMetricsPass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index f8156d4fe..709a903f1 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -33,6 +33,7 @@ Pass *createInliningPass();
 Pass *createLegalizeJSInterfacePass();
 Pass *createLocalCSEPass();
 Pass *createLogExecutionPass();
+Pass *createInstrumentMemoryPass();
 Pass *createMemoryPackingPass();
 Pass *createMergeBlocksPass();
 Pass *createMinifiedPrinterPass();
diff --git a/test/passes/instrument-memory.txt b/test/passes/instrument-memory.txt
new file mode 100644
index 000000000..dd2e876d0
--- /dev/null
+++ b/test/passes/instrument-memory.txt
@@ -0,0 +1,453 @@
+(module
+ (type $1 (func))
+ (type $FUNCSIG$iiiii (func (param i32 i32 i32 i32) (result i32)))
+ (import "instrument" "load" (func $load (param i32 i32 i32 i32) (result i32)))
+ (import "instrument" "store" (func $store (param i32 i32 i32 i32) (result i32)))
+ (memory $0 256 256)
+ (func $A (type $1)
+  (drop
+   (i32.load8_s
+    (call $load
+     (i32.const 0)
+     (i32.const 1)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load8_u
+    (call $load
+     (i32.const 1)
+     (i32.const 1)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load16_s
+    (call $load
+     (i32.const 2)
+     (i32.const 2)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load16_u
+    (call $load
+     (i32.const 3)
+     (i32.const 2)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load
+    (call $load
+     (i32.const 4)
+     (i32.const 4)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load8_s
+    (call $load
+     (i32.const 5)
+     (i32.const 1)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load8_u
+    (call $load
+     (i32.const 6)
+     (i32.const 1)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load16_s
+    (call $load
+     (i32.const 7)
+     (i32.const 2)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load16_u
+    (call $load
+     (i32.const 8)
+     (i32.const 2)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load32_s
+    (call $load
+     (i32.const 9)
+     (i32.const 4)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load32_u
+    (call $load
+     (i32.const 10)
+     (i32.const 4)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load
+    (call $load
+     (i32.const 11)
+     (i32.const 8)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (f32.load
+    (call $load
+     (i32.const 12)
+     (i32.const 4)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (f64.load
+    (call $load
+     (i32.const 13)
+     (i32.const 8)
+     (i32.const 0)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load8_s offset=1
+    (call $load
+     (i32.const 14)
+     (i32.const 1)
+     (i32.const 1)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load8_u offset=2
+    (call $load
+     (i32.const 15)
+     (i32.const 1)
+     (i32.const 2)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load16_s offset=3 align=1
+    (call $load
+     (i32.const 16)
+     (i32.const 2)
+     (i32.const 3)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load16_u offset=4 align=1
+    (call $load
+     (i32.const 17)
+     (i32.const 2)
+     (i32.const 4)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i32.load offset=5 align=2
+    (call $load
+     (i32.const 18)
+     (i32.const 4)
+     (i32.const 5)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load8_s offset=6
+    (call $load
+     (i32.const 19)
+     (i32.const 1)
+     (i32.const 6)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load8_u offset=7
+    (call $load
+     (i32.const 20)
+     (i32.const 1)
+     (i32.const 7)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load16_s offset=8 align=1
+    (call $load
+     (i32.const 21)
+     (i32.const 2)
+     (i32.const 8)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load16_u offset=9 align=1
+    (call $load
+     (i32.const 22)
+     (i32.const 2)
+     (i32.const 9)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load32_s offset=10 align=2
+    (call $load
+     (i32.const 23)
+     (i32.const 4)
+     (i32.const 10)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load32_u offset=11 align=2
+    (call $load
+     (i32.const 24)
+     (i32.const 4)
+     (i32.const 11)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (i64.load offset=12 align=2
+    (call $load
+     (i32.const 25)
+     (i32.const 8)
+     (i32.const 12)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (f32.load offset=13 align=2
+    (call $load
+     (i32.const 26)
+     (i32.const 4)
+     (i32.const 13)
+     (i32.const 0)
+    )
+   )
+  )
+  (drop
+   (f64.load offset=14 align=2
+    (call $load
+     (i32.const 27)
+     (i32.const 8)
+     (i32.const 14)
+     (i32.const 0)
+    )
+   )
+  )
+ )
+ (func $B (type $1)
+  (i32.store8
+   (call $store
+    (i32.const 28)
+    (i32.const 1)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i32.const 1)
+  )
+  (i32.store16
+   (call $store
+    (i32.const 29)
+    (i32.const 2)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i32.const 2)
+  )
+  (i32.store
+   (call $store
+    (i32.const 30)
+    (i32.const 4)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i32.const 3)
+  )
+  (i64.store8
+   (call $store
+    (i32.const 31)
+    (i32.const 1)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i64.const 4)
+  )
+  (i64.store16
+   (call $store
+    (i32.const 32)
+    (i32.const 2)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i64.const 5)
+  )
+  (i64.store32
+   (call $store
+    (i32.const 33)
+    (i32.const 4)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i64.const 6)
+  )
+  (i64.store
+   (call $store
+    (i32.const 34)
+    (i32.const 8)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (i64.const 7)
+  )
+  (f32.store
+   (call $store
+    (i32.const 35)
+    (i32.const 4)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (f32.const 8)
+  )
+  (f64.store
+   (call $store
+    (i32.const 36)
+    (i32.const 8)
+    (i32.const 0)
+    (i32.const 0)
+   )
+   (f64.const 9)
+  )
+  (i32.store8 offset=1
+   (call $store
+    (i32.const 37)
+    (i32.const 1)
+    (i32.const 1)
+    (i32.const 0)
+   )
+   (i32.const 1)
+  )
+  (i32.store16 offset=2 align=1
+   (call $store
+    (i32.const 38)
+    (i32.const 2)
+    (i32.const 2)
+    (i32.const 0)
+   )
+   (i32.const 2)
+  )
+  (i32.store offset=3 align=2
+   (call $store
+    (i32.const 39)
+    (i32.const 4)
+    (i32.const 3)
+    (i32.const 0)
+   )
+   (i32.const 3)
+  )
+  (i64.store8 offset=4
+   (call $store
+    (i32.const 40)
+    (i32.const 1)
+    (i32.const 4)
+    (i32.const 0)
+   )
+   (i64.const 4)
+  )
+  (i64.store16 offset=5
+   (call $store
+    (i32.const 41)
+    (i32.const 2)
+    (i32.const 5)
+    (i32.const 0)
+   )
+   (i64.const 5)
+  )
+  (i64.store32 offset=6 align=2
+   (call $store
+    (i32.const 42)
+    (i32.const 4)
+    (i32.const 6)
+    (i32.const 0)
+   )
+   (i64.const 6)
+  )
+  (i64.store offset=7 align=2
+   (call $store
+    (i32.const 43)
+    (i32.const 8)
+    (i32.const 7)
+    (i32.const 0)
+   )
+   (i64.const 7)
+  )
+  (f32.store offset=8 align=2
+   (call $store
+    (i32.const 44)
+    (i32.const 4)
+    (i32.const 8)
+    (i32.const 0)
+   )
+   (f32.const 8)
+  )
+  (f64.store offset=9 align=2
+   (call $store
+    (i32.const 45)
+    (i32.const 8)
+    (i32.const 9)
+    (i32.const 0)
+   )
+   (f64.const 9)
+  )
+ )
+)
diff --git a/test/passes/instrument-memory.wast b/test/passes/instrument-memory.wast
new file mode 100644
index 000000000..7f92de9cd
--- /dev/null
+++ b/test/passes/instrument-memory.wast
@@ -0,0 +1,58 @@
+(module
+  (memory 256 256)
+  (type $1 (func))
+  (func $A (type $1)
+    (drop (i32.load8_s (i32.const 0)))
+    (drop (i32.load8_u (i32.const 0)))
+    (drop (i32.load16_s (i32.const 0)))
+    (drop (i32.load16_u (i32.const 0)))
+    (drop (i32.load (i32.const 0)))
+    (drop (i64.load8_s (i32.const 0)))
+    (drop (i64.load8_u (i32.const 0)))
+    (drop (i64.load16_s (i32.const 0)))
+    (drop (i64.load16_u (i32.const 0)))
+    (drop (i64.load32_s (i32.const 0)))
+    (drop (i64.load32_u (i32.const 0)))
+    (drop (i64.load (i32.const 0)))
+    (drop (f32.load (i32.const 0)))
+    (drop (f64.load (i32.const 0)))
+
+    (drop (i32.load8_s align=1 offset=1 (i32.const 0)))
+    (drop (i32.load8_u align=1 offset=2 (i32.const 0)))
+    (drop (i32.load16_s align=1 offset=3 (i32.const 0)))
+    (drop (i32.load16_u align=1 offset=4 (i32.const 0)))
+    (drop (i32.load align=2 offset=5 (i32.const 0)))
+    (drop (i64.load8_s align=1 offset=6 (i32.const 0)))
+    (drop (i64.load8_u align=1 offset=7 (i32.const 0)))
+    (drop (i64.load16_s align=1 offset=8 (i32.const 0)))
+    (drop (i64.load16_u align=1 offset=9 (i32.const 0)))
+    (drop (i64.load32_s align=2 offset=10 (i32.const 0)))
+    (drop (i64.load32_u align=2 offset=11 (i32.const 0)))
+    (drop (i64.load align=2 offset=12 (i32.const 0)))
+    (drop (f32.load align=2 offset=13 (i32.const 0)))
+    (drop (f64.load align=2 offset=14 (i32.const 0)))
+  )
+
+  (func $B (type $1)
+    (i32.store8 (i32.const 0) (i32.const 1))
+    (i32.store16 (i32.const 0) (i32.const 2))
+    (i32.store (i32.const 0) (i32.const 3))
+    (i64.store8 (i32.const 0) (i64.const 4))
+    (i64.store16 (i32.const 0) (i64.const 5))
+    (i64.store326 (i32.const 0) (i64.const 6))
+    (i64.store (i32.const 0) (i64.const 7))
+    (f32.store (i32.const 0) (f32.const 8))
+    (f64.store (i32.const 0) (f64.const 9))
+
+    (i32.store8 align=1 offset=1 (i32.const 0) (i32.const 1))
+    (i32.store16 align=1 offset=2 (i32.const 0) (i32.const 2))
+    (i32.store align=2 offset=3 (i32.const 0) (i32.const 3))
+    (i64.store8 align=1 offset=4 (i32.const 0) (i64.const 4))
+    (i64.store16 align=2 offset=5 (i32.const 0) (i64.const 5))
+    (i64.store32 align=2 offset=6 (i32.const 0) (i64.const 6))
+    (i64.store align=2 offset=7 (i32.const 0) (i64.const 7))
+    (f32.store align=2 offset=8 (i32.const 0) (f32.const 8))
+    (f64.store align=2 offset=9 (i32.const 0) (f64.const 9))
+  )
+)
+