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 1308

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

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

powered by: WebSVN 2.1.0

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