gcc/ddg.c

   1 /* DDG - Data Dependence Graph implementation.
   2    Copyright (C) 2004
   3    Free Software Foundation, Inc.
   4    Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "tm.h"
  28 #include "toplev.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "regs.h"
  34 #include "function.h"
  35 #include "flags.h"
  36 #include "insn-config.h"
  37 #include "insn-attr.h"
  38 #include "except.h"
  39 #include "recog.h"
  40 #include "sched-int.h"
  41 #include "target.h"
  42 #include "cfglayout.h"
  43 #include "cfgloop.h"
  44 #include "sbitmap.h"
  45 #include "expr.h"
  46 #include "bitmap.h"
  47 #include "df.h"
  48 #include "ddg.h"
  49
  50 /* A flag indicating that a ddg edge belongs to an SCC or not.  */
  51 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
  52
  53 /* Forward declarations.  */
  54 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
  55 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
  56 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
  57 static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx);
  58 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
  59                                     dep_type, dep_data_type, int);
  60 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
  61                                      dep_data_type, int, int);
  62 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
  63 \f
  64 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p.  */
  65 static bool mem_ref_p;
  66
  67 /* Auxiliary function for mem_read_insn_p.  */
  68 static int
  69 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
  70 {
  71   if (MEM_P (*x))
  72     mem_ref_p = true;
  73   return 0;
  74 }
  75
  76 /* Auxiliary function for mem_read_insn_p.  */
  77 static void
  78 mark_mem_use_1 (rtx *x, void *data)
  79 {
  80   for_each_rtx (x, mark_mem_use, data);
  81 }
  82
  83 /* Returns nonzero if INSN reads from memory.  */
  84 static bool
  85 mem_read_insn_p (rtx insn)
  86 {
  87   mem_ref_p = false;
  88   note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
  89   return mem_ref_p;
  90 }
  91
  92 static void
  93 mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
  94 {
  95   if (MEM_P (loc))
  96     mem_ref_p = true;
  97 }
  98
  99 /* Returns nonzero if INSN writes to memory.  */
 100 static bool
 101 mem_write_insn_p (rtx insn)
 102 {
 103   mem_ref_p = false;
 104   note_stores (PATTERN (insn), mark_mem_store, NULL);
 105   return mem_ref_p;
 106 }
 107
 108 /* Returns nonzero if X has access to memory.  */
 109 static bool
 110 rtx_mem_access_p (rtx x)
 111 {
 112   int i, j;
 113   const char *fmt;
 114   enum rtx_code code;
 115
 116   if (x == 0)
 117     return false;
 118
 119   if (MEM_P (x))
 120     return true;
 121
 122   code = GET_CODE (x);
 123   fmt = GET_RTX_FORMAT (code);
 124   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 125     {
 126       if (fmt[i] == 'e')
 127         {
 128           if (rtx_mem_access_p (XEXP (x, i)))
 129             return true;
 130         }
 131       else if (fmt[i] == 'E')
 132         for (j = 0; j < XVECLEN (x, i); j++)
 133           {
 134             if (rtx_mem_access_p (XVECEXP (x, i, j)))
 135               return true;
 136           }
 137     }
 138   return false;
 139 }
 140
 141 /* Returns nonzero if INSN reads to or writes from memory.  */
 142 static bool
 143 mem_access_insn_p (rtx insn)
 144 {
 145   return rtx_mem_access_p (PATTERN (insn));
 146 }
 147
 148 /* Computes the dependence parameters (latency, distance etc.), creates
 149    a ddg_edge and adds it to the given DDG.  */
 150 static void
 151 create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node,
 152                        ddg_node_ptr dest_node, rtx link)
 153 {
 154   ddg_edge_ptr e;
 155   int latency, distance = 0;
 156   int interloop = (src_node->cuid >= dest_node->cuid);
 157   dep_type t = TRUE_DEP;
 158   dep_data_type dt = (mem_access_insn_p (src_node->insn)
 159                       && mem_access_insn_p (dest_node->insn) ? MEM_DEP
 160                                                              : REG_DEP);
 161
 162   /* For now we don't have an exact calculation of the distance,
 163      so assume 1 conservatively.  */
 164   if (interloop)
 165      distance = 1;
 166
 167   gcc_assert (link);
 168
 169   /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!!  */
 170   if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 171     t = ANTI_DEP;
 172   else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 173     t = OUTPUT_DEP;
 174   latency = insn_cost (src_node->insn, link, dest_node->insn);
 175
 176   e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
 177
 178   if (interloop)
 179     {
 180       /* Some interloop dependencies are relaxed:
 181          1. Every insn is output dependent on itself; ignore such deps.
 182          2. Every true/flow dependence is an anti dependence in the
 183          opposite direction with distance 1; such register deps
 184          will be removed by renaming if broken --- ignore them.  */
 185       if (!(t == OUTPUT_DEP && src_node == dest_node)
 186           && !(t == ANTI_DEP && dt == REG_DEP))
 187         add_backarc_to_ddg (g, e);
 188       else
 189         free (e);
 190     }
 191   else
 192     add_edge_to_ddg (g, e);
 193 }
 194
 195 /* The same as the above function, but it doesn't require a link parameter.  */
 196 static void
 197 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
 198                         dep_type d_t, dep_data_type d_dt, int distance)
 199 {
 200   ddg_edge_ptr e;
 201   int l;
 202   rtx link = alloc_INSN_LIST (to->insn, NULL_RTX);
 203
 204   if (d_t == ANTI_DEP)
 205     PUT_REG_NOTE_KIND (link, REG_DEP_ANTI);
 206   else if (d_t == OUTPUT_DEP)
 207     PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT);
 208
 209   l = insn_cost (from->insn, link, to->insn);
 210   free_INSN_LIST_node (link);
 211
 212   e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
 213   if (distance > 0)
 214     add_backarc_to_ddg (g, e);
 215   else
 216     add_edge_to_ddg (g, e);
 217 }
 218
 219 \f
 220 /* Given a downwards exposed register def RD, add inter-loop true dependences
 221    for all its uses in the next iteration, and an output dependence to the
 222    first def of the next iteration.  */
 223 static void
 224 add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd)
 225 {
 226   int regno = DF_REF_REGNO (rd);
 227   struct bb_info *bb_info = DF_BB_INFO (df, g->bb);
 228   struct df_link *r_use;
 229   int use_before_def = false;
 230   rtx def_insn = DF_REF_INSN (rd);
 231   ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
 232
 233   /* Create and inter-loop true dependence between RD and each of its uses
 234      that is upwards exposed in RD's block.  */
 235   for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
 236     {
 237       if (bitmap_bit_p (bb_info->ru_gen, r_use->ref->id))
 238         {
 239           rtx use_insn = DF_REF_INSN (r_use->ref);
 240           ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
 241
 242           gcc_assert (src_node && dest_node);
 243
 244           /* Any such upwards exposed use appears before the rd def.  */
 245           use_before_def = true;
 246           create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
 247                                   REG_DEP, 1);
 248         }
 249     }
 250
 251   /* Create an inter-loop output dependence between RD (which is the
 252      last def in its block, being downwards exposed) and the first def
 253      in its block.  Avoid creating a self output dependence.  Avoid creating
 254      an output dependence if there is a dependence path between the two defs
 255      starting with a true dependence followed by an anti dependence (i.e. if
 256      there is a use between the two defs.  */
 257   if (! use_before_def)
 258     {
 259       struct ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
 260       int i;
 261       ddg_node_ptr dest_node;
 262
 263       if (!def || rd->id == def->id)
 264         return;
 265
 266       /* Check if there are uses after RD.  */
 267       for (i = src_node->cuid + 1; i < g->num_nodes; i++)
 268          if (df_reg_used (df, g->nodes[i].insn, rd->reg))
 269            return;
 270
 271       dest_node = get_node_of_insn (g, def->insn);
 272       create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
 273     }
 274 }
 275
 276 /* Given a register USE, add an inter-loop anti dependence to the first
 277    (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
 278    by a def in the block.  */
 279 static void
 280 add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use)
 281 {
 282   int i;
 283   int regno = DF_REF_REGNO (use);
 284   struct ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno);
 285   ddg_node_ptr use_node;
 286   ddg_node_ptr def_node;
 287   struct bb_info *bb_info;
 288
 289   bb_info = DF_BB_INFO (df, g->bb);
 290
 291   if (!first_def)
 292     return;
 293
 294   use_node = get_node_of_insn (g, use->insn);
 295   def_node = get_node_of_insn (g, first_def->insn);
 296
 297   gcc_assert (use_node && def_node);
 298
 299   /* Make sure there are no defs after USE.  */
 300   for (i = use_node->cuid + 1; i < g->num_nodes; i++)
 301      if (df_find_def (df, g->nodes[i].insn, use->reg))
 302        return;
 303   /* We must not add ANTI dep when there is an intra-loop TRUE dep in
 304      the opozite direction. If the first_def reaches the USE then there is
 305      such a dep.  */
 306   if (! bitmap_bit_p (bb_info->rd_gen, first_def->id))
 307     create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
 308 }
 309
 310 /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
 311 static void
 312 build_inter_loop_deps (ddg_ptr g, struct df *df)
 313 {
 314   unsigned rd_num, u_num;
 315   struct bb_info *bb_info;
 316   bitmap_iterator bi;
 317
 318   bb_info = DF_BB_INFO (df, g->bb);
 319
 320   /* Find inter-loop output and true deps by connecting downward exposed defs
 321      to the first def of the BB and to upwards exposed uses.  */
 322   EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num, bi)
 323     {
 324       struct ref *rd = df->defs[rd_num];
 325
 326       add_deps_for_def (g, df, rd);
 327     }
 328
 329   /* Find inter-loop anti deps.  We are interested in uses of the block that
 330      appear below all defs; this implies that these uses are killed.  */
 331   EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num, bi)
 332     {
 333       struct ref *use = df->uses[u_num];
 334
 335       /* We are interested in uses of this BB.  */
 336       if (BLOCK_FOR_INSN (use->insn) == g->bb)
 337         add_deps_for_use (g, df,use);
 338     }
 339 }
 340
 341 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
 342    to ddg G.  */
 343 static void
 344 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
 345 {
 346   if (mem_write_insn_p (from->insn))
 347     {
 348       if (mem_read_insn_p (to->insn))
 349         create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
 350       else if (from->cuid != to->cuid)
 351         create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
 352     }
 353   else
 354     {
 355       if (mem_read_insn_p (to->insn))
 356         return;
 357       else if (from->cuid != to->cuid)
 358         {
 359           create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
 360           create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
 361         }
 362     }
 363
 364 }
 365
 366 /* Perform intra-block Data Dependency analysis and connect the nodes in
 367    the DDG.  We assume the loop has a single basic block.  */
 368 static void
 369 build_intra_loop_deps (ddg_ptr g)
 370 {
 371   int i;
 372   /* Hold the dependency analysis state during dependency calculations.  */
 373   struct deps tmp_deps;
 374   rtx head, tail, link;
 375
 376   /* Build the dependence information, using the sched_analyze function.  */
 377   init_deps_global ();
 378   init_deps (&tmp_deps);
 379
 380   /* Do the intra-block data dependence analysis for the given block.  */
 381   get_block_head_tail (g->bb->index, &head, &tail);
 382   sched_analyze (&tmp_deps, head, tail);
 383
 384   /* Build intra-loop data dependencies using the scheduler dependency
 385      analysis.  */
 386   for (i = 0; i < g->num_nodes; i++)
 387     {
 388       ddg_node_ptr dest_node = &g->nodes[i];
 389
 390       if (! INSN_P (dest_node->insn))
 391         continue;
 392
 393       for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1))
 394         {
 395           ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0));
 396
 397           if (!src_node)
 398             continue;
 399
 400           add_forward_dependence (XEXP (link, 0), dest_node->insn,
 401                                   REG_NOTE_KIND (link));
 402           create_ddg_dependence (g, src_node, dest_node,
 403                                  INSN_DEPEND (src_node->insn));
 404         }
 405
 406       /* If this insn modifies memory, add an edge to all insns that access
 407          memory.  */
 408       if (mem_access_insn_p (dest_node->insn))
 409         {
 410           int j;
 411
 412           for (j = 0; j <= i; j++)
 413             {
 414               ddg_node_ptr j_node = &g->nodes[j];
 415               if (mem_access_insn_p (j_node->insn))
 416                 /* Don't bother calculating inter-loop dep if an intra-loop dep
 417                    already exists.  */
 418                   if (! TEST_BIT (dest_node->successors, j))
 419                     add_inter_loop_mem_dep (g, dest_node, j_node);
 420             }
 421         }
 422     }
 423
 424   /* Free the INSN_LISTs.  */
 425   finish_deps_global ();
 426   free_deps (&tmp_deps);
 427 }
 428
 429
 430 /* Given a basic block, create its DDG and return a pointer to a variable
 431    of ddg type that represents it.
 432    Initialize the ddg structure fields to the appropriate values.  */
 433 ddg_ptr
 434 create_ddg (basic_block bb, struct df *df, int closing_branch_deps)
 435 {
 436   ddg_ptr g;
 437   rtx insn, first_note;
 438   int i;
 439   int num_nodes = 0;
 440
 441   g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
 442
 443   g->bb = bb;
 444   g->closing_branch_deps = closing_branch_deps;
 445
 446   /* Count the number of insns in the BB.  */
 447   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
 448        insn = NEXT_INSN (insn))
 449     {
 450       if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
 451         continue;
 452
 453       if (mem_read_insn_p (insn))
 454         g->num_loads++;
 455       if (mem_write_insn_p (insn))
 456         g->num_stores++;
 457       num_nodes++;
 458     }
 459
 460   /* There is nothing to do for this BB.  */
 461   if (num_nodes <= 1)
 462     {
 463       free (g);
 464       return NULL;
 465     }
 466
 467   /* Allocate the nodes array, and initialize the nodes.  */
 468   g->num_nodes = num_nodes;
 469   g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
 470   g->closing_branch = NULL;
 471   i = 0;
 472   first_note = NULL_RTX;
 473   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
 474        insn = NEXT_INSN (insn))
 475     {
 476       if (! INSN_P (insn))
 477         {
 478           if (! first_note && NOTE_P (insn)
 479               && NOTE_LINE_NUMBER (insn) !=  NOTE_INSN_BASIC_BLOCK)
 480             first_note = insn;
 481           continue;
 482         }
 483       if (JUMP_P (insn))
 484         {
 485           gcc_assert (!g->closing_branch);
 486           g->closing_branch = &g->nodes[i];
 487         }
 488       else if (GET_CODE (PATTERN (insn)) == USE)
 489         {
 490           if (! first_note)
 491             first_note = insn;
 492           continue;
 493         }
 494
 495       g->nodes[i].cuid = i;
 496       g->nodes[i].successors = sbitmap_alloc (num_nodes);
 497       sbitmap_zero (g->nodes[i].successors);
 498       g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
 499       sbitmap_zero (g->nodes[i].predecessors);
 500       g->nodes[i].first_note = (first_note ? first_note : insn);
 501       g->nodes[i++].insn = insn;
 502       first_note = NULL_RTX;
 503     }
 504
 505   /* We must have found a branch in DDG.  */
 506   gcc_assert (g->closing_branch);
 507
 508
 509   /* Build the data dependency graph.  */
 510   build_intra_loop_deps (g);
 511   build_inter_loop_deps (g, df);
 512   return g;
 513 }
 514
 515 /* Free all the memory allocated for the DDG.  */
 516 void
 517 free_ddg (ddg_ptr g)
 518 {
 519   int i;
 520
 521   if (!g)
 522     return;
 523
 524   for (i = 0; i < g->num_nodes; i++)
 525     {
 526       ddg_edge_ptr e = g->nodes[i].out;
 527
 528       while (e)
 529         {
 530           ddg_edge_ptr next = e->next_out;
 531
 532           free (e);
 533           e = next;
 534         }
 535       sbitmap_free (g->nodes[i].successors);
 536       sbitmap_free (g->nodes[i].predecessors);
 537     }
 538   if (g->num_backarcs > 0)
 539     free (g->backarcs);
 540   free (g->nodes);
 541   free (g);
 542 }
 543
 544 void
 545 print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
 546 {
 547   char dep_c;
 548
 549   switch (e->type) {
 550     case OUTPUT_DEP :
 551       dep_c = 'O';
 552       break;
 553     case ANTI_DEP :
 554       dep_c = 'A';
 555       break;
 556     default:
 557       dep_c = 'T';
 558   }
 559
 560   fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
 561            dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
 562 }
 563
 564 /* Print the DDG nodes with there in/out edges to the dump file.  */
 565 void
 566 print_ddg (FILE *dump_file, ddg_ptr g)
 567 {
 568   int i;
 569
 570   for (i = 0; i < g->num_nodes; i++)
 571     {
 572       ddg_edge_ptr e;
 573
 574       print_rtl_single (dump_file, g->nodes[i].insn);
 575       fprintf (dump_file, "OUT ARCS: ");
 576       for (e = g->nodes[i].out; e; e = e->next_out)
 577         print_ddg_edge (dump_file, e);
 578
 579       fprintf (dump_file, "\nIN ARCS: ");
 580       for (e = g->nodes[i].in; e; e = e->next_in)
 581         print_ddg_edge (dump_file, e);
 582
 583       fprintf (dump_file, "\n");
 584     }
 585 }
 586
 587 /* Print the given DDG in VCG format.  */
 588 void
 589 vcg_print_ddg (FILE *dump_file, ddg_ptr g)
 590 {
 591   int src_cuid;
 592
 593   fprintf (dump_file, "graph: {\n");
 594   for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
 595     {
 596       ddg_edge_ptr e;
 597       int src_uid = INSN_UID (g->nodes[src_cuid].insn);
 598
 599       fprintf (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
 600       print_rtl_single (dump_file, g->nodes[src_cuid].insn);
 601       fprintf (dump_file, "\"}\n");
 602       for (e = g->nodes[src_cuid].out; e; e = e->next_out)
 603         {
 604           int dst_uid = INSN_UID (e->dest->insn);
 605           int dst_cuid = e->dest->cuid;
 606
 607           /* Give the backarcs a different color.  */
 608           if (e->distance > 0)
 609             fprintf (dump_file, "backedge: {color: red ");
 610           else
 611             fprintf (dump_file, "edge: { ");
 612
 613           fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
 614           fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
 615           fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance);
 616         }
 617     }
 618   fprintf (dump_file, "}\n");
 619 }
 620
 621 /* Create an edge and initialize it with given values.  */
 622 static ddg_edge_ptr
 623 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
 624                  dep_type t, dep_data_type dt, int l, int d)
 625 {
 626   ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
 627
 628   e->src = src;
 629   e->dest = dest;
 630   e->type = t;
 631   e->data_type = dt;
 632   e->latency = l;
 633   e->distance = d;
 634   e->next_in = e->next_out = NULL;
 635   e->aux.info = 0;
 636   return e;
 637 }
 638
 639 /* Add the given edge to the in/out linked lists of the DDG nodes.  */
 640 static void
 641 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
 642 {
 643   ddg_node_ptr src = e->src;
 644   ddg_node_ptr dest = e->dest;
 645
 646   /* Should have allocated the sbitmaps.  */
 647   gcc_assert (src->successors && dest->predecessors);
 648
 649   SET_BIT (src->successors, dest->cuid);
 650   SET_BIT (dest->predecessors, src->cuid);
 651   e->next_in = dest->in;
 652   dest->in = e;
 653   e->next_out = src->out;
 654   src->out = e;
 655 }
 656
 657
 658 \f
 659 /* Algorithm for computing the recurrence_length of an scc.  We assume at
 660    for now that cycles in the data dependence graph contain a single backarc.
 661    This simplifies the algorithm, and can be generalized later.  */
 662 static void
 663 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
 664 {
 665   int j;
 666   int result = -1;
 667
 668   for (j = 0; j < scc->num_backarcs; j++)
 669     {
 670       ddg_edge_ptr backarc = scc->backarcs[j];
 671       int length;
 672       int distance = backarc->distance;
 673       ddg_node_ptr src = backarc->dest;
 674       ddg_node_ptr dest = backarc->src;
 675
 676       length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
 677       if (length < 0 )
 678         {
 679           /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
 680           continue;
 681         }
 682       length += backarc->latency;
 683       result = MAX (result, (length / distance));
 684     }
 685   scc->recurrence_length = result;
 686 }
 687
 688 /* Create a new SCC given the set of its nodes.  Compute its recurrence_length
 689    and mark edges that belong to this scc as IN_SCC.  */
 690 static ddg_scc_ptr
 691 create_scc (ddg_ptr g, sbitmap nodes)
 692 {
 693   ddg_scc_ptr scc;
 694   int u;
 695
 696   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
 697   scc->backarcs = NULL;
 698   scc->num_backarcs = 0;
 699   scc->nodes = sbitmap_alloc (g->num_nodes);
 700   sbitmap_copy (scc->nodes, nodes);
 701
 702   /* Mark the backarcs that belong to this SCC.  */
 703   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
 704     {
 705       ddg_edge_ptr e;
 706       ddg_node_ptr n = &g->nodes[u];
 707
 708       for (e = n->out; e; e = e->next_out)
 709         if (TEST_BIT (nodes, e->dest->cuid))
 710           {
 711             e->aux.count = IN_SCC;
 712             if (e->distance > 0)
 713               add_backarc_to_scc (scc, e);
 714           }
 715     });
 716
 717   set_recurrence_length (scc, g);
 718   return scc;
 719 }
 720
 721 /* Cleans the memory allocation of a given SCC.  */
 722 static void
 723 free_scc (ddg_scc_ptr scc)
 724 {
 725   if (!scc)
 726     return;
 727
 728   sbitmap_free (scc->nodes);
 729   if (scc->num_backarcs > 0)
 730     free (scc->backarcs);
 731   free (scc);
 732 }
 733
 734
 735 /* Add a given edge known to be a backarc to the given DDG.  */
 736 static void
 737 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
 738 {
 739   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 740
 741   add_edge_to_ddg (g, e);
 742   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
 743   g->backarcs[g->num_backarcs++] = e;
 744 }
 745
 746 /* Add backarc to an SCC.  */
 747 static void
 748 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
 749 {
 750   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 751
 752   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
 753   scc->backarcs[scc->num_backarcs++] = e;
 754 }
 755
 756 /* Add the given SCC to the DDG.  */
 757 static void
 758 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
 759 {
 760   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
 761
 762   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
 763   g->sccs[g->num_sccs++] = scc;
 764 }
 765
 766 /* Given the instruction INSN return the node that represents it.  */
 767 ddg_node_ptr
 768 get_node_of_insn (ddg_ptr g, rtx insn)
 769 {
 770   int i;
 771
 772   for (i = 0; i < g->num_nodes; i++)
 773     if (insn == g->nodes[i].insn)
 774       return &g->nodes[i];
 775   return NULL;
 776 }
 777
 778 /* Given a set OPS of nodes in the DDG, find the set of their successors
 779    which are not in OPS, and set their bits in SUCC.  Bits corresponding to
 780    OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
 781 void
 782 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
 783 {
 784   int i;
 785
 786   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 787     {
 788       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
 789       sbitmap_a_or_b (succ, succ, node_succ);
 790     });
 791
 792   /* We want those that are not in ops.  */
 793   sbitmap_difference (succ, succ, ops);
 794 }
 795
 796 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
 797    which are not in OPS, and set their bits in PREDS.  Bits corresponding to
 798    OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
 799 void
 800 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
 801 {
 802   int i;
 803
 804   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 805     {
 806       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
 807       sbitmap_a_or_b (preds, preds, node_preds);
 808     });
 809
 810   /* We want those that are not in ops.  */
 811   sbitmap_difference (preds, preds, ops);
 812 }
 813
 814
 815 /* Compare function to be passed to qsort to order the backarcs in descending
 816    recMII order.  */
 817 static int
 818 compare_sccs (const void *s1, const void *s2)
 819 {
 820   int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length;
 821   int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length;
 822   return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
 823
 824 }
 825
 826 /* Order the backarcs in descending recMII order using compare_sccs.  */
 827 static void
 828 order_sccs (ddg_all_sccs_ptr g)
 829 {
 830   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
 831          (int (*) (const void *, const void *)) compare_sccs);
 832 }
 833
 834 /* Perform the Strongly Connected Components decomposing algorithm on the
 835    DDG and return DDG_ALL_SCCS structure that contains them.  */
 836 ddg_all_sccs_ptr
 837 create_ddg_all_sccs (ddg_ptr g)
 838 {
 839   int i;
 840   int num_nodes = g->num_nodes;
 841   sbitmap from = sbitmap_alloc (num_nodes);
 842   sbitmap to = sbitmap_alloc (num_nodes);
 843   sbitmap scc_nodes = sbitmap_alloc (num_nodes);
 844   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
 845                           xmalloc (sizeof (struct ddg_all_sccs));
 846
 847   sccs->ddg = g;
 848   sccs->sccs = NULL;
 849   sccs->num_sccs = 0;
 850
 851   for (i = 0; i < g->num_backarcs; i++)
 852     {
 853       ddg_scc_ptr  scc;
 854       ddg_edge_ptr backarc = g->backarcs[i];
 855       ddg_node_ptr src = backarc->src;
 856       ddg_node_ptr dest = backarc->dest;
 857
 858       /* If the backarc already belongs to an SCC, continue.  */
 859       if (backarc->aux.count == IN_SCC)
 860         continue;
 861
 862       sbitmap_zero (from);
 863       sbitmap_zero (to);
 864       SET_BIT (from, dest->cuid);
 865       SET_BIT (to, src->cuid);
 866
 867       if (find_nodes_on_paths (scc_nodes, g, from, to))
 868         {
 869           scc = create_scc (g, scc_nodes);
 870           add_scc_to_ddg (sccs, scc);
 871         }
 872     }
 873   order_sccs (sccs);
 874   sbitmap_free (from);
 875   sbitmap_free (to);
 876   sbitmap_free (scc_nodes);
 877   return sccs;
 878 }
 879
 880 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
 881 void
 882 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
 883 {
 884   int i;
 885
 886   if (!all_sccs)
 887     return;
 888
 889   for (i = 0; i < all_sccs->num_sccs; i++)
 890     free_scc (all_sccs->sccs[i]);
 891
 892   free (all_sccs);
 893 }
 894
 895 \f
 896 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
 897    nodes - find all nodes that lie on paths from FROM to TO (not excluding
 898    nodes from FROM and TO).  Return nonzero if nodes exist.  */
 899 int
 900 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
 901 {
 902   int answer;
 903   int change, u;
 904   int num_nodes = g->num_nodes;
 905   sbitmap workset = sbitmap_alloc (num_nodes);
 906   sbitmap reachable_from = sbitmap_alloc (num_nodes);
 907   sbitmap reach_to = sbitmap_alloc (num_nodes);
 908   sbitmap tmp = sbitmap_alloc (num_nodes);
 909
 910   sbitmap_copy (reachable_from, from);
 911   sbitmap_copy (tmp, from);
 912
 913   change = 1;
 914   while (change)
 915     {
 916       change = 0;
 917       sbitmap_copy (workset, tmp);
 918       sbitmap_zero (tmp);
 919       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 920         {
 921           ddg_edge_ptr e;
 922           ddg_node_ptr u_node = &g->nodes[u];
 923
 924           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
 925             {
 926               ddg_node_ptr v_node = e->dest;
 927               int v = v_node->cuid;
 928
 929               if (!TEST_BIT (reachable_from, v))
 930                 {
 931                   SET_BIT (reachable_from, v);
 932                   SET_BIT (tmp, v);
 933                   change = 1;
 934                 }
 935             }
 936         });
 937     }
 938
 939   sbitmap_copy (reach_to, to);
 940   sbitmap_copy (tmp, to);
 941
 942   change = 1;
 943   while (change)
 944     {
 945       change = 0;
 946       sbitmap_copy (workset, tmp);
 947       sbitmap_zero (tmp);
 948       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 949         {
 950           ddg_edge_ptr e;
 951           ddg_node_ptr u_node = &g->nodes[u];
 952
 953           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
 954             {
 955               ddg_node_ptr v_node = e->src;
 956               int v = v_node->cuid;
 957
 958               if (!TEST_BIT (reach_to, v))
 959                 {
 960                   SET_BIT (reach_to, v);
 961                   SET_BIT (tmp, v);
 962                   change = 1;
 963                 }
 964             }
 965         });
 966     }
 967
 968   answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
 969   sbitmap_free (workset);
 970   sbitmap_free (reachable_from);
 971   sbitmap_free (reach_to);
 972   sbitmap_free (tmp);
 973   return answer;
 974 }
 975
 976
 977 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
 978    at-least as large as the count of U_NODE plus the latency between them.
 979    Sets a bit in TMP for each successor whose count was changed (increased).
 980    Returns nonzero if any count was changed.  */
 981 static int
 982 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
 983 {
 984   ddg_edge_ptr e;
 985   int result = 0;
 986
 987   for (e = u_node->out; e; e = e->next_out)
 988     {
 989       ddg_node_ptr v_node = e->dest;
 990       int v = v_node->cuid;
 991
 992       if (TEST_BIT (nodes, v)
 993           && (e->distance == 0)
 994           && (v_node->aux.count < u_node->aux.count + e->latency))
 995         {
 996           v_node->aux.count = u_node->aux.count + e->latency;
 997           SET_BIT (tmp, v);
 998           result = 1;
 999         }
1000     }
1001   return result;
1002 }
1003
1004
1005 /* Find the length of a longest path from SRC to DEST in G,
1006    going only through NODES, and disregarding backarcs.  */
1007 int
1008 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1009 {
1010   int i, u;
1011   int change = 1;
1012   int result;
1013   int num_nodes = g->num_nodes;
1014   sbitmap workset = sbitmap_alloc (num_nodes);
1015   sbitmap tmp = sbitmap_alloc (num_nodes);
1016
1017
1018   /* Data will hold the distance of the longest path found so far from
1019      src to each node.  Initialize to -1 = less than minimum.  */
1020   for (i = 0; i < g->num_nodes; i++)
1021     g->nodes[i].aux.count = -1;
1022   g->nodes[src].aux.count = 0;
1023
1024   sbitmap_zero (tmp);
1025   SET_BIT (tmp, src);
1026
1027   while (change)
1028     {
1029       change = 0;
1030       sbitmap_copy (workset, tmp);
1031       sbitmap_zero (tmp);
1032       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
1033         {
1034           ddg_node_ptr u_node = &g->nodes[u];
1035
1036           change |= update_dist_to_successors (u_node, nodes, tmp);
1037         });
1038     }
1039   result = g->nodes[dest].aux.count;
1040   sbitmap_free (workset);
1041   sbitmap_free (tmp);
1042   return result;
1043 }