Bug 1058095 - IonMonkey: Eliminate the loops in entryOf and exitOf r=bhackett
authorDan Gohman <sunfish@mozilla.com
Fri, 10 Oct 2014 21:21:36 -0700
changeset 209959 80c1cb537478c1bacc45a6a33356465efc2f06ab
parent 209958 ba2a7e2ec1a072a198ee416bd4db9aa56523b4e3
child 209960 204dc904b8c01bf29ce336abbc4b18e554cc023d
push id27632
push userryanvm@gmail.com
push dateSat, 11 Oct 2014 20:21:25 +0000
treeherdermozilla-central@44168a7af20d [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs1058095
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 1058095 - IonMonkey: Eliminate the loops in entryOf and exitOf r=bhackett
js/src/jit/FixedList.h
js/src/jit/LIR-Common.h
js/src/jit/LIR.cpp
js/src/jit/LIR.h
js/src/jit/LiveRangeAllocator.cpp
js/src/jit/RegisterAllocator.h
--- a/js/src/jit/FixedList.h
+++ b/js/src/jit/FixedList.h
@@ -38,16 +38,20 @@ class FixedList
             return true;
 
         if (length & mozilla::tl::MulOverflowMask<sizeof(T)>::value)
             return false;
         list_ = (T *)alloc.allocate(length * sizeof(T));
         return list_ != nullptr;
     }
 
+    size_t empty() const {
+        return length_ == 0;
+    }
+
     size_t length() const {
         return length_;
     }
 
     void shrink(size_t num) {
         MOZ_ASSERT(num < length_);
         length_ -= num;
     }
--- a/js/src/jit/LIR-Common.h
+++ b/js/src/jit/LIR-Common.h
@@ -6060,78 +6060,16 @@ class LGuardClass : public LInstructionH
     const MGuardClass *mir() const {
         return mir_->toGuardClass();
     }
     const LDefinition *tempInt() {
         return getTemp(0);
     }
 };
 
-class MPhi;
-
-// Phi is a pseudo-instruction that emits no code, and is an annotation for the
-// register allocator. Like its equivalent in MIR, phis are collected at the
-// top of blocks and are meant to be executed in parallel, choosing the input
-// corresponding to the predecessor taken in the control flow graph.
-class LPhi MOZ_FINAL : public LNode
-{
-    LAllocation *const inputs_;
-    LDefinition def_;
-
-  public:
-    LIR_HEADER(Phi)
-
-    LPhi(MPhi *ins, LAllocation *inputs)
-        : inputs_(inputs)
-    {
-        setMir(ins);
-    }
-
-    size_t numDefs() const {
-        return 1;
-    }
-    LDefinition *getDef(size_t index) {
-        MOZ_ASSERT(index == 0);
-        return &def_;
-    }
-    void setDef(size_t index, const LDefinition &def) {
-        MOZ_ASSERT(index == 0);
-        def_ = def;
-    }
-    size_t numOperands() const {
-        return mir_->toPhi()->numOperands();
-    }
-    LAllocation *getOperand(size_t index) {
-        MOZ_ASSERT(index < numOperands());
-        return &inputs_[index];
-    }
-    void setOperand(size_t index, const LAllocation &a) {
-        MOZ_ASSERT(index < numOperands());
-        inputs_[index] = a;
-    }
-    size_t numTemps() const {
-        return 0;
-    }
-    LDefinition *getTemp(size_t index) {
-        MOZ_CRASH("no temps");
-    }
-    void setTemp(size_t index, const LDefinition &temp) {
-        MOZ_CRASH("no temps");
-    }
-    size_t numSuccessors() const {
-        return 0;
-    }
-    MBasicBlock *getSuccessor(size_t i) const {
-        MOZ_CRASH("no successors");
-    }
-    void setSuccessor(size_t i, MBasicBlock *) {
-        MOZ_CRASH("no successors");
-    }
-};
-
 class LIn : public LCallInstructionHelper<1, BOX_PIECES+1, 0>
 {
   public:
     LIR_HEADER(In)
     explicit LIn(const LAllocation &rhs) {
         setOperand(RHS, rhs);
     }
 
--- a/js/src/jit/LIR.cpp
+++ b/js/src/jit/LIR.cpp
@@ -112,39 +112,25 @@ LBlock::init(TempAllocator &alloc)
 
             LPhi *lphi = new (&phis_[phiIndex++]) LPhi(phi, inputs);
             lphi->setBlock(this);
         }
     }
     return true;
 }
 
-uint32_t
-LBlock::firstId() const
+const LInstruction *
+LBlock::firstInstructionWithId() const
 {
-    if (phis_.length()) {
-        return phis_[0].id();
-    } else {
-        for (LInstructionIterator i(instructions_.begin()); i != instructions_.end(); i++) {
-            if (i->id())
-                return i->id();
-        }
+    for (LInstructionIterator i(instructions_.begin()); i != instructions_.end(); ++i) {
+        if (i->id())
+            return *i;
     }
     return 0;
 }
-uint32_t
-LBlock::lastId() const
-{
-    LInstruction *last = *instructions_.rbegin();
-    MOZ_ASSERT(last->id());
-    // The last instruction is a control flow instruction which does not have
-    // any output.
-    MOZ_ASSERT(last->numDefs() == 0);
-    return last->id();
-}
 
 LMoveGroup *
 LBlock::getEntryMoveGroup(TempAllocator &alloc)
 {
     if (entryMoveGroup_)
         return entryMoveGroup_;
     entryMoveGroup_ = LMoveGroup::New(alloc);
     if (begin()->isLabel())
--- a/js/src/jit/LIR.h
+++ b/js/src/jit/LIR.h
@@ -707,21 +707,31 @@ class LNode
     virtual void printOperands(FILE *fp);
 
   public:
     // Opcode testing and casts.
 #   define LIROP(name)                                                      \
     bool is##name() const {                                                 \
         return op() == LOp_##name;                                          \
     }                                                                       \
-    inline L##name *to##name();
+    inline L##name *to##name();                                             \
+    inline const L##name *to##name() const;
     LIR_OPCODE_LIST(LIROP)
 #   undef LIROP
 
     virtual bool accept(LElementVisitor *visitor) = 0;
+
+#define LIR_HEADER(opcode)                                                  \
+    Opcode op() const {                                                     \
+        return LInstruction::LOp_##opcode;                                  \
+    }                                                                       \
+    bool accept(LElementVisitor *visitor) {                                 \
+        visitor->setElement(this);                                          \
+        return visitor->visit##opcode(this);                                \
+    }
 };
 
 class LInstruction
   : public LNode
   , public TempObject
   , public InlineListNode<LInstruction>
 {
     // This snapshot could be set after a ResumePoint.  It is used to restart
@@ -814,17 +824,78 @@ class LElementVisitor
 #define VISIT_INS(op) virtual bool visit##op(L##op *) { MOZ_CRASH("NYI: " #op); }
     LIR_OPCODE_LIST(VISIT_INS)
 #undef VISIT_INS
 };
 
 typedef InlineList<LInstruction>::iterator LInstructionIterator;
 typedef InlineList<LInstruction>::reverse_iterator LInstructionReverseIterator;
 
-class LPhi;
+class MPhi;
+
+// Phi is a pseudo-instruction that emits no code, and is an annotation for the
+// register allocator. Like its equivalent in MIR, phis are collected at the
+// top of blocks and are meant to be executed in parallel, choosing the input
+// corresponding to the predecessor taken in the control flow graph.
+class LPhi MOZ_FINAL : public LNode
+{
+    LAllocation *const inputs_;
+    LDefinition def_;
+
+  public:
+    LIR_HEADER(Phi)
+
+    LPhi(MPhi *ins, LAllocation *inputs)
+        : inputs_(inputs)
+    {
+        setMir(ins);
+    }
+
+    size_t numDefs() const {
+        return 1;
+    }
+    LDefinition *getDef(size_t index) {
+        MOZ_ASSERT(index == 0);
+        return &def_;
+    }
+    void setDef(size_t index, const LDefinition &def) {
+        MOZ_ASSERT(index == 0);
+        def_ = def;
+    }
+    size_t numOperands() const {
+        return mir_->toPhi()->numOperands();
+    }
+    LAllocation *getOperand(size_t index) {
+        MOZ_ASSERT(index < numOperands());
+        return &inputs_[index];
+    }
+    void setOperand(size_t index, const LAllocation &a) {
+        MOZ_ASSERT(index < numOperands());
+        inputs_[index] = a;
+    }
+    size_t numTemps() const {
+        return 0;
+    }
+    LDefinition *getTemp(size_t index) {
+        MOZ_CRASH("no temps");
+    }
+    void setTemp(size_t index, const LDefinition &temp) {
+        MOZ_CRASH("no temps");
+    }
+    size_t numSuccessors() const {
+        return 0;
+    }
+    MBasicBlock *getSuccessor(size_t i) const {
+        MOZ_CRASH("no successors");
+    }
+    void setSuccessor(size_t i, MBasicBlock *) {
+        MOZ_CRASH("no successors");
+    }
+};
+
 class LMoveGroup;
 class LBlock
 {
     MBasicBlock *block_;
     FixedList<LPhi> phis_;
     InlineList<LInstruction> instructions_;
     LMoveGroup *entryMoveGroup_;
     LMoveGroup *exitMoveGroup_;
@@ -839,16 +910,19 @@ class LBlock
         instructions_.pushBack(ins);
     }
     size_t numPhis() const {
         return phis_.length();
     }
     LPhi *getPhi(size_t index) {
         return &phis_[index];
     }
+    const LPhi *getPhi(size_t index) const {
+        return &phis_[index];
+    }
     MBasicBlock *mir() const {
         return block_;
     }
     LInstructionIterator begin() {
         return instructions_.begin();
     }
     LInstructionIterator begin(LInstruction *at) {
         return instructions_.begin(at);
@@ -870,18 +944,36 @@ class LBlock
     }
     void insertAfter(LInstruction *at, LInstruction *ins) {
         instructions_.insertAfter(at, ins);
     }
     void insertBefore(LInstruction *at, LInstruction *ins) {
         MOZ_ASSERT(!at->isLabel());
         instructions_.insertBefore(at, ins);
     }
-    uint32_t firstId() const;
-    uint32_t lastId() const;
+    const LNode *firstElementWithId() const {
+        return !phis_.empty()
+               ? static_cast<const LNode *>(getPhi(0))
+               : firstInstructionWithId();
+    }
+    uint32_t firstId() const {
+        return firstElementWithId()->id();
+    }
+    uint32_t lastId() const {
+        return lastInstructionWithId()->id();
+    }
+    const LInstruction *firstInstructionWithId() const;
+    const LInstruction *lastInstructionWithId() const {
+        const LInstruction *last = *instructions_.rbegin();
+        MOZ_ASSERT(last->id());
+        // The last instruction is a control flow instruction which does not have
+        // any output.
+        MOZ_ASSERT(last->numDefs() == 0);
+        return last;
+    }
 
     // Return the label to branch to when branching to this block.
     Label *label() {
         MOZ_ASSERT(!isTrivial());
         return &label_;
     }
 
     LMoveGroup *getEntryMoveGroup(TempAllocator &alloc);
@@ -1707,25 +1799,16 @@ LAllocation::toRegister() const
     if (isFloatReg())
         return AnyRegister(toFloatReg()->reg());
     return AnyRegister(toGeneralReg()->reg());
 }
 
 } // namespace jit
 } // namespace js
 
-#define LIR_HEADER(opcode)                                                  \
-    Opcode op() const {                                                     \
-        return LInstruction::LOp_##opcode;                                  \
-    }                                                                       \
-    bool accept(LElementVisitor *visitor) {                                 \
-        visitor->setElement(this);                                          \
-        return visitor->visit##opcode(this);                                \
-    }
-
 #include "jit/LIR-Common.h"
 #if defined(JS_CODEGEN_X86) || defined(JS_CODEGEN_X64)
 # if defined(JS_CODEGEN_X86)
 #  include "jit/x86/LIR-x86.h"
 # elif defined(JS_CODEGEN_X64)
 #  include "jit/x64/LIR-x64.h"
 # endif
 # include "jit/shared/LIR-x86-shared.h"
@@ -1744,16 +1827,21 @@ LAllocation::toRegister() const
 namespace js {
 namespace jit {
 
 #define LIROP(name)                                                         \
     L##name *LNode::to##name()                                              \
     {                                                                       \
         MOZ_ASSERT(is##name());                                             \
         return static_cast<L##name *>(this);                                \
+    }                                                                       \
+    const L##name *LNode::to##name() const                                  \
+    {                                                                       \
+        MOZ_ASSERT(is##name());                                             \
+        return static_cast<const L##name *>(this);                          \
     }
     LIR_OPCODE_LIST(LIROP)
 #undef LIROP
 
 #define LALLOC_CAST(type)                                                   \
     L##type *LAllocation::to##type() {                                      \
         MOZ_ASSERT(is##type());                                             \
         return static_cast<L##type *>(this);                                \
--- a/js/src/jit/LiveRangeAllocator.cpp
+++ b/js/src/jit/LiveRangeAllocator.cpp
@@ -770,17 +770,17 @@ LiveRangeAllocator<VREG, forLSRA>::build
             DebugOnly<bool> hasUseRegister = false;
             DebugOnly<bool> hasUseRegisterAtStart = false;
 
             for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); inputAlloc.next()) {
                 if (inputAlloc->isUse()) {
                     LUse *use = inputAlloc->toUse();
 
                     // The first instruction, LLabel, has no uses.
-                    MOZ_ASSERT_IF(forLSRA, inputOf(*ins) > outputOf(block->firstId()));
+                    MOZ_ASSERT_IF(forLSRA, inputOf(*ins) > outputOf(block->firstElementWithId()));
 
                     // Call uses should always be at-start or fixed, since the fixed intervals
                     // use all registers.
                     MOZ_ASSERT_IF(ins->isCall() && !inputAlloc.isSnapshotInput(),
                                   use->isFixedRegister() || use->usedAtStart());
 
 #ifdef DEBUG
                     // Don't allow at-start call uses if there are temps of the same kind,
@@ -862,21 +862,19 @@ LiveRangeAllocator<VREG, forLSRA>::build
         // contain any phi outputs.
         for (unsigned int i = 0; i < block->numPhis(); i++) {
             LDefinition *def = block->getPhi(i)->getDef(0);
             if (live->contains(def->virtualRegister())) {
                 live->remove(def->virtualRegister());
             } else {
                 // This is a dead phi, so add a dummy range over all phis. This
                 // can go away if we have an earlier dead code elimination pass.
-                if (!vregs[def].getInterval(0)->addRangeAtHead(entryOf(block),
-                                                               outputOf(block->firstId())))
-                {
+                CodePosition entryPos = entryOf(block);
+                if (!vregs[def].getInterval(0)->addRangeAtHead(entryPos, entryPos.next()))
                     return false;
-                }
             }
         }
 
         if (mblock->isLoopHeader()) {
             // A divergence from the published algorithm is required here, as
             // our block order does not guarantee that blocks of a loop are
             // contiguous. As a result, a single live interval spanning the
             // loop is not possible. Additionally, we require liveIn in a later
--- a/js/src/jit/RegisterAllocator.h
+++ b/js/src/jit/RegisterAllocator.h
@@ -286,47 +286,52 @@ class RegisterAllocator
     }
 
     bool init();
 
     TempAllocator &alloc() const {
         return mir->alloc();
     }
 
-    CodePosition outputOf(uint32_t pos) const {
+    CodePosition outputOf(const LNode *ins) const {
+        return ins->isPhi()
+               ? outputOf(ins->toPhi())
+               : outputOf(ins->toInstruction());
+    }
+    CodePosition outputOf(const LPhi *ins) const {
         // All phis in a block write their outputs after all of them have
         // read their inputs. Consequently, it doesn't make sense to talk
         // about code positions in the middle of a series of phis.
-        if (insData[pos]->isPhi()) {
-            while (insData[pos + 1]->isPhi())
-                ++pos;
-        }
-        return CodePosition(pos, CodePosition::OUTPUT);
+        LBlock *block = ins->block();
+        return CodePosition(block->getPhi(block->numPhis() - 1)->id(), CodePosition::OUTPUT);
+    }
+    CodePosition outputOf(const LInstruction *ins) const {
+        return CodePosition(ins->id(), CodePosition::OUTPUT);
     }
-    CodePosition outputOf(const LNode *ins) const {
-        return outputOf(ins->id());
+    CodePosition inputOf(const LNode *ins) const {
+        return ins->isPhi()
+               ? inputOf(ins->toPhi())
+               : inputOf(ins->toInstruction());
     }
-    CodePosition inputOf(uint32_t pos) const {
+    CodePosition inputOf(const LPhi *ins) const {
         // All phis in a block read their inputs before any of them write their
         // outputs. Consequently, it doesn't make sense to talk about code
         // positions in the middle of a series of phis.
-        if (insData[pos]->isPhi()) {
-            while (pos > 0 && insData[pos - 1]->isPhi())
-                --pos;
-        }
-        return CodePosition(pos, CodePosition::INPUT);
+        return CodePosition(ins->block()->getPhi(0)->id(), CodePosition::INPUT);
     }
-    CodePosition inputOf(const LNode *ins) const {
-        return inputOf(ins->id());
+    CodePosition inputOf(const LInstruction *ins) const {
+        return CodePosition(ins->id(), CodePosition::INPUT);
     }
     CodePosition entryOf(const LBlock *block) {
-        return inputOf(block->firstId());
+        return block->numPhis() != 0
+               ? CodePosition(block->getPhi(0)->id(), CodePosition::INPUT)
+               : inputOf(block->firstInstructionWithId());
     }
     CodePosition exitOf(const LBlock *block) {
-        return outputOf(block->lastId());
+        return outputOf(block->lastInstructionWithId());
     }
 
     LMoveGroup *getInputMoveGroup(uint32_t id);
     LMoveGroup *getMoveGroupAfter(uint32_t id);
 
     LMoveGroup *getInputMoveGroup(CodePosition pos) {
         return getInputMoveGroup(pos.ins());
     }