The Tor Browser: js/src/jit/ValueNumbering.cpp@b8a032363ba2

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

     2  * vim: set ts=8 sts=4 et sw=4 tw=99:

     3  * This Source Code Form is subject to the terms of the Mozilla Public

     4  * License, v. 2.0. If a copy of the MPL was not distributed with this

     5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     7 #include "jit/ValueNumbering.h"

     9 #include "jit/IonSpewer.h"

    10 #include "jit/MIRGenerator.h"

    11 #include "jit/MIRGraph.h"

    13 using namespace js;

    14 using namespace js::jit;

    16 ValueNumberer::ValueNumberer(MIRGenerator *mir, MIRGraph &graph, bool optimistic)

    17   : mir(mir),

    18     graph_(graph),

    19     values(graph.alloc()),

    20     pessimisticPass_(!optimistic),

    21     count_(0)

    22 { }

    24 TempAllocator &

    25 ValueNumberer::alloc() const

    26 {

    27     return graph_.alloc();

    28 }

    30 uint32_t

    31 ValueNumberer::lookupValue(MDefinition *ins)

    32 {

    33     ValueMap::AddPtr p = values.lookupForAdd(ins);

    34     if (p) {

    35         // make sure this is in the correct group

    36         setClass(ins, p->key());

    37         return p->value();

    38     }

    40     if (!values.add(p, ins, ins->id()))

    41         return 0;

    42     breakClass(ins);

    44     return ins->id();

    45 }

    47 MDefinition *

    48 ValueNumberer::simplify(MDefinition *def, bool useValueNumbers)

    49 {

    50     if (def->isEffectful())

    51         return def;

    53     MDefinition *ins = def->foldsTo(alloc(), useValueNumbers);

    54     if (ins == def)

    55         return def;

    57     // Ensure this instruction has a value number.

    58     if (!ins->valueNumberData())

    59         ins->setValueNumberData(new(alloc()) ValueNumberData);

    61     if (!ins->block()) {

    62         // In this case, we made a new def by constant folding, for

    63         // example, we replaced add(#3,#4) with a new const(#7) node.

    65         // We will only fold a phi into one of its operands.

    66         JS_ASSERT(!def->isPhi());

    68         def->block()->insertAfter(def->toInstruction(), ins->toInstruction());

    69         ins->setValueNumber(lookupValue(ins));

    70     }

    72     JS_ASSERT(ins->id() != 0);

    74     def->replaceAllUsesWith(ins);

    76     IonSpew(IonSpew_GVN, "Folding %d to be %d", def->id(), ins->id());

    77     return ins;

    78 }

    80 MControlInstruction *

    81 ValueNumberer::simplifyControlInstruction(MControlInstruction *def)

    82 {

    83     if (def->isEffectful())

    84         return def;

    86     MDefinition *repl = def->foldsTo(alloc(), false);

    87     if (repl == def)

    88         return def;

    90     // Ensure this instruction has a value number.

    91     if (!repl->valueNumberData())

    92         repl->setValueNumberData(new(alloc()) ValueNumberData);

    94     MBasicBlock *block = def->block();

    96     // MControlInstructions should not have consumers.

    97     JS_ASSERT(repl->isControlInstruction());

    98     JS_ASSERT(!def->hasUses());

   100     if (def->isInWorklist())

   101         repl->setInWorklist();

   103     block->discardLastIns();

   104     block->end((MControlInstruction *)repl);

   105     return (MControlInstruction *)repl;

   106 }

   108 void

   109 ValueNumberer::markDefinition(MDefinition *def)

   110 {

   111     if (isMarked(def))

   112         return;

   114     IonSpew(IonSpew_GVN, "marked %d", def->id());

   115     def->setInWorklist();

   116     count_++;

   117 }

   119 void

   120 ValueNumberer::unmarkDefinition(MDefinition *def)

   121 {

   122     if (pessimisticPass_)

   123         return;

   125     JS_ASSERT(count_ > 0);

   126     IonSpew(IonSpew_GVN, "unmarked %d", def->id());

   127     def->setNotInWorklist();

   128     count_--;

   129 }

   131 void

   132 ValueNumberer::markBlock(MBasicBlock *block)

   133 {

   134     for (MDefinitionIterator iter(block); iter; iter++)

   135         markDefinition(*iter);

   136     markDefinition(block->lastIns());

   137 }

   139 void

   140 ValueNumberer::markConsumers(MDefinition *def)

   141 {

   142     if (pessimisticPass_)

   143         return;

   145     JS_ASSERT(!def->isInWorklist());

   146     JS_ASSERT(!def->isControlInstruction());

   147     for (MUseDefIterator use(def); use; use++)

   148         markDefinition(use.def());

   149 }

   151 bool

   152 ValueNumberer::computeValueNumbers()

   153 {

   154     // At the end of this function, we will have the value numbering stored in

   155     // each instruction.

   156     //

   157     // We also need an "optimistic" value number, for temporary use, which is

   158     // stored in a hashtable.

   159     //

   160     // For the instruction x := y op z, we map (op, VN[y], VN[z]) to a value

   161     // number, say v. If it is not in the map, we use the instruction id.

   162     //

   163     // If the instruction in question's value number is not already

   164     // v, we break the congruence and set it to v. We repeat until saturation.

   165     // This will take at worst O(d) time, where d is the loop connectedness

   166     // of the SSA def/use graph.

   167     //

   168     // The algorithm is the simple RPO-based algorithm from

   169     // "SCC-Based Value Numbering" by Cooper and Simpson.

   170     //

   171     // If we are performing a pessimistic pass, then we assume that every

   172     // definition is in its own congruence class, since we know nothing about

   173     // values that enter Phi nodes through back edges. We then make one pass

   174     // through the graph, ignoring back edges. This yields less congruences on

   175     // any graph with back-edges, but is much faster to perform.

   177     IonSpew(IonSpew_GVN, "Numbering instructions");

   179     if (!values.init())

   180         return false;

   181     // Stick a VN object onto every mdefinition

   182     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   183         if (mir->shouldCancel("Value Numbering (preparation loop"))

   184             return false;

   185         for (MDefinitionIterator iter(*block); iter; iter++)

   186             iter->setValueNumberData(new(alloc()) ValueNumberData);

   187         MControlInstruction *jump = block->lastIns();

   188         jump->setValueNumberData(new(alloc()) ValueNumberData);

   189     }

   191     // Assign unique value numbers if pessimistic.

   192     // It might be productive to do this in the MDefinition constructor or

   193     // possibly in a previous pass, if it seems reasonable.

   194     if (pessimisticPass_) {

   195         for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   196             for (MDefinitionIterator iter(*block); iter; iter++)

   197                 iter->setValueNumber(iter->id());

   198         }

   199     } else {

   200         // For each root block, add all of its instructions to the worklist.

   201         markBlock(*(graph_.begin()));

   202         if (graph_.osrBlock())

   203             markBlock(graph_.osrBlock());

   204     }

   206     while (count_ > 0) {

   207 #ifdef DEBUG

   208         if (!pessimisticPass_) {

   209             size_t debugCount = 0;

   210             IonSpew(IonSpew_GVN, "The following instructions require processing:");

   211             for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   212                 for (MDefinitionIterator iter(*block); iter; iter++) {

   213                     if (iter->isInWorklist()) {

   214                         IonSpew(IonSpew_GVN, "\t%d", iter->id());

   215                         debugCount++;

   216                     }

   217                 }

   218                 if (block->lastIns()->isInWorklist()) {

   219                     IonSpew(IonSpew_GVN, "\t%d", block->lastIns()->id());

   220                     debugCount++;

   221                 }

   222             }

   223             if (!debugCount)

   224                 IonSpew(IonSpew_GVN, "\tNone");

   225             JS_ASSERT(debugCount == count_);

   226         }

   227 #endif

   228         for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   229             if (mir->shouldCancel("Value Numbering (main loop)"))

   230                 return false;

   231             for (MDefinitionIterator iter(*block); iter; ) {

   233                 if (!isMarked(*iter)) {

   234                     iter++;

   235                     continue;

   236                 }

   238                 JS_ASSERT_IF(!pessimisticPass_, count_ > 0);

   239                 unmarkDefinition(*iter);

   241                 MDefinition *ins = simplify(*iter, false);

   243                 if (ins != *iter) {

   244                     iter = block->discardDefAt(iter);

   245                     continue;

   246                 }

   248                 // Don't bother storing this instruction in the HashMap if

   249                 // (a) eliminateRedundancies will never eliminate it (because

   250                 // it's non-movable or effectful) and (b) no other instruction's

   251                 // value number depends on it.

   252                 if (!ins->hasDefUses() && (!ins->isMovable() || ins->isEffectful())) {

   253                     iter++;

   254                     continue;

   255                 }

   257                 uint32_t value = lookupValue(ins);

   259                 if (!value)

   260                     return false; // Hashtable insertion failed

   262                 if (ins->valueNumber() != value) {

   263                     IonSpew(IonSpew_GVN,

   264                             "Broke congruence for instruction %d (%p) with VN %d (now using %d)",

   265                             ins->id(), (void *) ins, ins->valueNumber(), value);

   266                     ins->setValueNumber(value);

   267                     markConsumers(ins);

   268                 }

   270                 iter++;

   271             }

   272             // Process control flow instruction:

   273             MControlInstruction *jump = block->lastIns();

   274             jump = simplifyControlInstruction(jump);

   276             // If we are pessimistic, then this will never get set.

   277             if (!jump->isInWorklist())

   278                 continue;

   279             unmarkDefinition(jump);

   280             if (jump->valueNumber() == 0) {

   281                 jump->setValueNumber(jump->id());

   282                 for (size_t i = 0; i < jump->numSuccessors(); i++)

   283                     markBlock(jump->getSuccessor(i));

   284             }

   286         }

   288         // If we are doing a pessimistic pass, we only go once through the

   289         // instruction list.

   290         if (pessimisticPass_)

   291             break;

   292     }

   293 #ifdef DEBUG

   294     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   295         for (MDefinitionIterator iter(*block); iter; iter++) {

   296             JS_ASSERT(!iter->isInWorklist());

   297             JS_ASSERT_IF(iter->valueNumber() == 0,

   298                          !iter->hasDefUses() && (!iter->isMovable() || iter->isEffectful()));

   299         }

   300     }

   301 #endif

   302     return true;

   303 }

   305 MDefinition *

   306 ValueNumberer::findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index)

   307 {

   308     JS_ASSERT(ins->valueNumber() != 0);

   309     InstructionMap::Ptr p = defs.lookup(ins->valueNumber());

   310     MDefinition *dom;

   311     if (!p || index > p->value().validUntil) {

   312         DominatingValue value;

   313         value.def = ins;

   314         // Since we are traversing the dominator tree in pre-order, when we

   315         // are looking at the |index|-th block, the next numDominated() blocks

   316         // we traverse are precisely the set of blocks that are dominated.

   317         //

   318         // So, this value is visible in all blocks if:

   319         // index <= index + ins->block->numDominated()

   320         // and becomes invalid after that.

   321         value.validUntil = index + ins->block()->numDominated();

   323         if(!defs.put(ins->valueNumber(), value))

   324             return nullptr;

   326         dom = ins;

   327     } else {

   328         dom = p->value().def;

   329     }

   331     return dom;

   332 }

   334 bool

   335 ValueNumberer::eliminateRedundancies()

   336 {

   337     // A definition is 'redundant' iff it is dominated by another definition

   338     // with the same value number.

   339     //

   340     // So, we traverse the dominator tree in pre-order, maintaining a hashmap

   341     // from value numbers to instructions.

   342     //

   343     // For each definition d with value number v, we look up v in the hashmap.

   344     //

   345     // If there is a definition d' in the hashmap, and the current traversal

   346     // index is within that instruction's dominated range, then we eliminate d,

   347     // replacing all uses of d with uses of d'.

   348     //

   349     // If there is no valid definition in the hashtable (the current definition

   350     // is not in dominated scope), then we insert the current instruction,

   351     // since it is the most dominant instruction with the given value number.

   353     InstructionMap defs(alloc());

   355     if (!defs.init())

   356         return false;

   358     IonSpew(IonSpew_GVN, "Eliminating redundant instructions");

   360     // Stack for pre-order CFG traversal.

   361     Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(alloc());

   363     // The index of the current block in the CFG traversal.

   364     size_t index = 0;

   366     // Add all self-dominating blocks to the worklist.

   367     // This includes all roots. Order does not matter.

   368     for (MBasicBlockIterator i(graph_.begin()); i != graph_.end(); i++) {

   369         MBasicBlock *block = *i;

   370         if (block->immediateDominator() == block) {

   371             if (!worklist.append(block))

   372                 return false;

   373         }

   374     }

   376     // Starting from each self-dominating block, traverse the CFG in pre-order.

   377     while (!worklist.empty()) {

   378         if (mir->shouldCancel("Value Numbering (eliminate loop)"))

   379             return false;

   380         MBasicBlock *block = worklist.popCopy();

   382         IonSpew(IonSpew_GVN, "Looking at block %d", block->id());

   384         // Add all immediate dominators to the front of the worklist.

   385         if (!worklist.append(block->immediatelyDominatedBlocksBegin(),

   386                              block->immediatelyDominatedBlocksEnd())) {

   387             return false;

   388         }

   390         // For each instruction, attempt to look up a dominating definition.

   391         for (MDefinitionIterator iter(block); iter; ) {

   392             MDefinition *ins = simplify(*iter, true);

   394             // Instruction was replaced, and all uses have already been fixed.

   395             if (ins != *iter) {

   396                 iter = block->discardDefAt(iter);

   397                 continue;

   398             }

   400             // Instruction has side-effects and cannot be folded.

   401             if (!ins->isMovable() || ins->isEffectful()) {

   402                 iter++;

   403                 continue;

   404             }

   406             MDefinition *dom = findDominatingDef(defs, ins, index);

   407             if (!dom)

   408                 return false; // Insertion failed.

   410             if (dom == ins || !dom->updateForReplacement(ins)) {

   411                 iter++;

   412                 continue;

   413             }

   415             IonSpew(IonSpew_GVN, "instruction %d is dominated by instruction %d (from block %d)",

   416                     ins->id(), dom->id(), dom->block()->id());

   418             ins->replaceAllUsesWith(dom);

   420             JS_ASSERT(!ins->hasUses());

   421             JS_ASSERT(ins->block() == block);

   422             JS_ASSERT(!ins->isEffectful());

   423             JS_ASSERT(ins->isMovable());

   425             iter = ins->block()->discardDefAt(iter);

   426         }

   427         index++;

   428     }

   430     JS_ASSERT(index == graph_.numBlocks());

   431     return true;

   432 }

   434 // Exported method, called by the compiler.

   435 bool

   436 ValueNumberer::analyze()

   437 {

   438     return computeValueNumbers() && eliminateRedundancies();

   439 }

   441 // Called by the compiler if we need to re-run GVN.

   442 bool

   443 ValueNumberer::clear()

   444 {

   445     IonSpew(IonSpew_GVN, "Clearing value numbers");

   447     // Clear the VN of every MDefinition

   448     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {

   449         if (mir->shouldCancel("Value Numbering (clearing)"))

   450             return false;

   451         for (MDefinitionIterator iter(*block); iter; iter++)

   452             iter->clearValueNumberData();

   453         block->lastIns()->clearValueNumberData();

   454     }

   456     return true;

   457 }

   459 uint32_t

   460 MDefinition::valueNumber() const

   461 {

   462     JS_ASSERT(block_);

   463     if (valueNumber_ == nullptr)

   464         return 0;

   465     return valueNumber_->valueNumber();

   466 }

   467 void

   468 MDefinition::setValueNumber(uint32_t vn)

   469 {

   470     valueNumber_->setValueNumber(vn);

   471 }

   472 // Set the class of this to the given representative value.

   473 void

   474 ValueNumberer::setClass(MDefinition *def, MDefinition *rep)

   475 {

   476     def->valueNumberData()->setClass(def, rep);

   477 }

   479 MDefinition *

   480 ValueNumberer::findSplit(MDefinition *def)

   481 {

   482     for (MDefinition *vncheck = def->valueNumberData()->classNext;

   483          vncheck != nullptr;

   484          vncheck = vncheck->valueNumberData()->classNext) {

   485         if (!def->congruentTo(vncheck)) {

   486             IonSpew(IonSpew_GVN, "Proceeding with split because %d is not congruent to %d",

   487                     def->id(), vncheck->id());

   488             return vncheck;

   489         }

   490     }

   491     return nullptr;

   492 }

   494 void

   495 ValueNumberer::breakClass(MDefinition *def)

   496 {

   497     if (def->valueNumber() == def->id()) {

   498         IonSpew(IonSpew_GVN, "Breaking congruence with itself: %d", def->id());

   499         ValueNumberData *defdata = def->valueNumberData();

   500         JS_ASSERT(defdata->classPrev == nullptr);

   501         // If the def was the only member of the class, then there is nothing to do.

   502         if (defdata->classNext == nullptr)

   503             return;

   504         // If upon closer inspection, we are still equivalent to this class

   505         // then there isn't anything for us to do.

   506         MDefinition *newRep = findSplit(def);

   507         if (!newRep)

   508             return;

   509         markConsumers(def);

   510         ValueNumberData *newdata = newRep->valueNumberData();

   512         // Right now, |defdata| is at the front of the list, and |newdata| is

   513         // somewhere in the middle.

   514         //

   515         // We want to move |defdata| and everything up to but excluding

   516         // |newdata| to a new list, with |defdata| still as the canonical

   517         // element.

   518         //

   519         // We then want to take |newdata| and everything after, and

   520         // mark them for processing (since |newdata| is now a new canonical

   521         // element).

   522         //

   523         MDefinition *lastOld = newdata->classPrev;

   525         JS_ASSERT(lastOld); // newRep is NOT the first element of the list.

   526         JS_ASSERT(lastOld->valueNumberData()->classNext == newRep);

   528         //lastOld is now the last element of the old list (congruent to

   529         //|def|)

   530         lastOld->valueNumberData()->classNext = nullptr;

   532 #ifdef DEBUG

   533         for (MDefinition *tmp = def; tmp != nullptr; tmp = tmp->valueNumberData()->classNext) {

   534             JS_ASSERT(tmp->valueNumber() == def->valueNumber());

   535             JS_ASSERT(tmp->congruentTo(def));

   536             JS_ASSERT(tmp != newRep);

   537         }

   538 #endif

   539         //|newRep| is now the first element of a new list, therefore it is the

   540         //new canonical element. Mark the remaining elements in the list

   541         //(including |newRep|)

   542         newdata->classPrev = nullptr;

   543         IonSpew(IonSpew_GVN, "Choosing a new representative: %d", newRep->id());

   545         // make the VN of every member in the class the VN of the new representative number.

   546         for (MDefinition *tmp = newRep; tmp != nullptr; tmp = tmp->valueNumberData()->classNext) {

   547             // if this instruction is already scheduled to be processed, don't do anything.

   548             if (tmp->isInWorklist()) {

   549                 IonSpew(IonSpew_GVN, "Defer  to a new congruence class: %d", tmp->id());

   550                 continue;

   551             }

   552             IonSpew(IonSpew_GVN, "Moving to a new congruence class: %d", tmp->id());

   553             tmp->setValueNumber(newRep->id());

   554             markConsumers(tmp);

   555             markDefinition(tmp);

   556         }

   558         // Insert the new representative => number mapping into the table

   559         // Logically, there should not be anything in the table currently, but

   560         // old values are never removed, so there's a good chance something will

   561         // already be there.

   562         values.put(newRep, newRep->id());

   563     } else {

   564         // The element that is breaking from the list isn't the representative element

   565         // just strip it from the list

   566         ValueNumberData *defdata = def->valueNumberData();

   567         if (defdata->classPrev)

   568             defdata->classPrev->valueNumberData()->classNext = defdata->classNext;

   569         if (defdata->classNext)

   570             defdata->classNext->valueNumberData()->classPrev = defdata->classPrev;

   572         // Make sure there is no nastinees accidentally linking elements into the old list later.

   573         defdata->classPrev = nullptr;

   574         defdata->classNext = nullptr;

   575     }

   576 }

The Tor Browser / file revision

js/src/jit/ValueNumbering.cpp@b8a032363ba2

js/src/jit/ValueNumbering.cpp