basis/compiler/cfg/stacks/local/local-docs.factor

   1 USING: assocs compiler.cfg compiler.cfg.instructions
   2 compiler.cfg.registers compiler.cfg.stacks hash-sets hashtables
   3 help.markup help.syntax kernel math sequences ;
   4 IN: compiler.cfg.stacks.local
   5
   6 HELP: begin-local-analysis
   7 { $values { "basic-block" basic-block } }
   8 { $description "Begins the local analysis of the block. The height slot of the block is initialized with the resulting height of the last block." } ;
   9
  10 HELP: emit-insns
  11 { $values { "replaces" sequence } { "state" sequence } }
  12 { $description "Insert height and stack changes prior to the last instruction." } ;
  13
  14 HELP: end-local-analysis
  15 { $values { "basic-block" basic-block } }
  16 { $description "Called to end the local analysis of a block. The word fills in the blocks slots " { $slot "replaces" } ", " { $slot "peeks" } " and " { $slot "kills" } " with what the blocks replaces, peeks and kill locations are." } ;
  17
  18 HELP: global-loc>local
  19 { $values { "loc" loc } { "height-state" height-state } { "loc'" loc } }
  20 { $description "Translates an absolute stack location to one that is relative to the given height state." }
  21 { $examples
  22   { $example
  23     "USING: compiler.cfg.stacks.local compiler.cfg.registers namespaces prettyprint ;"
  24     "D: 7 T{ height-state f 3 0 0 0 } global-loc>local ."
  25     "D: 4"
  26   }
  27 }
  28 { $see-also height-state local-loc>global } ;
  29
  30 HELP: height-state
  31 { $description "A tuple which keeps track of the stacks heights and increments of a " { $link basic-block } " during local analysis. The idea is that if the stack change instructions are tracked, then multiple changes can be folded into one. It has the following slots:"
  32   { $slots
  33     {
  34         "ds-begin"
  35         "Datastack height at the beginning of the block."
  36     }
  37     {
  38         "rs-begin"
  39         "Retainstack height at the beginning of the block."
  40     }
  41     {
  42         "ds-inc"
  43         "Datastack change during the block."
  44     }
  45     {
  46         "rs-inc"
  47         "Retainstack change during the block."
  48     }
  49   }
  50 }
  51 { $see-also inc-stack reset-incs } ;
  52
  53 HELP: height-state>insns
  54 { $values { "height-state" height-state } { "insns" sequence } }
  55 { $description "Converts a " { $link height-state } " tuple to 0-2 stack height change instructions." }
  56 { $examples
  57   "In this example the datastacks height is increased by 4 and the retainstacks decreased by 2."
  58   { $example
  59     "USING: compiler.cfg.stacks.local prettyprint ;"
  60     "T{ height-state f 0 0 4 -2 } height-state>insns ."
  61     "{ T{ ##inc { loc D: 4 } } T{ ##inc { loc R: -2 } } }"
  62   }
  63 } ;
  64
  65 HELP: inc-stack
  66 { $values { "loc" loc } }
  67 { $description "Increases or decreases the data or retain stack depending on if loc is a " { $link ds-loc } " or " { $link rs-loc } " instance. An " { $link ##inc } " instruction will later be inserted." } ;
  68
  69 HELP: local-loc>global
  70 { $values { "loc" loc } { "height-state" height-state } { "loc'" loc } }
  71 { $description "Translates a stack location relative to a block to an absolute one. The word does the opposite to " { $link global-loc>local } "." } ;
  72
  73 HELP: loc>vreg
  74 { $values { "loc" loc } { "vreg" "virtual register" } }
  75 { $description "Maps a stack location to a virtual register." } ;
  76
  77 HELP: local-kill-set
  78 { $values
  79   { "ds-begin" integer }
  80   { "ds-inc" integer }
  81   { "rs-begin" integer }
  82   { "rs-inc" integer }
  83   { "set" hash-set }
  84 }
  85 { $description "The set of stack locations that was killed. Locations on a stack are deemed killed if that stacks height is decremented." }
  86 { $see-also compute-local-kill-set } ;
  87
  88 HELP: local-peek-set
  89 { $var-description "A " { $link hash-set } " used during local block analysis to keep track of peeked stack locations." } ;
  90
  91 HELP: peek-loc
  92 { $values { "loc" loc } { "vreg" "virtual register" } }
  93 { $description "Retrieves the virtual register at the given stack location. If no register has been stored at that location, then a new vreg is returned." } ;
  94
  95 HELP: replace-loc
  96 { $values { "vreg" "virtual register" } { "loc" loc } }
  97 { $description "Registers that the absolute stack location " { $snippet "loc" } " should be overwritten with the contents of the virtual register." }
  98 { $see-also replaces } ;
  99
 100 HELP: replaces
 101 { $var-description "An " { $link assoc } " that maps from stack locations to virtual registers that were put on the stack during the local analysis phase. " { $link ds-push } " and similar words writes to it." }
 102 { $see-also replace-loc } ;
 103
 104 ARTICLE: "compiler.cfg.stacks.local" "Local stack analysis"
 105 "For each " { $link basic-block } " in the " { $link cfg } ", local stack analysis is performed. The analysis is started right after the block is created with " { $link begin-local-analysis } " and finished with " { $link end-local-analysis } ", when the construction of the block is complete. During the analysis, three sets containing stack locations are built:"
 106 { $slots
 107   { "peeks" { " all stack locations that the block reads before writing" } }
 108   { "replaces" { " all stack locations that the block writes" } }
 109   { "kills" { " all stack locations which become unavailable after the block ends because of the stack height being decremented. For example, if the block contains " { $link drop } ", then D: 0 will be contained in kills because that stack location will not be live anymore." } }
 110 }
 111 "This is done while constructing the CFG. These sets are then used by the " { $link end-stack-analysis } " word to emit optimal sequences of " { $link ##peek } " and " { $link ##replace } " instructions to the cfg."
 112 $nl
 113 "For example, the code [ dup dup dup ] will only execute ##peek once, instead of three time which a 'non-lazy' method would."
 114 $nl
 115 "Words for reading the stack state:"
 116 { $subsections
 117   peek-loc
 118   global-loc>local
 119   local-loc>global
 120 }
 121 "Words for writing the stack state:"
 122 { $subsections
 123   inc-stack
 124   replace-loc
 125 }
 126 "Beginning and ending analysis:"
 127 { $subsections
 128   begin-local-analysis
 129   end-local-analysis
 130 }
 131 "Temporary variables that keeps track of the block's read and written stack locations:"
 132 { $subsections
 133   local-peek-set
 134   replaces
 135 } ;
 136
 137
 138 ABOUT: "compiler.cfg.stacks.local"