michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef jit_ValueNumbering_h
michael@0: #define jit_ValueNumbering_h
michael@0: 
michael@0: #include "jit/MIR.h"
michael@0: 
michael@0: namespace js {
michael@0: namespace jit {
michael@0: 
michael@0: class ValueNumberer
michael@0: {
michael@0:   protected:
michael@0:     struct ValueHasher
michael@0:     {
michael@0:         typedef MDefinition * Lookup;
michael@0:         typedef MDefinition * Key;
michael@0:         static HashNumber hash(const Lookup &ins) {
michael@0:             return ins->valueHash();
michael@0:         }
michael@0: 
michael@0:         static bool match(const Key &k, const Lookup &l) {
michael@0:             // If one of the instructions depends on a store, and the
michael@0:             // other instruction does not depend on the same store,
michael@0:             // the instructions are not congruent.
michael@0:             if (k->dependency() != l->dependency())
michael@0:                 return false;
michael@0:             return k->congruentTo(l);
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     typedef HashMap<MDefinition *,
michael@0:                     uint32_t,
michael@0:                     ValueHasher,
michael@0:                     IonAllocPolicy> ValueMap;
michael@0: 
michael@0:     struct DominatingValue
michael@0:     {
michael@0:         MDefinition *def;
michael@0:         uint32_t validUntil;
michael@0:     };
michael@0: 
michael@0:     typedef HashMap<uint32_t,
michael@0:                     DominatingValue,
michael@0:                     DefaultHasher<uint32_t>,
michael@0:                     IonAllocPolicy> InstructionMap;
michael@0: 
michael@0:   protected:
michael@0:     TempAllocator &alloc() const;
michael@0:     uint32_t lookupValue(MDefinition *ins);
michael@0:     MDefinition *findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index);
michael@0: 
michael@0:     MDefinition *simplify(MDefinition *def, bool useValueNumbers);
michael@0:     MControlInstruction *simplifyControlInstruction(MControlInstruction *def);
michael@0:     bool eliminateRedundancies();
michael@0: 
michael@0:     bool computeValueNumbers();
michael@0: 
michael@0:     inline bool isMarked(MDefinition *def) {
michael@0:         return pessimisticPass_ || def->isInWorklist();
michael@0:     }
michael@0: 
michael@0:     void markDefinition(MDefinition *def);
michael@0:     void unmarkDefinition(MDefinition *def);
michael@0: 
michael@0:     void markConsumers(MDefinition *def);
michael@0:     void markBlock(MBasicBlock *block);
michael@0:     void setClass(MDefinition *toSet, MDefinition *representative);
michael@0: 
michael@0:   public:
michael@0:     static MDefinition *findSplit(MDefinition *);
michael@0:     void breakClass(MDefinition*);
michael@0: 
michael@0:   protected:
michael@0:     MIRGenerator *mir;
michael@0:     MIRGraph &graph_;
michael@0:     ValueMap values;
michael@0:     bool pessimisticPass_;
michael@0:     size_t count_;
michael@0: 
michael@0:   public:
michael@0:     ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic);
michael@0:     bool analyze();
michael@0:     bool clear();
michael@0: };
michael@0: 
michael@0: class ValueNumberData : public TempObject {
michael@0: 
michael@0:     friend void ValueNumberer::breakClass(MDefinition*);
michael@0:     friend MDefinition *ValueNumberer::findSplit(MDefinition*);
michael@0:     uint32_t number;
michael@0:     MDefinition *classNext;
michael@0:     MDefinition *classPrev;
michael@0: 
michael@0:   public:
michael@0:     ValueNumberData() : number(0), classNext(nullptr), classPrev(nullptr) {}
michael@0: 
michael@0:     void setValueNumber(uint32_t number_) {
michael@0:         number = number_;
michael@0:     }
michael@0: 
michael@0:     uint32_t valueNumber() {
michael@0:         return number;
michael@0:     }
michael@0:     // Set the class of this to the given representative value.
michael@0:     void setClass(MDefinition *thisDef, MDefinition *rep) {
michael@0:         JS_ASSERT(thisDef->valueNumberData() == this);
michael@0:         // If we are attempting to insert ourself, then nothing needs to be done.
michael@0:         // However, if the definition to be inserted already has the correct value number,
michael@0:         // it still needs to be inserted, since the value number needs to be updated lazily.
michael@0:         // this updating tactic can leave the world in a state where thisDef is not in the
michael@0:         // equivalence class of rep, but it has the same value number. Defs in this state
michael@0:         // need to be re-processed.
michael@0:         if (this == rep->valueNumberData())
michael@0:             return;
michael@0: 
michael@0:         if (classNext)
michael@0:             classNext->valueNumberData()->classPrev = classPrev;
michael@0:         if (classPrev)
michael@0:             classPrev->valueNumberData()->classNext = classNext;
michael@0: 
michael@0: 
michael@0:         classPrev = rep;
michael@0:         classNext = rep->valueNumberData()->classNext;
michael@0: 
michael@0:         if (rep->valueNumberData()->classNext)
michael@0:             rep->valueNumberData()->classNext->valueNumberData()->classPrev = thisDef;
michael@0:         rep->valueNumberData()->classNext = thisDef;
michael@0:     }
michael@0: };
michael@0: } // namespace jit
michael@0: } // namespace js
michael@0: 
michael@0: #endif /* jit_ValueNumbering_h */