Bug 1028580 - Improve code generated for conditional and &&/|| tests, r=jandem,sunfish.
☠☠ backed out by b2a0854d295e ☠ ☠
authorBrian Hackett <bhackett1024@gmail.com>
Tue, 22 Jul 2014 18:34:03 -0800
changeset 217259 9c80c5b76cf074a94da52f8ac69e1b4c41d436e5
parent 217258 ec7f2af2c4d6343ab91dc851bfc4807fbc9fa428
child 217260 5c157de1ee6ce6288d08981c599855e505b676d1
push id3979
push userraliiev@mozilla.com
push dateMon, 13 Oct 2014 16:35:44 +0000
treeherdermozilla-beta@30f2cc610691 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem, sunfish
bugs1028580
milestone34.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 1028580 - Improve code generated for conditional and &&/|| tests, r=jandem,sunfish.
js/src/jit/CodeGenerator.cpp
js/src/jit/Ion.cpp
js/src/jit/IonAnalysis.cpp
js/src/jit/IonAnalysis.h
js/src/jit/MIRGraph.cpp
js/src/jit/MIRGraph.h
js/src/vm/TraceLogging.cpp
js/src/vm/TraceLogging.h
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -3105,17 +3105,17 @@ CodeGenerator::maybeCreateScriptCounts()
             offset = script->pcToOffset(resume->pc());
         }
 
         if (!counts->block(i).init(block->id(), offset, block->numSuccessors())) {
             js_delete(counts);
             return nullptr;
         }
         for (size_t j = 0; j < block->numSuccessors(); j++)
-            counts->block(i).setSuccessor(j, block->getSuccessor(j)->id());
+            counts->block(i).setSuccessor(j, skipTrivialBlocks(block->getSuccessor(j))->id());
     }
 
     scriptCounts_ = counts;
     return counts;
 }
 
 // Structure for managing the state tracked for a block by script counters.
 struct ScriptCountBlockState
--- a/js/src/jit/Ion.cpp
+++ b/js/src/jit/Ion.cpp
@@ -1295,16 +1295,26 @@ OptimizeMIR(MIRGenerator *mir)
     }
 
     IonSpewPass("BuildSSA");
     AssertBasicGraphCoherency(graph);
 
     if (mir->shouldCancel("Start"))
         return false;
 
+    if (!mir->compilingAsmJS()) {
+        AutoTraceLog log(logger, TraceLogger::FoldTests);
+        FoldTests(graph);
+        IonSpewPass("Fold Tests");
+        AssertBasicGraphCoherency(graph);
+
+        if (mir->shouldCancel("Fold Tests"))
+            return false;
+    }
+
     {
         AutoTraceLog log(logger, TraceLogger::SplitCriticalEdges);
         if (!SplitCriticalEdges(graph))
             return false;
         IonSpewPass("Split Critical Edges");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("Split Critical Edges"))
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -20,16 +20,324 @@
 #include "jsobjinlines.h"
 #include "jsopcodeinlines.h"
 
 using namespace js;
 using namespace js::jit;
 
 using mozilla::DebugOnly;
 
+// Return whether a block simply computes the specified constant value.
+static bool
+BlockComputesConstant(MBasicBlock *block, MDefinition *value)
+{
+    // Look for values with no uses. This is used to eliminate constant
+    // computing blocks in condition statements, and the phi which used to
+    // consume the constant has already been removed.
+    if (value->hasUses())
+        return false;
+
+    if (!value->isConstant() || value->block() != block)
+        return false;
+    if (!block->phisEmpty())
+        return false;
+    for (MInstructionIterator iter = block->begin(); iter != block->end(); ++iter) {
+        if (*iter != value || !iter->isGoto())
+            return false;
+    }
+    return true;
+}
+
+// Determine whether a block simply computes a phi and performs a test on it.
+static bool
+BlockIsSingleTest(MBasicBlock *block, MPhi **pphi, MTest **ptest)
+{
+    *pphi = nullptr;
+    *ptest = nullptr;
+
+    MInstruction *ins = *block->begin();
+    if (!ins->isTest())
+        return false;
+    MTest *test = ins->toTest();
+    if (!test->input()->isPhi())
+        return false;
+    MPhi *phi = test->input()->toPhi();
+    if (phi->block() != block)
+        return false;
+
+    for (MUseIterator iter = phi->usesBegin(); iter != phi->usesEnd(); ++iter) {
+        MUse *use = *iter;
+        if (use->consumer() == test)
+            continue;
+        if (use->consumer()->isResumePoint() && use->consumer()->block() == block)
+            continue;
+        return false;
+    }
+
+    for (MPhiIterator iter = block->phisBegin(); iter != block->phisEnd(); ++iter) {
+        if (*iter != phi)
+            return false;
+    }
+
+    *pphi = phi;
+    *ptest = test;
+
+    return true;
+}
+
+// Change block so that it ends in a test of the specified value, going to
+// either ifTrue or ifFalse. existingPred is an existing predecessor of ifTrue
+// or ifFalse with the same values incoming to ifTrue/ifFalse as block.
+// existingPred is not required to be a predecessor of ifTrue/ifFalse if block
+// already ends in a test going to that block on a true/false result.
+static void
+UpdateTestSuccessors(TempAllocator &alloc, MBasicBlock *block,
+                     MDefinition *value, MBasicBlock *ifTrue, MBasicBlock *ifFalse,
+                     MBasicBlock *existingPred)
+{
+    MInstruction *ins = block->lastIns();
+    if (ins->isTest()) {
+        MTest *test = ins->toTest();
+        JS_ASSERT(test->input() == value);
+
+        if (ifTrue != test->ifTrue()) {
+            test->ifTrue()->removePredecessor(block);
+            ifTrue->addPredecessorSameInputsAs(block, existingPred);
+            JS_ASSERT(test->ifTrue() == test->getSuccessor(0));
+            test->replaceSuccessor(0, ifTrue);
+        }
+
+        if (ifFalse != test->ifFalse()) {
+            test->ifFalse()->removePredecessor(block);
+            ifFalse->addPredecessorSameInputsAs(block, existingPred);
+            JS_ASSERT(test->ifFalse() == test->getSuccessor(1));
+            test->replaceSuccessor(1, ifFalse);
+        }
+
+        return;
+    }
+
+    JS_ASSERT(ins->isGoto());
+    ins->toGoto()->target()->removePredecessor(block);
+    block->discardLastIns();
+
+    MTest *test = MTest::New(alloc, value, ifTrue, ifFalse);
+    block->end(test);
+
+    ifTrue->addPredecessorSameInputsAs(block, existingPred);
+    ifFalse->addPredecessorSameInputsAs(block, existingPred);
+}
+
+static void
+MaybeFoldConditionBlock(MIRGraph &graph, MBasicBlock *initialBlock)
+{
+    // Optimize the MIR graph to improve the code generated for conditional
+    // operations. A test like 'if (a ? b : c)' normally requires four blocks,
+    // with a phi for the intermediate value. This can be improved to use three
+    // blocks with no phi value, and if either b or c is constant,
+    // e.g. 'if (a ? b : 0)', then the block associated with that constant
+    // can be eliminated.
+
+    // Look for a diamond pattern:
+    //
+    //       initialBlock
+    //         /     \
+    // trueBranch  falseBranch
+    //         \     /
+    //        testBlock
+    //
+    // Where testBlock contains only a test on a phi combining two values
+    // pushed onto the stack by trueBranch and falseBranch.
+
+    MInstruction *ins = initialBlock->lastIns();
+    if (!ins->isTest())
+        return;
+    MTest *initialTest = ins->toTest();
+
+    MBasicBlock *trueBranch = initialTest->ifTrue();
+    if (trueBranch->numPredecessors() != 1 || trueBranch->numSuccessors() != 1)
+        return;
+    MBasicBlock *falseBranch = initialTest->ifFalse();
+    if (falseBranch->numPredecessors() != 1 || falseBranch->numSuccessors() != 1)
+        return;
+    MBasicBlock *testBlock = trueBranch->getSuccessor(0);
+    if (testBlock != falseBranch->getSuccessor(0))
+        return;
+    if (testBlock->numPredecessors() != 2)
+        return;
+
+    MPhi *phi;
+    MTest *finalTest;
+    if (!BlockIsSingleTest(testBlock, &phi, &finalTest))
+        return;
+
+    if (&testBlock->info() != &initialBlock->info() ||
+        &trueBranch->info() != &initialBlock->info() ||
+        &falseBranch->info() != &initialBlock->info())
+    {
+        return;
+    }
+
+    MDefinition *trueResult = phi->getOperand(testBlock->indexForPredecessor(trueBranch));
+    MDefinition *falseResult = phi->getOperand(testBlock->indexForPredecessor(falseBranch));
+
+    if (trueBranch->stackDepth() != falseBranch->stackDepth())
+        return;
+
+    if (trueBranch->stackDepth() != testBlock->stackDepth() + 1)
+        return;
+
+    if (trueResult != trueBranch->peek(-1) || falseResult != falseBranch->peek(-1))
+        return;
+
+    // OK, we found the desired pattern, now transform the graph.
+
+    // Remove the phi and its inputs from testBlock.
+    MPhiIterator phis = testBlock->phisBegin();
+    testBlock->discardPhiAt(phis);
+    trueBranch->pop();
+    falseBranch->pop();
+
+    // If either trueBranch or falseBranch just computes a constant for the
+    // test, determine the block that branch will end up jumping to and eliminate
+    // the branch. Otherwise, change the end of the block to a test that jumps
+    // directly to successors of testBlock, rather than to testBlock itself.
+
+    MBasicBlock *trueTarget = trueBranch;
+    if (BlockComputesConstant(trueBranch, trueResult)) {
+        trueTarget = trueResult->toConstant()->valueToBoolean()
+                     ? finalTest->ifTrue()
+                     : finalTest->ifFalse();
+        testBlock->removePredecessor(trueBranch);
+        graph.removeBlock(trueBranch);
+    } else {
+        UpdateTestSuccessors(graph.alloc(), trueBranch, trueResult,
+                             finalTest->ifTrue(), finalTest->ifFalse(), testBlock);
+    }
+
+    MBasicBlock *falseTarget = falseBranch;
+    if (BlockComputesConstant(falseBranch, falseResult)) {
+        falseTarget = falseResult->toConstant()->valueToBoolean()
+                      ? finalTest->ifTrue()
+                      : finalTest->ifFalse();
+        testBlock->removePredecessor(falseBranch);
+        graph.removeBlock(falseBranch);
+    } else {
+        UpdateTestSuccessors(graph.alloc(), falseBranch, falseResult,
+                             finalTest->ifTrue(), finalTest->ifFalse(), testBlock);
+    }
+
+    // Short circuit the initial test to skip any constant branch eliminated above.
+    UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
+                         trueTarget, falseTarget, testBlock);
+
+    // Finally, remove testBlock itself.
+    finalTest->ifTrue()->removePredecessor(testBlock);
+    finalTest->ifFalse()->removePredecessor(testBlock);
+    graph.removeBlock(testBlock);
+
+    printf("WOOT\n");
+}
+
+static void
+MaybeFoldAndOrBlock(MIRGraph &graph, MBasicBlock *initialBlock)
+{
+    // Optimize the MIR graph to improve the code generated for && and ||
+    // operations when they are used in tests. This is very similar to the
+    // above method for folding condition blocks, though the two are
+    // separated (with as much common code as possible) for clarity. This
+    // normally requires three blocks. The final test can always be eliminated,
+    // though we don't try to constant fold away the branch block as well.
+
+    // Look for a triangle pattern:
+    //
+    //       initialBlock
+    //         /     |
+    // branchBlock   |
+    //         \     |
+    //        testBlock
+    //
+    // Where testBlock contains only a test on a phi combining two values
+    // pushed onto the stack by initialBlock and branchBlock.
+
+    MInstruction *ins = initialBlock->lastIns();
+    if (!ins->isTest())
+        return;
+    MTest *initialTest = ins->toTest();
+
+    bool branchIsTrue = true;
+    MBasicBlock *branchBlock = initialTest->ifTrue();
+    MBasicBlock *testBlock = initialTest->ifFalse();
+    if (branchBlock->numSuccessors() != 1 || branchBlock->getSuccessor(0) != testBlock) {
+        branchIsTrue = false;
+        branchBlock = initialTest->ifFalse();
+        testBlock = initialTest->ifTrue();
+    }
+
+    if (branchBlock->numSuccessors() != 1 || branchBlock->getSuccessor(0) != testBlock)
+        return;
+    if (branchBlock->numPredecessors() != 1 || testBlock->numPredecessors() != 2)
+        return;
+
+    MPhi *phi;
+    MTest *finalTest;
+    if (!BlockIsSingleTest(testBlock, &phi, &finalTest))
+        return;
+
+    if (&testBlock->info() != &initialBlock->info() || &branchBlock->info() != &initialBlock->info())
+        return;
+
+    MDefinition *branchResult = phi->getOperand(testBlock->indexForPredecessor(branchBlock));
+    MDefinition *initialResult = phi->getOperand(testBlock->indexForPredecessor(initialBlock));
+
+    if (branchBlock->stackDepth() != initialBlock->stackDepth())
+        return;
+
+    if (branchBlock->stackDepth() != testBlock->stackDepth() + 1)
+        return;
+
+    if (branchResult != branchBlock->peek(-1) || initialResult != initialBlock->peek(-1))
+        return;
+
+    // OK, we found the desired pattern, now transform the graph.
+
+    // Remove the phi and its inputs from testBlock.
+    MPhiIterator phis = testBlock->phisBegin();
+    testBlock->discardPhiAt(phis);
+    branchBlock->pop();
+    initialBlock->pop();
+
+    // Change the end of the initial and branch blocks to a test that jumps
+    // directly to successors of testBlock, rather than to testBlock itself.
+
+    UpdateTestSuccessors(graph.alloc(), initialBlock, initialResult,
+                         branchIsTrue ? branchBlock : finalTest->ifTrue(),
+                         branchIsTrue ? finalTest->ifFalse() : branchBlock,
+                         testBlock);
+
+    UpdateTestSuccessors(graph.alloc(), branchBlock, branchResult,
+                         finalTest->ifTrue(), finalTest->ifFalse(), testBlock);
+
+    // Finally, remove testBlock itself.
+    finalTest->ifTrue()->removePredecessor(testBlock);
+    finalTest->ifFalse()->removePredecessor(testBlock);
+    graph.removeBlock(testBlock);
+
+    printf("WOOT\n");
+}
+
+void
+jit::FoldTests(MIRGraph &graph)
+{
+    for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+        MaybeFoldConditionBlock(graph, *block);
+        MaybeFoldAndOrBlock(graph, *block);
+    }
+}
+
 // A critical edge is an edge which is neither its successor's only predecessor
 // nor its predecessor's only successor. Critical edges must be split to
 // prevent copy-insertion and code motion from affecting other edges.
 bool
 jit::SplitCriticalEdges(MIRGraph &graph)
 {
     for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
         if (block->numSuccessors() < 2)
--- a/js/src/jit/IonAnalysis.h
+++ b/js/src/jit/IonAnalysis.h
@@ -15,16 +15,19 @@
 #include "jit/MIR.h"
 
 namespace js {
 namespace jit {
 
 class MIRGenerator;
 class MIRGraph;
 
+void
+FoldTests(MIRGraph &graph);
+
 bool
 SplitCriticalEdges(MIRGraph &graph);
 
 enum Observability {
     ConservativeObservability,
     AggressiveObservability
 };
 
--- a/js/src/jit/MIRGraph.cpp
+++ b/js/src/jit/MIRGraph.cpp
@@ -921,16 +921,38 @@ MBasicBlock::addPredecessorPopN(TempAllo
                     entryResumePoint()->replaceOperand(i, phi);
             }
         }
     }
 
     return predecessors_.append(pred);
 }
 
+void
+MBasicBlock::addPredecessorSameInputsAs(MBasicBlock *pred, MBasicBlock *existingPred)
+{
+    JS_ASSERT(pred);
+    JS_ASSERT(predecessors_.length() > 0);
+
+    // Predecessors must be finished, and at the correct stack depth.
+    JS_ASSERT(pred->hasLastIns());
+    JS_ASSERT(!pred->successorWithPhis());
+
+    if (!phisEmpty()) {
+        size_t existingPosition = indexForPredecessor(existingPred);
+        for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
+            if (!iter->addInputSlow(iter->getOperand(existingPosition)))
+                CrashAtUnhandlableOOM("MBasicBlock::addPredecessorAdjustPhis");
+        }
+    }
+
+    if (!predecessors_.append(pred))
+        CrashAtUnhandlableOOM("MBasicBlock::addPredecessorAdjustPhis");
+}
+
 bool
 MBasicBlock::addPredecessorWithoutPhis(MBasicBlock *pred)
 {
     // Predecessors must be finished.
     JS_ASSERT(pred && pred->hasLastIns());
     return predecessors_.append(pred);
 }
 
@@ -1128,23 +1150,26 @@ MBasicBlock::removePredecessor(MBasicBlo
 
     for (size_t i = 0; i < numPredecessors(); i++) {
         if (getPredecessor(i) != pred)
             continue;
 
         // Adjust phis.  Note that this can leave redundant phis
         // behind.
         if (!phisEmpty()) {
-            JS_ASSERT(pred->successorWithPhis());
-            JS_ASSERT(pred->positionInPhiSuccessor() == i);
             for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++)
                 iter->removeOperand(i);
-            pred->setSuccessorWithPhis(nullptr, 0);
-            for (size_t j = i+1; j < numPredecessors(); j++)
-                getPredecessor(j)->setSuccessorWithPhis(this, j - 1);
+            if (pred->successorWithPhis()) {
+                // Don't adjust successorWithPhis() if we haven't constructed
+                // this information yet.
+                JS_ASSERT(pred->positionInPhiSuccessor() == i);
+                pred->setSuccessorWithPhis(nullptr, 0);
+                for (size_t j = i+1; j < numPredecessors(); j++)
+                    getPredecessor(j)->setSuccessorWithPhis(this, j - 1);
+            }
         }
 
         // Remove from pred list.
         MBasicBlock **ptr = predecessors_.begin() + i;
         predecessors_.erase(ptr);
         return;
     }
 
--- a/js/src/jit/MIRGraph.h
+++ b/js/src/jit/MIRGraph.h
@@ -171,16 +171,20 @@ class MBasicBlock : public TempObject, p
     }
 
     // Adds a predecessor. Every predecessor must have the same exit stack
     // depth as the entry state to this block. Adding a predecessor
     // automatically creates phi nodes and rewrites uses as needed.
     bool addPredecessor(TempAllocator &alloc, MBasicBlock *pred);
     bool addPredecessorPopN(TempAllocator &alloc, MBasicBlock *pred, uint32_t popped);
 
+    // Add a predecessor which won't introduce any new phis to this block.
+    // This may be called after the contents of this block have been built.
+    void addPredecessorSameInputsAs(MBasicBlock *pred, MBasicBlock *existingPred);
+
     // Stranger utilities used for inlining.
     bool addPredecessorWithoutPhis(MBasicBlock *pred);
     void inheritSlots(MBasicBlock *parent);
     bool initEntrySlots(TempAllocator &alloc);
 
     // Replaces an edge for a given block with a new block. This is
     // used for critical edge splitting and also for inserting
     // bailouts during ParallelSafetyAnalysis.
@@ -275,16 +279,26 @@ class MBasicBlock : public TempObject, p
     }
     void setDomIndex(uint32_t d) {
         domIndex_ = d;
     }
 
     MBasicBlock *getPredecessor(uint32_t i) const {
         return predecessors_[i];
     }
+    size_t indexForPredecessor(MBasicBlock *block) const {
+        // This should only be called before critical edge splitting.
+        JS_ASSERT(!block->successorWithPhis());
+
+        for (size_t i = 0; i < predecessors_.length(); i++) {
+            if (predecessors_[i] == block)
+                return i;
+        }
+        MOZ_CRASH();
+    }
 #ifdef DEBUG
     bool hasLastIns() const {
         return !instructions_.empty() && instructions_.rbegin()->isControlInstruction();
     }
 #endif
     MControlInstruction *lastIns() const {
         return instructions_.rbegin()->toControlInstruction();
     }
--- a/js/src/vm/TraceLogging.cpp
+++ b/js/src/vm/TraceLogging.cpp
@@ -833,16 +833,17 @@ TraceLogging::lazyInit()
         enabledTextIds[TraceLogger::ParserCompileScript] = true;
         enabledTextIds[TraceLogger::IrregexpCompile] = true;
         enabledTextIds[TraceLogger::IrregexpExecute] = true;
     }
 
     if (ContainsFlag(env, "IonCompiler") || strlen(env) == 0) {
         enabledTextIds[TraceLogger::IonCompilation] = true;
         enabledTextIds[TraceLogger::IonLinking] = true;
+        enabledTextIds[TraceLogger::FoldTests] = true;
         enabledTextIds[TraceLogger::SplitCriticalEdges] = true;
         enabledTextIds[TraceLogger::RenumberBlocks] = true;
         enabledTextIds[TraceLogger::DominatorTree] = true;
         enabledTextIds[TraceLogger::PhiAnalysis] = true;
         enabledTextIds[TraceLogger::ApplyTypes] = true;
         enabledTextIds[TraceLogger::ParallelSafetyAnalysis] = true;
         enabledTextIds[TraceLogger::AliasAnalysis] = true;
         enabledTextIds[TraceLogger::GVN] = true;
--- a/js/src/vm/TraceLogging.h
+++ b/js/src/vm/TraceLogging.h
@@ -126,16 +126,17 @@ namespace jit {
     _(ParserCompileLazy)                              \
     _(ParserCompileScript)                            \
     _(TL)                                             \
     _(IrregexpCompile)                                \
     _(IrregexpExecute)                                \
     _(VM)                                             \
                                                       \
     /* Specific passes during ion compilation */      \
+    _(FoldTests)                                      \
     _(SplitCriticalEdges)                             \
     _(RenumberBlocks)                                 \
     _(ScalarReplacement)                              \
     _(DominatorTree)                                  \
     _(PhiAnalysis)                                    \
     _(MakeLoopsContiguous)                            \
     _(ApplyTypes)                                     \
     _(ParallelSafetyAnalysis)                         \