[Bug rtl-optimization/17841] New: Optimizer generating code which runs slower than other code which makes optimizer generate actually optimal code on AMD Duron.

[dhruvbird at yahoo dot com]

When I compile and run this program test01()/test02(), with and without the case
DUMMY: statement, the optimizer generates totally different code, and the code
genetared with case DUMMY: (test01()) is surprizingly faster (about 1s!) than
the code generated without the case DUMMY: statement! One would expect test02()
to be faster normally. What is happening is that when the case numbers are
serial i.e. 1, 2, 3, ... Then the optimizer uses a table lookup to get the
address to jump to, which is an indirect jump. The intel manual says that such
jumps are generally not fast compared to the normal ones because, here
pre-fetching is not possible. However, in the other approach, the optimizer
resorts to the binary search like algorithm, where target pre-fetching is
possible, and hence results in much faster code. This should probably be looked
into, and further timing tests conducted. One nifty thing that I noticed was
that the optimizer evaluates all the returns for all the case statements before
hand, which is quite nice and time saving!

For the current run(1GHz, AMD Duron), the 2 timings were:
test01()
========
real    0m2.581s
user    0m2.580s
sys     0m0.000s

test01()
========
real    0m3.169s
user    0m3.170s
sys     0m0.000s

The code follows:

#include <stdio.h>
#include <stdlib.h>

int g = 0;
#define DUMMY 999

int
test01(int x)
{
  int y, z;
  switch (x)
    {
    case 1:
      y = x + x;
      z = x + y;
      break;

    case 2:
      y = x + 2 * x;
      z = x * y;
      break;

    case 3:
      y = x + x / 2;
      z = x / y;
      break;

    case 4:
      y = x - (2 - x);
      z = x * y;
      break;

    case 6:
      y = -x - 2;
      z = y / x;
      break;

    case 7:
      y = 2 - x;
      z = y / x * y;
      break;

    case 8:
      y = 32 - 23 + x;
      z = x * 3 * y;
      break;

    case 9:
      y = x / 33;
      z = y * x;
      break;

    case DUMMY:

    default:
      y = 0;
      z = y;
    }
  g = z;
  return z;
}


int
test02(int x)
{
  int y, z;
  switch (x)
    {
    case 1:
      y = x + x;
      z = x + y;
      break;

    case 2:
      y = x + 2 * x;
      z = x * y;
      break;

    case 3:
      y = x + x / 2;
      z = x / y;
      break;

    case 4:
      y = x - (2 - x);
      z = x * y;
      break;

    case 6:
      y = -x - 2;
      z = y / x;
      break;

    case 7:
      y = 2 - x;
      z = y / x * y;
      break;

    case 8:
      y = 32 - 23 + x;
      z = x * 3 * y;
      break;

    case 9:
      y = x / 33;
      z = y * x;
      break;

    default:
      y = 0;
      z = y;
    }
  g = z;
  return z;
}



int main()
{
  int x = 9; //rand() % 5;
  int i = 0;

  for (x = 0; x < 50; ++x)
    for (i = 0; i < 700000; ++i)
      test02(i % 11);

  return g;
}

-Dhruv.

-- 
           Summary: Optimizer generating code which runs slower than other
                    code which makes optimizer generate actually optimal
                    code on AMD Duron.
           Product: gcc
           Version: 3.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dhruvbird at yahoo dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i386-pc-linux-gnu
  GCC host triplet: i386-pc-linux-gnu
GCC target triplet: i386-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17841