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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [ddg.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* DDG - Data Dependence Graph implementation.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3
   Free Software Foundation, Inc.
4
   Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
 
23
#include "config.h"
24
#include "system.h"
25
#include "coretypes.h"
26
#include "tm.h"
27
#include "toplev.h"
28
#include "rtl.h"
29
#include "tm_p.h"
30
#include "hard-reg-set.h"
31
#include "regs.h"
32
#include "function.h"
33
#include "flags.h"
34
#include "insn-config.h"
35
#include "insn-attr.h"
36
#include "except.h"
37
#include "recog.h"
38
#include "sched-int.h"
39
#include "target.h"
40
#include "cfglayout.h"
41
#include "cfgloop.h"
42
#include "sbitmap.h"
43
#include "expr.h"
44
#include "bitmap.h"
45
#include "ddg.h"
46
 
47
#ifdef INSN_SCHEDULING
48
 
49
/* A flag indicating that a ddg edge belongs to an SCC or not.  */
50
enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
51
 
52
/* Forward declarations.  */
53
static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
54
static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
55
static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
56
static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
57
                                                 ddg_node_ptr, dep_t);
58
static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
59
                                    dep_type, dep_data_type, int);
60
static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
61
                                     dep_data_type, int, int);
62
static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
63
 
64
/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p.  */
65
static bool mem_ref_p;
66
 
67
/* Auxiliary function for mem_read_insn_p.  */
68
static int
69
mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
70
{
71
  if (MEM_P (*x))
72
    mem_ref_p = true;
73
  return 0;
74
}
75
 
76
/* Auxiliary function for mem_read_insn_p.  */
77
static void
78
mark_mem_use_1 (rtx *x, void *data)
79
{
80
  for_each_rtx (x, mark_mem_use, data);
81
}
82
 
83
/* Returns nonzero if INSN reads from memory.  */
84
static bool
85
mem_read_insn_p (rtx insn)
86
{
87
  mem_ref_p = false;
88
  note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
89
  return mem_ref_p;
90
}
91
 
92
static void
93
mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
94
{
95
  if (MEM_P (loc))
96
    mem_ref_p = true;
97
}
98
 
99
/* Returns nonzero if INSN writes to memory.  */
100
static bool
101
mem_write_insn_p (rtx insn)
102
{
103
  mem_ref_p = false;
104
  note_stores (PATTERN (insn), mark_mem_store, NULL);
105
  return mem_ref_p;
106
}
107
 
108
/* Returns nonzero if X has access to memory.  */
109
static bool
110
rtx_mem_access_p (rtx x)
111
{
112
  int i, j;
113
  const char *fmt;
114
  enum rtx_code code;
115
 
116
  if (x == 0)
117
    return false;
118
 
119
  if (MEM_P (x))
120
    return true;
121
 
122
  code = GET_CODE (x);
123
  fmt = GET_RTX_FORMAT (code);
124
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
125
    {
126
      if (fmt[i] == 'e')
127
        {
128
          if (rtx_mem_access_p (XEXP (x, i)))
129
            return true;
130
        }
131
      else if (fmt[i] == 'E')
132
        for (j = 0; j < XVECLEN (x, i); j++)
133
          {
134
            if (rtx_mem_access_p (XVECEXP (x, i, j)))
135
              return true;
136
          }
137
    }
138
  return false;
139
}
140
 
141
/* Returns nonzero if INSN reads to or writes from memory.  */
142
static bool
143
mem_access_insn_p (rtx insn)
144
{
145
  return rtx_mem_access_p (PATTERN (insn));
146
}
147
 
148
/* Computes the dependence parameters (latency, distance etc.), creates
149
   a ddg_edge and adds it to the given DDG.  */
150
static void
151
create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
152
                                     ddg_node_ptr dest_node, dep_t link)
153
{
154
  ddg_edge_ptr e;
155
  int latency, distance = 0;
156
  dep_type t = TRUE_DEP;
157
  dep_data_type dt = (mem_access_insn_p (src_node->insn)
158
                      && mem_access_insn_p (dest_node->insn) ? MEM_DEP
159
                                                             : REG_DEP);
160
  gcc_assert (src_node->cuid < dest_node->cuid);
161
  gcc_assert (link);
162
 
163
  /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!!  */
164
  if (DEP_TYPE (link) == REG_DEP_ANTI)
165
    t = ANTI_DEP;
166
  else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
167
    t = OUTPUT_DEP;
168
 
169
  gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
170
  gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
171
 
172
  /* We currently choose not to create certain anti-deps edges and
173
     compensate for that by generating reg-moves based on the life-range
174
     analysis.  The anti-deps that will be deleted are the ones which
175
     have true-deps edges in the opposite direction (in other words
176
     the kernel has only one def of the relevant register).  TODO:
177
     support the removal of all anti-deps edges, i.e. including those
178
     whose register has multiple defs in the loop.  */
179
  if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
180
    {
181
      rtx set;
182
 
183
      set = single_set (dest_node->insn);
184
      /* TODO: Handle registers that REG_P is not true for them, i.e.
185
         subregs and special registers.  */
186
      if (set && REG_P (SET_DEST (set)))
187
        {
188
          int regno = REGNO (SET_DEST (set));
189
          df_ref first_def;
190
          struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
191
 
192
          first_def = df_bb_regno_first_def_find (g->bb, regno);
193
          gcc_assert (first_def);
194
 
195
          if (bitmap_bit_p (bb_info->gen, DF_REF_ID (first_def)))
196
            return;
197
        }
198
    }
199
 
200
   latency = dep_cost (link);
201
   e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
202
   add_edge_to_ddg (g, e);
203
}
204
 
205
/* The same as the above function, but it doesn't require a link parameter.  */
206
static void
207
create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
208
                        dep_type d_t, dep_data_type d_dt, int distance)
209
{
210
  ddg_edge_ptr e;
211
  int l;
212
  enum reg_note dep_kind;
213
  struct _dep _dep, *dep = &_dep;
214
 
215
  gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
216
  gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
217
 
218
  if (d_t == ANTI_DEP)
219
    dep_kind = REG_DEP_ANTI;
220
  else if (d_t == OUTPUT_DEP)
221
    dep_kind = REG_DEP_OUTPUT;
222
  else
223
    {
224
      gcc_assert (d_t == TRUE_DEP);
225
 
226
      dep_kind = REG_DEP_TRUE;
227
    }
228
 
229
  init_dep (dep, from->insn, to->insn, dep_kind);
230
 
231
  l = dep_cost (dep);
232
 
233
  e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
234
  if (distance > 0)
235
    add_backarc_to_ddg (g, e);
236
  else
237
    add_edge_to_ddg (g, e);
238
}
239
 
240
 
241
/* Given a downwards exposed register def LAST_DEF (which is the last
242
   definition of that register in the bb), add inter-loop true dependences
243
   to all its uses in the next iteration, an output dependence to the
244
   first def of the same register (possibly itself) in the next iteration
245
   and anti-dependences from its uses in the current iteration to the
246
   first definition in the next iteration.  */
247
static void
248
add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
249
{
250
  int regno = DF_REF_REGNO (last_def);
251
  struct df_link *r_use;
252
  int has_use_in_bb_p = false;
253
  rtx def_insn = DF_REF_INSN (last_def);
254
  ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
255
  ddg_node_ptr use_node;
256
#ifdef ENABLE_CHECKING
257
  struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
258
#endif
259
  df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
260
 
261
  gcc_assert (last_def_node);
262
  gcc_assert (first_def);
263
 
264
#ifdef ENABLE_CHECKING
265
  if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
266
    gcc_assert (!bitmap_bit_p (bb_info->gen, DF_REF_ID (first_def)));
267
#endif
268
 
269
  /* Create inter-loop true dependences and anti dependences.  */
270
  for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
271
    {
272
      rtx use_insn = DF_REF_INSN (r_use->ref);
273
 
274
      if (BLOCK_FOR_INSN (use_insn) != g->bb)
275
        continue;
276
 
277
      /* ??? Do not handle uses with DF_REF_IN_NOTE notes.  */
278
      use_node = get_node_of_insn (g, use_insn);
279
      gcc_assert (use_node);
280
      has_use_in_bb_p = true;
281
      if (use_node->cuid <= last_def_node->cuid)
282
        {
283
          /* Add true deps from last_def to it's uses in the next
284
             iteration.  Any such upwards exposed use appears before
285
             the last_def def.  */
286
          create_ddg_dep_no_link (g, last_def_node, use_node,
287
                                  DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
288
                                  REG_DEP, 1);
289
        }
290
      else if (!DEBUG_INSN_P (use_insn))
291
        {
292
          /* Add anti deps from last_def's uses in the current iteration
293
             to the first def in the next iteration.  We do not add ANTI
294
             dep when there is an intra-loop TRUE dep in the opposite
295
             direction, but use regmoves to fix such disregarded ANTI
296
             deps when broken.  If the first_def reaches the USE then
297
             there is such a dep.  */
298
          ddg_node_ptr first_def_node = get_node_of_insn (g,
299
                                                          DF_REF_INSN (first_def));
300
 
301
          gcc_assert (first_def_node);
302
 
303
          if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
304
              || !flag_modulo_sched_allow_regmoves)
305
            create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
306
                                    REG_DEP, 1);
307
 
308
        }
309
    }
310
  /* Create an inter-loop output dependence between LAST_DEF (which is the
311
     last def in its block, being downwards exposed) and the first def in
312
     its block.  Avoid creating a self output dependence.  Avoid creating
313
     an output dependence if there is a dependence path between the two
314
     defs starting with a true dependence to a use which can be in the
315
     next iteration; followed by an anti dependence of that use to the
316
     first def (i.e. if there is a use between the two defs.)  */
317
  if (!has_use_in_bb_p)
318
    {
319
      ddg_node_ptr dest_node;
320
 
321
      if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
322
        return;
323
 
324
      dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
325
      gcc_assert (dest_node);
326
      create_ddg_dep_no_link (g, last_def_node, dest_node,
327
                              OUTPUT_DEP, REG_DEP, 1);
328
    }
329
}
330
/* Build inter-loop dependencies, by looking at DF analysis backwards.  */
331
static void
332
build_inter_loop_deps (ddg_ptr g)
333
{
334
  unsigned rd_num;
335
  struct df_rd_bb_info *rd_bb_info;
336
  bitmap_iterator bi;
337
 
338
  rd_bb_info = DF_RD_BB_INFO (g->bb);
339
 
340
  /* Find inter-loop register output, true and anti deps.  */
341
  EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
342
  {
343
    df_ref rd = DF_DEFS_GET (rd_num);
344
 
345
    add_cross_iteration_register_deps (g, rd);
346
  }
347
}
348
 
349
 
350
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
351
   to ddg G.  */
352
static void
353
add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
354
{
355
  if (!insn_alias_sets_conflict_p (from->insn, to->insn))
356
    /* Do not create edge if memory references have disjoint alias sets.  */
357
    return;
358
 
359
  if (mem_write_insn_p (from->insn))
360
    {
361
      if (mem_read_insn_p (to->insn))
362
        create_ddg_dep_no_link (g, from, to,
363
                                DEBUG_INSN_P (to->insn)
364
                                ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
365
      else if (from->cuid != to->cuid)
366
        create_ddg_dep_no_link (g, from, to,
367
                                DEBUG_INSN_P (to->insn)
368
                                ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
369
    }
370
  else
371
    {
372
      if (mem_read_insn_p (to->insn))
373
        return;
374
      else if (from->cuid != to->cuid)
375
        {
376
          create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
377
          if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
378
            create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
379
          else
380
            create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
381
        }
382
    }
383
 
384
}
385
 
386
/* Perform intra-block Data Dependency analysis and connect the nodes in
387
   the DDG.  We assume the loop has a single basic block.  */
388
static void
389
build_intra_loop_deps (ddg_ptr g)
390
{
391
  int i;
392
  /* Hold the dependency analysis state during dependency calculations.  */
393
  struct deps_desc tmp_deps;
394
  rtx head, tail;
395
 
396
  /* Build the dependence information, using the sched_analyze function.  */
397
  init_deps_global ();
398
  init_deps (&tmp_deps, false);
399
 
400
  /* Do the intra-block data dependence analysis for the given block.  */
401
  get_ebb_head_tail (g->bb, g->bb, &head, &tail);
402
  sched_analyze (&tmp_deps, head, tail);
403
 
404
  /* Build intra-loop data dependencies using the scheduler dependency
405
     analysis.  */
406
  for (i = 0; i < g->num_nodes; i++)
407
    {
408
      ddg_node_ptr dest_node = &g->nodes[i];
409
      sd_iterator_def sd_it;
410
      dep_t dep;
411
 
412
      if (! INSN_P (dest_node->insn))
413
        continue;
414
 
415
      FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
416
        {
417
          ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
418
 
419
          if (!src_node)
420
            continue;
421
 
422
          create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
423
        }
424
 
425
      /* If this insn modifies memory, add an edge to all insns that access
426
         memory.  */
427
      if (mem_access_insn_p (dest_node->insn))
428
        {
429
          int j;
430
 
431
          for (j = 0; j <= i; j++)
432
            {
433
              ddg_node_ptr j_node = &g->nodes[j];
434
              if (DEBUG_INSN_P (j_node->insn))
435
                continue;
436
              if (mem_access_insn_p (j_node->insn))
437
                /* Don't bother calculating inter-loop dep if an intra-loop dep
438
                   already exists.  */
439
                  if (! TEST_BIT (dest_node->successors, j))
440
                    add_inter_loop_mem_dep (g, dest_node, j_node);
441
            }
442
        }
443
    }
444
 
445
  /* Free the INSN_LISTs.  */
446
  finish_deps_global ();
447
  free_deps (&tmp_deps);
448
 
449
  /* Free dependencies.  */
450
  sched_free_deps (head, tail, false);
451
}
452
 
453
 
454
/* Given a basic block, create its DDG and return a pointer to a variable
455
   of ddg type that represents it.
456
   Initialize the ddg structure fields to the appropriate values.  */
457
ddg_ptr
458
create_ddg (basic_block bb, int closing_branch_deps)
459
{
460
  ddg_ptr g;
461
  rtx insn, first_note;
462
  int i;
463
  int num_nodes = 0;
464
 
465
  g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
466
 
467
  g->bb = bb;
468
  g->closing_branch_deps = closing_branch_deps;
469
 
470
  /* Count the number of insns in the BB.  */
471
  for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
472
       insn = NEXT_INSN (insn))
473
    {
474
      if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
475
        continue;
476
 
477
      if (DEBUG_INSN_P (insn))
478
        g->num_debug++;
479
      else
480
        {
481
          if (mem_read_insn_p (insn))
482
            g->num_loads++;
483
          if (mem_write_insn_p (insn))
484
            g->num_stores++;
485
        }
486
      num_nodes++;
487
    }
488
 
489
  /* There is nothing to do for this BB.  */
490
  if ((num_nodes - g->num_debug) <= 1)
491
    {
492
      free (g);
493
      return NULL;
494
    }
495
 
496
  /* Allocate the nodes array, and initialize the nodes.  */
497
  g->num_nodes = num_nodes;
498
  g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
499
  g->closing_branch = NULL;
500
  i = 0;
501
  first_note = NULL_RTX;
502
  for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
503
       insn = NEXT_INSN (insn))
504
    {
505
      if (! INSN_P (insn))
506
        {
507
          if (! first_note && NOTE_P (insn)
508
              && NOTE_KIND (insn) !=  NOTE_INSN_BASIC_BLOCK)
509
            first_note = insn;
510
          continue;
511
        }
512
      if (JUMP_P (insn))
513
        {
514
          gcc_assert (!g->closing_branch);
515
          g->closing_branch = &g->nodes[i];
516
        }
517
      else if (GET_CODE (PATTERN (insn)) == USE)
518
        {
519
          if (! first_note)
520
            first_note = insn;
521
          continue;
522
        }
523
 
524
      g->nodes[i].cuid = i;
525
      g->nodes[i].successors = sbitmap_alloc (num_nodes);
526
      sbitmap_zero (g->nodes[i].successors);
527
      g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
528
      sbitmap_zero (g->nodes[i].predecessors);
529
      g->nodes[i].first_note = (first_note ? first_note : insn);
530
      g->nodes[i++].insn = insn;
531
      first_note = NULL_RTX;
532
    }
533
 
534
  /* We must have found a branch in DDG.  */
535
  gcc_assert (g->closing_branch);
536
 
537
 
538
  /* Build the data dependency graph.  */
539
  build_intra_loop_deps (g);
540
  build_inter_loop_deps (g);
541
  return g;
542
}
543
 
544
/* Free all the memory allocated for the DDG.  */
545
void
546
free_ddg (ddg_ptr g)
547
{
548
  int i;
549
 
550
  if (!g)
551
    return;
552
 
553
  for (i = 0; i < g->num_nodes; i++)
554
    {
555
      ddg_edge_ptr e = g->nodes[i].out;
556
 
557
      while (e)
558
        {
559
          ddg_edge_ptr next = e->next_out;
560
 
561
          free (e);
562
          e = next;
563
        }
564
      sbitmap_free (g->nodes[i].successors);
565
      sbitmap_free (g->nodes[i].predecessors);
566
    }
567
  if (g->num_backarcs > 0)
568
    free (g->backarcs);
569
  free (g->nodes);
570
  free (g);
571
}
572
 
573
void
574
print_ddg_edge (FILE *file, ddg_edge_ptr e)
575
{
576
  char dep_c;
577
 
578
  switch (e->type)
579
    {
580
    case OUTPUT_DEP :
581
      dep_c = 'O';
582
      break;
583
    case ANTI_DEP :
584
      dep_c = 'A';
585
      break;
586
    default:
587
      dep_c = 'T';
588
    }
589
 
590
  fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
591
           dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
592
}
593
 
594
/* Print the DDG nodes with there in/out edges to the dump file.  */
595
void
596
print_ddg (FILE *file, ddg_ptr g)
597
{
598
  int i;
599
 
600
  for (i = 0; i < g->num_nodes; i++)
601
    {
602
      ddg_edge_ptr e;
603
 
604
      fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
605
      print_rtl_single (file, g->nodes[i].insn);
606
      fprintf (file, "OUT ARCS: ");
607
      for (e = g->nodes[i].out; e; e = e->next_out)
608
        print_ddg_edge (file, e);
609
 
610
      fprintf (file, "\nIN ARCS: ");
611
      for (e = g->nodes[i].in; e; e = e->next_in)
612
        print_ddg_edge (file, e);
613
 
614
      fprintf (file, "\n");
615
    }
616
}
617
 
618
/* Print the given DDG in VCG format.  */
619
void
620
vcg_print_ddg (FILE *file, ddg_ptr g)
621
{
622
  int src_cuid;
623
 
624
  fprintf (file, "graph: {\n");
625
  for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
626
    {
627
      ddg_edge_ptr e;
628
      int src_uid = INSN_UID (g->nodes[src_cuid].insn);
629
 
630
      fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
631
      print_rtl_single (file, g->nodes[src_cuid].insn);
632
      fprintf (file, "\"}\n");
633
      for (e = g->nodes[src_cuid].out; e; e = e->next_out)
634
        {
635
          int dst_uid = INSN_UID (e->dest->insn);
636
          int dst_cuid = e->dest->cuid;
637
 
638
          /* Give the backarcs a different color.  */
639
          if (e->distance > 0)
640
            fprintf (file, "backedge: {color: red ");
641
          else
642
            fprintf (file, "edge: { ");
643
 
644
          fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
645
          fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
646
          fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
647
        }
648
    }
649
  fprintf (file, "}\n");
650
}
651
 
652
/* Dump the sccs in SCCS.  */
653
void
654
print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
655
{
656
  unsigned int u = 0;
657
  sbitmap_iterator sbi;
658
  int i;
659
 
660
  if (!file)
661
    return;
662
 
663
  fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
664
  for (i = 0; i < sccs->num_sccs; i++)
665
    {
666
      fprintf (file, "SCC number: %d\n", i);
667
      EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
668
      {
669
        fprintf (file, "insn num %d\n", u);
670
        print_rtl_single (file, g->nodes[u].insn);
671
      }
672
    }
673
  fprintf (file, "\n");
674
}
675
 
676
/* Create an edge and initialize it with given values.  */
677
static ddg_edge_ptr
678
create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
679
                 dep_type t, dep_data_type dt, int l, int d)
680
{
681
  ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
682
 
683
  e->src = src;
684
  e->dest = dest;
685
  e->type = t;
686
  e->data_type = dt;
687
  e->latency = l;
688
  e->distance = d;
689
  e->next_in = e->next_out = NULL;
690
  e->aux.info = 0;
691
  return e;
692
}
693
 
694
/* Add the given edge to the in/out linked lists of the DDG nodes.  */
695
static void
696
add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
697
{
698
  ddg_node_ptr src = e->src;
699
  ddg_node_ptr dest = e->dest;
700
 
701
  /* Should have allocated the sbitmaps.  */
702
  gcc_assert (src->successors && dest->predecessors);
703
 
704
  SET_BIT (src->successors, dest->cuid);
705
  SET_BIT (dest->predecessors, src->cuid);
706
  e->next_in = dest->in;
707
  dest->in = e;
708
  e->next_out = src->out;
709
  src->out = e;
710
}
711
 
712
 
713
 
714
/* Algorithm for computing the recurrence_length of an scc.  We assume at
715
   for now that cycles in the data dependence graph contain a single backarc.
716
   This simplifies the algorithm, and can be generalized later.  */
717
static void
718
set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
719
{
720
  int j;
721
  int result = -1;
722
 
723
  for (j = 0; j < scc->num_backarcs; j++)
724
    {
725
      ddg_edge_ptr backarc = scc->backarcs[j];
726
      int length;
727
      int distance = backarc->distance;
728
      ddg_node_ptr src = backarc->dest;
729
      ddg_node_ptr dest = backarc->src;
730
 
731
      length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
732
      if (length < 0 )
733
        {
734
          /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
735
          continue;
736
        }
737
      length += backarc->latency;
738
      result = MAX (result, (length / distance));
739
    }
740
  scc->recurrence_length = result;
741
}
742
 
743
/* Create a new SCC given the set of its nodes.  Compute its recurrence_length
744
   and mark edges that belong to this scc as IN_SCC.  */
745
static ddg_scc_ptr
746
create_scc (ddg_ptr g, sbitmap nodes)
747
{
748
  ddg_scc_ptr scc;
749
  unsigned int u = 0;
750
  sbitmap_iterator sbi;
751
 
752
  scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
753
  scc->backarcs = NULL;
754
  scc->num_backarcs = 0;
755
  scc->nodes = sbitmap_alloc (g->num_nodes);
756
  sbitmap_copy (scc->nodes, nodes);
757
 
758
  /* Mark the backarcs that belong to this SCC.  */
759
  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
760
    {
761
      ddg_edge_ptr e;
762
      ddg_node_ptr n = &g->nodes[u];
763
 
764
      for (e = n->out; e; e = e->next_out)
765
        if (TEST_BIT (nodes, e->dest->cuid))
766
          {
767
            e->aux.count = IN_SCC;
768
            if (e->distance > 0)
769
              add_backarc_to_scc (scc, e);
770
          }
771
    }
772
 
773
  set_recurrence_length (scc, g);
774
  return scc;
775
}
776
 
777
/* Cleans the memory allocation of a given SCC.  */
778
static void
779
free_scc (ddg_scc_ptr scc)
780
{
781
  if (!scc)
782
    return;
783
 
784
  sbitmap_free (scc->nodes);
785
  if (scc->num_backarcs > 0)
786
    free (scc->backarcs);
787
  free (scc);
788
}
789
 
790
 
791
/* Add a given edge known to be a backarc to the given DDG.  */
792
static void
793
add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
794
{
795
  int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
796
 
797
  add_edge_to_ddg (g, e);
798
  g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
799
  g->backarcs[g->num_backarcs++] = e;
800
}
801
 
802
/* Add backarc to an SCC.  */
803
static void
804
add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
805
{
806
  int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
807
 
808
  scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
809
  scc->backarcs[scc->num_backarcs++] = e;
810
}
811
 
812
/* Add the given SCC to the DDG.  */
813
static void
814
add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
815
{
816
  int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
817
 
818
  g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
819
  g->sccs[g->num_sccs++] = scc;
820
}
821
 
822
/* Given the instruction INSN return the node that represents it.  */
823
ddg_node_ptr
824
get_node_of_insn (ddg_ptr g, rtx insn)
825
{
826
  int i;
827
 
828
  for (i = 0; i < g->num_nodes; i++)
829
    if (insn == g->nodes[i].insn)
830
      return &g->nodes[i];
831
  return NULL;
832
}
833
 
834
/* Given a set OPS of nodes in the DDG, find the set of their successors
835
   which are not in OPS, and set their bits in SUCC.  Bits corresponding to
836
   OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
837
void
838
find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
839
{
840
  unsigned int i = 0;
841
  sbitmap_iterator sbi;
842
 
843
  EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
844
    {
845
      const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
846
      sbitmap_a_or_b (succ, succ, node_succ);
847
    };
848
 
849
  /* We want those that are not in ops.  */
850
  sbitmap_difference (succ, succ, ops);
851
}
852
 
853
/* Given a set OPS of nodes in the DDG, find the set of their predecessors
854
   which are not in OPS, and set their bits in PREDS.  Bits corresponding to
855
   OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
856
void
857
find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
858
{
859
  unsigned int i = 0;
860
  sbitmap_iterator sbi;
861
 
862
  EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
863
    {
864
      const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
865
      sbitmap_a_or_b (preds, preds, node_preds);
866
    };
867
 
868
  /* We want those that are not in ops.  */
869
  sbitmap_difference (preds, preds, ops);
870
}
871
 
872
 
873
/* Compare function to be passed to qsort to order the backarcs in descending
874
   recMII order.  */
875
static int
876
compare_sccs (const void *s1, const void *s2)
877
{
878
  const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
879
  const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
880
  return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
881
 
882
}
883
 
884
/* Order the backarcs in descending recMII order using compare_sccs.  */
885
static void
886
order_sccs (ddg_all_sccs_ptr g)
887
{
888
  qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
889
         (int (*) (const void *, const void *)) compare_sccs);
890
}
891
 
892
#ifdef ENABLE_CHECKING
893
/* Check that every node in SCCS belongs to exactly one strongly connected
894
   component and that no element of SCCS is empty.  */
895
static void
896
check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
897
{
898
  int i = 0;
899
  sbitmap tmp = sbitmap_alloc (num_nodes);
900
 
901
  sbitmap_zero (tmp);
902
  for (i = 0; i < sccs->num_sccs; i++)
903
    {
904
      gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
905
      /* Verify that every node in sccs is in exactly one strongly
906
         connected component.  */
907
      gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
908
      sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
909
    }
910
  sbitmap_free (tmp);
911
}
912
#endif
913
 
914
/* Perform the Strongly Connected Components decomposing algorithm on the
915
   DDG and return DDG_ALL_SCCS structure that contains them.  */
916
ddg_all_sccs_ptr
917
create_ddg_all_sccs (ddg_ptr g)
918
{
919
  int i;
920
  int num_nodes = g->num_nodes;
921
  sbitmap from = sbitmap_alloc (num_nodes);
922
  sbitmap to = sbitmap_alloc (num_nodes);
923
  sbitmap scc_nodes = sbitmap_alloc (num_nodes);
924
  ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
925
                          xmalloc (sizeof (struct ddg_all_sccs));
926
 
927
  sccs->ddg = g;
928
  sccs->sccs = NULL;
929
  sccs->num_sccs = 0;
930
 
931
  for (i = 0; i < g->num_backarcs; i++)
932
    {
933
      ddg_scc_ptr  scc;
934
      ddg_edge_ptr backarc = g->backarcs[i];
935
      ddg_node_ptr src = backarc->src;
936
      ddg_node_ptr dest = backarc->dest;
937
 
938
      /* If the backarc already belongs to an SCC, continue.  */
939
      if (backarc->aux.count == IN_SCC)
940
        continue;
941
 
942
      sbitmap_zero (scc_nodes);
943
      sbitmap_zero (from);
944
      sbitmap_zero (to);
945
      SET_BIT (from, dest->cuid);
946
      SET_BIT (to, src->cuid);
947
 
948
      if (find_nodes_on_paths (scc_nodes, g, from, to))
949
        {
950
          scc = create_scc (g, scc_nodes);
951
          add_scc_to_ddg (sccs, scc);
952
        }
953
    }
954
  order_sccs (sccs);
955
  sbitmap_free (from);
956
  sbitmap_free (to);
957
  sbitmap_free (scc_nodes);
958
#ifdef ENABLE_CHECKING
959
  check_sccs (sccs, num_nodes);
960
#endif
961
  return sccs;
962
}
963
 
964
/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
965
void
966
free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
967
{
968
  int i;
969
 
970
  if (!all_sccs)
971
    return;
972
 
973
  for (i = 0; i < all_sccs->num_sccs; i++)
974
    free_scc (all_sccs->sccs[i]);
975
 
976
  free (all_sccs);
977
}
978
 
979
 
980
/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
981
   nodes - find all nodes that lie on paths from FROM to TO (not excluding
982
   nodes from FROM and TO).  Return nonzero if nodes exist.  */
983
int
984
find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
985
{
986
  int answer;
987
  int change;
988
  unsigned int u = 0;
989
  int num_nodes = g->num_nodes;
990
  sbitmap_iterator sbi;
991
 
992
  sbitmap workset = sbitmap_alloc (num_nodes);
993
  sbitmap reachable_from = sbitmap_alloc (num_nodes);
994
  sbitmap reach_to = sbitmap_alloc (num_nodes);
995
  sbitmap tmp = sbitmap_alloc (num_nodes);
996
 
997
  sbitmap_copy (reachable_from, from);
998
  sbitmap_copy (tmp, from);
999
 
1000
  change = 1;
1001
  while (change)
1002
    {
1003
      change = 0;
1004
      sbitmap_copy (workset, tmp);
1005
      sbitmap_zero (tmp);
1006
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1007
        {
1008
          ddg_edge_ptr e;
1009
          ddg_node_ptr u_node = &g->nodes[u];
1010
 
1011
          for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
1012
            {
1013
              ddg_node_ptr v_node = e->dest;
1014
              int v = v_node->cuid;
1015
 
1016
              if (!TEST_BIT (reachable_from, v))
1017
                {
1018
                  SET_BIT (reachable_from, v);
1019
                  SET_BIT (tmp, v);
1020
                  change = 1;
1021
                }
1022
            }
1023
        }
1024
    }
1025
 
1026
  sbitmap_copy (reach_to, to);
1027
  sbitmap_copy (tmp, to);
1028
 
1029
  change = 1;
1030
  while (change)
1031
    {
1032
      change = 0;
1033
      sbitmap_copy (workset, tmp);
1034
      sbitmap_zero (tmp);
1035
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1036
        {
1037
          ddg_edge_ptr e;
1038
          ddg_node_ptr u_node = &g->nodes[u];
1039
 
1040
          for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1041
            {
1042
              ddg_node_ptr v_node = e->src;
1043
              int v = v_node->cuid;
1044
 
1045
              if (!TEST_BIT (reach_to, v))
1046
                {
1047
                  SET_BIT (reach_to, v);
1048
                  SET_BIT (tmp, v);
1049
                  change = 1;
1050
                }
1051
            }
1052
        }
1053
    }
1054
 
1055
  answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1056
  sbitmap_free (workset);
1057
  sbitmap_free (reachable_from);
1058
  sbitmap_free (reach_to);
1059
  sbitmap_free (tmp);
1060
  return answer;
1061
}
1062
 
1063
 
1064
/* Updates the counts of U_NODE's successors (that belong to NODES) to be
1065
   at-least as large as the count of U_NODE plus the latency between them.
1066
   Sets a bit in TMP for each successor whose count was changed (increased).
1067
   Returns nonzero if any count was changed.  */
1068
static int
1069
update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1070
{
1071
  ddg_edge_ptr e;
1072
  int result = 0;
1073
 
1074
  for (e = u_node->out; e; e = e->next_out)
1075
    {
1076
      ddg_node_ptr v_node = e->dest;
1077
      int v = v_node->cuid;
1078
 
1079
      if (TEST_BIT (nodes, v)
1080
          && (e->distance == 0)
1081
          && (v_node->aux.count < u_node->aux.count + e->latency))
1082
        {
1083
          v_node->aux.count = u_node->aux.count + e->latency;
1084
          SET_BIT (tmp, v);
1085
          result = 1;
1086
        }
1087
    }
1088
  return result;
1089
}
1090
 
1091
 
1092
/* Find the length of a longest path from SRC to DEST in G,
1093
   going only through NODES, and disregarding backarcs.  */
1094
int
1095
longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1096
{
1097
  int i;
1098
  unsigned int u = 0;
1099
  int change = 1;
1100
  int result;
1101
  int num_nodes = g->num_nodes;
1102
  sbitmap workset = sbitmap_alloc (num_nodes);
1103
  sbitmap tmp = sbitmap_alloc (num_nodes);
1104
 
1105
 
1106
  /* Data will hold the distance of the longest path found so far from
1107
     src to each node.  Initialize to -1 = less than minimum.  */
1108
  for (i = 0; i < g->num_nodes; i++)
1109
    g->nodes[i].aux.count = -1;
1110
  g->nodes[src].aux.count = 0;
1111
 
1112
  sbitmap_zero (tmp);
1113
  SET_BIT (tmp, src);
1114
 
1115
  while (change)
1116
    {
1117
      sbitmap_iterator sbi;
1118
 
1119
      change = 0;
1120
      sbitmap_copy (workset, tmp);
1121
      sbitmap_zero (tmp);
1122
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1123
        {
1124
          ddg_node_ptr u_node = &g->nodes[u];
1125
 
1126
          change |= update_dist_to_successors (u_node, nodes, tmp);
1127
        }
1128
    }
1129
  result = g->nodes[dest].aux.count;
1130
  sbitmap_free (workset);
1131
  sbitmap_free (tmp);
1132
  return result;
1133
}
1134
 
1135
#endif /* INSN_SCHEDULING */

powered by: WebSVN 2.1.0

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