Minor wibbles
[packages/hoopl.git] / src / LOOPS
1 Thoughts about loop-based analyses
2 ==================================
3
4 A loop analysis will want to have certain inputs, perhaps including
5
6   - A set of loop headers
7   - The dominance relation
8   - The reachability relation
9
10 Let's assume
11
12   type Header  = Label
13   type Headers = LabelSet
14
15 We can imagine doing loop analyses as follows:
16
17   - The dataflow fact is `Map Header f` where `f` is a lattice of
18     facts.
19
20   - If at a given point (edge) in the flow graph, header `H` is a key in the
21     map, then that point is reachable from `H`, and the fact stored in
22     the map is true on all paths that originate at `H` and terminate
23     at that point.
24
25   - If a given point (edge) in the flow graph cannot reach `H`, it is
26     safe (but not necessary) to delete `H` from the map.  It is
27     probably worth deleting `H` if possible, because if nothing else
28     it will keep the program from allocating one thunk per node `N`
29     that is reachable from `H` but does not reach `H`.
30
31   - If at a given point in the flow graph, `H` is not a key in the map,
32     then we expect either the point is not reachable from `H` or it
33     does not reach `H`.  That is, we want `H` to be a key at exactly
34     those points that are in a loop containing `H`.
35
36   - If a join function gets two maps and `H` is a key in just one of
37     them, the map without `H` can be ignored, since that edge is not
38     yet known to be reachable from `H`.  We can therefore use the
39     empty map as a bottom element.
40
41   - If `join` is the join function on `f`, the join function on maps
42     can *almost* be defined using `Data.Map.unionWithKey f`, but
43     unfortunately not, because of the beastly `ChangeFlag`.
44     A person like Chris Rice should explore a suitable higher-order
45     function for lifting joins into finite maps.