Subversion Repositories or1k

/* CSE -- common subexpression elimination */

void cse (cuc_func *f)

{

  int b, i, j, b1, i1, b2, i2, j2;

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

    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)

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

        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++) {

          cuc_insn *ii1 = &f->bb[b1].insn[i1];

          cuc_insn *ii2 = &f->bb[b2].insn[i2];

          /* Do we have an exact match? */

          if (ii1->index == ii2->index) continue;

          if (ii1->type & IT_VOLATILE) continue;

          if (ii1->op[1] != ii2->op[1] || ii1->opt[1] != ii2->opt[1]) continue;

          if (ii1->op[2] != ii2->op[2] || ii1->opt[2] != ii2->opt[2]) continue;

          if (ii1->opt[3] != ii2->opt[3]) continue;

          if (ii1->opt[3] != OPT_NONE && ii1->op[3] != ii2->op[3]) continue;

          /* Check if we drive outputs? */

          if ((ii1->opt[0] & OPT_REGISTER) && ii1->op[0] >= 0)

            if ((ii2->opt[0] & OPT_REGISTER) && ii2->op[0] >= 0) continue;

            else ii2->op[0] = ii1->op[0];

          /* remove duplicated instruction and relink the references */

          change_insn_type (ii2, II_NOP);

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

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

              for (j = 0; j < MAX_OPERANDS; j++)

                if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == REF (b2, i2))

                  f->bb[b].insn[i].op[j] = REF (b1, i1);

        }

}

static int count_cmovs (cuc_insn *ii, int match)

{

  int c = 0, j;

  if (match & 2) {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (ii->opt[j] & OPT_DEST) c++;

  }

  if (match & 1) {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;

  } else {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;

  }

  return c;

}

static void search_csm (int iter, cuc_func *f, cuc_shared *list);

static cuc_shared *main_list;

static int *iteration;

/* CSM -- common subexpression matching -- resource sharing */

void csm (cuc_func *f)

{

  int b, i, j;

  int cnt;

  cuc_shared *list;

  cuc_timings timings;

  analyse_timings (f, &timings);

  main_list = NULL;

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

    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));

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

      int cnt = 0, cntc = 0;

      double size = 0., sizec = 0.;

      int j2 = 0;

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

        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {

          int ok = 1;

          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))

            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]

             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {

              ok = 0;

              break;

            }

          if (ok) {

            cntc++;

            sizec = sizec + insn_size (&f->bb[b].insn[j]);

          } else {

            cnt++;

            size = size + insn_size (&f->bb[b].insn[j]);

          }

          iteration[j] = 0;

        } else iteration[j] = -1;

      if (cntc > 1) {

        assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));

        list->next = main_list;

        list->from = NULL;

        list->ref = REF (b, i);

        list->cnt = cnt;

        list->cmatch = 1;

        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);

        list->osize = sizec;

        list->size = ii_size (f->bb[b].insn[i].index, 1);

        main_list = list;

        search_csm (0, f, list);

      }

      if (cnt > 1) {

        assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));

        list->next = main_list;

        list->from = NULL;

        list->ref = REF (b, i);

        list->cnt = cnt + cntc;

        list->cmatch = 0;

        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);

        list->osize = size + sizec;

        list->size = ii_size (f->bb[b].insn[i].index, 0);

        main_list = list;

        search_csm (0, f, list);

      }

    }

    free (iteration);

  }

  for (list = main_list; list; list = list->next) list->dead = 0;

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

  /* Now we will check the real size of the 'improvements'; if the size

     actually increases, we abandom the option */

  for (list = main_list; list; list = list->next)

    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

  /* Count number of instructions grouped */

  for (list = main_list; list; list = list->next) {

    cuc_shared *l = list;

    int c = 0;

    while (l) {

      c++;

      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;

      l = l->from;

    }

    list->ninsn = c;

  }

  cnt = 0;

  for (list = main_list; list; list = list->next)

    if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

#if 1

  /* We can get a lot of options here, so we will delete duplicates */

  for (list = main_list; list; list = list->next) if (!list->dead) {

    cuc_shared *l;

    for (l = list->next; l; l = l->next) if (!l->dead) {

      int ok = 1;

      cuc_shared *t1 = list;

      cuc_shared *t2 = l;

      while (ok && t1 && t2) {

        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {

          /* If other operands are matching, we must check for them also */

          if (t1->cmatch) {

            int j;

            for (j = 0; j < MAX_OPERANDS; j++)

              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)

               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]

               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {

                ok = 0;

                break;

              }

          }

          /* This option is duplicate, remove */

          if (ok) t1->dead = 1;

        }

        t1 = t1->from;

        t2 = t2->from;

      }

    }

  }

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

#endif

  /* Print out */

  for (list = main_list; list; list = list->next) if (!list->dead) {

    cuc_shared *l = list;

    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",

           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,

           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);

    while (l) {

      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);

      l = l->from;

    }

    cucdebug (1, "\n");

  }

  /* Calculate estimated timings */

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

    cnt = 0;

    for (list = main_list; list; list = list->next)

      if (!list->dead && REF_BB(list->ref) == b) cnt++;

    f->bb[b].ntim = cnt;

    if (!cnt) {

      f->bb[b].tim = NULL;

      continue;

    }

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

    cnt = 0;

    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {

      cuc_shared *l = list;

      f->bb[b].tim[cnt].b = b;

      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;

      f->bb[b].tim[cnt].nshared = list->ninsn;

      assert (f->bb[b].tim[cnt].shared = (int *) malloc (sizeof(int) * list->ninsn));

      for (i =  0; i < list->ninsn; i++, l = l->from) f->bb[b].tim[cnt].shared[i] = l->ref;

      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);

      f->bb[b].tim[cnt].size = timings.size + list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;

      cnt++;

    }

  }

}

/* Recursive function for searching through instruction graph */

static void search_csm (int iter, cuc_func *f, cuc_shared *list)

{

  int b, i, j, i1;

  cuc_shared *l;

  b = REF_BB(list->ref);

  i = REF_I(list->ref);

  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {

    int t = f->bb[b].insn[i].op[j];

    int cnt = 0, cntc = 0;

    double size = 0., sizec = 0.;

    /* Mark neighbours */

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

      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {

        int t2 = f->bb[b].insn[i1].op[j];

        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {

          int j2;

          int ok = 1;

          iteration[REF_I(t2)] = iter + 1;

          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))

            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]

             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {

              ok = 0;

              break;

            }

          if (ok) {

            cntc++;

            sizec = sizec + insn_size (&f->bb[b].insn[i1]);

          } else {

            cnt++;

            size = size + insn_size (&f->bb[b].insn[i1]);

          }

        }

      }

    }

    if (cntc > 1) {

      assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));

      l->next = main_list;

      main_list = l;

      l->from = list;

      l->ref = t;

      l->cnt = cnt;

      l->cmatch = 1;

      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;

      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);

      l->osize = sizec;

      search_csm (iter + 1, f, l);

    }

    if (cnt > 1) {

      assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));

      l->next = main_list;

      main_list = l;

      l->from = list;

      l->ref = t;

      l->cnt = cnt + cntc;

      l->cmatch = 0;

      l->osize = size + sizec;

      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;

      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);

      search_csm (iter + 1, f, l);

    }

    /* Unmark them back */

    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;

  }

}