KnownCase

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.

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.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.