Fix GVN by implementing congruence classes as a list, attempt 2 (bug 723536, r=dvander)
authorMarty Rosenberg <mrosenberg@mozilla.com>
Fri, 02 Mar 2012 09:34:46 -0800
changeset 89503 1d0f999708ca0f92ed118bfe29121d9ac0585759
parent 89502 ea48d5e141e78e1ae8f488760bbe8d05197c1d9f
child 89504 60def326b4d02d4b20b0575364c9bedaf3db3fe6
push id696
push usermrosenberg@mozilla.com
push dateFri, 09 Mar 2012 09:00:05 +0000
reviewersdvander
bugs723536
milestone13.0a1
Fix GVN by implementing congruence classes as a list, attempt 2 (bug 723536, r=dvander)
js/src/ion/Ion.h
js/src/ion/MIR.h
js/src/ion/ValueNumbering.cpp
js/src/ion/ValueNumbering.h
--- a/js/src/ion/Ion.h
+++ b/js/src/ion/Ion.h
@@ -112,17 +112,17 @@ struct IonOptions
 
         // Eagerly inline calls to improve test coverage.
         usesBeforeInlining = usesBeforeCompile;
     }
 
     IonOptions()
       : enabled(false),
         gvn(true),
-        gvnIsOptimistic(false),
+        gvnIsOptimistic(true),
         licm(true),
         osr(true),
         lsra(true),
         inlining(true),
         usesBeforeCompile(40),
         usesBeforeInlining(10240)
     { }
 };
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -56,17 +56,17 @@
 #include "InlineList.h"
 #include "MOpcodes.h"
 #include "FixedArityList.h"
 #include "IonMacroAssembler.h"
 #include "Bailouts.h"
 
 namespace js {
 namespace ion {
-
+class ValueNumberData;
 static const inline
 MIRType MIRTypeFromValue(const js::Value &vp)
 {
     if (vp.isDouble())
         return MIRType_Double;
     return MIRTypeFromValueType(vp.extractNonDoubleType());
 }
 
@@ -250,17 +250,17 @@ class MDefinition : public MNode
 #   undef DEFINE_OPCODES
         Op_Invalid
     };
 
   private:
     InlineForwardList<MUse> uses_; // Use chain.
     uint32 id_;                    // Instruction ID, which after block re-ordering
                                    // is sorted within a basic block.
-    uint32 valueNumber_;           // The instruction's value number (see GVN for details in use)
+    ValueNumberData *valueNumber_; // The instruction's value number (see GVN for details in use)
     MIRType resultType_;           // Representation of result type.
     uint32 flags_;                 // Bit flags.
     MDefinition *dependency_;      // Implicit dependency (store, call, etc.) of this instruction.
 
   private:
     enum Flag {
         None = 0,
 #   define DEFINE_FLAG(flag) flag,
@@ -296,17 +296,17 @@ class MDefinition : public MNode
     jsbytecode *trackedPc() {
         return trackedPc_;
     }
 #endif
 
   public:
     MDefinition()
       : id_(0),
-        valueNumber_(0),
+        valueNumber_(NULL),
         resultType_(MIRType_None),
         flags_(0),
         dependency_(NULL)
 #ifdef TRACK_SNAPSHOTS
       , trackedPc_(NULL)
 #endif
     { }
 
@@ -329,22 +329,23 @@ class MDefinition : public MNode
     uint32 id() const {
         JS_ASSERT(block_);
         return id_;
     }
     void setId(uint32 id) {
         id_ = id;
     }
 
-    uint32 valueNumber() const {
-        JS_ASSERT(block_);
+    uint32 valueNumber() const;
+    void setValueNumber(uint32 vn);
+    ValueNumberData *valueNumberData() {
         return valueNumber_;
     }
-
-    void setValueNumber(uint32 vn) {
+    void setValueNumberData(ValueNumberData *vn) {
+        JS_ASSERT(valueNumber_ == NULL);
         valueNumber_ = vn;
     }
 #define FLAG_ACCESSOR(flag) \
     bool is##flag() const {\
         return hasFlags(1 << flag);\
     }\
     void set##flag() {\
         JS_ASSERT(!hasFlags(1 << flag));\
--- a/js/src/ion/ValueNumbering.cpp
+++ b/js/src/ion/ValueNumbering.cpp
@@ -54,35 +54,42 @@ ValueNumberer::ValueNumberer(MIRGraph &g
 { }
 
 uint32
 ValueNumberer::lookupValue(MDefinition *ins)
 {
 
     ValueMap::AddPtr p = values.lookupForAdd(ins);
 
-    if (!p) {
+    if (p) {
+        // make sure this is in the correct group
+        setClass(ins, p->key);
+    } else {
         if (!values.add(p, ins, ins->id()))
             return 0;
+        breakClass(ins);
     }
 
     return p->value;
 }
 
 MDefinition *
 ValueNumberer::simplify(MDefinition *def, bool useValueNumbers)
 {
     if (def->isEffectful())
         return def;
 
     MDefinition *ins = def->foldsTo(useValueNumbers);
 
     if (ins == def || !ins->updateForReplacement(def))
         return def;
 
+    // ensure this instruction has a VN
+    if (!ins->valueNumberData())
+        ins->setValueNumberData(new ValueNumberData);
     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());
@@ -165,16 +172,23 @@ ValueNumberer::computeValueNumbers()
     // values that enter Phi nodes through back edges. We then make one pass
     // through the graph, ignoring back edges. This yields less congruences on
     // any graph with back-edges, but is much faster to perform.
 
     IonSpew(IonSpew_GVN, "Numbering instructions");
 
     if (!values.init())
         return false;
+    // Stick a VN object onto every mdefinition
+    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
+        for (MDefinitionIterator iter(*block); iter; iter++)
+            iter->setValueNumberData(new ValueNumberData);
+        MControlInstruction *jump = block->lastIns();
+        jump->setValueNumberData(new ValueNumberData);
+    }
 
     // Assign unique value numbers if pessimistic.
     // It might be productive to do this in the MDefinition constructor or
     // possibly in a previous pass, if it seems reasonable.
     if (pessimisticPass_) {
         for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
             for (MDefinitionIterator iter(*block); iter; iter++)
                 iter->setValueNumber(iter->id());
@@ -401,8 +415,73 @@ ValueNumberer::eliminateRedundancies()
 
 // Exported method, called by the compiler.
 bool
 ValueNumberer::analyze()
 {
     return computeValueNumbers() && eliminateRedundancies();
 }
 
+uint32
+MDefinition::valueNumber() const
+{
+    JS_ASSERT(block_);
+    if (valueNumber_ == NULL)
+        return 0;
+    return valueNumber_->valueNumber();
+}
+void
+MDefinition::setValueNumber(uint32 vn)
+{
+    valueNumber_->setValueNumber(vn);
+}
+// Set the class of this to the given representative value.
+void
+ValueNumberer::setClass(MDefinition *def, MDefinition *rep)
+{
+    def->valueNumberData()->setClass(def, rep);
+}
+
+void
+ValueNumberer::breakClass(MDefinition *def)
+{
+    if (def->valueNumber() == def->id()) {
+        IonSpew(IonSpew_GVN, "Breaking congruence with itself: %d", def->id());
+        ValueNumberData *defdata = def->valueNumberData();
+        JS_ASSERT(defdata->classPrev == NULL);
+        // If the def was the only member of the class, then there is nothing to do.
+        if (defdata->classNext == NULL)
+            return;
+
+        // Get a new representative member
+        MDefinition *newRep = defdata->classNext;
+
+        // Chop off the head of the list (the old representative)
+        newRep->valueNumberData()->classPrev = NULL;
+        def->valueNumberData()->classNext = NULL;
+        IonSpew(IonSpew_GVN, "Choosing a new representative: %d", newRep->id());
+
+        // make the VN of every member in the class the VN of the new representative number.
+        for (MDefinition *tmp = newRep; tmp != NULL; tmp = tmp->valueNumberData()->classNext) {
+            // if this instruction is already scheduled to be processed, don't do anything.
+            if (tmp->isInWorklist())
+                continue;
+            IonSpew(IonSpew_GVN, "Moving to a new congruence class: %d", tmp->id());
+            tmp->setValueNumber(newRep->id());
+            markConsumers(tmp);
+        }
+
+        // Insert the new representative => number mapping into the table
+        values.putNew(newRep, newRep->id());
+    } else {
+        // The element that is breaking from the list isn't the representative element
+        // just strip it from the list
+        ValueNumberData *defdata = def->valueNumberData();
+        if (defdata->classPrev)
+            defdata->classPrev->valueNumberData()->classNext = defdata->classNext;
+        if (defdata->classNext)
+            defdata->classNext->valueNumberData()->classPrev = defdata->classPrev;
+
+        // Make sure there is no nastinees accidentally linking elements into the old list later.
+        defdata->classPrev = NULL;
+        defdata->classNext = NULL;
+    }
+}
--- a/js/src/ion/ValueNumbering.h
+++ b/js/src/ion/ValueNumbering.h
@@ -99,25 +99,61 @@ class ValueNumberer
         return pessimisticPass_ || def->isInWorklist();
     }
 
     void markDefinition(MDefinition *def);
     void unmarkDefinition(MDefinition *def);
 
     void markConsumers(MDefinition *def);
     void markBlock(MBasicBlock *block);
+    void setClass(MDefinition *toSet, MDefinition *representative);
+
+  public:
+    void breakClass(MDefinition*);
 
   protected:
     MIRGraph &graph_;
     ValueMap values;
     bool pessimisticPass_;
     size_t count_;
 
   public:
     ValueNumberer(MIRGraph &graph, bool optimistic);
     bool analyze();
 };
 
+class ValueNumberData : public TempObject {
+
+    friend void ValueNumberer::breakClass(MDefinition*);
+    uint32 number;
+    MDefinition *classNext;
+    MDefinition *classPrev;
+
+  public:
+    ValueNumberData() : number(0), classNext(NULL), classPrev(NULL) {}
+
+    void setValueNumber(uint32 number_) {
+        number = number_;
+    }
+
+    uint32 valueNumber() {
+        return number;
+    }
+    // Set the class of this to the given representative value.
+    void setClass(MDefinition *thisDef, MDefinition *rep) {
+        JS_ASSERT(thisDef->valueNumberData() == this);
+        // If this value should already be in the given set, don't do anything
+        if (number == rep->valueNumber())
+            return;
+        if (classNext)
+            classNext->valueNumberData()->classPrev = classPrev;
+        if (classPrev)
+            classPrev->valueNumberData()->classPrev = classNext;
+        classPrev = rep;
+        classNext = rep->valueNumberData()->classNext;
+        rep->valueNumberData()->classNext = thisDef;
+    }
+};
 } // namespace ion
 } // namespace js
 
 #endif // jsion_value_numbering_h__