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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_69/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 1041

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

powered by: WebSVN 2.1.0

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