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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_50/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 928

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

powered by: WebSVN 2.1.0

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