HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
1 | Zone |
| 2 | ==== | |
| 3 | ||
| 4 | <:Zone:> is an optimization pass for the <:SSA2:> | |
| 5 | <:IntermediateLanguage:>, invoked from <:SSA2Simplify:>. | |
| 6 | ||
| 7 | == Description == | |
| 8 | ||
| 9 | This pass breaks large <:SSA2:> functions into zones, which are | |
| 10 | connected subgraphs of the dominator tree. For each zone, at the node | |
| 11 | that dominates the zone (the "zone root"), it places a tuple | |
| 12 | collecting all of the live variables at that node. It replaces any | |
| 13 | variables used in that zone with offsets from the tuple. The goal is | |
| 14 | to decrease the liveness information in large <:SSA:> functions. | |
| 15 | ||
| 16 | == Implementation == | |
| 17 | ||
| 18 | * <!ViewGitFile(mlton,master,mlton/ssa/zone.fun)> | |
| 19 | ||
| 20 | == Details and Notes == | |
| 21 | ||
| 22 | Compute strongly-connected components to avoid put tuple constructions | |
| 23 | in loops. | |
| 24 | ||
| 25 | There are two (expert) flags that govern the use of this pass | |
| 26 | ||
| 27 | * `-max-function-size <n>` | |
| 28 | * `-zone-cut-depth <n>` | |
| 29 | ||
| 30 | Zone splitting only works when the number of basic blocks in a | |
| 31 | function is greater than `n`. The `n` used to cut the dominator tree | |
| 32 | is set by `-zone-cut-depth`. | |
| 33 | ||
| 34 | There is currently no attempt to be safe-for-space. That is, the | |
| 35 | tuples are not restricted to containing only "small" values. | |
| 36 | ||
| 37 | In the `HOL` program, the particular problem is the main function, | |
| 38 | which has 161,783 blocks and 257,519 variables -- the product of those | |
| 39 | two numbers being about 41 billion. Now, we're not likely going to | |
| 40 | need that much space since we use a sparse representation. But even | |
| 41 | 1/100th would really hurt. And of course this rules out bit vectors. |