From 2aa4a82499d4becd2284cdb482213d541b8804dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 16:29:10 +0200 Subject: Adding upstream version 86.0.1. Signed-off-by: Daniel Baumann --- js/src/gc/GenerateStatsPhases.py | 416 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 416 insertions(+) create mode 100644 js/src/gc/GenerateStatsPhases.py (limited to 'js/src/gc/GenerateStatsPhases.py') diff --git a/js/src/gc/GenerateStatsPhases.py b/js/src/gc/GenerateStatsPhases.py new file mode 100644 index 0000000000..4cc53235a7 --- /dev/null +++ b/js/src/gc/GenerateStatsPhases.py @@ -0,0 +1,416 @@ +# 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/. + +# flake8: noqa: F821 + +# Generate graph structures for GC statistics recording. +# +# Stats phases are nested and form a directed acyclic graph starting +# from a set of root phases. Importantly, a phase may appear under more +# than one parent phase. +# +# For example, the following arrangement is possible: +# +# +---+ +# | A | +# +---+ +# | +# +-------+-------+ +# | | | +# v v v +# +---+ +---+ +---+ +# | B | | C | | D | +# +---+ +---+ +---+ +# | | +# +---+---+ +# | +# v +# +---+ +# | E | +# +---+ +# +# This graph is expanded into a tree (or really a forest) and phases +# with multiple parents are duplicated. +# +# For example, the input example above would be expanded to: +# +# +---+ +# | A | +# +---+ +# | +# +-------+-------+ +# | | | +# v v v +# +---+ +---+ +---+ +# | B | | C | | D | +# +---+ +---+ +---+ +# | | +# v v +# +---+ +---+ +# | E | | E'| +# +---+ +---+ + +# NOTE: If you add new phases here the current next phase kind number can be +# found at the end of js/src/gc/StatsPhasesGenerated.inc + +import re +import collections + + +class PhaseKind: + def __init__(self, name, descr, bucket, children=[]): + self.name = name + self.descr = descr + # For telemetry + self.bucket = bucket + self.children = children + + +# The root marking phase appears in several places in the graph. +MarkRootsPhaseKind = PhaseKind( + "MARK_ROOTS", + "Mark Roots", + 48, + [ + PhaseKind("MARK_CCWS", "Mark Cross Compartment Wrappers", 50), + PhaseKind("MARK_STACK", "Mark C and JS stacks", 51), + PhaseKind("MARK_RUNTIME_DATA", "Mark Runtime-wide Data", 52), + PhaseKind("MARK_EMBEDDING", "Mark Embedding", 53), + PhaseKind("MARK_COMPARTMENTS", "Mark Compartments", 54), + ], +) + +JoinParallelTasksPhaseKind = PhaseKind("JOIN_PARALLEL_TASKS", "Join Parallel Tasks", 67) + +PhaseKindGraphRoots = [ + PhaseKind("MUTATOR", "Mutator Running", 0), + PhaseKind("GC_BEGIN", "Begin Callback", 1), + PhaseKind( + "EVICT_NURSERY_FOR_MAJOR_GC", + "Evict Nursery For Major GC", + 70, + [ + MarkRootsPhaseKind, + ], + ), + PhaseKind("WAIT_BACKGROUND_THREAD", "Wait Background Thread", 2), + PhaseKind( + "PREPARE", + "Prepare For Collection", + 69, + [ + PhaseKind("UNMARK", "Unmark", 7), + PhaseKind("UNMARK_WEAKMAPS", "Unmark WeakMaps", 76), + PhaseKind("BUFFER_GRAY_ROOTS", "Buffer Gray Roots", 49), + PhaseKind("MARK_DISCARD_CODE", "Mark Discard Code", 3), + PhaseKind("RELAZIFY_FUNCTIONS", "Relazify Functions", 4), + PhaseKind("PURGE", "Purge", 5), + PhaseKind("PURGE_SHAPE_CACHES", "Purge ShapeCaches", 60), + PhaseKind("PURGE_SOURCE_URLS", "Purge Source URLs", 73), + JoinParallelTasksPhaseKind, + ], + ), + PhaseKind( + "MARK", + "Mark", + 6, + [MarkRootsPhaseKind, PhaseKind("MARK_DELAYED", "Mark Delayed", 8)], + ), + PhaseKind( + "SWEEP", + "Sweep", + 9, + [ + PhaseKind( + "SWEEP_MARK", + "Mark During Sweeping", + 10, + [ + PhaseKind( + "SWEEP_MARK_INCOMING_BLACK", "Mark Incoming Black Pointers", 12 + ), + PhaseKind( + "SWEEP_MARK_WEAK", + "Mark Weak", + 13, + [PhaseKind("SWEEP_MARK_GRAY_WEAK", "Mark Gray and Weak", 16)], + ), + PhaseKind( + "SWEEP_MARK_INCOMING_GRAY", "Mark Incoming Gray Pointers", 14 + ), + PhaseKind("SWEEP_MARK_GRAY", "Mark Gray", 15), + ], + ), + PhaseKind( + "FINALIZE_START", + "Finalize Start Callbacks", + 17, + [ + PhaseKind("WEAK_ZONES_CALLBACK", "Per-Slice Weak Callback", 57), + PhaseKind( + "WEAK_COMPARTMENT_CALLBACK", "Per-Compartment Weak Callback", 58 + ), + ], + ), + PhaseKind("UPDATE_ATOMS_BITMAP", "Sweep Atoms Bitmap", 68), + PhaseKind("SWEEP_ATOMS_TABLE", "Sweep Atoms Table", 18), + PhaseKind( + "SWEEP_COMPARTMENTS", + "Sweep Compartments", + 20, + [ + PhaseKind("SWEEP_DISCARD_CODE", "Sweep Discard Code", 21), + PhaseKind("SWEEP_INNER_VIEWS", "Sweep Inner Views", 22), + PhaseKind( + "SWEEP_CC_WRAPPER", "Sweep Cross Compartment Wrappers", 23 + ), + PhaseKind("SWEEP_BASE_SHAPE", "Sweep Base Shapes", 24), + PhaseKind("SWEEP_INITIAL_SHAPE", "Sweep Initial Shapes", 25), + PhaseKind("SWEEP_REGEXP", "Sweep Regexps", 28), + PhaseKind("SWEEP_COMPRESSION", "Sweep Compression Tasks", 62), + PhaseKind("SWEEP_WEAKMAPS", "Sweep WeakMaps", 63), + PhaseKind("SWEEP_UNIQUEIDS", "Sweep Unique IDs", 64), + PhaseKind( + "SWEEP_FINALIZATION_REGISTRIES", + "Sweep FinalizationRegistries", + 74, + ), + PhaseKind("SWEEP_WEAKREFS", "Sweep WeakRefs", 75), + PhaseKind("SWEEP_JIT_DATA", "Sweep JIT Data", 65), + PhaseKind("SWEEP_WEAK_CACHES", "Sweep Weak Caches", 66), + PhaseKind("SWEEP_MISC", "Sweep Miscellaneous", 29), + JoinParallelTasksPhaseKind, + ], + ), + PhaseKind("SWEEP_OBJECT", "Sweep Object", 33), + PhaseKind("SWEEP_STRING", "Sweep String", 34), + PhaseKind("SWEEP_SCRIPT", "Sweep Script", 35), + PhaseKind("SWEEP_SCOPE", "Sweep Scope", 59), + PhaseKind("SWEEP_REGEXP_SHARED", "Sweep RegExpShared", 61), + PhaseKind("SWEEP_SHAPE", "Sweep Shape", 36), + PhaseKind("FINALIZE_END", "Finalize End Callback", 38), + PhaseKind("DESTROY", "Deallocate", 39), + JoinParallelTasksPhaseKind, + ], + ), + PhaseKind( + "COMPACT", + "Compact", + 40, + [ + PhaseKind("COMPACT_MOVE", "Compact Move", 41), + PhaseKind( + "COMPACT_UPDATE", + "Compact Update", + 42, + [ + MarkRootsPhaseKind, + PhaseKind("COMPACT_UPDATE_CELLS", "Compact Update Cells", 43), + JoinParallelTasksPhaseKind, + ], + ), + ], + ), + PhaseKind("DECOMMIT", "Decommit", 72), + PhaseKind("GC_END", "End Callback", 44), + PhaseKind( + "MINOR_GC", + "All Minor GCs", + 45, + [ + MarkRootsPhaseKind, + ], + ), + PhaseKind( + "EVICT_NURSERY", + "Minor GCs to Evict Nursery", + 46, + [ + MarkRootsPhaseKind, + ], + ), + PhaseKind( + "TRACE_HEAP", + "Trace Heap", + 47, + [ + MarkRootsPhaseKind, + ], + ), + PhaseKind("BARRIER", "Barriers", 55, [PhaseKind("UNMARK_GRAY", "Unmark gray", 56)]), +] + + +def findAllPhaseKinds(): + # Make a linear list of all unique phases by performing a depth first + # search on the phase graph starting at the roots. This will be used to + # generate the PhaseKind enum. + phases = [] + seen = set() + + def dfs(phase): + if phase in seen: + return + phases.append(phase) + seen.add(phase) + for child in phase.children: + dfs(child) + + for phase in PhaseKindGraphRoots: + dfs(phase) + return phases + + +AllPhaseKinds = findAllPhaseKinds() + + +class Phase: + # Expand the DAG into a tree, duplicating phases which have more than + # one parent. + def __init__(self, phaseKind, parent): + self.phaseKind = phaseKind + self.parent = parent + self.depth = parent.depth + 1 if parent else 0 + self.children = [] + self.nextSibling = None + self.nextInPhaseKind = None + + self.path = re.sub(r"\W+", "_", phaseKind.name.lower()) + if parent is not None: + self.path = parent.path + "." + self.path + + +def expandPhases(): + phases = [] + phasesForKind = collections.defaultdict(list) + + def traverse(phaseKind, parent): + ep = Phase(phaseKind, parent) + phases.append(ep) + + # Update list of expanded phases for this phase kind. + if phasesForKind[phaseKind]: + phasesForKind[phaseKind][-1].nextInPhaseKind = ep + phasesForKind[phaseKind].append(ep) + + # Recurse over children. + for child in phaseKind.children: + child_ep = traverse(child, ep) + if ep.children: + ep.children[-1].nextSibling = child_ep + ep.children.append(child_ep) + return ep + + for phaseKind in PhaseKindGraphRoots: + traverse(phaseKind, None) + + return phases, phasesForKind + + +AllPhases, PhasesForPhaseKind = expandPhases() + +# Name phases based on phase kind name and index if there are multiple phases +# corresponding to a single phase kind. + +for phaseKind in AllPhaseKinds: + phases = PhasesForPhaseKind[phaseKind] + if len(phases) == 1: + phases[0].name = "%s" % phaseKind.name + else: + for index, phase in enumerate(phases): + phase.name = "%s_%d" % (phaseKind.name, index + 1) + +# Find the maximum phase nesting. +MaxPhaseNesting = max(phase.depth for phase in AllPhases) + 1 + +# And the maximum bucket number. +MaxBucket = max(kind.bucket for kind in AllPhaseKinds) + +# Generate code. + + +def writeList(out, items): + if items: + out.write(",\n".join(" " + item for item in items) + "\n") + + +def writeEnumClass(out, name, type, items, extraItems): + items = ["FIRST"] + list(items) + ["LIMIT"] + list(extraItems) + items[1] += " = " + items[0] + out.write("enum class %s : %s {\n" % (name, type)) + writeList(out, items) + out.write("};\n") + + +def generateHeader(out): + # + # Generate PhaseKind enum. + # + phaseKindNames = map(lambda phaseKind: phaseKind.name, AllPhaseKinds) + extraPhaseKinds = [ + "NONE = LIMIT", + "EXPLICIT_SUSPENSION = LIMIT", + "IMPLICIT_SUSPENSION", + ] + writeEnumClass(out, "PhaseKind", "uint8_t", phaseKindNames, extraPhaseKinds) + out.write("\n") + + # + # Generate Phase enum. + # + phaseNames = map(lambda phase: phase.name, AllPhases) + extraPhases = ["NONE = LIMIT", "EXPLICIT_SUSPENSION = LIMIT", "IMPLICIT_SUSPENSION"] + writeEnumClass(out, "Phase", "uint8_t", phaseNames, extraPhases) + out.write("\n") + + # + # Generate MAX_PHASE_NESTING constant. + # + out.write("static const size_t MAX_PHASE_NESTING = %d;\n" % MaxPhaseNesting) + + +def generateCpp(out): + # + # Generate the PhaseKindInfo table. + # + out.write("static constexpr PhaseKindTable phaseKinds = {\n") + for phaseKind in AllPhaseKinds: + phase = PhasesForPhaseKind[phaseKind][0] + out.write( + " /* PhaseKind::%s */ PhaseKindInfo { Phase::%s, %d },\n" + % (phaseKind.name, phase.name, phaseKind.bucket) + ) + out.write("};\n") + out.write("\n") + + # + # Generate the PhaseInfo tree. + # + def name(phase): + return "Phase::" + phase.name if phase else "Phase::NONE" + + out.write("static constexpr PhaseTable phases = {\n") + for phase in AllPhases: + firstChild = phase.children[0] if phase.children else None + phaseKind = phase.phaseKind + out.write( + ' /* %s */ PhaseInfo { %s, %s, %s, %s, PhaseKind::%s, %d, "%s", "%s" },\n' + % ( # NOQA: E501 + name(phase), + name(phase.parent), + name(firstChild), + name(phase.nextSibling), + name(phase.nextInPhaseKind), + phaseKind.name, + phase.depth, + phaseKind.descr, + phase.path, + ) + ) + out.write("};\n") + + # + # Print in a comment the next available phase kind number. + # + out.write("// The next available phase kind number is: %d\n" % (MaxBucket + 1)) -- cgit v1.2.3