The Tor Browser: js/src/jit/BacktrackingAllocator.h@129ffea94266 (annotated)

js/src/jit/BacktrackingAllocator.h@129ffea94266 (annotated)

js/src/jit/BacktrackingAllocator.h

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/. */
 #ifndef jit_BacktrackingAllocator_h
 #define jit_BacktrackingAllocator_h
 #include "mozilla/Array.h"
 #include "ds/PriorityQueue.h"
 #include "ds/SplayTree.h"
 #include "jit/LiveRangeAllocator.h"
 // Backtracking priority queue based register allocator based on that described
 // in the following blog post:
 //
 // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
 namespace js {
 namespace jit {
 // Information about a group of registers. Registers may be grouped together
 // when (a) all of their lifetimes are disjoint, (b) they are of the same type
 // (double / non-double) and (c) it is desirable that they have the same
 // allocation.
 struct VirtualRegisterGroup : public TempObject
 {
     // All virtual registers in the group.
     Vector<uint32_t, 2, IonAllocPolicy> registers;
     // Desired physical register to use for registers in the group.
     LAllocation allocation;
     // Spill location to be shared by registers in the group.
     LAllocation spill;
     explicit VirtualRegisterGroup(TempAllocator &alloc)
       : registers(alloc), allocation(LUse(0, LUse::ANY)), spill(LUse(0, LUse::ANY))
     {}
     uint32_t canonicalReg() {
         uint32_t minimum = registers[0];
         for (size_t i = 1; i < registers.length(); i++)
             minimum = Min(minimum, registers[i]);
         return minimum;
     }
 };
 class BacktrackingVirtualRegister : public VirtualRegister
 {
     // If this register's definition is MUST_REUSE_INPUT, whether a copy must
     // be introduced before the definition that relaxes the policy.
     bool mustCopyInput_;
     // Spill location to use for this register.
     LAllocation canonicalSpill_;
     // Code position above which the canonical spill cannot be used; such
     // intervals may overlap other registers in the same group.
     CodePosition canonicalSpillExclude_;
     // If this register is associated with a group of other registers,
     // information about the group. This structure is shared between all
     // registers in the group.
     VirtualRegisterGroup *group_;
   public:
     explicit BacktrackingVirtualRegister(TempAllocator &alloc)
       : VirtualRegister(alloc)
     {}
     void setMustCopyInput() {
         mustCopyInput_ = true;
     }
     bool mustCopyInput() {
         return mustCopyInput_;
     }
     void setCanonicalSpill(LAllocation alloc) {
         JS_ASSERT(!alloc.isUse());
         canonicalSpill_ = alloc;
     }
     const LAllocation *canonicalSpill() const {
         return canonicalSpill_.isUse() ? nullptr : &canonicalSpill_;
     }
     void setCanonicalSpillExclude(CodePosition pos) {
         canonicalSpillExclude_ = pos;
     }
     bool hasCanonicalSpillExclude() const {
         return canonicalSpillExclude_.pos() != 0;
     }
     CodePosition canonicalSpillExclude() const {
         JS_ASSERT(hasCanonicalSpillExclude());
         return canonicalSpillExclude_;
     }
     void setGroup(VirtualRegisterGroup *group) {
         group_ = group;
     }
     VirtualRegisterGroup *group() {
         return group_;
     }
 };
 // A sequence of code positions, for tellings BacktrackingAllocator::splitAt
 // where to split.
 typedef js::Vector<CodePosition, 4, SystemAllocPolicy> SplitPositionVector;
 class BacktrackingAllocator
   : private LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>
 {
     // Priority queue element: either an interval or group of intervals and the
     // associated priority.
     struct QueueItem
     {
         LiveInterval *interval;
         VirtualRegisterGroup *group;
         QueueItem(LiveInterval *interval, size_t priority)
           : interval(interval), group(nullptr), priority_(priority)
         {}
         QueueItem(VirtualRegisterGroup *group, size_t priority)
           : interval(nullptr), group(group), priority_(priority)
         {}
         static size_t priority(const QueueItem &v) {
             return v.priority_;
         }
       private:
         size_t priority_;
     };
     PriorityQueue<QueueItem, QueueItem, 0, SystemAllocPolicy> allocationQueue;
     // A subrange over which a physical register is allocated.
     struct AllocatedRange {
         LiveInterval *interval;
         const LiveInterval::Range *range;
         AllocatedRange()
           : interval(nullptr), range(nullptr)
         {}
         AllocatedRange(LiveInterval *interval, const LiveInterval::Range *range)
           : interval(interval), range(range)
         {}
         static int compare(const AllocatedRange &v0, const AllocatedRange &v1) {
             // LiveInterval::Range includes 'from' but excludes 'to'.
             if (v0.range->to.pos() <= v1.range->from.pos())
                 return -1;
             if (v0.range->from.pos() >= v1.range->to.pos())
                 return 1;
             return 0;
         }
     };
     typedef SplayTree<AllocatedRange, AllocatedRange> AllocatedRangeSet;
     // Each physical register is associated with the set of ranges over which
     // that register is currently allocated.
     struct PhysicalRegister {
         bool allocatable;
         AnyRegister reg;
         AllocatedRangeSet allocations;
         PhysicalRegister() : allocatable(false) {}
     };
     mozilla::Array<PhysicalRegister, AnyRegister::Total> registers;
     // Ranges of code which are considered to be hot, for which good allocation
     // should be prioritized.
     AllocatedRangeSet hotcode;
   public:
     BacktrackingAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
       : LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>(mir, lir, graph)
     { }
     bool go();
   private:
     typedef Vector<LiveInterval *, 4, SystemAllocPolicy> LiveIntervalVector;
     bool init();
     bool canAddToGroup(VirtualRegisterGroup *group, BacktrackingVirtualRegister *reg);
     bool tryGroupRegisters(uint32_t vreg0, uint32_t vreg1);
     bool tryGroupReusedRegister(uint32_t def, uint32_t use);
     bool groupAndQueueRegisters();
     bool tryAllocateFixed(LiveInterval *interval, bool *success, bool *pfixed, LiveInterval **pconflicting);
     bool tryAllocateNonFixed(LiveInterval *interval, bool *success, bool *pfixed, LiveInterval **pconflicting);
     bool processInterval(LiveInterval *interval);
     bool processGroup(VirtualRegisterGroup *group);
     bool setIntervalRequirement(LiveInterval *interval);
     bool tryAllocateRegister(PhysicalRegister &r, LiveInterval *interval,
                              bool *success, bool *pfixed, LiveInterval **pconflicting);
     bool tryAllocateGroupRegister(PhysicalRegister &r, VirtualRegisterGroup *group,
                                   bool *psuccess, bool *pfixed, LiveInterval **pconflicting);
     bool evictInterval(LiveInterval *interval);
     void distributeUses(LiveInterval *interval, const LiveIntervalVector &newIntervals);
     bool split(LiveInterval *interval, const LiveIntervalVector &newIntervals);
     bool requeueIntervals(const LiveIntervalVector &newIntervals);
     void spill(LiveInterval *interval);
     bool isReusedInput(LUse *use, LInstruction *ins, bool considerCopy);
     bool isRegisterUse(LUse *use, LInstruction *ins, bool considerCopy = false);
     bool isRegisterDefinition(LiveInterval *interval);
     bool addLiveInterval(LiveIntervalVector &intervals, uint32_t vreg,
                          LiveInterval *spillInterval,
                          CodePosition from, CodePosition to);
     bool resolveControlFlow();
     bool reifyAllocations();
     bool populateSafepoints();
     void dumpRegisterGroups();
     void dumpLiveness();
     void dumpAllocations();
     struct PrintLiveIntervalRange;
     bool minimalDef(const LiveInterval *interval, LInstruction *ins);
     bool minimalUse(const LiveInterval *interval, LInstruction *ins);
     bool minimalInterval(const LiveInterval *interval, bool *pfixed = nullptr);
     // Heuristic methods.
     size_t computePriority(const LiveInterval *interval);
     size_t computeSpillWeight(const LiveInterval *interval);
     size_t computePriority(const VirtualRegisterGroup *group);
     size_t computeSpillWeight(const VirtualRegisterGroup *group);
     bool chooseIntervalSplit(LiveInterval *interval, LiveInterval *conflict);
     bool splitAt(LiveInterval *interval,
                  const SplitPositionVector &splitPositions);
     bool trySplitAcrossHotcode(LiveInterval *interval, bool *success);
     bool trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success);
     bool splitAtAllRegisterUses(LiveInterval *interval);
     bool splitAcrossCalls(LiveInterval *interval);
 };
 } // namespace jit
 } // namespace js
 #endif /* jit_BacktrackingAllocator_h */

The Tor Browser / annotate

js/src/jit/BacktrackingAllocator.h@129ffea94266 (annotated)

js/src/jit/BacktrackingAllocator.h