Bug 1004363 - IonMonkey: Eliminate the UnsplitEdges pass and just have Codegen know how to skip past trivial blocks. r=mjrosenb
authorDan Gohman <sunfish@mozilla.com>
Tue, 20 May 2014 20:28:49 -0700
changeset 203277 71da35d73be5b3c6c2185437a1e35a8d78095ba4
parent 203276 aa35d4e17c822c4eeecfd665af54b86d67d57376
child 203278 efa8579fe73a883ea656c1c98e62e4d1fdc238a0
push id3741
push userasasaki@mozilla.com
push dateMon, 21 Jul 2014 20:25:18 +0000
treeherdermozilla-beta@4d6f46f5af68 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmjrosenb
bugs1004363
milestone32.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1004363 - IonMonkey: Eliminate the UnsplitEdges pass and just have Codegen know how to skip past trivial blocks. r=mjrosenb
js/src/jit/CodeGenerator.cpp
js/src/jit/Ion.cpp
js/src/jit/IonAnalysis.cpp
js/src/jit/IonAnalysis.h
js/src/jit/LIR.h
js/src/jit/mips/CodeGenerator-mips.cpp
js/src/jit/shared/CodeGenerator-shared.cpp
js/src/jit/shared/CodeGenerator-shared.h
js/src/jit/shared/CodeGenerator-x86-shared.cpp
js/src/vm/TraceLogging.cpp
js/src/vm/TraceLogging.h
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -639,16 +639,19 @@ CodeGenerator::testValueTruthy(const Val
 {
     testValueTruthyKernel(value, scratch1, scratch2, fr, ifTruthy, ifFalsy, ool, valueMIR);
     masm.jump(ifTruthy);
 }
 
 Label *
 CodeGenerator::getJumpLabelForBranch(MBasicBlock *block)
 {
+    // Skip past trivial blocks.
+    block = skipTrivialBlocks(block);
+
     if (!labelForBackedgeWithImplicitCheck(block))
         return block->lir()->label();
 
     // We need to use a patchable jump for this backedge, but want to treat
     // this as a normal label target to simplify codegen. Efficiency isn't so
     // important here as these tests are extremely unlikely to be used in loop
     // backedges, so emit inline code for the patchable jump. Heap allocating
     // the label allows it to be used by out of line blocks.
@@ -712,27 +715,27 @@ CodeGenerator::visitFunctionDispatch(LFu
     Register input = ToRegister(lir->input());
     Label *lastLabel;
     size_t casesWithFallback;
 
     // Determine if the last case is fallback or an ordinary case.
     if (!mir->hasFallback()) {
         JS_ASSERT(mir->numCases() > 0);
         casesWithFallback = mir->numCases();
-        lastLabel = mir->getCaseBlock(mir->numCases() - 1)->lir()->label();
+        lastLabel = skipTrivialBlocks(mir->getCaseBlock(mir->numCases() - 1))->lir()->label();
     } else {
         casesWithFallback = mir->numCases() + 1;
-        lastLabel = mir->getFallback()->lir()->label();
+        lastLabel = skipTrivialBlocks(mir->getFallback())->lir()->label();
     }
 
     // Compare function pointers, except for the last case.
     for (size_t i = 0; i < casesWithFallback - 1; i++) {
         JS_ASSERT(i < mir->numCases());
         JSFunction *func = mir->getCase(i);
-        LBlock *target = mir->getCaseBlock(i)->lir();
+        LBlock *target = skipTrivialBlocks(mir->getCaseBlock(i))->lir();
         masm.branchPtr(Assembler::Equal, input, ImmGCPtr(func), target->label());
     }
 
     // Jump to the last case.
     masm.jump(lastLabel);
 
     return true;
 }
@@ -746,31 +749,31 @@ CodeGenerator::visitTypeObjectDispatch(L
 
     // Hold the incoming TypeObject.
     masm.loadPtr(Address(input, JSObject::offsetOfType()), temp);
 
     // Compare TypeObjects.
     InlinePropertyTable *propTable = mir->propTable();
     for (size_t i = 0; i < mir->numCases(); i++) {
         JSFunction *func = mir->getCase(i);
-        LBlock *target = mir->getCaseBlock(i)->lir();
+        LBlock *target = skipTrivialBlocks(mir->getCaseBlock(i))->lir();
 
         DebugOnly<bool> found = false;
         for (size_t j = 0; j < propTable->numEntries(); j++) {
             if (propTable->getFunction(j) != func)
                 continue;
             types::TypeObject *typeObj = propTable->getTypeObject(j);
             masm.branchPtr(Assembler::Equal, temp, ImmGCPtr(typeObj), target->label());
             found = true;
         }
         JS_ASSERT(found);
     }
 
     // Unknown function: jump to fallback block.
-    LBlock *fallback = mir->getFallback()->lir();
+    LBlock *fallback = skipTrivialBlocks(mir->getFallback())->lir();
     masm.jump(fallback->label());
     return true;
 }
 
 bool
 CodeGenerator::visitBooleanToString(LBooleanToString *lir)
 {
     Register input = ToRegister(lir->input());
@@ -1258,17 +1261,17 @@ CodeGenerator::visitInterruptCheckImplic
     masm.bind(ool->rejoin());
     return true;
 }
 
 bool
 CodeGenerator::visitTableSwitch(LTableSwitch *ins)
 {
     MTableSwitch *mir = ins->mir();
-    Label *defaultcase = mir->getDefault()->lir()->label();
+    Label *defaultcase = skipTrivialBlocks(mir->getDefault())->lir()->label();
     const LAllocation *temp;
 
     if (mir->getOperand(0)->type() != MIRType_Int32) {
         temp = ins->tempInt()->output();
 
         // The input is a double, so try and convert it to an integer.
         // If it does not fit in an integer, take the default case.
         masm.convertDoubleToInt32(ToFloatRegister(ins->index()), ToRegister(temp), defaultcase, false);
@@ -1278,17 +1281,17 @@ CodeGenerator::visitTableSwitch(LTableSw
 
     return emitTableSwitchDispatch(mir, ToRegister(temp), ToRegisterOrInvalid(ins->tempPointer()));
 }
 
 bool
 CodeGenerator::visitTableSwitchV(LTableSwitchV *ins)
 {
     MTableSwitch *mir = ins->mir();
-    Label *defaultcase = mir->getDefault()->lir()->label();
+    Label *defaultcase = skipTrivialBlocks(mir->getDefault())->lir()->label();
 
     Register index = ToRegister(ins->tempInt());
     ValueOperand value = ToValue(ins, LTableSwitchV::InputValue);
     Register tag = masm.extractTag(value, index);
     masm.branchTestNumber(Assembler::NotEqual, tag, defaultcase);
 
     Label unboxInt, isInt;
     masm.branchTestInt32(Assembler::Equal, tag, &unboxInt);
@@ -3360,16 +3363,23 @@ CodeGenerator::generateBody()
 #if defined(JS_ION_PERF)
     PerfSpewer *perfSpewer = &perfSpewer_;
     if (gen->compilingAsmJS())
         perfSpewer = &gen->perfSpewer();
 #endif
 
     for (size_t i = 0; i < graph.numBlocks(); i++) {
         current = graph.getBlock(i);
+
+        // Don't emit any code for trivial blocks, containing just a goto. Such
+        // blocks are created to split critical edges, and if we didn't end up
+        // putting any instructions in them, we can skip them.
+        if (current->isTrivial())
+            continue; 
+
         masm.bind(current->label());
 
         mozilla::Maybe<ScriptCountBlockState> blockCounts;
         if (counts) {
             blockCounts.construct(&counts->block(i), &masm);
             if (!blockCounts.ref().init())
                 return false;
         }
--- a/js/src/jit/Ion.cpp
+++ b/js/src/jit/Ion.cpp
@@ -1626,26 +1626,16 @@ GenerateLIR(MIRGenerator *mir)
           default:
             MOZ_ASSUME_UNREACHABLE("Bad regalloc");
         }
 
         if (mir->shouldCancel("Allocate Registers"))
             return nullptr;
     }
 
-    {
-        AutoTraceLog log(logger, TraceLogger::UnsplitEdges);
-        // Now that all optimization and register allocation is done, re-introduce
-        // critical edges to avoid unnecessary jumps.
-        if (!UnsplitEdges(lir))
-            return nullptr;
-        IonSpewPass("Unsplit Critical Edges");
-        AssertBasicGraphCoherency(graph);
-    }
-
     return lir;
 }
 
 CodeGenerator *
 GenerateCode(MIRGenerator *mir, LIRGraph *lir)
 {
     TraceLogger *logger;
     if (GetIonContext()->runtime->onMainThread())
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -1909,107 +1909,16 @@ jit::EliminateRedundantChecks(MIRGraph &
         }
         index++;
     }
 
     JS_ASSERT(index == graph.numBlocks());
     return true;
 }
 
-// If the given block contains a goto and nothing interesting before that,
-// return the goto. Return nullptr otherwise.
-static LGoto *
-FindLeadingGoto(LBlock *bb)
-{
-    for (LInstructionIterator ins(bb->begin()); ins != bb->end(); ins++) {
-        // Ignore labels.
-        if (ins->isLabel())
-            continue;
-        // If we have a goto, we're good to go.
-        if (ins->isGoto())
-            return ins->toGoto();
-        break;
-    }
-    return nullptr;
-}
-
-// Eliminate blocks containing nothing interesting besides gotos. These are
-// often created by optimizer, which splits all critical edges. If these
-// splits end up being unused after optimization and register allocation,
-// fold them back away to avoid unnecessary branching.
-bool
-jit::UnsplitEdges(LIRGraph *lir)
-{
-    for (size_t i = 0; i < lir->numBlocks(); i++) {
-        LBlock *bb = lir->getBlock(i);
-        MBasicBlock *mirBlock = bb->mir();
-
-        // Renumber the MIR blocks as we go, since we may remove some.
-        mirBlock->setId(i);
-
-        // Register allocation is done by this point, so we don't need the phis
-        // anymore. Clear them to avoid needed to keep them current as we edit
-        // the CFG.
-        bb->clearPhis();
-        mirBlock->discardAllPhis();
-
-        // First make sure the MIR block looks sane. Some of these checks may be
-        // over-conservative, but we're attempting to keep everything in MIR
-        // current as we modify the LIR, so only proceed if the MIR is simple.
-        if (mirBlock->numPredecessors() == 0 || mirBlock->numSuccessors() != 1 ||
-            !mirBlock->begin()->isGoto())
-        {
-            continue;
-        }
-
-        // The MIR block is empty, but check the LIR block too (in case the
-        // register allocator inserted spill code there, or whatever).
-        LGoto *theGoto = FindLeadingGoto(bb);
-        if (!theGoto)
-            continue;
-        MBasicBlock *target = theGoto->target();
-        if (target == mirBlock || target != mirBlock->getSuccessor(0))
-            continue;
-
-        // If we haven't yet cleared the phis for the successor, do so now so
-        // that the CFG manipulation routines don't trip over them.
-        if (!target->phisEmpty()) {
-            target->discardAllPhis();
-            target->lir()->clearPhis();
-        }
-
-        // Edit the CFG to remove lir/mirBlock and reconnect all its edges.
-        for (size_t j = 0; j < mirBlock->numPredecessors(); j++) {
-            MBasicBlock *mirPred = mirBlock->getPredecessor(j);
-
-            for (size_t k = 0; k < mirPred->numSuccessors(); k++) {
-                if (mirPred->getSuccessor(k) == mirBlock) {
-                    mirPred->replaceSuccessor(k, target);
-                    if (!target->addPredecessorWithoutPhis(mirPred))
-                        return false;
-                }
-            }
-
-            LInstruction *predTerm = *mirPred->lir()->rbegin();
-            for (size_t k = 0; k < predTerm->numSuccessors(); k++) {
-                if (predTerm->getSuccessor(k) == mirBlock)
-                    predTerm->setSuccessor(k, target);
-            }
-        }
-        target->removePredecessor(mirBlock);
-
-        // Zap the block.
-        lir->removeBlock(i);
-        lir->mir().removeBlock(mirBlock);
-        --i;
-    }
-
-    return true;
-}
-
 bool
 LinearSum::multiply(int32_t scale)
 {
     for (size_t i = 0; i < terms_.length(); i++) {
         if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale))
             return false;
     }
     return SafeMul(scale, constant_, &constant_);
--- a/js/src/jit/IonAnalysis.h
+++ b/js/src/jit/IonAnalysis.h
@@ -59,19 +59,16 @@ void
 AssertGraphCoherency(MIRGraph &graph);
 
 void
 AssertExtendedGraphCoherency(MIRGraph &graph);
 
 bool
 EliminateRedundantChecks(MIRGraph &graph);
 
-bool
-UnsplitEdges(LIRGraph *lir);
-
 class MDefinition;
 
 // Simple linear sum of the form 'n' or 'x + n'.
 struct SimpleLinearSum
 {
     MDefinition *term;
     int32_t constant;
 
--- a/js/src/jit/LIR.h
+++ b/js/src/jit/LIR.h
@@ -792,22 +792,35 @@ class LBlock : public TempObject
         instructions_.insertAfter(at, ins);
     }
     void insertBefore(LInstruction *at, LInstruction *ins) {
         JS_ASSERT(!at->isLabel());
         instructions_.insertBefore(at, ins);
     }
     uint32_t firstId();
     uint32_t lastId();
+
+    // Return the label to branch to when branching to this block.
     Label *label() {
+        JS_ASSERT(!isTrivial());
         return &label_;
     }
+
     LMoveGroup *getEntryMoveGroup(TempAllocator &alloc);
     LMoveGroup *getExitMoveGroup(TempAllocator &alloc);
 
+    // Test whether this basic block is empty except for a simple goto, and
+    // which is not forming a loop. No code will be emitted for such blocks.
+    bool isTrivial() {
+        LInstructionIterator ins(begin());
+        while (ins->isLabel())
+            ++ins;
+        return ins->isGoto() && !mir()->isLoopHeader();
+    }
+
     void dump(FILE *fp);
     void dump();
 };
 
 template <size_t Defs, size_t Operands, size_t Temps>
 class LInstructionHelper : public LInstruction
 {
     mozilla::Array<LDefinition, Defs> defs_;
--- a/js/src/jit/mips/CodeGenerator-mips.cpp
+++ b/js/src/jit/mips/CodeGenerator-mips.cpp
@@ -81,16 +81,19 @@ CodeGeneratorMIPS::generateEpilogue()
     }
     return true;
 }
 
 void
 CodeGeneratorMIPS::branchToBlock(Assembler::FloatFormat fmt, FloatRegister lhs, FloatRegister rhs,
                                  MBasicBlock *mir, Assembler::DoubleCondition cond)
 {
+    // Skip past trivial blocks.
+    mir = skipTrivialBlocks(mir);
+
     Label *label = mir->lir()->label();
     if (Label *oolEntry = labelForBackedgeWithImplicitCheck(mir)) {
         // Note: the backedge is initially a jump to the next instruction.
         // It will be patched to the target block's label during link().
         RepatchLabel rejoin;
 
         CodeOffsetJump backedge;
         Label skip;
--- a/js/src/jit/shared/CodeGenerator-shared.cpp
+++ b/js/src/jit/shared/CodeGenerator-shared.cpp
@@ -972,16 +972,19 @@ CodeGeneratorShared::labelForBackedgeWit
     }
 
     return nullptr;
 }
 
 void
 CodeGeneratorShared::jumpToBlock(MBasicBlock *mir)
 {
+    // Skip past trivial blocks.
+    mir = skipTrivialBlocks(mir);
+
     // No jump necessary if we can fall through to the next block.
     if (isNextBlock(mir->lir()))
         return;
 
     if (Label *oolEntry = labelForBackedgeWithImplicitCheck(mir)) {
         // Note: the backedge is initially a jump to the next instruction.
         // It will be patched to the target block's label during link().
         RepatchLabel rejoin;
@@ -994,16 +997,19 @@ CodeGeneratorShared::jumpToBlock(MBasicB
     }
 }
 
 // This function is not used for MIPS. MIPS has branchToBlock.
 #ifndef JS_CODEGEN_MIPS
 void
 CodeGeneratorShared::jumpToBlock(MBasicBlock *mir, Assembler::Condition cond)
 {
+    // Skip past trivial blocks.
+    mir = skipTrivialBlocks(mir);
+
     if (Label *oolEntry = labelForBackedgeWithImplicitCheck(mir)) {
         // Note: the backedge is initially a jump to the next instruction.
         // It will be patched to the target block's label during link().
         RepatchLabel rejoin;
         CodeOffsetJump backedge = masm.jumpWithPatch(&rejoin, cond);
         masm.bind(&rejoin);
 
         masm.propagateOOM(patchableBackedges_.append(PatchableBackedgeInfo(backedge, mir->lir()->label(), oolEntry)));
--- a/js/src/jit/shared/CodeGenerator-shared.h
+++ b/js/src/jit/shared/CodeGenerator-shared.h
@@ -303,18 +303,40 @@ class CodeGeneratorShared : public LInst
 
     OutOfLineCode *oolTruncateDouble(FloatRegister src, Register dest);
     bool emitTruncateDouble(FloatRegister src, Register dest);
     bool emitTruncateFloat32(FloatRegister src, Register dest);
 
     void emitPreBarrier(Register base, const LAllocation *index, MIRType type);
     void emitPreBarrier(Address address, MIRType type);
 
+    // We don't emit code for trivial blocks, so if we want to branch to the
+    // given block, and it's trivial, return the ultimate block we should
+    // actually branch directly to.
+    MBasicBlock *skipTrivialBlocks(MBasicBlock *block) {
+        while (block->lir()->isTrivial()) {
+            JS_ASSERT(block->lir()->rbegin()->numSuccessors() == 1);
+            block = block->lir()->rbegin()->getSuccessor(0);
+        }
+        return block;
+    }
+
+    // Test whether the given block can be reached via fallthrough from the
+    // current block.
     inline bool isNextBlock(LBlock *block) {
-        return current->mir()->id() + 1 == block->mir()->id();
+        uint32_t target = skipTrivialBlocks(block->mir())->id();
+        uint32_t i = current->mir()->id() + 1;
+        if (target < i)
+            return false;
+        // Trivial blocks can be crossed via fallthrough.
+        for (; i != target; ++i) {
+            if (!graph.getBlock(i)->isTrivial())
+                return false;
+        }
+        return true;
     }
 
   public:
     // Save and restore all volatile registers to/from the stack, excluding the
     // specified register(s), before a function call made using callWithABI and
     // after storing the function call's return value to an output register.
     // (The only registers that don't need to be saved/restored are 1) the
     // temporary register used to store the return value of the function call,
--- a/js/src/jit/shared/CodeGenerator-x86-shared.cpp
+++ b/js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ -1465,17 +1465,17 @@ CodeGeneratorX86Shared::visitOutOfLineTa
     MTableSwitch *mir = ool->mir();
 
     masm.align(sizeof(void*));
     masm.bind(ool->jumpLabel()->src());
     if (!masm.addCodeLabel(*ool->jumpLabel()))
         return false;
 
     for (size_t i = 0; i < mir->numCases(); i++) {
-        LBlock *caseblock = mir->getCase(i)->lir();
+        LBlock *caseblock = skipTrivialBlocks(mir->getCase(i))->lir();
         Label *caseheader = caseblock->label();
         uint32_t caseoffset = caseheader->offset();
 
         // The entries of the jump table need to be absolute addresses and thus
         // must be patched after codegen is finished.
         CodeLabel cl;
         masm.writeCodePointer(cl.dest());
         cl.src()->bind(caseoffset);
@@ -1484,17 +1484,17 @@ CodeGeneratorX86Shared::visitOutOfLineTa
     }
 
     return true;
 }
 
 bool
 CodeGeneratorX86Shared::emitTableSwitchDispatch(MTableSwitch *mir, Register index, Register base)
 {
-    Label *defaultcase = mir->getDefault()->lir()->label();
+    Label *defaultcase = skipTrivialBlocks(mir->getDefault())->lir()->label();
 
     // Lower value with low value
     if (mir->low() != 0)
         masm.subl(Imm32(mir->low()), index);
 
     // Jump to default case if input is out of range
     int32_t cases = mir->numCases();
     masm.cmpl(index, Imm32(cases));
--- a/js/src/vm/TraceLogging.cpp
+++ b/js/src/vm/TraceLogging.cpp
@@ -850,17 +850,16 @@ TraceLogging::lazyInit()
         enabledTextIds[TraceLogger::LICM] = true;
         enabledTextIds[TraceLogger::RangeAnalysis] = true;
         enabledTextIds[TraceLogger::EffectiveAddressAnalysis] = true;
         enabledTextIds[TraceLogger::EliminateDeadCode] = true;
         enabledTextIds[TraceLogger::EdgeCaseAnalysis] = true;
         enabledTextIds[TraceLogger::EliminateRedundantChecks] = true;
         enabledTextIds[TraceLogger::GenerateLIR] = true;
         enabledTextIds[TraceLogger::RegisterAllocation] = true;
-        enabledTextIds[TraceLogger::UnsplitEdges] = true;
         enabledTextIds[TraceLogger::GenerateCode] = true;
     }
 
     const char *options = getenv("TLOPTIONS");
     if (options) {
         if (strstr(options, "help")) {
             fflush(nullptr);
             printf(
--- a/js/src/vm/TraceLogging.h
+++ b/js/src/vm/TraceLogging.h
@@ -145,17 +145,16 @@ namespace jit {
     _(LICM)                                           \
     _(RangeAnalysis)                                  \
     _(EffectiveAddressAnalysis)                       \
     _(EliminateDeadCode)                              \
     _(EdgeCaseAnalysis)                               \
     _(EliminateRedundantChecks)                       \
     _(GenerateLIR)                                    \
     _(RegisterAllocation)                             \
-    _(UnsplitEdges)                                   \
     _(GenerateCode)                                   \
 
 class AutoTraceLog;
 
 template <class T>
 class ContinuousSpace {
     T *data_;
     uint32_t next_;