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 209492 a850f2bc582469c6b6253199a222c69427c08368
parent 209491 3562875c38997303db045e404f764791f2429545
child 209493 811aad892522dca9901dc11308ddc1a0b4106f70
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewersnbp
bugs1077720
milestone35.0a1
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) {