HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
1 | XMLShrink |
| 2 | ========= | |
| 3 | ||
| 4 | XMLShrink is an optimization pass for the <:XML:> | |
| 5 | <:IntermediateLanguage:>, invoked from <:XMLSimplify:>. | |
| 6 | ||
| 7 | == Description == | |
| 8 | ||
| 9 | This pass performs optimizations based on a reduction system. | |
| 10 | ||
| 11 | == Implementation == | |
| 12 | ||
| 13 | * <!ViewGitFile(mlton,master,mlton/xml/shrink.sig)> | |
| 14 | * <!ViewGitFile(mlton,master,mlton/xml/shrink.fun)> | |
| 15 | ||
| 16 | == Details and Notes == | |
| 17 | ||
| 18 | The simplifier is based on <!Cite(AppelJim97, Shrinking Lambda | |
| 19 | Expressions in Linear Time)>. | |
| 20 | ||
| 21 | The source program may contain functions that are only called once, or | |
| 22 | not even called at all. Match compilation introduces many such | |
| 23 | functions. In order to reduce the program size, speed up later | |
| 24 | phases, and improve the flow analysis, a source to source simplifier | |
| 25 | is run on <:XML:> after type inference and match compilation. | |
| 26 | ||
| 27 | The simplifier implements the reductions shown below. The reductions | |
| 28 | eliminate unnecessary declarations (see the side constraint in the | |
| 29 | figure), applications where the function is immediate, and case | |
| 30 | statements where the test is immediate. Declarations can be | |
| 31 | eliminated only when the expression is nonexpansive (see Section 4.7 | |
| 32 | of the <:DefinitionOfStandardML: Definition>), which is a syntactic | |
| 33 | condition that ensures that the expression has no effects | |
| 34 | (assignments, raises, or nontermination). The reductions on case | |
| 35 | statements do not show the other irrelevant cases that may exist. The | |
| 36 | reductions were chosen so that they were strongly normalizing and so | |
| 37 | that they never increased tree size. | |
| 38 | ||
| 39 | * {empty} | |
| 40 | + | |
| 41 | -- | |
| 42 | [source,sml] | |
| 43 | ---- | |
| 44 | let x = e1 in e2 | |
| 45 | ---- | |
| 46 | ||
| 47 | reduces to | |
| 48 | ||
| 49 | [source,sml] | |
| 50 | ---- | |
| 51 | e2 [x -> e1] | |
| 52 | ---- | |
| 53 | ||
| 54 | if `e1` is a constant or variable or if `e1` is nonexpansive and `x` occurs zero or one time in `e2` | |
| 55 | -- | |
| 56 | ||
| 57 | * {empty} | |
| 58 | + | |
| 59 | -- | |
| 60 | [source,sml] | |
| 61 | ---- | |
| 62 | (fn x => e1) e2 | |
| 63 | ---- | |
| 64 | ||
| 65 | reduces to | |
| 66 | ||
| 67 | [source,sml] | |
| 68 | ---- | |
| 69 | let x = e2 in e1 | |
| 70 | ---- | |
| 71 | -- | |
| 72 | ||
| 73 | * {empty} | |
| 74 | + | |
| 75 | -- | |
| 76 | [source,sml] | |
| 77 | ---- | |
| 78 | e1 handle e2 | |
| 79 | ---- | |
| 80 | ||
| 81 | reduces to | |
| 82 | ||
| 83 | [source,sml] | |
| 84 | ---- | |
| 85 | e1 | |
| 86 | ---- | |
| 87 | ||
| 88 | if `e1` is nonexpansive | |
| 89 | -- | |
| 90 | ||
| 91 | * {empty} | |
| 92 | + | |
| 93 | -- | |
| 94 | [source,sml] | |
| 95 | ---- | |
| 96 | case let d in e end of p1 => e1 ... | |
| 97 | ---- | |
| 98 | ||
| 99 | reduces to | |
| 100 | ||
| 101 | [source,sml] | |
| 102 | ---- | |
| 103 | let d in case e of p1 => e1 ... end | |
| 104 | ---- | |
| 105 | -- | |
| 106 | ||
| 107 | * {empty} | |
| 108 | + | |
| 109 | -- | |
| 110 | [source,sml] | |
| 111 | ---- | |
| 112 | case C e1 of C x => e2 | |
| 113 | ---- | |
| 114 | ||
| 115 | reduces to | |
| 116 | ||
| 117 | [source,sml] | |
| 118 | ---- | |
| 119 | let x = e1 in e2 | |
| 120 | ---- | |
| 121 | -- |