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

   1 ! Copyright (C) 2008, 2010 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel accessors assocs sequences namespaces make locals
   4 cpu.architecture
   5 compiler.cfg
   6 compiler.cfg.rpo
   7 compiler.cfg.registers
   8 compiler.cfg.instructions
   9 compiler.cfg.linear-scan.numbering
  10 compiler.cfg.linear-scan.live-intervals
  11 compiler.cfg.linear-scan.allocation
  12 compiler.cfg.linear-scan.allocation.state
  13 compiler.cfg.linear-scan.assignment
  14 compiler.cfg.linear-scan.resolve ;
  15 FROM: assocs => change-at ;
  16 IN: compiler.cfg.linear-scan
  17
  18 ! References:
  19
  20 ! Linear Scan Register Allocation
  21 ! by Massimiliano Poletto and Vivek Sarkar
  22 ! http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf
  23
  24 ! Linear Scan Register Allocation for the Java HotSpot Client Compiler
  25 ! by Christian Wimmer
  26 ! and http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/
  27
  28 ! Quality and Speed in Linear-scan Register Allocation
  29 ! by Omri Traub, Glenn Holloway, Michael D. Smith
  30 ! http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8435
  31
  32 ! SSA liveness must have been computed already
  33
  34 :: (linear-scan) ( cfg machine-registers -- )
  35     cfg number-instructions
  36     cfg compute-live-intervals machine-registers allocate-registers
  37     cfg assign-registers
  38     cfg resolve-data-flow
  39     cfg check-numbering ;
  40
  41 : admissible-registers ( cfg -- regs )
  42     machine-registers swap frame-pointer?>> [
  43         [ [ frame-reg = not ] filter ] assoc-map
  44     ] when ;
  45
  46 : linear-scan ( cfg -- cfg' )
  47     dup dup admissible-registers (linear-scan) ;