gcc/ddg.c

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