Subzero. Wasm. Implement sbrk and correctly do bounds checks.

Cleans up and generally improves memory handling in
WASM. WasmTranslator now outputs the number of pages requested so the
runtime can do correct bounds checks. The runtime also initializes the
stack pointer correctly (stored at address 1024), so we no longer have
to deal with negative pointers. This allows bounds checks to be done
with a single comparison against the size of the heap. Because of
this, we now support non-power-of-two heap sizes.

Sbrk is implemented by having the runtime keep track of the current
heap break and incrementing it as necessary. The heap break is
initialized to the start of the first page beyond any initialized data
in the WASM heap.

These changes allow us to pass the complete set of torture tests that
are passing on the Wasm waterfall.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4369
R=kschimpf@google.com, stichnot@chromium.org

Review URL: https://codereview.chromium.org/1913153003 .

src/WasmTranslator.cpp

diff --git a/src/WasmTranslator.cpp b/src/WasmTranslator.cpp
index a3ca88d..59b7068 100644
--- a/src/WasmTranslator.cpp
+++ b/src/WasmTranslator.cpp
@@ -1065,9 +1065,7 @@
     assert(Module);
     const auto &IndirectTable = Module->function_table;
 
-    // TODO(eholk): This should probably actually call abort instead.
-    auto *Abort = Func->makeNode();
-    Abort->appendInst(InstUnreachable::create(Func));
+    auto *Abort = getAbortTarget();
 
     assert(Args[0].toOperand());
 
@@ -1137,14 +1135,23 @@
 
   Operand *sanitizeAddress(Operand *Base, uint32_t Offset) {
     SizeT MemSize = Module->module->min_mem_pages * WASM_PAGE_SIZE;
-    SizeT MemMask = MemSize - 1;
 
     bool ConstZeroBase = false;
 
     // first, add the index and the offset together.
     if (auto *ConstBase = llvm::dyn_cast<ConstantInteger32>(Base)) {
       uint32_t RealOffset = Offset + ConstBase->getValue();
-      RealOffset &= MemMask;
+      if (RealOffset >= MemSize) {
+        // We've proven this will always be an out of bounds access, so insert
+        // an unconditional trap.
+        Control()->appendInst(InstUnreachable::create(Func));
+        // It doesn't matter what we return here, so return something that will
+        // allow the rest of code generation to happen.
+        //
+        // We might be tempted to just abort translation here, but out of bounds
+        // memory access is a runtime trap, not a compile error.
+        return Ctx->getConstantZero(getPointerType());
+      }
       Base = Ctx->getConstantInt32(RealOffset);
       ConstZeroBase = (0 == RealOffset);
     } else if (0 != Offset) {
@@ -1156,12 +1163,25 @@
       Base = Addr;
     }
 
+    // Do the bounds check.
+    //
+    // TODO (eholk): Add a command line argument to control whether bounds
+    // checks are inserted, and maybe add a way to duplicate bounds checks to
+    // get a better sense of the overhead.
     if (!llvm::dyn_cast<ConstantInteger32>(Base)) {
-      auto *ClampedAddr = makeVariable(Ice::getPointerType());
+      // TODO (eholk): creating a new basic block on every memory access is
+      // terrible (see https://goo.gl/Zj7DTr). Try adding a new instruction that
+      // encapsulates this "abort if false" pattern.
+      auto *CheckPassed = Func->makeNode();
+      auto *CheckFailed = getAbortTarget();
+
+      auto *Check = makeVariable(IceType_i1);
+      Control()->appendInst(InstIcmp::create(Func, InstIcmp::Ult, Check, Base,
+                                             Ctx->getConstantInt32(MemSize)));
       Control()->appendInst(
-          InstArithmetic::create(Func, InstArithmetic::And, ClampedAddr, Base,
-                                 Ctx->getConstantInt32(MemSize - 1)));
-      Base = ClampedAddr;
+          InstBr::create(Func, Check, CheckPassed, CheckFailed));
+
+      *ControlPtr = OperandNode(CheckPassed);
     }
 
     Ice::Operand *RealAddr = nullptr;
@@ -1261,6 +1281,8 @@
   class Cfg *Func;
   GlobalContext *Ctx;
 
+  CfgNode *AbortTarget = nullptr;
+
   SizeT NextArg = 0;
 
   CfgUnorderedMap<Operand *, InstPhi *> PhiMap;
@@ -1297,6 +1319,18 @@
     return Iter->second;
   }
 
+  CfgNode *getAbortTarget() {
+    if (!AbortTarget) {
+      // TODO (eholk): Move this node to the end of the CFG, or even better,
+      // have only one abort block for the whole module.
+      AbortTarget = Func->makeNode();
+      // TODO (eholk): This should probably actually call abort instead.
+      AbortTarget->appendInst(InstUnreachable::create(Func));
+    }
+
+    return AbortTarget;
+  }
+
   template <typename F = std::function<void(Ostream &)>> void log(F Fn) const {
     if (BuildDefs::dump() && (getFlags().getVerbose() & IceV_Wasm)) {
       Fn(Ctx->getStrDump());
@@ -1470,6 +1504,14 @@
       WritePtr += Seg.source_size;
     }
 
+    // Save the size of the initialized data in a global variable so the runtime
+    // can use it to determine the initial heap break.
+    auto *GlobalDataSize = VariableDeclaration::createExternal(Globals.get());
+    GlobalDataSize->setName(Ctx->getGlobalString("WASM_DATA_SIZE"));
+    GlobalDataSize->addInitializer(VariableDeclaration::DataInitializer::create(
+        Globals.get(), reinterpret_cast<const char *>(&WritePtr),
+        sizeof(WritePtr)));
+
     // Pad the rest with zeros
     SizeT DataSize = Module->min_mem_pages * WASM_PAGE_SIZE;
     if (WritePtr < DataSize) {
@@ -1477,7 +1519,16 @@
           Globals.get(), DataSize - WritePtr));
     }
 
+    // Save the number of pages for the runtime
+    auto *GlobalNumPages = VariableDeclaration::createExternal(Globals.get());
+    GlobalNumPages->setName(Ctx->getGlobalString("WASM_NUM_PAGES"));
+    GlobalNumPages->addInitializer(VariableDeclaration::DataInitializer::create(
+        Globals.get(), reinterpret_cast<const char *>(&Module->min_mem_pages),
+        sizeof(Module->min_mem_pages)));
+
     Globals->push_back(WasmMemory);
+    Globals->push_back(GlobalDataSize);
+    Globals->push_back(GlobalNumPages);
 
     lowerGlobals(std::move(Globals));
   }