basis/compiler/cfg/rpo/rpo.factor

   1 ! Copyright (C) 2008, 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel accessors namespaces make math sequences sets
   4 assocs fry compiler.cfg compiler.cfg.instructions ;
   5 IN: compiler.cfg.rpo
   6
   7 SYMBOL: visited
   8
   9 : post-order-traversal ( bb -- )
  10     dup visited get key? [ drop ] [
  11         dup visited get conjoin
  12         [
  13             successors>> <reversed>
  14             [ post-order-traversal ] each
  15         ] [ , ] bi
  16     ] if ;
  17
  18 : number-blocks ( blocks -- )
  19     dup length iota <reversed>
  20     [ >>number drop ] 2each ;
  21
  22 : post-order ( cfg -- blocks )
  23     dup post-order>> [ ] [
  24         [
  25             H{ } clone visited set
  26             dup entry>> post-order-traversal
  27         ] { } make dup number-blocks
  28         >>post-order post-order>>
  29     ] ?if ;
  30
  31 : reverse-post-order ( cfg -- blocks )
  32     post-order <reversed> ; inline
  33
  34 : each-basic-block ( cfg quot -- )
  35     [ reverse-post-order ] dip each ; inline
  36
  37 : optimize-basic-block ( bb quot -- )
  38     [ drop basic-block set ]
  39     [ change-instructions drop ] 2bi ; inline
  40
  41 : local-optimization ( cfg quot: ( insns -- insns' ) -- cfg' )
  42     dupd '[ _ optimize-basic-block ] each-basic-block ; inline
  43
  44 : needs-post-order ( cfg -- cfg' )
  45     dup post-order drop ;