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