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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_52/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 941

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

powered by: WebSVN 2.1.0

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