diff options
Diffstat (limited to 'js/src/jit/OptimizationTracking.h')
| -rw-r--r-- | js/src/jit/OptimizationTracking.h | 575 |
1 files changed, 575 insertions, 0 deletions
diff --git a/js/src/jit/OptimizationTracking.h b/js/src/jit/OptimizationTracking.h new file mode 100644 index 000000000..a37c6377c --- /dev/null +++ b/js/src/jit/OptimizationTracking.h @@ -0,0 +1,575 @@ +/* -*- 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_OptimizationTracking_h +#define jit_OptimizationTracking_h + +#include "mozilla/Maybe.h" + +#include "jit/CompactBuffer.h" +#include "jit/CompileInfo.h" +#include "jit/JitAllocPolicy.h" +#include "js/TrackedOptimizationInfo.h" +#include "vm/TypeInference.h" + +namespace js { + +namespace jit { + +struct NativeToTrackedOptimizations; + +class OptimizationAttempt +{ + JS::TrackedStrategy strategy_; + JS::TrackedOutcome outcome_; + + public: + OptimizationAttempt(JS::TrackedStrategy strategy, JS::TrackedOutcome outcome) + : strategy_(strategy), + outcome_(outcome) + { } + + void setOutcome(JS::TrackedOutcome outcome) { outcome_ = outcome; } + bool succeeded() const { return outcome_ >= JS::TrackedOutcome::GenericSuccess; } + bool failed() const { return outcome_ < JS::TrackedOutcome::GenericSuccess; } + JS::TrackedStrategy strategy() const { return strategy_; } + JS::TrackedOutcome outcome() const { return outcome_; } + + bool operator ==(const OptimizationAttempt& other) const { + return strategy_ == other.strategy_ && outcome_ == other.outcome_; + } + bool operator !=(const OptimizationAttempt& other) const { + return strategy_ != other.strategy_ || outcome_ != other.outcome_; + } + HashNumber hash() const { + return (HashNumber(strategy_) << 8) + HashNumber(outcome_); + } + + void writeCompact(CompactBufferWriter& writer) const; +}; + +typedef Vector<OptimizationAttempt, 4, JitAllocPolicy> TempOptimizationAttemptsVector; +typedef Vector<TypeSet::Type, 1, JitAllocPolicy> TempTypeList; + +class UniqueTrackedTypes; + +class OptimizationTypeInfo +{ + JS::TrackedTypeSite site_; + MIRType mirType_; + TempTypeList types_; + + public: + OptimizationTypeInfo(OptimizationTypeInfo&& other) + : site_(other.site_), + mirType_(other.mirType_), + types_(mozilla::Move(other.types_)) + { } + + OptimizationTypeInfo(TempAllocator& alloc, JS::TrackedTypeSite site, MIRType mirType) + : site_(site), + mirType_(mirType), + types_(alloc) + { } + + MOZ_MUST_USE bool trackTypeSet(TemporaryTypeSet* typeSet); + MOZ_MUST_USE bool trackType(TypeSet::Type type); + + JS::TrackedTypeSite site() const { return site_; } + MIRType mirType() const { return mirType_; } + const TempTypeList& types() const { return types_; } + + bool operator ==(const OptimizationTypeInfo& other) const; + bool operator !=(const OptimizationTypeInfo& other) const; + + HashNumber hash() const; + + MOZ_MUST_USE bool writeCompact(JSContext* cx, CompactBufferWriter& writer, + UniqueTrackedTypes& uniqueTypes) const; +}; + +typedef Vector<OptimizationTypeInfo, 1, JitAllocPolicy> TempOptimizationTypeInfoVector; + +// Tracks the optimization attempts made at a bytecode location. +class TrackedOptimizations : public TempObject +{ + friend class UniqueTrackedOptimizations; + TempOptimizationTypeInfoVector types_; + TempOptimizationAttemptsVector attempts_; + uint32_t currentAttempt_; + + public: + explicit TrackedOptimizations(TempAllocator& alloc) + : types_(alloc), + attempts_(alloc), + currentAttempt_(UINT32_MAX) + { } + + void clear() { + types_.clear(); + attempts_.clear(); + currentAttempt_ = UINT32_MAX; + } + + MOZ_MUST_USE bool trackTypeInfo(OptimizationTypeInfo&& ty); + + MOZ_MUST_USE bool trackAttempt(JS::TrackedStrategy strategy); + void amendAttempt(uint32_t index); + void trackOutcome(JS::TrackedOutcome outcome); + void trackSuccess(); + + bool matchTypes(const TempOptimizationTypeInfoVector& other) const; + bool matchAttempts(const TempOptimizationAttemptsVector& other) const; + + void spew() const; +}; + +// Assigns each unique sequence of optimization attempts an index; outputs a +// compact table. +class UniqueTrackedOptimizations +{ + public: + struct SortEntry + { + const TempOptimizationTypeInfoVector* types; + const TempOptimizationAttemptsVector* attempts; + uint32_t frequency; + }; + typedef Vector<SortEntry, 4> SortedVector; + + private: + struct Key + { + const TempOptimizationTypeInfoVector* types; + const TempOptimizationAttemptsVector* attempts; + + typedef Key Lookup; + static HashNumber hash(const Lookup& lookup); + static bool match(const Key& key, const Lookup& lookup); + static void rekey(Key& key, const Key& newKey) { + key = newKey; + } + }; + + struct Entry + { + uint8_t index; + uint32_t frequency; + }; + + // Map of unique (TempOptimizationTypeInfoVector, + // TempOptimizationAttemptsVector) pairs to indices. + typedef HashMap<Key, Entry, Key> AttemptsMap; + AttemptsMap map_; + + // TempOptimizationAttemptsVectors sorted by frequency. + SortedVector sorted_; + + public: + explicit UniqueTrackedOptimizations(JSContext* cx) + : map_(cx), + sorted_(cx) + { } + + MOZ_MUST_USE bool init() { return map_.init(); } + MOZ_MUST_USE bool add(const TrackedOptimizations* optimizations); + + MOZ_MUST_USE bool sortByFrequency(JSContext* cx); + bool sorted() const { return !sorted_.empty(); } + uint32_t count() const { MOZ_ASSERT(sorted()); return sorted_.length(); } + const SortedVector& sortedVector() const { MOZ_ASSERT(sorted()); return sorted_; } + uint8_t indexOf(const TrackedOptimizations* optimizations) const; +}; + +// A compact table of tracked optimization information. Pictorially, +// +// +------------------------------------------------+ +// | Region 1 | | +// |------------------------------------------------| | +// | Region 2 | | +// |------------------------------------------------| |-- PayloadR of list-of-list of +// | ... | | range triples (see below) +// |------------------------------------------------| | +// | Region M | | +// +================================================+ <- IonTrackedOptimizationsRegionTable +// | uint32_t numRegions_ = M | | +// +------------------------------------------------+ | +// | Region 1 | | +// | uint32_t regionOffset = size(PayloadR) | | +// +------------------------------------------------+ |-- Table +// | ... | | +// +------------------------------------------------+ | +// | Region M | | +// | uint32_t regionOffset | | +// +================================================+ +// | Optimization type info 1 | | +// |------------------------------------------------| | +// | Optimization type info 2 | |-- PayloadT of list of +// |------------------------------------------------| | OptimizationTypeInfo in +// | ... | | order of decreasing frequency +// |------------------------------------------------| | +// | Optimization type info N | | +// +================================================+ <- IonTrackedOptimizationsTypesTable +// | uint32_t numEntries_ = N | | +// +------------------------------------------------+ | +// | Optimization type info 1 | | +// | uint32_t entryOffset = size(PayloadT) | | +// +------------------------------------------------+ |-- Table +// | ... | | +// +------------------------------------------------+ | +// | Optimization type info N | | +// | uint32_t entryOffset | | +// +================================================+ +// | Optimization attempts 1 | | +// |------------------------------------------------| | +// | Optimization attempts 2 | |-- PayloadA of list of +// |------------------------------------------------| | OptimizationAttempts in +// | ... | | order of decreasing frequency +// |------------------------------------------------| | +// | Optimization attempts N | | +// +================================================+ <- IonTrackedOptimizationsAttemptsTable +// | uint32_t numEntries_ = N | | +// +------------------------------------------------+ | +// | Optimization attempts 1 | | +// | uint32_t entryOffset = size(PayloadA) | | +// +------------------------------------------------+ |-- Table +// | ... | | +// +------------------------------------------------+ | +// | Optimization attempts N | | +// | uint32_t entryOffset | | +// +------------------------------------------------+ +// +// Abstractly, each region in the PayloadR section is a list of triples of the +// following, in order of ascending startOffset: +// +// (startOffset, endOffset, optimization attempts index) +// +// The range of [startOffset, endOffset) is the native machine code offsets +// for which the optimization attempts referred to by the index applies. +// +// Concretely, each region starts with a header of: +// +// { startOffset : 32, endOffset : 32 } +// +// followed by an (endOffset, index) pair, then by delta-encoded variants +// triples described below. +// +// Each list of type infos in the PayloadT section is a list of triples: +// +// (kind, MIR type, type set) +// +// The type set is separately in another vector, and what is encoded instead +// is the (offset, length) pair needed to index into that vector. +// +// Each list of optimization attempts in the PayloadA section is a list of +// pairs: +// +// (strategy, outcome) +// +// Both tail tables for PayloadR and PayloadA use reverse offsets from the +// table pointers. + +class IonTrackedOptimizationsRegion +{ + const uint8_t* start_; + const uint8_t* end_; + + // Unpacked state. + uint32_t startOffset_; + uint32_t endOffset_; + const uint8_t* rangesStart_; + + void unpackHeader(); + + public: + IonTrackedOptimizationsRegion(const uint8_t* start, const uint8_t* end) + : start_(start), end_(end), + startOffset_(0), endOffset_(0), rangesStart_(nullptr) + { + MOZ_ASSERT(start < end); + unpackHeader(); + } + + // Offsets for the entire range that this region covers. + // + // This, as well as the offsets for the deltas, is open at the ending + // address: [startOffset, endOffset). + uint32_t startOffset() const { return startOffset_; } + uint32_t endOffset() const { return endOffset_; } + + class RangeIterator + { + const uint8_t* cur_; + const uint8_t* start_; + const uint8_t* end_; + + uint32_t firstStartOffset_; + uint32_t prevEndOffset_; + + public: + RangeIterator(const uint8_t* start, const uint8_t* end, uint32_t startOffset) + : cur_(start), start_(start), end_(end), + firstStartOffset_(startOffset), prevEndOffset_(0) + { } + + bool more() const { return cur_ < end_; } + void readNext(uint32_t* startOffset, uint32_t* endOffset, uint8_t* index); + }; + + RangeIterator ranges() const { return RangeIterator(rangesStart_, end_, startOffset_); } + + // Find the index of tracked optimization info (e.g., type info and + // attempts) at a native code offset. + mozilla::Maybe<uint8_t> findIndex(uint32_t offset, uint32_t* entryOffsetOut) const; + + // For the variants below, S stands for startDelta, L for length, and I + // for index. These were automatically generated from training on the + // Octane benchmark. + // + // byte 1 byte 0 + // SSSS-SSSL LLLL-LII0 + // startDelta max 127, length max 63, index max 3 + + static const uint32_t ENC1_MASK = 0x1; + static const uint32_t ENC1_MASK_VAL = 0x0; + + static const uint32_t ENC1_START_DELTA_MAX = 0x7f; + static const uint32_t ENC1_START_DELTA_SHIFT = 9; + + static const uint32_t ENC1_LENGTH_MAX = 0x3f; + static const uint32_t ENC1_LENGTH_SHIFT = 3; + + static const uint32_t ENC1_INDEX_MAX = 0x3; + static const uint32_t ENC1_INDEX_SHIFT = 1; + + // byte 2 byte 1 byte 0 + // SSSS-SSSS SSSS-LLLL LLII-II01 + // startDelta max 4095, length max 63, index max 15 + + static const uint32_t ENC2_MASK = 0x3; + static const uint32_t ENC2_MASK_VAL = 0x1; + + static const uint32_t ENC2_START_DELTA_MAX = 0xfff; + static const uint32_t ENC2_START_DELTA_SHIFT = 12; + + static const uint32_t ENC2_LENGTH_MAX = 0x3f; + static const uint32_t ENC2_LENGTH_SHIFT = 6; + + static const uint32_t ENC2_INDEX_MAX = 0xf; + static const uint32_t ENC2_INDEX_SHIFT = 2; + + // byte 3 byte 2 byte 1 byte 0 + // SSSS-SSSS SSSL-LLLL LLLL-LIII IIII-I011 + // startDelta max 2047, length max 1023, index max 255 + + static const uint32_t ENC3_MASK = 0x7; + static const uint32_t ENC3_MASK_VAL = 0x3; + + static const uint32_t ENC3_START_DELTA_MAX = 0x7ff; + static const uint32_t ENC3_START_DELTA_SHIFT = 21; + + static const uint32_t ENC3_LENGTH_MAX = 0x3ff; + static const uint32_t ENC3_LENGTH_SHIFT = 11; + + static const uint32_t ENC3_INDEX_MAX = 0xff; + static const uint32_t ENC3_INDEX_SHIFT = 3; + + // byte 4 byte 3 byte 2 byte 1 byte 0 + // SSSS-SSSS SSSS-SSSL LLLL-LLLL LLLL-LIII IIII-I111 + // startDelta max 32767, length max 16383, index max 255 + + static const uint32_t ENC4_MASK = 0x7; + static const uint32_t ENC4_MASK_VAL = 0x7; + + static const uint32_t ENC4_START_DELTA_MAX = 0x7fff; + static const uint32_t ENC4_START_DELTA_SHIFT = 25; + + static const uint32_t ENC4_LENGTH_MAX = 0x3fff; + static const uint32_t ENC4_LENGTH_SHIFT = 11; + + static const uint32_t ENC4_INDEX_MAX = 0xff; + static const uint32_t ENC4_INDEX_SHIFT = 3; + + static bool IsDeltaEncodeable(uint32_t startDelta, uint32_t length) { + MOZ_ASSERT(length != 0); + return startDelta <= ENC4_START_DELTA_MAX && length <= ENC4_LENGTH_MAX; + } + + static const uint32_t MAX_RUN_LENGTH = 100; + + static uint32_t ExpectedRunLength(const NativeToTrackedOptimizations* start, + const NativeToTrackedOptimizations* end); + + static void ReadDelta(CompactBufferReader& reader, uint32_t* startDelta, uint32_t* length, + uint8_t* index); + static void WriteDelta(CompactBufferWriter& writer, uint32_t startDelta, uint32_t length, + uint8_t index); + static MOZ_MUST_USE bool WriteRun(CompactBufferWriter& writer, + const NativeToTrackedOptimizations* start, + const NativeToTrackedOptimizations* end, + const UniqueTrackedOptimizations& unique); +}; + +class IonTrackedOptimizationsAttempts +{ + const uint8_t* start_; + const uint8_t* end_; + + public: + IonTrackedOptimizationsAttempts(const uint8_t* start, const uint8_t* end) + : start_(start), end_(end) + { + // Cannot be empty. + MOZ_ASSERT(start < end); + } + + void forEach(JS::ForEachTrackedOptimizationAttemptOp& op); +}; + +struct IonTrackedTypeWithAddendum +{ + TypeSet::Type type; + + enum HasAddendum { + HasNothing, + HasAllocationSite, + HasConstructor + }; + HasAddendum hasAddendum; + + // If type is a type object and is tied to a site, the script and pc are + // resolved early and stored below. This is done to avoid accessing the + // compartment during profiling time. + union { + struct { + JSScript* script; + uint32_t offset; + }; + JSFunction* constructor; + }; + + explicit IonTrackedTypeWithAddendum(TypeSet::Type type) + : type(type), + hasAddendum(HasNothing) + { } + + IonTrackedTypeWithAddendum(TypeSet::Type type, JSScript* script, uint32_t offset) + : type(type), + hasAddendum(HasAllocationSite), + script(script), + offset(offset) + { } + + IonTrackedTypeWithAddendum(TypeSet::Type type, JSFunction* constructor) + : type(type), + hasAddendum(HasConstructor), + constructor(constructor) + { } + + bool hasAllocationSite() const { return hasAddendum == HasAllocationSite; } + bool hasConstructor() const { return hasAddendum == HasConstructor; } +}; + +typedef Vector<IonTrackedTypeWithAddendum, 1, SystemAllocPolicy> IonTrackedTypeVector; + +class IonTrackedOptimizationsTypeInfo +{ + const uint8_t* start_; + const uint8_t* end_; + + public: + IonTrackedOptimizationsTypeInfo(const uint8_t* start, const uint8_t* end) + : start_(start), end_(end) + { + // Can be empty; i.e., no type info was tracked. + } + + bool empty() const { return start_ == end_; } + + // Unlike IonTrackedOptimizationAttempts, + // JS::ForEachTrackedOptimizationTypeInfoOp cannot be used directly. The + // internal API needs to deal with engine-internal data structures (e.g., + // TypeSet::Type) directly. + // + // An adapter is provided below. + struct ForEachOp + { + virtual void readType(const IonTrackedTypeWithAddendum& tracked) = 0; + virtual void operator()(JS::TrackedTypeSite site, MIRType mirType) = 0; + }; + + class ForEachOpAdapter : public ForEachOp + { + JS::ForEachTrackedOptimizationTypeInfoOp& op_; + + public: + explicit ForEachOpAdapter(JS::ForEachTrackedOptimizationTypeInfoOp& op) + : op_(op) + { } + + void readType(const IonTrackedTypeWithAddendum& tracked) override; + void operator()(JS::TrackedTypeSite site, MIRType mirType) override; + }; + + void forEach(ForEachOp& op, const IonTrackedTypeVector* allTypes); +}; + +template <class Entry> +class IonTrackedOptimizationsOffsetsTable +{ + uint32_t padding_; + uint32_t numEntries_; + uint32_t entryOffsets_[1]; + + protected: + const uint8_t* payloadEnd() const { + return (uint8_t*)(this) - padding_; + } + + public: + uint32_t numEntries() const { return numEntries_; } + uint32_t entryOffset(uint32_t index) const { + MOZ_ASSERT(index < numEntries()); + return entryOffsets_[index]; + } + + Entry entry(uint32_t index) const { + const uint8_t* start = payloadEnd() - entryOffset(index); + const uint8_t* end = payloadEnd(); + if (index < numEntries() - 1) + end -= entryOffset(index + 1); + return Entry(start, end); + } +}; + +class IonTrackedOptimizationsRegionTable + : public IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsRegion> +{ + public: + mozilla::Maybe<IonTrackedOptimizationsRegion> findRegion(uint32_t offset) const; + + const uint8_t* payloadStart() const { return payloadEnd() - entryOffset(0); } +}; + +typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsAttempts> + IonTrackedOptimizationsAttemptsTable; + +typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsTypeInfo> + IonTrackedOptimizationsTypesTable; + +MOZ_MUST_USE bool +WriteIonTrackedOptimizationsTable(JSContext* cx, CompactBufferWriter& writer, + const NativeToTrackedOptimizations* start, + const NativeToTrackedOptimizations* end, + const UniqueTrackedOptimizations& unique, + uint32_t* numRegions, uint32_t* regionTableOffsetp, + uint32_t* typesTableOffsetp, uint32_t* attemptsTableOffsetp, + IonTrackedTypeVector* allTypes); + +} // namespace jit +} // namespace js + +#endif // jit_OptimizationTracking_h |