[LLVMdev] Case in Case optimisation: worthwhile?

[John van Schie]

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