Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef jit_OptimizationTracking_h
8 : #define jit_OptimizationTracking_h
9 :
10 : #include "mozilla/Maybe.h"
11 :
12 : #include "jit/CompactBuffer.h"
13 : #include "jit/CompileInfo.h"
14 : #include "jit/JitAllocPolicy.h"
15 : #include "jit/JitSpewer.h"
16 : #include "js/TrackedOptimizationInfo.h"
17 : #include "vm/TypeInference.h"
18 :
19 : namespace js {
20 :
21 : namespace jit {
22 :
23 : struct NativeToTrackedOptimizations;
24 :
25 : class OptimizationAttempt
26 : {
27 : JS::TrackedStrategy strategy_;
28 : JS::TrackedOutcome outcome_;
29 :
30 : public:
31 0 : OptimizationAttempt(JS::TrackedStrategy strategy, JS::TrackedOutcome outcome)
32 0 : : strategy_(strategy),
33 0 : outcome_(outcome)
34 0 : { }
35 :
36 0 : void setOutcome(JS::TrackedOutcome outcome) { outcome_ = outcome; }
37 : bool succeeded() const { return outcome_ >= JS::TrackedOutcome::GenericSuccess; }
38 : bool failed() const { return outcome_ < JS::TrackedOutcome::GenericSuccess; }
39 0 : JS::TrackedStrategy strategy() const { return strategy_; }
40 0 : JS::TrackedOutcome outcome() const { return outcome_; }
41 :
42 : bool operator ==(const OptimizationAttempt& other) const {
43 : return strategy_ == other.strategy_ && outcome_ == other.outcome_;
44 : }
45 0 : bool operator !=(const OptimizationAttempt& other) const {
46 0 : return strategy_ != other.strategy_ || outcome_ != other.outcome_;
47 : }
48 0 : HashNumber hash() const {
49 0 : return (HashNumber(strategy_) << 8) + HashNumber(outcome_);
50 : }
51 :
52 : void writeCompact(CompactBufferWriter& writer) const;
53 : };
54 :
55 : typedef Vector<OptimizationAttempt, 4, JitAllocPolicy> TempOptimizationAttemptsVector;
56 : typedef Vector<TypeSet::Type, 1, JitAllocPolicy> TempTypeList;
57 :
58 : class UniqueTrackedTypes;
59 :
60 0 : class OptimizationTypeInfo
61 : {
62 : JS::TrackedTypeSite site_;
63 : MIRType mirType_;
64 : TempTypeList types_;
65 :
66 : public:
67 0 : OptimizationTypeInfo(OptimizationTypeInfo&& other)
68 0 : : site_(other.site_),
69 0 : mirType_(other.mirType_),
70 0 : types_(mozilla::Move(other.types_))
71 0 : { }
72 :
73 0 : OptimizationTypeInfo(TempAllocator& alloc, JS::TrackedTypeSite site, MIRType mirType)
74 0 : : site_(site),
75 : mirType_(mirType),
76 0 : types_(alloc)
77 0 : { }
78 :
79 : MOZ_MUST_USE bool trackTypeSet(TemporaryTypeSet* typeSet);
80 : MOZ_MUST_USE bool trackType(TypeSet::Type type);
81 :
82 0 : JS::TrackedTypeSite site() const { return site_; }
83 0 : MIRType mirType() const { return mirType_; }
84 0 : const TempTypeList& types() const { return types_; }
85 :
86 : bool operator ==(const OptimizationTypeInfo& other) const;
87 : bool operator !=(const OptimizationTypeInfo& other) const;
88 :
89 : HashNumber hash() const;
90 :
91 : MOZ_MUST_USE bool writeCompact(JSContext* cx, CompactBufferWriter& writer,
92 : UniqueTrackedTypes& uniqueTypes) const;
93 : };
94 :
95 : typedef Vector<OptimizationTypeInfo, 1, JitAllocPolicy> TempOptimizationTypeInfoVector;
96 :
97 : // Tracks the optimization attempts made at a bytecode location.
98 : class TrackedOptimizations : public TempObject
99 : {
100 : friend class UniqueTrackedOptimizations;
101 : TempOptimizationTypeInfoVector types_;
102 : TempOptimizationAttemptsVector attempts_;
103 : uint32_t currentAttempt_;
104 :
105 : public:
106 0 : explicit TrackedOptimizations(TempAllocator& alloc)
107 0 : : types_(alloc),
108 : attempts_(alloc),
109 0 : currentAttempt_(UINT32_MAX)
110 0 : { }
111 :
112 0 : void clear() {
113 0 : types_.clear();
114 0 : attempts_.clear();
115 0 : currentAttempt_ = UINT32_MAX;
116 0 : }
117 :
118 : MOZ_MUST_USE bool trackTypeInfo(OptimizationTypeInfo&& ty);
119 :
120 : MOZ_MUST_USE bool trackAttempt(JS::TrackedStrategy strategy);
121 : void amendAttempt(uint32_t index);
122 : void trackOutcome(JS::TrackedOutcome outcome);
123 : void trackSuccess();
124 :
125 : bool matchTypes(const TempOptimizationTypeInfoVector& other) const;
126 : bool matchAttempts(const TempOptimizationAttemptsVector& other) const;
127 :
128 : void spew(JitSpewChannel channel) const;
129 : };
130 :
131 : // Assigns each unique sequence of optimization attempts an index; outputs a
132 : // compact table.
133 0 : class UniqueTrackedOptimizations
134 : {
135 : public:
136 : struct SortEntry
137 : {
138 : const TempOptimizationTypeInfoVector* types;
139 : const TempOptimizationAttemptsVector* attempts;
140 : uint32_t frequency;
141 : };
142 : typedef Vector<SortEntry, 4> SortedVector;
143 :
144 : private:
145 : struct Key
146 : {
147 : const TempOptimizationTypeInfoVector* types;
148 : const TempOptimizationAttemptsVector* attempts;
149 :
150 : typedef Key Lookup;
151 : static HashNumber hash(const Lookup& lookup);
152 : static bool match(const Key& key, const Lookup& lookup);
153 : static void rekey(Key& key, const Key& newKey) {
154 : key = newKey;
155 : }
156 : };
157 :
158 : struct Entry
159 : {
160 : uint8_t index;
161 : uint32_t frequency;
162 : };
163 :
164 : // Map of unique (TempOptimizationTypeInfoVector,
165 : // TempOptimizationAttemptsVector) pairs to indices.
166 : typedef HashMap<Key, Entry, Key> AttemptsMap;
167 : AttemptsMap map_;
168 :
169 : // TempOptimizationAttemptsVectors sorted by frequency.
170 : SortedVector sorted_;
171 :
172 : public:
173 0 : explicit UniqueTrackedOptimizations(JSContext* cx)
174 0 : : map_(cx),
175 0 : sorted_(cx)
176 0 : { }
177 :
178 0 : MOZ_MUST_USE bool init() { return map_.init(); }
179 : MOZ_MUST_USE bool add(const TrackedOptimizations* optimizations);
180 :
181 : MOZ_MUST_USE bool sortByFrequency(JSContext* cx);
182 0 : bool sorted() const { return !sorted_.empty(); }
183 0 : uint32_t count() const { MOZ_ASSERT(sorted()); return sorted_.length(); }
184 0 : const SortedVector& sortedVector() const { MOZ_ASSERT(sorted()); return sorted_; }
185 : uint8_t indexOf(const TrackedOptimizations* optimizations) const;
186 : };
187 :
188 : // A compact table of tracked optimization information. Pictorially,
189 : //
190 : // +------------------------------------------------+
191 : // | Region 1 | |
192 : // |------------------------------------------------| |
193 : // | Region 2 | |
194 : // |------------------------------------------------| |-- PayloadR of list-of-list of
195 : // | ... | | range triples (see below)
196 : // |------------------------------------------------| |
197 : // | Region M | |
198 : // +================================================+ <- IonTrackedOptimizationsRegionTable
199 : // | uint32_t numRegions_ = M | |
200 : // +------------------------------------------------+ |
201 : // | Region 1 | |
202 : // | uint32_t regionOffset = size(PayloadR) | |
203 : // +------------------------------------------------+ |-- Table
204 : // | ... | |
205 : // +------------------------------------------------+ |
206 : // | Region M | |
207 : // | uint32_t regionOffset | |
208 : // +================================================+
209 : // | Optimization type info 1 | |
210 : // |------------------------------------------------| |
211 : // | Optimization type info 2 | |-- PayloadT of list of
212 : // |------------------------------------------------| | OptimizationTypeInfo in
213 : // | ... | | order of decreasing frequency
214 : // |------------------------------------------------| |
215 : // | Optimization type info N | |
216 : // +================================================+ <- IonTrackedOptimizationsTypesTable
217 : // | uint32_t numEntries_ = N | |
218 : // +------------------------------------------------+ |
219 : // | Optimization type info 1 | |
220 : // | uint32_t entryOffset = size(PayloadT) | |
221 : // +------------------------------------------------+ |-- Table
222 : // | ... | |
223 : // +------------------------------------------------+ |
224 : // | Optimization type info N | |
225 : // | uint32_t entryOffset | |
226 : // +================================================+
227 : // | Optimization attempts 1 | |
228 : // |------------------------------------------------| |
229 : // | Optimization attempts 2 | |-- PayloadA of list of
230 : // |------------------------------------------------| | OptimizationAttempts in
231 : // | ... | | order of decreasing frequency
232 : // |------------------------------------------------| |
233 : // | Optimization attempts N | |
234 : // +================================================+ <- IonTrackedOptimizationsAttemptsTable
235 : // | uint32_t numEntries_ = N | |
236 : // +------------------------------------------------+ |
237 : // | Optimization attempts 1 | |
238 : // | uint32_t entryOffset = size(PayloadA) | |
239 : // +------------------------------------------------+ |-- Table
240 : // | ... | |
241 : // +------------------------------------------------+ |
242 : // | Optimization attempts N | |
243 : // | uint32_t entryOffset | |
244 : // +------------------------------------------------+
245 : //
246 : // Abstractly, each region in the PayloadR section is a list of triples of the
247 : // following, in order of ascending startOffset:
248 : //
249 : // (startOffset, endOffset, optimization attempts index)
250 : //
251 : // The range of [startOffset, endOffset) is the native machine code offsets
252 : // for which the optimization attempts referred to by the index applies.
253 : //
254 : // Concretely, each region starts with a header of:
255 : //
256 : // { startOffset : 32, endOffset : 32 }
257 : //
258 : // followed by an (endOffset, index) pair, then by delta-encoded variants
259 : // triples described below.
260 : //
261 : // Each list of type infos in the PayloadT section is a list of triples:
262 : //
263 : // (kind, MIR type, type set)
264 : //
265 : // The type set is separately in another vector, and what is encoded instead
266 : // is the (offset, length) pair needed to index into that vector.
267 : //
268 : // Each list of optimization attempts in the PayloadA section is a list of
269 : // pairs:
270 : //
271 : // (strategy, outcome)
272 : //
273 : // Both tail tables for PayloadR and PayloadA use reverse offsets from the
274 : // table pointers.
275 :
276 : class IonTrackedOptimizationsRegion
277 : {
278 : const uint8_t* start_;
279 : const uint8_t* end_;
280 :
281 : // Unpacked state.
282 : uint32_t startOffset_;
283 : uint32_t endOffset_;
284 : const uint8_t* rangesStart_;
285 :
286 : void unpackHeader();
287 :
288 : public:
289 0 : IonTrackedOptimizationsRegion(const uint8_t* start, const uint8_t* end)
290 0 : : start_(start), end_(end),
291 0 : startOffset_(0), endOffset_(0), rangesStart_(nullptr)
292 : {
293 0 : MOZ_ASSERT(start < end);
294 0 : unpackHeader();
295 0 : }
296 :
297 : // Offsets for the entire range that this region covers.
298 : //
299 : // This, as well as the offsets for the deltas, is open at the ending
300 : // address: [startOffset, endOffset).
301 0 : uint32_t startOffset() const { return startOffset_; }
302 0 : uint32_t endOffset() const { return endOffset_; }
303 :
304 : class RangeIterator
305 : {
306 : const uint8_t* cur_;
307 : const uint8_t* start_;
308 : const uint8_t* end_;
309 :
310 : uint32_t firstStartOffset_;
311 : uint32_t prevEndOffset_;
312 :
313 : public:
314 0 : RangeIterator(const uint8_t* start, const uint8_t* end, uint32_t startOffset)
315 0 : : cur_(start), start_(start), end_(end),
316 0 : firstStartOffset_(startOffset), prevEndOffset_(0)
317 0 : { }
318 :
319 0 : bool more() const { return cur_ < end_; }
320 : void readNext(uint32_t* startOffset, uint32_t* endOffset, uint8_t* index);
321 : };
322 :
323 0 : RangeIterator ranges() const { return RangeIterator(rangesStart_, end_, startOffset_); }
324 :
325 : // Find the index of tracked optimization info (e.g., type info and
326 : // attempts) at a native code offset.
327 : mozilla::Maybe<uint8_t> findIndex(uint32_t offset, uint32_t* entryOffsetOut) const;
328 :
329 : // For the variants below, S stands for startDelta, L for length, and I
330 : // for index. These were automatically generated from training on the
331 : // Octane benchmark.
332 : //
333 : // byte 1 byte 0
334 : // SSSS-SSSL LLLL-LII0
335 : // startDelta max 127, length max 63, index max 3
336 :
337 : static const uint32_t ENC1_MASK = 0x1;
338 : static const uint32_t ENC1_MASK_VAL = 0x0;
339 :
340 : static const uint32_t ENC1_START_DELTA_MAX = 0x7f;
341 : static const uint32_t ENC1_START_DELTA_SHIFT = 9;
342 :
343 : static const uint32_t ENC1_LENGTH_MAX = 0x3f;
344 : static const uint32_t ENC1_LENGTH_SHIFT = 3;
345 :
346 : static const uint32_t ENC1_INDEX_MAX = 0x3;
347 : static const uint32_t ENC1_INDEX_SHIFT = 1;
348 :
349 : // byte 2 byte 1 byte 0
350 : // SSSS-SSSS SSSS-LLLL LLII-II01
351 : // startDelta max 4095, length max 63, index max 15
352 :
353 : static const uint32_t ENC2_MASK = 0x3;
354 : static const uint32_t ENC2_MASK_VAL = 0x1;
355 :
356 : static const uint32_t ENC2_START_DELTA_MAX = 0xfff;
357 : static const uint32_t ENC2_START_DELTA_SHIFT = 12;
358 :
359 : static const uint32_t ENC2_LENGTH_MAX = 0x3f;
360 : static const uint32_t ENC2_LENGTH_SHIFT = 6;
361 :
362 : static const uint32_t ENC2_INDEX_MAX = 0xf;
363 : static const uint32_t ENC2_INDEX_SHIFT = 2;
364 :
365 : // byte 3 byte 2 byte 1 byte 0
366 : // SSSS-SSSS SSSL-LLLL LLLL-LIII IIII-I011
367 : // startDelta max 2047, length max 1023, index max 255
368 :
369 : static const uint32_t ENC3_MASK = 0x7;
370 : static const uint32_t ENC3_MASK_VAL = 0x3;
371 :
372 : static const uint32_t ENC3_START_DELTA_MAX = 0x7ff;
373 : static const uint32_t ENC3_START_DELTA_SHIFT = 21;
374 :
375 : static const uint32_t ENC3_LENGTH_MAX = 0x3ff;
376 : static const uint32_t ENC3_LENGTH_SHIFT = 11;
377 :
378 : static const uint32_t ENC3_INDEX_MAX = 0xff;
379 : static const uint32_t ENC3_INDEX_SHIFT = 3;
380 :
381 : // byte 4 byte 3 byte 2 byte 1 byte 0
382 : // SSSS-SSSS SSSS-SSSL LLLL-LLLL LLLL-LIII IIII-I111
383 : // startDelta max 32767, length max 16383, index max 255
384 :
385 : static const uint32_t ENC4_MASK = 0x7;
386 : static const uint32_t ENC4_MASK_VAL = 0x7;
387 :
388 : static const uint32_t ENC4_START_DELTA_MAX = 0x7fff;
389 : static const uint32_t ENC4_START_DELTA_SHIFT = 25;
390 :
391 : static const uint32_t ENC4_LENGTH_MAX = 0x3fff;
392 : static const uint32_t ENC4_LENGTH_SHIFT = 11;
393 :
394 : static const uint32_t ENC4_INDEX_MAX = 0xff;
395 : static const uint32_t ENC4_INDEX_SHIFT = 3;
396 :
397 0 : static bool IsDeltaEncodeable(uint32_t startDelta, uint32_t length) {
398 0 : MOZ_ASSERT(length != 0);
399 0 : return startDelta <= ENC4_START_DELTA_MAX && length <= ENC4_LENGTH_MAX;
400 : }
401 :
402 : static const uint32_t MAX_RUN_LENGTH = 100;
403 :
404 : static uint32_t ExpectedRunLength(const NativeToTrackedOptimizations* start,
405 : const NativeToTrackedOptimizations* end);
406 :
407 : static void ReadDelta(CompactBufferReader& reader, uint32_t* startDelta, uint32_t* length,
408 : uint8_t* index);
409 : static void WriteDelta(CompactBufferWriter& writer, uint32_t startDelta, uint32_t length,
410 : uint8_t index);
411 : static MOZ_MUST_USE bool WriteRun(CompactBufferWriter& writer,
412 : const NativeToTrackedOptimizations* start,
413 : const NativeToTrackedOptimizations* end,
414 : const UniqueTrackedOptimizations& unique);
415 : };
416 :
417 : class IonTrackedOptimizationsAttempts
418 : {
419 : const uint8_t* start_;
420 : const uint8_t* end_;
421 :
422 : public:
423 0 : IonTrackedOptimizationsAttempts(const uint8_t* start, const uint8_t* end)
424 0 : : start_(start), end_(end)
425 : {
426 : // Cannot be empty.
427 0 : MOZ_ASSERT(start < end);
428 0 : }
429 :
430 : void forEach(JS::ForEachTrackedOptimizationAttemptOp& op);
431 : };
432 :
433 : struct IonTrackedTypeWithAddendum
434 : {
435 : TypeSet::Type type;
436 :
437 : enum HasAddendum {
438 : HasNothing,
439 : HasAllocationSite,
440 : HasConstructor
441 : };
442 : HasAddendum hasAddendum;
443 :
444 : // If type is a type object and is tied to a site, the script and pc are
445 : // resolved early and stored below. This is done to avoid accessing the
446 : // compartment during profiling time.
447 : union {
448 : struct {
449 : JSScript* script;
450 : uint32_t offset;
451 : };
452 : JSFunction* constructor;
453 : };
454 :
455 0 : explicit IonTrackedTypeWithAddendum(TypeSet::Type type)
456 0 : : type(type),
457 0 : hasAddendum(HasNothing)
458 0 : { }
459 :
460 0 : IonTrackedTypeWithAddendum(TypeSet::Type type, JSScript* script, uint32_t offset)
461 0 : : type(type),
462 : hasAddendum(HasAllocationSite),
463 : script(script),
464 0 : offset(offset)
465 0 : { }
466 :
467 0 : IonTrackedTypeWithAddendum(TypeSet::Type type, JSFunction* constructor)
468 0 : : type(type),
469 : hasAddendum(HasConstructor),
470 0 : constructor(constructor)
471 0 : { }
472 :
473 0 : bool hasAllocationSite() const { return hasAddendum == HasAllocationSite; }
474 0 : bool hasConstructor() const { return hasAddendum == HasConstructor; }
475 : };
476 :
477 : typedef Vector<IonTrackedTypeWithAddendum, 1, SystemAllocPolicy> IonTrackedTypeVector;
478 :
479 : class IonTrackedOptimizationsTypeInfo
480 : {
481 : const uint8_t* start_;
482 : const uint8_t* end_;
483 :
484 : public:
485 0 : IonTrackedOptimizationsTypeInfo(const uint8_t* start, const uint8_t* end)
486 0 : : start_(start), end_(end)
487 : {
488 : // Can be empty; i.e., no type info was tracked.
489 0 : }
490 :
491 : bool empty() const { return start_ == end_; }
492 :
493 : // Unlike IonTrackedOptimizationAttempts,
494 : // JS::ForEachTrackedOptimizationTypeInfoOp cannot be used directly. The
495 : // internal API needs to deal with engine-internal data structures (e.g.,
496 : // TypeSet::Type) directly.
497 : //
498 : // An adapter is provided below.
499 0 : struct ForEachOp
500 : {
501 : virtual void readType(const IonTrackedTypeWithAddendum& tracked) = 0;
502 : virtual void operator()(JS::TrackedTypeSite site, MIRType mirType) = 0;
503 : };
504 :
505 : class ForEachOpAdapter : public ForEachOp
506 : {
507 : JS::ForEachTrackedOptimizationTypeInfoOp& op_;
508 :
509 : public:
510 0 : explicit ForEachOpAdapter(JS::ForEachTrackedOptimizationTypeInfoOp& op)
511 0 : : op_(op)
512 0 : { }
513 :
514 : void readType(const IonTrackedTypeWithAddendum& tracked) override;
515 : void operator()(JS::TrackedTypeSite site, MIRType mirType) override;
516 : };
517 :
518 : void forEach(ForEachOp& op, const IonTrackedTypeVector* allTypes);
519 : };
520 :
521 : template <class Entry>
522 : class IonTrackedOptimizationsOffsetsTable
523 : {
524 : uint32_t padding_;
525 : uint32_t numEntries_;
526 : uint32_t entryOffsets_[1];
527 :
528 : protected:
529 0 : const uint8_t* payloadEnd() const {
530 0 : return (uint8_t*)(this) - padding_;
531 : }
532 :
533 : public:
534 0 : uint32_t numEntries() const { return numEntries_; }
535 0 : uint32_t entryOffset(uint32_t index) const {
536 0 : MOZ_ASSERT(index < numEntries());
537 0 : return entryOffsets_[index];
538 : }
539 :
540 0 : Entry entry(uint32_t index) const {
541 0 : const uint8_t* start = payloadEnd() - entryOffset(index);
542 0 : const uint8_t* end = payloadEnd();
543 0 : if (index < numEntries() - 1)
544 0 : end -= entryOffset(index + 1);
545 0 : return Entry(start, end);
546 : }
547 : };
548 :
549 : class IonTrackedOptimizationsRegionTable
550 : : public IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsRegion>
551 : {
552 : public:
553 : mozilla::Maybe<IonTrackedOptimizationsRegion> findRegion(uint32_t offset) const;
554 :
555 0 : const uint8_t* payloadStart() const { return payloadEnd() - entryOffset(0); }
556 : };
557 :
558 : typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsAttempts>
559 : IonTrackedOptimizationsAttemptsTable;
560 :
561 : typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsTypeInfo>
562 : IonTrackedOptimizationsTypesTable;
563 :
564 : MOZ_MUST_USE bool
565 : WriteIonTrackedOptimizationsTable(JSContext* cx, CompactBufferWriter& writer,
566 : const NativeToTrackedOptimizations* start,
567 : const NativeToTrackedOptimizations* end,
568 : const UniqueTrackedOptimizations& unique,
569 : uint32_t* numRegions, uint32_t* regionTableOffsetp,
570 : uint32_t* typesTableOffsetp, uint32_t* attemptsTableOffsetp,
571 : IonTrackedTypeVector* allTypes);
572 :
573 : } // namespace jit
574 : } // namespace js
575 :
576 : #endif // jit_OptimizationTracking_h
|
