1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/LICM.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,382 @@
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/LICM.h"
1.11 +
1.12 +#include <stdio.h>
1.13 +
1.14 +#include "jit/IonSpewer.h"
1.15 +#include "jit/MIR.h"
1.16 +#include "jit/MIRGenerator.h"
1.17 +#include "jit/MIRGraph.h"
1.18 +
1.19 +using namespace js;
1.20 +using namespace js::jit;
1.21 +
1.22 +namespace {
1.23 +
1.24 +typedef Vector<MInstruction*, 1, IonAllocPolicy> InstructionQueue;
1.25 +
1.26 +class Loop
1.27 +{
1.28 + MIRGenerator *mir;
1.29 +
1.30 + public:
1.31 + // Loop code may return three values:
1.32 + enum LoopReturn {
1.33 + LoopReturn_Success,
1.34 + LoopReturn_Error, // Compilation failure.
1.35 + LoopReturn_Skip // The loop is not suitable for LICM, but there is no error.
1.36 + };
1.37 +
1.38 + public:
1.39 + // A loop is constructed on a backedge found in the control flow graph.
1.40 + Loop(MIRGenerator *mir, MBasicBlock *footer);
1.41 +
1.42 + // Initializes the loop, finds all blocks and instructions contained in the loop.
1.43 + LoopReturn init();
1.44 +
1.45 + // Identifies hoistable loop invariant instructions and moves them out of the loop.
1.46 + bool optimize();
1.47 +
1.48 + private:
1.49 + // These blocks define the loop. header_ points to the loop header
1.50 + MBasicBlock *header_;
1.51 +
1.52 + // The pre-loop block is the first predecessor of the loop header. It is where
1.53 + // the loop is first entered and where hoisted instructions will be placed.
1.54 + MBasicBlock* preLoop_;
1.55 +
1.56 + // This indicates whether the loop contains calls or other things which
1.57 + // clobber most or all floating-point registers. In such loops,
1.58 + // floating-point constants should not be hoisted unless it enables further
1.59 + // hoisting.
1.60 + bool containsPossibleCall_;
1.61 +
1.62 + TempAllocator &alloc() const {
1.63 + return mir->alloc();
1.64 + }
1.65 +
1.66 + bool hoistInstructions(InstructionQueue &toHoist);
1.67 +
1.68 + // Utility methods for invariance testing and instruction hoisting.
1.69 + bool isInLoop(MDefinition *ins);
1.70 + bool isBeforeLoop(MDefinition *ins);
1.71 + bool isLoopInvariant(MInstruction *ins);
1.72 +
1.73 + // This method determines if this block hot within a loop. That is, if it's
1.74 + // always or usually run when the loop executes
1.75 + bool checkHotness(MBasicBlock *block);
1.76 +
1.77 + // Worklist and worklist usage methods
1.78 + InstructionQueue worklist_;
1.79 + bool insertInWorklist(MInstruction *ins);
1.80 + MInstruction* popFromWorklist();
1.81 +
1.82 + inline bool isHoistable(const MDefinition *ins) const {
1.83 + return ins->isMovable() && !ins->isEffectful() && !ins->neverHoist();
1.84 + }
1.85 +
1.86 + bool requiresHoistedUse(const MDefinition *ins) const;
1.87 +};
1.88 +
1.89 +} /* namespace anonymous */
1.90 +
1.91 +LICM::LICM(MIRGenerator *mir, MIRGraph &graph)
1.92 + : mir(mir), graph(graph)
1.93 +{
1.94 +}
1.95 +
1.96 +bool
1.97 +LICM::analyze()
1.98 +{
1.99 + IonSpew(IonSpew_LICM, "Beginning LICM pass.");
1.100 +
1.101 + // Iterate in RPO to visit outer loops before inner loops.
1.102 + for (ReversePostorderIterator i(graph.rpoBegin()); i != graph.rpoEnd(); i++) {
1.103 + MBasicBlock *header = *i;
1.104 +
1.105 + // Skip non-headers and self-loops.
1.106 + if (!header->isLoopHeader() || header->numPredecessors() < 2)
1.107 + continue;
1.108 +
1.109 + // Attempt to optimize loop.
1.110 + Loop loop(mir, header);
1.111 +
1.112 + Loop::LoopReturn lr = loop.init();
1.113 + if (lr == Loop::LoopReturn_Error)
1.114 + return false;
1.115 + if (lr == Loop::LoopReturn_Skip) {
1.116 + graph.unmarkBlocks();
1.117 + continue;
1.118 + }
1.119 +
1.120 + if (!loop.optimize())
1.121 + return false;
1.122 +
1.123 + graph.unmarkBlocks();
1.124 + }
1.125 +
1.126 + return true;
1.127 +}
1.128 +
1.129 +Loop::Loop(MIRGenerator *mir, MBasicBlock *header)
1.130 + : mir(mir),
1.131 + header_(header),
1.132 + containsPossibleCall_(false),
1.133 + worklist_(mir->alloc())
1.134 +{
1.135 + preLoop_ = header_->getPredecessor(0);
1.136 +}
1.137 +
1.138 +Loop::LoopReturn
1.139 +Loop::init()
1.140 +{
1.141 + IonSpew(IonSpew_LICM, "Loop identified, headed by block %d", header_->id());
1.142 + IonSpew(IonSpew_LICM, "footer is block %d", header_->backedge()->id());
1.143 +
1.144 + // The first predecessor of the loop header must dominate the header.
1.145 + JS_ASSERT(header_->id() > header_->getPredecessor(0)->id());
1.146 +
1.147 + // Loops from backedge to header and marks all visited blocks
1.148 + // as part of the loop. At the same time add all hoistable instructions
1.149 + // (in RPO order) to the instruction worklist.
1.150 + Vector<MBasicBlock *, 1, IonAllocPolicy> inlooplist(alloc());
1.151 + if (!inlooplist.append(header_->backedge()))
1.152 + return LoopReturn_Error;
1.153 + header_->backedge()->mark();
1.154 +
1.155 + while (!inlooplist.empty()) {
1.156 + MBasicBlock *block = inlooplist.back();
1.157 +
1.158 + // Hoisting requires more finesse if the loop contains a block that
1.159 + // self-dominates: there exists control flow that may enter the loop
1.160 + // without passing through the loop preheader.
1.161 + //
1.162 + // Rather than perform a complicated analysis of the dominance graph,
1.163 + // just return a soft error to ignore this loop.
1.164 + if (block->immediateDominator() == block) {
1.165 + while (!worklist_.empty())
1.166 + popFromWorklist();
1.167 + return LoopReturn_Skip;
1.168 + }
1.169 +
1.170 + // Add not yet visited predecessors to the inlooplist.
1.171 + if (block != header_) {
1.172 + for (size_t i = 0; i < block->numPredecessors(); i++) {
1.173 + MBasicBlock *pred = block->getPredecessor(i);
1.174 + if (pred->isMarked())
1.175 + continue;
1.176 +
1.177 + if (!inlooplist.append(pred))
1.178 + return LoopReturn_Error;
1.179 + pred->mark();
1.180 + }
1.181 + }
1.182 +
1.183 + // If any block was added, process them first.
1.184 + if (block != inlooplist.back())
1.185 + continue;
1.186 +
1.187 + // Add all instructions in this block (but the control instruction) to the worklist
1.188 + for (MInstructionIterator i = block->begin(); i != block->end(); i++) {
1.189 + MInstruction *ins = *i;
1.190 +
1.191 + // Remember whether this loop contains anything which clobbers most
1.192 + // or all floating-point registers. This is just a rough heuristic.
1.193 + if (ins->possiblyCalls())
1.194 + containsPossibleCall_ = true;
1.195 +
1.196 + if (isHoistable(ins)) {
1.197 + if (!insertInWorklist(ins))
1.198 + return LoopReturn_Error;
1.199 + }
1.200 + }
1.201 +
1.202 + // All successors of this block are visited.
1.203 + inlooplist.popBack();
1.204 + }
1.205 +
1.206 + return LoopReturn_Success;
1.207 +}
1.208 +
1.209 +bool
1.210 +Loop::optimize()
1.211 +{
1.212 + InstructionQueue invariantInstructions(alloc());
1.213 +
1.214 + IonSpew(IonSpew_LICM, "These instructions are in the loop: ");
1.215 +
1.216 + while (!worklist_.empty()) {
1.217 + if (mir->shouldCancel("LICM (worklist)"))
1.218 + return false;
1.219 +
1.220 + MInstruction *ins = popFromWorklist();
1.221 +
1.222 + IonSpewHeader(IonSpew_LICM);
1.223 +
1.224 + if (IonSpewEnabled(IonSpew_LICM)) {
1.225 + ins->printName(IonSpewFile);
1.226 + fprintf(IonSpewFile, " <- ");
1.227 + ins->printOpcode(IonSpewFile);
1.228 + fprintf(IonSpewFile, ": ");
1.229 + }
1.230 +
1.231 + if (isLoopInvariant(ins)) {
1.232 + // Flag this instruction as loop invariant.
1.233 + ins->setLoopInvariant();
1.234 + if (!invariantInstructions.append(ins))
1.235 + return false;
1.236 +
1.237 + if (IonSpewEnabled(IonSpew_LICM))
1.238 + fprintf(IonSpewFile, " Loop Invariant!\n");
1.239 + }
1.240 + }
1.241 +
1.242 + if (!hoistInstructions(invariantInstructions))
1.243 + return false;
1.244 + return true;
1.245 +}
1.246 +
1.247 +bool
1.248 +Loop::requiresHoistedUse(const MDefinition *ins) const
1.249 +{
1.250 + if (ins->isConstantElements() || ins->isBox())
1.251 + return true;
1.252 +
1.253 + // Integer constants can often be folded as immediates and aren't worth
1.254 + // hoisting on their own, in general. Floating-point constants typically
1.255 + // are worth hoisting, unless they'll end up being spilled (eg. due to a
1.256 + // call).
1.257 + if (ins->isConstant() && (IsFloatingPointType(ins->type()) || containsPossibleCall_))
1.258 + return true;
1.259 +
1.260 + return false;
1.261 +}
1.262 +
1.263 +bool
1.264 +Loop::hoistInstructions(InstructionQueue &toHoist)
1.265 +{
1.266 + // Iterate in post-order (uses before definitions)
1.267 + for (int32_t i = toHoist.length() - 1; i >= 0; i--) {
1.268 + MInstruction *ins = toHoist[i];
1.269 +
1.270 + // Don't hoist a cheap constant if it doesn't enable us to hoist one of
1.271 + // its uses. We want those instructions as close as possible to their
1.272 + // use, to facilitate folding and minimize register pressure.
1.273 + if (requiresHoistedUse(ins)) {
1.274 + bool loopInvariantUse = false;
1.275 + for (MUseDefIterator use(ins); use; use++) {
1.276 + if (use.def()->isLoopInvariant()) {
1.277 + loopInvariantUse = true;
1.278 + break;
1.279 + }
1.280 + }
1.281 +
1.282 + if (!loopInvariantUse)
1.283 + ins->setNotLoopInvariant();
1.284 + }
1.285 + }
1.286 +
1.287 + // Move all instructions to the preLoop_ block just before the control instruction.
1.288 + for (size_t i = 0; i < toHoist.length(); i++) {
1.289 + MInstruction *ins = toHoist[i];
1.290 +
1.291 + // Loads may have an implicit dependency on either stores (effectful instructions) or
1.292 + // control instructions so we should never move these.
1.293 + JS_ASSERT(!ins->isControlInstruction());
1.294 + JS_ASSERT(!ins->isEffectful());
1.295 + JS_ASSERT(ins->isMovable());
1.296 +
1.297 + if (!ins->isLoopInvariant())
1.298 + continue;
1.299 +
1.300 + if (checkHotness(ins->block())) {
1.301 + ins->block()->moveBefore(preLoop_->lastIns(), ins);
1.302 + ins->setNotLoopInvariant();
1.303 + }
1.304 + }
1.305 +
1.306 + return true;
1.307 +}
1.308 +
1.309 +bool
1.310 +Loop::isInLoop(MDefinition *ins)
1.311 +{
1.312 + return ins->block()->isMarked();
1.313 +}
1.314 +
1.315 +bool
1.316 +Loop::isBeforeLoop(MDefinition *ins)
1.317 +{
1.318 + return ins->block()->id() < header_->id();
1.319 +}
1.320 +
1.321 +bool
1.322 +Loop::isLoopInvariant(MInstruction *ins)
1.323 +{
1.324 + if (!isHoistable(ins)) {
1.325 + if (IonSpewEnabled(IonSpew_LICM))
1.326 + fprintf(IonSpewFile, "not hoistable\n");
1.327 + return false;
1.328 + }
1.329 +
1.330 + // Don't hoist if this instruction depends on a store inside or after the loop.
1.331 + // Note: "after the loop" can sound strange, but Alias Analysis doesn't look
1.332 + // at the control flow. Therefore it doesn't match the definition here, that a block
1.333 + // is in the loop when there is a (directed) path from the block to the loop header.
1.334 + if (ins->dependency() && !isBeforeLoop(ins->dependency())) {
1.335 + if (IonSpewEnabled(IonSpew_LICM)) {
1.336 + fprintf(IonSpewFile, "depends on store inside or after loop: ");
1.337 + ins->dependency()->printName(IonSpewFile);
1.338 + fprintf(IonSpewFile, "\n");
1.339 + }
1.340 + return false;
1.341 + }
1.342 +
1.343 + // An instruction is only loop invariant if it and all of its operands can
1.344 + // be safely hoisted into the loop preheader.
1.345 + for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
1.346 + if (isInLoop(ins->getOperand(i)) &&
1.347 + !ins->getOperand(i)->isLoopInvariant()) {
1.348 +
1.349 + if (IonSpewEnabled(IonSpew_LICM)) {
1.350 + ins->getOperand(i)->printName(IonSpewFile);
1.351 + fprintf(IonSpewFile, " is in the loop.\n");
1.352 + }
1.353 +
1.354 + return false;
1.355 + }
1.356 + }
1.357 +
1.358 + return true;
1.359 +}
1.360 +
1.361 +bool
1.362 +Loop::checkHotness(MBasicBlock *block)
1.363 +{
1.364 + // TODO: determine if instructions within this block are worth hoisting.
1.365 + // They might not be if the block is cold enough within the loop.
1.366 + // BUG 669517
1.367 + return true;
1.368 +}
1.369 +
1.370 +bool
1.371 +Loop::insertInWorklist(MInstruction *ins)
1.372 +{
1.373 + if (!worklist_.insert(worklist_.begin(), ins))
1.374 + return false;
1.375 + ins->setInWorklist();
1.376 + return true;
1.377 +}
1.378 +
1.379 +MInstruction*
1.380 +Loop::popFromWorklist()
1.381 +{
1.382 + MInstruction* toReturn = worklist_.popCopy();
1.383 + toReturn->setNotInWorklist();
1.384 + return toReturn;
1.385 +}
