HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
1 | KnownCase |
| 2 | ========= | |
| 3 | ||
| 4 | <:KnownCase:> is an optimization pass for the <:SSA:> | |
| 5 | <:IntermediateLanguage:>, invoked from <:SSASimplify:>. | |
| 6 | ||
| 7 | == Description == | |
| 8 | ||
| 9 | This pass duplicates and simplifies `Case` transfers when the | |
| 10 | constructor of the scrutinee is known. | |
| 11 | ||
| 12 | Uses <:Restore:>. | |
| 13 | ||
| 14 | For example, the program | |
| 15 | [source,sml] | |
| 16 | ---- | |
| 17 | val rec last = | |
| 18 | fn [] => 0 | |
| 19 | | [x] => x | |
| 20 | | _ :: l => last l | |
| 21 | ||
| 22 | val _ = 1 + last [2, 3, 4, 5, 6, 7] | |
| 23 | ---- | |
| 24 | ||
| 25 | gives rise to the <:SSA:> function | |
| 26 | ||
| 27 | ---- | |
| 28 | fun last_0 (x_142) = loopS_1 () | |
| 29 | loopS_1 () | |
| 30 | loop_11 (x_142) | |
| 31 | loop_11 (x_143) | |
| 32 | case x_143 of | |
| 33 | nil_1 => L_73 | ::_0 => L_74 | |
| 34 | L_73 () | |
| 35 | return global_5 | |
| 36 | L_74 (x_145, x_144) | |
| 37 | case x_145 of | |
| 38 | nil_1 => L_75 | _ => L_76 | |
| 39 | L_75 () | |
| 40 | return x_144 | |
| 41 | L_76 () | |
| 42 | loop_11 (x_145) | |
| 43 | ---- | |
| 44 | ||
| 45 | which is simplified to | |
| 46 | ||
| 47 | ---- | |
| 48 | fun last_0 (x_142) = loopS_1 () | |
| 49 | loopS_1 () | |
| 50 | case x_142 of | |
| 51 | nil_1 => L_73 | ::_0 => L_118 | |
| 52 | L_73 () | |
| 53 | return global_5 | |
| 54 | L_118 (x_230, x_229) | |
| 55 | L_74 (x_230, x_229, x_142) | |
| 56 | L_74 (x_145, x_144, x_232) | |
| 57 | case x_145 of | |
| 58 | nil_1 => L_75 | ::_0 => L_114 | |
| 59 | L_75 () | |
| 60 | return x_144 | |
| 61 | L_114 (x_227, x_226) | |
| 62 | L_74 (x_227, x_226, x_145) | |
| 63 | ---- | |
| 64 | ||
| 65 | == Implementation == | |
| 66 | ||
| 67 | * <!ViewGitFile(mlton,master,mlton/ssa/known-case.fun)> | |
| 68 | ||
| 69 | == Details and Notes == | |
| 70 | ||
| 71 | One interesting aspect of <:KnownCase:>, is that it often has the | |
| 72 | effect of unrolling list traversals by one iteration, moving the | |
| 73 | `nil`/`::` check to the end of the loop, rather than the beginning. |