The Tor Browser: js/src/jit/AliasAnalysis.cpp@129ffea94266 (annotated)

js/src/jit/AliasAnalysis.cpp@129ffea94266 (annotated)

js/src/jit/AliasAnalysis.cpp

Sat, 03 Jan 2015 20:18:00 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Sat, 03 Jan 2015 20:18:00 +0100
branch: TOR_BUG_3246
changeset 7: 129ffea94266
permissions: -rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/AliasAnalysis.h"
 #include <stdio.h>
 #include "jit/Ion.h"
 #include "jit/IonBuilder.h"
 #include "jit/IonSpewer.h"
 #include "jit/MIR.h"
 #include "jit/MIRGraph.h"
 using namespace js;
 using namespace js::jit;
 using mozilla::Array;
 namespace js {
 namespace jit {
 class LoopAliasInfo : public TempObject
 {
   private:
     LoopAliasInfo *outer_;
     MBasicBlock *loopHeader_;
     MDefinitionVector invariantLoads_;
   public:
     LoopAliasInfo(TempAllocator &alloc, LoopAliasInfo *outer, MBasicBlock *loopHeader)
       : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)
     { }
     MBasicBlock *loopHeader() const {
         return loopHeader_;
     }
     LoopAliasInfo *outer() const {
         return outer_;
     }
     bool addInvariantLoad(MDefinition *ins) {
         return invariantLoads_.append(ins);
     }
     const MDefinitionVector& invariantLoads() const {
         return invariantLoads_;
     }
     MDefinition *firstInstruction() const {
         return *loopHeader_->begin();
     }
 };
 } // namespace jit
 } // namespace js
 namespace {
 // Iterates over the flags in an AliasSet.
 class AliasSetIterator
 {
   private:
     uint32_t flags;
     unsigned pos;
   public:
     AliasSetIterator(AliasSet set)
       : flags(set.flags()), pos(0)
     {
         while (flags && (flags & 1) == 0) {
             flags >>= 1;
             pos++;
         }
     }
     AliasSetIterator& operator ++(int) {
         do {
             flags >>= 1;
             pos++;
         } while (flags && (flags & 1) == 0);
         return *this;
     }
     operator bool() const {
         return !!flags;
     }
     unsigned operator *() const {
         JS_ASSERT(pos < AliasSet::NumCategories);
         return pos;
     }
 };
 } /* anonymous namespace */
 AliasAnalysis::AliasAnalysis(MIRGenerator *mir, MIRGraph &graph)
   : mir(mir),
     graph_(graph),
     loop_(nullptr)
 {
 }
 // Whether there might be a path from src to dest, excluding loop backedges. This is
 // approximate and really ought to depend on precomputed reachability information.
 static inline bool
 BlockMightReach(MBasicBlock *src, MBasicBlock *dest)
 {
     while (src->id() <= dest->id()) {
         if (src == dest)
             return true;
         switch (src->numSuccessors()) {
           case 0:
             return false;
           case 1: {
             MBasicBlock *successor = src->getSuccessor(0);
             if (successor->id() <= src->id())
                 return true; // Don't iloop.
             src = successor;
             break;
           }
           default:
             return true;
         }
     }
     return false;
 }
 static void
 IonSpewDependency(MDefinition *load, MDefinition *store, const char *verb, const char *reason)
 {
     if (!IonSpewEnabled(IonSpew_Alias))
         return;
     fprintf(IonSpewFile, "Load ");
     load->printName(IonSpewFile);
     fprintf(IonSpewFile, " %s on store ", verb);
     store->printName(IonSpewFile);
     fprintf(IonSpewFile, " (%s)\n", reason);
 }
 static void
 IonSpewAliasInfo(const char *pre, MDefinition *ins, const char *post)
 {
     if (!IonSpewEnabled(IonSpew_Alias))
         return;
     fprintf(IonSpewFile, "%s ", pre);
     ins->printName(IonSpewFile);
     fprintf(IonSpewFile, " %s\n", post);
 }
 // This pass annotates every load instruction with the last store instruction
 // on which it depends. The algorithm is optimistic in that it ignores explicit
 // dependencies and only considers loads and stores.
 //
 // Loads inside loops only have an implicit dependency on a store before the
 // loop header if no instruction inside the loop body aliases it. To calculate
 // this efficiently, we maintain a list of maybe-invariant loads and the combined
 // alias set for all stores inside the loop. When we see the loop's backedge, this
 // information is used to mark every load we wrongly assumed to be loop invaraint as
 // having an implicit dependency on the last instruction of the loop header, so that
 // it's never moved before the loop header.
 //
 // The algorithm depends on the invariant that both control instructions and effectful
 // instructions (stores) are never hoisted.
 bool
 AliasAnalysis::analyze()
 {
     Vector<MDefinitionVector, AliasSet::NumCategories, IonAllocPolicy> stores(alloc());
     // Initialize to the first instruction.
     MDefinition *firstIns = *graph_.begin()->begin();
     for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
         MDefinitionVector defs(alloc());
         if (!defs.append(firstIns))
             return false;
         if (!stores.append(Move(defs)))
             return false;
     }
     // Type analysis may have inserted new instructions. Since this pass depends
     // on the instruction number ordering, all instructions are renumbered.
     // We start with 1 because some passes use 0 to denote failure.
     uint32_t newId = 1;
     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
         if (mir->shouldCancel("Alias Analysis (main loop)"))
             return false;
         if (block->isLoopHeader()) {
             IonSpew(IonSpew_Alias, "Processing loop header %d", block->id());
             loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
         }
         for (MDefinitionIterator def(*block); def; def++) {
             def->setId(newId++);
             AliasSet set = def->getAliasSet();
             if (set.isNone())
                 continue;
             if (set.isStore()) {
                 for (AliasSetIterator iter(set); iter; iter++) {
                     if (!stores[*iter].append(*def))
                         return false;
                 }
                 if (IonSpewEnabled(IonSpew_Alias)) {
                     fprintf(IonSpewFile, "Processing store ");
                     def->printName(IonSpewFile);
                     fprintf(IonSpewFile, " (flags %x)\n", set.flags());
                 }
             } else {
                 // Find the most recent store on which this instruction depends.
                 MDefinition *lastStore = firstIns;
                 for (AliasSetIterator iter(set); iter; iter++) {
                     MDefinitionVector &aliasedStores = stores[*iter];
                     for (int i = aliasedStores.length() - 1; i >= 0; i--) {
                         MDefinition *store = aliasedStores[i];
                         if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
                             if (lastStore->id() < store->id())
                                 lastStore = store;
                             break;
                         }
                     }
                 }
                 def->setDependency(lastStore);
                 IonSpewDependency(*def, lastStore, "depends", "");
                 // If the last store was before the current loop, we assume this load
                 // is loop invariant. If a later instruction writes to the same location,
                 // we will fix this at the end of the loop.
                 if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
                     if (!loop_->addInvariantLoad(*def))
                         return false;
                 }
             }
         }
         // Renumber the last instruction, as the analysis depends on this and the order.
         block->lastIns()->setId(newId++);
         if (block->isLoopBackedge()) {
             JS_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
             IonSpew(IonSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
                     loop_->loopHeader()->id());
             LoopAliasInfo *outerLoop = loop_->outer();
             MInstruction *firstLoopIns = *loop_->loopHeader()->begin();
             const MDefinitionVector &invariant = loop_->invariantLoads();
             for (unsigned i = 0; i < invariant.length(); i++) {
                 MDefinition *ins = invariant[i];
                 AliasSet set = ins->getAliasSet();
                 JS_ASSERT(set.isLoad());
                 bool hasAlias = false;
                 for (AliasSetIterator iter(set); iter; iter++) {
                     MDefinitionVector &aliasedStores = stores[*iter];
                     for (int i = aliasedStores.length() - 1;; i--) {
                         MDefinition *store = aliasedStores[i];
                         if (store->id() < firstLoopIns->id())
                             break;
                         if (ins->mightAlias(store)) {
                             hasAlias = true;
                             IonSpewDependency(ins, store, "aliases", "store in loop body");
                             break;
                         }
                     }
                     if (hasAlias)
                         break;
                 }
                 if (hasAlias) {
                     // This instruction depends on stores inside the loop body. Mark it as having a
                     // dependency on the last instruction of the loop header. The last instruction is a
                     // control instruction and these are never hoisted.
                     MControlInstruction *controlIns = loop_->loopHeader()->lastIns();
                     IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");
                     ins->setDependency(controlIns);
                 } else {
                     IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");
                     if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
                         IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
                         if (!outerLoop->addInvariantLoad(ins))
                             return false;
                     }
                 }
             }
             loop_ = loop_->outer();
         }
     }
     JS_ASSERT(loop_ == nullptr);
     return true;
 }

The Tor Browser / annotate

js/src/jit/AliasAnalysis.cpp@129ffea94266 (annotated)

js/src/jit/AliasAnalysis.cpp