/* -*- 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); }