perform algebraic simplification and constant folding (Bug 669789, r=dvander)
authorRyan Pearl <rpearl@mozilla.com>
Fri, 29 Jul 2011 18:55:06 -0700
changeset 74949 526fb26e0ecf489d108dc3235a751f023b891089
parent 74948 089cfaf1c992b46bdeb17953ef62bc81b9720337
child 74950 d3ecc4cdd9ddfa1957d6cc3c4333b25f634522ec
push id102
push userrpearl@mozilla.com
push dateMon, 08 Aug 2011 23:40:27 +0000
reviewersdvander
bugs669789
milestone8.0a1
perform algebraic simplification and constant folding (Bug 669789, r=dvander)
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/ValueNumbering.cpp
js/src/ion/ValueNumbering.h
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -56,16 +56,25 @@ PrintOpcodeName(FILE *fp, MDefinition::O
 #undef NAME
     };
     const char *name = names[op];
     size_t len = strlen(name);
     for (size_t i = 0; i < len; i++)
         fprintf(fp, "%c", tolower(name[i]));
 }
 
+static inline bool
+EqualValues(bool useGVN, MDefinition *left, MDefinition *right)
+{
+    if (useGVN)
+        return left->valueNumber() == right->valueNumber();
+
+    return left->id() == right->id();
+}
+
 void
 MDefinition::printName(FILE *fp)
 {
     PrintOpcodeName(fp, op());
     fprintf(fp, "%u", id());
 
     if (valueNumber() != 0)
         fprintf(fp, "-vn%u", valueNumber());
@@ -93,16 +102,24 @@ MDefinition::congruentTo(MDefinition * c
 
     for (size_t i = 0; i < numOperands(); i++) {
         if (getOperand(i)->valueNumber() != ins->getOperand(i)->valueNumber())
             return false;
     }
 
     return true;
 }
+
+MDefinition *
+MDefinition::foldsTo(bool useValueNumbers)
+{
+    // In the default case, there are no constants to fold.
+    return this;
+}
+
 static const char *MirTypeNames[] =
 {
     "",
     "v",
     "n",
     "b",
     "i",
     "s",
@@ -335,16 +352,32 @@ MGoto::New(MBasicBlock *target)
 }
 
 MPhi *
 MPhi::New(uint32 slot)
 {
     return new MPhi(slot);
 }
 
+MDefinition *
+MPhi::foldsTo(bool useValueNumbers)
+{
+    JS_ASSERT(inputs_.length() != 0);
+
+    MDefinition *first = getOperand(0);
+
+    for (size_t i = 1; i < inputs_.length(); i++) {
+        if (!EqualValues(useValueNumbers, getOperand(i), first))
+            return this;
+    }
+
+    return first;
+}
+
+
 bool
 MPhi::congruentTo(MDefinition *const &ins) const
 {
     if (!ins->isPhi())
         return false;
     // Since we do not know which predecessor we are merging from, we must
     // assume that phi instructions in different blocks are not equal.
     // (Bug 674656)
@@ -370,29 +403,32 @@ MReturn::New(MDefinition *ins)
 void
 MBinaryBitwiseInstruction::infer(const TypeOracle::Binary &b)
 {
     if (b.lhs == MIRType_Object || b.rhs == MIRType_Object)
         specialization_ = MIRType_None;
     else {
         specialization_ = MIRType_Int32;
         setIdempotent();
+        setCommutative();
     }
 }
 
 void
 MBinaryArithInstruction::infer(const TypeOracle::Binary &b)
 {
     if (b.lhs == MIRType_Int32 && b.rhs == MIRType_Int32) {
         specialization_ = MIRType_Int32;
         setIdempotent();
+        setCommutative();
         setResultType(specialization_);
     } else if (b.lhs == MIRType_Double && b.rhs == MIRType_Double) {
         specialization_ = MIRType_Double;
         setIdempotent();
+        setCommutative();
         setResultType(specialization_);
     } else if (b.lhs < MIRType_String && b.rhs < MIRType_String) {
         specialization_ = MIRType_Any;
         if (CoercesToDouble(b.lhs) || CoercesToDouble(b.rhs))
             setResultType(MIRType_Double);
         else
             setResultType(MIRType_Int32);
     } else {
@@ -401,28 +437,151 @@ MBinaryArithInstruction::infer(const Typ
 }
 
 MBitAnd *
 MBitAnd::New(MDefinition *left, MDefinition *right)
 {
     return new MBitAnd(left, right);
 }
 
+static inline int32
+ToInt32(MDefinition *def)
+{
+    JS_ASSERT(def->isConstant());
+    return def->toConstant()->value().toInt32();
+}
+
+static inline double
+ToDouble(MDefinition *def)
+{
+    JS_ASSERT(def->isConstant());
+    return def->toConstant()->value().toDouble();
+}
+
+MDefinition *
+MBitAnd::foldsTo(bool useValueNumbers)
+{
+    if (specialization_ != MIRType_Int32)
+        return this;
+
+    MDefinition *lhs = getOperand(0);
+    MDefinition *rhs = getOperand(1);
+
+    if (lhs->isConstant() && rhs->isConstant()) {
+        js::Value v = Int32Value(ToInt32(lhs) & ToInt32(rhs));
+        return MConstant::New(v);
+    }
+
+    if (lhs->isConstant() && lhs->toConstant()->value() == Int32Value(0))
+        return lhs; // 0 & x => 0
+
+    if (rhs->isConstant() && rhs->toConstant()->value() == Int32Value(0))
+        return rhs; // x & 0 => 0
+
+    if (EqualValues(useValueNumbers, lhs, rhs))
+        return lhs;
+    return this;
+}
+
+
 MBitOr *
 MBitOr::New(MDefinition *left, MDefinition *right)
 {
     return new MBitOr(left, right);
 }
 
+MDefinition *
+MBitOr::foldsTo(bool useValueNumbers)
+{
+    if (specialization_ != MIRType_Int32)
+        return this;
+
+    MDefinition *lhs = getOperand(0);
+    MDefinition *rhs = getOperand(1);
+
+    if (lhs->isConstant() && rhs->isConstant()) {
+        js::Value v = Int32Value(ToInt32(lhs) | ToInt32(rhs));
+        return MConstant::New(v);
+    }
+
+    if (lhs->isConstant() && lhs->toConstant()->value() == Int32Value(0))
+        return rhs; // 0 | x => x
+
+    if (rhs->isConstant() && rhs->toConstant()->value() == Int32Value(0))
+        return lhs; // x | 0 => x
+
+    if (EqualValues(useValueNumbers, lhs, rhs))
+        return lhs; // x | x => x
+
+    return this;
+}
+
 MBitXor *
 MBitXor::New(MDefinition *left, MDefinition *right)
 {
     return new MBitXor(left, right);
 }
 
+MDefinition *
+MBitXor::foldsTo(bool useValueNumbers)
+{
+    if (specialization_ != MIRType_Int32)
+        return this;
+
+    MDefinition *lhs = getOperand(0);
+    MDefinition *rhs = getOperand(1);
+
+    if (lhs->isConstant() && rhs->isConstant()) {
+        js::Value v = Int32Value(ToInt32(lhs) ^ ToInt32(rhs));
+        return MConstant::New(v);
+    }
+
+    if (lhs->isConstant() && lhs->toConstant()->value() == Int32Value(0))
+        return rhs; // 0 ^ x => x
+
+    if (rhs->isConstant() && rhs->toConstant()->value() == Int32Value(0))
+        return lhs; // x ^ 0 => x
+
+    if (EqualValues(useValueNumbers, lhs, rhs))
+        return MConstant::New(Int32Value(0)); // x ^ x => x
+
+    return this;
+}
+
+
+MDefinition *
+MAdd::foldsTo(bool useValueNumbers)
+{
+    MDefinition *lhs = getOperand(0);
+    MDefinition *rhs = getOperand(1);
+    js::Value val;
+    if (specialization_ == MIRType_Int32) {
+        if (lhs->isConstant() && rhs->isConstant()) {
+            val = Int32Value(ToInt32(lhs) + ToInt32(rhs));
+            return MConstant::New(val);
+        }
+        val = Int32Value(0);
+    } else if (specialization_ == MIRType_Double) {
+        if (lhs->isConstant() && rhs->isConstant()) {
+            val = DoubleValue (ToDouble(lhs) + ToDouble(rhs));
+            return MConstant::New(val);
+        }
+        val = DoubleValue(0.0);
+    } else {
+        return this; // No specialization
+    }
+
+    if (lhs->isConstant() && lhs->toConstant()->value() == val)
+        return rhs; // 0 + x => x
+    if (rhs->isConstant() && rhs->toConstant()->value() == val)
+        return lhs; // x + 0 => x
+
+    return this;
+}
+
 MSnapshot *
 MSnapshot::New(MBasicBlock *block, jsbytecode *pc)
 {
     MSnapshot *snapshot = new MSnapshot(block, pc);
     if (!snapshot->init(block))
         return NULL;
     snapshot->inherit(block);
     return snapshot;
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -80,16 +80,17 @@ MIRType MIRTypeFromValue(const js::Value
         return MIRType_None;
     }
 }
 
 #define MIR_FLAG_LIST(_)                                                    \
     _(InWorklist)                                                           \
     _(EmittedAtUses)                                                        \
     _(LoopInvariant)                                                        \
+    _(Commutative)                                                          \
     _(Idempotent) /* The instruction has no side-effects. */                \
     _(NeverHoisted) /* Don't hoist, even if loop invariant */
 
 class MDefinition;
 class MInstruction;
 class MBasicBlock;
 class MNode;
 class MUse;
@@ -157,17 +158,16 @@ class MNode : public TempObject
 
     bool isDefinition() const {
         return kind() == Definition;
     }
     bool isSnapshot() const {
         return kind() == Snapshot;
     }
     MBasicBlock *block() const {
-        JS_ASSERT(block_);
         return block_;
     }
 
     // Instructions needing to hook into type analysis should return a
     // TypePolicy.
     virtual TypePolicy *typePolicy() {
         return NULL;
     }
@@ -244,16 +244,17 @@ class MDefinition : public MNode
     { }
 
     virtual Opcode op() const = 0;
     void printName(FILE *fp);
     virtual void printOpcode(FILE *fp);
 
     virtual HashNumber valueHash() const;
     virtual bool congruentTo(MDefinition* const &ins) const;
+    virtual MDefinition *foldsTo(bool useValueNumbers);
 
     MNode::Kind kind() const {
         return MNode::Definition;
     }
 
     uint32 id() const {
         JS_ASSERT(block_);
         return id_;
@@ -309,16 +310,20 @@ class MDefinition : public MNode
     }
 
     // Removes a use at the given position
     MUseIterator removeUse(MUseIterator use);
 
     // Number of uses of this instruction.
     size_t useCount() const;
 
+    bool hasUses() const {
+        return !uses_.empty();
+    }
+
     virtual bool isControlInstruction() {
         return false;
     }
 
     void addUse(MNode *node, size_t index) {
         uses_.pushFront(MUse::New(node, index));
     }
     void replaceAllUsesWith(MDefinition *dom);
@@ -760,16 +765,51 @@ class MUnaryInstruction : public MAryIns
 class MBinaryInstruction : public MAryInstruction<2>
 {
   protected:
     MBinaryInstruction(MDefinition *left, MDefinition *right)
     {
         initOperand(0, left);
         initOperand(1, right);
     }
+
+    HashNumber valueHash() const
+    {
+        MDefinition *lhs = getOperand(0);
+        MDefinition *rhs = getOperand(1);
+
+        return op() ^ lhs->valueNumber() ^ rhs->valueNumber();
+    }
+
+    bool congruentTo(MDefinition *const &ins) const
+    {
+        if (op() != ins->op())
+            return false;
+
+        MDefinition *left = getOperand(0);
+        MDefinition *right = getOperand(1);
+        MDefinition *tmp;
+
+        if (isCommutative() && left->valueNumber() > right->valueNumber()) {
+            tmp = right;
+            right = left;
+            left = tmp;
+        }
+
+        MDefinition *insLeft = ins->getOperand(0);
+        MDefinition *insRight = ins->getOperand(1);
+        if (isCommutative() && insLeft->valueNumber() > insRight->valueNumber()) {
+            tmp = insRight;
+            insRight = insLeft;
+            insLeft = tmp;
+        }
+
+        return (left->valueNumber() == insLeft->valueNumber()) &&
+               (right->valueNumber() == insRight->valueNumber());
+    }
 };
 
 // Wraps an SSA name in a new SSA name. This is used for correctness while
 // constructing SSA, and is removed immediately after the initial SSA is built.
 class MCopy : public MUnaryInstruction
 {
     MCopy(MDefinition *ins)
       : MUnaryInstruction(ins)
@@ -907,38 +947,41 @@ class MBitAnd : public MBinaryBitwiseIns
 {
     MBitAnd(MDefinition *left, MDefinition *right)
       : MBinaryBitwiseInstruction(left, right)
     { }
 
   public:
     INSTRUCTION_HEADER(BitAnd);
     static MBitAnd *New(MDefinition *left, MDefinition *right);
+    MDefinition *foldsTo(bool useValueNumbers);
 };
 
 class MBitOr : public MBinaryBitwiseInstruction
 {
     MBitOr(MDefinition *left, MDefinition *right)
       : MBinaryBitwiseInstruction(left, right)
     { }
 
   public:
     INSTRUCTION_HEADER(BitOr);
     static MBitOr *New(MDefinition *left, MDefinition *right);
+    MDefinition *foldsTo(bool useValueNumbers);
 };
 
 class MBitXor : public MBinaryBitwiseInstruction
 {
     MBitXor(MDefinition *left, MDefinition *right)
       : MBinaryBitwiseInstruction(left, right)
     { }
 
   public:
     INSTRUCTION_HEADER(BitXor);
     static MBitXor *New(MDefinition *left, MDefinition *right);
+    MDefinition *foldsTo(bool useValueNumbers);
 };
 
 class MBinaryArithInstruction
   : public MBinaryInstruction,
     public BinaryArithPolicy
 {
   public:
     MBinaryArithInstruction(MDefinition *left, MDefinition *right)
@@ -962,16 +1005,17 @@ class MAdd : public MBinaryArithInstruct
         setResultType(MIRType_Value);
     }
 
   public:
     INSTRUCTION_HEADER(Add);
     static MAdd *New(MDefinition *left, MDefinition *right) {
         return new MAdd(left, right);
     }
+    MDefinition *foldsTo(bool useValueNumbers);
 };
 
 class MPhi : public MDefinition, public InlineForwardListNode<MPhi>
 {
     js::Vector<MDefinition *, 2, IonAllocPolicy> inputs_;
     uint32 slot_;
     bool triedToSpecialize_;
 
@@ -1004,16 +1048,18 @@ class MPhi : public MDefinition, public 
         return triedToSpecialize_;
     }
     void specialize(MIRType type) {
         triedToSpecialize_ = true;
         setResultType(type);
     }
     bool addInput(MDefinition *ins);
 
+    MDefinition *foldsTo(bool useValueNumbers);
+
     bool congruentTo(MDefinition * const &ins) const;
 };
 
 // A snapshot contains the information needed to reconstruct the interpreter
 // state from a position in the JIT. See the big comment near snapshot() in
 // IonBuilder.cpp.
 class MSnapshot : public MNode
 {
--- a/js/src/ion/ValueNumbering.cpp
+++ b/js/src/ion/ValueNumbering.cpp
@@ -61,16 +61,48 @@ ValueNumberer::lookupValue(ValueMap &val
     if (!p) {
         if (!values.add(p, ins, ins->id()))
             return 0;
     }
 
     return p->value;
 }
 
+MDefinition *
+ValueNumberer::simplify(MDefinition *def, bool useValueNumbers)
+{
+    if (!def->isIdempotent())
+        return def;
+
+    MDefinition *ins = def->foldsTo(useValueNumbers);
+
+    if (ins == def)
+        return def;
+
+    if (!ins->block()) {
+        // In this case, we made a new def by constant folding, for
+        // example, we replaced add(#3,#4) with a new const(#7) node.
+
+        // We will only fold a phi into one of its operands.
+        JS_ASSERT(!def->isPhi());
+
+        def->block()->insertAfter(def->toInstruction(), ins->toInstruction());
+    }
+
+    JS_ASSERT(ins->id() != 0);
+
+    def->replaceAllUsesWith(ins);
+
+    IonSpew(IonSpew_GVN, "Folding %d to be %d", def->id(), ins->id());
+    return ins;
+}
+
+
+
+
 bool
 ValueNumberer::computeValueNumbers()
 {
     // At the end of this function, we will have the value numbering stored in
     // each instruction.
     //
     // We also need an "optimistic" value number, for temporary use, which is
     // stored in a hashtable.
@@ -109,30 +141,38 @@ ValueNumberer::computeValueNumbers()
         }
     }
 
     bool changed = true;
     while (changed) {
         changed = false;
 
         for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
-            for (MDefinitionIterator iter(*block); iter; iter++) {
-                MDefinition *ins = *iter;
+            for (MDefinitionIterator iter(*block); iter; ) {
+                MDefinition *ins = simplify(*iter, false);
+
+                if (ins != *iter || !ins->hasUses()) {
+                    iter = block->removeDefAt(iter);
+                    continue;
+                }
 
                 uint32 value = lookupValue(values, ins);
 
                 if (!value)
                     return false; // Hashtable insertion failed
 
                 if (ins->valueNumber() != value) {
-                    IonSpew(IonSpew_GVN, "Broke congruence for instruction %d (%p) with VN %d (now using %d)",
+                    IonSpew(IonSpew_GVN,
+                            "Broke congruence for instruction %d (%p) with VN %d (now using %d)",
                             ins->id(), ins, ins->valueNumber(), value);
                     ins->setValueNumber(value);
                     changed = true;
                 }
+
+                iter++;
             }
         }
         values.clear();
 
         // If we are doing a pessimistic pass, we only go once through the
         // instruction list.
         if (pessimisticPass_)
             break;
@@ -208,38 +248,47 @@ ValueNumberer::eliminateRedundancies()
         MBasicBlock *block = nodes.popCopy();
 
         IonSpew(IonSpew_GVN, "Looking at block %d", block->id());
 
         for (size_t i = 0; i < block->numImmediatelyDominatedBlocks(); i++) {
             if (!nodes.append(block->getImmediatelyDominatedBlock(i)))
                 return false;
         }
-        MDefinitionIterator i(block);
-        while (i) {
-            MDefinition *ins = *i;
+        for (MDefinitionIterator iter(block); iter; ) {
+            MDefinition *ins = simplify(*iter, true);
+
+            if (ins != *iter || !ins->hasUses()) {
+                iter = block->removeDefAt(iter);
+                continue;
+            }
+
+            if (!ins->isIdempotent()) {
+                iter++;
+                continue;
+            }
 
             MDefinition *dom = findDominatingDef(defs, ins, index);
 
             if (!dom)
                 return false; // Insertion failed
 
             if (dom == ins) {
-                i++;
+                iter++;
                 continue;
             }
 
             IonSpew(IonSpew_GVN, "instruction %d is dominated by instruction %d (from block %d)",
                     ins->id(), dom->id(), dom->block()->id());
 
             ins->replaceAllUsesWith(dom);
 
-            JS_ASSERT(ins->useCount() == 0);
+            JS_ASSERT(!ins->hasUses());
             JS_ASSERT(ins->block() == block);
-            i = ins->block()->removeDefAt(i);
+            iter = ins->block()->removeDefAt(iter);
         }
         index++;
     }
 
     JS_ASSERT(index == graph_.numBlocks());
     return true;
 }
 
--- a/js/src/ion/ValueNumbering.h
+++ b/js/src/ion/ValueNumbering.h
@@ -80,16 +80,18 @@ class ValueNumberer
                     DefaultHasher<uint32>,
                     IonAllocPolicy> InstructionMap;
 
     MIRGraph &graph_;
     bool pessimisticPass_;
 
     uint32 lookupValue(ValueMap &values, MDefinition *ins);
     MDefinition *findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index);
+
+    MDefinition *simplify(MDefinition *def, bool useValueNumbers);
     bool eliminateRedundancies();
 
     bool computeValueNumbers();
 
   public:
     ValueNumberer(MIRGraph &graph, bool optimistic);
     bool analyze();
 };