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 FROM: namespaces => set ;
   6 IN: compiler.cfg.rpo
   7
   8 SYMBOL: visited
   9
  10 : post-order-traversal ( bb -- )
  11     dup visited get key? [ drop ] [
  12         dup visited get conjoin
  13         [
  14             successors>> <reversed>
  15             [ post-order-traversal ] each
  16         ] [ , ] bi
  17     ] if ;
  18
  19 : number-blocks ( blocks -- )
  20     dup length iota <reversed>
  21     [ >>number drop ] 2each ;
  22
  23 : post-order ( cfg -- blocks )
  24     dup post-order>> [ ] [
  25         [
  26             H{ } clone visited set
  27             dup entry>> post-order-traversal
  28         ] { } make dup number-blocks
  29         >>post-order post-order>>
  30     ] ?if ;
  31
  32 : reverse-post-order ( cfg -- blocks )
  33     post-order <reversed> ; inline
  34
  35 : each-basic-block ( cfg quot -- )
  36     [ reverse-post-order ] dip each ; inline
  37
  38 : optimize-basic-block ( bb quot -- )
  39     [ drop basic-block set ]
  40     [ change-instructions drop ] 2bi ; inline
  41
  42 : local-optimization ( ... cfg quot: ( ... insns -- ... insns' ) -- ... cfg' )
  43     dupd '[ _ optimize-basic-block ] each-basic-block ; inline
  44
  45 : needs-post-order ( cfg -- cfg' )
  46     dup post-order drop ;