1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/ValueNumbering.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,576 @@
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 +#include "jit/ValueNumbering.h"
1.11 +
1.12 +#include "jit/IonSpewer.h"
1.13 +#include "jit/MIRGenerator.h"
1.14 +#include "jit/MIRGraph.h"
1.15 +
1.16 +using namespace js;
1.17 +using namespace js::jit;
1.18 +
1.19 +ValueNumberer::ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic)
1.20 + : mir(mir),
1.21 + graph_(graph),
1.22 + values(graph.alloc()),
1.23 + pessimisticPass_(!optimistic),
1.24 + count_(0)
1.25 +{ }
1.26 +
1.27 +TempAllocator &
1.28 +ValueNumberer::alloc() const
1.29 +{
1.30 + return graph_.alloc();
1.31 +}
1.32 +
1.33 +uint32_t
1.34 +ValueNumberer::lookupValue(MDefinition *ins)
1.35 +{
1.36 + ValueMap::AddPtr p = values.lookupForAdd(ins);
1.37 + if (p) {
1.38 + // make sure this is in the correct group
1.39 + setClass(ins, p->key());
1.40 + return p->value();
1.41 + }
1.42 +
1.43 + if (!values.add(p, ins, ins->id()))
1.44 + return 0;
1.45 + breakClass(ins);
1.46 +
1.47 + return ins->id();
1.48 +}
1.49 +
1.50 +MDefinition *
1.51 +ValueNumberer::simplify(MDefinition *def, bool useValueNumbers)
1.52 +{
1.53 + if (def->isEffectful())
1.54 + return def;
1.55 +
1.56 + MDefinition *ins = def->foldsTo(alloc(), useValueNumbers);
1.57 + if (ins == def)
1.58 + return def;
1.59 +
1.60 + // Ensure this instruction has a value number.
1.61 + if (!ins->valueNumberData())
1.62 + ins->setValueNumberData(new(alloc()) ValueNumberData);
1.63 +
1.64 + if (!ins->block()) {
1.65 + // In this case, we made a new def by constant folding, for
1.66 + // example, we replaced add(#3,#4) with a new const(#7) node.
1.67 +
1.68 + // We will only fold a phi into one of its operands.
1.69 + JS_ASSERT(!def->isPhi());
1.70 +
1.71 + def->block()->insertAfter(def->toInstruction(), ins->toInstruction());
1.72 + ins->setValueNumber(lookupValue(ins));
1.73 + }
1.74 +
1.75 + JS_ASSERT(ins->id() != 0);
1.76 +
1.77 + def->replaceAllUsesWith(ins);
1.78 +
1.79 + IonSpew(IonSpew_GVN, "Folding %d to be %d", def->id(), ins->id());
1.80 + return ins;
1.81 +}
1.82 +
1.83 +MControlInstruction *
1.84 +ValueNumberer::simplifyControlInstruction(MControlInstruction *def)
1.85 +{
1.86 + if (def->isEffectful())
1.87 + return def;
1.88 +
1.89 + MDefinition *repl = def->foldsTo(alloc(), false);
1.90 + if (repl == def)
1.91 + return def;
1.92 +
1.93 + // Ensure this instruction has a value number.
1.94 + if (!repl->valueNumberData())
1.95 + repl->setValueNumberData(new(alloc()) ValueNumberData);
1.96 +
1.97 + MBasicBlock *block = def->block();
1.98 +
1.99 + // MControlInstructions should not have consumers.
1.100 + JS_ASSERT(repl->isControlInstruction());
1.101 + JS_ASSERT(!def->hasUses());
1.102 +
1.103 + if (def->isInWorklist())
1.104 + repl->setInWorklist();
1.105 +
1.106 + block->discardLastIns();
1.107 + block->end((MControlInstruction *)repl);
1.108 + return (MControlInstruction *)repl;
1.109 +}
1.110 +
1.111 +void
1.112 +ValueNumberer::markDefinition(MDefinition *def)
1.113 +{
1.114 + if (isMarked(def))
1.115 + return;
1.116 +
1.117 + IonSpew(IonSpew_GVN, "marked %d", def->id());
1.118 + def->setInWorklist();
1.119 + count_++;
1.120 +}
1.121 +
1.122 +void
1.123 +ValueNumberer::unmarkDefinition(MDefinition *def)
1.124 +{
1.125 + if (pessimisticPass_)
1.126 + return;
1.127 +
1.128 + JS_ASSERT(count_ > 0);
1.129 + IonSpew(IonSpew_GVN, "unmarked %d", def->id());
1.130 + def->setNotInWorklist();
1.131 + count_--;
1.132 +}
1.133 +
1.134 +void
1.135 +ValueNumberer::markBlock(MBasicBlock *block)
1.136 +{
1.137 + for (MDefinitionIterator iter(block); iter; iter++)
1.138 + markDefinition(*iter);
1.139 + markDefinition(block->lastIns());
1.140 +}
1.141 +
1.142 +void
1.143 +ValueNumberer::markConsumers(MDefinition *def)
1.144 +{
1.145 + if (pessimisticPass_)
1.146 + return;
1.147 +
1.148 + JS_ASSERT(!def->isInWorklist());
1.149 + JS_ASSERT(!def->isControlInstruction());
1.150 + for (MUseDefIterator use(def); use; use++)
1.151 + markDefinition(use.def());
1.152 +}
1.153 +
1.154 +bool
1.155 +ValueNumberer::computeValueNumbers()
1.156 +{
1.157 + // At the end of this function, we will have the value numbering stored in
1.158 + // each instruction.
1.159 + //
1.160 + // We also need an "optimistic" value number, for temporary use, which is
1.161 + // stored in a hashtable.
1.162 + //
1.163 + // For the instruction x := y op z, we map (op, VN[y], VN[z]) to a value
1.164 + // number, say v. If it is not in the map, we use the instruction id.
1.165 + //
1.166 + // If the instruction in question's value number is not already
1.167 + // v, we break the congruence and set it to v. We repeat until saturation.
1.168 + // This will take at worst O(d) time, where d is the loop connectedness
1.169 + // of the SSA def/use graph.
1.170 + //
1.171 + // The algorithm is the simple RPO-based algorithm from
1.172 + // "SCC-Based Value Numbering" by Cooper and Simpson.
1.173 + //
1.174 + // If we are performing a pessimistic pass, then we assume that every
1.175 + // definition is in its own congruence class, since we know nothing about
1.176 + // values that enter Phi nodes through back edges. We then make one pass
1.177 + // through the graph, ignoring back edges. This yields less congruences on
1.178 + // any graph with back-edges, but is much faster to perform.
1.179 +
1.180 + IonSpew(IonSpew_GVN, "Numbering instructions");
1.181 +
1.182 + if (!values.init())
1.183 + return false;
1.184 + // Stick a VN object onto every mdefinition
1.185 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.186 + if (mir->shouldCancel("Value Numbering (preparation loop"))
1.187 + return false;
1.188 + for (MDefinitionIterator iter(*block); iter; iter++)
1.189 + iter->setValueNumberData(new(alloc()) ValueNumberData);
1.190 + MControlInstruction *jump = block->lastIns();
1.191 + jump->setValueNumberData(new(alloc()) ValueNumberData);
1.192 + }
1.193 +
1.194 + // Assign unique value numbers if pessimistic.
1.195 + // It might be productive to do this in the MDefinition constructor or
1.196 + // possibly in a previous pass, if it seems reasonable.
1.197 + if (pessimisticPass_) {
1.198 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.199 + for (MDefinitionIterator iter(*block); iter; iter++)
1.200 + iter->setValueNumber(iter->id());
1.201 + }
1.202 + } else {
1.203 + // For each root block, add all of its instructions to the worklist.
1.204 + markBlock(*(graph_.begin()));
1.205 + if (graph_.osrBlock())
1.206 + markBlock(graph_.osrBlock());
1.207 + }
1.208 +
1.209 + while (count_ > 0) {
1.210 +#ifdef DEBUG
1.211 + if (!pessimisticPass_) {
1.212 + size_t debugCount = 0;
1.213 + IonSpew(IonSpew_GVN, "The following instructions require processing:");
1.214 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.215 + for (MDefinitionIterator iter(*block); iter; iter++) {
1.216 + if (iter->isInWorklist()) {
1.217 + IonSpew(IonSpew_GVN, "\t%d", iter->id());
1.218 + debugCount++;
1.219 + }
1.220 + }
1.221 + if (block->lastIns()->isInWorklist()) {
1.222 + IonSpew(IonSpew_GVN, "\t%d", block->lastIns()->id());
1.223 + debugCount++;
1.224 + }
1.225 + }
1.226 + if (!debugCount)
1.227 + IonSpew(IonSpew_GVN, "\tNone");
1.228 + JS_ASSERT(debugCount == count_);
1.229 + }
1.230 +#endif
1.231 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.232 + if (mir->shouldCancel("Value Numbering (main loop)"))
1.233 + return false;
1.234 + for (MDefinitionIterator iter(*block); iter; ) {
1.235 +
1.236 + if (!isMarked(*iter)) {
1.237 + iter++;
1.238 + continue;
1.239 + }
1.240 +
1.241 + JS_ASSERT_IF(!pessimisticPass_, count_ > 0);
1.242 + unmarkDefinition(*iter);
1.243 +
1.244 + MDefinition *ins = simplify(*iter, false);
1.245 +
1.246 + if (ins != *iter) {
1.247 + iter = block->discardDefAt(iter);
1.248 + continue;
1.249 + }
1.250 +
1.251 + // Don't bother storing this instruction in the HashMap if
1.252 + // (a) eliminateRedundancies will never eliminate it (because
1.253 + // it's non-movable or effectful) and (b) no other instruction's
1.254 + // value number depends on it.
1.255 + if (!ins->hasDefUses() && (!ins->isMovable() || ins->isEffectful())) {
1.256 + iter++;
1.257 + continue;
1.258 + }
1.259 +
1.260 + uint32_t value = lookupValue(ins);
1.261 +
1.262 + if (!value)
1.263 + return false; // Hashtable insertion failed
1.264 +
1.265 + if (ins->valueNumber() != value) {
1.266 + IonSpew(IonSpew_GVN,
1.267 + "Broke congruence for instruction %d (%p) with VN %d (now using %d)",
1.268 + ins->id(), (void *) ins, ins->valueNumber(), value);
1.269 + ins->setValueNumber(value);
1.270 + markConsumers(ins);
1.271 + }
1.272 +
1.273 + iter++;
1.274 + }
1.275 + // Process control flow instruction:
1.276 + MControlInstruction *jump = block->lastIns();
1.277 + jump = simplifyControlInstruction(jump);
1.278 +
1.279 + // If we are pessimistic, then this will never get set.
1.280 + if (!jump->isInWorklist())
1.281 + continue;
1.282 + unmarkDefinition(jump);
1.283 + if (jump->valueNumber() == 0) {
1.284 + jump->setValueNumber(jump->id());
1.285 + for (size_t i = 0; i < jump->numSuccessors(); i++)
1.286 + markBlock(jump->getSuccessor(i));
1.287 + }
1.288 +
1.289 + }
1.290 +
1.291 + // If we are doing a pessimistic pass, we only go once through the
1.292 + // instruction list.
1.293 + if (pessimisticPass_)
1.294 + break;
1.295 + }
1.296 +#ifdef DEBUG
1.297 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.298 + for (MDefinitionIterator iter(*block); iter; iter++) {
1.299 + JS_ASSERT(!iter->isInWorklist());
1.300 + JS_ASSERT_IF(iter->valueNumber() == 0,
1.301 + !iter->hasDefUses() && (!iter->isMovable() || iter->isEffectful()));
1.302 + }
1.303 + }
1.304 +#endif
1.305 + return true;
1.306 +}
1.307 +
1.308 +MDefinition *
1.309 +ValueNumberer::findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index)
1.310 +{
1.311 + JS_ASSERT(ins->valueNumber() != 0);
1.312 + InstructionMap::Ptr p = defs.lookup(ins->valueNumber());
1.313 + MDefinition *dom;
1.314 + if (!p || index > p->value().validUntil) {
1.315 + DominatingValue value;
1.316 + value.def = ins;
1.317 + // Since we are traversing the dominator tree in pre-order, when we
1.318 + // are looking at the |index|-th block, the next numDominated() blocks
1.319 + // we traverse are precisely the set of blocks that are dominated.
1.320 + //
1.321 + // So, this value is visible in all blocks if:
1.322 + // index <= index + ins->block->numDominated()
1.323 + // and becomes invalid after that.
1.324 + value.validUntil = index + ins->block()->numDominated();
1.325 +
1.326 + if(!defs.put(ins->valueNumber(), value))
1.327 + return nullptr;
1.328 +
1.329 + dom = ins;
1.330 + } else {
1.331 + dom = p->value().def;
1.332 + }
1.333 +
1.334 + return dom;
1.335 +}
1.336 +
1.337 +bool
1.338 +ValueNumberer::eliminateRedundancies()
1.339 +{
1.340 + // A definition is 'redundant' iff it is dominated by another definition
1.341 + // with the same value number.
1.342 + //
1.343 + // So, we traverse the dominator tree in pre-order, maintaining a hashmap
1.344 + // from value numbers to instructions.
1.345 + //
1.346 + // For each definition d with value number v, we look up v in the hashmap.
1.347 + //
1.348 + // If there is a definition d' in the hashmap, and the current traversal
1.349 + // index is within that instruction's dominated range, then we eliminate d,
1.350 + // replacing all uses of d with uses of d'.
1.351 + //
1.352 + // If there is no valid definition in the hashtable (the current definition
1.353 + // is not in dominated scope), then we insert the current instruction,
1.354 + // since it is the most dominant instruction with the given value number.
1.355 +
1.356 + InstructionMap defs(alloc());
1.357 +
1.358 + if (!defs.init())
1.359 + return false;
1.360 +
1.361 + IonSpew(IonSpew_GVN, "Eliminating redundant instructions");
1.362 +
1.363 + // Stack for pre-order CFG traversal.
1.364 + Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(alloc());
1.365 +
1.366 + // The index of the current block in the CFG traversal.
1.367 + size_t index = 0;
1.368 +
1.369 + // Add all self-dominating blocks to the worklist.
1.370 + // This includes all roots. Order does not matter.
1.371 + for (MBasicBlockIterator i(graph_.begin()); i != graph_.end(); i++) {
1.372 + MBasicBlock *block = *i;
1.373 + if (block->immediateDominator() == block) {
1.374 + if (!worklist.append(block))
1.375 + return false;
1.376 + }
1.377 + }
1.378 +
1.379 + // Starting from each self-dominating block, traverse the CFG in pre-order.
1.380 + while (!worklist.empty()) {
1.381 + if (mir->shouldCancel("Value Numbering (eliminate loop)"))
1.382 + return false;
1.383 + MBasicBlock *block = worklist.popCopy();
1.384 +
1.385 + IonSpew(IonSpew_GVN, "Looking at block %d", block->id());
1.386 +
1.387 + // Add all immediate dominators to the front of the worklist.
1.388 + if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
1.389 + block->immediatelyDominatedBlocksEnd())) {
1.390 + return false;
1.391 + }
1.392 +
1.393 + // For each instruction, attempt to look up a dominating definition.
1.394 + for (MDefinitionIterator iter(block); iter; ) {
1.395 + MDefinition *ins = simplify(*iter, true);
1.396 +
1.397 + // Instruction was replaced, and all uses have already been fixed.
1.398 + if (ins != *iter) {
1.399 + iter = block->discardDefAt(iter);
1.400 + continue;
1.401 + }
1.402 +
1.403 + // Instruction has side-effects and cannot be folded.
1.404 + if (!ins->isMovable() || ins->isEffectful()) {
1.405 + iter++;
1.406 + continue;
1.407 + }
1.408 +
1.409 + MDefinition *dom = findDominatingDef(defs, ins, index);
1.410 + if (!dom)
1.411 + return false; // Insertion failed.
1.412 +
1.413 + if (dom == ins || !dom->updateForReplacement(ins)) {
1.414 + iter++;
1.415 + continue;
1.416 + }
1.417 +
1.418 + IonSpew(IonSpew_GVN, "instruction %d is dominated by instruction %d (from block %d)",
1.419 + ins->id(), dom->id(), dom->block()->id());
1.420 +
1.421 + ins->replaceAllUsesWith(dom);
1.422 +
1.423 + JS_ASSERT(!ins->hasUses());
1.424 + JS_ASSERT(ins->block() == block);
1.425 + JS_ASSERT(!ins->isEffectful());
1.426 + JS_ASSERT(ins->isMovable());
1.427 +
1.428 + iter = ins->block()->discardDefAt(iter);
1.429 + }
1.430 + index++;
1.431 + }
1.432 +
1.433 + JS_ASSERT(index == graph_.numBlocks());
1.434 + return true;
1.435 +}
1.436 +
1.437 +// Exported method, called by the compiler.
1.438 +bool
1.439 +ValueNumberer::analyze()
1.440 +{
1.441 + return computeValueNumbers() && eliminateRedundancies();
1.442 +}
1.443 +
1.444 +// Called by the compiler if we need to re-run GVN.
1.445 +bool
1.446 +ValueNumberer::clear()
1.447 +{
1.448 + IonSpew(IonSpew_GVN, "Clearing value numbers");
1.449 +
1.450 + // Clear the VN of every MDefinition
1.451 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.452 + if (mir->shouldCancel("Value Numbering (clearing)"))
1.453 + return false;
1.454 + for (MDefinitionIterator iter(*block); iter; iter++)
1.455 + iter->clearValueNumberData();
1.456 + block->lastIns()->clearValueNumberData();
1.457 + }
1.458 +
1.459 + return true;
1.460 +}
1.461 +
1.462 +uint32_t
1.463 +MDefinition::valueNumber() const
1.464 +{
1.465 + JS_ASSERT(block_);
1.466 + if (valueNumber_ == nullptr)
1.467 + return 0;
1.468 + return valueNumber_->valueNumber();
1.469 +}
1.470 +void
1.471 +MDefinition::setValueNumber(uint32_t vn)
1.472 +{
1.473 + valueNumber_->setValueNumber(vn);
1.474 +}
1.475 +// Set the class of this to the given representative value.
1.476 +void
1.477 +ValueNumberer::setClass(MDefinition *def, MDefinition *rep)
1.478 +{
1.479 + def->valueNumberData()->setClass(def, rep);
1.480 +}
1.481 +
1.482 +MDefinition *
1.483 +ValueNumberer::findSplit(MDefinition *def)
1.484 +{
1.485 + for (MDefinition *vncheck = def->valueNumberData()->classNext;
1.486 + vncheck != nullptr;
1.487 + vncheck = vncheck->valueNumberData()->classNext) {
1.488 + if (!def->congruentTo(vncheck)) {
1.489 + IonSpew(IonSpew_GVN, "Proceeding with split because %d is not congruent to %d",
1.490 + def->id(), vncheck->id());
1.491 + return vncheck;
1.492 + }
1.493 + }
1.494 + return nullptr;
1.495 +}
1.496 +
1.497 +void
1.498 +ValueNumberer::breakClass(MDefinition *def)
1.499 +{
1.500 + if (def->valueNumber() == def->id()) {
1.501 + IonSpew(IonSpew_GVN, "Breaking congruence with itself: %d", def->id());
1.502 + ValueNumberData *defdata = def->valueNumberData();
1.503 + JS_ASSERT(defdata->classPrev == nullptr);
1.504 + // If the def was the only member of the class, then there is nothing to do.
1.505 + if (defdata->classNext == nullptr)
1.506 + return;
1.507 + // If upon closer inspection, we are still equivalent to this class
1.508 + // then there isn't anything for us to do.
1.509 + MDefinition *newRep = findSplit(def);
1.510 + if (!newRep)
1.511 + return;
1.512 + markConsumers(def);
1.513 + ValueNumberData *newdata = newRep->valueNumberData();
1.514 +
1.515 + // Right now, |defdata| is at the front of the list, and |newdata| is
1.516 + // somewhere in the middle.
1.517 + //
1.518 + // We want to move |defdata| and everything up to but excluding
1.519 + // |newdata| to a new list, with |defdata| still as the canonical
1.520 + // element.
1.521 + //
1.522 + // We then want to take |newdata| and everything after, and
1.523 + // mark them for processing (since |newdata| is now a new canonical
1.524 + // element).
1.525 + //
1.526 + MDefinition *lastOld = newdata->classPrev;
1.527 +
1.528 + JS_ASSERT(lastOld); // newRep is NOT the first element of the list.
1.529 + JS_ASSERT(lastOld->valueNumberData()->classNext == newRep);
1.530 +
1.531 + //lastOld is now the last element of the old list (congruent to
1.532 + //|def|)
1.533 + lastOld->valueNumberData()->classNext = nullptr;
1.534 +
1.535 +#ifdef DEBUG
1.536 + for (MDefinition *tmp = def; tmp != nullptr; tmp = tmp->valueNumberData()->classNext) {
1.537 + JS_ASSERT(tmp->valueNumber() == def->valueNumber());
1.538 + JS_ASSERT(tmp->congruentTo(def));
1.539 + JS_ASSERT(tmp != newRep);
1.540 + }
1.541 +#endif
1.542 + //|newRep| is now the first element of a new list, therefore it is the
1.543 + //new canonical element. Mark the remaining elements in the list
1.544 + //(including |newRep|)
1.545 + newdata->classPrev = nullptr;
1.546 + IonSpew(IonSpew_GVN, "Choosing a new representative: %d", newRep->id());
1.547 +
1.548 + // make the VN of every member in the class the VN of the new representative number.
1.549 + for (MDefinition *tmp = newRep; tmp != nullptr; tmp = tmp->valueNumberData()->classNext) {
1.550 + // if this instruction is already scheduled to be processed, don't do anything.
1.551 + if (tmp->isInWorklist()) {
1.552 + IonSpew(IonSpew_GVN, "Defer to a new congruence class: %d", tmp->id());
1.553 + continue;
1.554 + }
1.555 + IonSpew(IonSpew_GVN, "Moving to a new congruence class: %d", tmp->id());
1.556 + tmp->setValueNumber(newRep->id());
1.557 + markConsumers(tmp);
1.558 + markDefinition(tmp);
1.559 + }
1.560 +
1.561 + // Insert the new representative => number mapping into the table
1.562 + // Logically, there should not be anything in the table currently, but
1.563 + // old values are never removed, so there's a good chance something will
1.564 + // already be there.
1.565 + values.put(newRep, newRep->id());
1.566 + } else {
1.567 + // The element that is breaking from the list isn't the representative element
1.568 + // just strip it from the list
1.569 + ValueNumberData *defdata = def->valueNumberData();
1.570 + if (defdata->classPrev)
1.571 + defdata->classPrev->valueNumberData()->classNext = defdata->classNext;
1.572 + if (defdata->classNext)
1.573 + defdata->classNext->valueNumberData()->classPrev = defdata->classPrev;
1.574 +
1.575 + // Make sure there is no nastinees accidentally linking elements into the old list later.
1.576 + defdata->classPrev = nullptr;
1.577 + defdata->classNext = nullptr;
1.578 + }
1.579 +}
