Bug 1253344: Defer br/br_if/br_table then-block definition to avoid indirections; r=sunfish
authorBenjamin Bouvier <benj@benj.me>
Wed, 23 Mar 2016 19:57:58 +0100
changeset 290178 84196783659ed24425afdb6079ab1a7ff366e716
parent 290177 189899f5bdf6f266e7376d087347b46ed3332fb3
child 290179 dc60c84a3b2f1071a87d3fa781eb05246b210c7f
push id19656
push usergwagner@mozilla.com
push dateMon, 04 Apr 2016 13:43:23 +0000
treeherderb2g-inbound@e99061fde28a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs1253344
milestone48.0a1
Bug 1253344: Defer br/br_if/br_table then-block definition to avoid indirections; r=sunfish MozReview-Commit-ID: FeXMs4M7jHJ
js/src/asmjs/WasmIonCompile.cpp
js/src/jit/IonAnalysis.cpp
js/src/jit/MIR.cpp
js/src/jit/MIR.h
--- a/js/src/asmjs/WasmIonCompile.cpp
+++ b/js/src/asmjs/WasmIonCompile.cpp
@@ -31,34 +31,44 @@ using mozilla::Maybe;
 typedef Vector<MBasicBlock*, 8, SystemAllocPolicy> BlockVector;
 
 // Encapsulates the compilation of a single function in an asm.js module. The
 // function compiler handles the creation and final backend compilation of the
 // MIR graph.
 class FunctionCompiler
 {
   private:
-    typedef Vector<BlockVector, 0, SystemAllocPolicy> BlocksVector;
+    struct ControlFlowPatch {
+        MControlInstruction* ins;
+        uint32_t index;
+        ControlFlowPatch(MControlInstruction* ins, uint32_t index)
+          : ins(ins),
+            index(index)
+        {}
+    };
+
+    typedef Vector<ControlFlowPatch, 0, SystemAllocPolicy> ControlFlowPatchVector;
+    typedef Vector<ControlFlowPatchVector, 0, SystemAllocPolicy> ControlFlowPatchsVector;
 
     ModuleGeneratorThreadView& mg_;
     Decoder&                   decoder_;
     const FuncBytes&           func_;
     const ValTypeVector&       locals_;
     size_t                     lastReadCallSite_;
 
     TempAllocator&             alloc_;
     MIRGraph&                  graph_;
     const CompileInfo&         info_;
     MIRGenerator&              mirGen_;
 
     MBasicBlock*               curBlock_;
 
     uint32_t                   loopDepth_;
     uint32_t                   blockDepth_;
-    BlocksVector               targets_;
+    ControlFlowPatchsVector    blockPatches_;
 
     FuncCompileResults&        compileResults_;
 
   public:
     FunctionCompiler(ModuleGeneratorThreadView& mg,
                      Decoder& decoder,
                      const FuncBytes& func,
                      const ValTypeVector& locals,
@@ -143,18 +153,18 @@ class FunctionCompiler
         return true;
     }
 
     void checkPostconditions()
     {
         MOZ_ASSERT(loopDepth_ == 0);
         MOZ_ASSERT(blockDepth_ == 0);
 #ifdef DEBUG
-        for (BlockVector& vec : targets_) {
-            MOZ_ASSERT(vec.empty());
+        for (ControlFlowPatchVector& patches : blockPatches_) {
+            MOZ_ASSERT(patches.empty());
         }
 #endif
         MOZ_ASSERT(inDeadCode());
         MOZ_ASSERT(decoder_.done(), "all bytes must be consumed");
         MOZ_ASSERT(func_.callSiteLineNums().length() == lastReadCallSite_);
     }
 
     /************************* Read-only interface (after local scope setup) */
@@ -1008,17 +1018,17 @@ class FunctionCompiler
             *def = curBlock_->pop();
         else
             *def = nullptr;
         return true;
     }
 
     bool startBlock()
     {
-        MOZ_ASSERT_IF(blockDepth_ < targets_.length(), targets_[blockDepth_].empty());
+        MOZ_ASSERT_IF(blockDepth_ < blockPatches_.length(), blockPatches_[blockDepth_].empty());
         blockDepth_++;
         return true;
     }
 
     bool finishBlock()
     {
         MOZ_ASSERT(blockDepth_);
         uint32_t topLabel = --blockDepth_;
@@ -1076,18 +1086,19 @@ class FunctionCompiler
                 phi->setUnused();
         }
 
         // The loop result may also be referencing a recycled phi.
         if (*loopResult && (*loopResult)->isUnused())
             *loopResult = (*loopResult)->toPhi()->getOperand(0);
 
         // Fix up phis stored in the slots Vector of pending blocks.
-        for (BlockVector& vec : targets_) {
-            for (MBasicBlock* block : vec) {
+        for (ControlFlowPatchVector& patches : blockPatches_) {
+            for (ControlFlowPatch& p : patches) {
+                MBasicBlock* block = p.ins->block();
                 if (block->loopDepth() >= loopEntry->loopDepth())
                     fixupRedundantPhis(block);
             }
         }
 
         // The loop body, if any, might be referencing recycled phis too.
         if (loopBody)
             fixupRedundantPhis(loopBody);
@@ -1112,18 +1123,18 @@ class FunctionCompiler
         MOZ_ASSERT(blockDepth_ >= 2);
         MOZ_ASSERT(loopDepth_);
 
         uint32_t headerLabel = blockDepth_ - 1;
         uint32_t afterLabel = blockDepth_ - 2;
 
         if (!loopHeader) {
             MOZ_ASSERT(inDeadCode());
-            MOZ_ASSERT(afterLabel >= targets_.length() || targets_[afterLabel].empty());
-            MOZ_ASSERT(headerLabel >= targets_.length() || targets_[headerLabel].empty());
+            MOZ_ASSERT(afterLabel >= blockPatches_.length() || blockPatches_[afterLabel].empty());
+            MOZ_ASSERT(headerLabel >= blockPatches_.length() || blockPatches_[headerLabel].empty());
             blockDepth_ -= 2;
             loopDepth_--;
             return true;
         }
 
         // Expr::Loop doesn't have an implicit backedge so temporarily set
         // aside the end of the loop body to bind backedges.
         MBasicBlock* loopBody = curBlock_;
@@ -1159,113 +1170,95 @@ class FunctionCompiler
                 return false;
             curBlock_ = out;
         }
 
         blockDepth_ -= 2;
         return true;
     }
 
-    bool startSwitch(MDefinition* expr, uint32_t numCases, MBasicBlock** switchBlock)
-    {
-        if (inDeadCode()) {
-            *switchBlock = nullptr;
-            return true;
-        }
-        MOZ_ASSERT(numCases <= INT32_MAX);
-        MOZ_ASSERT(numCases);
-        curBlock_->end(MTableSwitch::New(alloc(), expr, 0, int32_t(numCases - 1)));
-        *switchBlock = curBlock_;
-        curBlock_ = nullptr;
-        return true;
-    }
-
-    bool startSwitchCase(MBasicBlock* switchBlock, MBasicBlock** next)
-    {
-        MOZ_ASSERT(inDeadCode());
-        if (!switchBlock) {
-            *next = nullptr;
-            return true;
-        }
-        if (!newBlock(switchBlock, next))
+    bool addControlFlowPatch(MControlInstruction* ins, uint32_t relative, uint32_t index) {
+        MOZ_ASSERT(relative < blockDepth_);
+        uint32_t absolute = blockDepth_ - 1 - relative;
+
+        if (absolute >= blockPatches_.length() && !blockPatches_.resize(absolute + 1))
             return false;
-        curBlock_ = *next;
-        return true;
-    }
-
-    bool joinSwitch(MBasicBlock* switchBlock, const BlockVector& cases, MBasicBlock* defaultBlock)
-    {
-        MOZ_ASSERT(inDeadCode());
-        if (!switchBlock)
-            return true;
-
-        MTableSwitch* mir = switchBlock->lastIns()->toTableSwitch();
-        size_t defaultIndex;
-        if (!mir->addDefault(defaultBlock, &defaultIndex))
-            return false;
-
-        for (MBasicBlock* caseBlock : cases) {
-            if (!caseBlock) {
-                if (!mir->addCase(defaultIndex))
-                    return false;
-            } else {
-                size_t caseIndex;
-                if (!mir->addSuccessor(caseBlock, &caseIndex))
-                    return false;
-                if (!mir->addCase(caseIndex))
-                    return false;
-            }
-        }
-
-        return true;
+
+        return blockPatches_[absolute].append(ControlFlowPatch(ins, index));
     }
 
     bool br(uint32_t relativeDepth)
     {
         if (inDeadCode())
             return true;
 
-        MOZ_ASSERT(relativeDepth < blockDepth_);
-        uint32_t absolute = blockDepth_ - 1 - relativeDepth;
-        if (absolute >= targets_.length()) {
-            if (!targets_.resize(absolute + 1))
-                return false;
-        }
-
-        if (!targets_[absolute].append(curBlock_))
+        MGoto* jump = MGoto::NewAsm(alloc());
+        if (!addControlFlowPatch(jump, relativeDepth, MGoto::TargetIndex))
             return false;
 
+        curBlock_->end(jump);
         curBlock_ = nullptr;
         return true;
     }
 
     bool brIf(uint32_t relativeDepth, MDefinition* condition)
     {
         if (inDeadCode())
             return true;
 
-        // TODO (bug 1253334): we could use MTest with the right jump target,
-        // here. If it's backward, it's trivial; if it's forward, we need to
-        // memorize it, then fix it later when we actually encounter the target.
-        MBasicBlock* thenBlock = nullptr;
         MBasicBlock* joinBlock = nullptr;
-        if (!newBlock(curBlock_, &thenBlock))
-            return false;
         if (!newBlock(curBlock_, &joinBlock))
             return false;
 
-        curBlock_->end(MTest::New(alloc(), condition, thenBlock, joinBlock));
-        curBlock_ = thenBlock;
-        mirGraph().moveBlockToEnd(curBlock_);
-
-        if (!br(relativeDepth))
+        MTest* test = MTest::NewAsm(alloc(), condition, joinBlock);
+        if (!addControlFlowPatch(test, relativeDepth, MTest::TrueBranchIndex))
+            return false;
+
+        curBlock_->end(test);
+        curBlock_ = joinBlock;
+        return true;
+    }
+
+    bool brTable(MDefinition* expr, uint32_t defaultDepth, const Uint32Vector& depths)
+    {
+        if (inDeadCode())
+            return true;
+
+        size_t numCases = depths.length();
+        MOZ_ASSERT(numCases <= INT32_MAX);
+        MOZ_ASSERT(numCases);
+
+        MTableSwitch* table = MTableSwitch::New(alloc(), expr, 0, int32_t(numCases - 1));
+
+        size_t defaultIndex;
+        if (!table->addDefault(nullptr, &defaultIndex))
             return false;
-
-        MOZ_ASSERT(inDeadCode());
-        curBlock_ = joinBlock;
+        if (!addControlFlowPatch(table, defaultDepth, defaultIndex))
+            return false;
+
+        for (size_t i = 0; i < numCases; i++) {
+            uint32_t depth = depths[i];
+            if (depth == defaultDepth) {
+                if (!table->addCase(defaultIndex))
+                    return false;
+                continue;
+            }
+
+            size_t caseIndex;
+            if (!table->addSuccessor(nullptr, &caseIndex))
+                return false;
+            if (!table->addCase(caseIndex))
+                return false;
+            if (!addControlFlowPatch(table, depth, caseIndex))
+                return false;
+        }
+
+        curBlock_->end(table);
+        curBlock_ = nullptr;
+
         return true;
     }
 
     /************************************************************ DECODING ***/
 
     uint8_t        readU8()       { return decoder_.uncheckedReadFixedU8(); }
     uint32_t       readU32()      { return decoder_.uncheckedReadFixedU32(); }
     uint32_t       readVarS32()   { return decoder_.uncheckedReadVarS32(); }
@@ -1324,36 +1317,42 @@ class FunctionCompiler
         MOZ_ASSERT(prev);
         MOZ_ASSERT(next);
         prev->end(MGoto::New(alloc(), next));
         return next->addPredecessor(alloc(), prev);
     }
 
     bool bindBranches(uint32_t absolute)
     {
-        if (absolute >= targets_.length() || targets_[absolute].empty())
+        if (absolute >= blockPatches_.length())
+            return true;
+
+        ControlFlowPatchVector& patches = blockPatches_[absolute];
+        if (patches.empty())
             return true;
 
-        BlockVector& preds = targets_[absolute];
-
-        MBasicBlock* join;
-        if (!goToNewBlock(preds[0], &join))
+        MBasicBlock* join = nullptr;
+        MControlInstruction* ins = patches[0].ins;
+        if (!newBlock(ins->block(), &join))
             return false;
-        for (size_t i = 1; i < preds.length(); i++) {
-            if (!mirGen_.ensureBallast())
+
+        ins->replaceSuccessor(patches[0].index, join);
+
+        for (size_t i = 1; i < patches.length(); i++) {
+            ins = patches[i].ins;
+            if (!join->addPredecessor(alloc(), ins->block()))
                 return false;
-            if (!goToExistingBlock(preds[i], join))
-                return false;
+            ins->replaceSuccessor(patches[i].index, join);
         }
 
         if (curBlock_ && !goToExistingBlock(curBlock_, join))
             return false;
         curBlock_ = join;
 
-        preds.clear();
+        patches.clear();
         return true;
     }
 };
 
 static bool
 EmitLiteral(FunctionCompiler& f, ValType type, MDefinition** def)
 {
     switch (type) {
@@ -2579,20 +2578,16 @@ EmitIfElse(FunctionCompiler& f, Expr op,
     return f.joinIfElse(elseDef, &blocks, def);
 }
 
 static bool
 EmitBrTable(FunctionCompiler& f, MDefinition** def)
 {
     uint32_t numCases = f.readVarU32();
 
-    BlockVector cases;
-    if (!cases.resize(numCases))
-        return false;
-
     Uint32Vector depths;
     if (!depths.resize(numCases))
         return false;
 
     for (size_t i = 0; i < numCases; i++)
         depths[i] = f.readU32();
 
     uint32_t defaultDepth = f.readU32();
@@ -2602,44 +2597,17 @@ EmitBrTable(FunctionCompiler& f, MDefini
         return false;
 
     *def = nullptr;
 
     // Empty table
     if (!numCases)
         return f.br(defaultDepth);
 
-    MBasicBlock* switchBlock;
-    if (!f.startSwitch(index, numCases, &switchBlock))
-        return false;
-
-    MBasicBlock* defaultBlock = nullptr;
-    if (!f.startSwitchCase(switchBlock, &defaultBlock))
-        return false;
-    if (!f.br(defaultDepth))
-        return false;
-
-    // TODO (bug 1253334): we could avoid one indirection here, by
-    // jump-threading by hand the jump to the right enclosing block.
-    for (uint32_t i = 0; i < numCases; i++) {
-        uint32_t depth = depths[i];
-        // Don't emit blocks for the default case, to reduce the number of
-        // MBasicBlocks created.
-        if (depth == defaultDepth)
-            continue;
-        if (!f.startSwitchCase(switchBlock, &cases[i]))
-            return false;
-        if (!f.br(depth))
-            return false;
-    }
-
-    if (!f.joinSwitch(switchBlock, cases, defaultBlock))
-        return false;
-
-    return true;
+    return f.brTable(index, defaultDepth, depths);
 }
 
 static bool
 EmitReturn(FunctionCompiler& f, MDefinition** def)
 {
     ExprType ret = f.sig().ret();
 
     if (IsVoid(ret)) {
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -2388,16 +2388,18 @@ jit::AssertBasicGraphCoherency(MIRGraph&
         MOZ_ASSERT(control->block() == *block);
         MOZ_ASSERT(!control->hasUses());
         MOZ_ASSERT(control->type() == MIRType_None);
         MOZ_ASSERT(!control->isDiscarded());
         MOZ_ASSERT(!control->isRecoveredOnBailout());
         MOZ_ASSERT(control->resumePoint() == nullptr);
         for (uint32_t i = 0, end = control->numOperands(); i < end; i++)
             CheckOperand(control, control->getUseFor(i), &usesBalance);
+        for (size_t i = 0; i < control->numSuccessors(); i++)
+            MOZ_ASSERT(control->getSuccessor(i));
     }
 
     // In case issues, see the _DEBUG_CHECK_OPERANDS_USES_BALANCE macro above.
     MOZ_ASSERT(usesBalance <= 0, "More use checks than operand checks");
     MOZ_ASSERT(usesBalance >= 0, "More operand checks than use checks");
     MOZ_ASSERT(graph.numBlocks() == count);
 #endif
 }
--- a/js/src/jit/MIR.cpp
+++ b/js/src/jit/MIR.cpp
@@ -346,16 +346,22 @@ MaybeCallable(CompilerConstraintList* co
 }
 
 MTest*
 MTest::New(TempAllocator& alloc, MDefinition* ins, MBasicBlock* ifTrue, MBasicBlock* ifFalse)
 {
     return new(alloc) MTest(ins, ifTrue, ifFalse);
 }
 
+MTest*
+MTest::NewAsm(TempAllocator& alloc, MDefinition* ins, MBasicBlock* ifFalse)
+{
+    return new(alloc) MTest(ins, nullptr, ifFalse);
+}
+
 void
 MTest::cacheOperandMightEmulateUndefined(CompilerConstraintList* constraints)
 {
     MOZ_ASSERT(operandMightEmulateUndefined());
 
     if (!getOperand(0)->maybeEmulatesUndefined(constraints))
         markNoOperandEmulatesUndefined();
 }
@@ -1382,18 +1388,22 @@ MCloneLiteral::New(TempAllocator& alloc,
 {
     return new(alloc) MCloneLiteral(obj);
 }
 
 void
 MControlInstruction::printOpcode(GenericPrinter& out) const
 {
     MDefinition::printOpcode(out);
-    for (size_t j = 0; j < numSuccessors(); j++)
-        out.printf(" block%u", getSuccessor(j)->id());
+    for (size_t j = 0; j < numSuccessors(); j++) {
+        if (getSuccessor(j))
+            out.printf(" block%u", getSuccessor(j)->id());
+        else
+            out.printf(" (null-to-be-patched)");
+    }
 }
 
 void
 MCompare::printOpcode(GenericPrinter& out) const
 {
     MDefinition::printOpcode(out);
     out.printf(" %s", CodeName[jsop()]);
 }
@@ -1828,16 +1838,22 @@ MTableSwitch::New(TempAllocator& alloc, 
 
 MGoto*
 MGoto::New(TempAllocator& alloc, MBasicBlock* target)
 {
     MOZ_ASSERT(target);
     return new(alloc) MGoto(target);
 }
 
+MGoto*
+MGoto::NewAsm(TempAllocator& alloc)
+{
+    return new(alloc) MGoto(nullptr);
+}
+
 void
 MUnbox::printOpcode(GenericPrinter& out) const
 {
     PrintOpcodeName(out, op());
     out.printf(" ");
     getOperand(0)->printName(out);
     out.printf(" ");
 
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -2808,16 +2808,21 @@ class MGoto
     explicit MGoto(MBasicBlock* target) {
         setSuccessor(0, target);
     }
 
   public:
     INSTRUCTION_HEADER(Goto)
     static MGoto* New(TempAllocator& alloc, MBasicBlock* target);
 
+    // Factory for asm, which may patch the target later.
+    static MGoto* NewAsm(TempAllocator& alloc);
+
+    static const size_t TargetIndex = 0;
+
     MBasicBlock* target() {
         return getSuccessor(0);
     }
     AliasSet getAliasSet() const override {
         return AliasSet::None();
     }
 };
 
@@ -2835,29 +2840,34 @@ NegateBranchDirection(BranchDirection di
 // Tests if the input instruction evaluates to true or false, and jumps to the
 // start of a corresponding basic block.
 class MTest
   : public MAryControlInstruction<1, 2>,
     public TestPolicy::Data
 {
     bool operandMightEmulateUndefined_;
 
-    MTest(MDefinition* ins, MBasicBlock* if_true, MBasicBlock* if_false)
+    MTest(MDefinition* ins, MBasicBlock* trueBranch, MBasicBlock* falseBranch)
       : operandMightEmulateUndefined_(true)
     {
         initOperand(0, ins);
-        setSuccessor(0, if_true);
-        setSuccessor(1, if_false);
+        setSuccessor(0, trueBranch);
+        setSuccessor(1, falseBranch);
     }
 
   public:
     INSTRUCTION_HEADER(Test)
     static MTest* New(TempAllocator& alloc, MDefinition* ins,
                       MBasicBlock* ifTrue, MBasicBlock* ifFalse);
 
+    // Factory for asm, which may patch the ifTrue branch later.
+    static MTest* NewAsm(TempAllocator& alloc, MDefinition* ins, MBasicBlock* ifFalse);
+
+    static const size_t TrueBranchIndex = 0;
+
     MDefinition* input() const {
         return getOperand(0);
     }
     MBasicBlock* ifTrue() const {
         return getSuccessor(0);
     }
     MBasicBlock* ifFalse() const {
         return getSuccessor(1);