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, 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 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   int u;
 696
 697   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
 698   scc->backarcs = NULL;
 699   scc->num_backarcs = 0;
 700   scc->nodes = sbitmap_alloc (g->num_nodes);
 701   sbitmap_copy (scc->nodes, nodes);
 702
 703   /* Mark the backarcs that belong to this SCC.  */
 704   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
 705     {
 706       ddg_edge_ptr e;
 707       ddg_node_ptr n = &g->nodes[u];
 708
 709       for (e = n->out; e; e = e->next_out)
 710         if (TEST_BIT (nodes, e->dest->cuid))
 711           {
 712             e->aux.count = IN_SCC;
 713             if (e->distance > 0)
 714               add_backarc_to_scc (scc, e);
 715           }
 716     });
 717
 718   set_recurrence_length (scc, g);
 719   return scc;
 720 }
 721
 722 /* Cleans the memory allocation of a given SCC.  */
 723 static void
 724 free_scc (ddg_scc_ptr scc)
 725 {
 726   if (!scc)
 727     return;
 728
 729   sbitmap_free (scc->nodes);
 730   if (scc->num_backarcs > 0)
 731     free (scc->backarcs);
 732   free (scc);
 733 }
 734
 735
 736 /* Add a given edge known to be a backarc to the given DDG.  */
 737 static void
 738 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
 739 {
 740   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 741
 742   add_edge_to_ddg (g, e);
 743   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
 744   g->backarcs[g->num_backarcs++] = e;
 745 }
 746
 747 /* Add backarc to an SCC.  */
 748 static void
 749 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
 750 {
 751   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 752
 753   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
 754   scc->backarcs[scc->num_backarcs++] = e;
 755 }
 756
 757 /* Add the given SCC to the DDG.  */
 758 static void
 759 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
 760 {
 761   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
 762
 763   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
 764   g->sccs[g->num_sccs++] = scc;
 765 }
 766
 767 /* Given the instruction INSN return the node that represents it.  */
 768 ddg_node_ptr
 769 get_node_of_insn (ddg_ptr g, rtx insn)
 770 {
 771   int i;
 772
 773   for (i = 0; i < g->num_nodes; i++)
 774     if (insn == g->nodes[i].insn)
 775       return &g->nodes[i];
 776   return NULL;
 777 }
 778
 779 /* Given a set OPS of nodes in the DDG, find the set of their successors
 780    which are not in OPS, and set their bits in SUCC.  Bits corresponding to
 781    OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
 782 void
 783 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
 784 {
 785   int i;
 786
 787   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 788     {
 789       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
 790       sbitmap_a_or_b (succ, succ, node_succ);
 791     });
 792
 793   /* We want those that are not in ops.  */
 794   sbitmap_difference (succ, succ, ops);
 795 }
 796
 797 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
 798    which are not in OPS, and set their bits in PREDS.  Bits corresponding to
 799    OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
 800 void
 801 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
 802 {
 803   int i;
 804
 805   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 806     {
 807       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
 808       sbitmap_a_or_b (preds, preds, node_preds);
 809     });
 810
 811   /* We want those that are not in ops.  */
 812   sbitmap_difference (preds, preds, ops);
 813 }
 814
 815
 816 /* Compare function to be passed to qsort to order the backarcs in descending
 817    recMII order.  */
 818 static int
 819 compare_sccs (const void *s1, const void *s2)
 820 {
 821   int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length;
 822   int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length;
 823   return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
 824
 825 }
 826
 827 /* Order the backarcs in descending recMII order using compare_sccs.  */
 828 static void
 829 order_sccs (ddg_all_sccs_ptr g)
 830 {
 831   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
 832          (int (*) (const void *, const void *)) compare_sccs);
 833 }
 834
 835 /* Perform the Strongly Connected Components decomposing algorithm on the
 836    DDG and return DDG_ALL_SCCS structure that contains them.  */
 837 ddg_all_sccs_ptr
 838 create_ddg_all_sccs (ddg_ptr g)
 839 {
 840   int i;
 841   int num_nodes = g->num_nodes;
 842   sbitmap from = sbitmap_alloc (num_nodes);
 843   sbitmap to = sbitmap_alloc (num_nodes);
 844   sbitmap scc_nodes = sbitmap_alloc (num_nodes);
 845   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
 846                           xmalloc (sizeof (struct ddg_all_sccs));
 847
 848   sccs->ddg = g;
 849   sccs->sccs = NULL;
 850   sccs->num_sccs = 0;
 851
 852   for (i = 0; i < g->num_backarcs; i++)
 853     {
 854       ddg_scc_ptr  scc;
 855       ddg_edge_ptr backarc = g->backarcs[i];
 856       ddg_node_ptr src = backarc->src;
 857       ddg_node_ptr dest = backarc->dest;
 858
 859       /* If the backarc already belongs to an SCC, continue.  */
 860       if (backarc->aux.count == IN_SCC)
 861         continue;
 862
 863       sbitmap_zero (from);
 864       sbitmap_zero (to);
 865       SET_BIT (from, dest->cuid);
 866       SET_BIT (to, src->cuid);
 867
 868       if (find_nodes_on_paths (scc_nodes, g, from, to))
 869         {
 870           scc = create_scc (g, scc_nodes);
 871           add_scc_to_ddg (sccs, scc);
 872         }
 873     }
 874   order_sccs (sccs);
 875   sbitmap_free (from);
 876   sbitmap_free (to);
 877   sbitmap_free (scc_nodes);
 878   return sccs;
 879 }
 880
 881 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
 882 void
 883 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
 884 {
 885   int i;
 886
 887   if (!all_sccs)
 888     return;
 889
 890   for (i = 0; i < all_sccs->num_sccs; i++)
 891     free_scc (all_sccs->sccs[i]);
 892
 893   free (all_sccs);
 894 }
 895
 896 \f
 897 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
 898    nodes - find all nodes that lie on paths from FROM to TO (not excluding
 899    nodes from FROM and TO).  Return nonzero if nodes exist.  */
 900 int
 901 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
 902 {
 903   int answer;
 904   int change, u;
 905   int num_nodes = g->num_nodes;
 906   sbitmap workset = sbitmap_alloc (num_nodes);
 907   sbitmap reachable_from = sbitmap_alloc (num_nodes);
 908   sbitmap reach_to = sbitmap_alloc (num_nodes);
 909   sbitmap tmp = sbitmap_alloc (num_nodes);
 910
 911   sbitmap_copy (reachable_from, from);
 912   sbitmap_copy (tmp, from);
 913
 914   change = 1;
 915   while (change)
 916     {
 917       change = 0;
 918       sbitmap_copy (workset, tmp);
 919       sbitmap_zero (tmp);
 920       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 921         {
 922           ddg_edge_ptr e;
 923           ddg_node_ptr u_node = &g->nodes[u];
 924
 925           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
 926             {
 927               ddg_node_ptr v_node = e->dest;
 928               int v = v_node->cuid;
 929
 930               if (!TEST_BIT (reachable_from, v))
 931                 {
 932                   SET_BIT (reachable_from, v);
 933                   SET_BIT (tmp, v);
 934                   change = 1;
 935                 }
 936             }
 937         });
 938     }
 939
 940   sbitmap_copy (reach_to, to);
 941   sbitmap_copy (tmp, to);
 942
 943   change = 1;
 944   while (change)
 945     {
 946       change = 0;
 947       sbitmap_copy (workset, tmp);
 948       sbitmap_zero (tmp);
 949       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 950         {
 951           ddg_edge_ptr e;
 952           ddg_node_ptr u_node = &g->nodes[u];
 953
 954           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
 955             {
 956               ddg_node_ptr v_node = e->src;
 957               int v = v_node->cuid;
 958
 959               if (!TEST_BIT (reach_to, v))
 960                 {
 961                   SET_BIT (reach_to, v);
 962                   SET_BIT (tmp, v);
 963                   change = 1;
 964                 }
 965             }
 966         });
 967     }
 968
 969   answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
 970   sbitmap_free (workset);
 971   sbitmap_free (reachable_from);
 972   sbitmap_free (reach_to);
 973   sbitmap_free (tmp);
 974   return answer;
 975 }
 976
 977
 978 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
 979    at-least as large as the count of U_NODE plus the latency between them.
 980    Sets a bit in TMP for each successor whose count was changed (increased).
 981    Returns nonzero if any count was changed.  */
 982 static int
 983 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
 984 {
 985   ddg_edge_ptr e;
 986   int result = 0;
 987
 988   for (e = u_node->out; e; e = e->next_out)
 989     {
 990       ddg_node_ptr v_node = e->dest;
 991       int v = v_node->cuid;
 992
 993       if (TEST_BIT (nodes, v)
 994           && (e->distance == 0)
 995           && (v_node->aux.count < u_node->aux.count + e->latency))
 996         {
 997           v_node->aux.count = u_node->aux.count + e->latency;
 998           SET_BIT (tmp, v);
 999           result = 1;
1000         }
1001     }
1002   return result;
1003 }
1004
1005
1006 /* Find the length of a longest path from SRC to DEST in G,
1007    going only through NODES, and disregarding backarcs.  */
1008 int
1009 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1010 {
1011   int i, u;
1012   int change = 1;
1013   int result;
1014   int num_nodes = g->num_nodes;
1015   sbitmap workset = sbitmap_alloc (num_nodes);
1016   sbitmap tmp = sbitmap_alloc (num_nodes);
1017
1018
1019   /* Data will hold the distance of the longest path found so far from
1020      src to each node.  Initialize to -1 = less than minimum.  */
1021   for (i = 0; i < g->num_nodes; i++)
1022     g->nodes[i].aux.count = -1;
1023   g->nodes[src].aux.count = 0;
1024
1025   sbitmap_zero (tmp);
1026   SET_BIT (tmp, src);
1027
1028   while (change)
1029     {
1030       change = 0;
1031       sbitmap_copy (workset, tmp);
1032       sbitmap_zero (tmp);
1033       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
1034         {
1035           ddg_node_ptr u_node = &g->nodes[u];
1036
1037           change |= update_dist_to_successors (u_node, nodes, tmp);
1038         });
1039     }
1040   result = g->nodes[dest].aux.count;
1041   sbitmap_free (workset);
1042   sbitmap_free (tmp);
1043   return result;
1044 }