DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Header

Mercurial (b6d82b1a6b02)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * 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/Sink.h"

#include "mozilla/Vector.h"

#include "jit/IonAnalysis.h"
#include "jit/JitSpewer.h"
#include "jit/MIR.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"

namespace js {
namespace jit {

// Given the last found common dominator and a new definition to dominate, the
// CommonDominator function returns the basic block which dominate the last
// common dominator and the definition. If no such block exists, then this
// functions return null.
static MBasicBlock* CommonDominator(MBasicBlock* commonDominator,
                                    MBasicBlock* defBlock) {
  // This is the first instruction visited, record its basic block as being
  // the only interesting one.
  if (!commonDominator) {
    return defBlock;
  }

  // Iterate on immediate dominators of the known common dominator to find a
  // block which dominates all previous uses as well as this instruction.
  while (!commonDominator->dominates(defBlock)) {
    MBasicBlock* nextBlock = commonDominator->immediateDominator();
    // All uses are dominated, so, this cannot happen unless the graph
    // coherency is not respected.
    MOZ_ASSERT(commonDominator != nextBlock);
    commonDominator = nextBlock;
  }

  return commonDominator;
}

bool Sink(MIRGenerator* mir, MIRGraph& graph) {
  TempAllocator& alloc = graph.alloc();
  bool sinkEnabled = mir->optimizationInfo().sinkEnabled();

  for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
       block++) {
    if (mir->shouldCancel("Sink")) {
      return false;
    }

    for (MInstructionReverseIterator iter = block->rbegin();
         iter != block->rend();) {
      MInstruction* ins = *iter++;

      // Only instructions which can be recovered on bailout can be moved
      // into the bailout paths.
      if (ins->isGuard() || ins->isGuardRangeBailouts() ||
          ins->isRecoveredOnBailout() || !ins->canRecoverOnBailout()) {
        continue;
      }

      // Compute a common dominator for all uses of the current
      // instruction.
      bool hasLiveUses = false;
      bool hasUses = false;
      MBasicBlock* usesDominator = nullptr;
      for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e; i++) {
        hasUses = true;
        MNode* consumerNode = (*i)->consumer();
        if (consumerNode->isResumePoint()) {
          continue;
        }

        MDefinition* consumer = consumerNode->toDefinition();
        if (consumer->isRecoveredOnBailout()) {
          continue;
        }

        hasLiveUses = true;

        // If the instruction is a Phi, then we should dominate the
        // predecessor from which the value is coming from.
        MBasicBlock* consumerBlock = consumer->block();
        if (consumer->isPhi()) {
          consumerBlock = consumerBlock->getPredecessor(consumer->indexOf(*i));
        }

        usesDominator = CommonDominator(usesDominator, consumerBlock);
        if (usesDominator == *block) {
          break;
        }
      }

      // Leave this instruction for DCE.
      if (!hasUses) {
        continue;
      }

      // We have no uses, so sink this instruction in all the bailout
      // paths.
      if (!hasLiveUses) {
        MOZ_ASSERT(!usesDominator);
        ins->setRecoveredOnBailout();
        JitSpewDef(JitSpew_Sink,
                   "  No live uses, recover the instruction on bailout\n", ins);
        continue;
      }

      // This guard is temporarly moved here as the above code deals with
      // Dead Code elimination, which got moved into this Sink phase, as
      // the Dead Code elimination used to move instructions with no-live
      // uses to the bailout path.
      if (!sinkEnabled) {
        continue;
      }

      // To move an effectful instruction, we would have to verify that the
      // side-effect is not observed. In the mean time, we just inhibit
      // this optimization on effectful instructions.
      if (ins->isEffectful()) {
        continue;
      }

      // If all the uses are under a loop, we might not want to work
      // against LICM by moving everything back into the loop, but if the
      // loop is it-self inside an if, then we still want to move the
      // computation under this if statement.
      while (block->loopDepth() < usesDominator->loopDepth()) {
        MOZ_ASSERT(usesDominator != usesDominator->immediateDominator());
        usesDominator = usesDominator->immediateDominator();
      }

      // Only move instructions if there is a branch between the dominator
      // of the uses and the original instruction. This prevent moving the
      // computation of the arguments into an inline function if there is
      // no major win.
      MBasicBlock* lastJoin = usesDominator;
      while (*block != lastJoin && lastJoin->numPredecessors() == 1) {
        MOZ_ASSERT(lastJoin != lastJoin->immediateDominator());
        MBasicBlock* next = lastJoin->immediateDominator();
        if (next->numSuccessors() > 1) {
          break;
        }
        lastJoin = next;
      }
      if (*block == lastJoin) {
        continue;
      }

      // Skip to the next instruction if we cannot find a common dominator
      // for all the uses of this instruction, or if the common dominator
      // correspond to the block of the current instruction.
      if (!usesDominator || usesDominator == *block) {
        continue;
      }

      // Only instruction which can be recovered on bailout and which are
      // sinkable can be moved into blocks which are below while filling
      // the resume points with a clone which is recovered on bailout.

      // If the instruction has live uses and if it is clonable, then we
      // can clone the instruction for all non-dominated uses and move the
      // instruction into the block which is dominating all live uses.
      if (!ins->canClone()) {
        continue;
      }

      // If the block is a split-edge block, which is created for folding
      // test conditions, then the block has no resume point and has
      // multiple predecessors.  In such case, we cannot safely move
      // bailing instruction to these blocks as we have no way to bailout.
      if (!usesDominator->entryResumePoint() &&
          usesDominator->numPredecessors() != 1) {
        continue;
      }

      JitSpewDef(JitSpew_Sink, "  Can Clone & Recover, sink instruction\n",
                 ins);
      JitSpew(JitSpew_Sink, "  into Block %u", usesDominator->id());

      // Copy the arguments and clone the instruction.
      MDefinitionVector operands(alloc);
      for (size_t i = 0, end = ins->numOperands(); i < end; i++) {
        if (!operands.append(ins->getOperand(i))) {
          return false;
        }
      }

      MInstruction* clone = ins->clone(alloc, operands);
      ins->block()->insertBefore(ins, clone);
      clone->setRecoveredOnBailout();

      // We should not update the producer of the entry resume point, as
      // it cannot refer to any instruction within the basic block excepts
      // for Phi nodes.
      MResumePoint* entry = usesDominator->entryResumePoint();

      // Replace the instruction by its clone in all the resume points /
      // recovered-on-bailout instructions which are not in blocks which
      // are dominated by the usesDominator block.
      for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e;) {
        MUse* use = *i++;
        MNode* consumer = use->consumer();

        // If the consumer is a Phi, then we look for the index of the
        // use to find the corresponding predecessor block, which is
        // then used as the consumer block.
        MBasicBlock* consumerBlock = consumer->block();
        if (consumer->isDefinition() && consumer->toDefinition()->isPhi()) {
          consumerBlock = consumerBlock->getPredecessor(
              consumer->toDefinition()->toPhi()->indexOf(use));
        }

        // Keep the current instruction for all dominated uses, except
        // for the entry resume point of the block in which the
        // instruction would be moved into.
        if (usesDominator->dominates(consumerBlock) &&
            (!consumer->isResumePoint() ||
             consumer->toResumePoint() != entry)) {
          continue;
        }

        use->replaceProducer(clone);
      }

      // As we move this instruction in a different block, we should
      // verify that we do not carry over a resume point which would refer
      // to an outdated state of the control flow.
      if (ins->resumePoint()) {
        ins->clearResumePoint();
      }

      // Now, that all uses which are not dominated by usesDominator are
      // using the cloned instruction, we can safely move the instruction
      // into the usesDominator block.
      MInstruction* at =
          usesDominator->safeInsertTop(nullptr, MBasicBlock::IgnoreRecover);
      block->moveBefore(at, ins);
    }
  }

  return true;
}

}  // namespace jit
}  // namespace js