gcc/ddg.c

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