1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
Sketch of the new arrivals:
MkZipCfg Constructor functions for control-flow graphs.
Not understandable in its entirety without reference
to ZipCfg, but nevertheless a worthy starting point,
as it is a good deal simpler than full ZipCfg.
MkZipCfg is polymorphic in the types of middle and last
nodes.
ZipCfg Describes a zipper-like representation for true basic-block
control-flow graphs. A block has a single entry point,
which is a always a label, followed by zero or mode 'middle
nodes', each of which represents an uninterruptible
single-entry, single-exit computation, then finally a 'last
node', which may have zero or more successors. A special
'exit node' is used for splicing together graphs.
In addition to three representations of flow graphs, the
module provides a surfeit of functions for observing and
modifying graphs and related data:
- Block IDs, sets and environments thereof
- supply of fresh block IDS (as String -> UniqSM BlockId)
- myriad functions for splicing graphs
- postorder_dfs layout of blocks
- folding, mapping, and translation functions
ZipCFG is polymorphic in the type of middle and last nodes.
CmmExpr Code for C-- expressions, which is shared among old and new
representations of flow graphs. Of primary interest is the
type class UserOfLocalRegs and its method foldRegsUsed,
which is sufficiently overloaded to be used against
expressions, statements, formals, hinted formals, and so
on. This overloading greatly clarifies the computation of
liveness as well as some other analyses.
ZipCfgCmm Types to instantiate ZipCfg for C--: middle and last nodes,
and a bunch of abbreviations of types in ZipCfg and Cmm.
Also provides suitable constructor functions for building
graphs from Cmm statements.
CmmLiveZ A good example of a very simple dataflow analysis. It
computes the set of live local registers at each point.
DFMonad Support for dataflow analysis and dataflow-based
transformation. This module needs work. Includes
DataflowLattice - for tracking dataflow facts (good)
DFA - monad for iterative dataflow analysis (OK)
DFM - monad for iterative dataflow analysis and rewriting (OK)
DFTx - monad to track Whalley/Davidson transactions (ugly)
type class DataflowAnalysis - operations common to DFA, DFM
Some dodgy bits are
subAnalysis, which may not be right
ZipDataflow Iteratively solve forward and backward dataflow problems over
flow graphs. Polymorphic in the type of graph and in the
lattice of dataflow facts. Supports the incremental
rewriting technique described by Lerner, Grove, and Chambers
in POPL 2002. The code is a mess and is still being
sorted out.
CmmTx A simple monad for tracking when a transformation has
occurred (something has changed).
CmmCvt Converts between Cmm and ZipCfgCmm representations.
CmmProcPointZ One module that performs three analyses and
transformations:
1. Using Michael Adams's iterative algorithm, computes a
minimal set of proc points that enable code to be
generated without copying any basic blocks.
2. Assigns a protocol to each proc point. The assigner
is rigged to enable the 'Adams optimization' whereby
we attempt to eliminate return continuations by
making procedures return directly to join points.
Arguably this could be done by a separate rewriting
pass to perform earlier.
3. Insert CopyIn and CopyOut nodes where needed
according to the protocols.
CmmSpillReload Inserts spills and reloads to establish the invariant that
at a safe call, there are no live variables in registers.
CmmCPSZ The CPS transformation so far.
CmmContFlowOpt Branch-chain elimination and elimination of unreachable code.
CmmCvt Conversion to and from the new format.
CmmOpt Changed optimization to use 'foldRegsUsed'; eliminated
significant duplication of code.
PprCmmZ Prettyprinting functions related to ZipCfg and ZipCfgCmm
|
