#include "global.h"
#define SAMPLES 5

#define CUTOFF 2.552

#define SLOW_FACTOR 10.0
/* SLOW_FACTOR was 100.0 for stock benchmark */

clock_t ticks_per_sec = 0;

int test(int ok,
         FunPar base_case,
         FunPar test_case,
         int *data,
         int n,
         char *id);
long int determine_iterations(FunPar base_case,
                              int *data);

void collect_timings(long int iterations,
                     FunPar routine,
                     int *data,
                     double *times);
double mean(double *times);
double variance(double mean, double *times);
extern void dead_test1(int *data);
extern void dead_test2(int *data);
extern void dead_test3(int *data);
extern void dead_test4(int *data);
extern void dead_test5(int *data);
extern void dead_test6(int *data);
extern void dead_test7(int *data);
extern void dead_test8(int *data);
extern void dead_test9(int *data);
extern void dead_test10(int *data);
extern void dead_test11(int *data);
extern void dead_result1(int *data);
extern void dead_result2(int *data);
extern void dead_result3(int *data);
extern void dead_result4(int *data);
extern void dead_result5(int *data);
extern void dead_result6(int *data);
extern void dead_result7(int *data);
extern void dead_result8(int *data);
extern void dead_result9(int *data);
extern void dead_result10(int *data);
extern void dead_result11(int *data);
extern void cprop_test1(int *data);
extern void cprop_test2(int *data);
extern void cprop_test3(int *data);
extern void cprop_test35(int *data);
extern void cprop_test4(int *data);
extern void cprop_test5(int *data);
extern void cprop_test6(int *data);
extern void cprop_test7(int *data);
extern void cprop_test8(int *data);
extern void cprop_test9(int *data);
extern void cprop_test10(int *data);
extern void cprop_test11(int *data);
extern void cprop_test12(int *data);
extern void cprop_test13(int *data);
extern void cprop_test14(int *data);
extern void cprop_result1(int *data);
extern void cprop_result2(int *data);
extern void cprop_result3(int *data);
extern void cprop_result4(int *data);
extern void cprop_result5(int *data);
extern void cprop_result6(int *data);
extern void cprop_result7(int *data);
extern void cprop_result8(int *data);
extern void cprop_result9(int *data);
extern void cprop_result10(int *data);
extern void cprop_result11(int *data);
extern void cprop_result12(int *data);
extern void cprop_result13(int *data);
extern void cprop_result14(int *data);
extern void vnum_test1(int *);
extern void vnum_test2(int *);
extern void vnum_test3(int *);
extern void vnum_test4(int *);
extern void vnum_test5(int *);
extern void vnum_test6(int *);
extern void vnum_test7(int *);
extern void vnum_test8(int *);
extern void vnum_test9(int *);
extern void vnum_test10(int *);
extern void vnum_test11(int *);
extern void vnum_test12(int *);
extern void vnum_result1(int *);
extern void vnum_result2(int *);
extern void vnum_result3(int *);
extern void vnum_result4(int *);
extern void vnum_result5(int *);
extern void vnum_result6(int *);
extern void vnum_result7(int *);
extern void vnum_result8(int *);
extern void vnum_result9(int *);
extern void vnum_result10(int *);
extern void vnum_result11(int *);
extern void vnum_result12(int *);
extern void motion_test1(int *);
extern void motion_test2(int *);
extern void motion_test3(int *);
extern void motion_test4(int *);
extern void motion_test5(int *);
extern void motion_test6(int *);
extern void motion_test7(int *);
extern void motion_test8(int *);
extern void motion_test9(int *);
extern void motion_test10(int *);
extern void motion_test11(int *);
extern void motion_result1(int *);
extern void motion_result2(int *);
extern void motion_result3(int *);
extern void motion_result4(int *);
extern void motion_result5(int *);
extern void motion_result6(int *);
extern void motion_result7(int *);
extern void motion_result8(int *);
extern void motion_result9(int *);
extern void motion_result10(int *);
extern void motion_result11(int *);
extern void strength_test1(int *);
extern void strength_test2(int *);
extern void strength_test3(int *);
extern void strength_test4(int *);
extern void strength_test5(int *);
extern void strength_test6(int *);
extern void strength_test7(int *);
extern void strength_test8(int *);
extern void strength_test9(int *);
extern void strength_test10(int *);
extern void strength_result1(int *);
extern void strength_result2(int *);
extern void strength_result3(int *);
extern void strength_result4(int *);
extern void strength_result5(int *);
extern void strength_result6(int *);
extern void strength_result7(int *);
extern void strength_result8(int *);
extern void strength_result9(int *);
extern void strength_result10(int *);

int main()
{
  {
    clock_t start, diff;
    {
      if (clock() == -1) {
        fputs("\nThe routine 'clock' is not supported\n", stderr);
        exit(-1);
      }
    }
    start = clock();
    diff = clock() - start;
    while (diff == 0)
      diff = clock() - start;
    ticks_per_sec =  CLOCKS_PER_SEC / diff;
    printf("Timer seems to run at %d ticks/second\n", ticks_per_sec);
  }
  puts("Begin tests, version 0.06");
  {
    int ok;
    puts("Dead code elimination");
    {
      int data[3] = { 0, 1, 2 };
      ok = test(1, dead_result1, dead_test1, data, 1, "basic block");
    }{
      int data[5] = { 0, 1, 2, 3, 4 };
      ok = test(ok, dead_result2, dead_test2, data, 2, "basic block");
    }{
      int data[4] = { 0, 1, 2 };
      ok = test(ok, dead_result3, dead_test3, data, 3, "across basic blocks");
    }{
      int data[5] = { 0, 1, 2, 3, 4 };
      ok = test(ok, dead_result4, dead_test4, data, 4, "across basic blocks");
    }{
      int data[3] = { 2, 1, 2 };
      ok = test(ok, dead_result5, dead_test5, data, 5, "around loops");
    }{
      int data[4] = { 2, 1, 2 };
      ok = test(ok, dead_result6, dead_test6, data, 6, "around loops");
    }{
      int data[3] = { 0, 1, 2 };
      ok = test(1, dead_result7, dead_test7, data, 7, "useless conditionals");
    }{
      int data[3] = { 2, 1, 2 };
      ok = test(ok, dead_result8, dead_test8, data, 8, "useless conditionals");
    }{
      int data[3] = { 0, 1, 2 };
      ok = test(1, dead_result9, dead_test9, data, 9, "useless loops (conservative)");
    }{
      int data[3] = { 2, 1, 2 };
      (void) test(ok, dead_result10, dead_test10, data, 10, "useless loops (aggressive)");
    }{
      int data[3] = { 0, 1, 2 };
      (void) test(1, dead_result11, dead_test11, data, 11, "partially dead");
    }
  }{
    int ok;
    puts("Constant propagation");
    {
      int data[1];
      ok = test(1, cprop_result1, cprop_test1, data, 1, "folding");
    }{
      int data[1];
      ok = test(ok, cprop_result2, cprop_test2, data, 2, "basic block");
    }{
      int data[3] = { 1 };
      ok = test(ok, cprop_result3, cprop_test3, data, 3, "extended basic blocks");
    }{
      int data[3] = { 1 };
      (void) test(ok, cprop_result4, cprop_test4, data, 4, "extended basic blocks");
    }{
      int data[4] = { 1 };
      ok = test(ok, cprop_result5, cprop_test5, data, 5, "dominators");
    }{
      int data[4] = { 1 };
      (void) test(ok, cprop_result6, cprop_test6, data, 6, "dominators");
    }{
      int data[4] = { 1 };
      ok = test(ok, cprop_result7, cprop_test7, data, 7, "dags");
    }{
      int data[4] = { 1 };
      (void) test(ok, cprop_result8, cprop_test8, data, 8, "dags (hard)");
    }{
      int data[3] = { 2 };
      ok = test(ok, cprop_result9, cprop_test9, data, 9, "loops");
    }{
      int data[2] = { 1, 2 };
      ok = test(1, cprop_result10, cprop_test10, data, 10, "conditional constants");
    }{
      int data[3] = { 2 };
      (void) test(ok, cprop_result11, cprop_test11, data, 11, "conditional constants");
    }{
      int data[2] = { 5 };
      ok = test(1, cprop_result12, cprop_test12, data, 12, "conditional-based assertions");
    }{
      int data[3] = { 10, 5 };
      (void) test(ok, cprop_result13, cprop_test13, data, 13, "conditional-based assertions");
    }{
      int data[4] = { 0, 1, 2 };
      (void) test(ok, cprop_result14, cprop_test14, data, 14, "reassociation");
    }
  }{
    int ok;
    puts("Value numbering");
    {
      int data[4] = {0, 1, 2, 3 };
      ok = test(1,  vnum_result1, vnum_test1, data, 1, "expressions");
    }{
      int data[4] = { 0, 1, 2, 3 };
      (void)  test(ok, vnum_result2, vnum_test2, data, 2, "expressions");
    }{
      int data[4] = { 0, 1, 2, 3 };
      ok = test(ok, vnum_result3, vnum_test3, data, 3, "basic block");
    }{
      int data[4] = { 0, 1, 2, 3 };
      (void) test(ok, vnum_result4, vnum_test4, data, 4, "basic block");
    }{
      int data[4] = { 0, 1, 2, 3 };
      ok = test(ok, vnum_result5, vnum_test5, data, 5, "extended basic block");
    }{
      int data[5] = { 0, 1, 2, 3, 4 };
      ok = test(ok, vnum_result6, vnum_test6, data, 6, "dominators");
    }{
      int data[5] = { 0, 1, 2, 3, 4 };
      ok = test(1,  vnum_result7, vnum_test7, data, 7, "global DAGs");
    }{
      int data[5] = { 0, 1, 2, 3, 4 };
      ok = test(ok, vnum_result8, vnum_test8, data, 8, "global loops");
    }{
      int data[3] = { 0, 0 };
      ok = test(1, vnum_result9, vnum_test9, data, 9, "conditional-based assertions");
    }{
      int data[4] = { 0, 0 };
      ok = test(ok, vnum_result10, vnum_test10, data, 10, "conditional-based assertions");
    }{
      int data[4] = { 0, 1, 2, 3 };
      ok = test(1, vnum_result11, vnum_test11, data, 11, "conditional value numbers");
    }{
      int data[4] = { 0, 1, 2, 3 };
      ok = test(ok, vnum_result12, vnum_test12, data, 12, "cprop + vnum");
    }
  }{
    int ok;
    puts("Code motion");
    {
      int data[5] = { 0, 1, 2, 3 };
      ok = test(1, motion_result1, motion_test1, data, 1, "DAGs");
    }{
      int data[6] = { 0, 1, 2, 3 };
      ok = test(ok, motion_result2, motion_test2, data, 2, "DAGs (edge placement)");
    }{
      int data[5] = { 0, 1, 2, 3 };
      ok = test(1, motion_result3, motion_test3, data, 3, "loops");
    }{
      int data[5] = { 0, 1, 2, 3 };
      (void) test(ok, motion_result4, motion_test4, data, 4, "loops (hoisting divide)");
    }{
      int data[5] = { 0, 1, 2, 3 };
      (void) test(ok, motion_result5, motion_test5, data, 5, "irreducible loops");
    }{
      int data[5] = { 0, 1, 0, 3 };
      (void) test(ok, motion_result6, motion_test6, data, 6, "reassociation");
    }{
      int data[5] = { 0, 1, 4, 10 };
      ok = !test(1, motion_result7, motion_test7, data, 7, "aggressive");
    }{
      int data[5] = { 0, 1, 2, 3 };
      (void) test(ok, motion_result8, motion_test8, data, 8, "loop rotation");
    }{
      int data[5] = { 0, 1, 2, 3 };
      (void) test(ok, motion_result9, motion_test9, data, 9, "loop rotation");
    }{
      int data[5] = { 0, 1, 2, 10 };
      (void) test(ok, motion_result10, motion_test10, data, 10, "invariant control structures");
    }{
      int data[5] = { 0, 1, 2, 10 };
      (void) test(ok, motion_result11, motion_test11, data, 11, "loop unswitching");
    }
  }{
    int ok;
    puts("Strength reduction");
    {
      int data[3] = { 0, 22, 2 };
      ok = test(1, strength_result1, strength_test1, data, 1, "iv * constant");
    }{
      int data[3] = { 1, 3, 2 };
      (void) test(ok, strength_result2, strength_test2, data, 2, "iv * rc");
    }{
      int data[4] = { 0, 1, 2, 100 };
      (void) test(ok, strength_result3, strength_test3, data, 3, "iv * iv");
    }{
      int data[4] = { 0, 1, 2, 100 };
      (void) test(ok, strength_result4, strength_test4, data, 4, "irreducible loop");
    }{
      int data[4] = { 0, 1, 2, 100 };
      (void) test(ok, strength_result5, strength_test5, data, 5, "control flow in loop");
    }{
      int data[4] = { 1, 1, 2, 100 };
      (void) test(ok, strength_result6, strength_test6, data, 6, "inc by rc");
    }{
      int data[4] = { 0, 1, 2, 100 };
      (void) test(ok, strength_result7, strength_test7, data, 7, "monotonic iv");
    }{
      int data[4] = { 0, 1, 1, 100 };
      (void) test(ok, strength_result8, strength_test8, data, 8, "mutual iv's");
    }{
      int data[4] = { 0, 1, 1, 100 };
      (void) test(ok, strength_result9, strength_test9, data, 9, "multiple strides");
    }{
      int data[4] = { 0, 1, 1, 20 };
      (void) test(ok, strength_result10, strength_test10, data, 10, "test replacement");
    }
  }
  puts("Tests completed");
  exit(0);
}
int test(int ok,
         FunPar base_case,
         FunPar test_case,
         int *data,
         int n,
         char *id)
{
  int ret_val = 0;
  printf("    %d) %s - ", n, id);
  if (1 /* always test, for now */ || ok) {
    double base_times[SAMPLES], test_times[SAMPLES];
    long int iterations = determine_iterations(base_case, data);
    collect_timings(iterations, test_case, data, test_times);
    collect_timings(iterations, base_case, data, base_times);
    {
      double base_mean = mean(base_times);
      double test_mean = mean(test_times);
      double result = test_mean - base_mean;
      double base_variance = variance(base_mean, base_times);
      double test_variance = variance(test_mean, test_times);
      double sum = base_variance + test_variance;
      if (sum == 0.0) {
        if (result == 0.0)     ret_val = 1;
        else if (result < 0.0) ret_val = -1;
      }
      else {
        result = result * sqrt(SAMPLES / sum);
        if (fabs(result) <= CUTOFF) ret_val = 1;
        else if (result < 0.0)      ret_val = -1;
      }
      if (ret_val > 0)       puts("yes");
      else if (ret_val == 0) puts("no");
      else                   puts("bad test");
      {
        int n = noisy(base_variance) || noisy(test_variance);
        if (n)
          puts("\t(warning -- the timings were not very consistent)");
        if (1 /* always print, for now */ || n || ret_val == -1)
          {
            int i;
            puts("\nTimings\n\tbase-case\ttest-case");
            for (i=0; i<SAMPLES; i++)
              printf("\t%-9.3f\t%-9.3f\n", base_times[i], test_times[i]);
            printf("means\t%-9.3f\t%-9.3f\n", base_mean, test_mean);
            printf("vars\t%-9.6f\t%-9.6f\n", base_variance, test_variance);
            printf("sds\t%-9.6f\t%-9.6f\n", sqrt(base_variance), sqrt(test_variance));
            printf("result\t%-9.6f\n\n", result);
          }
      }
    }
  }
  else puts("skipping");
  return ret_val;
}
int noisy(double variance)
{
  double std_dev = sqrt(variance);
  return std_dev > 2.0 / ticks_per_sec;
}
double mean(double *times)
{
  int i;
  double sum = 0.0;
  for (i=0; i<SAMPLES; i++)
    sum += times[i];
  return sum / SAMPLES;
}
double variance(double mean, double *times)
{
  int i;
  double sum = 0.0;
  for (i=0; i<SAMPLES; i++) {
    double diff = mean - times[i];
    sum += diff * diff;
  }
  return sum / (SAMPLES - 1);
}
long int determine_iterations(FunPar base_case,
                              int *data)
{
  long int iterations = 1;
  base_case(data);  /* an initial, untimed invocation */
  while (1) {
    long int i;
    clock_t start = clock();
    for (i=0; i<iterations; i++)
      base_case(data);
    if (((double) clock() - start) / CLOCKS_PER_SEC > SLOW_FACTOR / ticks_per_sec)
      return iterations;
    iterations += iterations;
  }
}
void collect_timings(long int iterations,
                     FunPar routine,
                     int *data,
                     double *times)
{
  int i;
  routine(data);  /* an initial, untimed invocation */
  for (i=0; i<SAMPLES; i++) {
    long int j;
    clock_t start = clock();
    for (j=0; j<iterations; j++)
      routine(data);
    times[i] = ((double) (clock() - start)) / CLOCKS_PER_SEC;
  }
}