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 <ctype.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};

/* returns log2(x) */

int log2 (unsigned long x)

{

  int c = 0;

  assert (x >= 0);

  if (!x) return 0; /* not by the book, but practical */

  while (x != 1) x >>= 1, c++;

  return c;

}

/* Does all known instruction optimizations */

void cuc_optimize (cuc_func *func)

{

  int modified = 0;

  log ("Optimizing.\n");

  insert_conditional_facts (func);

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

  do {

    modified = 0;

    if (optimize_cmovs (func)) {

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

      modified = 1;

    }

    if (optimize_tree (func)) {

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

      modified = 1;

    }

    if (remove_nops (func)) {

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

      modified = 1;

    }

    if (remove_dead (func)) {

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

      modified = 1;

    }

    if (cse (func)) {

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

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

      modified = 1;

    }

    if (optimize_bb (func)) {

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

      modified = 1;

    }

    if (remove_nops (func)) {

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

      modified = 1;

    }

    if (remove_dead_bb (func)) {

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

      modified = 1;

    }

    if (remove_trivial_regs (func)) {

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

      modified = 1;

    }

    if (remove_nops (func)) {

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

      modified = 1;

    }

  } while (modified);

  set_io (func);

}

/* Pre/unrolls basic block and optimizes it */

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");

  cuc_optimize (func);

  add_latches (func);

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

  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;

}

/* Simple comparison function */

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;

}

/* Analyses function; done when cuc command is entered in (sim) prompt */

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;

  func->nfdeps = 0;

  func->fdeps = NULL;

  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");

  cuc_optimize (func);

#if 0

  csm (func);

#endif

  assert (saved = dup_func (func));

  timings.preroll = timings.unroll = 1;

  timings.nshared = 0;

  add_latches (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[30];

  char *name = prof_func[func_no].name;

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

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

            strstrip (tmp, name, 28));

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

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

  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, char *cut_filename)

{

  int b, i, j;

  char tmp[256];

  cuc_timings tt;

  cuc_func *f;

  assert (f = dup_func (rf));

  if (cuc_debug >= 2) print_cuc_bb (f, "BEFORE_GENERATE");

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

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

  format_func_options (tmp, rf);

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

  else printf ("Using 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);

  }

  add_latches (f);

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

  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");

  sprintf (tmp, "%s%s", cut_filename, name);

  output_verilog (f, tmp);

  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];

/* Detects function dependencies and removes  */

static void set_func_deps ()

{

  int f, b, i, j;

restart:

  for (f = 0; f < prof_nfuncs - 1; f++) if (func[f]) {

    int fused[MAX_FUNCS] = {0};

    int c;

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

      for (i = 0; i < func[f]->bb[b].ninsn; i++) {

        cuc_insn *ii = &func[f]->bb[b].insn[i];

        if (ii->index == II_CALL) {

          assert (ii->opt[0] == OPT_CONST);

          for (j = 0; j < prof_nfuncs - 1; j++)

            if (func[j] && func[j]->start_addr == ii->op[0]) break;

          if (j >= prof_nfuncs - 1) {

            log ("%s is calling unknown function, address %08x\n",

                            prof_func[f].name, ii->op[0]);

            debug (1, "%s is calling unknown function, address %08x\n",

                            prof_func[f].name, ii->op[0]);

            free_func (func[f]);

            func[f] = NULL;

            goto restart;

          } else if (f == j) {

            log ("%s is recursive, ignoring\n", prof_func[f].name);

            debug (1, "%s is recursive, ignoring\n", prof_func[f].name);

            free_func (func[f]);

            func[f] = NULL;

            goto restart;

          } else fused[j]++;

        }

      }

    for (i = 0; i < MAX_FUNCS; i++) if (fused[i]) c++;

    if (func[f]->nfdeps) free (func[f]->fdeps);

    func[f]->nfdeps = c;

    func[f]->fdeps = (cuc_func **) malloc (sizeof (cuc_func *) * c);

    for (i = 0, j = 0; i < MAX_FUNCS; i++)

      if (fused[i]) func[f]->fdeps[j++] = func[i];

  }

  /* Detect loops */

  {

    int change;

    for (f = 0; f < MAX_FUNCS; f++) if (func[f]) func[f]->tmp = 0;

    do {

      change = 0;

      for (f = 0; f < MAX_FUNCS; f++) if (func[f] && !func[f]->tmp) {

        int o = 1;

        for (i = 0; i < func[f]->nfdeps; i++)

          if (!func[f]->fdeps[i]->tmp) {o = 0; break;}

        if (o) {

          func[f]->tmp = 1;