1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/ValueNumbering.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,138 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jit_ValueNumbering_h
1.11 +#define jit_ValueNumbering_h
1.12 +
1.13 +#include "jit/MIR.h"
1.14 +
1.15 +namespace js {
1.16 +namespace jit {
1.17 +
1.18 +class ValueNumberer
1.19 +{
1.20 + protected:
1.21 + struct ValueHasher
1.22 + {
1.23 + typedef MDefinition * Lookup;
1.24 + typedef MDefinition * Key;
1.25 + static HashNumber hash(const Lookup &ins) {
1.26 + return ins->valueHash();
1.27 + }
1.28 +
1.29 + static bool match(const Key &k, const Lookup &l) {
1.30 + // If one of the instructions depends on a store, and the
1.31 + // other instruction does not depend on the same store,
1.32 + // the instructions are not congruent.
1.33 + if (k->dependency() != l->dependency())
1.34 + return false;
1.35 + return k->congruentTo(l);
1.36 + }
1.37 + };
1.38 +
1.39 + typedef HashMap<MDefinition *,
1.40 + uint32_t,
1.41 + ValueHasher,
1.42 + IonAllocPolicy> ValueMap;
1.43 +
1.44 + struct DominatingValue
1.45 + {
1.46 + MDefinition *def;
1.47 + uint32_t validUntil;
1.48 + };
1.49 +
1.50 + typedef HashMap<uint32_t,
1.51 + DominatingValue,
1.52 + DefaultHasher<uint32_t>,
1.53 + IonAllocPolicy> InstructionMap;
1.54 +
1.55 + protected:
1.56 + TempAllocator &alloc() const;
1.57 + uint32_t lookupValue(MDefinition *ins);
1.58 + MDefinition *findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index);
1.59 +
1.60 + MDefinition *simplify(MDefinition *def, bool useValueNumbers);
1.61 + MControlInstruction *simplifyControlInstruction(MControlInstruction *def);
1.62 + bool eliminateRedundancies();
1.63 +
1.64 + bool computeValueNumbers();
1.65 +
1.66 + inline bool isMarked(MDefinition *def) {
1.67 + return pessimisticPass_ || def->isInWorklist();
1.68 + }
1.69 +
1.70 + void markDefinition(MDefinition *def);
1.71 + void unmarkDefinition(MDefinition *def);
1.72 +
1.73 + void markConsumers(MDefinition *def);
1.74 + void markBlock(MBasicBlock *block);
1.75 + void setClass(MDefinition *toSet, MDefinition *representative);
1.76 +
1.77 + public:
1.78 + static MDefinition *findSplit(MDefinition *);
1.79 + void breakClass(MDefinition*);
1.80 +
1.81 + protected:
1.82 + MIRGenerator *mir;
1.83 + MIRGraph &graph_;
1.84 + ValueMap values;
1.85 + bool pessimisticPass_;
1.86 + size_t count_;
1.87 +
1.88 + public:
1.89 + ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic);
1.90 + bool analyze();
1.91 + bool clear();
1.92 +};
1.93 +
1.94 +class ValueNumberData : public TempObject {
1.95 +
1.96 + friend void ValueNumberer::breakClass(MDefinition*);
1.97 + friend MDefinition *ValueNumberer::findSplit(MDefinition*);
1.98 + uint32_t number;
1.99 + MDefinition *classNext;
1.100 + MDefinition *classPrev;
1.101 +
1.102 + public:
1.103 + ValueNumberData() : number(0), classNext(nullptr), classPrev(nullptr) {}
1.104 +
1.105 + void setValueNumber(uint32_t number_) {
1.106 + number = number_;
1.107 + }
1.108 +
1.109 + uint32_t valueNumber() {
1.110 + return number;
1.111 + }
1.112 + // Set the class of this to the given representative value.
1.113 + void setClass(MDefinition *thisDef, MDefinition *rep) {
1.114 + JS_ASSERT(thisDef->valueNumberData() == this);
1.115 + // If we are attempting to insert ourself, then nothing needs to be done.
1.116 + // However, if the definition to be inserted already has the correct value number,
1.117 + // it still needs to be inserted, since the value number needs to be updated lazily.
1.118 + // this updating tactic can leave the world in a state where thisDef is not in the
1.119 + // equivalence class of rep, but it has the same value number. Defs in this state
1.120 + // need to be re-processed.
1.121 + if (this == rep->valueNumberData())
1.122 + return;
1.123 +
1.124 + if (classNext)
1.125 + classNext->valueNumberData()->classPrev = classPrev;
1.126 + if (classPrev)
1.127 + classPrev->valueNumberData()->classNext = classNext;
1.128 +
1.129 +
1.130 + classPrev = rep;
1.131 + classNext = rep->valueNumberData()->classNext;
1.132 +
1.133 + if (rep->valueNumberData()->classNext)
1.134 + rep->valueNumberData()->classNext->valueNumberData()->classPrev = thisDef;
1.135 + rep->valueNumberData()->classNext = thisDef;
1.136 + }
1.137 +};
1.138 +} // namespace jit
1.139 +} // namespace js
1.140 +
1.141 +#endif /* jit_ValueNumbering_h */
