Bug 1077720 - IonMonkey: Optimize MPhi's addInput and addInputSlow r=nbp
--- 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) {