gcc/ddg.c

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