1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/AliasAnalysis.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,296 @@
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/AliasAnalysis.h"
1.11 +
1.12 +#include <stdio.h>
1.13 +
1.14 +#include "jit/Ion.h"
1.15 +#include "jit/IonBuilder.h"
1.16 +#include "jit/IonSpewer.h"
1.17 +#include "jit/MIR.h"
1.18 +#include "jit/MIRGraph.h"
1.19 +
1.20 +using namespace js;
1.21 +using namespace js::jit;
1.22 +
1.23 +using mozilla::Array;
1.24 +
1.25 +namespace js {
1.26 +namespace jit {
1.27 +
1.28 +class LoopAliasInfo : public TempObject
1.29 +{
1.30 + private:
1.31 + LoopAliasInfo *outer_;
1.32 + MBasicBlock *loopHeader_;
1.33 + MDefinitionVector invariantLoads_;
1.34 +
1.35 + public:
1.36 + LoopAliasInfo(TempAllocator &alloc, LoopAliasInfo *outer, MBasicBlock *loopHeader)
1.37 + : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)
1.38 + { }
1.39 +
1.40 + MBasicBlock *loopHeader() const {
1.41 + return loopHeader_;
1.42 + }
1.43 + LoopAliasInfo *outer() const {
1.44 + return outer_;
1.45 + }
1.46 + bool addInvariantLoad(MDefinition *ins) {
1.47 + return invariantLoads_.append(ins);
1.48 + }
1.49 + const MDefinitionVector& invariantLoads() const {
1.50 + return invariantLoads_;
1.51 + }
1.52 + MDefinition *firstInstruction() const {
1.53 + return *loopHeader_->begin();
1.54 + }
1.55 +};
1.56 +
1.57 +} // namespace jit
1.58 +} // namespace js
1.59 +
1.60 +namespace {
1.61 +
1.62 +// Iterates over the flags in an AliasSet.
1.63 +class AliasSetIterator
1.64 +{
1.65 + private:
1.66 + uint32_t flags;
1.67 + unsigned pos;
1.68 +
1.69 + public:
1.70 + AliasSetIterator(AliasSet set)
1.71 + : flags(set.flags()), pos(0)
1.72 + {
1.73 + while (flags && (flags & 1) == 0) {
1.74 + flags >>= 1;
1.75 + pos++;
1.76 + }
1.77 + }
1.78 + AliasSetIterator& operator ++(int) {
1.79 + do {
1.80 + flags >>= 1;
1.81 + pos++;
1.82 + } while (flags && (flags & 1) == 0);
1.83 + return *this;
1.84 + }
1.85 + operator bool() const {
1.86 + return !!flags;
1.87 + }
1.88 + unsigned operator *() const {
1.89 + JS_ASSERT(pos < AliasSet::NumCategories);
1.90 + return pos;
1.91 + }
1.92 +};
1.93 +
1.94 +} /* anonymous namespace */
1.95 +
1.96 +AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)
1.97 + : mir(mir),
1.98 + graph_(graph),
1.99 + loop_(nullptr)
1.100 +{
1.101 +}
1.102 +
1.103 +// Whether there might be a path from src to dest, excluding loop backedges. This is
1.104 +// approximate and really ought to depend on precomputed reachability information.
1.105 +static inline bool
1.106 +BlockMightReach(MBasicBlock *src, MBasicBlock *dest)
1.107 +{
1.108 + while (src->id() <= dest->id()) {
1.109 + if (src == dest)
1.110 + return true;
1.111 + switch (src->numSuccessors()) {
1.112 + case 0:
1.113 + return false;
1.114 + case 1: {
1.115 + MBasicBlock *successor = src->getSuccessor(0);
1.116 + if (successor->id() <= src->id())
1.117 + return true; // Don't iloop.
1.118 + src = successor;
1.119 + break;
1.120 + }
1.121 + default:
1.122 + return true;
1.123 + }
1.124 + }
1.125 + return false;
1.126 +}
1.127 +
1.128 +static void
1.129 +IonSpewDependency(MDefinition *load, MDefinition *store, const char *verb, const char *reason)
1.130 +{
1.131 + if (!IonSpewEnabled(IonSpew_Alias))
1.132 + return;
1.133 +
1.134 + fprintf(IonSpewFile, "Load ");
1.135 + load->printName(IonSpewFile);
1.136 + fprintf(IonSpewFile, " %s on store ", verb);
1.137 + store->printName(IonSpewFile);
1.138 + fprintf(IonSpewFile, " (%s)\n", reason);
1.139 +}
1.140 +
1.141 +static void
1.142 +IonSpewAliasInfo(const char *pre, MDefinition *ins, const char *post)
1.143 +{
1.144 + if (!IonSpewEnabled(IonSpew_Alias))
1.145 + return;
1.146 +
1.147 + fprintf(IonSpewFile, "%s ", pre);
1.148 + ins->printName(IonSpewFile);
1.149 + fprintf(IonSpewFile, " %s\n", post);
1.150 +}
1.151 +
1.152 +// This pass annotates every load instruction with the last store instruction
1.153 +// on which it depends. The algorithm is optimistic in that it ignores explicit
1.154 +// dependencies and only considers loads and stores.
1.155 +//
1.156 +// Loads inside loops only have an implicit dependency on a store before the
1.157 +// loop header if no instruction inside the loop body aliases it. To calculate
1.158 +// this efficiently, we maintain a list of maybe-invariant loads and the combined
1.159 +// alias set for all stores inside the loop. When we see the loop's backedge, this
1.160 +// information is used to mark every load we wrongly assumed to be loop invaraint as
1.161 +// having an implicit dependency on the last instruction of the loop header, so that
1.162 +// it's never moved before the loop header.
1.163 +//
1.164 +// The algorithm depends on the invariant that both control instructions and effectful
1.165 +// instructions (stores) are never hoisted.
1.166 +bool
1.167 +AliasAnalysis::analyze()
1.168 +{
1.169 + Vector<MDefinitionVector, AliasSet::NumCategories, IonAllocPolicy> stores(alloc());
1.170 +
1.171 + // Initialize to the first instruction.
1.172 + MDefinition *firstIns = *graph_.begin()->begin();
1.173 + for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
1.174 + MDefinitionVector defs(alloc());
1.175 + if (!defs.append(firstIns))
1.176 + return false;
1.177 + if (!stores.append(Move(defs)))
1.178 + return false;
1.179 + }
1.180 +
1.181 + // Type analysis may have inserted new instructions. Since this pass depends
1.182 + // on the instruction number ordering, all instructions are renumbered.
1.183 + // We start with 1 because some passes use 0 to denote failure.
1.184 + uint32_t newId = 1;
1.185 +
1.186 + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
1.187 + if (mir->shouldCancel("Alias Analysis (main loop)"))
1.188 + return false;
1.189 +
1.190 + if (block->isLoopHeader()) {
1.191 + IonSpew(IonSpew_Alias, "Processing loop header %d", block->id());
1.192 + loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
1.193 + }
1.194 +
1.195 + for (MDefinitionIterator def(*block); def; def++) {
1.196 + def->setId(newId++);
1.197 +
1.198 + AliasSet set = def->getAliasSet();
1.199 + if (set.isNone())
1.200 + continue;
1.201 +
1.202 + if (set.isStore()) {
1.203 + for (AliasSetIterator iter(set); iter; iter++) {
1.204 + if (!stores[*iter].append(*def))
1.205 + return false;
1.206 + }
1.207 +
1.208 + if (IonSpewEnabled(IonSpew_Alias)) {
1.209 + fprintf(IonSpewFile, "Processing store ");
1.210 + def->printName(IonSpewFile);
1.211 + fprintf(IonSpewFile, " (flags %x)\n", set.flags());
1.212 + }
1.213 + } else {
1.214 + // Find the most recent store on which this instruction depends.
1.215 + MDefinition *lastStore = firstIns;
1.216 +
1.217 + for (AliasSetIterator iter(set); iter; iter++) {
1.218 + MDefinitionVector &aliasedStores = stores[*iter];
1.219 + for (int i = aliasedStores.length() - 1; i >= 0; i--) {
1.220 + MDefinition *store = aliasedStores[i];
1.221 + if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
1.222 + if (lastStore->id() < store->id())
1.223 + lastStore = store;
1.224 + break;
1.225 + }
1.226 + }
1.227 + }
1.228 +
1.229 + def->setDependency(lastStore);
1.230 + IonSpewDependency(*def, lastStore, "depends", "");
1.231 +
1.232 + // If the last store was before the current loop, we assume this load
1.233 + // is loop invariant. If a later instruction writes to the same location,
1.234 + // we will fix this at the end of the loop.
1.235 + if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
1.236 + if (!loop_->addInvariantLoad(*def))
1.237 + return false;
1.238 + }
1.239 + }
1.240 + }
1.241 +
1.242 + // Renumber the last instruction, as the analysis depends on this and the order.
1.243 + block->lastIns()->setId(newId++);
1.244 +
1.245 + if (block->isLoopBackedge()) {
1.246 + JS_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
1.247 + IonSpew(IonSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
1.248 + loop_->loopHeader()->id());
1.249 + LoopAliasInfo *outerLoop = loop_->outer();
1.250 + MInstruction *firstLoopIns = *loop_->loopHeader()->begin();
1.251 +
1.252 + const MDefinitionVector &invariant = loop_->invariantLoads();
1.253 +
1.254 + for (unsigned i = 0; i < invariant.length(); i++) {
1.255 + MDefinition *ins = invariant[i];
1.256 + AliasSet set = ins->getAliasSet();
1.257 + JS_ASSERT(set.isLoad());
1.258 +
1.259 + bool hasAlias = false;
1.260 + for (AliasSetIterator iter(set); iter; iter++) {
1.261 + MDefinitionVector &aliasedStores = stores[*iter];
1.262 + for (int i = aliasedStores.length() - 1;; i--) {
1.263 + MDefinition *store = aliasedStores[i];
1.264 + if (store->id() < firstLoopIns->id())
1.265 + break;
1.266 + if (ins->mightAlias(store)) {
1.267 + hasAlias = true;
1.268 + IonSpewDependency(ins, store, "aliases", "store in loop body");
1.269 + break;
1.270 + }
1.271 + }
1.272 + if (hasAlias)
1.273 + break;
1.274 + }
1.275 +
1.276 + if (hasAlias) {
1.277 + // This instruction depends on stores inside the loop body. Mark it as having a
1.278 + // dependency on the last instruction of the loop header. The last instruction is a
1.279 + // control instruction and these are never hoisted.
1.280 + MControlInstruction *controlIns = loop_->loopHeader()->lastIns();
1.281 + IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");
1.282 + ins->setDependency(controlIns);
1.283 + } else {
1.284 + IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");
1.285 +
1.286 + if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
1.287 + IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
1.288 + if (!outerLoop->addInvariantLoad(ins))
1.289 + return false;
1.290 + }
1.291 + }
1.292 + }
1.293 + loop_ = loop_->outer();
1.294 + }
1.295 + }
1.296 +
1.297 + JS_ASSERT(loop_ == nullptr);
1.298 + return true;
1.299 +}
