HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
1 | CommonSubexp |
| 2 | ============ | |
| 3 | ||
| 4 | <:CommonSubexp:> is an optimization pass for the <:SSA:> | |
| 5 | <:IntermediateLanguage:>, invoked from <:SSASimplify:>. | |
| 6 | ||
| 7 | == Description == | |
| 8 | ||
| 9 | It eliminates instances of common subexpressions. | |
| 10 | ||
| 11 | == Implementation == | |
| 12 | ||
| 13 | * <!ViewGitFile(mlton,master,mlton/ssa/common-subexp.fun)> | |
| 14 | ||
| 15 | == Details and Notes == | |
| 16 | ||
| 17 | In addition to getting the usual sorts of things like | |
| 18 | ||
| 19 | * {empty} | |
| 20 | + | |
| 21 | ---- | |
| 22 | (w + 0wx1) + (w + 0wx1) | |
| 23 | ---- | |
| 24 | + | |
| 25 | rewritten to | |
| 26 | + | |
| 27 | ---- | |
| 28 | let val w' = w + 0wx1 in w' + w' end | |
| 29 | ---- | |
| 30 | ||
| 31 | it also gets things like | |
| 32 | ||
| 33 | * {empty} | |
| 34 | + | |
| 35 | ---- | |
| 36 | val a = Array_uninit n | |
| 37 | val b = Array_length a | |
| 38 | ---- | |
| 39 | + | |
| 40 | rewritten to | |
| 41 | + | |
| 42 | ---- | |
| 43 | val a = Array_uninit n | |
| 44 | val b = n | |
| 45 | ---- | |
| 46 | ||
| 47 | `Arith` transfers are handled specially. The _result_ of an `Arith` | |
| 48 | transfer can be used in _common_ `Arith` transfers that it dominates: | |
| 49 | ||
| 50 | * {empty} | |
| 51 | + | |
| 52 | ---- | |
| 53 | val l = (n + m) + (n + m) | |
| 54 | ||
| 55 | val k = (l + n) + ((l + m) handle Overflow => ((l + m) | |
| 56 | handle Overflow => l + n)) | |
| 57 | ---- | |
| 58 | + | |
| 59 | is rewritten so that `(n + m)` is computed exactly once, as are | |
| 60 | `(l + n)` and `(l + m)`. |