js/src/gc/GenerateStatsPhases.py

   1 # This Source Code Form is subject to the terms of the Mozilla Public
   2 # License, v. 2.0. If a copy of the MPL was not distributed with this
   3 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
   4
   5 # flake8: noqa: F821
   6
   7 # Generate graph structures for GC statistics recording.
   8 #
   9 # Stats phases are nested and form a directed acyclic graph starting
  10 # from a set of root phases. Importantly, a phase may appear under more
  11 # than one parent phase.
  12 #
  13 # For example, the following arrangement is possible:
  14 #
  15 #            +---+
  16 #            | A |
  17 #            +---+
  18 #              |
  19 #      +-------+-------+
  20 #      |       |       |
  21 #      v       v       v
  22 #    +---+   +---+   +---+
  23 #    | B |   | C |   | D |
  24 #    +---+   +---+   +---+
  25 #              |       |
  26 #              +---+---+
  27 #                  |
  28 #                  v
  29 #                +---+
  30 #                | E |
  31 #                +---+
  32 #
  33 # This graph is expanded into a tree (or really a forest) and phases
  34 # with multiple parents are duplicated.
  35 #
  36 # For example, the input example above would be expanded to:
  37 #
  38 #            +---+
  39 #            | A |
  40 #            +---+
  41 #              |
  42 #      +-------+-------+
  43 #      |       |       |
  44 #      v       v       v
  45 #    +---+   +---+   +---+
  46 #    | B |   | C |   | D |
  47 #    +---+   +---+   +---+
  48 #              |       |
  49 #              v       v
  50 #            +---+   +---+
  51 #            | E |   | E'|
  52 #            +---+   +---+
  53
  54 # NOTE: If you add new phases here the current next phase kind number can be
  55 # found at the end of js/src/gc/StatsPhasesGenerated.inc
  56
  57 import collections
  58 import re
  59
  60
  61 class PhaseKind:
  62     def __init__(self, name, descr, bucket, children=[]):
  63         self.name = name
  64         self.descr = descr
  65         # For telemetry
  66         self.bucket = bucket
  67         self.children = children
  68
  69
  70 AllPhaseKinds = []
  71 PhaseKindsByName = dict()
  72
  73
  74 def addPhaseKind(name, descr, bucket, children=[]):
  75     assert name not in PhaseKindsByName
  76     phaseKind = PhaseKind(name, descr, bucket, children)
  77     AllPhaseKinds.append(phaseKind)
  78     PhaseKindsByName[name] = phaseKind
  79     return phaseKind
  80
  81
  82 def getPhaseKind(name):
  83     return PhaseKindsByName[name]
  84
  85
  86 PhaseKindGraphRoots = [
  87     addPhaseKind("MUTATOR", "Mutator Running", 0),
  88     addPhaseKind("GC_BEGIN", "Begin Callback", 1),
  89     addPhaseKind(
  90         "EVICT_NURSERY_FOR_MAJOR_GC",
  91         "Evict Nursery For Major GC",
  92         70,
  93         [
  94             addPhaseKind(
  95                 "MARK_ROOTS",
  96                 "Mark Roots",
  97                 48,
  98                 [
  99                     addPhaseKind("MARK_CCWS", "Mark Cross Compartment Wrappers", 50),
 100                     addPhaseKind("MARK_STACK", "Mark C and JS stacks", 51),
 101                     addPhaseKind("MARK_RUNTIME_DATA", "Mark Runtime-wide Data", 52),
 102                     addPhaseKind("MARK_EMBEDDING", "Mark Embedding", 53),
 103                 ],
 104             )
 105         ],
 106     ),
 107     addPhaseKind("WAIT_BACKGROUND_THREAD", "Wait Background Thread", 2),
 108     addPhaseKind(
 109         "PREPARE",
 110         "Prepare For Collection",
 111         69,
 112         [
 113             addPhaseKind("UNMARK", "Unmark", 7),
 114             addPhaseKind("UNMARK_WEAKMAPS", "Unmark WeakMaps", 76),
 115             addPhaseKind("MARK_DISCARD_CODE", "Mark Discard Code", 3),
 116             addPhaseKind("RELAZIFY_FUNCTIONS", "Relazify Functions", 4),
 117             addPhaseKind("PURGE", "Purge", 5),
 118             addPhaseKind("PURGE_PROP_MAP_TABLES", "Purge PropMapTables", 60),
 119             addPhaseKind("PURGE_SOURCE_URLS", "Purge Source URLs", 73),
 120             addPhaseKind("JOIN_PARALLEL_TASKS", "Join Parallel Tasks", 67),
 121         ],
 122     ),
 123     addPhaseKind(
 124         "MARK",
 125         "Mark",
 126         6,
 127         [
 128             getPhaseKind("MARK_ROOTS"),
 129             addPhaseKind("MARK_DELAYED", "Mark Delayed", 8),
 130             addPhaseKind(
 131                 "MARK_WEAK",
 132                 "Mark Weak",
 133                 13,
 134                 [
 135                     getPhaseKind("MARK_DELAYED"),
 136                     addPhaseKind("MARK_GRAY_WEAK", "Mark Gray and Weak", 16),
 137                 ],
 138             ),
 139             addPhaseKind("MARK_INCOMING_GRAY", "Mark Incoming Gray Pointers", 14),
 140             addPhaseKind("MARK_GRAY", "Mark Gray", 15),
 141             addPhaseKind(
 142                 "PARALLEL_MARK",
 143                 "Parallel marking",
 144                 78,
 145                 [
 146                     getPhaseKind("JOIN_PARALLEL_TASKS"),
 147                     # The following are only used for parallel phase times:
 148                     addPhaseKind("PARALLEL_MARK_MARK", "Parallel marking work", 79),
 149                     addPhaseKind("PARALLEL_MARK_WAIT", "Waiting for work", 80),
 150                     addPhaseKind(
 151                         "PARALLEL_MARK_OTHER", "Parallel marking overhead", 82
 152                     ),
 153                 ],
 154             ),
 155         ],
 156     ),
 157     addPhaseKind(
 158         "SWEEP",
 159         "Sweep",
 160         9,
 161         [
 162             getPhaseKind("MARK"),
 163             addPhaseKind(
 164                 "FINALIZE_START",
 165                 "Finalize Start Callbacks",
 166                 17,
 167                 [
 168                     addPhaseKind("WEAK_ZONES_CALLBACK", "Per-Slice Weak Callback", 57),
 169                     addPhaseKind(
 170                         "WEAK_COMPARTMENT_CALLBACK", "Per-Compartment Weak Callback", 58
 171                     ),
 172                 ],
 173             ),
 174             addPhaseKind("UPDATE_ATOMS_BITMAP", "Sweep Atoms Bitmap", 68),
 175             addPhaseKind("SWEEP_ATOMS_TABLE", "Sweep Atoms Table", 18),
 176             addPhaseKind(
 177                 "SWEEP_COMPARTMENTS",
 178                 "Sweep Compartments",
 179                 20,
 180                 [
 181                     addPhaseKind("SWEEP_DISCARD_CODE", "Sweep Discard Code", 21),
 182                     addPhaseKind("SWEEP_INNER_VIEWS", "Sweep Inner Views", 22),
 183                     addPhaseKind(
 184                         "SWEEP_CC_WRAPPER", "Sweep Cross Compartment Wrappers", 23
 185                     ),
 186                     addPhaseKind("SWEEP_BASE_SHAPE", "Sweep Base Shapes", 24),
 187                     addPhaseKind("SWEEP_INITIAL_SHAPE", "Sweep Initial Shapes", 25),
 188                     addPhaseKind("SWEEP_REGEXP", "Sweep Regexps", 28),
 189                     addPhaseKind("SWEEP_COMPRESSION", "Sweep Compression Tasks", 62),
 190                     addPhaseKind("SWEEP_WEAKMAPS", "Sweep WeakMaps", 63),
 191                     addPhaseKind("SWEEP_UNIQUEIDS", "Sweep Unique IDs", 64),
 192                     addPhaseKind("SWEEP_WEAK_POINTERS", "Sweep Weak Pointers", 81),
 193                     addPhaseKind(
 194                         "SWEEP_FINALIZATION_OBSERVERS",
 195                         "Sweep FinalizationRegistries and WeakRefs",
 196                         74,
 197                     ),
 198                     addPhaseKind("SWEEP_JIT_DATA", "Sweep JIT Data", 65),
 199                     addPhaseKind("SWEEP_WEAK_CACHES", "Sweep Weak Caches", 66),
 200                     addPhaseKind("SWEEP_MISC", "Sweep Miscellaneous", 29),
 201                     getPhaseKind("JOIN_PARALLEL_TASKS"),
 202                 ],
 203             ),
 204             addPhaseKind("FINALIZE_OBJECT", "Finalize Objects", 33),
 205             addPhaseKind("FINALIZE_NON_OBJECT", "Finalize Non-objects", 34),
 206             addPhaseKind("SWEEP_PROP_MAP", "Sweep PropMap Tree", 77),
 207             addPhaseKind("FINALIZE_END", "Finalize End Callback", 38),
 208             addPhaseKind("DESTROY", "Deallocate", 39),
 209             getPhaseKind("JOIN_PARALLEL_TASKS"),
 210             addPhaseKind("FIND_DEAD_COMPARTMENTS", "Find Dead Compartments", 54),
 211         ],
 212     ),
 213     addPhaseKind(
 214         "COMPACT",
 215         "Compact",
 216         40,
 217         [
 218             addPhaseKind("COMPACT_MOVE", "Compact Move", 41),
 219             addPhaseKind(
 220                 "COMPACT_UPDATE",
 221                 "Compact Update",
 222                 42,
 223                 [
 224                     getPhaseKind("MARK_ROOTS"),
 225                     addPhaseKind("COMPACT_UPDATE_CELLS", "Compact Update Cells", 43),
 226                     getPhaseKind("JOIN_PARALLEL_TASKS"),
 227                 ],
 228             ),
 229         ],
 230     ),
 231     addPhaseKind("DECOMMIT", "Decommit", 72),
 232     addPhaseKind("GC_END", "End Callback", 44),
 233     addPhaseKind(
 234         "MINOR_GC",
 235         "All Minor GCs",
 236         45,
 237         [
 238             getPhaseKind("MARK_ROOTS"),
 239         ],
 240     ),
 241     addPhaseKind(
 242         "EVICT_NURSERY",
 243         "Minor GCs to Evict Nursery",
 244         46,
 245         [
 246             getPhaseKind("MARK_ROOTS"),
 247         ],
 248     ),
 249     addPhaseKind(
 250         "TRACE_HEAP",
 251         "Trace Heap",
 252         47,
 253         [
 254             getPhaseKind("MARK_ROOTS"),
 255         ],
 256     ),
 257 ]
 258
 259
 260 class Phase:
 261     # Expand the DAG into a tree, duplicating phases which have more than
 262     # one parent.
 263     def __init__(self, phaseKind, parent):
 264         self.phaseKind = phaseKind
 265         self.parent = parent
 266         self.depth = parent.depth + 1 if parent else 0
 267         self.children = []
 268         self.nextSibling = None
 269         self.nextInPhaseKind = None
 270
 271         self.path = re.sub(r"\W+", "_", phaseKind.name.lower())
 272         if parent is not None:
 273             self.path = parent.path + "." + self.path
 274
 275
 276 def expandPhases():
 277     phases = []
 278     phasesForKind = collections.defaultdict(list)
 279
 280     def traverse(phaseKind, parent):
 281         ep = Phase(phaseKind, parent)
 282         phases.append(ep)
 283
 284         # Update list of expanded phases for this phase kind.
 285         if phasesForKind[phaseKind]:
 286             phasesForKind[phaseKind][-1].nextInPhaseKind = ep
 287         phasesForKind[phaseKind].append(ep)
 288
 289         # Recurse over children.
 290         for child in phaseKind.children:
 291             child_ep = traverse(child, ep)
 292             if ep.children:
 293                 ep.children[-1].nextSibling = child_ep
 294             ep.children.append(child_ep)
 295         return ep
 296
 297     for phaseKind in PhaseKindGraphRoots:
 298         traverse(phaseKind, None)
 299
 300     return phases, phasesForKind
 301
 302
 303 AllPhases, PhasesForPhaseKind = expandPhases()
 304
 305 # Name phases based on phase kind name and index if there are multiple phases
 306 # corresponding to a single phase kind.
 307
 308 for phaseKind in AllPhaseKinds:
 309     phases = PhasesForPhaseKind[phaseKind]
 310     if len(phases) == 1:
 311         phases[0].name = "%s" % phaseKind.name
 312     else:
 313         for index, phase in enumerate(phases):
 314             phase.name = "%s_%d" % (phaseKind.name, index + 1)
 315
 316 # Find the maximum phase nesting.
 317 MaxPhaseNesting = max(phase.depth for phase in AllPhases) + 1
 318
 319 # And the maximum bucket number.
 320 MaxBucket = max(kind.bucket for kind in AllPhaseKinds)
 321
 322 # Generate code.
 323
 324
 325 def writeList(out, items):
 326     if items:
 327         out.write(",\n".join("  " + item for item in items) + "\n")
 328
 329
 330 def writeEnumClass(out, name, type, items, extraItems):
 331     items = ["FIRST"] + list(items) + ["LIMIT"] + list(extraItems)
 332     items[1] += " = " + items[0]
 333     out.write("enum class %s : %s {\n" % (name, type))
 334     writeList(out, items)
 335     out.write("};\n")
 336
 337
 338 def generateHeader(out):
 339     #
 340     # Generate PhaseKind enum.
 341     #
 342     phaseKindNames = map(lambda phaseKind: phaseKind.name, AllPhaseKinds)
 343     extraPhaseKinds = [
 344         "NONE = LIMIT",
 345         "EXPLICIT_SUSPENSION = LIMIT",
 346         "IMPLICIT_SUSPENSION",
 347     ]
 348     writeEnumClass(out, "PhaseKind", "uint8_t", phaseKindNames, extraPhaseKinds)
 349     out.write("\n")
 350
 351     #
 352     # Generate Phase enum.
 353     #
 354     phaseNames = map(lambda phase: phase.name, AllPhases)
 355     extraPhases = ["NONE = LIMIT", "EXPLICIT_SUSPENSION = LIMIT", "IMPLICIT_SUSPENSION"]
 356     writeEnumClass(out, "Phase", "uint8_t", phaseNames, extraPhases)
 357     out.write("\n")
 358
 359     #
 360     # Generate MAX_PHASE_NESTING constant.
 361     #
 362     out.write("static const size_t MAX_PHASE_NESTING = %d;\n" % MaxPhaseNesting)
 363
 364
 365 def generateCpp(out):
 366     #
 367     # Generate the PhaseKindInfo table.
 368     #
 369     out.write("static constexpr PhaseKindTable phaseKinds = {\n")
 370     for phaseKind in AllPhaseKinds:
 371         phase = PhasesForPhaseKind[phaseKind][0]
 372         out.write(
 373             '    /* PhaseKind::%s */ PhaseKindInfo { Phase::%s, %d, "%s" },\n'
 374             % (phaseKind.name, phase.name, phaseKind.bucket, phaseKind.name)
 375         )
 376     out.write("};\n")
 377     out.write("\n")
 378
 379     #
 380     # Generate the PhaseInfo tree.
 381     #
 382     def name(phase):
 383         return "Phase::" + phase.name if phase else "Phase::NONE"
 384
 385     out.write("static constexpr PhaseTable phases = {\n")
 386     for phase in AllPhases:
 387         firstChild = phase.children[0] if phase.children else None
 388         phaseKind = phase.phaseKind
 389         out.write(
 390             '    /* %s */ PhaseInfo { %s, %s, %s, %s, PhaseKind::%s, %d, "%s", "%s" },\n'
 391             % (  # NOQA: E501
 392                 name(phase),
 393                 name(phase.parent),
 394                 name(firstChild),
 395                 name(phase.nextSibling),
 396                 name(phase.nextInPhaseKind),
 397                 phaseKind.name,
 398                 phase.depth,
 399                 phaseKind.descr,
 400                 phase.path,
 401             )
 402         )
 403     out.write("};\n")
 404
 405     #
 406     # Print in a comment the next available phase kind number.
 407     #
 408     out.write("// The next available phase kind number is: %d\n" % (MaxBucket + 1))