case optimizations

Matthew Fluet fluet@CS.Cornell.EDU
Wed, 5 Dec 2001 15:23:52 -0500 (EST)


> case x of A => L1 | B => L2 | _ => L1
> -->
> case x of B => L2 | _ => L1
> 
> 
> case x of A => L1 | B => L2 | C => L2
> -->
> case x of A => L1 | _ => L2  
> if B and C are non-value-carrying

These two aren't that hard; could they go in the shrinker?
I say that, because they are completely local transformations -- it
doesn't matter what is passed for x.

> case x of 
>     A => LA
>   | _ => (case x of 
>              B => LB
>            | C => LC
>            | _ => LD)
> -->
> case x of
>     A => LA
>   | B => LB
>   | C => LC
>   | D => LD


The more annoying case is

 case x of 
     A => LA
   | _ => (case x of 
              A => LA'
            | B => LB
            | C => LC
            | _ => LD)
 -->
 case x of
     A => LA
   | B => LB
   | C => LC
   | D => LD

Let me think about these and see if they fit in.  
Part of the problem is that the transformations above are always good.
KnownCase is going to need an inliner like metric.  Initially, I was
thinking of just checking if we ever knew what x was when at a transfer to
a block of the form
 LX (??) = case x of A => LA | B => LB | ... | _ => LD

The more troubling cases are when we have blocks like
 LX (??) = 
   s1
   s2
   ...
   sN
   case x of A => LA | B => LB | ... | _ => LD

If there is a place where x is known to be an A and place where x is known
to be B, then do we want to duplicate s1...sN?  Maybe up to some small
value of N, but certainly not in all cases.