MLton MLTONWIKIVERSION

KnownCase

Home Index

KnownCase is an optimization pass for the SSA IntermediateLanguage, invoked from SSASimplify.

## Description

This pass duplicates and simplifies `Case` transfers when the constructor of the scrutinee is known.

Uses Restore.

For example, the program

    val rec last =
       fn [] => 0
        | [x] => x
        | _ :: l => last l

    val _ = 1 + last [2, 3, 4, 5, 6, 7]

gives rise to the SSA function

    fun last_0 (x_142) = loopS_1 ()
      loopS_1 ()
        loop_11 (x_142)
      loop_11 (x_143)
        case x_143 of
          nil_1 => L_73 | ::_0 => L_74
      L_73 ()
        return global_5
      L_74 (x_145, x_144)
        case x_145 of
          nil_1 => L_75 | _ => L_76
      L_75 ()
        return x_144
      L_76 ()
        loop_11 (x_145)

which is simplified to

    fun last_0 (x_142) = loopS_1 ()
      loopS_1 ()
        case x_142 of
          nil_1 => L_73 | ::_0 => L_118
      L_73 ()
        return global_5
      L_118 (x_230, x_229)
        L_74 (x_230, x_229, x_142)
      L_74 (x_145, x_144, x_232)
        case x_145 of
          nil_1 => L_75 | ::_0 => L_114
      L_75 ()
        return x_144
      L_114 (x_227, x_226)
        L_74 (x_227, x_226, x_145)

## Implementation

known-case.sig known-case.fun

## Details and Notes

One interesting aspect of KnownCase, is that it often has the effect of unrolling list traversals by one iteration, moving the `nil`/`::` check to the end of the loop, rather than the beginning.

Last edited on 2006-11-02 17:54:28 by MatthewFluet.