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