basis/compiler/cfg/liveness/liveness-docs.factor

   1 USING: assocs compiler.cfg compiler.cfg.def-use
   2 compiler.cfg.instructions compiler.cfg.representations
   3 cpu.architecture hash-sets help.markup help.syntax kernel math
   4 sequences ;
   5 IN: compiler.cfg.liveness
   6
   7 HELP: base-pointers
   8 { $var-description "Mapping from vregs to base pointer vregs. If the vreg doesn't have a base pointer, then it will be mapped to " { $link f } "." }
   9 { $see-also lookup-base-pointer } ;
  10
  11 HELP: compute-live-sets
  12 { $values { "cfg" cfg } }
  13 { $description "Main entry point for vocab. Pass must only be run after representation selection. In this pass " { $slot "gc-roots" } " are set." } ;
  14
  15 HELP: edge-live-ins
  16 { $var-description { $link assoc } " mapping basic blocks to sequences of sets of vregs; each sequence is in correspondence with a predecessor." } ;
  17
  18 HELP: fill-gc-map
  19 { $values { "live-set" assoc } { "gc-map" gc-map } }
  20 { $description "Assigns values to the " { $slot "gc-roots" } " and " { $slot "derived-roots" } " slots of the " { $link gc-map } ". Does nothing if the " { $link select-representations } " pass hasn't ran." } ;
  21
  22 HELP: gc-roots
  23 { $values { "live-set" assoc } { "derived-roots" hash-set } { "gc-roots" sequence } } ;
  24
  25 HELP: gen-uses
  26 { $values { "live-set" assoc } { "insn" insn } }
  27 { $description "Adds the vregs the instruction uses to the live set." }
  28 { $see-also uses-vregs } ;
  29
  30 HELP: kill-defs
  31 { $values { "live-set" assoc } { "insn" insn } }
  32 { $description "If liveness analysis is run after SSA destruction, we need to kill vregs that have been coalesced with others (they won't have been renamed from their original values in the CFG). Otherwise, we get a bunch of stray uses that wind up live-in/out when they shouldn't be. However, we must take care to still report the original vregs in the live-sets, because they have information associated with them (like representations) that would get lost if we just used the leaders for everything." } ;
  33
  34 HELP: live-in
  35 { $values { "bb" basic-block } { "set" assoc } }
  36 { $description "All the virtual registers that are live in a basic block." } ;
  37
  38 HELP: live-in?
  39 { $values { "vreg" "virtual register" } { "bb" basic-block } { "?" boolean } }
  40 { $description "Whether the vreg is live in the block or not." } ;
  41
  42 HELP: live-ins
  43 { $var-description "Hash that maps from basic blocks to vregs that are live in them." }
  44 { $see-also compute-live-sets } ;
  45
  46 HELP: live-outs
  47 { $var-description "Hash that maps from basic blocks to sets of vregs that are live after execution leaves the block. The data is computed by " { $link compute-live-sets } } ;
  48
  49 HELP: lookup-base-pointer
  50 { $values { "vreg" "vreg" } { "vreg/f" { $maybe "vreg" } } }
  51 { $description "Tries to figure out what the base pointer for a vreg is. Can't use cache here because of infinite recursion inside the quotation passed to cache" }
  52 { $see-also base-pointers } ;
  53
  54 HELP: visit-gc-root
  55 { $values
  56   { "vreg" integer }
  57   { "derived-roots" assoc }
  58   { "gc-roots" sequence }
  59 }
  60 { $description "Handles a vreg that is live at a gc point. The vreg is handled in three ways depending on its representation:"
  61   { $list
  62     { "If it is " { $link tagged-rep } ", then the vreg contains a pointer to an object and it is added to the 'gc-roots' sequence." }
  63     { "If it is " { $link int-rep } " and the vreg has a base pointer, then it is added to the 'derived-roots' assoc along with that base pointer." }
  64     "Otherwise the vreg does not contain an object reference and nothing is done with it."
  65   }
  66 }
  67 { $see-also lookup-base-pointer } ;
  68
  69 ARTICLE: "compiler.cfg.liveness" "Liveness analysis"
  70 "Similar to http://en.wikipedia.org/wiki/Liveness_analysis, with three additions:"
  71 $nl
  72 { $list
  73   "With SSA, it is not sufficient to have a single live-in set per block. There is also an edge-live-in set per edge, consisting of phi inputs from each predecessor."
  74   "Liveness analysis annotates call sites with GC maps indicating the spill slots in the stack frame that contain tagged pointers, and thus have to be visited if a GC occurs inside the call."
  75   { "GC maps can contain derived pointers. A derived pointer is a pointer into the middle of a data heap object. Each derived pointer has a base pointer, to keep it up to date when objects are moved by the garbage collector. This extends live intervals and inserts new " { $link ##phi } " instructions." }
  76 }
  77 $nl
  78 "Querying liveness data:"
  79 { $subsections
  80   live-in live-in? live-ins
  81   live-out live-out? live-outs
  82 }
  83 "Filling GC maps:"
  84 { $subsections
  85   lookup-base-pointer
  86   visit-gc-root
  87 } ;
  88
  89 ABOUT: "compiler.cfg.liveness"