diff -r 000000000000 -r 6474c204b198 js/src/jit/ValueNumbering.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/ValueNumbering.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,576 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "jit/ValueNumbering.h" + +#include "jit/IonSpewer.h" +#include "jit/MIRGenerator.h" +#include "jit/MIRGraph.h" + +using namespace js; +using namespace js::jit; + +ValueNumberer::ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic) + : mir(mir), + graph_(graph), + values(graph.alloc()), + pessimisticPass_(!optimistic), + count_(0) +{ } + +TempAllocator & +ValueNumberer::alloc() const +{ + return graph_.alloc(); +} + +uint32_t +ValueNumberer::lookupValue(MDefinition *ins) +{ + ValueMap::AddPtr p = values.lookupForAdd(ins); + if (p) { + // make sure this is in the correct group + setClass(ins, p->key()); + return p->value(); + } + + if (!values.add(p, ins, ins->id())) + return 0; + breakClass(ins); + + return ins->id(); +} + +MDefinition * +ValueNumberer::simplify(MDefinition *def, bool useValueNumbers) +{ + if (def->isEffectful()) + return def; + + MDefinition *ins = def->foldsTo(alloc(), useValueNumbers); + if (ins == def) + return def; + + // Ensure this instruction has a value number. + if (!ins->valueNumberData()) + ins->setValueNumberData(new(alloc()) 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()); + ins->setValueNumber(lookupValue(ins)); + } + + JS_ASSERT(ins->id() != 0); + + def->replaceAllUsesWith(ins); + + IonSpew(IonSpew_GVN, "Folding %d to be %d", def->id(), ins->id()); + return ins; +} + +MControlInstruction * +ValueNumberer::simplifyControlInstruction(MControlInstruction *def) +{ + if (def->isEffectful()) + return def; + + MDefinition *repl = def->foldsTo(alloc(), false); + if (repl == def) + return def; + + // Ensure this instruction has a value number. + if (!repl->valueNumberData()) + repl->setValueNumberData(new(alloc()) ValueNumberData); + + MBasicBlock *block = def->block(); + + // MControlInstructions should not have consumers. + JS_ASSERT(repl->isControlInstruction()); + JS_ASSERT(!def->hasUses()); + + if (def->isInWorklist()) + repl->setInWorklist(); + + block->discardLastIns(); + block->end((MControlInstruction *)repl); + return (MControlInstruction *)repl; +} + +void +ValueNumberer::markDefinition(MDefinition *def) +{ + if (isMarked(def)) + return; + + IonSpew(IonSpew_GVN, "marked %d", def->id()); + def->setInWorklist(); + count_++; +} + +void +ValueNumberer::unmarkDefinition(MDefinition *def) +{ + if (pessimisticPass_) + return; + + JS_ASSERT(count_ > 0); + IonSpew(IonSpew_GVN, "unmarked %d", def->id()); + def->setNotInWorklist(); + count_--; +} + +void +ValueNumberer::markBlock(MBasicBlock *block) +{ + for (MDefinitionIterator iter(block); iter; iter++) + markDefinition(*iter); + markDefinition(block->lastIns()); +} + +void +ValueNumberer::markConsumers(MDefinition *def) +{ + if (pessimisticPass_) + return; + + JS_ASSERT(!def->isInWorklist()); + JS_ASSERT(!def->isControlInstruction()); + for (MUseDefIterator use(def); use; use++) + markDefinition(use.def()); +} + +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. + // + // For the instruction x := y op z, we map (op, VN[y], VN[z]) to a value + // number, say v. If it is not in the map, we use the instruction id. + // + // If the instruction in question's value number is not already + // v, we break the congruence and set it to v. We repeat until saturation. + // This will take at worst O(d) time, where d is the loop connectedness + // of the SSA def/use graph. + // + // The algorithm is the simple RPO-based algorithm from + // "SCC-Based Value Numbering" by Cooper and Simpson. + // + // If we are performing a pessimistic pass, then we assume that every + // definition is in its own congruence class, since we know nothing about + // 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++) { + if (mir->shouldCancel("Value Numbering (preparation loop")) + return false; + for (MDefinitionIterator iter(*block); iter; iter++) + iter->setValueNumberData(new(alloc()) ValueNumberData); + MControlInstruction *jump = block->lastIns(); + jump->setValueNumberData(new(alloc()) 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()); + } + } else { + // For each root block, add all of its instructions to the worklist. + markBlock(*(graph_.begin())); + if (graph_.osrBlock()) + markBlock(graph_.osrBlock()); + } + + while (count_ > 0) { +#ifdef DEBUG + if (!pessimisticPass_) { + size_t debugCount = 0; + IonSpew(IonSpew_GVN, "The following instructions require processing:"); + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + for (MDefinitionIterator iter(*block); iter; iter++) { + if (iter->isInWorklist()) { + IonSpew(IonSpew_GVN, "\t%d", iter->id()); + debugCount++; + } + } + if (block->lastIns()->isInWorklist()) { + IonSpew(IonSpew_GVN, "\t%d", block->lastIns()->id()); + debugCount++; + } + } + if (!debugCount) + IonSpew(IonSpew_GVN, "\tNone"); + JS_ASSERT(debugCount == count_); + } +#endif + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + if (mir->shouldCancel("Value Numbering (main loop)")) + return false; + for (MDefinitionIterator iter(*block); iter; ) { + + if (!isMarked(*iter)) { + iter++; + continue; + } + + JS_ASSERT_IF(!pessimisticPass_, count_ > 0); + unmarkDefinition(*iter); + + MDefinition *ins = simplify(*iter, false); + + if (ins != *iter) { + iter = block->discardDefAt(iter); + continue; + } + + // Don't bother storing this instruction in the HashMap if + // (a) eliminateRedundancies will never eliminate it (because + // it's non-movable or effectful) and (b) no other instruction's + // value number depends on it. + if (!ins->hasDefUses() && (!ins->isMovable() || ins->isEffectful())) { + iter++; + continue; + } + + uint32_t value = lookupValue(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)", + ins->id(), (void *) ins, ins->valueNumber(), value); + ins->setValueNumber(value); + markConsumers(ins); + } + + iter++; + } + // Process control flow instruction: + MControlInstruction *jump = block->lastIns(); + jump = simplifyControlInstruction(jump); + + // If we are pessimistic, then this will never get set. + if (!jump->isInWorklist()) + continue; + unmarkDefinition(jump); + if (jump->valueNumber() == 0) { + jump->setValueNumber(jump->id()); + for (size_t i = 0; i < jump->numSuccessors(); i++) + markBlock(jump->getSuccessor(i)); + } + + } + + // If we are doing a pessimistic pass, we only go once through the + // instruction list. + if (pessimisticPass_) + break; + } +#ifdef DEBUG + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + for (MDefinitionIterator iter(*block); iter; iter++) { + JS_ASSERT(!iter->isInWorklist()); + JS_ASSERT_IF(iter->valueNumber() == 0, + !iter->hasDefUses() && (!iter->isMovable() || iter->isEffectful())); + } + } +#endif + return true; +} + +MDefinition * +ValueNumberer::findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index) +{ + JS_ASSERT(ins->valueNumber() != 0); + InstructionMap::Ptr p = defs.lookup(ins->valueNumber()); + MDefinition *dom; + if (!p || index > p->value().validUntil) { + DominatingValue value; + value.def = ins; + // Since we are traversing the dominator tree in pre-order, when we + // are looking at the |index|-th block, the next numDominated() blocks + // we traverse are precisely the set of blocks that are dominated. + // + // So, this value is visible in all blocks if: + // index <= index + ins->block->numDominated() + // and becomes invalid after that. + value.validUntil = index + ins->block()->numDominated(); + + if(!defs.put(ins->valueNumber(), value)) + return nullptr; + + dom = ins; + } else { + dom = p->value().def; + } + + return dom; +} + +bool +ValueNumberer::eliminateRedundancies() +{ + // A definition is 'redundant' iff it is dominated by another definition + // with the same value number. + // + // So, we traverse the dominator tree in pre-order, maintaining a hashmap + // from value numbers to instructions. + // + // For each definition d with value number v, we look up v in the hashmap. + // + // If there is a definition d' in the hashmap, and the current traversal + // index is within that instruction's dominated range, then we eliminate d, + // replacing all uses of d with uses of d'. + // + // If there is no valid definition in the hashtable (the current definition + // is not in dominated scope), then we insert the current instruction, + // since it is the most dominant instruction with the given value number. + + InstructionMap defs(alloc()); + + if (!defs.init()) + return false; + + IonSpew(IonSpew_GVN, "Eliminating redundant instructions"); + + // Stack for pre-order CFG traversal. + Vector worklist(alloc()); + + // The index of the current block in the CFG traversal. + size_t index = 0; + + // Add all self-dominating blocks to the worklist. + // This includes all roots. Order does not matter. + for (MBasicBlockIterator i(graph_.begin()); i != graph_.end(); i++) { + MBasicBlock *block = *i; + if (block->immediateDominator() == block) { + if (!worklist.append(block)) + return false; + } + } + + // Starting from each self-dominating block, traverse the CFG in pre-order. + while (!worklist.empty()) { + if (mir->shouldCancel("Value Numbering (eliminate loop)")) + return false; + MBasicBlock *block = worklist.popCopy(); + + IonSpew(IonSpew_GVN, "Looking at block %d", block->id()); + + // Add all immediate dominators to the front of the worklist. + if (!worklist.append(block->immediatelyDominatedBlocksBegin(), + block->immediatelyDominatedBlocksEnd())) { + return false; + } + + // For each instruction, attempt to look up a dominating definition. + for (MDefinitionIterator iter(block); iter; ) { + MDefinition *ins = simplify(*iter, true); + + // Instruction was replaced, and all uses have already been fixed. + if (ins != *iter) { + iter = block->discardDefAt(iter); + continue; + } + + // Instruction has side-effects and cannot be folded. + if (!ins->isMovable() || ins->isEffectful()) { + iter++; + continue; + } + + MDefinition *dom = findDominatingDef(defs, ins, index); + if (!dom) + return false; // Insertion failed. + + if (dom == ins || !dom->updateForReplacement(ins)) { + 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->hasUses()); + JS_ASSERT(ins->block() == block); + JS_ASSERT(!ins->isEffectful()); + JS_ASSERT(ins->isMovable()); + + iter = ins->block()->discardDefAt(iter); + } + index++; + } + + JS_ASSERT(index == graph_.numBlocks()); + return true; +} + +// Exported method, called by the compiler. +bool +ValueNumberer::analyze() +{ + return computeValueNumbers() && eliminateRedundancies(); +} + +// Called by the compiler if we need to re-run GVN. +bool +ValueNumberer::clear() +{ + IonSpew(IonSpew_GVN, "Clearing value numbers"); + + // Clear the VN of every MDefinition + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + if (mir->shouldCancel("Value Numbering (clearing)")) + return false; + for (MDefinitionIterator iter(*block); iter; iter++) + iter->clearValueNumberData(); + block->lastIns()->clearValueNumberData(); + } + + return true; +} + +uint32_t +MDefinition::valueNumber() const +{ + JS_ASSERT(block_); + if (valueNumber_ == nullptr) + return 0; + return valueNumber_->valueNumber(); +} +void +MDefinition::setValueNumber(uint32_t 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); +} + +MDefinition * +ValueNumberer::findSplit(MDefinition *def) +{ + for (MDefinition *vncheck = def->valueNumberData()->classNext; + vncheck != nullptr; + vncheck = vncheck->valueNumberData()->classNext) { + if (!def->congruentTo(vncheck)) { + IonSpew(IonSpew_GVN, "Proceeding with split because %d is not congruent to %d", + def->id(), vncheck->id()); + return vncheck; + } + } + return nullptr; +} + +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 == nullptr); + // If the def was the only member of the class, then there is nothing to do. + if (defdata->classNext == nullptr) + return; + // If upon closer inspection, we are still equivalent to this class + // then there isn't anything for us to do. + MDefinition *newRep = findSplit(def); + if (!newRep) + return; + markConsumers(def); + ValueNumberData *newdata = newRep->valueNumberData(); + + // Right now, |defdata| is at the front of the list, and |newdata| is + // somewhere in the middle. + // + // We want to move |defdata| and everything up to but excluding + // |newdata| to a new list, with |defdata| still as the canonical + // element. + // + // We then want to take |newdata| and everything after, and + // mark them for processing (since |newdata| is now a new canonical + // element). + // + MDefinition *lastOld = newdata->classPrev; + + JS_ASSERT(lastOld); // newRep is NOT the first element of the list. + JS_ASSERT(lastOld->valueNumberData()->classNext == newRep); + + //lastOld is now the last element of the old list (congruent to + //|def|) + lastOld->valueNumberData()->classNext = nullptr; + +#ifdef DEBUG + for (MDefinition *tmp = def; tmp != nullptr; tmp = tmp->valueNumberData()->classNext) { + JS_ASSERT(tmp->valueNumber() == def->valueNumber()); + JS_ASSERT(tmp->congruentTo(def)); + JS_ASSERT(tmp != newRep); + } +#endif + //|newRep| is now the first element of a new list, therefore it is the + //new canonical element. Mark the remaining elements in the list + //(including |newRep|) + newdata->classPrev = nullptr; + 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 != nullptr; tmp = tmp->valueNumberData()->classNext) { + // if this instruction is already scheduled to be processed, don't do anything. + if (tmp->isInWorklist()) { + IonSpew(IonSpew_GVN, "Defer to a new congruence class: %d", tmp->id()); + continue; + } + IonSpew(IonSpew_GVN, "Moving to a new congruence class: %d", tmp->id()); + tmp->setValueNumber(newRep->id()); + markConsumers(tmp); + markDefinition(tmp); + } + + // Insert the new representative => number mapping into the table + // Logically, there should not be anything in the table currently, but + // old values are never removed, so there's a good chance something will + // already be there. + values.put(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 = nullptr; + defdata->classNext = nullptr; + } +}