OpenCores
URL https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk

Subversion Repositories openrisc_2011-10-31

[/] [openrisc/] [trunk/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 166

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

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

powered by: WebSVN 2.1.0

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