tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Sink.cpp (9489B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      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/. */
      6 
      7 #include "jit/Sink.h"
      8 
      9 #include "jit/IonOptimizationLevels.h"
     10 #include "jit/JitSpewer.h"
     11 #include "jit/MIR-wasm.h"
     12 #include "jit/MIR.h"
     13 #include "jit/MIRGenerator.h"
     14 #include "jit/MIRGraph.h"
     15 
     16 namespace js {
     17 namespace jit {
     18 
     19 // Given the last found common dominator and a new definition to dominate, the
     20 // CommonDominator function returns the basic block which dominate the last
     21 // common dominator and the definition. If no such block exists, then this
     22 // functions return null.
     23 static MBasicBlock* CommonDominator(MBasicBlock* commonDominator,
     24                                    MBasicBlock* defBlock) {
     25  // This is the first instruction visited, record its basic block as being
     26  // the only interesting one.
     27  if (!commonDominator) {
     28    return defBlock;
     29  }
     30 
     31  // Iterate on immediate dominators of the known common dominator to find a
     32  // block which dominates all previous uses as well as this instruction.
     33  while (!commonDominator->dominates(defBlock)) {
     34    MBasicBlock* nextBlock = commonDominator->immediateDominator();
     35    // All uses are dominated, so, this cannot happen unless the graph
     36    // coherency is not respected.
     37    MOZ_ASSERT(commonDominator != nextBlock);
     38    commonDominator = nextBlock;
     39  }
     40 
     41  return commonDominator;
     42 }
     43 
     44 bool Sink(const MIRGenerator* mir, MIRGraph& graph) {
     45  JitSpew(JitSpew_Sink, "Begin");
     46  TempAllocator& alloc = graph.alloc();
     47  bool sinkEnabled = mir->optimizationInfo().sinkEnabled();
     48 
     49  for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
     50       block++) {
     51    if (mir->shouldCancel("Sink")) {
     52      return false;
     53    }
     54 
     55    for (MInstructionReverseIterator iter = block->rbegin();
     56         iter != block->rend();) {
     57      MInstruction* ins = *iter++;
     58 
     59      // Only instructions which can be recovered on bailout can be moved
     60      // into the bailout paths.
     61      if (ins->isGuard() || ins->isGuardRangeBailouts() ||
     62          ins->isRecoveredOnBailout() || !ins->canRecoverOnBailout()) {
     63        continue;
     64      }
     65 
     66      // Compute a common dominator for all uses of the current
     67      // instruction.
     68      bool hasLiveUses = false;
     69      bool hasUses = false;
     70      MBasicBlock* usesDominator = nullptr;
     71      for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e; i++) {
     72        hasUses = true;
     73        MNode* consumerNode = (*i)->consumer();
     74        if (consumerNode->isResumePoint()) {
     75          if (!consumerNode->toResumePoint()->isRecoverableOperand(*i)) {
     76            hasLiveUses = true;
     77          }
     78          continue;
     79        }
     80 
     81        MDefinition* consumer = consumerNode->toDefinition();
     82        if (consumer->isRecoveredOnBailout()) {
     83          continue;
     84        }
     85 
     86        hasLiveUses = true;
     87 
     88        // If the instruction is a Phi, then we should dominate the
     89        // predecessor from which the value is coming from.
     90        MBasicBlock* consumerBlock = consumer->block();
     91        if (consumer->isPhi()) {
     92          consumerBlock = consumerBlock->getPredecessor(consumer->indexOf(*i));
     93        }
     94 
     95        usesDominator = CommonDominator(usesDominator, consumerBlock);
     96        if (usesDominator == *block) {
     97          break;
     98        }
     99      }
    100 
    101      // Leave this instruction for DCE.
    102      if (!hasUses) {
    103        continue;
    104      }
    105 
    106      // We have no uses, so sink this instruction in all the bailout
    107      // paths.
    108      if (!hasLiveUses) {
    109        MOZ_ASSERT(!usesDominator);
    110        ins->setRecoveredOnBailout();
    111        JitSpewDef(JitSpew_Sink,
    112                   "  No live uses, recover the instruction on bailout\n", ins);
    113        continue;
    114      }
    115 
    116      // This guard is temporarly moved here as the above code deals with
    117      // Dead Code elimination, which got moved into this Sink phase, as
    118      // the Dead Code elimination used to move instructions with no-live
    119      // uses to the bailout path.
    120      if (!sinkEnabled) {
    121        continue;
    122      }
    123 
    124      // To move an effectful instruction, we would have to verify that the
    125      // side-effect is not observed. In the mean time, we just inhibit
    126      // this optimization on effectful instructions.
    127      if (ins->isEffectful()) {
    128        continue;
    129      }
    130 
    131      // If all the uses are under a loop, we might not want to work
    132      // against LICM by moving everything back into the loop, but if the
    133      // loop is it-self inside an if, then we still want to move the
    134      // computation under this if statement.
    135      while (block->loopDepth() < usesDominator->loopDepth()) {
    136        MOZ_ASSERT(usesDominator != usesDominator->immediateDominator());
    137        usesDominator = usesDominator->immediateDominator();
    138      }
    139 
    140      // Only move instructions if there is a branch between the dominator
    141      // of the uses and the original instruction. This prevent moving the
    142      // computation of the arguments into an inline function if there is
    143      // no major win.
    144      MBasicBlock* lastJoin = usesDominator;
    145      while (*block != lastJoin && lastJoin->numPredecessors() == 1) {
    146        MOZ_ASSERT(lastJoin != lastJoin->immediateDominator());
    147        MBasicBlock* next = lastJoin->immediateDominator();
    148        if (next->numSuccessors() > 1) {
    149          break;
    150        }
    151        lastJoin = next;
    152      }
    153      if (*block == lastJoin) {
    154        continue;
    155      }
    156 
    157      // Skip to the next instruction if we cannot find a common dominator
    158      // for all the uses of this instruction, or if the common dominator
    159      // correspond to the block of the current instruction.
    160      if (!usesDominator || usesDominator == *block) {
    161        continue;
    162      }
    163 
    164      // Only instruction which can be recovered on bailout and which are
    165      // sinkable can be moved into blocks which are below while filling
    166      // the resume points with a clone which is recovered on bailout.
    167 
    168      // If the instruction has live uses and if it is clonable, then we
    169      // can clone the instruction for all non-dominated uses and move the
    170      // instruction into the block which is dominating all live uses.
    171      if (!ins->canClone()) {
    172        continue;
    173      }
    174 
    175      // If the block is a split-edge block, which is created for folding
    176      // test conditions, then the block has no resume point and has
    177      // multiple predecessors.  In such case, we cannot safely move
    178      // bailing instruction to these blocks as we have no way to bailout.
    179      if (!usesDominator->entryResumePoint() &&
    180          usesDominator->numPredecessors() != 1) {
    181        continue;
    182      }
    183 
    184      JitSpewDef(JitSpew_Sink, "  Can Clone & Recover, sink instruction\n",
    185                 ins);
    186      JitSpew(JitSpew_Sink, "  into Block %u", usesDominator->id());
    187 
    188      // Copy the arguments and clone the instruction.
    189      MDefinitionVector operands(alloc);
    190      for (size_t i = 0, end = ins->numOperands(); i < end; i++) {
    191        if (!operands.append(ins->getOperand(i))) {
    192          return false;
    193        }
    194      }
    195 
    196      MInstruction* clone = ins->clone(alloc, operands);
    197      if (!clone) {
    198        return false;
    199      }
    200      ins->block()->insertBefore(ins, clone);
    201      clone->setRecoveredOnBailout();
    202 
    203      // We should not update the producer of the entry resume point, as
    204      // it cannot refer to any instruction within the basic block excepts
    205      // for Phi nodes.
    206      MResumePoint* entry = usesDominator->entryResumePoint();
    207 
    208      // Replace the instruction by its clone in all the resume points /
    209      // recovered-on-bailout instructions which are not in blocks which
    210      // are dominated by the usesDominator block.
    211      for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e;) {
    212        MUse* use = *i++;
    213        MNode* consumer = use->consumer();
    214 
    215        // If the consumer is a Phi, then we look for the index of the
    216        // use to find the corresponding predecessor block, which is
    217        // then used as the consumer block.
    218        MBasicBlock* consumerBlock = consumer->block();
    219        if (consumer->isDefinition() && consumer->toDefinition()->isPhi()) {
    220          consumerBlock = consumerBlock->getPredecessor(
    221              consumer->toDefinition()->toPhi()->indexOf(use));
    222        }
    223 
    224        // Keep the current instruction for all dominated uses, except
    225        // for the entry resume point of the block in which the
    226        // instruction would be moved into.
    227        if (usesDominator->dominates(consumerBlock) &&
    228            (!consumer->isResumePoint() ||
    229             consumer->toResumePoint() != entry)) {
    230          continue;
    231        }
    232 
    233        use->replaceProducer(clone);
    234      }
    235 
    236      // As we move this instruction in a different block, we should
    237      // verify that we do not carry over a resume point which would refer
    238      // to an outdated state of the control flow.
    239      if (ins->resumePoint()) {
    240        ins->clearResumePoint();
    241      }
    242 
    243      // Now, that all uses which are not dominated by usesDominator are
    244      // using the cloned instruction, we can safely move the instruction
    245      // into the usesDominator block.
    246      MInstruction* at =
    247          usesDominator->safeInsertTop(nullptr, MBasicBlock::IgnoreRecover);
    248      block->moveBefore(at, ins);
    249    }
    250  }
    251 
    252  return true;
    253 }
    254 
    255 }  // namespace jit
    256 }  // namespace js