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

Subversion Repositories or1k

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

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

powered by: WebSVN 2.1.0

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