llvm dev - Oct 2007 - [LLVMdev] Case in Case optimisation: worthwhile?

Hi,

The back end of our functional compiler often generates sequential
switch statements in LLVM typed assembly that scrutinize on the same
expression. For example, in C syntax:

#1
switch( e )
{
  case e2:
  {
    e3
  }
  ...
}
switch( e )
{
  case e2:
  {
    e4
  }
  ...
}

In this case, it would be nice if the second switch would be embedded in
each arm of the first switch. Because the set of values of e are known
in each arm, it is possible to remove the switch in that arm.

So lets say we translate it to

#2
switch( e )
{
  case e2:
  {
    e3

    switch( e )
    {
      case e2:
      {
        e4
      }
      ...
    }
  }
  ...
}

Then the existing LLVM transformations reduce this further to:

#3
switch( e )
{
  case e2:
  {
    e3
    e4
  }
}

So the only problem is that LLVM does not perform the step from #1 to #2.

This transformation is not only beneficial in the case described above
but also in cases as the following:

#4
int c = 0;
switch( e )
{
  case e2:
  {
    e3
    c = e5
  }
...
}

switch( c )
{
...
}

If the second switch would be embedded in each arm of the first one, the
second switch can be eliminated. The only disadvantage that I see is the
possible code duplication,

So basicly I want to know the following:

1) Do you think this optimisation is nice to implement in LLVM, then  I
am not the only one benefitting from it, or should I apply it on the
intermediate language in the back end.
2) If I want to implement this in LLVM, can somebody give me pointers to
the source files to start with?

Thanks!

-- John van Schie

On Thu, 4 Oct 2007, John van Schie wrote:
> So basicly I want to know the following:
>
> 1) Do you think this optimisation is nice to implement in LLVM, then  I
> am not the only one benefitting from it, or should I apply it on the
> intermediate language in the back end.
Yes, this should go into LLVM.
> 2) If I want to implement this in LLVM, can somebody give me pointers to
> the source files to start with?
This sort of optimization is the thing that predsimplify was supposed to 
fix.  The basic issue is that you need to know that in "switch (x) { case 
14:" in the region dominated by the 'case 14' that x is equal to
14.
Knowing and tracking this information allows simplifications, for example 
another switch on x can be reduced to switch on 14.. which turns into an 
unconditional branch.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/