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

src/WasmTranslator.cpp

 //===- subzero/src/WasmTranslator.cpp - WASM to Subzero Translation -------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 1047 matching lines @@
     LOG(out << "Call Result = " << Node(Dest) << "\n");
     return OperandNode(Dest);
   }
   Node CallIndirect(uint32_t SigIndex, Node *Args) {
     LOG(out << "CallIndirect(" << SigIndex << ")\n");
     // TODO(eholk): Compile to something better than a switch.
     const auto *Module = this->Module->module;
     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());
 
     auto *Switch = InstSwitch::create(Func, IndirectTable.size(),
                                       Args[0].toOperand(), Abort);
     assert(Abort);
 
     const bool HasReturn = Module->signatures[SigIndex]->return_count() != 0;
     const Ice::Type DestTy =
         HasReturn ? toIceType(Module->signatures[SigIndex]->GetReturn())
@@ skipping 49 matching lines @@
     llvm::report_fatal_error("LoadGlobal");
   }
   Node StoreGlobal(uint32_t Index, Node Val) {
     (void)Index;
     (void)Val;
     llvm::report_fatal_error("StoreGlobal");
   }
 
   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(IceType_i32);

[Jim Stichnoth, 2016/04/23 16:23:04]

Maybe use getPointerType() instead of IceType_i32, to be a bit more
future-proof?

[Eric Holk, 2016/04/25 19:53:03]

Done.

+      }
       Base = Ctx->getConstantInt32(RealOffset);
       ConstZeroBase = (0 == RealOffset);
     } else if (0 != Offset) {
       auto *Addr = makeVariable(Ice::getPointerType());
       auto *OffsetConstant = Ctx->getConstantInt32(Offset);
       Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
                                                    Addr, Base, OffsetConstant));
 
       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://goto.google.com/aqydy).  Try adding a new

[Jim Stichnoth, 2016/04/23 16:23:04]

Use a link that is externally viewable...

[Eric Holk, 2016/04/25 19:53:03]

I thought goto was, but just to be safe, I switched it to a goo.gl link.

+      // 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;
     auto MemBase = Ctx->getConstantSym(0, Ctx->getGlobalString("WASM_MEMORY"));
     if (!ConstZeroBase) {
       auto RealAddrV = Func->makeVariable(Ice::getPointerType());
       Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
                                                    RealAddrV, Base, MemBase));
 
       RealAddr = RealAddrV;
@@ skipping 79 matching lines @@
   void set_effect_ptr(Node *Effect) { this->EffectPtr = Effect; }
 
 private:
   wasm::ModuleEnv *Module;
   Node *ControlPtr;
   Node *EffectPtr;
 
   class Cfg *Func;
   GlobalContext *Ctx;
 
+  CfgNode *AbortTarget = nullptr;
+
   SizeT NextArg = 0;
 
   CfgUnorderedMap<Operand *, InstPhi *> PhiMap;
   CfgUnorderedMap<Operand *, CfgNode *> DefNodeMap;
 
   InstPhi *getDefiningInst(Operand *Op) const {
     const auto &Iter = PhiMap.find(Op);
     if (Iter == PhiMap.end()) {
       return nullptr;
     }
@@ skipping 16 matching lines @@
   }
 
   CfgNode *getDefNode(Operand *Op) const {
     const auto &Iter = DefNodeMap.find(Op);
     if (Iter == DefNodeMap.end()) {
       return nullptr;
     }
     return Iter->second;
   }
 
+  CfgNode *getAbortTarget() {
+    if (!AbortTarget) {
+      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());
       Ctx->getStrDump().flush();
     }
   }
 };
 
 std::unique_ptr<Cfg> WasmTranslator::translateFunction(Zone *Zone,
                                                        FunctionBody &Body) {
@@ skipping 153 matching lines @@
 
       // Add the data
       WasmMemory->addInitializer(VariableDeclaration::DataInitializer::create(
           Globals.get(), reinterpret_cast<const char *>(Module->module_start) +
                              Seg.source_offset,
           Seg.source_size));
 
       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) {
       WasmMemory->addInitializer(VariableDeclaration::ZeroInitializer::create(
           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));
   }
 
   // Translate each function.
   for (const auto Fn : Module->functions) {
     const auto FnName = getFunctionName(Module, Fn.func_index);
 
     LOG(out << "  " << Fn.func_index << ": " << FnName << "...");
 
     Body.sig = Fn.sig;
     Body.base = Buffer.get();
     Body.start = Buffer.get() + Fn.code_start_offset;
     Body.end = Buffer.get() + Fn.code_end_offset;
 
     auto Func = translateFunction(&Zone, Body);
     Func->setFunctionName(Ctx->getGlobalString(FnName));
 
     Ctx->optQueueBlockingPush(makeUnique<CfgOptWorkItem>(std::move(Func)));
     LOG(out << "done.\n");
   }
 
   return;
 }
 
 #endif // ALLOW_WASM