gcc/ddg.c

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