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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [ddg.c] - Blame information for rev 831

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

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

powered by: WebSVN 2.1.0

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