diff options
Diffstat (limited to 'js/src/jit/OptimizationTracking.cpp')
| -rw-r--r-- | js/src/jit/OptimizationTracking.cpp | 1305 |
1 files changed, 1305 insertions, 0 deletions
diff --git a/js/src/jit/OptimizationTracking.cpp b/js/src/jit/OptimizationTracking.cpp new file mode 100644 index 000000000..308def041 --- /dev/null +++ b/js/src/jit/OptimizationTracking.cpp @@ -0,0 +1,1305 @@ +/* -*- 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/OptimizationTracking.h" + +#include "mozilla/SizePrintfMacros.h" + +#include "jsprf.h" + +#include "ds/Sort.h" +#include "jit/IonBuilder.h" +#include "jit/JitcodeMap.h" +#include "jit/JitSpewer.h" +#include "js/TrackedOptimizationInfo.h" + +#include "vm/ObjectGroup-inl.h" +#include "vm/TypeInference-inl.h" + +using namespace js; +using namespace js::jit; + +using mozilla::Maybe; +using mozilla::Some; +using mozilla::Nothing; + +using JS::TrackedStrategy; +using JS::TrackedOutcome; +using JS::TrackedTypeSite; +using JS::ForEachTrackedOptimizationAttemptOp; +using JS::ForEachTrackedOptimizationTypeInfoOp; + +bool +TrackedOptimizations::trackTypeInfo(OptimizationTypeInfo&& ty) +{ + return types_.append(mozilla::Move(ty)); +} + +bool +TrackedOptimizations::trackAttempt(TrackedStrategy strategy) +{ + OptimizationAttempt attempt(strategy, TrackedOutcome::GenericFailure); + currentAttempt_ = attempts_.length(); + return attempts_.append(attempt); +} + +void +TrackedOptimizations::amendAttempt(uint32_t index) +{ + currentAttempt_ = index; +} + +void +TrackedOptimizations::trackOutcome(TrackedOutcome outcome) +{ + attempts_[currentAttempt_].setOutcome(outcome); +} + +void +TrackedOptimizations::trackSuccess() +{ + attempts_[currentAttempt_].setOutcome(TrackedOutcome::GenericSuccess); +} + +template <class Vec> +static bool +VectorContentsMatch(const Vec* xs, const Vec* ys) +{ + if (xs->length() != ys->length()) + return false; + for (auto x = xs->begin(), y = ys->begin(); x != xs->end(); x++, y++) { + MOZ_ASSERT(y != ys->end()); + if (*x != *y) + return false; + } + return true; +} + +bool +TrackedOptimizations::matchTypes(const TempOptimizationTypeInfoVector& other) const +{ + return VectorContentsMatch(&types_, &other); +} + +bool +TrackedOptimizations::matchAttempts(const TempOptimizationAttemptsVector& other) const +{ + return VectorContentsMatch(&attempts_, &other); +} + +JS_PUBLIC_API(const char*) +JS::TrackedStrategyString(TrackedStrategy strategy) +{ + switch (strategy) { +#define STRATEGY_CASE(name) \ + case TrackedStrategy::name: \ + return #name; + TRACKED_STRATEGY_LIST(STRATEGY_CASE) +#undef STRATEGY_CASE + + default: + MOZ_CRASH("bad strategy"); + } +} + +JS_PUBLIC_API(const char*) +JS::TrackedOutcomeString(TrackedOutcome outcome) +{ + switch (outcome) { +#define OUTCOME_CASE(name) \ + case TrackedOutcome::name: \ + return #name; + TRACKED_OUTCOME_LIST(OUTCOME_CASE) +#undef OUTCOME_CASE + + default: + MOZ_CRASH("bad outcome"); + } +} + +JS_PUBLIC_API(const char*) +JS::TrackedTypeSiteString(TrackedTypeSite site) +{ + switch (site) { +#define TYPESITE_CASE(name) \ + case TrackedTypeSite::name: \ + return #name; + TRACKED_TYPESITE_LIST(TYPESITE_CASE) +#undef TYPESITE_CASE + + default: + MOZ_CRASH("bad type site"); + } +} + +void +SpewTempOptimizationTypeInfoVector(const TempOptimizationTypeInfoVector* types, + const char* indent = nullptr) +{ +#ifdef JS_JITSPEW + for (const OptimizationTypeInfo* t = types->begin(); t != types->end(); t++) { + JitSpewStart(JitSpew_OptimizationTracking, " %s%s of type %s, type set", + indent ? indent : "", + TrackedTypeSiteString(t->site()), StringFromMIRType(t->mirType())); + for (uint32_t i = 0; i < t->types().length(); i++) + JitSpewCont(JitSpew_OptimizationTracking, " %s", TypeSet::TypeString(t->types()[i])); + JitSpewFin(JitSpew_OptimizationTracking); + } +#endif +} + +void +SpewTempOptimizationAttemptsVector(const TempOptimizationAttemptsVector* attempts, + const char* indent = nullptr) +{ +#ifdef JS_JITSPEW + for (const OptimizationAttempt* a = attempts->begin(); a != attempts->end(); a++) { + JitSpew(JitSpew_OptimizationTracking, " %s%s: %s", indent ? indent : "", + TrackedStrategyString(a->strategy()), TrackedOutcomeString(a->outcome())); + } +#endif +} + +void +TrackedOptimizations::spew() const +{ +#ifdef JS_JITSPEW + SpewTempOptimizationTypeInfoVector(&types_); + SpewTempOptimizationAttemptsVector(&attempts_); +#endif +} + +bool +OptimizationTypeInfo::trackTypeSet(TemporaryTypeSet* typeSet) +{ + if (!typeSet) + return true; + return typeSet->enumerateTypes(&types_); +} + +bool +OptimizationTypeInfo::trackType(TypeSet::Type type) +{ + return types_.append(type); +} + +bool +OptimizationTypeInfo::operator ==(const OptimizationTypeInfo& other) const +{ + return site_ == other.site_ && mirType_ == other.mirType_ && + VectorContentsMatch(&types_, &other.types_); +} + +bool +OptimizationTypeInfo::operator !=(const OptimizationTypeInfo& other) const +{ + return !(*this == other); +} + +static inline HashNumber +CombineHash(HashNumber h, HashNumber n) +{ + h += n; + h += (h << 10); + h ^= (h >> 6); + return h; +} + +static inline HashNumber +HashType(TypeSet::Type ty) +{ + if (ty.isObjectUnchecked()) + return PointerHasher<TypeSet::ObjectKey*, 3>::hash(ty.objectKey()); + return HashNumber(ty.raw()); +} + +static HashNumber +HashTypeList(const TempTypeList& types) +{ + HashNumber h = 0; + for (uint32_t i = 0; i < types.length(); i++) + h = CombineHash(h, HashType(types[i])); + return h; +} + +HashNumber +OptimizationTypeInfo::hash() const +{ + return ((HashNumber(site_) << 24) + (HashNumber(mirType_) << 16)) ^ HashTypeList(types_); +} + +template <class Vec> +static HashNumber +HashVectorContents(const Vec* xs, HashNumber h) +{ + for (auto x = xs->begin(); x != xs->end(); x++) + h = CombineHash(h, x->hash()); + return h; +} + +/* static */ HashNumber +UniqueTrackedOptimizations::Key::hash(const Lookup& lookup) +{ + HashNumber h = HashVectorContents(lookup.types, 0); + h = HashVectorContents(lookup.attempts, h); + h += (h << 3); + h ^= (h >> 11); + h += (h << 15); + return h; +} + +/* static */ bool +UniqueTrackedOptimizations::Key::match(const Key& key, const Lookup& lookup) +{ + return VectorContentsMatch(key.attempts, lookup.attempts) && + VectorContentsMatch(key.types, lookup.types); +} + +bool +UniqueTrackedOptimizations::add(const TrackedOptimizations* optimizations) +{ + MOZ_ASSERT(!sorted()); + Key key; + key.types = &optimizations->types_; + key.attempts = &optimizations->attempts_; + AttemptsMap::AddPtr p = map_.lookupForAdd(key); + if (p) { + p->value().frequency++; + return true; + } + Entry entry; + entry.index = UINT8_MAX; + entry.frequency = 1; + return map_.add(p, key, entry); +} + +struct FrequencyComparator +{ + bool operator()(const UniqueTrackedOptimizations::SortEntry& a, + const UniqueTrackedOptimizations::SortEntry& b, + bool* lessOrEqualp) + { + *lessOrEqualp = b.frequency <= a.frequency; + return true; + } +}; + +bool +UniqueTrackedOptimizations::sortByFrequency(JSContext* cx) +{ + MOZ_ASSERT(!sorted()); + + JitSpew(JitSpew_OptimizationTracking, "=> Sorting unique optimizations by frequency"); + + // Sort by frequency. + Vector<SortEntry> entries(cx); + for (AttemptsMap::Range r = map_.all(); !r.empty(); r.popFront()) { + SortEntry entry; + entry.types = r.front().key().types; + entry.attempts = r.front().key().attempts; + entry.frequency = r.front().value().frequency; + if (!entries.append(entry)) + return false; + } + + // The compact table stores indices as a max of uint8_t. In practice each + // script has fewer unique optimization attempts than UINT8_MAX. + if (entries.length() >= UINT8_MAX - 1) + return false; + + Vector<SortEntry> scratch(cx); + if (!scratch.resize(entries.length())) + return false; + + FrequencyComparator comparator; + MOZ_ALWAYS_TRUE(MergeSort(entries.begin(), entries.length(), scratch.begin(), comparator)); + + // Update map entries' indices. + for (size_t i = 0; i < entries.length(); i++) { + Key key; + key.types = entries[i].types; + key.attempts = entries[i].attempts; + AttemptsMap::Ptr p = map_.lookup(key); + MOZ_ASSERT(p); + p->value().index = sorted_.length(); + + JitSpew(JitSpew_OptimizationTracking, " Entry %" PRIuSIZE " has frequency %" PRIu32, + sorted_.length(), p->value().frequency); + + if (!sorted_.append(entries[i])) + return false; + } + + return true; +} + +uint8_t +UniqueTrackedOptimizations::indexOf(const TrackedOptimizations* optimizations) const +{ + MOZ_ASSERT(sorted()); + Key key; + key.types = &optimizations->types_; + key.attempts = &optimizations->attempts_; + AttemptsMap::Ptr p = map_.lookup(key); + MOZ_ASSERT(p); + MOZ_ASSERT(p->value().index != UINT8_MAX); + return p->value().index; +} + +// Assigns each unique tracked type an index; outputs a compact list. +class jit::UniqueTrackedTypes +{ + public: + struct TypeHasher + { + typedef TypeSet::Type Lookup; + + static HashNumber hash(const Lookup& ty) { return HashType(ty); } + static bool match(const TypeSet::Type& ty1, const TypeSet::Type& ty2) { return ty1 == ty2; } + }; + + private: + // Map of unique TypeSet::Types to indices. + typedef HashMap<TypeSet::Type, uint8_t, TypeHasher> TypesMap; + TypesMap map_; + + Vector<TypeSet::Type, 1> list_; + + public: + explicit UniqueTrackedTypes(JSContext* cx) + : map_(cx), + list_(cx) + { } + + bool init() { return map_.init(); } + bool getIndexOf(JSContext* cx, TypeSet::Type ty, uint8_t* indexp); + + uint32_t count() const { MOZ_ASSERT(map_.count() == list_.length()); return list_.length(); } + bool enumerate(TypeSet::TypeList* types) const; +}; + +bool +UniqueTrackedTypes::getIndexOf(JSContext* cx, TypeSet::Type ty, uint8_t* indexp) +{ + TypesMap::AddPtr p = map_.lookupForAdd(ty); + if (p) { + *indexp = p->value(); + return true; + } + + // Store indices as max of uint8_t. In practice each script has fewer than + // UINT8_MAX of unique observed types. + if (count() >= UINT8_MAX) + return false; + + uint8_t index = (uint8_t) count(); + if (!map_.add(p, ty, index)) + return false; + if (!list_.append(ty)) + return false; + *indexp = index; + return true; +} + +bool +UniqueTrackedTypes::enumerate(TypeSet::TypeList* types) const +{ + return types->append(list_.begin(), list_.end()); +} + +void +IonTrackedOptimizationsRegion::unpackHeader() +{ + CompactBufferReader reader(start_, end_); + startOffset_ = reader.readUnsigned(); + endOffset_ = reader.readUnsigned(); + rangesStart_ = reader.currentPosition(); + MOZ_ASSERT(startOffset_ < endOffset_); +} + +void +IonTrackedOptimizationsRegion::RangeIterator::readNext(uint32_t* startOffset, uint32_t* endOffset, + uint8_t* index) +{ + MOZ_ASSERT(more()); + + CompactBufferReader reader(cur_, end_); + + // The very first entry isn't delta-encoded. + if (cur_ == start_) { + *startOffset = firstStartOffset_; + *endOffset = prevEndOffset_ = reader.readUnsigned(); + *index = reader.readByte(); + cur_ = reader.currentPosition(); + MOZ_ASSERT(cur_ <= end_); + return; + } + + // Otherwise, read a delta. + uint32_t startDelta, length; + ReadDelta(reader, &startDelta, &length, index); + *startOffset = prevEndOffset_ + startDelta; + *endOffset = prevEndOffset_ = *startOffset + length; + cur_ = reader.currentPosition(); + MOZ_ASSERT(cur_ <= end_); +} + +Maybe<uint8_t> +JitcodeGlobalEntry::IonEntry::trackedOptimizationIndexAtAddr(JSRuntime *rt, void* ptr, + uint32_t* entryOffsetOut) +{ + MOZ_ASSERT(hasTrackedOptimizations()); + MOZ_ASSERT(containsPointer(ptr)); + uint32_t ptrOffset = ((uint8_t*) ptr) - ((uint8_t*) nativeStartAddr()); + Maybe<IonTrackedOptimizationsRegion> region = optsRegionTable_->findRegion(ptrOffset); + if (region.isNothing()) + return Nothing(); + return region->findIndex(ptrOffset, entryOffsetOut); +} + +void +JitcodeGlobalEntry::IonEntry::forEachOptimizationAttempt(JSRuntime *rt, uint8_t index, + ForEachTrackedOptimizationAttemptOp& op) +{ + trackedOptimizationAttempts(index).forEach(op); +} + +void +JitcodeGlobalEntry::IonEntry::forEachOptimizationTypeInfo(JSRuntime *rt, uint8_t index, + IonTrackedOptimizationsTypeInfo::ForEachOpAdapter& op) +{ + trackedOptimizationTypeInfo(index).forEach(op, allTrackedTypes()); +} + +void +IonTrackedOptimizationsAttempts::forEach(ForEachTrackedOptimizationAttemptOp& op) +{ + CompactBufferReader reader(start_, end_); + const uint8_t* cur = start_; + while (cur != end_) { + TrackedStrategy strategy = TrackedStrategy(reader.readUnsigned()); + TrackedOutcome outcome = TrackedOutcome(reader.readUnsigned()); + MOZ_ASSERT(strategy < TrackedStrategy::Count); + MOZ_ASSERT(outcome < TrackedOutcome::Count); + op(strategy, outcome); + cur = reader.currentPosition(); + MOZ_ASSERT(cur <= end_); + } +} + +void +IonTrackedOptimizationsTypeInfo::forEach(ForEachOp& op, const IonTrackedTypeVector* allTypes) +{ + CompactBufferReader reader(start_, end_); + const uint8_t* cur = start_; + while (cur != end_) { + TrackedTypeSite site = JS::TrackedTypeSite(reader.readUnsigned()); + MOZ_ASSERT(site < JS::TrackedTypeSite::Count); + MIRType mirType = MIRType(reader.readUnsigned()); + uint32_t length = reader.readUnsigned(); + for (uint32_t i = 0; i < length; i++) + op.readType((*allTypes)[reader.readByte()]); + op(site, mirType); + cur = reader.currentPosition(); + MOZ_ASSERT(cur <= end_); + } +} + +Maybe<uint8_t> +IonTrackedOptimizationsRegion::findIndex(uint32_t offset, uint32_t* entryOffsetOut) const +{ + if (offset <= startOffset_ || offset > endOffset_) + return Nothing(); + + // Linear search through the run. + RangeIterator iter = ranges(); + while (iter.more()) { + uint32_t startOffset, endOffset; + uint8_t index; + iter.readNext(&startOffset, &endOffset, &index); + if (startOffset < offset && offset <= endOffset) { + *entryOffsetOut = endOffset; + return Some(index); + } + } + return Nothing(); +} + +Maybe<IonTrackedOptimizationsRegion> +IonTrackedOptimizationsRegionTable::findRegion(uint32_t offset) const +{ + // For two contiguous regions, e.g., [i, j] and [j, k], an offset exactly + // at j will be associated with [i, j] instead of [j, k]. An offset + // exactly at j is often a return address from a younger frame, which case + // the next region, despite starting at j, has not yet logically started + // execution. + + static const uint32_t LINEAR_SEARCH_THRESHOLD = 8; + uint32_t regions = numEntries(); + MOZ_ASSERT(regions > 0); + + // For small numbers of regions, do linear search. + if (regions <= LINEAR_SEARCH_THRESHOLD) { + for (uint32_t i = 0; i < regions; i++) { + IonTrackedOptimizationsRegion region = entry(i); + if (region.startOffset() < offset && offset <= region.endOffset()) { + return Some(entry(i)); + } + } + return Nothing(); + } + + // Otherwise, do binary search. + uint32_t i = 0; + while (regions > 1) { + uint32_t step = regions / 2; + uint32_t mid = i + step; + IonTrackedOptimizationsRegion region = entry(mid); + + if (offset <= region.startOffset()) { + // Entry is below mid. + regions = step; + } else if (offset > region.endOffset()) { + // Entry is above mid. + i = mid; + regions -= step; + } else { + // Entry is in mid. + return Some(entry(i)); + } + } + return Nothing(); +} + +/* static */ uint32_t +IonTrackedOptimizationsRegion::ExpectedRunLength(const NativeToTrackedOptimizations* start, + const NativeToTrackedOptimizations* end) +{ + MOZ_ASSERT(start < end); + + // A run always has at least 1 entry, which is not delta encoded. + uint32_t runLength = 1; + uint32_t prevEndOffset = start->endOffset.offset(); + + for (const NativeToTrackedOptimizations* entry = start + 1; entry != end; entry++) { + uint32_t startOffset = entry->startOffset.offset(); + uint32_t endOffset = entry->endOffset.offset(); + uint32_t startDelta = startOffset - prevEndOffset; + uint32_t length = endOffset - startOffset; + + if (!IsDeltaEncodeable(startDelta, length)) + break; + + runLength++; + if (runLength == MAX_RUN_LENGTH) + break; + + prevEndOffset = endOffset; + } + + return runLength; +} + +void +OptimizationAttempt::writeCompact(CompactBufferWriter& writer) const +{ + writer.writeUnsigned((uint32_t) strategy_); + writer.writeUnsigned((uint32_t) outcome_); +} + +bool +OptimizationTypeInfo::writeCompact(JSContext* cx, CompactBufferWriter& writer, + UniqueTrackedTypes& uniqueTypes) const +{ + writer.writeUnsigned((uint32_t) site_); + writer.writeUnsigned((uint32_t) mirType_); + writer.writeUnsigned(types_.length()); + for (uint32_t i = 0; i < types_.length(); i++) { + uint8_t index; + if (!uniqueTypes.getIndexOf(cx, types_[i], &index)) + return false; + writer.writeByte(index); + } + return true; +} + +/* static */ void +IonTrackedOptimizationsRegion::ReadDelta(CompactBufferReader& reader, + uint32_t* startDelta, uint32_t* length, + uint8_t* index) +{ + // 2 bytes + // SSSS-SSSL LLLL-LII0 + const uint32_t firstByte = reader.readByte(); + const uint32_t secondByte = reader.readByte(); + if ((firstByte & ENC1_MASK) == ENC1_MASK_VAL) { + uint32_t encVal = firstByte | secondByte << 8; + *startDelta = encVal >> ENC1_START_DELTA_SHIFT; + *length = (encVal >> ENC1_LENGTH_SHIFT) & ENC1_LENGTH_MAX; + *index = (encVal >> ENC1_INDEX_SHIFT) & ENC1_INDEX_MAX; + MOZ_ASSERT(length != 0); + return; + } + + // 3 bytes + // SSSS-SSSS SSSS-LLLL LLII-II01 + const uint32_t thirdByte = reader.readByte(); + if ((firstByte & ENC2_MASK) == ENC2_MASK_VAL) { + uint32_t encVal = firstByte | secondByte << 8 | thirdByte << 16; + *startDelta = encVal >> ENC2_START_DELTA_SHIFT; + *length = (encVal >> ENC2_LENGTH_SHIFT) & ENC2_LENGTH_MAX; + *index = (encVal >> ENC2_INDEX_SHIFT) & ENC2_INDEX_MAX; + MOZ_ASSERT(length != 0); + return; + } + + // 4 bytes + // SSSS-SSSS SSSL-LLLL LLLL-LIII IIII-I011 + const uint32_t fourthByte = reader.readByte(); + if ((firstByte & ENC3_MASK) == ENC3_MASK_VAL) { + uint32_t encVal = firstByte | secondByte << 8 | thirdByte << 16 | fourthByte << 24; + *startDelta = encVal >> ENC3_START_DELTA_SHIFT; + *length = (encVal >> ENC3_LENGTH_SHIFT) & ENC3_LENGTH_MAX; + *index = (encVal >> ENC3_INDEX_SHIFT) & ENC3_INDEX_MAX; + MOZ_ASSERT(length != 0); + return; + } + + // 5 bytes + // SSSS-SSSS SSSS-SSSL LLLL-LLLL LLLL-LIII IIII-I111 + MOZ_ASSERT((firstByte & ENC4_MASK) == ENC4_MASK_VAL); + uint64_t fifthByte = reader.readByte(); + uint64_t encVal = firstByte | secondByte << 8 | thirdByte << 16 | fourthByte << 24 | + fifthByte << 32; + *startDelta = encVal >> ENC4_START_DELTA_SHIFT; + *length = (encVal >> ENC4_LENGTH_SHIFT) & ENC4_LENGTH_MAX; + *index = (encVal >> ENC4_INDEX_SHIFT) & ENC4_INDEX_MAX; + MOZ_ASSERT(length != 0); +} + +/* static */ void +IonTrackedOptimizationsRegion::WriteDelta(CompactBufferWriter& writer, + uint32_t startDelta, uint32_t length, + uint8_t index) +{ + // 2 bytes + // SSSS-SSSL LLLL-LII0 + if (startDelta <= ENC1_START_DELTA_MAX && + length <= ENC1_LENGTH_MAX && + index <= ENC1_INDEX_MAX) + { + uint16_t val = ENC1_MASK_VAL | + (startDelta << ENC1_START_DELTA_SHIFT) | + (length << ENC1_LENGTH_SHIFT) | + (index << ENC1_INDEX_SHIFT); + writer.writeByte(val & 0xff); + writer.writeByte((val >> 8) & 0xff); + return; + } + + // 3 bytes + // SSSS-SSSS SSSS-LLLL LLII-II01 + if (startDelta <= ENC2_START_DELTA_MAX && + length <= ENC2_LENGTH_MAX && + index <= ENC2_INDEX_MAX) + { + uint32_t val = ENC2_MASK_VAL | + (startDelta << ENC2_START_DELTA_SHIFT) | + (length << ENC2_LENGTH_SHIFT) | + (index << ENC2_INDEX_SHIFT); + writer.writeByte(val & 0xff); + writer.writeByte((val >> 8) & 0xff); + writer.writeByte((val >> 16) & 0xff); + return; + } + + // 4 bytes + // SSSS-SSSS SSSL-LLLL LLLL-LIII IIII-I011 + if (startDelta <= ENC3_START_DELTA_MAX && + length <= ENC3_LENGTH_MAX) + { + // index always fits because it's an uint8_t; change this if + // ENC3_INDEX_MAX changes. + MOZ_ASSERT(ENC3_INDEX_MAX == UINT8_MAX); + uint32_t val = ENC3_MASK_VAL | + (startDelta << ENC3_START_DELTA_SHIFT) | + (length << ENC3_LENGTH_SHIFT) | + (index << ENC3_INDEX_SHIFT); + writer.writeByte(val & 0xff); + writer.writeByte((val >> 8) & 0xff); + writer.writeByte((val >> 16) & 0xff); + writer.writeByte((val >> 24) & 0xff); + return; + } + + // 5 bytes + // SSSS-SSSS SSSS-SSSL LLLL-LLLL LLLL-LIII IIII-I111 + if (startDelta <= ENC4_START_DELTA_MAX && + length <= ENC4_LENGTH_MAX) + { + // index always fits because it's an uint8_t; change this if + // ENC4_INDEX_MAX changes. + MOZ_ASSERT(ENC4_INDEX_MAX == UINT8_MAX); + uint64_t val = ENC4_MASK_VAL | + (((uint64_t) startDelta) << ENC4_START_DELTA_SHIFT) | + (((uint64_t) length) << ENC4_LENGTH_SHIFT) | + (((uint64_t) index) << ENC4_INDEX_SHIFT); + writer.writeByte(val & 0xff); + writer.writeByte((val >> 8) & 0xff); + writer.writeByte((val >> 16) & 0xff); + writer.writeByte((val >> 24) & 0xff); + writer.writeByte((val >> 32) & 0xff); + return; + } + + MOZ_CRASH("startDelta,length,index triple too large to encode."); +} + +/* static */ bool +IonTrackedOptimizationsRegion::WriteRun(CompactBufferWriter& writer, + const NativeToTrackedOptimizations* start, + const NativeToTrackedOptimizations* end, + const UniqueTrackedOptimizations& unique) +{ + // Write the header, which is the range that this whole run encompasses. + JitSpew(JitSpew_OptimizationTracking, " Header: [%" PRIuSIZE ", %" PRIuSIZE "]", + start->startOffset.offset(), (end - 1)->endOffset.offset()); + writer.writeUnsigned(start->startOffset.offset()); + writer.writeUnsigned((end - 1)->endOffset.offset()); + + // Write the first entry of the run, which is not delta-encoded. + JitSpew(JitSpew_OptimizationTracking, + " [%6" PRIuSIZE ", %6" PRIuSIZE "] vector %3u, offset %4" PRIuSIZE, + start->startOffset.offset(), start->endOffset.offset(), + unique.indexOf(start->optimizations), writer.length()); + uint32_t prevEndOffset = start->endOffset.offset(); + writer.writeUnsigned(prevEndOffset); + writer.writeByte(unique.indexOf(start->optimizations)); + + // Delta encode the run. + for (const NativeToTrackedOptimizations* entry = start + 1; entry != end; entry++) { + uint32_t startOffset = entry->startOffset.offset(); + uint32_t endOffset = entry->endOffset.offset(); + + uint32_t startDelta = startOffset - prevEndOffset; + uint32_t length = endOffset - startOffset; + uint8_t index = unique.indexOf(entry->optimizations); + + JitSpew(JitSpew_OptimizationTracking, + " [%6u, %6u] delta [+%5u, +%5u] vector %3u, offset %4" PRIuSIZE, + startOffset, endOffset, startDelta, length, index, writer.length()); + + WriteDelta(writer, startDelta, length, index); + + prevEndOffset = endOffset; + } + + if (writer.oom()) + return false; + + return true; +} + +static bool +WriteOffsetsTable(CompactBufferWriter& writer, const Vector<uint32_t, 16>& offsets, + uint32_t* tableOffsetp) +{ + // 4-byte align for the uint32s. + uint32_t padding = sizeof(uint32_t) - (writer.length() % sizeof(uint32_t)); + if (padding == sizeof(uint32_t)) + padding = 0; + JitSpew(JitSpew_OptimizationTracking, " Padding %u byte%s", + padding, padding == 1 ? "" : "s"); + for (uint32_t i = 0; i < padding; i++) + writer.writeByte(0); + + // Record the start of the table to compute reverse offsets for entries. + uint32_t tableOffset = writer.length(); + + // Write how many bytes were padded and numEntries. + writer.writeNativeEndianUint32_t(padding); + writer.writeNativeEndianUint32_t(offsets.length()); + + // Write entry offset table. + for (size_t i = 0; i < offsets.length(); i++) { + JitSpew(JitSpew_OptimizationTracking, " Entry %" PRIuSIZE " reverse offset %u", + i, tableOffset - padding - offsets[i]); + writer.writeNativeEndianUint32_t(tableOffset - padding - offsets[i]); + } + + if (writer.oom()) + return false; + + *tableOffsetp = tableOffset; + return true; +} + +static JSFunction* +MaybeConstructorFromType(TypeSet::Type ty) +{ + if (ty.isUnknown() || ty.isAnyObject() || !ty.isGroup()) + return nullptr; + ObjectGroup* obj = ty.group(); + TypeNewScript* newScript = obj->newScript(); + if (!newScript && obj->maybeUnboxedLayout()) + newScript = obj->unboxedLayout().newScript(); + return newScript ? newScript->function() : nullptr; +} + +static void +InterpretedFunctionFilenameAndLineNumber(JSFunction* fun, const char** filename, + Maybe<unsigned>* lineno) +{ + if (fun->hasScript()) { + *filename = fun->nonLazyScript()->maybeForwardedScriptSource()->filename(); + *lineno = Some((unsigned) fun->nonLazyScript()->lineno()); + } else if (fun->lazyScriptOrNull()) { + *filename = fun->lazyScript()->maybeForwardedScriptSource()->filename(); + *lineno = Some((unsigned) fun->lazyScript()->lineno()); + } else { + *filename = "(self-hosted builtin)"; + *lineno = Nothing(); + } +} + +static void +SpewConstructor(TypeSet::Type ty, JSFunction* constructor) +{ +#ifdef JS_JITSPEW + if (!constructor->isInterpreted()) { + JitSpew(JitSpew_OptimizationTracking, " Unique type %s has native constructor", + TypeSet::TypeString(ty)); + return; + } + + char buf[512]; + if (constructor->displayAtom()) + PutEscapedString(buf, 512, constructor->displayAtom(), 0); + else + snprintf(buf, mozilla::ArrayLength(buf), "??"); + + const char* filename; + Maybe<unsigned> lineno; + InterpretedFunctionFilenameAndLineNumber(constructor, &filename, &lineno); + + JitSpew(JitSpew_OptimizationTracking, " Unique type %s has constructor %s (%s:%u)", + TypeSet::TypeString(ty), buf, filename, lineno.isSome() ? *lineno : 0); +#endif +} + +static void +SpewAllocationSite(TypeSet::Type ty, JSScript* script, uint32_t offset) +{ +#ifdef JS_JITSPEW + JitSpew(JitSpew_OptimizationTracking, " Unique type %s has alloc site %s:%u", + TypeSet::TypeString(ty), script->filename(), + PCToLineNumber(script, script->offsetToPC(offset))); +#endif +} + +bool +jit::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* optimizationTableOffsetp, + IonTrackedTypeVector* allTypes) +{ + MOZ_ASSERT(unique.sorted()); + +#ifdef JS_JITSPEW + // Spew training data, which may be fed into a script to determine a good + // encoding strategy. + if (JitSpewEnabled(JitSpew_OptimizationTracking)) { + JitSpewStart(JitSpew_OptimizationTracking, "=> Training data: "); + for (const NativeToTrackedOptimizations* entry = start; entry != end; entry++) { + JitSpewCont(JitSpew_OptimizationTracking, "%" PRIuSIZE ",%" PRIuSIZE ",%u ", + entry->startOffset.offset(), entry->endOffset.offset(), + unique.indexOf(entry->optimizations)); + } + JitSpewFin(JitSpew_OptimizationTracking); + } +#endif + + Vector<uint32_t, 16> offsets(cx); + const NativeToTrackedOptimizations* entry = start; + + // Write out region offloads, partitioned into runs. + JitSpew(JitSpew_Profiling, "=> Writing regions"); + while (entry != end) { + uint32_t runLength = IonTrackedOptimizationsRegion::ExpectedRunLength(entry, end); + JitSpew(JitSpew_OptimizationTracking, + " Run at entry %" PRIuSIZE ", length %" PRIu32 ", offset %" PRIuSIZE, + size_t(entry - start), runLength, writer.length()); + + if (!offsets.append(writer.length())) + return false; + + if (!IonTrackedOptimizationsRegion::WriteRun(writer, entry, entry + runLength, unique)) + return false; + + entry += runLength; + } + + // Write out the table indexing into the payloads. 4-byte align for the uint32s. + if (!WriteOffsetsTable(writer, offsets, regionTableOffsetp)) + return false; + + *numRegions = offsets.length(); + + // Clear offsets so that it may be reused below for the unique + // optimizations table. + offsets.clear(); + + const UniqueTrackedOptimizations::SortedVector& vec = unique.sortedVector(); + JitSpew(JitSpew_OptimizationTracking, "=> Writing unique optimizations table with %" PRIuSIZE " entr%s", + vec.length(), vec.length() == 1 ? "y" : "ies"); + + // Write out type info payloads. + UniqueTrackedTypes uniqueTypes(cx); + if (!uniqueTypes.init()) + return false; + + for (const UniqueTrackedOptimizations::SortEntry* p = vec.begin(); p != vec.end(); p++) { + const TempOptimizationTypeInfoVector* v = p->types; + JitSpew(JitSpew_OptimizationTracking, + " Type info entry %" PRIuSIZE " of length %" PRIuSIZE ", offset %" PRIuSIZE, + size_t(p - vec.begin()), v->length(), writer.length()); + SpewTempOptimizationTypeInfoVector(v, " "); + + if (!offsets.append(writer.length())) + return false; + + for (const OptimizationTypeInfo* t = v->begin(); t != v->end(); t++) { + if (!t->writeCompact(cx, writer, uniqueTypes)) + return false; + } + } + + // Enumerate the unique types, and pull out any 'new' script constructor + // functions and allocation site information. We do this during linking + // instead of during profiling to avoid touching compartment tables during + // profiling. Additionally, TypeNewScript is subject to GC in the + // meantime. + TypeSet::TypeList uniqueTypeList; + if (!uniqueTypes.enumerate(&uniqueTypeList)) + return false; + for (uint32_t i = 0; i < uniqueTypeList.length(); i++) { + TypeSet::Type ty = uniqueTypeList[i]; + if (JSFunction* constructor = MaybeConstructorFromType(ty)) { + if (!allTypes->append(IonTrackedTypeWithAddendum(ty, constructor))) + return false; + SpewConstructor(ty, constructor); + } else { + JSScript* script; + uint32_t offset; + if (!ty.isUnknown() && !ty.isAnyObject() && ty.isGroup() && + ObjectGroup::findAllocationSite(cx, ty.group(), &script, &offset)) + { + if (!allTypes->append(IonTrackedTypeWithAddendum(ty, script, offset))) + return false; + SpewAllocationSite(ty, script, offset); + } else { + if (!allTypes->append(IonTrackedTypeWithAddendum(ty))) + return false; + } + } + } + + if (!WriteOffsetsTable(writer, offsets, typesTableOffsetp)) + return false; + offsets.clear(); + + // Write out attempts payloads. + for (const UniqueTrackedOptimizations::SortEntry* p = vec.begin(); p != vec.end(); p++) { + const TempOptimizationAttemptsVector* v = p->attempts; + JitSpew(JitSpew_OptimizationTracking, + " Attempts entry %" PRIuSIZE " of length %" PRIuSIZE ", offset %" PRIuSIZE, + size_t(p - vec.begin()), v->length(), writer.length()); + SpewTempOptimizationAttemptsVector(v, " "); + + if (!offsets.append(writer.length())) + return false; + + for (const OptimizationAttempt* a = v->begin(); a != v->end(); a++) + a->writeCompact(writer); + } + + return WriteOffsetsTable(writer, offsets, optimizationTableOffsetp); +} + + +BytecodeSite* +IonBuilder::maybeTrackedOptimizationSite(jsbytecode* pc) +{ + // BytecodeSites that track optimizations need to be 1-1 with the pc + // when optimization tracking is enabled, so that all MIR generated by + // a single pc are tracked at one place, even across basic blocks. + // + // Alternatively, we could make all BytecodeSites 1-1 with the pc, but + // there is no real need as optimization tracking is a toggled + // feature. + // + // Since sites that track optimizations should be sparse, just do a + // reverse linear search, as we're most likely advancing in pc. + MOZ_ASSERT(isOptimizationTrackingEnabled()); + for (size_t i = trackedOptimizationSites_.length(); i != 0; i--) { + BytecodeSite* site = trackedOptimizationSites_[i - 1]; + if (site->pc() == pc) { + MOZ_ASSERT(site->tree() == info().inlineScriptTree()); + return site; + } + } + return nullptr; +} + +void +IonBuilder::startTrackingOptimizations() +{ + if (isOptimizationTrackingEnabled()) { + BytecodeSite* site = maybeTrackedOptimizationSite(current->trackedSite()->pc()); + + if (!site) { + site = current->trackedSite(); + site->setOptimizations(new(alloc()) TrackedOptimizations(alloc())); + // OOMs are handled as if optimization tracking were turned off. + if (!trackedOptimizationSites_.append(site)) + site = nullptr; + } else if (site->hasOptimizations()) { + // The same bytecode may be visited multiple times (see + // restartLoop). Only the last time matters, so clear any previous + // tracked optimizations. + site->optimizations()->clear(); + } + + // The case of !site->hasOptimizations() means we had an OOM when + // previously attempting to track optimizations. Leave + // site->optimizations_ nullptr to leave optimization tracking off. + + if (site) + current->updateTrackedSite(site); + } +} + +void +IonBuilder::trackTypeInfoUnchecked(TrackedTypeSite kind, MIRType mirType, + TemporaryTypeSet* typeSet) +{ + BytecodeSite* site = current->trackedSite(); + // OOMs are handled as if optimization tracking were turned off. + OptimizationTypeInfo typeInfo(alloc(), kind, mirType); + if (!typeInfo.trackTypeSet(typeSet)) { + site->setOptimizations(nullptr); + return; + } + if (!site->optimizations()->trackTypeInfo(mozilla::Move(typeInfo))) + site->setOptimizations(nullptr); +} + +void +IonBuilder::trackTypeInfoUnchecked(TrackedTypeSite kind, JSObject* obj) +{ + BytecodeSite* site = current->trackedSite(); + // OOMs are handled as if optimization tracking were turned off. + OptimizationTypeInfo typeInfo(alloc(), kind, MIRType::Object); + if (!typeInfo.trackType(TypeSet::ObjectType(obj))) + return; + if (!site->optimizations()->trackTypeInfo(mozilla::Move(typeInfo))) + site->setOptimizations(nullptr); +} + +void +IonBuilder::trackTypeInfoUnchecked(CallInfo& callInfo) +{ + MDefinition* thisArg = callInfo.thisArg(); + trackTypeInfoUnchecked(TrackedTypeSite::Call_This, thisArg->type(), thisArg->resultTypeSet()); + + for (uint32_t i = 0; i < callInfo.argc(); i++) { + MDefinition* arg = callInfo.getArg(i); + trackTypeInfoUnchecked(TrackedTypeSite::Call_Arg, arg->type(), arg->resultTypeSet()); + } + + TemporaryTypeSet* returnTypes = getInlineReturnTypeSet(); + trackTypeInfoUnchecked(TrackedTypeSite::Call_Return, returnTypes->getKnownMIRType(), + returnTypes); +} + +void +IonBuilder::trackOptimizationAttemptUnchecked(TrackedStrategy strategy) +{ + BytecodeSite* site = current->trackedSite(); + // OOMs are handled as if optimization tracking were turned off. + if (!site->optimizations()->trackAttempt(strategy)) + site->setOptimizations(nullptr); +} + +void +IonBuilder::amendOptimizationAttemptUnchecked(uint32_t index) +{ + const BytecodeSite* site = current->trackedSite(); + site->optimizations()->amendAttempt(index); +} + +void +IonBuilder::trackOptimizationOutcomeUnchecked(TrackedOutcome outcome) +{ + const BytecodeSite* site = current->trackedSite(); + site->optimizations()->trackOutcome(outcome); +} + +void +IonBuilder::trackOptimizationSuccessUnchecked() +{ + const BytecodeSite* site = current->trackedSite(); + site->optimizations()->trackSuccess(); +} + +void +IonBuilder::trackInlineSuccessUnchecked(InliningStatus status) +{ + if (status == InliningStatus_Inlined) + trackOptimizationOutcome(TrackedOutcome::Inlined); +} + +static JSFunction* +FunctionFromTrackedType(const IonTrackedTypeWithAddendum& tracked) +{ + if (tracked.hasConstructor()) + return tracked.constructor; + + TypeSet::Type ty = tracked.type; + + if (ty.isSingleton()) { + JSObject* obj = ty.singleton(); + return obj->is<JSFunction>() ? &obj->as<JSFunction>() : nullptr; + } + + return ty.group()->maybeInterpretedFunction(); +} + +void +IonTrackedOptimizationsTypeInfo::ForEachOpAdapter::readType(const IonTrackedTypeWithAddendum& tracked) +{ + TypeSet::Type ty = tracked.type; + + if (ty.isPrimitive() || ty.isUnknown() || ty.isAnyObject()) { + op_.readType("primitive", TypeSet::NonObjectTypeString(ty), nullptr, Nothing()); + return; + } + + char buf[512]; + const uint32_t bufsize = mozilla::ArrayLength(buf); + + if (JSFunction* fun = FunctionFromTrackedType(tracked)) { + // The displayAtom is useful for identifying both native and + // interpreted functions. + char* name = nullptr; + if (fun->displayAtom()) { + PutEscapedString(buf, bufsize, fun->displayAtom(), 0); + name = buf; + } + + if (fun->isNative()) { + // + // Try printing out the displayAtom of the native function and the + // absolute address of the native function pointer. + // + // Note that this address is not usable without knowing the + // starting address at which our shared library is loaded. Shared + // library information is exposed by the profiler. If this address + // needs to be symbolicated manually (e.g., when it is gotten via + // debug spewing of all optimization information), it needs to be + // converted to an offset from the beginning of the shared library + // for use with utilities like `addr2line` on Linux and `atos` on + // OS X. Converting to an offset may be done via dladdr(): + // + // void* addr = JS_FUNC_TO_DATA_PTR(void*, fun->native()); + // uintptr_t offset; + // Dl_info info; + // if (dladdr(addr, &info) != 0) + // offset = uintptr_t(addr) - uintptr_t(info.dli_fbase); + // + char locationBuf[20]; + if (!name) { + uintptr_t addr = JS_FUNC_TO_DATA_PTR(uintptr_t, fun->native()); + snprintf(locationBuf, mozilla::ArrayLength(locationBuf), "%" PRIxPTR, addr); + } + op_.readType("native", name, name ? nullptr : locationBuf, Nothing()); + return; + } + + const char* filename; + Maybe<unsigned> lineno; + InterpretedFunctionFilenameAndLineNumber(fun, &filename, &lineno); + op_.readType(tracked.constructor ? "constructor" : "function", + name, filename, lineno); + return; + } + + const char* className = ty.objectKey()->clasp()->name; + snprintf(buf, bufsize, "[object %s]", className); + + if (tracked.hasAllocationSite()) { + JSScript* script = tracked.script; + op_.readType("alloc site", buf, + script->maybeForwardedScriptSource()->filename(), + Some(PCToLineNumber(script, script->offsetToPC(tracked.offset)))); + return; + } + + if (ty.isGroup()) { + op_.readType("prototype", buf, nullptr, Nothing()); + return; + } + + op_.readType("singleton", buf, nullptr, Nothing()); +} + +void +IonTrackedOptimizationsTypeInfo::ForEachOpAdapter::operator()(JS::TrackedTypeSite site, + MIRType mirType) +{ + op_(site, StringFromMIRType(mirType)); +} + +typedef JS::ForEachProfiledFrameOp::FrameHandle FrameHandle; + +void +FrameHandle::updateHasTrackedOptimizations() +{ + // All inlined frames will have the same optimization information by + // virtue of sharing the JitcodeGlobalEntry, but such information is + // only interpretable on the youngest frame. + if (depth() != 0) + return; + if (!entry_.hasTrackedOptimizations()) + return; + + uint32_t entryOffset; + optsIndex_ = entry_.trackedOptimizationIndexAtAddr(rt_, addr_, &entryOffset); + if (optsIndex_.isSome()) + canonicalAddr_ = (void*)(((uint8_t*) entry_.nativeStartAddr()) + entryOffset); +} + +JS_PUBLIC_API(void) +FrameHandle::forEachOptimizationAttempt(ForEachTrackedOptimizationAttemptOp& op, + JSScript** scriptOut, jsbytecode** pcOut) const +{ + MOZ_ASSERT(optsIndex_.isSome()); + entry_.forEachOptimizationAttempt(rt_, *optsIndex_, op); + entry_.youngestFrameLocationAtAddr(rt_, addr_, scriptOut, pcOut); +} + +JS_PUBLIC_API(void) +FrameHandle::forEachOptimizationTypeInfo(ForEachTrackedOptimizationTypeInfoOp& op) const +{ + MOZ_ASSERT(optsIndex_.isSome()); + IonTrackedOptimizationsTypeInfo::ForEachOpAdapter adapter(op); + entry_.forEachOptimizationTypeInfo(rt_, *optsIndex_, adapter); +} |