OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [branches/] [stable_0_2_x/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 1778

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 879 markom 
/* bb.c -- OpenRISC Custom Unit Compiler, Basic Block handling
2 
 *    Copyright (C) 2002 Marko Mlinar, markom@opencores.org
3 
 *
4 
 *    This file is part of OpenRISC 1000 Architectural Simulator.
5 
 *
6 
 *    This program is free software; you can redistribute it and/or modify
7 
 *    it under the terms of the GNU General Public License as published by
8 
 *    the Free Software Foundation; either version 2 of the License, or
9 
 *    (at your option) any later version.
10 
 *
11 
 *    This program is distributed in the hope that it will be useful,
12 
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
13 
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 
 *    GNU General Public License for more details.
15 
 *
16 
 *    You should have received a copy of the GNU General Public License
17 
 *    along with this program; if not, write to the Free Software
18 
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
19 
 
20 
#include <stdio.h>
21 
#include <stdlib.h>
22 
#include <stdarg.h>
23 
#include <assert.h>
24 1308 phoenix 
#include <string.h>
25 
 
26 1350 nogj 
#include "config.h"
27 
 
28 
#ifdef HAVE_INTTYPES_H
29 
#include <inttypes.h>
30 
#endif
31 
 
32 
#include "port.h"
33 
#include "arch.h"
34 897 markom 
#include "sim-config.h"
35 
#include "abstract.h"
36 879 markom 
#include "cuc.h"
37 
#include "insn.h"
38 
#include "support/profile.h"
39 
 
40 925 markom 
/* prints out bb string */
41 
void print_bb_num (int num)
42 
{
43 997 markom 
  if (num < 0) PRINTF ("*");
44 
  else if (num == BBID_END) PRINTF ("END");
45 
  else if (num == BBID_START) PRINTF ("START");
46 
  else PRINTF ("%2x", num);
47 925 markom 
}
48 
 
49 879 markom 
/* Print out basic blocks */
50 
void print_cuc_bb (cuc_func *f, char *s)
51 
{
52 
  int i;
53 997 markom 
  PRINTF ("------- %s -------\n", s);
54 879 markom 
  for (i = 0; i < f->num_bb; i++) {
55 997 markom 
    if (f->bb[i].insn) PRINTF ("\n---- BB%-2x * %x ---- ", i, f->bb[i].cnt);
56 
    else PRINTF ("BB%-2x: %4x-%-4x", i, f->bb[i].first, f->bb[i].last);
57 1308 phoenix 
    PRINTF (" type %02lx tmp %i ", f->bb[i].type, f->bb[i].tmp);
58 997 markom 
    PRINTF ("next "); print_bb_num (f->bb[i].next[0]);
59 
    PRINTF (" "); print_bb_num (f->bb[i].next[1]);
60 
    PRINTF (" prev "); print_bb_num (f->bb[i].prev[0]);
61 
    PRINTF (" "); print_bb_num (f->bb[i].prev[1]);
62 
    PRINTF ("\n");
63 879 markom 
 
64 1062 markom 
    if (f->bb[i].insn) print_insns (i, f->bb[i].insn, f->bb[i].ninsn, 0);
65 879 markom 
  }
66 953 markom 
  if (f->nmsched) {
67 997 markom 
    PRINTF ("\nmsched: ");
68 953 markom 
    for (i = 0; i < f->nmsched; i++)
69 997 markom 
      PRINTF ("%x ", f->msched[i]);
70 
    PRINTF ("\n\n\n");
71 
  } else PRINTF ("\n");
72 897 markom 
  fflush (stdout);
73 879 markom 
}
74 
 
75 
/* Copies src basic block into destination */
76 1557 nogj 
void cpy_bb (cuc_bb *dest, cuc_bb *src)
77 879 markom 
{
78 897 markom 
  int i, j;
79 941 markom 
  dep_list *d;
80 897 markom 
  assert (dest != src);
81 879 markom 
  *dest = *src;
82 
  assert (dest->insn = malloc (sizeof (cuc_insn) * src->ninsn));
83 941 markom 
  for (i = 0; i < src->ninsn; i++) {
84 
    d = src->insn[i].dep;
85 879 markom 
    dest->insn[i] = src->insn[i];
86 941 markom 
    dest->insn[i].dep = NULL;
87 
    while (d) {
88 
      add_dep (&dest->insn[i].dep, d->ref);
89 
      d = d->next;
90 
    }
91 
  }
92 
 
93 
  d = src->mdep;
94 
  dest->mdep = NULL;
95 
  while (d) {
96 
    add_dep (&dest->mdep, d->ref);
97 
    d = d->next;
98 
  }
99 879 markom 
  if (src->ntim) {
100 
    assert (dest->tim = malloc (sizeof (cuc_timings) * src->ntim));
101 897 markom 
    for (i = 0; i < src->ntim; i++) {
102 
      dest->tim[i] = src->tim[i];
103 
      if (src->tim[i].nshared) {
104 
        assert (dest->tim[i].shared = malloc (sizeof (int) * src->tim[i].nshared));
105 
        for (j = 0; j < src->tim[i].nshared; j++)
106 
          dest->tim[i].shared[j] = src->tim[i].shared[j];
107 
      }
108 
    }
109 879 markom 
  }
110 
}
111 
 
112 
/* Duplicates function */
113 
cuc_func *dup_func (cuc_func *f)
114 
{
115 
  cuc_func *n = (cuc_func *) malloc (sizeof (cuc_func));
116 
  int b, i;
117 
  for (b = 0; b < f->num_bb; b++) cpy_bb (&n->bb[b], &f->bb[b]);
118 
  n->num_bb = f->num_bb;
119 
  assert (n->init_bb_reloc = (int *)malloc (sizeof (int) * f->num_init_bb));
120 
  for (b = 0; b < f->num_init_bb; b++) n->init_bb_reloc[b] = f->init_bb_reloc[b];
121 
  n->num_init_bb = f->num_init_bb;
122 915 markom 
  for (i = 0; i < MAX_REGS; i++) {
123 
    n->saved_regs[i] = f->saved_regs[i];
124 
    n->lur[i] = f->lur[i];
125 
    n->used_regs[i] = f->used_regs[i];
126 
  }
127 879 markom 
  n->start_addr = f->start_addr;
128 
  n->end_addr = f->end_addr;
129 
  n->orig_time = f->orig_time;
130 
  n->nmsched = f->nmsched;
131 1041 markom 
  n->num_runs = f->num_runs;
132 879 markom 
  for (i = 0; i < f->nmsched; i++) {
133 
    n->msched[i] = f->msched[i];
134 
    n->mtype[i] = f->mtype[i];
135 
  }
136 906 markom 
  n->nfdeps = f->nfdeps;
137 
  if (f->nfdeps) {
138 
    f->fdeps = (cuc_func **) malloc (sizeof (cuc_func *) * f->nfdeps);
139 
    for (i = 0; i < f->nfdeps; i++) n->fdeps[i] = f->fdeps[i];
140 
  }
141 879 markom 
  return n;
142 
}
143 
 
144 
/* Releases memory allocated by function */
145 
void free_func (cuc_func *f)
146 
{
147 
  int b, i;
148 
  for (b = 0; b < f->num_bb; b++) {
149 
    for (i = 0; i < f->bb[b].ninsn; i++)
150 
      dispose_list (&f->bb[b].insn[i].dep);
151 
    if (f->bb[b].insn) free (f->bb[b].insn);
152 897 markom 
    for (i = 0; i < f->bb[b].ntim; i++)
153 
      if (f->bb[b].tim[i].nshared && f->bb[b].tim[i].shared)
154 
        free (f->bb[b].tim[i].shared);
155 879 markom 
    if (f->bb[b].tim && f->bb[b].ntim) free (f->bb[b].tim);
156 
  }
157 
  free (f);
158 
}
159 
 
160 
/* Recalculates last_used_reg */
161 
void recalc_last_used_reg (cuc_func *f, int b)
162 
{
163 
  int i;
164 
  cuc_bb *bb = &f->bb[b];
165 
 
166 
  /* rebuild last used reg array */
167 
  if (bb->insn[0].index == II_LRBB) bb->last_used_reg[LRBB_REG] = 0;
168 
  else bb->last_used_reg[LRBB_REG] = -1;
169 
 
170 
  for (i = 1; i < MAX_REGS - 1; i++) bb->last_used_reg[i] = -1;
171 
 
172 
    /* Create references */
173 
  for (i = 0; i < bb->ninsn; i++) {
174 
    int k;
175 
    /* Now check for destination operand(s) */
176 
    for (k = 0; k < MAX_OPERANDS; k++) if (bb->insn[i].opt[k] & OPT_DEST)
177 
      if ((bb->insn[i].opt[k] & ~OPT_DEST) == OPT_REGISTER
178 
        && (int)bb->insn[i].op[k] >= 0) {
179 
        bb->last_used_reg[bb->insn[i].op[k]] = REF (b, i);
180 
      }
181 
  }
182 
}
183 
 
184 
/* Set the BB limits */
185 
void detect_bb (cuc_func *f)
186 
{
187 
  int i, j, end_bb = 0, eb = 0;
188 
 
189 
  /* Mark block starts/ends */
190 
  for (i = 0; i < num_insn; i++) {
191 
    if (end_bb) insn[i].type |= IT_BBSTART;
192 
    end_bb = 0;
193 
    if (insn[i].type & IT_BRANCH) {
194 
      int jt = insn[i].op[0];
195 
      insn[i].type |= IT_BBEND;
196 
      end_bb = 1;
197 
      if (jt < 0 || jt >= num_insn) {
198 
        fprintf (stderr, "Instruction #%i:Jump out of function '%s'.\n", i, insn[i].disasm);
199 
        exit (1);
200 
      }
201 
      if (jt > 0) insn[jt - 1].type |= IT_BBEND;
202 
      insn[jt].type |= IT_BBSTART;
203 
    }
204 
  }
205 
 
206 
  /* Initialize bb array */
207 
  insn[0].type |= IT_BBSTART;
208 
  insn[num_insn - 1].type |= IT_BBEND;
209 
  f->num_bb = 0;
210 
  for (i = 0; i < num_insn; i++) {
211 
    if (insn[i].type & IT_BBSTART) {
212 
      f->bb[f->num_bb].first = i;
213 
      f->bb[f->num_bb].cnt = 0;
214 
    }
215 
    /* Determine repetitions of a loop */
216 
    if (insn[i].type & IT_BBEND) {
217 
      f->bb[f->num_bb].type = 0;
218 
      f->bb[f->num_bb].last = i;
219 
      f->bb[f->num_bb].next[0] = f->bb[f->num_bb].next[1] = -1;
220 
      f->bb[f->num_bb].tmp = 0;
221 
      f->bb[f->num_bb].ntim = 0;
222 
      f->num_bb++;
223 
      assert (f->num_bb < MAX_BB);
224 
    }
225 
  }
226 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INIT");
227 879 markom 
 
228 
  /* Build forward connections between BBs */
229 
  for (i = 0; i < f->num_bb; i++)
230 
    if (insn[f->bb[i].last].type & IT_BRANCH) {
231 
      int j;
232 
      assert (insn[f->bb[i].last].index == II_BF);
233 
      /* Find block this instruction jumps to */
234 
      for (j = 0; j < f->num_bb; j++)
235 
        if (f->bb[j].first == insn[f->bb[i].last].op[0]) break;
236 
      assert (j < f->num_bb);
237 
 
238 
      /* Convert the jump address to BB link */
239 
      insn[f->bb[i].last].op[0] = j; insn[f->bb[i].last].opt[0] = OPT_BB;
240 
 
241 
      /* Make a link */
242 
      f->bb[i].next[0] = j;
243 
      if (++f->bb[j].tmp > 2) eb++;
244 
      f->bb[i].next[1] = i + 1;
245 
      if (++f->bb[i + 1].tmp > 2) eb++;
246 
    } else if (f->bb[i].last == num_insn - 1) { /* Last instruction doesn't have to do anything */
247 
    } else {
248 
      f->bb[i].next[0] = i + 1;
249 
      if (++f->bb[i + 1].tmp > 2) eb++;
250 
    }
251 
 
252 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_NEXT");
253 879 markom 
 
254 
  /* Build backward connections, but first insert artificial blocks
255 
   * to handle more than 2 connections */
256 883 markom 
  cucdebug (6, "artificial %i %i\n", f->num_bb, eb);
257 879 markom 
  end_bb = f->num_bb + eb;
258 
  for (i = f->num_bb - 1; i >= 0; i--) {
259 
    j = f->bb[i].tmp;
260 
    if (f->bb[i].tmp > 2) f->bb[i].tmp = -f->bb[i].tmp;
261 
    f->bb[--end_bb] = f->bb[i];
262 
    reloc[i] = end_bb;
263 
    while (j-- > 2) {
264 
      f->bb[--end_bb].first = f->bb[i].first;
265 
      f->bb[end_bb].last = -1;
266 
      f->bb[end_bb].next[0] = -1;
267 
      f->bb[end_bb].next[1] = -1;
268 
      f->bb[end_bb].tmp = 0;
269 
      f->bb[end_bb].cnt = f->bb[i].cnt;
270 
      f->bb[end_bb].ntim = 0;
271 
    }
272 
  }
273 
  f->num_bb += eb;
274 
 
275 
  /* relocate jump instructions */
276 
  for (i = 0; i < num_insn; i++)
277 
    for (j = 0; j < MAX_OPERANDS; j++)
278 
      if (insn[i].opt[j] & OPT_BB)
279 
        insn[i].op[j] = reloc[insn[i].op[j]];
280 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INSERT-reloc");
281 879 markom 
  for (i = 0; i < f->num_bb; i++) {
282 
    if (f->bb[i].next[0] >= 0) {
283 
      int t = reloc[f->bb[i].next[0]];
284 
      if (f->bb[t].tmp < 0) {
285 
        f->bb[t].tmp = -f->bb[t].tmp;
286 
        t -= f->bb[t].tmp - 2;
287 
      } else if (f->bb[t].tmp > 2) t -= f->bb[t].tmp-- - 2;
288 
      f->bb[i].next[0] = t;
289 
    }
290 
    if (f->bb[i].next[1] >= 0) {
291 
      int t = reloc[f->bb[i].next[1]];
292 
      if (f->bb[t].tmp < 0) {
293 
        f->bb[t].tmp = -f->bb[t].tmp;
294 
        t -= f->bb[t].tmp - 2;
295 
      } else if (f->bb[t].tmp > 2) t -= f->bb[t].tmp-- - 2;
296 
      f->bb[i].next[1] = t;
297 
    }
298 
    /* artificial blocks do not have relocations, hardcode them */
299 
    if (f->bb[i].last < 0) f->bb[i].next[0] = i + 1;
300 
  }
301 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INSERT");
302 879 markom 
 
303 
  /* Uncoditional branched do not continue to next block */
304 
  for (i = 0; i < f->num_bb; i++) {
305 
    cuc_insn *ii;
306 
    if (f->bb[i].last < 0) continue;
307 
    ii = &insn[f->bb[i].last];
308 
    /* Unconditional branch? */
309 
    if (ii->type & IT_BRANCH && ii->opt[1] & OPT_CONST) {
310 
      change_insn_type (ii, II_NOP);
311 1044 markom 
#if 0
312 879 markom 
      if (f->bb[i].next[1] == i + 1) f->bb[i].next[0] = f->bb[i].next[1];
313 1044 markom 
#endif
314 879 markom 
      f->bb[i].next[1] = -1;
315 
    }
316 1044 markom 
  }
317 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_UNCOND_JUMP");
318 879 markom 
 
319 
  /* Add backward connections */
320 
  for (i = 0; i < f->num_bb; i++)
321 
    f->bb[i].prev[0] = f->bb[i].prev[1] = -1;
322 
 
323 
  for (i = 0; i < f->num_bb; i++) {
324 
    if (f->bb[i].next[0] >= 0) {
325 
      int t = f->bb[i].next[0];
326 
      if (f->bb[t].prev[0] < 0) f->bb[t].prev[0] = i;
327 
      else {
328 
        assert (f->bb[t].prev[1] < 0);
329 
        f->bb[t].prev[1] = i;
330 
      }
331 
    }
332 
    if (f->bb[i].next[1] >= 0) {
333 
      int t = f->bb[i].next[1];
334 
      if (f->bb[t].prev[0] < 0) f->bb[t].prev[0] = i;
335 
      else {
336 
        assert (f->bb[t].prev[1] < 0);
337 
        f->bb[t].prev[1] = i;
338 
      }
339 
    }
340 
  }
341 932 markom 
  /* Add START marker */
342 
  assert (f->bb[0].prev[0] < 0);
343 1061 markom 
  f->bb[0].prev[0] = BBID_START;
344 932 markom 
 
345 925 markom 
  /* Add END marker */
346 1061 markom 
  assert (f->bb[f->num_bb - 1].next[0] < 0);
347 
  assert (f->bb[f->num_bb - 1].next[1] < 0);
348 
  f->bb[f->num_bb - 1].next[0] = BBID_END;
349 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_PREV");
350 879 markom 
}
351 
 
352 905 markom 
/* We do a quick check if there are some anomalies with references */
353 
void cuc_check (cuc_func *f)
354 
{
355 1557 nogj 
  int i, j = 0, k = 0;
356 973 markom 
  cucdebug (1, "cuc_check\n");
357 905 markom 
  for (i = 0; i < f->num_bb; i++) {
358 930 markom 
    if (!f->bb[i].insn && f->bb[i].ninsn) goto err;
359 
    for (j = 0; j < f->bb[i].ninsn; j++) {
360 
      cuc_insn *ii = &f->bb[i].insn[j];
361 1062 markom 
      if ((ii->index == II_CMOV || ii->index == II_ADD) && ii->type & IT_COND && ii->opt[0] & OPT_DEST) {
362 930 markom 
        k = 0;
363 
        assert (ii->opt[k] & OPT_REGISTER);
364 
        if ((signed)ii->op[k] >= 0 && ii->op[k] != FLAG_REG && ii->op[k] != LRBB_REG) {
365 1308 phoenix 
          cucdebug (1, "Invalid dest conditional type opt%x op%lx\n", ii->opt[0], ii->op[0]);
366 930 markom 
          goto err;
367 
        }
368 
      }
369 1061 markom 
      for (k = 0; k < MAX_OPERANDS; k++) {
370 930 markom 
        if (ii->opt[k] & OPT_REF) {
371 
          int t = ii->op[k];
372 1557 nogj 
          if (REF_BB(t) >= f->num_bb || REF_I (t) >= f->bb[REF_BB(t)].ninsn ||
373 
              ((ii->index == II_CMOV || ii->index == II_ADD) &&
374 
               (((f->INSN(t).type & IT_COND) != (ii->type & IT_COND) && k < 3) ||
375 
               ((!(f->INSN(t).type & IT_COND) && k == 3))))) {
376 1062 markom 
            cucdebug (1, "Conditional misused\n");
377 
            goto err;
378 
          }
379 905 markom 
        }
380 1061 markom 
        if (k && ii->opt[k] & OPT_DEST) {
381 
          cucdebug (1, "Destination only allowed for op0!\n");
382 
          goto err;
383 
        }
384 
      }
385 930 markom 
    }
386 905 markom 
  }
387 930 markom 
  return;
388 
err:
389 1062 markom 
  cucdebug (1, "Anomaly detected at [%x_%x].%i\n", i, j, k);
390 930 markom 
  print_cuc_bb (f, "ANOMALY");
391 1062 markom 
  cucdebug (1, "Anomaly detected at [%x_%x].%i\n", i, j, k);
392 930 markom 
  exit (1);
393 905 markom 
}
394 
 
395 879 markom 
/* Build basic blocks */
396 
void build_bb (cuc_func *f)
397 
{
398 
  int i, j, k;
399 
  for (i = 0; i < f->num_bb; i++) {
400 
    if (f->bb[i].last < 0) f->bb[i].ninsn = MAX_REGS - 1;
401 
    else f->bb[i].ninsn = f->bb[i].last - f->bb[i].first + 1 + MAX_REGS - 1;
402 
    assert (f->bb[i].ninsn >= MAX_REGS - 1);
403 
    f->bb[i].insn = (cuc_insn *) malloc (sizeof (cuc_insn) * f->bb[i].ninsn);
404 
    assert (f->bb[i].insn);
405 
    f->bb[i].nmemory = 0;
406 
    f->bb[i].unrolled = 1;
407 
 
408 
    /* Save space for conditional moves, exclude r0, place lrbb instead */
409 
    change_insn_type (&f->bb[i].insn[0], II_LRBB);
410 
    strcpy (f->bb[i].insn[0].disasm, "lrbb");
411 930 markom 
    f->bb[i].insn[0].type = IT_UNUSED | IT_COND;
412 879 markom 
    f->bb[i].insn[0].dep = NULL;
413 
    f->bb[i].insn[0].op[0] = LRBB_REG; f->bb[i].insn[0].opt[0] = OPT_REGISTER | OPT_DEST;
414 
    f->bb[i].insn[0].opt[1] = OPT_LRBB;
415 
    f->bb[i].insn[0].opt[2] = f->bb[i].insn[0].opt[3] = OPT_NONE;
416 
    for (j = 1; j < MAX_REGS - 1; j++) {
417 
      change_insn_type (&f->bb[i].insn[j], II_CMOV);
418 
      strcpy (f->bb[i].insn[j].disasm, "cmov");
419 930 markom 
      f->bb[i].insn[j].type = j == FLAG_REG || j == LRBB_REG ? IT_COND : 0;
420 879 markom 
      f->bb[i].insn[j].dep = NULL;
421 
      f->bb[i].insn[j].opt[0] = f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_REGISTER;
422 
      f->bb[i].insn[j].opt[0] |= OPT_DEST;
423 
      f->bb[i].insn[j].op[0] = f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = j;
424 
      f->bb[i].insn[j].op[3] = LRBB_REG; f->bb[i].insn[j].opt[3] = OPT_REGISTER;
425 
    }
426 897 markom 
 
427 
    /* Relocate instructions */
428 879 markom 
    for (j = MAX_REGS - 1; j < f->bb[i].ninsn; j++) {
429 
      f->bb[i].insn[j] = insn[f->bb[i].first + j - (MAX_REGS - 1)];
430 
      for (k = 0; k < MAX_OPERANDS; k++)
431 
        if (f->bb[i].insn[j].opt[k] & OPT_REF) {
432 
          int b1;
433 
          for (b1 = 0; b1 < i; b1++)
434 898 markom 
            if (f->bb[b1].first <= (signed) f->bb[i].insn[j].op[k]
435 
              && (signed)f->bb[i].insn[j].op[k] <= f->bb[b1].last) break;
436 879 markom 
          assert (b1 < f->num_bb);
437 
          f->bb[i].insn[j].op[k] = REF (b1, f->bb[i].insn[j].op[k] - f->bb[b1].first + MAX_REGS - 1);
438 
        }
439 
      if (f->bb[i].insn[j].type & IT_MEMORY) f->bb[i].nmemory++;
440 
    }
441 
  }
442 905 markom 
  cuc_check (f);
443 879 markom 
}
444 
 
445 1042 markom 
/* Does simplification on blocks A, B, C:
446 
   A->B->C, A->C to just A->B->C */
447 
static void simplify_bb (cuc_func *f, int pred, int s1, int s2, int neg)
448 
{
449 
  cuc_insn *last;
450 
  int i;
451 
  if (cuc_debug >= 3) print_cuc_bb (f, "BEFORE_SIMPLIFY");
452 
  cucdebug (3, "simplify %x->%x->%x (%i)\n", pred, s1, s2, neg);
453 
  assert (s2 != pred); /* Shouldn't occur => stupid */
454 
  f->bb[pred].next[1] = -1;
455 
  f->bb[pred].next[0] = s1;
456 
 
457 
  if (f->bb[s2].prev[0] == pred) {
458 
    f->bb[s2].prev[0] = f->bb[s2].prev[1];
459 
    f->bb[s2].prev[1] = -1;
460 
  } else if (f->bb[s2].prev[1] == pred) {
461 
    f->bb[s2].prev[1] = -1;
462 
  } else assert (0);
463 
 
464 
  last = &f->bb[pred].insn[f->bb[pred].ninsn - 1];
465 
  assert (last->type & IT_BRANCH);
466 
  for (i = 0; i < f->bb[s2].ninsn; i++) {
467 
    cuc_insn *ii= &f->bb[s2].insn[i];
468 
    if (ii->index == II_LRBB) {
469 
      change_insn_type (ii, II_CMOV);
470 
      ii->type = IT_COND;
471 
      ii->op[1] = neg ? 0 : 1; ii->opt[1] = OPT_CONST;
472 
      ii->op[2] = neg ? 1 : 0; ii->opt[2] = OPT_CONST;
473 
      ii->op[3] = last->op[1]; ii->opt[3] = last->opt[1];
474 
    }
475 
  }
476 
  change_insn_type (last, II_NOP);
477 
  if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_SIMPLIFY");
478 
}
479 
 
480 879 markom 
/* type == 0; keep predecessor condition
481 
 * type == 1; keep successor condition
482 
 * type == 2; join loop unrolled blocks */
483 
static void join_bb (cuc_func *f, int pred, int succ, int type)
484 
{
485 905 markom 
  int i, j, k, n1, n2, ninsn, add_cond = 0;
486 1557 nogj 
  unsigned long cond_op = 0, cond_opt = 0;
487 879 markom 
  cuc_insn *insn;
488 
 
489 905 markom 
  if (cuc_debug) cuc_check (f);
490 897 markom 
  cucdebug (3, "%x <= %x+%x (%i)\n", pred, pred, succ, type);
491 
  cucdebug (3, "%x %x\n", f->bb[pred].ninsn, f->bb[succ].ninsn);
492 
  if (cuc_debug >= 3) fflush (stdout);
493 879 markom 
 
494 905 markom 
  n1 = f->bb[pred].ninsn;
495 
  n2 = f->bb[succ].ninsn;
496 
  if (n1 <= 0
497 
   || !(f->bb[pred].insn[n1 - 1].type & IT_BRANCH)) type = 1;
498 879 markom 
  if (type == 0 && f->bb[succ].prev[0] == f->bb[succ].next[0]) add_cond = 1;
499 905 markom 
  if (type == 2) add_cond = 1;
500 
 
501 1045 markom 
  //assert (f->bb[pred].next[0] == f->bb[succ].next[0] || type != 2); /* not supported */
502 879 markom 
 
503 905 markom 
  ninsn = n1 + n2 + (type == 1 ? 0 : 1) + (add_cond ? MAX_REGS : 0);
504 879 markom 
 
505 
  insn = (cuc_insn *) malloc (ninsn * sizeof (cuc_insn));
506 905 markom 
  for (i = 0; i < n1; i++) insn[i] = f->bb[pred].insn[i];
507 
  /* when type == 0, we move the last (jump) instruction to the end */
508 879 markom 
  if (type == 0 || type == 2) {
509 905 markom 
    /* Move first branch instruction to the end */
510 
    assert (insn[n1 - 1].type & IT_BRANCH);
511 
    insn[ninsn - 1] = insn[n1 - 1];
512 
    cond_op = insn[n1 - 1].op[1];
513 
    cond_opt = insn[n1 - 1].opt[1];
514 
 
515 
    /* Remove old branch */
516 
    change_insn_type (&insn[n1 - 1], II_NOP);
517 879 markom 
  }
518 
  /* Copy second block */
519 905 markom 
  for (i = 0; i < n2; i++) insn[i + n1] = f->bb[succ].insn[i];
520 902 markom 
 
521 
  /* and when type == 2, we may need to add sfor instruction, to quit when either is true */
522 
  if (type == 2) {
523 905 markom 
    /* Move second branch instruction to the end */
524 
    if (insn[n1 + n2 - 1].type & IT_BRANCH) {
525 
      insn[ninsn - 1] = insn[n1 + n2 - 1];
526 
 
527 
      /* Use conditional from cmov FLAG_REG, c_p, c_s, c_p */
528 
      insn[ninsn - 1].op[1] = REF (pred, n1 + n2 + FLAG_REG); insn[ninsn - 1].opt[1] = OPT_REF;
529 
 
530 
      /* Remove old one */
531 
      change_insn_type (&insn[n1 + n2 - 1], II_NOP);
532 
    } else change_insn_type (&insn[ninsn - 1], II_NOP); /* do not use branch slot */
533 902 markom 
  }
534 
 
535 905 markom 
#if 1
536 927 markom 
  /* LRBB at start of succ BB is not valid anymore */
537 933 markom 
  if (n1 > 0 && insn[n1].index == II_LRBB) {
538 925 markom 
    if (type == 1) {
539 
      /* We have two possibilities, how this could have happened:
540 
         1. we just moved second predecessor of succ to pred,
541 
            pred now having two predecessors => everything is ok
542 
         2. we just moved second predecessor of succ to pred,
543 
            now, having just one predecessor => LRBB is not needed anymore */
544 
      if (f->bb[pred].prev[1] < 0) { /* handle second option */
545 
        change_insn_type (&insn[n1], II_ADD);
546 
        insn[n1].op[1] = 1; insn[n1].opt[1] = OPT_CONST;
547 
        insn[n1].op[2] = 0; insn[n1].opt[2] = OPT_CONST;
548 
        insn[n1].opt[3] = OPT_NONE;
549 
      }
550 
    } else {
551 
      assert (0); /* not tested yet */
552 
      change_insn_type (&insn[n1], II_NOP);
553 
      for (i = n1; i < ninsn; i++)
554 
        if (insn[i].index == II_CMOV && insn[i].op[3] == REF (pred, n1)) {
555 
          assert (insn[i].opt[3] == OPT_REF);
556 
          insn[i].op[3] = cond_op;
557 
          insn[i].opt[3] = cond_opt;
558 
          if (f->bb[pred].next[0] != succ) {
559 
            unsigned long t; /* negate conditional -- exchange */
560 
            assert (f->bb[pred].next[1] == succ);
561 
            t = insn[i].op[1];
562 
            insn[i].op[1] = insn[i].op[2];
563 
            insn[i].op[2] = t;
564 
            t = insn[i].opt[1];
565 
            insn[i].opt[1] = insn[i].opt[2];
566 
            insn[i].opt[2] = t;
567 
          }
568 902 markom 
        }
569 925 markom 
    }
570 902 markom 
  }
571 905 markom 
#endif
572 879 markom 
 
573 
  for (i = 0; i < ninsn; i++) reloc[i] = -1;
574 
 
575 
  /* Add conditional instructions if required */
576 
  if (add_cond) {
577 
    recalc_last_used_reg (f, pred);
578 
    recalc_last_used_reg (f, succ);
579 1045 markom 
 
580 879 markom 
    /* r0 -- add nop for it */
581 905 markom 
    change_insn_type (&insn[n1 + n2], II_NOP);
582 879 markom 
    for (i = 1; i < MAX_REGS; i++) {
583 905 markom 
      cuc_insn *ii = &insn[n1 + n2 + i];
584 879 markom 
      int a = f->bb[pred].last_used_reg[i];
585 
      int b = f->bb[succ].last_used_reg[i];
586 
 
587 1045 markom 
      /* We have deleted first branch instruction, now we must setup FLAG_REG,
588 
         to point to conditional */
589 
      if (i == FLAG_REG) {
590 
        change_insn_type (ii, II_CMOV);
591 
        ii->type = i == FLAG_REG || i == LRBB_REG ? IT_COND : 0;
592 
        ii->dep = NULL;
593 
        ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
594 
        ii->op[1] = cond_op; ii->opt[1] = cond_opt;
595 
        if (b >= 0) {
596 
          ii->op[2] = b; ii->opt[2] = OPT_REF;
597 
        } else {
598 
          ii->op[2] = cond_op; ii->opt[2] = cond_opt;
599 
        }
600 
        ii->op[3] = cond_op; ii->opt[3] = cond_opt;
601 
        reloc[REF_I(a)] = REF (pred, n1 + n2 + i);
602 
      } else if (b < 0) change_insn_type (ii, II_NOP);
603 879 markom 
      else if (a < 0) {
604 
        change_insn_type (ii, II_ADD);
605 930 markom 
        ii->type = i == FLAG_REG || i == LRBB_REG ? IT_COND : 0;
606 879 markom 
        ii->dep = NULL;
607 
        ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
608 
        ii->op[1] = b; ii->opt[1] = OPT_REF;
609 
        ii->op[2] = 0; ii->opt[2] = OPT_CONST;
610 905 markom 
        ii->opt[3] = OPT_NONE;
611 879 markom 
      } else if (b >= 0) {
612 
        change_insn_type (ii, II_CMOV);
613 930 markom 
        ii->type = i == FLAG_REG || i == LRBB_REG ? IT_COND : 0;
614 879 markom 
        ii->dep = NULL;
615 
        ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
616 
        ii->op[1] = a; ii->opt[1] = OPT_REF;
617 
        ii->op[2] = b; ii->opt[2] = OPT_REF;
618 
        ii->op[3] = cond_op; ii->opt[3] = cond_opt;
619 905 markom 
        reloc[REF_I(a)] = REF (pred, n1 + n2 + i);
620 879 markom 
      }
621 
      sprintf (ii->disasm, "cmov (join BB)");
622 
    }
623 
  }
624 
 
625 905 markom 
  if (cuc_debug) cuc_check (f);
626 879 markom 
  i = 0;
627 
  switch (type) {
628 
  case 0:
629 1061 markom 
    assert (f->bb[pred].next[0] >= 0);
630 879 markom 
    if (f->bb[pred].next[0] == succ) f->bb[pred].next[0] = f->bb[succ].next[0];
631 
    if (f->bb[pred].next[1] == succ) f->bb[pred].next[1] = f->bb[succ].next[0];
632 
    break;
633 
  case 1:
634 1061 markom 
    assert (f->bb[pred].next[0] >= 0 && f->bb[pred].next[0] != BBID_END);
635 879 markom 
    f->bb[pred].next[0] = f->bb[succ].next[0];
636 
    f->bb[pred].next[1] = f->bb[succ].next[1];
637 
    break;
638 905 markom 
  case 2:
639 1061 markom 
    assert (f->bb[pred].next[0] >= 0 && f->bb[pred].next[0] != BBID_END);
640 905 markom 
    f->bb[pred].next[0] = f->bb[succ].next[0];
641 
    f->bb[pred].next[1] = f->bb[succ].next[1];
642 
    break;
643 879 markom 
  }
644 924 markom 
  if (f->bb[pred].next[0] < 0) f->bb[pred].next[0] = f->bb[pred].next[1];
645 879 markom 
  if (f->bb[pred].next[0] == f->bb[pred].next[1]) f->bb[pred].next[1] = -1;
646 927 markom 
 
647 1061 markom 
  if (type == 0) assert (f->bb[succ].next[1] < 0);
648 
 
649 927 markom 
  /* We just did something stupid -- we joined two predecessors into one;
650 
     succ may need the information from which block we came.  We will repair
651 
     this by converting LRBB to CMOV */
652 930 markom 
  for (j = 0; j < 2; j++) {
653 
    int nb = f->bb[pred].next[j];
654 927 markom 
    int t;
655 
 
656 
    /* check just valid connections */
657 
    if (nb < 0 || nb == BBID_END) continue;
658 
 
659 
    /* check type */
660 
    if (f->bb[nb].prev[0] == pred && f->bb[nb].prev[1] == succ) t = 1;
661 
    else if (f->bb[nb].prev[1] == pred && f->bb[nb].prev[0] == succ) t = 0;
662 
    else continue;
663 
 
664 930 markom 
    /* check all LRBB instructions.  */
665 
    for (i = 0; i < f->bb[nb].ninsn; i++)
666 
      if (f->bb[nb].insn[i].index == II_LRBB) {
667 
        cuc_insn *lrbb =&f->bb[nb].insn[i];
668 
        change_insn_type (lrbb, II_CMOV);
669 
        lrbb->op[1] = t; lrbb->opt[1] = OPT_CONST;
670 
        lrbb->op[2] = 1 - t; lrbb->opt[2] = OPT_CONST;
671 
        lrbb->op[3] = cond_op; lrbb->opt[3] = cond_opt;
672 
        lrbb->type |= IT_COND;
673 
      }
674 927 markom 
  }
675 
 
676 879 markom 
  f->bb[succ].type = BB_DEAD;
677 997 markom 
  //PRINTF (" %x %x %x %x %x\n", f->bb[pred].next[0], f->bb[pred].next[1], f->bb[succ].next[0], f->bb[succ].next[1], insn[ninsn - 1].type);
678 905 markom 
  /* remove branch instruction, if there is only one successor */
679 933 markom 
  if (f->bb[pred].next[1] < 0 && ninsn > 0 && insn[ninsn - 1].type & IT_BRANCH) {
680 925 markom 
    assert (f->bb[pred].next[0] != pred); /* end BB, loop should not be possible */
681 905 markom 
    change_insn_type (&insn[ninsn - 1], II_NOP);
682 925 markom 
  }
683 879 markom 
 
684 
  /* Set max count */
685 
  if (f->bb[pred].cnt < f->bb[succ].cnt) f->bb[pred].cnt = f->bb[succ].cnt;
686 
  f->bb[pred].ninsn = ninsn;
687 905 markom 
  f->bb[succ].ninsn = 0;
688 879 markom 
  free (f->bb[pred].insn); f->bb[pred].insn = NULL;
689 
  free (f->bb[succ].insn); f->bb[succ].insn = NULL;
690 
  f->bb[pred].insn = insn;
691 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
692 
    if (f->bb[i].prev[0] == succ) f->bb[i].prev[0] = pred;
693 
    if (f->bb[i].prev[1] == succ) f->bb[i].prev[1] = pred;
694 
    if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
695 
    for (j = 0; j < f->bb[i].ninsn; j++)
696 
      for (k = 0; k < MAX_OPERANDS; k++)
697 
        if (f->bb[i].insn[j].opt[k] & OPT_REF) {
698 
          /* Check if we are referencing successor BB -> relocate to second part of
699 
             the new block */
700 
          if (REF_BB (f->bb[i].insn[j].op[k]) == succ) {
701 905 markom 
            int t = f->bb[i].insn[j].op[k];
702 
            int ndest = REF (pred, REF_I (t) + n1);
703 997 markom 
            //PRINTF ("%x: %x %x\n", REF(i, j), t, ndest);
704 879 markom 
 
705 905 markom 
            /* We've found a reference to succ. block, being removed, relocate */
706 
            f->bb[i].insn[j].op[k] = ndest;
707 879 markom 
          } else if (REF_BB(f->bb[i].insn[j].op[k]) == pred) {
708 
            if (i != pred && reloc[REF_I(f->bb[i].insn[j].op[k])] >= 0) {
709 
              f->bb[i].insn[j].op[k] = reloc[REF_I(f->bb[i].insn[j].op[k])];
710 
            }
711 
          }
712 
        }
713 
  }
714 
 
715 905 markom 
  if (cuc_debug) cuc_check (f);
716 883 markom 
  if (cuc_debug >= 3) print_cuc_bb (f, "join");
717 879 markom 
}
718 
 
719 
/* Optimize basic blocks */
720 931 markom 
int optimize_bb (cuc_func *f)
721 879 markom 
{
722 931 markom 
  int modified = 0;
723 879 markom 
  int i, j;
724 
remove_lrbb:
725 
  /* we can remove lrbb instructions from blocks with just one predecessor */
726 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
727 
    if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* exactly one predecessor */
728 
      for (j = 0; j < f->bb[i].ninsn; j++)
729 
        if (f->bb[i].insn[j].index == II_LRBB) {
730 
          cuc_insn *t;
731 925 markom 
          cucdebug (4, "-lrbb %x.%x\n", i, j);
732 879 markom 
 
733 
          /* Change to add LRBB, 0, 0 */
734 
          change_insn_type (&f->bb[i].insn[j], II_ADD);
735 
          f->bb[i].insn[j].type &= ~IT_VOLATILE;
736 
          f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_CONST;
737 
          f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = 0; /* always use left block */
738 
          f->bb[i].insn[j].opt[3] = OPT_NONE;
739 931 markom 
          modified = 1;
740 934 markom 
          if (f->bb[i].prev[0] != BBID_START && f->bb[f->bb[i].prev[0]].ninsn > 0) {
741 932 markom 
            t = &f->bb[f->bb[i].prev[0]].insn[f->bb[f->bb[i].prev[0]].ninsn - 1];
742 879 markom 
 
743 932 markom 
            /* If the predecessor still has a conditional jump instruction, we must be careful.
744 
               If next[0] == next[1] join them. Now we will link lrbb and correct the situation */
745 
            if (t->type & IT_BRANCH) { /* We must set a reference to branch result */
746 
              f->bb[i].insn[j].opt[1] = t->opt[1];
747 
              f->bb[i].insn[j].op[1] = t->op[1];
748 
              /* sometimes branch is not needed anymore */
749 
              if (f->bb[f->bb[i].prev[0]].next[1] < 0) change_insn_type (t, II_NOP);
750 
            }
751 879 markom 
          }
752 
        }
753 
    }
754 
  }
755 
 
756 927 markom 
  /* Ordering of joining types is cruical -- we should concat all directly connected BBs
757 
     together first, so when we do a type != 1 joining, we can remove LRBB, directly by
758 
     looking at number of its predeccessors */
759 879 markom 
 
760 
  /* Type 1 joining
761 
     1. link between pred & succ
762 
     2. no other pred's successors
763 925 markom 
     3. no other succ's predecessors, except if pred has max one */
764 932 markom 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
765 
    int p = f->bb[i].prev[0];
766 
    if (p < 0 || p == BBID_START) continue;
767 925 markom 
    /* one successor and max sum of 3 predecessors */
768 932 markom 
    if (f->bb[p].next[0] >= 0 && f->bb[p].next[1] < 0
769 
     && (f->bb[p].prev[1] < 0 || f->bb[i].prev[1] < 0)) {
770 925 markom 
      /* First we will move all predecessors from succ to pred, and then we will do
771 
         real type 1 joining */
772 932 markom 
      if (f->bb[i].prev[1] >= 0 && f->bb[i].prev[1] != BBID_START) {
773 
        int p1 = f->bb[i].prev[1];
774 925 markom 
        /* joining is surely not worth another extra memory access */
775 932 markom 
        if (f->bb[p].nmemory) continue;
776 
        if (f->bb[p].prev[0] >= 0) {
777 
           assert (f->bb[p].prev[1] < 0);
778 
           f->bb[p].prev[1] = p1;
779 
        } else f->bb[p].prev[0] = p1;
780 
        if (f->bb[p1].next[0] == i) f->bb[p1].next[0] = p;
781 
        else if (f->bb[p1].next[1] == i) f->bb[p1].next[1] = p;
782 925 markom 
        else assert (0);
783 
        f->bb[i].prev[1] = -1;
784 
      }
785 932 markom 
      assert (p >= 0 && f->bb[i].prev[1] < 0); /* one predecessor */
786 
      join_bb (f, p, i, 1);
787 931 markom 
      modified = 1;
788 879 markom 
      goto remove_lrbb;
789 
    }
790 932 markom 
  }
791 927 markom 
 
792 
  /* Type 0 joining
793 
     1. link between pred & succ
794 
     2. no memory accesses in succ
795 
     3. optional pred's second successors
796 
     4. max. one succ's successors */
797 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
798 932 markom 
    if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[0] != BBID_START
799 
     && f->bb[i].prev[1] < 0 /* one predecessor */
800 927 markom 
     && f->bb[i].next[1] < 0 /* max. one successor */
801 
     && f->bb[i].nmemory == 0) {                  /* and no memory acceses */
802 
      join_bb (f, f->bb[i].prev[0], i, 0);
803 931 markom 
      modified = 1;
804 927 markom 
      goto remove_lrbb;
805 
    }
806 879 markom 
 
807 
  /* Type 2 joining
808 
     1. link between pred & succ
809 
     2. succ has exactly one predeccessor
810 
     3. pred & succ share common successor
811 
     4. optional succ's second successor */
812 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
813 
    if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* one predecessor */
814 
      int p = f->bb[i].prev[0];
815 932 markom 
      if (p == BBID_START) continue;
816 905 markom 
#if 0 /* not yet supported */
817 
      if (f->bb[p].next[0] == i
818 
       && (f->bb[i].next[1] == f->bb[p].next[1]
819 
        || f->bb[i].next[1] == f->bb[p].next[0])) {
820 
        join_bb (f, p, i, 2);
821 897 markom 
        goto remove_lrbb;
822 
      }
823 905 markom 
#endif
824 
      if (f->bb[p].next[1] == i
825 1045 markom 
       && (f->bb[p].next[0] == f->bb[i].next[1]
826 
        || f->bb[p].next[0] == f->bb[i].next[0])) {
827 905 markom 
        join_bb (f, p, i, 2);
828 931 markom 
        modified = 1;
829 905 markom 
        goto remove_lrbb;
830 
      }
831 879 markom 
    }
832 1042 markom 
 
833 
  /* BB simplify:
834 
     1. a block has exactly 2 successors A and B
835 
     2. A has exactly one successor -- B
836 
     3. A has no memory accesses
837 
     to:
838 
     flow always goes though A, LRBB is replaced by current block conditional
839 
    */
840 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
841 
    if (f->bb[i].next[0] >= 0 && f->bb[i].next[0] != BBID_END
842 
      && f->bb[i].next[1] >= 0 && f->bb[i].next[1] != BBID_END) {
843 
      int a = f->bb[i].next[0];
844 
      int b = f->bb[i].next[1];
845 
      int neg = 0;
846 
      /* Exchange? */
847 
      if (f->bb[b].next[0] == a && f->bb[b].next[1] < 0) {
848 
        int t = a;
849 
        a = b;
850 
        b = t;
851 
        neg = 1;
852 
      }
853 
      /* Do the simplification if possible */
854 
      if (f->bb[a].next[0] == b && f->bb[a].next[1] < 0
855 
       && f->bb[a].nmemory == 0) {
856 
        simplify_bb (f, i, a, b, neg);
857 
        modified = 1;
858 
        goto remove_lrbb;
859 
      }
860 
    }
861 
 
862 931 markom 
  return modified;
863 879 markom 
}
864 
 
865 
/* Removes BBs marked as dead */
866 931 markom 
int remove_dead_bb (cuc_func *f)
867 879 markom 
{
868 
  int i, j, k, d = 0;
869 
 
870 
  for (i = 0; i < f->num_bb; i++) if (f->bb[i].type & BB_DEAD) {
871 
    if (f->bb[i].insn) free (f->bb[i].insn);
872 
    f->bb[i].insn = NULL;
873 
    reloc[i] = -1;
874 
  } else {
875 
    reloc[i] = d;
876 
    f->bb[d++] = f->bb[i];
877 
  }
878 931 markom 
  if (f->num_bb == d) return 0;
879 879 markom 
  f->num_bb = d;
880 
 
881 
  /* relocate initial blocks */
882 
  for (i = 0; i < f->num_init_bb; i++)
883 
    f->init_bb_reloc[i] = reloc[f->init_bb_reloc[i]];
884 
 
885 
  /* repair references */
886 
  for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
887 973 markom 
          cucdebug (5, "%x %x %x %x %x\n", i, f->bb[i].prev[0], f->bb[i].prev[1], f->bb[i].next[0], f->bb[i].next[1]);
888 925 markom 
          fflush (stdout);
889 932 markom 
    if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[0] != BBID_START)
890 
      assert ((f->bb[i].prev[0] = reloc[f->bb[i].prev[0]]) >= 0);
891 
    if (f->bb[i].prev[1] >= 0 && f->bb[i].prev[1] != BBID_START)
892 
      assert ((f->bb[i].prev[1] = reloc[f->bb[i].prev[1]]) >= 0);
893 925 markom 
    if (f->bb[i].next[0] >= 0 && f->bb[i].next[0] != BBID_END)
894 
      assert ((f->bb[i].next[0] = reloc[f->bb[i].next[0]]) >= 0);
895 
    if (f->bb[i].next[1] >= 0 && f->bb[i].next[1] != BBID_END)
896 
      assert ((f->bb[i].next[1] = reloc[f->bb[i].next[1]]) >= 0);
897 879 markom 
    if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
898 
    if (f->bb[i].next[0] == f->bb[i].next[1]) f->bb[i].next[1] = -1;
899 
 
900 
    for (j = 0; j < f->bb[i].ninsn; j++)
901 
      for (k = 0; k < MAX_OPERANDS; k++)
902 1308 phoenix 
        if ((f->bb[i].insn[j].opt[k] & OPT_BB) &&
903 
                                        ((signed)f->bb[i].insn[j].op[k] >= 0)) {
904 925 markom 
          if (f->bb[i].insn[j].op[k] != BBID_END)
905 
            assert ((f->bb[i].insn[j].op[k] = reloc[f->bb[i].insn[j].op[k]]) >= 0);
906 
        } else if (f->bb[i].insn[j].opt[k] & OPT_REF) {
907 879 markom 
          int t = f->bb[i].insn[j].op[k];
908 
          assert (reloc[REF_BB(t)] >= 0);
909 
          f->bb[i].insn[j].op[k] = REF (reloc[REF_BB(t)], REF_I (t));
910 
        }
911 
  }
912 931 markom 
  return 1;
913 879 markom 
}
914 
 
915 
/* Recursive calculation of dependencies */
916 1557 nogj 
static void reg_dep_rec (cuc_func *f, int cur)
917 879 markom 
{
918 
  int i, j;
919 
  cuc_insn *insn = f->bb[cur].insn;
920 
 
921 997 markom 
  //PRINTF ("\n %i", cur);
922 879 markom 
  /* Spread only, do not loop */
923 
  if (f->bb[cur].tmp) return;
924 
  f->bb[cur].tmp = 1;
925 997 markom 
  //PRINTF ("!   ");
926 879 markom 
 
927 
  for (i = 0; i < f->bb[cur].ninsn; i++) {
928 
    /* Check for destination operand(s) */
929 
    for (j = 0; j < MAX_OPERANDS; j++) if (insn[i].opt[j] & OPT_DEST)
930 
      if ((insn[i].opt[j] & ~OPT_DEST) == OPT_REGISTER && (signed)insn[i].op[j] >= 0) {
931 997 markom 
        //PRINTF ("%i:%i,%x ", insn[i].op[j], i, REF (cur, i));
932 879 markom 
        assert (insn[i].op[j] > 0 && insn[i].op[j] < MAX_REGS); /* r0 should never be dest */
933 
        f->bb[cur].last_used_reg[insn[i].op[j]] = REF (cur, i);
934 
      }
935 
  }
936 
 
937 925 markom 
  if (f->bb[cur].next[0] >= 0 && f->bb[cur].next[0] != BBID_END)
938 
    reg_dep_rec (f, f->bb[cur].next[0]);
939 
  if (f->bb[cur].next[1] >= 0 && f->bb[cur].next[1] != BBID_END)
940 
    reg_dep_rec (f, f->bb[cur].next[1]);
941 879 markom 
}
942 
 
943 
/* Detect register dependencies */
944 
void reg_dep (cuc_func *f)
945 
{
946 
  int i, b, c;
947 
 
948 
  /* Set dead blocks */
949 
  for (b = 0; b < f->num_bb; b++) {
950 
    f->bb[b].tmp = 0;
951 
    for (i = 0; i < MAX_REGS; i++) f->bb[b].last_used_reg[i] = -1;
952 
  }
953 
 
954 
  /* Start with first block and set dependecies of all reachable blocks */
955 
  /* At the same time set last_used_regs */
956 
  reg_dep_rec (f, 0);
957 
 
958 
  for (i = 0; i < f->num_bb; i++)
959 
    if (f->bb[i].tmp) f->bb[i].tmp = 0;
960 
    else f->bb[i].type |= BB_DEAD;
961 
 
962 
  /* Detect loops; mark BBs where loops must be broken */
963 
  for (c = 0; c < f->num_bb; c++) {
964 1557 nogj 
    int min = 3, minb = 0;
965 879 markom 
 
966 
    /* search though all non-visited for minimum number of unvisited predecessors */
967 
    for (b = 0; b < f->num_bb; b++) if (!f->bb[b].tmp) {
968 
      int tmp = 0;
969 932 markom 
      if (f->bb[b].prev[0] >= 0 && f->bb[b].prev[0] != BBID_START
970 
       && !f->bb[f->bb[b].prev[0]].tmp) tmp++;
971 
      if (f->bb[b].prev[1] >= 0 && f->bb[b].prev[1] != BBID_START
972 
       && !f->bb[f->bb[b].prev[1]].tmp) tmp++;
973 879 markom 
      if (tmp < min) {
974 
        minb = b;
975 
        min = tmp;
976 
        if (tmp == 0) break; /* We already have the best one */
977 
      }
978 
    }
979 
    b = minb;
980 
    f->bb[b].tmp = 1; /* Mark visited */
981 883 markom 
    cucdebug (3, "minb %i min %i\n", minb, min);
982 879 markom 
    if (min) { /* We just broke the loop */
983 
      f->bb[b].type |= BB_INLOOP;
984 
    }
985 
  }
986 
 
987 
  /* Set real predecessors in cmov instructions to previous blocks */
988 
  for (b = 0; b < f->num_bb; b++)
989 
    for (i = 1; i < MAX_REGS - 1; i++) {
990 
      int pa, pb;
991 
      assert (f->bb[b].insn[i].index ==  II_CMOV);
992 1557 nogj 
      assert (f->bb[b].insn[i].opt[0] == (OPT_REGISTER | OPT_DEST));
993 879 markom 
      assert (f->bb[b].insn[i].op[0] == i);
994 932 markom 
      if (f->bb[b].prev[0] < 0 || f->bb[b].prev[0] == BBID_START) pa = -1;
995 879 markom 
      else pa = f->bb[f->bb[b].prev[0]].last_used_reg[i];
996 932 markom 
      if (f->bb[b].prev[1] < 0 || f->bb[b].prev[1] == BBID_START) pb = -1;
997 879 markom 
      else pb = f->bb[f->bb[b].prev[1]].last_used_reg[i];
998 
 
999 
      /* We do some very simple optimizations right away to make things more readable */
1000 
      if (pa < 0 && pb < 0) {
1001 
        /* Was not used at all */
1002 
        change_insn_type (&f->bb[b].insn[i], II_ADD);
1003 
        f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
1004 
        f->bb[b].insn[i].opt[3] = OPT_NONE;
1005 
      } else if (pa < 0) {
1006 
        change_insn_type (&f->bb[b].insn[i], II_ADD);
1007 
        assert (f->INSN(pb).opt[0] == (OPT_REGISTER | OPT_DEST));
1008 
        f->bb[b].insn[i].op[1] = pb; f->bb[b].insn[i].opt[1] = OPT_REF;
1009 
        f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
1010 
        f->bb[b].insn[i].opt[3] = OPT_NONE;
1011 
      } else if (pb < 0) {
1012 
        change_insn_type (&f->bb[b].insn[i], II_ADD);
1013 
        assert (f->INSN(pa).opt[0] == (OPT_REGISTER | OPT_DEST));
1014 
        f->bb[b].insn[i].op[1] = pa; f->bb[b].insn[i].opt[1] = OPT_REF;
1015 
        f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
1016 
        f->bb[b].insn[i].opt[3] = OPT_NONE;
1017 
      } else {
1018 
        int t = REF (b, 0); /* lrbb should be first instruction */
1019 
        assert (f->INSN(t).index == II_LRBB);
1020 
 
1021 
        f->bb[b].insn[i].op[1] = pa; f->bb[b].insn[i].opt[1] = OPT_REF;
1022 
        assert (f->INSN(pa).opt[0] == (OPT_REGISTER | OPT_DEST));
1023 
 
1024 
        f->bb[b].insn[i].op[2] = pb; f->bb[b].insn[i].opt[2] = OPT_REF;
1025 
        assert (f->INSN(pb).opt[0] == (OPT_REGISTER | OPT_DEST));
1026 
 
1027 
        /* Update op[3] -- flag register */
1028 
        assert (f->bb[b].insn[i].opt[3] == OPT_REGISTER);
1029 
        assert (f->bb[b].insn[i].op[3] == LRBB_REG);
1030 
        assert (t >= 0);
1031 
        f->bb[b].insn[i].opt[3] = OPT_REF; /* Convert already used regs to references */
1032 
        f->bb[b].insn[i].op[3] = t;
1033 
        assert (f->INSN(t).opt[0] == (OPT_REGISTER | OPT_DEST));
1034 
      }
1035 
    }
1036 
 
1037 
  /* assign register references */
1038 
  for (b = 0; b < f->num_bb; b++) {
1039 
    /* rebuild last used reg array */
1040 
    f->bb[b].last_used_reg[0] = -1;
1041 
    if (f->bb[b].insn[0].index == II_LRBB) f->bb[b].last_used_reg[LRBB_REG] = 0;
1042 
    else f->bb[b].last_used_reg[LRBB_REG] = -1;
1043 
 
1044 
    for (i = 1; i < MAX_REGS - 1; i++)
1045 
      f->bb[b].last_used_reg[i] = -1;
1046 
 
1047 
    /* Create references */
1048 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1049 
      int k;
1050 
      /* Check for source operands first */
1051 
      for (k = 0; k < MAX_OPERANDS; k++) {
1052 1308 phoenix 
        if (!(f->bb[b].insn[i].opt[k] & OPT_DEST)) {
1053 
          if (f->bb[b].insn[i].opt[k] & OPT_REGISTER) {
1054 
            int t = f->bb[b].last_used_reg[f->bb[b].insn[i].op[k]];
1055 879 markom 
 
1056 1308 phoenix 
            if (f->bb[b].insn[i].op[k] == 0) { /* Convert r0 to const0 */
1057 
              f->bb[b].insn[i].opt[k] = OPT_CONST;
1058 
              f->bb[b].insn[i].op[k] = 0;
1059 
            } else if (t >= 0) {
1060 
              f->bb[b].insn[i].opt[k] = OPT_REF; /* Convert already used regs to references */
1061 
              f->bb[b].insn[i].op[k] = t;
1062 
              assert (f->INSN(t).opt[0] == (OPT_REGISTER | OPT_DEST));
1063 
              //f->INSN(t).op[0] = -1;
1064 
            }
1065 
          } else if (f->bb[b].insn[i].opt[k] & OPT_REF) {
1066 
            //f->INSN(f->bb[b].insn[i].op[k]).op[0] = -1; /* Mark referenced */
1067 
            f->INSN(f->bb[b].insn[i].op[k]).type &= ~IT_UNUSED;
1068 
          }
1069 879 markom 
        }
1070 
      }
1071 
 
1072 
      /* Now check for destination operand(s) */
1073 
      for (k = 0; k < MAX_OPERANDS; k++) if (f->bb[b].insn[i].opt[k] & OPT_DEST)
1074 
        if ((f->bb[b].insn[i].opt[k] & ~OPT_DEST) == OPT_REGISTER
1075 
          && (int)f->bb[b].insn[i].op[k] >= 0) {
1076 
          assert (f->bb[b].insn[i].op[k] != 0); /* r0 should never be dest */
1077 
          f->bb[b].last_used_reg[f->bb[b].insn[i].op[k]] = REF (b, i);
1078 
        }
1079 
    }
1080 
  }
1081 
 
1082 
  /* Remove all unused lrbb */
1083 
  for (b = 0; b < f->num_bb; b++)
1084 
    for (i = 0; i < f->bb[b].ninsn; i++)
1085 
      if (f->bb[b].insn[i].type & IT_UNUSED) change_insn_type (&f->bb[b].insn[i], II_NOP);
1086 
 
1087 
  /* SSAs with final register value are marked as outputs */
1088 1061 markom 
  assert (f->bb[f->num_bb - 1].next[0] == BBID_END);
1089 939 markom 
  for (i = 0; i < MAX_REGS; i++) if (!caller_saved[i]) {
1090 879 markom 
    int t = f->bb[f->num_bb - 1].last_used_reg[i];
1091 
    /* Mark them volatile, so optimizer does not remove them */
1092 
    if (t >= 0) f->bb[REF_BB(t)].insn[REF_I(t)].type |= IT_OUTPUT;
1093 
  }
1094 939 markom 
  {
1095 
    int t = f->bb[f->num_bb - 1].last_used_reg[i];
1096 
    /* Mark them volatile, so optimizer does not remove them */
1097 
    if (t >= 0) f->bb[REF_BB(t)].insn[REF_I(t)].type |= IT_OUTPUT;
1098 
  }
1099 879 markom 
}
1100 
 
1101 897 markom 
/* split the BB, based on the group numbers in .tmp */
1102 
void expand_bb (cuc_func *f, int b)
1103 
{
1104 
  int n = f->num_bb;
1105 
  int mg = 0;
1106 
  int b1, i, j;
1107 
 
1108 
  for (i = 0; i < f->bb[b].ninsn; i++)
1109 
    if (f->bb[b].insn[i].tmp > mg) mg = f->bb[b].insn[i].tmp;
1110 
 
1111 
  /* Create copies */
1112 
  for (b1 = 1; b1 <= mg; b1++) {
1113 
    assert (f->num_bb < MAX_BB);
1114 
    cpy_bb (&f->bb[f->num_bb], &f->bb[b]);
1115 
    f->num_bb++;
1116 
  }
1117 
 
1118 
  /* Relocate */
1119 
  for (b1 = 0; b1 < f->num_bb; b1++)
1120 
    for (i = 0; i < f->bb[b1].ninsn; i++) {
1121 
      dep_list *d = f->bb[b1].insn[i].dep;
1122 
      for (j = 0; j < MAX_OPERANDS; j++)
1123 
        if (f->bb[b1].insn[i].opt[j] & OPT_REF) {
1124 
          int t = f->bb[b1].insn[i].op[j];
1125 
          if (REF_BB(t) == b && f->INSN(t).tmp != 0)
1126 
            f->bb[b1].insn[i].op[j] = REF (n + f->INSN(t).tmp - 1, REF_I(t));
1127 
        }
1128 
      while (d) {
1129 
        if (REF_BB (d->ref) == b && f->INSN(d->ref).tmp != 0)
1130 
          d->ref = REF (n + f->INSN(d->ref).tmp - 1, REF_I(d->ref));
1131 
        d = d->next;
1132 
      }
1133 
    }
1134 
 
1135 
  /* Delete unused instructions */
1136 
  for (j = 0; j <= mg; j++) {
1137 
    if (j == 0) b1 = b;
1138 
    else b1 = n + j - 1;
1139 
    for (i = 0; i < f->bb[b1].ninsn; i++) {
1140 
      if (f->bb[b1].insn[i].tmp != j)
1141 
        change_insn_type (&f->bb[b1].insn[i], II_NOP);
1142 
      f->bb[b1].insn[i].tmp = 0;
1143 
    }
1144 
    if (j < mg) {
1145 
      f->bb[b1].next[0] = n + j;
1146 
      f->bb[b1].next[1] = -1;
1147 
      f->bb[n + j].prev[0] = b1;
1148 
      f->bb[n + j].prev[1] = -1;
1149 
    } else {
1150 
      i = f->bb[b1].next[0];
1151 
      f->bb[n + j].prev[0] = j == 1 ? b : b1 - 1;
1152 
      f->bb[n + j].prev[1] = -1;
1153 925 markom 
      if (i >= 0 && i != BBID_END) {
1154 897 markom 
        if (f->bb[i].prev[0] == b) f->bb[i].prev[0] = b1;
1155 
        if (f->bb[i].prev[1] == b) f->bb[i].prev[1] = b1;
1156 
      }
1157 
      i = f->bb[b1].next[1];
1158 925 markom 
      if (i >= 0 && i != BBID_END) {
1159 897 markom 
        if (f->bb[i].prev[0] == b) f->bb[i].prev[0] = b1;
1160 
        if (f->bb[i].prev[1] == b) f->bb[i].prev[1] = b1;
1161 
      }
1162 
    }
1163 
  }
1164 
}
1165 
 
1166 879 markom 
/* Scans sequence of BBs and set bb[].cnt */
1167 
void generate_bb_seq (cuc_func *f, char *mp_filename, char *bb_filename)
1168 
{
1169 
  FILE *fi, *fo;
1170 
  struct mprofentry_struct *buf;
1171 
  const int bufsize = 256;
1172 
  unsigned long *bb_start;
1173 
  unsigned long *bb_end;
1174 
  int b, i, r;
1175 
  int curbb, prevbb = -1;
1176 
  unsigned long addr = -1;
1177 
  unsigned long prevaddr = -1;
1178 897 markom 
  int mssum = 0;
1179 
  int mlsum = 0;
1180 
  int mscnt = 0;
1181 
  int mlcnt = 0;
1182 940 markom 
  int reopened = 0;
1183 879 markom 
 
1184 940 markom 
  /* Use already opened stream? */
1185 
  if (runtime.sim.fmprof) {
1186 
    fi = runtime.sim.fmprof;
1187 
    reopened = 1;
1188 
    rewind (fi);
1189 
  } else assert (fi = fopen (mp_filename, "rb"));
1190 879 markom 
  assert (fo = fopen (bb_filename, "wb+"));
1191 
 
1192 
  assert (bb_start = (unsigned long *) malloc (sizeof (unsigned long) * f->num_bb));
1193 
  assert (bb_end = (unsigned long *) malloc (sizeof (unsigned long) * f->num_bb));
1194 
  for (b = 0; b < f->num_bb; b++) {
1195 
    bb_start[b] = f->start_addr + f->bb[b].first * 4;
1196 
    bb_end[b] = f->start_addr + f->bb[b].last * 4;
1197 997 markom 
    //PRINTF ("%i %x %x\n", b, bb_start[b], bb_end[b]);
1198 879 markom 
    f->bb[0].cnt = 0;
1199 
  }
1200 
 
1201 
  buf = (struct mprofentry_struct *) malloc (sizeof (struct mprofentry_struct) * bufsize);
1202 
  assert (buf);
1203 
 
1204 997 markom 
  //PRINTF ("BBSEQ:\n");
1205 879 markom 
  do {
1206 
    r = fread (buf, sizeof (struct mprofentry_struct), bufsize, fi);
1207 997 markom 
    //PRINTF ("r%i : ", r);
1208 879 markom 
    for (i = 0; i < r; i++) {
1209 
      if (buf[i].type & MPROF_FETCH) {
1210 997 markom 
        //PRINTF ("%x, ", buf[i].addr);
1211 879 markom 
        if (buf[i].addr >= f->start_addr && buf[i].addr <= f->end_addr) {
1212 
          assert (buf[i].type & MPROF_32);
1213 
          prevaddr = addr;
1214 
          addr = buf[i].addr;
1215 
          for (b = 0; b < f->num_bb; b++)
1216 
            if (bb_start[b] <= addr && addr <= bb_end[b]) break;
1217 
          assert (b < f->num_bb);
1218 
          curbb = b;
1219 
          if (prevaddr + 4 != addr) prevbb = -1;
1220 
        } else curbb = -1;
1221 
 
1222 1557 nogj 
        /* TODO: do not count interrupts */
1223 879 markom 
        if (curbb != prevbb && curbb >= 0) {
1224 
          fwrite (&curbb, sizeof (unsigned long), 1, fo);
1225 997 markom 
          //PRINTF (" [%i] ", curbb);
1226 879 markom 
          f->bb[curbb].cnt++;
1227 
          prevbb = curbb;
1228 
        }
1229 897 markom 
      } else {
1230 1308 phoenix 
        if (verify_memoryarea(buf[i].addr)) {
1231 1486 nogj 
          if (buf[i].type & MPROF_WRITE) mscnt++, mssum += cur_area->ops.delayw;
1232 
          else mlcnt++, mlsum += cur_area->ops.delayr;
1233 1308 phoenix 
        }
1234 879 markom 
      }
1235 
    }
1236 997 markom 
    //PRINTF ("\n");
1237 879 markom 
  } while (r == bufsize);
1238 997 markom 
  //PRINTF ("\n");
1239 879 markom 
 
1240 897 markom 
  runtime.cuc.mdelay[0] = (1. * mlsum) / mlcnt;
1241 1041 markom 
  runtime.cuc.mdelay[1] = (1. * mssum) / mscnt;
1242 897 markom 
  runtime.cuc.mdelay[2] = runtime.cuc.mdelay[3] = 1;
1243 883 markom 
  f->num_runs = f->bb[0].cnt;
1244 940 markom 
  if (!reopened) fclose (fi);
1245 879 markom 
  fclose (fo);
1246 
  free (buf);
1247 
  free (bb_end);
1248 
  free (bb_start);
1249 
 
1250 
  /* Initialize basic block relocations */
1251 
  f->num_init_bb = f->num_bb;
1252 997 markom 
  //PRINTF ("num_init_bb = %i\n", f->num_init_bb);
1253 879 markom 
  assert (f->init_bb_reloc = (int *)malloc (sizeof (int) * f->num_init_bb));
1254 
  for (b = 0; b < f->num_init_bb; b++) f->init_bb_reloc[b] = b;
1255 
}
1256 
 
1257 
/* Scans sequence of BBs and set counts for pre/unrolled loop for BB b */
1258 
void count_bb_seq (cuc_func *f, int b, char *bb_filename, int *counts, int preroll, int unroll)
1259 
{
1260 
  FILE *fi;
1261 
  const int bufsize = 256;
1262 
  int i, r;
1263 
  int *buf;
1264 
  int cnt = 0;
1265 
  int times = preroll - 1 + unroll;
1266 
 
1267 
  assert (fi = fopen (bb_filename, "rb"));
1268 
  for (i = 0; i < times; i++) counts[i] = 0;
1269 
  assert (buf = (int *) malloc (sizeof (int) * bufsize));
1270 
 
1271 
  do {
1272 
    r = fread (buf, sizeof (int), bufsize, fi);
1273 
    for (i = 0; i < r; i++) {
1274 
      /* count consecutive acesses */
1275 
      if (f->init_bb_reloc[buf[i]] == b) {
1276 
        counts[cnt]++;
1277 
        if (++cnt >= times) cnt = preroll - 1;
1278 
      } else cnt = 0;
1279 
    }
1280 
  } while (r == bufsize);
1281 
 
1282 
  log ("Counts %i,%i :", preroll, unroll);
1283 
  for (i = 0; i < times; i++) log ("%x ", counts[i]);
1284 
  log ("\n");
1285 
 
1286 
  fclose (fi);
1287 
  free (buf);
1288 
}
1289 
 
1290 
/* relocate all accesses inside of BB b to back/fwd */
1291 
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
1292 
{
1293 
  int i, j;
1294 
  for (i = 0; i < bb->ninsn; i++)
1295 
    for (j = 0; j < MAX_OPERANDS; j++)
1296 
      if (bb->insn[i].opt[j] & OPT_REF
1297 
       && REF_BB (bb->insn[i].op[j]) == b) {
1298 
        int t = REF_I (bb->insn[i].op[j]);
1299 
        if (t < i) bb->insn[i].op[j] = REF (back, t);
1300 
        else bb->insn[i].op[j] = REF (fwd, t);
1301 
      }
1302 
}
1303 
 
1304 1061 markom 
/* Preroll if type == 1 or unroll if type == 0 loop in BB b `ntimes' times and return
1305 
   new function. Original function is unmodified. */
1306 
static cuc_func *roll_loop (cuc_func *f, int b, int ntimes, int type)
1307 879 markom 
{
1308 1308 phoenix 
  int b1, t, i, prevb, prevart_b;
1309 879 markom 
  cuc_func *n = dup_func (f);
1310 
  cuc_bb *ob = &f->bb[b];
1311 
  cuc_insn *ii;
1312 
 
1313 1061 markom 
  assert (ntimes > 1);
1314 
  cucdebug (3, "roll type = %i, BB%i x %i (num_bb %i)\n", type, b, ntimes, n->num_bb);
1315 
  ntimes--;
1316 
  assert (n->num_bb + ntimes * 2 < MAX_BB);
1317 879 markom 
 
1318 
  prevb = b;
1319 
  prevart_b = b;
1320 1061 markom 
 
1321 
  /* point to first artificial block */
1322 
  if (n->bb[b].next[0] != b) {
1323 
    n->bb[b].next[0] = n->num_bb + 1;
1324 
  } else if (n->bb[b].next[1] != b) {
1325 
    n->bb[b].next[1] = n->num_bb + 1;
1326 
  }
1327 
 
1328 879 markom 
  /* Duplicate the BB */
1329 1061 markom 
  for (t = 0; t < ntimes; t++) {
1330 879 markom 
    cuc_bb *pb = &n->bb[prevart_b];
1331 
    /* Add new block and set links */
1332 
    b1 = n->num_bb++;
1333 
    cpy_bb (&n->bb[b1], ob);
1334 
    /* Only one should be in loop, so we remove any INLOOP flags from duplicates */
1335 1061 markom 
    n->bb[b1].type &= ~BB_INLOOP;
1336 
    print_cuc_bb (n, "prerollA");
1337 879 markom 
 
1338 1061 markom 
    printf ("prevb %i b1 %i prevart %i\n", prevb, b1, prevart_b);
1339 879 markom 
    /* Set predecessor's successor */
1340 
    if (n->bb[prevb].next[0] == b) {
1341 
      n->bb[prevb].next[0] = b1;
1342 
      if (pb->next[0] < 0) pb->next[0] = b1 + 1;
1343 
      else pb->next[1] = b1 + 1;
1344 
      n->bb[b1].next[1] = b1 + 1;
1345 
    } else if (n->bb[prevb].next[1] == b) {
1346 
      if (pb->next[0] < 0) pb->next[0] = b1 + 1;
1347 
      else pb->next[1] = b1 + 1;
1348 
      n->bb[b1].next[0] = b1 + 1;
1349 
      n->bb[prevb].next[1] = b1;
1350 
    } else assert (0);
1351 
 
1352 
    /* Set predecessor */
1353 
    n->bb[b1].prev[0] = prevb;
1354 
    n->bb[b1].prev[1] = -1;
1355 
 
1356 
    /* Relocate backward references to current instance and forward references
1357 
       to previous one */
1358 
    relocate_bb (&n->bb[b1], b, b1, prevb);
1359 
 
1360 
    /* add artificial block, just to join accesses */
1361 
    b1 = n->num_bb++;
1362 
    cpy_bb (&n->bb[b1], ob);
1363 
    n->bb[b1].cnt = 0;
1364 
 
1365 
    for (i = 0; i < ob->ninsn - 1; i++) {
1366 
      ii = &n->bb[b1].insn[i];
1367 
      if (ob->insn[i].opt[0] & OPT_DEST) {
1368 
        change_insn_type (ii, II_CMOV);
1369 
        ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
1370 
        ii->op[1] = REF (prevart_b, i); ii->opt[1] = OPT_REF;
1371 
        ii->op[2] = REF (b1 - 1, i); ii->opt[2] = OPT_REF;
1372 
 
1373 
        /* Take left one, if we should have finished the first iteration*/
1374 
        if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
1375 
          ii->op[3] = pb->insn[pb->ninsn - 1].op[1]; ii->opt[3] = pb->insn[pb->ninsn - 1].opt[1];
1376 
        } else {
1377 
          assert (pb->insn[pb->ninsn - 1].type & IT_COND);
1378 
          ii->op[3] = REF (prevart_b, pb->ninsn - 1); ii->opt[3] = OPT_REF;
1379 
        }
1380 
        ii->dep = NULL;
1381 930 markom 
        ii->type = ob->insn[i].type & IT_COND;
1382 879 markom 
      } else {
1383 
        change_insn_type (ii, II_NOP);
1384 
      }
1385 
    }
1386 
 
1387 928 markom 
    /* Add conditional or instruction at the end, prioritizing flags */
1388 879 markom 
    ii = &n->bb[b1].insn[ob->ninsn - 1];
1389 928 markom 
    change_insn_type (ii, II_CMOV);
1390 879 markom 
    ii->op[0] = FLAG_REG; ii->opt[0] = OPT_REGISTER | OPT_DEST;
1391 
    if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
1392 
      ii->op[1] = pb->insn[pb->ninsn - 1].op[1];
1393 
      ii->opt[1] = pb->insn[pb->ninsn - 1].opt[1];
1394 
    } else {
1395 
      ii->op[1] = REF (prevart_b, pb->ninsn - 1);
1396 
      ii->opt[1] = OPT_REF;
1397 
    }
1398 
    if (n->bb[b1 - 1].insn[pb->ninsn - 1].type & IT_BRANCH) {
1399 
      ii->op[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].op[1];
1400 
      ii->opt[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].opt[1];
1401 
    } else {
1402 
      ii->op[2] = REF (b1 - 1, pb->ninsn - 1);
1403 
      ii->opt[2] = OPT_REF;
1404 
    }
1405 928 markom 
    /* {z = x || y;} is same as {z = x ? x : y;} */
1406 
    ii->op[3] = ii->op[1]; ii->opt[3] = ii->opt[1];
1407 933 markom 
    ii->type = IT_COND;
1408 879 markom 
 
1409 
    /* Only one should be in loop, so we remove any INLOOP flags from duplicates */
1410 1061 markom 
    n->bb[b1].type &= ~BB_INLOOP;
1411 879 markom 
    n->bb[b1].prev[0] = prevart_b;
1412 
    n->bb[b1].prev[1] = b1 - 1;
1413 925 markom 
    n->bb[b1].next[0] = -1;
1414 879 markom 
    n->bb[b1].next[1] = -1;
1415 1061 markom 
 
1416 879 markom 
    prevb = b1 - 1;
1417 
    prevart_b = b1;
1418 1061 markom 
    print_cuc_bb (n, "prerollB");
1419 879 markom 
  }
1420 1061 markom 
 
1421 
  print_cuc_bb (n, "preroll0");
1422 
  n->bb[prevart_b].next[0] = ob->next[0] == b ? ob->next[1] : ob->next[0];
1423 879 markom 
 
1424 1061 markom 
  print_cuc_bb (n, "preroll1");
1425 879 markom 
  /* repair BB after loop, to point back to latest artificial BB */
1426 
  b1 = n->bb[prevart_b].next[0];
1427 925 markom 
  if (b1 >= 0 && b1 != BBID_END) {
1428 897 markom 
    if (n->bb[b1].prev[0] == b) n->bb[b1].prev[0] = prevart_b;
1429 
    else if (n->bb[b1].prev[1] == b) n->bb[b1].prev[1] = prevart_b;
1430 879 markom 
    else assert (0);
1431 
  }
1432 
 
1433 1061 markom 
  if (type) {
1434 
    /* Relink to itself */
1435 
    /* Set predecessor's successor */
1436 
    if (n->bb[prevb].next[0] == b) n->bb[prevb].next[0] = prevb;
1437 
    else if (n->bb[prevb].next[1] == b) n->bb[prevb].next[1] = prevb;
1438 
    else assert (0);
1439 
    n->bb[prevb].prev[1] = prevb;
1440 879 markom 
 
1441 1061 markom 
    /* Set predecessor */
1442 
    if (n->bb[b].prev[0] == b) {
1443 
      n->bb[b].prev[0] = n->bb[b].prev[1];
1444 
      n->bb[b].prev[1] = -1;
1445 
    } else if (n->bb[b].prev[1] == b) n->bb[b].prev[1] = -1;
1446 
    else assert (0);
1447 
  } else {
1448 
    /* Relink back to start of the loop */
1449 879 markom 
    /* Set predecessor's successor */
1450 1061 markom 
    if (n->bb[prevb].next[0] == b) n->bb[prevb].next[0] = b;
1451 
    else if (n->bb[prevb].next[1] == b) n->bb[prevb].next[1] = b;
1452 
    else assert (0);
1453 879 markom 
 
1454 
    /* Set predecessor */
1455 1061 markom 
    if (n->bb[b].prev[0] == b) n->bb[b].prev[0] = prevb;
1456 
    else if (n->bb[b].prev[1] == b) n->bb[b].prev[1] = prevb;
1457 879 markom 
    else assert (0);
1458 
  }
1459 
 
1460 1061 markom 
  print_cuc_bb (n, "preroll2");
1461 879 markom 
 
1462 
  /* Relocate backward references to current instance and forward references
1463 
     to previous one */
1464 
  relocate_bb (&n->bb[b], b, b, prevb);
1465 
 
1466 
  /* Relocate all other blocks to point to latest prevart_b */
1467 
  for (i = 0; i < f->num_bb; i++)
1468 
    if (i != b) relocate_bb (&n->bb[i], b, prevart_b, prevart_b);
1469 
 
1470 
  return n;
1471 
}
1472 
 
1473 
/* Unroll loop b unroll times and return new function. Original
1474 
   function is unmodified. */
1475 
cuc_func *preunroll_loop (cuc_func *f, int b, int preroll, int unroll, char *bb_filename)
1476 
{
1477 
  int b1, i;
1478 
  cuc_func *n, *t;
1479 
  int *counts;
1480 
 
1481 
  if (preroll > 1) {
1482 1061 markom 
    t = roll_loop (f, b, preroll, 1);
1483 879 markom 
    b1 = t->num_bb - 2;
1484 
    if (unroll > 1) {
1485 
      //print_cuc_bb (t, "preunroll1");
1486 1061 markom 
      n = roll_loop (t, b1, unroll, 0);
1487 879 markom 
      free_func (t);
1488 
    } else n = t;
1489 
  } else {
1490 
    b1 = b;
1491 1061 markom 
    if (unroll > 1) n = roll_loop (f, b1, unroll, 0);
1492 897 markom 
    else return dup_func (f);
1493 879 markom 
  }
1494 
 
1495 897 markom 
  /* Assign new counts to functions */
1496 879 markom 
  assert (counts = (int *)malloc (sizeof (int) * (preroll - 1 + unroll)));
1497 
  count_bb_seq (n, b, bb_filename, counts, preroll, unroll);
1498 
  for (i = 0; i < preroll - 1 + unroll; i++) {
1499 
    if (i == 0) b1 = b;
1500 
    else b1 = f->num_bb + (i - 1) * 2;
1501 
    n->bb[b1].cnt = counts[i];
1502 
  }
1503 
 
1504 
  //print_cuc_bb (n, "preunroll");
1505 
  free (counts);
1506 
  return n;
1507 
}
1508 933 markom 
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.