basis/compiler/cfg/linear-scan/assignment/assignment-docs.factor

   1 USING: assocs compiler.cfg compiler.cfg.instructions
   2 compiler.cfg.linear-scan.allocation
   3 compiler.cfg.linear-scan.allocation.state
   4 compiler.cfg.linear-scan.live-intervals compiler.cfg.liveness
   5 compiler.cfg.registers heaps help.markup help.syntax math quotations
   6 sequences ;
   7 IN: compiler.cfg.linear-scan.assignment
   8
   9 HELP: add-pending
  10 { $values { "live-interval" live-interval-state } }
  11 { $description "Adds a live interval to the pending interval set." } ;
  12
  13 HELP: assign-registers-in-block
  14 { $values { "bb" basic-block } }
  15 { $description "Assigns registers to vregs and also inserts " { $link ##reload } " and " { $link ##spill } " instructions." } ;
  16
  17 HELP: assign-registers
  18 { $values { "cfg" cfg } { "live-intervals" sequence } }
  19 { $description "Uses the live intervals in the sequence to assign physical registers to all instructions in the cfg. The live intervals must first have had their physical registers assigned by " { $link allocate-registers } "." } ;
  20
  21 HELP: assign-all-registers
  22 { $values { "insn" insn } }
  23 { $description "Assigns physical registers for the virtual registers used and defined by the instruction." } ;
  24
  25 HELP: change-insn-gc-roots
  26 { $values { "gc-map-insn" gc-map-insn } { "quot" quotation } }
  27 { $description "Applies the quotation to all vregs in the instructions " { $link gc-map } "." } ;
  28
  29 HELP: compute-live-in
  30 { $values { "bb" basic-block } }
  31 { $description "Computes the live in registers for a basic block." }
  32 { $see-also machine-live-ins } ;
  33
  34 HELP: emit-##call-gc
  35 { $values { "insn" ##call-gc } }
  36 { $description "Emits a " { $link ##call-gc } " instruction and the " { $link ##reload } " and " { $link ##spill } " instructions it requires. ##call-gc aren't counted as sync points, so the instruction requires special handling." } ;
  37
  38 HELP: expire-old-intervals
  39 { $values { "n" integer } { "pending-heap" min-heap } }
  40 { $description "Expires all intervals older than the cutoff point. First they are removed from the 'pending-heap' and " { $link pending-interval-assoc } ". Then " { $link ##spill } " instructions are inserted for each interval that was removed." } ;
  41
  42 HELP: insert-reload
  43 { $values { "live-interval" live-interval-state } }
  44 { $description "Inserts a " { $link ##reload } " instruction for a live interval." }
  45 { $see-also handle-reload insert-spill } ;
  46
  47 HELP: insert-spill
  48 { $values { "live-interval" live-interval-state } }
  49 { $description "Inserts a " { $link ##spill } " instruction for a live interval." }
  50 { $see-also insert-reload } ;
  51
  52 HELP: machine-edge-live-ins
  53 { $var-description "Mapping from basic blocks to predecessors to values which are live on a particular incoming edge." } ;
  54
  55 HELP: machine-live-ins
  56 { $var-description "Mapping from basic blocks to values which are live at the start on all incoming CFG edges. Each value is a sequence of 2-tuples where the first element is the vreg and the second the register or " { $link spill-slot } " which contains its value. It's like " { $link live-ins } " except the registers are physical instead of virtual." } ;
  57
  58 HELP: machine-live-outs
  59 { $var-description "Mapping from " { $link basic-block } " to an " { $link assoc } " of pairs which are the values that are live at the end. The keys of the pairs are virtual registers and the values are either real registers or spill slots." } ;
  60
  61 HELP: remove-pending
  62 { $values { "live-interval" live-interval-state } }
  63 { $description "Removes a pending live interval." } ;
  64
  65 HELP: unhandled-intervals
  66 { $var-description { $link min-heap } " of live intervals which still need a register allocation." } ;
  67
  68 HELP: vreg>reg
  69 { $values { "vreg" "virtual register" } { "reg/spill-slot" "a register or a spill slot" } }
  70 { $description "Translates a virtual register to a physical one. If the vreg is not in the pending set, then it must have been spilled and its spill slot is returned." }
  71 { $errors "Can throw a " { $link bad-vreg } " error if the vreg is not in the " { $link pending-interval-assoc } " and also doesn't have a spill slot registered." }
  72 { $see-also lookup-spill-slot pending-interval-assoc } ;
  73
  74 HELP: vregs>regs
  75 { $values { "assoc" "an " { $link assoc } " (set) of virtual registers" } { "assoc'" assoc } }
  76 { $description "Creates a mapping of virtual registers to registers." } ;
  77
  78 HELP: vreg>spill-slot
  79 { $values { "vreg" integer } { "spill-slot" spill-slot } }
  80 { $description "Converts a vreg number to a spill slot." } ;
  81
  82 ARTICLE: "compiler.cfg.linear-scan.assignment" "Assigning registers to live intervals"
  83 "The " { $vocab-link "compiler.cfg.linear-scan.assignment" } " assigns registers to live intervals. Before this compiler pass, all values in the " { $link cfg } " were represented as simple integers called \"virtual registers\" or vregs. In this pass, using the live interval data computed in the register allocation pass (" { $vocab-link "compiler.cfg.linear-scan.allocation" } "), those vregs are translated into physical registers."
  84 $nl
  85 "Since there is an infinite number of vregs but the number of physical registers is limited, some values must be spilled. So this pass also handles spilling decisions and inserts " { $link ##spill } " and " { $link ##reload } " instructions where needed."
  86 $nl
  87 "GC maps:"
  88 { $subsections
  89   change-insn-gc-roots
  90   emit-##call-gc
  91 }
  92 "Pending intervals:"
  93 { $subsections
  94   activate-interval
  95   add-pending
  96   pending-interval-assoc
  97   expire-old-intervals
  98   remove-pending
  99 }
 100 "Spilling & reloading:"
 101 { $subsections
 102   insert-reload
 103   insert-spill
 104 }
 105 "Vreg transformations:"
 106 { $subsections
 107   vreg>reg
 108   vreg>spill-slot
 109   vregs>regs
 110 } ;
 111
 112 ABOUT: "compiler.cfg.linear-scan.assignment"