Bug 1077720 - IonMonkey: Optimize MPhi's addInput and addInputSlow r=nbp
authorDan Gohman <sunfish@mozilla.com>
Wed, 08 Oct 2014 15:04:12 -0700
changeset 232707 a850f2bc582469c6b6253199a222c69427c08368
parent 232706 3562875c38997303db045e404f764791f2429545
child 232708 811aad892522dca9901dc11308ddc1a0b4106f70
push id4187
push userbhearsum@mozilla.com
push dateFri, 28 Nov 2014 15:29:12 +0000
treeherdermozilla-beta@f23cc6a30c11 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp
bugs1077720
milestone35.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 1077720 - IonMonkey: Optimize MPhi's addInput and addInputSlow r=nbp
js/src/jit/FixedList.h
js/src/jit/InlineList.h
js/src/jit/MIR.cpp
js/src/jit/MIR.h
js/src/jit/MIRGraph.cpp
mfbt/Vector.h
--- a/js/src/jit/FixedList.h
+++ b/js/src/jit/FixedList.h
@@ -73,14 +73,21 @@ class FixedList
     T &operator[](size_t index) {
         MOZ_ASSERT(index < length_);
         return list_[index];
     }
     const T &operator [](size_t index) const {
         MOZ_ASSERT(index < length_);
         return list_[index];
     }
+
+    T *begin() {
+        return list_;
+    }
+    T *end() {
+        return list_ + length_;
+    }
 };
 
 } // namespace jit
 } // namespace js
 
 #endif /* jit_FixedList_h */
--- a/js/src/jit/InlineList.h
+++ b/js/src/jit/InlineList.h
@@ -206,17 +206,36 @@ class InlineListNode : public InlineForw
   public:
     InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr)
     { }
     InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p)
       : InlineForwardListNode<T>(n),
         prev(p)
     { }
 
+    // Move constructor. Nodes may be moved without being removed from their
+    // containing lists. For example, this allows list nodes to be safely
+    // stored in a resizable Vector -- when the Vector resizes, the new storage
+    // is initialized by this move constructor. |other| is a reference to the
+    // old node which the |this| node here is replacing.
+    InlineListNode(InlineListNode<T> &&other)
+      : InlineForwardListNode<T>(other.next)
+    {
+        InlineListNode<T> *newNext = static_cast<InlineListNode<T> *>(other.next);
+        InlineListNode<T> *newPrev = other.prev;
+        prev = newPrev;
+
+        // Update the pointers in the adjacent nodes to point to this node's new
+        // location.
+        newNext->prev = this;
+        newPrev->next = this;
+    }
+
     InlineListNode(const InlineListNode<T> &) MOZ_DELETE;
+    void operator=(const InlineListNode<T> &) MOZ_DELETE;
 
   protected:
     friend class InlineList<T>;
     friend class InlineListIterator<T>;
     friend class InlineListReverseIterator<T>;
 
     InlineListNode<T> *prev;
 };
--- a/js/src/jit/MIR.cpp
+++ b/js/src/jit/MIR.cpp
@@ -1356,29 +1356,16 @@ MPhi::congruentTo(const MDefinition *ins
     //
     // For now, consider phis in different blocks incongruent.
     if (ins->block() != block())
         return false;
 
     return congruentIfOperandsEqual(ins);
 }
 
-bool
-MPhi::reserveLength(size_t length)
-{
-    // Initializes a new MPhi to have an Operand vector of at least the given
-    // capacity. This permits use of addInput() instead of addInputSlow(), the
-    // latter of which may call pod_realloc().
-    MOZ_ASSERT(numOperands() == 0);
-#if DEBUG
-    capacity_ = length;
-#endif
-    return inputs_.reserve(length);
-}
-
 static inline types::TemporaryTypeSet *
 MakeMIRTypeSet(MIRType type)
 {
     MOZ_ASSERT(type != MIRType_Value);
     types::Type ntype = type == MIRType_Object
                         ? types::Type::AnyObjectType()
                         : types::Type::PrimitiveType(ValueTypeFromMIRType(type));
     LifoAlloc *alloc = GetIonContext()->temp->lifoAlloc();
@@ -1497,75 +1484,30 @@ MPhi::typeIncludes(MDefinition *def)
         // This phi must be able to be any value.
         return this->type() == MIRType_Value
             && (!this->resultTypeSet() || this->resultTypeSet()->unknown());
     }
 
     return this->mightBeType(def->type());
 }
 
-void
-MPhi::addInput(MDefinition *ins)
-{
-    // This can only been done if the length was reserved through reserveLength,
-    // else the slower addInputSlow need to get called.
-    MOZ_ASSERT(inputs_.length() < capacity_);
-
-    inputs_.append(MUse());
-    inputs_.back().init(ins, this);
-}
-
 bool
-MPhi::addInputSlow(MDefinition *ins, bool *ptypeChange)
-{
-    // The list of inputs to an MPhi is given as a vector of MUse nodes,
-    // each of which is in the list of the producer MDefinition.
-    // Because appending to a vector may reallocate the vector, it is possible
-    // that this operation may cause the producers' linked lists to reference
-    // invalid memory. Therefore, in the event of moving reallocation, each
-    // MUse must be removed and reinserted from/into its producer's use chain.
-    uint32_t index = inputs_.length();
-    bool performingRealloc = !inputs_.canAppendWithoutRealloc(1);
-
-    // Remove all MUses from all use lists, in case pod_realloc() moves.
-    if (performingRealloc) {
-        for (uint32_t i = 0; i < index; i++) {
-            MUse *use = &inputs_[i];
-            use->producer()->removeUse(use);
-        }
+MPhi::checkForTypeChange(MDefinition *ins, bool *ptypeChange)
+{
+    MIRType resultType = this->type();
+    types::TemporaryTypeSet *resultTypeSet = this->resultTypeSet();
+
+    if (!MergeTypes(&resultType, &resultTypeSet, ins->type(), ins->resultTypeSet()))
+        return false;
+
+    if (resultType != this->type() || resultTypeSet != this->resultTypeSet()) {
+        *ptypeChange = true;
+        setResultType(resultType);
+        setResultTypeSet(resultTypeSet);
     }
-
-    // Insert the new input.
-    if (!inputs_.append(MUse()))
-        return false;
-
-    inputs_.back().init(ins, this);
-
-    if (ptypeChange) {
-        MIRType resultType = this->type();
-        types::TemporaryTypeSet *resultTypeSet = this->resultTypeSet();
-
-        if (!MergeTypes(&resultType, &resultTypeSet, ins->type(), ins->resultTypeSet()))
-            return false;
-
-        if (resultType != this->type() || resultTypeSet != this->resultTypeSet()) {
-            *ptypeChange = true;
-            setResultType(resultType);
-            setResultTypeSet(resultTypeSet);
-        }
-    }
-
-    // Add all previously-removed MUses back.
-    if (performingRealloc) {
-        for (uint32_t i = 0; i < index; i++) {
-            MUse *use = &inputs_[i];
-            use->producer()->addUse(use);
-        }
-    }
-
     return true;
 }
 
 void
 MCall::addArg(size_t argnum, MDefinition *arg)
 {
     // The operand vector is initialized in reverse order by the IonBuilder.
     // It cannot be checked for consistency until all arguments are added.
--- a/js/src/jit/MIR.h
+++ b/js/src/jit/MIR.h
@@ -122,42 +122,43 @@ class MUse : public TempObject, public I
 {
     // Grant access to setProducerUnchecked.
     friend class MDefinition;
     friend class MPhi;
 
     MDefinition *producer_; // MDefinition that is being used.
     MNode *consumer_;       // The node that is using this operand.
 
-    MUse(MDefinition *producer, MNode *consumer)
-      : producer_(producer),
-        consumer_(consumer)
-    { }
-
     // Low-level unchecked edit method for replaceAllUsesWith and
     // MPhi::removeOperand. This doesn't update use lists!
     // replaceAllUsesWith and MPhi::removeOperand do that manually.
     void setProducerUnchecked(MDefinition *producer) {
         MOZ_ASSERT(consumer_);
         MOZ_ASSERT(producer_);
         MOZ_ASSERT(producer);
         producer_ = producer;
     }
 
   public:
     // Default constructor for use in vectors.
     MUse()
       : producer_(nullptr), consumer_(nullptr)
     { }
 
-    // MUses can only be copied when they are not in a use list.
-    explicit MUse(const MUse &other)
-      : producer_(other.producer_), consumer_(other.consumer_)
-    {
-        MOZ_ASSERT(!other.next && !other.prev);
+    // Move constructor for use in vectors. When an MUse is moved, it stays
+    // in its containing use list.
+    MUse(MUse &&other)
+      : InlineListNode<MUse>(mozilla::Move(other)),
+        producer_(other.producer_), consumer_(other.consumer_)
+    { }
+
+    // Construct an MUse initialized with |producer| and |consumer|.
+    MUse(MDefinition *producer, MNode *consumer)
+    {
+        initUnchecked(producer, consumer);
     }
 
     // Set this use, which was previously clear.
     inline void init(MDefinition *producer, MNode *consumer);
     // Like init, but works even when the use contains uninitialized data.
     inline void initUnchecked(MDefinition *producer, MNode *consumer);
     // Like initUnchecked, but set the producer to nullptr.
     inline void initUncheckedWithoutProducer(MNode *consumer);
@@ -5899,17 +5900,16 @@ class MPhi MOZ_FINAL : public MDefinitio
     bool hasBackedgeType_;
     bool triedToSpecialize_;
     bool isIterator_;
     bool canProduceFloat32_;
     bool canConsumeFloat32_;
 
 #if DEBUG
     bool specialized_;
-    uint32_t capacity_;
 #endif
 
   protected:
     MUse *getUseFor(size_t index) {
         // Note: after the initial IonBuilder pass, it is OK to change phi
         // operands such that they do not include the type sets of their
         // operands. This can arise during e.g. value numbering, where
         // definitions producing the same value may have different type sets.
@@ -5928,17 +5928,16 @@ class MPhi MOZ_FINAL : public MDefinitio
         truncateKind_(NoTruncate),
         hasBackedgeType_(false),
         triedToSpecialize_(false),
         isIterator_(false),
         canProduceFloat32_(false),
         canConsumeFloat32_(false)
 #if DEBUG
         , specialized_(false)
-        , capacity_(0)
 #endif
     {
         setResultType(resultType);
     }
 
     static MPhi *New(TempAllocator &alloc, MIRType resultType = MIRType_Value) {
         return new(alloc) MPhi(alloc, resultType);
     }
@@ -5998,24 +5997,46 @@ class MPhi MOZ_FINAL : public MDefinitio
     bool typeIncludes(MDefinition *def);
 
     // Add types for this phi which speculate about new inputs that may come in
     // via a loop backedge.
     bool addBackedgeType(MIRType type, types::TemporaryTypeSet *typeSet);
 
     // Initializes the operands vector to the given capacity,
     // permitting use of addInput() instead of addInputSlow().
-    bool reserveLength(size_t length);
+    bool reserveLength(size_t length) {
+        return inputs_.reserve(length);
+    }
 
     // Use only if capacity has been reserved by reserveLength
-    void addInput(MDefinition *ins);
-
-    // Appends a new input to the input vector. May call pod_realloc().
+    void addInput(MDefinition *ins) {
+        // Use infallibleGrowByUninitialized and placement-new instead of just
+        // infallibleAppend to avoid creating a temporary MUse which will get
+        // linked into |ins|'s use list and then unlinked in favor of the
+        // MUse in the Vector. We'd ideally like to use an emplace method here,
+        // once Vector supports that.
+        inputs_.infallibleGrowByUninitialized(1);
+        new (&inputs_.back()) MUse(ins, this);
+    }
+
+    // Appends a new input to the input vector. May perform reallocation.
     // Prefer reserveLength() and addInput() instead, where possible.
-    bool addInputSlow(MDefinition *ins, bool *ptypeChange = nullptr);
+    bool addInputSlow(MDefinition *ins) {
+        // Use growByUninitialized and placement-new instead of just append,
+        // similar to what addInput does.
+        if (!inputs_.growByUninitialized(1))
+            return false;
+
+        new (&inputs_.back()) MUse(ins, this);
+        return true;
+    }
+
+    // Update the type of this phi after adding |ins| as an input. Set
+    // |*ptypeChange| to true if the type changed.
+    bool checkForTypeChange(MDefinition *ins, bool *ptypeChange);
 
     MDefinition *foldsTo(TempAllocator &alloc);
     MDefinition *foldsTernary();
 
     bool congruentTo(const MDefinition *ins) const;
 
     bool isIterator() const {
         return isIterator_;
--- a/js/src/jit/MIRGraph.cpp
+++ b/js/src/jit/MIRGraph.cpp
@@ -330,17 +330,16 @@ MBasicBlock::NewAsmJS(MIRGraph &graph, C
 
             // Note: Phis are inserted in the same order as the slots.
             for (size_t i = 0; i < nphis; i++) {
                 MDefinition *predSlot = pred->getSlot(i);
 
                 MOZ_ASSERT(predSlot->type() != MIRType_Value);
                 MPhi *phi = new(phis + i) MPhi(alloc, predSlot->type());
 
-                JS_ALWAYS_TRUE(phi->reserveLength(2));
                 phi->addInput(predSlot);
 
                 // Add append Phis in the block.
                 block->addPhi(phi);
                 block->setSlot(i, phi);
             }
         } else {
             block->copySlots(pred);
@@ -402,18 +401,20 @@ MBasicBlock::ensureHasSlots(size_t num)
     return true;
 }
 
 void
 MBasicBlock::copySlots(MBasicBlock *from)
 {
     MOZ_ASSERT(stackPosition_ <= from->stackPosition_);
 
-    for (uint32_t i = 0; i < stackPosition_; i++)
-        slots_[i] = from->slots_[i];
+    MDefinition **thisSlots = slots_.begin();
+    MDefinition **fromSlots = from->slots_.begin();
+    for (size_t i = 0, e = stackPosition_; i < e; ++i)
+        thisSlots[i] = fromSlots[i];
 }
 
 bool
 MBasicBlock::inherit(TempAllocator &alloc, BytecodeAnalysis *analysis, MBasicBlock *pred,
                      uint32_t popped, unsigned stackPhiCount)
 {
     if (pred) {
         stackPosition_ = pred->stackPosition_;
@@ -442,18 +443,17 @@ MBasicBlock::inherit(TempAllocator &allo
     if (pred) {
         if (!predecessors_.append(pred))
             return false;
 
         if (kind_ == PENDING_LOOP_HEADER) {
             size_t i = 0;
             for (i = 0; i < info().firstStackSlot(); i++) {
                 MPhi *phi = MPhi::New(alloc);
-                if (!phi->addInputSlow(pred->getSlot(i)))
-                    return false;
+                phi->addInput(pred->getSlot(i));
                 addPhi(phi);
                 setSlot(i, phi);
                 entryResumePoint()->initOperand(i, phi);
             }
 
             MOZ_ASSERT(stackPhiCount <= stackDepth());
             MOZ_ASSERT(info().firstStackSlot() <= stackDepth() - stackPhiCount);
 
@@ -463,18 +463,17 @@ MBasicBlock::inherit(TempAllocator &allo
             for (; i < stackDepth() - stackPhiCount; i++) {
                 MDefinition *val = pred->getSlot(i);
                 setSlot(i, val);
                 entryResumePoint()->initOperand(i, val);
             }
 
             for (; i < stackDepth(); i++) {
                 MPhi *phi = MPhi::New(alloc);
-                if (!phi->addInputSlow(pred->getSlot(i)))
-                    return false;
+                phi->addInput(pred->getSlot(i));
                 addPhi(phi);
                 setSlot(i, phi);
                 entryResumePoint()->initOperand(i, phi);
             }
         } else {
             for (size_t i = 0; i < stackDepth(); i++)
                 entryResumePoint()->initOperand(i, getSlot(i));
         }
@@ -1020,17 +1019,17 @@ MBasicBlock::addPredecessorPopN(TempAllo
 {
     MOZ_ASSERT(pred);
     MOZ_ASSERT(predecessors_.length() > 0);
 
     // Predecessors must be finished, and at the correct stack depth.
     MOZ_ASSERT(pred->hasLastIns());
     MOZ_ASSERT(pred->stackPosition_ == stackPosition_ + popped);
 
-    for (uint32_t i = 0; i < stackPosition_; i++) {
+    for (uint32_t i = 0, e = stackPosition_; i < e; ++i) {
         MDefinition *mine = getSlot(i);
         MDefinition *other = pred->getSlot(i);
 
         if (mine != other) {
             // If the current instruction is a phi, and it was created in this
             // basic block, then we have already placed this phi and should
             // instead append to its operands.
             if (mine->isPhi() && mine->block() == this) {
@@ -1046,17 +1045,17 @@ MBasicBlock::addPredecessorPopN(TempAllo
                     phi = MPhi::New(alloc);
                 addPhi(phi);
 
                 // Prime the phi for each predecessor, so input(x) comes from
                 // predecessor(x).
                 if (!phi->reserveLength(predecessors_.length() + 1))
                     return false;
 
-                for (size_t j = 0; j < predecessors_.length(); j++) {
+                for (size_t j = 0, numPreds = predecessors_.length(); j < numPreds; ++j) {
                     MOZ_ASSERT(predecessors_[j]->getSlot(i) == mine);
                     phi->addInput(mine);
                 }
                 phi->addInput(other);
 
                 setSlot(i, phi);
                 if (entryResumePoint())
                     entryResumePoint()->replaceOperand(i, phi);
@@ -1192,17 +1191,17 @@ MBasicBlock::setBackedgeAsmJS(MBasicBloc
             // know that that's just the first input.
             //
             // Note that we eliminate later rather than now, to avoid any
             // weirdness around pending continue edges which might still hold
             // onto phis.
             exitDef = entryDef->getOperand(0);
         }
 
-        // MBasicBlock::NewAsmJS calls reserveLength(2) for loop header phis.
+        // Phis always have room for 2 operands, so we can use addInput.
         entryDef->addInput(exitDef);
 
         MOZ_ASSERT(slot < pred->stackDepth());
         setSlot(slot, entryDef);
     }
 
     // We are now a loop header proper
     kind_ = LOOP_HEADER;
@@ -1431,19 +1430,20 @@ MBasicBlock::inheritPhisFromBackedge(MBa
             // Note that we eliminate later rather than now, to avoid any
             // weirdness around pending continue edges which might still hold
             // onto phis.
             exitDef = entryDef->getOperand(0);
         }
 
         bool typeChange = false;
 
-        if (!entryDef->addInputSlow(exitDef, &typeChange))
+        if (!entryDef->addInputSlow(exitDef))
             return false;
-
+        if (!entryDef->checkForTypeChange(exitDef, &typeChange))
+            return false;
         *hadTypeChange |= typeChange;
         setSlot(slot, entryDef);
     }
 
     return true;
 }
 
 bool
--- a/mfbt/Vector.h
+++ b/mfbt/Vector.h
@@ -467,16 +467,17 @@ public:
   /** Call shrinkBy or growBy based on whether newSize > length(). */
   bool resize(size_t aNewLength);
 
   /**
    * Increase the length of the vector, but don't initialize the new elements
    * -- leave them as uninitialized memory.
    */
   bool growByUninitialized(size_t aIncr);
+  void infallibleGrowByUninitialized(size_t aIncr);
   bool resizeUninitialized(size_t aNewLength);
 
   /** Shorthand for shrinkBy(length()). */
   void clear();
 
   /** Clears and releases any heap-allocated storage. */
   void clearAndFree();
 
@@ -874,24 +875,31 @@ VectorBase<T, N, AP, TV>::growBy(size_t 
 template<typename T, size_t N, class AP, class TV>
 MOZ_ALWAYS_INLINE bool
 VectorBase<T, N, AP, TV>::growByUninitialized(size_t aIncr)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
   if (aIncr > mCapacity - mLength && !growStorageBy(aIncr)) {
     return false;
   }
+  infallibleGrowByUninitialized(aIncr);
+  return true;
+}
+
+template<typename T, size_t N, class AP, class TV>
+MOZ_ALWAYS_INLINE void
+VectorBase<T, N, AP, TV>::infallibleGrowByUninitialized(size_t aIncr)
+{
   MOZ_ASSERT(mLength + aIncr <= mCapacity);
   mLength += aIncr;
 #ifdef DEBUG
   if (mLength > mReserved) {
     mReserved = mLength;
   }
 #endif
-  return true;
 }
 
 template<typename T, size_t N, class AP, class TV>
 inline bool
 VectorBase<T, N, AP, TV>::resize(size_t aNewLength)
 {
   size_t curLength = mLength;
   if (aNewLength > curLength) {