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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_47/] [or1ksim/] [cuc/] [bb.c] - Blame information for rev 883

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

powered by: WebSVN 2.1.0

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