Subversion Repositories or1k

/* cuc.c -- OpenRISC Custom Unit Compiler

 *    Copyright (C) 2002 Marko Mlinar, markom@opencores.org

 *

 *    This file is part of OpenRISC 1000 Architectural Simulator.

 *

 *    This program is free software; you can redistribute it and/or modify

 *    it under the terms of the GNU General Public License as published by

 *    the Free Software Foundation; either version 2 of the License, or

 *    (at your option) any later version.

 *

 *    This program is distributed in the hope that it will be useful,

 *    but WITHOUT ANY WARRANTY; without even the implied warranty of

 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *    GNU General Public License for more details.

 *

 *    You should have received a copy of the GNU General Public License

 *    along with this program; if not, write to the Free Software

 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

/* Main file, including code optimization and command prompt */

#include <stdio.h>

#include <stdlib.h>

#include <stdarg.h>

#include <assert.h>

#include "sim-config.h"

#include "cuc.h"

#include "insn.h"

#include "profiler.h"

#include "opcode/or32.h"

#include "parse.h"

FILE *flog;

int cuc_debug = 0;

/* Last used registers by software convention */

const int call_saved[MAX_REGS] = {

  0, 0, 0, 1, 1, 1, 1, 1,

  1, 1, 0, 1, 0, 1, 0, 1,

  0, 1, 0, 1, 0, 1, 0, 1,

  0, 1, 0, 1, 0, 1, 0, 1,

  1, 1};

cuc_timings *preunroll_bb (char *bb_filename, cuc_func *f, cuc_timings *timings, int b, int i, int j)

{

  cuc_func *func;

  cucdebug (2, "BB%i unroll %i times preroll %i times\n", b, j, i);

  func = preunroll_loop (f, b, i, j, bb_filename);

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_PREUNROLL");

  log ("Optimizing.\n");

  optimize_tree (func);

  if (cuc_debug >= 6) //print_cuc_bb (func, "AFTER_OPT_TREE1");

  remove_nops (func);

  if (cuc_debug >= 6) //print_cuc_bb (func, "NO_NOPS");

  remove_dead (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_DEAD1");

  optimize_bb (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_OPT_BB");

  remove_dead_bb (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_DEAD_BB");

  optimize_tree (func);

  if (cuc_debug >= 3) print_cuc_bb (func, "AFTER_OPT_TREE");

  log ("Common subexpression elimination.\n");

  cse (func);

  if (cuc_debug >= 3) print_cuc_bb (func, "AFTER_CSE");

  remove_dead (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_DEAD");

  remove_trivial_regs (func);

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_TRIVIAL");

  add_latches (func);

  if (cuc_debug >= 1) print_cuc_bb (func, "AFTER_LATCHES");

  set_io (func);

  add_memory_dep (func, func->memory_order);

  if (cuc_debug >= 7) print_cuc_bb (func, "AFTER_MEMORY_DEP");

  add_data_dep (func);

  if (cuc_debug >= 8) print_cuc_bb (func, "AFTER_DATA_DEP");

  schedule_memory (func, func->memory_order);

  if (cuc_debug >= 7) print_cuc_bb (func, "AFTER_SCHEDULE_MEM");

  analyse_timings (func, timings);

  cucdebug (2, "new_time = %i, old_time = %i, size = %f\n",

           timings->new_time, func->orig_time, timings->size);

  log ("new time = %icyc, old_time = %icyc, size = %.0f gates\n",

         timings->new_time, func->orig_time, timings->size);

  //output_verilog (func, argv[1]);

  free_func (func);

  timings->b = b;

  timings->unroll = j;

  timings->preroll = i;

  timings->nshared = 0;

  return timings;

}

int tim_comp (cuc_timings *a, cuc_timings *b)

{

  if (a->new_time < b->new_time) return -1;

  else if (a->new_time > b->new_time) return 1;

  else return 0;

}

cuc_func *analyse_function (char *module_name, long orig_time,

                unsigned long start_addr, unsigned long end_addr,

                int memory_order)

{

  cuc_timings timings;

  cuc_func *func = (cuc_func *) malloc (sizeof (cuc_func));

  cuc_func *saved;

  int b, i, j;

  char tmp1[256];

  char tmp2[256];

  func->orig_time = orig_time;

  func->start_addr = start_addr;

  func->end_addr = end_addr;

  func->memory_order = memory_order;

  sprintf (tmp1, "%s.bin", module_name);

  cucdebug (2, "Loading %s.bin\n", module_name);

  if (cuc_load (tmp1)) {

    free (func);

    return NULL;

  }

  log ("Detecting basic blocks\n");

  detect_bb (func);

  if (cuc_debug >= 2) print_cuc_insns ("WITH_BB_LIMITS", 0);

  //sprintf (tmp1, "%s.bin.mp", module_name);

  sprintf (tmp2, "%s.bin.bb", module_name);

  generate_bb_seq (func, config.sim.mprof_fn, tmp2);

  log ("Assuming %i clk cycle load (%i cyc burst)\n", runtime.cuc.mdelay[0], runtime.cuc.mdelay[2]);

  log ("Assuming %i clk cycle store (%i cyc burst)\n", runtime.cuc.mdelay[1], runtime.cuc.mdelay[3]);

  build_bb (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_BUILD_BB");

  reg_dep (func);

  log ("Detecting dependencies\n");

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_REG_DEP");

  optimize_tree (func);

  log ("Optimizing.\n");

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_OPT_TREE1");

  remove_nops (func);

  if (cuc_debug >= 6) print_cuc_bb (func, "NO_NOPS");

  remove_dead (func);

  if (cuc_debug >= 6) print_cuc_bb (func, "AFTER_DEAD1");

  optimize_bb (func);

  if (cuc_debug >= 6) print_cuc_bb (func, "AFTER_OPT_BB");

  remove_dead_bb (func);

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_DEAD_BB");

  optimize_tree (func);

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_OPT_TREE");

  log ("Common subexpression elimination.\n");

  cse (func);

  if (cuc_debug >= 3) print_cuc_bb (func, "AFTER_CSE");

  remove_dead (func);

  if (cuc_debug >= 5) print_cuc_bb (func, "AFTER_DEAD");

  remove_trivial_regs (func);

  if (cuc_debug >= 2) print_cuc_bb (func, "AFTER_TRIVIAL");

#if 0

  csm (func);

#endif

  assert (saved = dup_func (func));

  timings.preroll = timings.unroll = 1;

  timings.nshared = 0;

  add_latches (func);

  set_io (func);

  if (cuc_debug >= 1) print_cuc_bb (func, "AFTER_LATCHES");

  analyse_timings (func, &timings);

  add_memory_dep (func, func->memory_order);

  if (cuc_debug >= 7) print_cuc_bb (func, "AFTER_MEMORY_DEP");

  add_data_dep (func);

  if (cuc_debug >= 8) print_cuc_bb (func, "AFTER_DATA_DEP");

  schedule_memory (func, memory_order);

  if (cuc_debug >= 7) print_cuc_bb (func, "AFTER_SCHEDULE_MEM");

  //output_verilog (func, module_name);

  free_func (func);

  log ("Base option: pre%i,un%i,sha%i: %icyc %.1f\n",

        timings.preroll, timings.unroll, timings.nshared, timings.new_time, timings.size);

  saved->timings = timings;

#if 1

  /* detect and unroll simple loops */

  for (b = 0; b < saved->num_bb; b++) {

    cuc_timings t[MAX_UNROLL * MAX_PREROLL];

    cuc_timings *ut;

    cuc_timings *cut = &t[0];

    int nt = 1;

    double csize;

    saved->bb[b].selected_tim = -1;

    /* Is it a loop? */

    if (saved->bb[b].next[0] != b && saved->bb[b].next[1] != b) continue;

    t[0] = timings;

    t[0].b = b;

    t[0].preroll = 1;

    t[0].unroll = 1;

    t[0].nshared = 0;

    sprintf (tmp1, "%s.bin.bb", module_name);

    i = 1;

    do {

      cuc_timings *pt;

      cuc_timings *cpt = cut;

      j = 1;

      do {

        pt = cpt;

        cpt = preunroll_bb (tmp1, saved, &t[nt++], b, ++j, i);

      } while (j <= MAX_PREROLL && pt->new_time >= cpt->new_time);

      i++;

      ut = cut;

      cut = preunroll_bb (tmp1, saved, &t[nt++], b, 1, i);

    } while (i <= MAX_UNROLL && ut->new_time >= cut->new_time);

    /* Sort the timings */

#if 0

    if (cuc_debug >= 3)

    for (i = 0; i < nt; i++) printf ("%i:%i,%i: %icyc\n",

                    t[i].b, t[i].preroll, t[i].unroll, t[i].new_time);

#endif

    qsort (t, nt, sizeof (cuc_timings), (int (*)(const void *, const void *))tim_comp);

    /* Delete timings, that have worst time and bigger size than other */

    j = 1;

    csize = t[0].size;

    for (i = 1; i < nt; i++)

      if (t[i].size < csize) t[j++] = t[i];

    nt = j;

    cucdebug (1, "Available options\n");

    for (i = 0; i < nt; i++) cucdebug (1, "%i:%i,%i: %icyc %.1f\n",

        t[i].b, t[i].preroll, t[i].unroll, t[i].new_time, t[i].size);

    /* Add results from CSM */

    j = nt;

    for (i = 0; i < saved->bb[b].ntim; i++) {

      int i1;

      for (i1 = 0; i1 < nt; i1++) {

        t[j] = t[i1];

        t[j].size += saved->bb[b].tim[i].size - timings.size;

        t[j].new_time += saved->bb[b].tim[i].new_time - timings.new_time;

        t[j].nshared = saved->bb[b].tim[i].nshared;

        t[j].shared = saved->bb[b].tim[i].shared;

        if (++j >= MAX_UNROLL * MAX_PREROLL) goto full;

      }

    }

full:

    nt = j;

    cucdebug (1, "Available options:\n");

    for (i = 0; i < nt; i++) cucdebug (1, "%i:%i,%i: %icyc %.1f\n",

        t[i].b, t[i].preroll, t[i].unroll, t[i].new_time, t[i].size);

    /* Sort again with new timings added */

    qsort (t, nt, sizeof (cuc_timings), (int (*)(const void *, const void *))tim_comp);

    /* Delete timings, that have worst time and bigger size than other */

    j = 1;

    csize = t[0].size;

    for (i = 1; i < nt; i++)

      if (t[i].size < csize) t[j++] = t[i];

    nt = j;

    cucdebug (1, "Available options:\n");

    for (i = 0; i < nt; i++) cucdebug (1, "%i:%i,%i: %icyc %.1f\n",

                               t[i].b, t[i].preroll, t[i].unroll, t[i].new_time, t[i].size);

    if (saved->bb[b].ntim) free (saved->bb[b].tim);

    saved->bb[b].ntim = nt;

    assert (saved->bb[b].tim = (cuc_timings *) malloc (sizeof (cuc_timings) * nt));

    /* Copy options in reverse order -- smallest first */

    for (i = 0; i < nt; i++) saved->bb[b].tim[i] = t[nt - 1 - i];

    log ("Available options:\n");

    for (i = 0; i < saved->bb[b].ntim; i++) {

      log ("%i:pre%i,un%i,sha%i: %icyc %.1f\n",

        saved->bb[b].tim[i].b, saved->bb[b].tim[i].preroll, saved->bb[b].tim[i].unroll,

        saved->bb[b].tim[i].nshared, saved->bb[b].tim[i].new_time, saved->bb[b].tim[i].size);

    }

  }

#endif

  return saved;

}

/* Utility option formatting functions */

static const char *option_char = "?abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*static */char *gen_option (char *s, int bb_no, int f_opt)

{

  if (bb_no >= 0) sprintf (s, "%i", bb_no);

  assert (f_opt <= strlen (option_char));

  sprintf (s, "%s%c", s, option_char[f_opt]);

  return s;

}

/*static */void print_option (int bb_no, int f_opt)

{

  char tmp1[10];

  char tmp2[10];

  sprintf (tmp2, "%s", gen_option (tmp1, bb_no, f_opt));

  printf ("%3s", tmp2);

}

static char *format_func_options (char *s, cuc_func *f)

{

  int b, first = 1;

  *s = '\0';

  for (b = 0; b < f->num_bb; b++)

    if (f->bb[b].selected_tim >= 0) {

      char tmp[10];

      sprintf (s, "%s%s%s", s, first ? "" : ",", gen_option (tmp, b, f->bb[b].selected_tim));

      first = 0;

    }

  return s;

}

static void options_cmd (int func_no, cuc_func *f)

{

  int b, i;

  char tmp[20];

  char *name = prof_func[func_no].name;

  printf ("--------------------------------------------------------\n");

  printf ("|%-16s|pre/unrolled|shared|  time  |  gates | old_time = %i \n",

            strstrip (tmp, name, 16), f->orig_time);

  printf ("|        BASE    |%4i / %4i | %4i |%8i|%8.f|\n", 1, 1, 0,

          f->timings.new_time, f->timings.size);

  for (b = 0; b < f->num_bb; b++) {

    /* Print out results */

    for (i = 1; i < f->bb[b].ntim; i++) { /* First one is base option */

      int time = f->bb[b].tim[i].new_time - f->timings.new_time;

      double size = f->bb[b].tim[i].size - f->timings.size;

      printf ("|       ");

      print_option (b, i);

      printf ("      |%4i / %4i | %4i |%+8i|%+8.f|\n",

        f->bb[b].tim[i].preroll, f->bb[b].tim[i].unroll, f->bb[b].tim[i].nshared,

        time, size);

    }

  }

}

/* Generates a function, based on specified parameters */

cuc_func *generate_function (cuc_func *rf, char *name)

{

  int b, i, j;

  char tmp[256];

  cuc_timings tt;

  cuc_func *f;

  assert (f = dup_func (rf));

  log ("Generating function %s.\n", name);

  printf ("Generating function %s.\n", name);

  print_cuc_bb (f, "BEFORE_GENERATE");

  add_latches (f);

  set_io (f);

  if (cuc_debug >= 1) print_cuc_bb (f, "AFTER_LATCHES");

  format_func_options (tmp, rf);

  if (strlen (tmp)) printf ("Applying options: %s\n", tmp);

  else printf ("Basic options.\n");

  /* Generate function as specified by options */

  for (b = 0; b < f->num_bb; b++) {

    cuc_timings *st;

    if (rf->bb[b].selected_tim < 0) continue;

    st = &rf->bb[b].tim[rf->bb[b].selected_tim];

    sprintf (tmp, "%s.bin.bb", name);

    preunroll_bb (&tmp[0], f, &tt, b, st->preroll, st->unroll);

    if (cuc_debug >= 1) print_cuc_bb (f, "AFTER_PREUNROLL");

  }

  for (b = 0; b < f->num_bb; b++) {

    cuc_timings *st;

    if (rf->bb[b].selected_tim < 0) continue;

    st = &rf->bb[b].tim[rf->bb[b].selected_tim];

    if (!st->nshared) continue;

    assert (0);

    //csm_gen (f, rf, st->nshared, st->shared);

  }

  analyse_timings (f, &tt);

  add_memory_dep (f, f->memory_order);

  if (cuc_debug >= 7) print_cuc_bb (f, "AFTER_MEMORY_DEP");

  add_data_dep (f);

  if (cuc_debug >= 8) print_cuc_bb (f, "AFTER_DATA_DEP");

  schedule_memory (f, f->memory_order);

  if (cuc_debug >= 7) print_cuc_bb (f, "AFTER_SCHEDULE_MEM");

  output_verilog (f, name);

  return f;

}

/* Calculates required time, based on selected options */

int calc_cycles (cuc_func *f)

{

  int b, i, ntime = f->timings.new_time;

  for (b = 0; b < f->num_bb; b++)

    if (f->bb[b].selected_tim >= 0) {

      assert (f->bb[b].selected_tim < f->bb[b].ntim);

      ntime += f->bb[b].tim[f->bb[b].selected_tim].new_time - f->timings.new_time;

    }

  return ntime;

}

/* Calculates required size, based on selected options */

double calc_size (cuc_func *f)

{

  int b, i;

  double size = f->timings.size;

  for (b = 0; b < f->num_bb; b++)

    if (f->bb[b].selected_tim >= 0) {

      assert (f->bb[b].selected_tim < f->bb[b].ntim);

      size += f->bb[b].tim[f->bb[b].selected_tim].size - f->timings.size;

    }

  return size;

}

/* Dumps specified function to file (hex) */

unsigned long extract_function (char *out_fn, unsigned long start_addr)

{

  FILE *fo;

  unsigned long a = start_addr;

  int x = 0;

  assert (fo = fopen (out_fn, "wt+"));

  do {

    unsigned long d = evalsim_mem32 (a);

    int index = insn_decode (d);

    assert (index >= 0);

    if (x) x++;

    if (strcmp (insn_name (index), "l.jr") == 0) x = 1;

    a += 4;

    fprintf (fo, "%08x\n", d);

  } while (x < 2);

  fclose (fo);

  return a - 4;

}

static cuc_func *func[MAX_FUNCS];

static int func_v[MAX_FUNCS];

void main_cuc (char *filename)

{

  int i, j;

  char tmp1[256];

  printf ("Entering OpenRISC Custom Unit Compiler command prompt\n");

  printf ("Using profile file \"%s\" and memory profile file \"%s\".\n", config.sim.prof_fn, config.sim.mprof_fn);

  sprintf (tmp1, "%s.log", filename);

  printf ("Analyzing. (log file \"%s\").\n", tmp1);

  assert (flog = fopen (tmp1, "wt+"));

  /* Loads in the specified timings table */

  printf ("Using timings from \"%s\" at %s\n",config.cuc.timings_fn,

                 generate_time_pretty (tmp1, config.sim.clkcycle_ps));

  load_timing_table (config.cuc.timings_fn);

  runtime.cuc.cycle_duration = 1000. * config.sim.clkcycle_ps;

  printf ("Multicycle logic %s, bursts %s, %s memory order.\n",

    config.cuc.no_multicycle ? "OFF" : "ON", config.cuc.enable_bursts ? "ON" : "OFF",

    config.cuc.memory_order == MO_NONE ? "no" : config.cuc.memory_order == MO_WEAK ? "weak" :

    config.cuc.memory_order == MO_STRONG ? "strong" : "exact");

  prof_set (1, 0);

  assert (prof_acquire (config.sim.prof_fn) == 0);

  if (config.cuc.calling_convention)

    printf ("Assuming OpenRISC standard calling convention.\n");

  /* Try all functions except "total" */

  for (i = 0; i < prof_nfuncs - 1; i++) {

    long orig_time;

    unsigned long start_addr, end_addr;

    orig_time = prof_func[i].cum_cycles;

    start_addr = prof_func[i].addr;

    /* Extract the function from the binary */

    sprintf (tmp1, "%s.bin", prof_func[i].name);

    end_addr = extract_function (tmp1, start_addr);

    log ("Testing function %s (%08x - %08x)\n", prof_func[i].name, start_addr, end_addr);

    printf ("Testing function %s (%08x - %08x)\n", prof_func[i].name, start_addr, end_addr);

    func[i] = analyse_function (prof_func[i].name, orig_time, start_addr,

                   end_addr, config.cuc.memory_order);

    func_v[i] = 0;

  }

  while (1) {

    char *s;

    printf ("(cuc) ");

    fflush (stdout);

    fgets(tmp1, sizeof tmp1, stdin);

    for (s = tmp1; *s != '\0' && *s != '\n' && *s != '\r'; s++);

    *s = '\0';

    if (strcmp (tmp1, "q") == 0 || strcmp (tmp1, "quit") == 0) {

      break;

    } else if (strcmp (tmp1, "p") == 0 || strcmp (tmp1, "profile") == 0) {

      int ntime = 0;

      int size = 0;

      printf ("-----------------------------------------------------------------------------\n");

      printf ("|function name       |calls|avg cycles  |old%| max. f.  | impr. f.| options |\n");

      printf ("|--------------------+-----+------------+----+----------|---------+---------|\n");

      for (j = 0; j < prof_nfuncs; j++) {

        int bestcyc = 0, besti = 0;

        char tmp[100];

        for (i = 0; i < prof_nfuncs; i++)

          if (prof_func[i].cum_cycles > bestcyc) {

            bestcyc = prof_func[i].cum_cycles;

            besti = i;

          }

        i = besti;

        printf ("|%-20s|%5i|%12.1f|%3.0f%%| ",

                strstrip (tmp, prof_func[i].name, 20),  prof_func[i].calls,

                ((double)prof_func[i].cum_cycles / prof_func[i].calls),

                (100. * prof_func[i].cum_cycles / prof_cycles));

        if (func[i]) {

          double f = 1.0;