knownCase pass

[Matthew Fluet]

> One other thing that I noticed about knownCase is in compiling the
> last function.
> 
> ----------------------------------------
> val rec last =
>    fn [] => 0
>     | [x] => x
>     | _ :: l => last l
> 
> val _ = 1 + last [2, 3, 4, 5, 6, 7]
> ----------------------------------------
>    
> The resulting SSA, for which I have included the dot below, has a
> knownCase-style optimization missing.  I would like to see the default
> branch for L_13 jump directly back to L_13, instead of going through
> L_11 and L_12.  Would another round of knownCase get it?  Could it be
> gotten in the first round?

I checked in an update to knownCase that does the "right thing" on the
above.  Out of curiosity, I wrote a little benchmark that repeatedly took
the last of a long list and compared with and without knownCase.
Disappointingly, almost no improvement.

But, as an interesting example of what knownCase can do, look at the dot
files for the following with and without knownCase.

----------------------------------------
val rec last =
   fn nil => 0
    | x::nil => x
    | x::_::nil => x
    | _ :: l => last l
val _ = 1 + last [2, 3, 4, 5, 6, 7]
----------------------------------------

After unrolling the loop a little, the restore pass introduces a variable
to track the last seen element of the list, which avoids the need for
repeated cons tests.