Bug 1489142 - Rewrite FlagPhiInputsAsHavingRemovedUses to iterate at most once per Phi. r=jandem
authorNicolas B. Pierron <nicolas.b.pierron@nbp.name>
Fri, 05 Oct 2018 18:35:19 +0200
changeset 446236 c0bef417dc8e17d6a2661075ae8db9df50480b2c
parent 446235 1368e9cf93447804f16e15384be8052f12422e15
child 446237 bb50bbe2a2e516727de68ccac144a047f83c43c9
push id35039
push userrmaries@mozilla.com
push dateWed, 14 Nov 2018 22:17:41 +0000
treeherdermozilla-central@b0a40093b6b7 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs1489142
milestone65.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 1489142 - Rewrite FlagPhiInputsAsHavingRemovedUses to iterate at most once per Phi. r=jandem
js/src/jit-test/tests/ion/merge-phi-usage-analysis.js
js/src/jit/IonAnalysis.cpp
js/src/jit/MIR.cpp
js/src/jit/MIR.h
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/merge-phi-usage-analysis.js
@@ -0,0 +1,63 @@
+
+function expensive() {
+    with({}) {}
+}
+
+function phi_merge_0(i) {
+    // These computations can overflow, if the output is not truncated.
+    i = i | 0;
+    var a0 = i + i;
+    var a1 = i + i;
+
+    if ((a1 | 0) - ((2 * i) | 0)) {
+        // Good candidate for branch pruning, which marks only a1 as having
+        // removed uses.
+        expensive();
+        expensive();
+        expensive();
+        expensive();
+        expensive();
+    }
+
+    // Simple branch made to let GVN merge the Phi instructions.
+    if (a1 % 3 == 1) {
+        a1 = 2 * i;
+        a0 = 2 * i;
+    }
+
+    // a0 is never used, but a1 is truncated.
+    return a1 | 0;
+}
+
+function phi_merge_1(i) {
+    // These computations can overflow, if the output is not truncated.
+    i = i | 0;
+    var a1 = i + i;
+    var a0 = i + i;
+
+    if ((a1 | 0) - ((2 * i) | 0)) {
+        // Good candidate for branch pruning, which marks only a1 as having
+        // removed uses.
+        expensive();
+        expensive();
+        expensive();
+        expensive();
+        expensive();
+    }
+
+    // Simple branch made to let GVN merge the Phi instructions.
+    if (a1 % 3 == 1) {
+        a1 = 2 * i;
+        a0 = 2 * i;
+    }
+
+    // a0 is never used, but a1 is truncated.
+    return a1 | 0;
+}
+
+for (var j = 0; j < 300; j++) {
+    for (var i = 1; i == (i | 0); i = 2 * i + 1) {
+        assertEq(phi_merge_0(i) < 0x80000000, true);
+        assertEq(phi_merge_1(i) < 0x80000000, true);
+    }
+}
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -1,16 +1,18 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "jit/IonAnalysis.h"
 
+#include <utility> // for ::std::pair
+
 #include "jit/AliasAnalysis.h"
 #include "jit/BaselineInspector.h"
 #include "jit/BaselineJIT.h"
 #include "jit/Ion.h"
 #include "jit/IonBuilder.h"
 #include "jit/IonOptimizationLevels.h"
 #include "jit/LIR.h"
 #include "jit/Lowering.h"
@@ -24,21 +26,126 @@
 #include "vm/JSScript-inl.h"
 #include "vm/TypeInference-inl.h"
 
 using namespace js;
 using namespace js::jit;
 
 using mozilla::DebugOnly;
 
-typedef Vector<MPhi*, 16, SystemAllocPolicy> MPhiVector;
+// Stack used by FlagPhiInputsAsHavingRemovedUses. It stores the Phi instruction
+// pointer and the MUseIterator which should be visited next.
+using MPhiUseIteratorStack = Vector<std::pair<MPhi*, MUseIterator>, 16, SystemAllocPolicy>;
+
+// Look for Phi uses with a depth-first search. If any uses are found the stack
+// of MPhi instructions is returned in the |worklist| argument.
+static bool
+DepthFirstSearchUse(MIRGenerator* mir, MPhiUseIteratorStack& worklist, MPhi* phi)
+{
+    // Push a Phi and the next use to iterate over in the worklist.
+    auto push = [&worklist](MPhi* phi, MUseIterator use) -> bool {
+        phi->setInWorklist();
+        return worklist.append(std::make_pair(phi, use));
+    };
+
+#ifdef DEBUG
+    // Used to assert that when we have no uses, we at least visited all the
+    // transitive uses.
+    size_t refUseCount = phi->useCount();
+    size_t useCount = 0;
+#endif
+    MOZ_ASSERT(worklist.empty());
+    if (!push(phi, phi->usesBegin())) {
+        return false;
+    }
+
+    while (!worklist.empty()) {
+        // Resume iterating over the last phi-use pair added by the next loop.
+        auto pair = worklist.popCopy();
+        MPhi* producer = pair.first;
+        MUseIterator use = pair.second;
+        MUseIterator end(producer->usesEnd());
+        producer->setNotInWorklist();
+
+        // Keep going down the tree of uses, skipping (continue)
+        // non-observable/unused cases and Phi which are already listed in the
+        // worklist. Stop (return) as soon as one use is found.
+        while (use != end) {
+            MNode* consumer = (*use)->consumer();
+            MUseIterator it = use;
+            use++;
+#ifdef DEBUG
+            useCount++;
+#endif
+            if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop")) {
+                return false;
+            }
+
+            if (consumer->isResumePoint()) {
+                MResumePoint* rp = consumer->toResumePoint();
+                // Observable operands are similar to potential uses.
+                if (rp->isObservableOperand(*it)) {
+                    return push(producer, use);
+                }
+                continue;
+            }
+
+            MDefinition* cdef = consumer->toDefinition();
+            if (!cdef->isPhi()) {
+                // The producer is explicitly used by a definition.
+                return push(producer, use);
+            }
+
+            MPhi* cphi = cdef->toPhi();
+            if (cphi->getUsageAnalysis() == PhiUsage::Used || cphi->isUseRemoved()) {
+                // The information got cached on the Phi the last time it
+                // got visited, or when flagging operands of removed
+                // instructions.
+                return push(producer, use);
+            }
+
+            if (cphi->isInWorklist() || cphi == producer) {
+                // We are already iterating over the uses of this Phi
+                // instruction. Skip it.
+                continue;
+            }
+
+            if (cphi->getUsageAnalysis() == PhiUsage::Unused) {
+                // The instruction already got visited and is known to have
+                // no uses. Skip it.
+                continue;
+            }
+
+            // We found another Phi instruction, move the use iterator to
+            // the next use push it to the worklist stack. Then, continue
+            // with a depth search.
+            if (!push(producer, use)) {
+                return false;
+            }
+            producer = cphi;
+            use = producer->usesBegin();
+            end = producer->usesEnd();
+#ifdef DEBUG
+            refUseCount += producer->useCount();
+#endif
+        }
+
+        // When unused, we cannot bubble up this information without iterating
+        // over the rest of the previous Phi instruction consumers.
+        MOZ_ASSERT(use == end);
+        producer->setUsageAnalysis(PhiUsage::Unused);
+    }
+
+    MOZ_ASSERT(useCount == refUseCount);
+    return true;
+}
 
 static bool
 FlagPhiInputsAsHavingRemovedUses(MIRGenerator* mir, MBasicBlock* block, MBasicBlock* succ,
-                                 MPhiVector& worklist)
+                                 MPhiUseIteratorStack& worklist)
 {
     // When removing an edge between 2 blocks, we might remove the ability of
     // later phases to figure out that the uses of a Phi should be considered as
     // a use of all its inputs. Thus we need to mark the Phi inputs as having
     // removed uses iff the phi has any uses.
     //
     //
     //        +--------------------+         +---------------------+
@@ -89,22 +196,21 @@ FlagPhiInputsAsHavingRemovedUses(MIRGene
     //                     |70 MReturn 50           |
     //                     +------------------------+
     //
     //
     // If the inputs of the Phi are not flagged as having removed uses, then
     // later compilation phase might optimize them out. The problem is that a
     // bailout will use this value and give it back to baseline, which will then
     // use the OptimizedOut magic value in a computation.
-
-    // Conservative upper limit for the number of Phi instructions which are
-    // visited while looking for uses.
-    const size_t conservativeUsesLimit = 128;
-
-    MOZ_ASSERT(worklist.empty());
+    //
+    // Unfortunately, we cannot be too conservative about flagging Phi inputs as
+    // having removed uses, as this would prevent many optimizations from being
+    // used. Thus, the following code is in charge of flagging Phi instructions
+    // as Unused or Used, and setting UseRemoved accordingly.
     size_t predIndex = succ->getPredecessorIndex(block);
     MPhiIterator end = succ->phisEnd();
     MPhiIterator it = succ->phisBegin();
     for (; it != end; it++) {
         MPhi* phi = *it;
 
         if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses outer loop")) {
             return false;
@@ -112,92 +218,46 @@ FlagPhiInputsAsHavingRemovedUses(MIRGene
 
         // We are looking to mark the Phi inputs which are used across the edge
         // between the |block| and its successor |succ|.
         MDefinition* def = phi->getOperand(predIndex);
         if (def->isUseRemoved()) {
             continue;
         }
 
-        phi->setInWorklist();
-        if (!worklist.append(phi)) {
+        // If the Phi is either Used or Unused, set the UseRemoved flag
+        // accordingly.
+        if (phi->getUsageAnalysis() == PhiUsage::Used || phi->isUseRemoved()) {
+            def->setUseRemoved();
+            continue;
+        } else if (phi->getUsageAnalysis() == PhiUsage::Unused) {
+            continue;
+        }
+
+        // We do not know if the Phi was Used or Unused, iterate over all uses
+        // with a depth-search of uses. Returns the matching stack in the
+        // worklist as soon as one use is found.
+        MOZ_ASSERT(worklist.empty());
+        if (!DepthFirstSearchUse(mir, worklist, phi)) {
             return false;
         }
 
-        // Fill the work list with all the Phi nodes uses until we reach either:
-        //  - A resume point which uses the Phi as an observable operand.
-        //  - An explicit use of the Phi instruction.
-        //  - An implicit use of the Phi instruction.
-        bool isUsed = false;
-        for (size_t idx = 0; !isUsed && idx < worklist.length(); idx++) {
-            phi = worklist[idx];
-
-            if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 1")) {
-                return false;
-            }
-
-            if (phi->isUseRemoved() || phi->isImplicitlyUsed()) {
-                // The phi is implicitly used.
-                isUsed = true;
-                break;
-            }
-
-            MUseIterator usesEnd(phi->usesEnd());
-            for (MUseIterator use(phi->usesBegin()); use != usesEnd; use++) {
-                MNode* consumer = (*use)->consumer();
-
-                if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 2")) {
-                    return false;
-                }
-
-                if (consumer->isResumePoint()) {
-                    MResumePoint* rp = consumer->toResumePoint();
-                    if (rp->isObservableOperand(*use)) {
-                        // The phi is observable via a resume point operand.
-                        isUsed = true;
-                        break;
-                    }
-                    continue;
-                }
-
-                MDefinition* cdef = consumer->toDefinition();
-                if (!cdef->isPhi()) {
-                    // The phi is explicitly used.
-                    isUsed = true;
-                    break;
-                }
-
-                phi = cdef->toPhi();
-                if (phi->isInWorklist()) {
-                    continue;
-                }
-
-                phi->setInWorklist();
-                if (!worklist.append(phi)) {
-                    return false;
-                }
-            }
-
-            // Use a conservative upper bound to avoid iterating too many times
-            // on very large graphs.
-            if (idx >= conservativeUsesLimit) {
-                isUsed = true;
-                break;
-            }
-        }
-
-        if (isUsed) {
+        MOZ_ASSERT_IF(worklist.empty(), phi->getUsageAnalysis() == PhiUsage::Unused);
+        if (!worklist.empty()) {
+            // One of the Phis is used, set Used flags on all the Phis which are
+            // in the use chain.
             def->setUseRemoved();
-        }
-
-        // Remove all the InWorklist flags.
-        while (!worklist.empty()) {
-            phi = worklist.popCopy();
-            phi->setNotInWorklist();
-        }
+            do {
+                auto pair = worklist.popCopy();
+                MPhi* producer = pair.first;
+                producer->setUsageAnalysis(PhiUsage::Used);
+                producer->setNotInWorklist();
+            } while (!worklist.empty());
+        }
+        MOZ_ASSERT(phi->getUsageAnalysis() != PhiUsage::Unknown);
     }
 
     return true;
 }
 
 static bool
 FlagAllOperandsAsHavingRemovedUses(MIRGenerator* mir, MBasicBlock* block)
 {
@@ -241,17 +301,17 @@ FlagAllOperandsAsHavingRemovedUses(MIRGe
                 rp->getOperand(i)->setUseRemovedUnchecked();
             }
         }
 
         rp = rp->caller();
     }
 
     // Flag Phi inputs of the successors has having removed uses.
-    MPhiVector worklist;
+    MPhiUseIteratorStack worklist;
     for (size_t i = 0, e = block->numSuccessors(); i < e; i++) {
         if (mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 3")) {
             return false;
         }
 
         if (!FlagPhiInputsAsHavingRemovedUses(mir, block, block->getSuccessor(i), worklist)) {
             return false;
         }
--- a/js/src/jit/MIR.cpp
+++ b/js/src/jit/MIR.cpp
@@ -2322,16 +2322,41 @@ MPhi::congruentTo(const MDefinition* ins
     // For now, consider phis in different blocks incongruent.
     if (ins->block() != block()) {
         return false;
     }
 
     return congruentIfOperandsEqual(ins);
 }
 
+bool
+MPhi::updateForReplacement(MDefinition* def)
+{
+    // This function is called to fix the current Phi flags using it as a
+    // replacement of the other Phi instruction |def|.
+    //
+    // When dealing with usage analysis, any Use will replace all other values,
+    // such as Unused and Unknown. Unless both are Unused, the merge would be
+    // Unknown.
+    MPhi* other = def->toPhi();
+    if (usageAnalysis_ == PhiUsage::Used || other->usageAnalysis_ == PhiUsage::Used) {
+        usageAnalysis_ = PhiUsage::Used;
+    } else if (usageAnalysis_ != other->usageAnalysis_) {
+        //    this == unused && other == unknown
+        // or this == unknown && other == unused
+        usageAnalysis_ = PhiUsage::Unknown;
+    } else {
+        //    this == unused && other == unused
+        // or this == unknown && other = unknown
+        MOZ_ASSERT(usageAnalysis_ == PhiUsage::Unused || usageAnalysis_ == PhiUsage::Unknown);
+        MOZ_ASSERT(usageAnalysis_ == other->usageAnalysis_);
+    }
+    return true;
+}
+
 static inline TemporaryTypeSet*
 MakeMIRTypeSet(TempAllocator& alloc, MIRType type)
 {
     MOZ_ASSERT(type != MIRType::Value);
     TypeSet::Type ntype = type == MIRType::Object
                           ? TypeSet::AnyObjectType()
                           : TypeSet::PrimitiveType(ValueTypeFromMIRType(type));
     return alloc.lifoAlloc()->new_<TemporaryTypeSet>(alloc.lifoAlloc(), ntype);
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -6821,30 +6821,42 @@ class MArrowNewTarget
         return congruentIfOperandsEqual(ins);
     }
     AliasSet getAliasSet() const override {
         // An arrow function's lexical |this| value is immutable.
         return AliasSet::None();
     }
 };
 
+// This is a 3 state flag used by FlagPhiInputsAsHavingRemovedUses to record and
+// propagate the information about the consumers of a Phi instruction. This is
+// then used to set UseRemoved flags on the inputs of such Phi instructions.
+enum class PhiUsage : uint8_t {
+    Unknown,
+    Unused,
+    Used
+};
+
 class MPhi final
   : public MDefinition,
     public InlineListNode<MPhi>,
     public NoTypePolicy::Data
 {
     using InputVector = js::Vector<MUse, 2, JitAllocPolicy>;
     InputVector inputs_;
 
     TruncateKind truncateKind_;
     bool hasBackedgeType_;
     bool triedToSpecialize_;
     bool isIterator_;
     bool canProduceFloat32_;
     bool canConsumeFloat32_;
+    // Record the state of the data flow before any mutation made to the control
+    // flow, such that removing branches is properly accounted for.
+    PhiUsage usageAnalysis_;
 
 #if DEBUG
     bool specialized_;
 #endif
 
   protected:
     MUse* getUseFor(size_t index) override {
         // Note: after the initial IonBuilder pass, it is OK to change phi
@@ -6866,17 +6878,18 @@ class MPhi final
     MPhi(TempAllocator& alloc, MIRType resultType)
       : MDefinition(classOpcode),
         inputs_(alloc),
         truncateKind_(NoTruncate),
         hasBackedgeType_(false),
         triedToSpecialize_(false),
         isIterator_(false),
         canProduceFloat32_(false),
-        canConsumeFloat32_(false)
+        canConsumeFloat32_(false),
+        usageAnalysis_(PhiUsage::Unknown)
 #if DEBUG
         , specialized_(false)
 #endif
     {
         setResultType(resultType);
     }
 
     static MPhi* New(TempAllocator& alloc, MIRType resultType = MIRType::Value) {
@@ -6973,16 +6986,17 @@ class MPhi final
     // |*ptypeChange| to true if the type changed.
     bool checkForTypeChange(TempAllocator& alloc, MDefinition* ins, bool* ptypeChange);
 
     MDefinition* foldsTo(TempAllocator& alloc) override;
     MDefinition* foldsTernary(TempAllocator& alloc);
     MDefinition* foldsFilterTypeSet();
 
     bool congruentTo(const MDefinition* ins) const override;
+    bool updateForReplacement(MDefinition* def) override;
 
     bool isIterator() const {
         return isIterator_;
     }
     void setIterator() {
         isIterator_ = true;
     }
 
@@ -7007,16 +7021,23 @@ class MPhi final
 
     void setCanConsumeFloat32(bool can) {
         canConsumeFloat32_ = can;
     }
 
     TruncateKind operandTruncateKind(size_t index) const override;
     bool needTruncation(TruncateKind kind) override;
     void truncate() override;
+
+    PhiUsage getUsageAnalysis() const { return usageAnalysis_; }
+    void setUsageAnalysis(PhiUsage pu) {
+        MOZ_ASSERT(usageAnalysis_ == PhiUsage::Unknown);
+        usageAnalysis_ = pu;
+        MOZ_ASSERT(usageAnalysis_ != PhiUsage::Unknown);
+    }
 };
 
 // The goal of a Beta node is to split a def at a conditionally taken
 // branch, so that uses dominated by it have a different name.
 class MBeta
   : public MUnaryInstruction,
     public NoTypePolicy::Data
 {