1 ! Copyright (C) 2009 Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors assocs deques dlists kernel locals sequences lexer
4 namespaces functors compiler.cfg.rpo compiler.cfg.utilities
5 compiler.cfg.predecessors compiler.cfg ;
6 IN: compiler.cfg.dataflow-analysis
8 GENERIC: join-sets ( sets bb dfa -- set )
9 GENERIC: transfer-set ( in-set bb dfa -- out-set )
10 GENERIC: block-order ( cfg dfa -- bbs )
11 GENERIC: successors ( bb dfa -- seq )
12 GENERIC: predecessors ( bb dfa -- seq )
16 MIXIN: dataflow-analysis
18 : <dfa-worklist> ( cfg dfa -- queue )
19 block-order <hashed-dlist> [ push-all-front ] keep ;
21 :: compute-in-set ( bb out-sets dfa -- set )
22 ! Only consider initialized sets.
23 bb kill-block?>> [ f ] [
25 [ out-sets key? ] filter
30 :: update-in-set ( bb in-sets out-sets dfa -- ? )
31 bb out-sets dfa compute-in-set
32 bb in-sets maybe-set-at ; inline
34 :: compute-out-set ( bb in-sets dfa -- set )
35 bb kill-block?>> [ f ] [ bb in-sets at bb dfa transfer-set ] if ;
37 :: update-out-set ( bb in-sets out-sets dfa -- ? )
38 bb in-sets dfa compute-out-set
39 bb out-sets maybe-set-at ; inline
41 :: dfa-step ( bb in-sets out-sets dfa work-list -- )
42 bb in-sets out-sets dfa update-in-set [
43 bb in-sets out-sets dfa update-out-set [
44 bb dfa successors work-list push-all-front
48 :: run-dataflow-analysis ( cfg dfa -- in-sets out-sets )
49 cfg needs-predecessors drop
51 H{ } clone :> out-sets
52 cfg dfa <dfa-worklist> :> work-list
53 work-list [ in-sets out-sets dfa work-list dfa-step ] slurp-deque
57 M: dataflow-analysis join-sets 2drop assoc-refine ;
59 FUNCTOR: define-analysis ( name -- )
61 name-analysis DEFINES-CLASS ${name}-analysis
62 name-ins DEFINES ${name}-ins
63 name-outs DEFINES ${name}-outs
64 name-in DEFINES ${name}-in
65 name-out DEFINES ${name}-out
69 SINGLETON: name-analysis
73 : name-in ( bb -- set ) name-ins get at ;
77 : name-out ( bb -- set ) name-outs get at ;
81 ! ! ! Forward dataflow analysis
83 MIXIN: forward-analysis
84 INSTANCE: forward-analysis dataflow-analysis
86 M: forward-analysis block-order drop reverse-post-order ;
87 M: forward-analysis successors drop successors>> ;
88 M: forward-analysis predecessors drop predecessors>> ;
90 FUNCTOR: define-forward-analysis ( name -- )
92 name-analysis IS ${name}-analysis
93 name-ins IS ${name}-ins
94 name-outs IS ${name}-outs
95 compute-name-sets DEFINES compute-${name}-sets
99 INSTANCE: name-analysis forward-analysis
101 : compute-name-sets ( cfg -- )
102 name-analysis run-dataflow-analysis
103 [ name-ins set ] [ name-outs set ] bi* ;
107 ! ! ! Backward dataflow analysis
109 MIXIN: backward-analysis
110 INSTANCE: backward-analysis dataflow-analysis
112 M: backward-analysis block-order drop post-order ;
113 M: backward-analysis successors drop predecessors>> ;
114 M: backward-analysis predecessors drop successors>> ;
116 FUNCTOR: define-backward-analysis ( name -- )
118 name-analysis IS ${name}-analysis
119 name-ins IS ${name}-ins
120 name-outs IS ${name}-outs
121 compute-name-sets DEFINES compute-${name}-sets
125 INSTANCE: name-analysis backward-analysis
127 : compute-name-sets ( cfg -- )
128 \ name-analysis run-dataflow-analysis
129 [ name-outs set ] [ name-ins set ] bi* ;
135 SYNTAX: FORWARD-ANALYSIS:
136 scan [ define-analysis ] [ define-forward-analysis ] bi ;
138 SYNTAX: BACKWARD-ANALYSIS:
139 scan [ define-analysis ] [ define-backward-analysis ] bi ;