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_rd_bb_info *bb_info = DF_RD_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     case OUTPUT_DEP :
 554       dep_c = 'O';
 555       break;
 556     case ANTI_DEP :
 557       dep_c = 'A';
 558       break;
 559     default:
 560       dep_c = 'T';
 561   }
 562
 563   fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
 564            dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
 565 }
 566
 567 /* Print the DDG nodes with there in/out edges to the dump file.  */
 568 void
 569 print_ddg (FILE *file, ddg_ptr g)
 570 {
 571   int i;
 572
 573   for (i = 0; i < g->num_nodes; i++)
 574     {
 575       ddg_edge_ptr e;
 576
 577       print_rtl_single (file, g->nodes[i].insn);
 578       fprintf (file, "OUT ARCS: ");
 579       for (e = g->nodes[i].out; e; e = e->next_out)
 580         print_ddg_edge (file, e);
 581
 582       fprintf (file, "\nIN ARCS: ");
 583       for (e = g->nodes[i].in; e; e = e->next_in)
 584         print_ddg_edge (file, e);
 585
 586       fprintf (file, "\n");
 587     }
 588 }
 589
 590 /* Print the given DDG in VCG format.  */
 591 void
 592 vcg_print_ddg (FILE *file, ddg_ptr g)
 593 {
 594   int src_cuid;
 595
 596   fprintf (file, "graph: {\n");
 597   for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
 598     {
 599       ddg_edge_ptr e;
 600       int src_uid = INSN_UID (g->nodes[src_cuid].insn);
 601
 602       fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
 603       print_rtl_single (file, g->nodes[src_cuid].insn);
 604       fprintf (file, "\"}\n");
 605       for (e = g->nodes[src_cuid].out; e; e = e->next_out)
 606         {
 607           int dst_uid = INSN_UID (e->dest->insn);
 608           int dst_cuid = e->dest->cuid;
 609
 610           /* Give the backarcs a different color.  */
 611           if (e->distance > 0)
 612             fprintf (file, "backedge: {color: red ");
 613           else
 614             fprintf (file, "edge: { ");
 615
 616           fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
 617           fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
 618           fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
 619         }
 620     }
 621   fprintf (file, "}\n");
 622 }
 623
 624 /* Create an edge and initialize it with given values.  */
 625 static ddg_edge_ptr
 626 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
 627                  dep_type t, dep_data_type dt, int l, int d)
 628 {
 629   ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
 630
 631   e->src = src;
 632   e->dest = dest;
 633   e->type = t;
 634   e->data_type = dt;
 635   e->latency = l;
 636   e->distance = d;
 637   e->next_in = e->next_out = NULL;
 638   e->aux.info = 0;
 639   return e;
 640 }
 641
 642 /* Add the given edge to the in/out linked lists of the DDG nodes.  */
 643 static void
 644 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
 645 {
 646   ddg_node_ptr src = e->src;
 647   ddg_node_ptr dest = e->dest;
 648
 649   /* Should have allocated the sbitmaps.  */
 650   gcc_assert (src->successors && dest->predecessors);
 651
 652   SET_BIT (src->successors, dest->cuid);
 653   SET_BIT (dest->predecessors, src->cuid);
 654   e->next_in = dest->in;
 655   dest->in = e;
 656   e->next_out = src->out;
 657   src->out = e;
 658 }
 659
 660
 661 \f
 662 /* Algorithm for computing the recurrence_length of an scc.  We assume at
 663    for now that cycles in the data dependence graph contain a single backarc.
 664    This simplifies the algorithm, and can be generalized later.  */
 665 static void
 666 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
 667 {
 668   int j;
 669   int result = -1;
 670
 671   for (j = 0; j < scc->num_backarcs; j++)
 672     {
 673       ddg_edge_ptr backarc = scc->backarcs[j];
 674       int length;
 675       int distance = backarc->distance;
 676       ddg_node_ptr src = backarc->dest;
 677       ddg_node_ptr dest = backarc->src;
 678
 679       length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
 680       if (length < 0 )
 681         {
 682           /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
 683           continue;
 684         }
 685       length += backarc->latency;
 686       result = MAX (result, (length / distance));
 687     }
 688   scc->recurrence_length = result;
 689 }
 690
 691 /* Create a new SCC given the set of its nodes.  Compute its recurrence_length
 692    and mark edges that belong to this scc as IN_SCC.  */
 693 static ddg_scc_ptr
 694 create_scc (ddg_ptr g, sbitmap nodes)
 695 {
 696   ddg_scc_ptr scc;
 697   unsigned int u = 0;
 698   sbitmap_iterator sbi;
 699
 700   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
 701   scc->backarcs = NULL;
 702   scc->num_backarcs = 0;
 703   scc->nodes = sbitmap_alloc (g->num_nodes);
 704   sbitmap_copy (scc->nodes, nodes);
 705
 706   /* Mark the backarcs that belong to this SCC.  */
 707   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
 708     {
 709       ddg_edge_ptr e;
 710       ddg_node_ptr n = &g->nodes[u];
 711
 712       for (e = n->out; e; e = e->next_out)
 713         if (TEST_BIT (nodes, e->dest->cuid))
 714           {
 715             e->aux.count = IN_SCC;
 716             if (e->distance > 0)
 717               add_backarc_to_scc (scc, e);
 718           }
 719     }
 720
 721   set_recurrence_length (scc, g);
 722   return scc;
 723 }
 724
 725 /* Cleans the memory allocation of a given SCC.  */
 726 static void
 727 free_scc (ddg_scc_ptr scc)
 728 {
 729   if (!scc)
 730     return;
 731
 732   sbitmap_free (scc->nodes);
 733   if (scc->num_backarcs > 0)
 734     free (scc->backarcs);
 735   free (scc);
 736 }
 737
 738
 739 /* Add a given edge known to be a backarc to the given DDG.  */
 740 static void
 741 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
 742 {
 743   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 744
 745   add_edge_to_ddg (g, e);
 746   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
 747   g->backarcs[g->num_backarcs++] = e;
 748 }
 749
 750 /* Add backarc to an SCC.  */
 751 static void
 752 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
 753 {
 754   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 755
 756   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
 757   scc->backarcs[scc->num_backarcs++] = e;
 758 }
 759
 760 /* Add the given SCC to the DDG.  */
 761 static void
 762 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
 763 {
 764   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
 765
 766   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
 767   g->sccs[g->num_sccs++] = scc;
 768 }
 769
 770 /* Given the instruction INSN return the node that represents it.  */
 771 ddg_node_ptr
 772 get_node_of_insn (ddg_ptr g, rtx insn)
 773 {
 774   int i;
 775
 776   for (i = 0; i < g->num_nodes; i++)
 777     if (insn == g->nodes[i].insn)
 778       return &g->nodes[i];
 779   return NULL;
 780 }
 781
 782 /* Given a set OPS of nodes in the DDG, find the set of their successors
 783    which are not in OPS, and set their bits in SUCC.  Bits corresponding to
 784    OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
 785 void
 786 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
 787 {
 788   unsigned int i = 0;
 789   sbitmap_iterator sbi;
 790
 791   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
 792     {
 793       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
 794       sbitmap_a_or_b (succ, succ, node_succ);
 795     };
 796
 797   /* We want those that are not in ops.  */
 798   sbitmap_difference (succ, succ, ops);
 799 }
 800
 801 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
 802    which are not in OPS, and set their bits in PREDS.  Bits corresponding to
 803    OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
 804 void
 805 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
 806 {
 807   unsigned int i = 0;
 808   sbitmap_iterator sbi;
 809
 810   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
 811     {
 812       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
 813       sbitmap_a_or_b (preds, preds, node_preds);
 814     };
 815
 816   /* We want those that are not in ops.  */
 817   sbitmap_difference (preds, preds, ops);
 818 }
 819
 820
 821 /* Compare function to be passed to qsort to order the backarcs in descending
 822    recMII order.  */
 823 static int
 824 compare_sccs (const void *s1, const void *s2)
 825 {
 826   int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length;
 827   int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length;
 828   return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
 829
 830 }
 831
 832 /* Order the backarcs in descending recMII order using compare_sccs.  */
 833 static void
 834 order_sccs (ddg_all_sccs_ptr g)
 835 {
 836   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
 837          (int (*) (const void *, const void *)) compare_sccs);
 838 }
 839
 840 /* Perform the Strongly Connected Components decomposing algorithm on the
 841    DDG and return DDG_ALL_SCCS structure that contains them.  */
 842 ddg_all_sccs_ptr
 843 create_ddg_all_sccs (ddg_ptr g)
 844 {
 845   int i;
 846   int num_nodes = g->num_nodes;
 847   sbitmap from = sbitmap_alloc (num_nodes);
 848   sbitmap to = sbitmap_alloc (num_nodes);
 849   sbitmap scc_nodes = sbitmap_alloc (num_nodes);
 850   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
 851                           xmalloc (sizeof (struct ddg_all_sccs));
 852
 853   sccs->ddg = g;
 854   sccs->sccs = NULL;
 855   sccs->num_sccs = 0;
 856
 857   for (i = 0; i < g->num_backarcs; i++)
 858     {
 859       ddg_scc_ptr  scc;
 860       ddg_edge_ptr backarc = g->backarcs[i];
 861       ddg_node_ptr src = backarc->src;
 862       ddg_node_ptr dest = backarc->dest;
 863
 864       /* If the backarc already belongs to an SCC, continue.  */
 865       if (backarc->aux.count == IN_SCC)
 866         continue;
 867
 868       sbitmap_zero (from);
 869       sbitmap_zero (to);
 870       SET_BIT (from, dest->cuid);
 871       SET_BIT (to, src->cuid);
 872
 873       if (find_nodes_on_paths (scc_nodes, g, from, to))
 874         {
 875           scc = create_scc (g, scc_nodes);
 876           add_scc_to_ddg (sccs, scc);
 877         }
 878     }
 879   order_sccs (sccs);
 880   sbitmap_free (from);
 881   sbitmap_free (to);
 882   sbitmap_free (scc_nodes);
 883   return sccs;
 884 }
 885
 886 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
 887 void
 888 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
 889 {
 890   int i;
 891
 892   if (!all_sccs)
 893     return;
 894
 895   for (i = 0; i < all_sccs->num_sccs; i++)
 896     free_scc (all_sccs->sccs[i]);
 897
 898   free (all_sccs);
 899 }
 900
 901 \f
 902 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
 903    nodes - find all nodes that lie on paths from FROM to TO (not excluding
 904    nodes from FROM and TO).  Return nonzero if nodes exist.  */
 905 int
 906 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
 907 {
 908   int answer;
 909   int change;
 910   unsigned int u = 0;
 911   int num_nodes = g->num_nodes;
 912   sbitmap_iterator sbi;
 913
 914   sbitmap workset = sbitmap_alloc (num_nodes);
 915   sbitmap reachable_from = sbitmap_alloc (num_nodes);
 916   sbitmap reach_to = sbitmap_alloc (num_nodes);
 917   sbitmap tmp = sbitmap_alloc (num_nodes);
 918
 919   sbitmap_copy (reachable_from, from);
 920   sbitmap_copy (tmp, from);
 921
 922   change = 1;
 923   while (change)
 924     {
 925       change = 0;
 926       sbitmap_copy (workset, tmp);
 927       sbitmap_zero (tmp);
 928       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
 929         {
 930           ddg_edge_ptr e;
 931           ddg_node_ptr u_node = &g->nodes[u];
 932
 933           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
 934             {
 935               ddg_node_ptr v_node = e->dest;
 936               int v = v_node->cuid;
 937
 938               if (!TEST_BIT (reachable_from, v))
 939                 {
 940                   SET_BIT (reachable_from, v);
 941                   SET_BIT (tmp, v);
 942                   change = 1;
 943                 }
 944             }
 945         }
 946     }
 947
 948   sbitmap_copy (reach_to, to);
 949   sbitmap_copy (tmp, to);
 950
 951   change = 1;
 952   while (change)
 953     {
 954       change = 0;
 955       sbitmap_copy (workset, tmp);
 956       sbitmap_zero (tmp);
 957       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
 958         {
 959           ddg_edge_ptr e;
 960           ddg_node_ptr u_node = &g->nodes[u];
 961
 962           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
 963             {
 964               ddg_node_ptr v_node = e->src;
 965               int v = v_node->cuid;
 966
 967               if (!TEST_BIT (reach_to, v))
 968                 {
 969                   SET_BIT (reach_to, v);
 970                   SET_BIT (tmp, v);
 971                   change = 1;
 972                 }
 973             }
 974         }
 975     }
 976
 977   answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
 978   sbitmap_free (workset);
 979   sbitmap_free (reachable_from);
 980   sbitmap_free (reach_to);
 981   sbitmap_free (tmp);
 982   return answer;
 983 }
 984
 985
 986 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
 987    at-least as large as the count of U_NODE plus the latency between them.
 988    Sets a bit in TMP for each successor whose count was changed (increased).
 989    Returns nonzero if any count was changed.  */
 990 static int
 991 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
 992 {
 993   ddg_edge_ptr e;
 994   int result = 0;
 995
 996   for (e = u_node->out; e; e = e->next_out)
 997     {
 998       ddg_node_ptr v_node = e->dest;
 999       int v = v_node->cuid;
1000
1001       if (TEST_BIT (nodes, v)
1002           && (e->distance == 0)
1003           && (v_node->aux.count < u_node->aux.count + e->latency))
1004         {
1005           v_node->aux.count = u_node->aux.count + e->latency;
1006           SET_BIT (tmp, v);
1007           result = 1;
1008         }
1009     }
1010   return result;
1011 }
1012
1013
1014 /* Find the length of a longest path from SRC to DEST in G,
1015    going only through NODES, and disregarding backarcs.  */
1016 int
1017 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1018 {
1019   int i;
1020   unsigned int u = 0;
1021   int change = 1;
1022   int result;
1023   int num_nodes = g->num_nodes;
1024   sbitmap workset = sbitmap_alloc (num_nodes);
1025   sbitmap tmp = sbitmap_alloc (num_nodes);
1026
1027
1028   /* Data will hold the distance of the longest path found so far from
1029      src to each node.  Initialize to -1 = less than minimum.  */
1030   for (i = 0; i < g->num_nodes; i++)
1031     g->nodes[i].aux.count = -1;
1032   g->nodes[src].aux.count = 0;
1033
1034   sbitmap_zero (tmp);
1035   SET_BIT (tmp, src);
1036
1037   while (change)
1038     {
1039       sbitmap_iterator sbi;
1040
1041       change = 0;
1042       sbitmap_copy (workset, tmp);
1043       sbitmap_zero (tmp);
1044       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1045         {
1046           ddg_node_ptr u_node = &g->nodes[u];
1047
1048           change |= update_dist_to_successors (u_node, nodes, tmp);
1049         }
1050     }
1051   result = g->nodes[dest].aux.count;
1052   sbitmap_free (workset);
1053   sbitmap_free (tmp);
1054   return result;
1055 }