summaryrefslogtreecommitdiffstats
path: root/js/src/gc/GenerateStatsPhases.py
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 14:29:10 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 14:29:10 +0000
commit2aa4a82499d4becd2284cdb482213d541b8804dd (patch)
treeb80bf8bf13c3766139fbacc530efd0dd9d54394c /js/src/gc/GenerateStatsPhases.py
parentInitial commit. (diff)
downloadfirefox-upstream.tar.xz
firefox-upstream.zip
Adding upstream version 86.0.1.upstream/86.0.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--js/src/gc/GenerateStatsPhases.py416
1 files changed, 416 insertions, 0 deletions
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))