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   if (!link)
 168     abort ();
 169
 170   /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!!  */
 171   if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 172     t = ANTI_DEP;
 173   else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 174     t = OUTPUT_DEP;
 175   latency = insn_cost (src_node->insn, link, dest_node->insn);
 176
 177   e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
 178
 179   if (interloop)
 180     {
 181       /* Some interloop dependencies are relaxed:
 182          1. Every insn is output dependent on itself; ignore such deps.
 183          2. Every true/flow dependence is an anti dependence in the
 184          opposite direction with distance 1; such register deps
 185          will be removed by renaming if broken --- ignore them.  */
 186       if (!(t == OUTPUT_DEP && src_node == dest_node)
 187           && !(t == ANTI_DEP && dt == REG_DEP))
 188         add_backarc_to_ddg (g, e);
 189       else
 190         free (e);
 191     }
 192   else
 193     add_edge_to_ddg (g, e);
 194 }
 195
 196 /* The same as the above function, but it doesn't require a link parameter.  */
 197 static void
 198 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
 199                         dep_type d_t, dep_data_type d_dt, int distance)
 200 {
 201   ddg_edge_ptr e;
 202   int l;
 203   rtx link = alloc_INSN_LIST (to->insn, NULL_RTX);
 204
 205   if (d_t == ANTI_DEP)
 206     PUT_REG_NOTE_KIND (link, REG_DEP_ANTI);
 207   else if (d_t == OUTPUT_DEP)
 208     PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT);
 209
 210   l = insn_cost (from->insn, link, to->insn);
 211   free_INSN_LIST_node (link);
 212
 213   e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
 214   if (distance > 0)
 215     add_backarc_to_ddg (g, e);
 216   else
 217     add_edge_to_ddg (g, e);
 218 }
 219
 220 \f
 221 /* Given a downwards exposed register def RD, add inter-loop true dependences
 222    for all its uses in the next iteration, and an output dependence to the
 223    first def of the next iteration.  */
 224 static void
 225 add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd)
 226 {
 227   int regno = DF_REF_REGNO (rd);
 228   struct bb_info *bb_info = DF_BB_INFO (df, g->bb);
 229   struct df_link *r_use;
 230   int use_before_def = false;
 231   rtx def_insn = DF_REF_INSN (rd);
 232   ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
 233
 234   /* Create and inter-loop true dependence between RD and each of its uses
 235      that is upwards exposed in RD's block.  */
 236   for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
 237     {
 238       if (bitmap_bit_p (bb_info->ru_gen, r_use->ref->id))
 239         {
 240           rtx use_insn = DF_REF_INSN (r_use->ref);
 241           ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
 242
 243           if (!src_node || !dest_node)
 244             abort ();
 245
 246           /* Any such upwards exposed use appears before the rd def.  */
 247           use_before_def = true;
 248           create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
 249                                   REG_DEP, 1);
 250         }
 251     }
 252
 253   /* Create an inter-loop output dependence between RD (which is the
 254      last def in its block, being downwards exposed) and the first def
 255      in its block.  Avoid creating a self output dependence.  Avoid creating
 256      an output dependence if there is a dependence path between the two defs
 257      starting with a true dependence followed by an anti dependence (i.e. if
 258      there is a use between the two defs.  */
 259   if (! use_before_def)
 260     {
 261       struct ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
 262       int i;
 263       ddg_node_ptr dest_node;
 264
 265       if (!def || rd->id == def->id)
 266         return;
 267
 268       /* Check if there are uses after RD.  */
 269       for (i = src_node->cuid + 1; i < g->num_nodes; i++)
 270          if (df_reg_used (df, g->nodes[i].insn, rd->reg))
 271            return;
 272
 273       dest_node = get_node_of_insn (g, def->insn);
 274       create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
 275     }
 276 }
 277
 278 /* Given a register USE, add an inter-loop anti dependence to the first
 279    (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
 280    by a def in the block.  */
 281 static void
 282 add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use)
 283 {
 284   int i;
 285   int regno = DF_REF_REGNO (use);
 286   struct ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno);
 287   ddg_node_ptr use_node;
 288   ddg_node_ptr def_node;
 289   struct bb_info *bb_info;
 290
 291   bb_info = DF_BB_INFO (df, g->bb);
 292
 293   if (!first_def)
 294     return;
 295
 296   use_node = get_node_of_insn (g, use->insn);
 297   def_node = get_node_of_insn (g, first_def->insn);
 298
 299   if (!use_node || !def_node)
 300     abort ();
 301
 302   /* Make sure there are no defs after USE.  */
 303   for (i = use_node->cuid + 1; i < g->num_nodes; i++)
 304      if (df_find_def (df, g->nodes[i].insn, use->reg))
 305        return;
 306   /* We must not add ANTI dep when there is an intra-loop TRUE dep in
 307      the opozite direction. If the first_def reaches the USE then there is
 308      such a dep.  */
 309   if (! bitmap_bit_p (bb_info->rd_gen, first_def->id))
 310     create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
 311 }
 312
 313 /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
 314 static void
 315 build_inter_loop_deps (ddg_ptr g, struct df *df)
 316 {
 317   int rd_num, u_num;
 318   struct bb_info *bb_info;
 319
 320   bb_info = DF_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 (bb_info->rd_gen, 0, rd_num,
 325     {
 326       struct ref *rd = df->defs[rd_num];
 327
 328       add_deps_for_def (g, df, rd);
 329     });
 330
 331   /* Find inter-loop anti deps.  We are interested in uses of the block that
 332      appear below all defs; this implies that these uses are killed.  */
 333   EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num,
 334     {
 335       struct ref *use = df->uses[u_num];
 336
 337       /* We are interested in uses of this BB.  */
 338       if (BLOCK_FOR_INSN (use->insn) == g->bb)
 339         add_deps_for_use (g, df,use);
 340     });
 341 }
 342
 343 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
 344    to ddg G.  */
 345 static void
 346 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
 347 {
 348   if (mem_write_insn_p (from->insn))
 349     {
 350       if (mem_read_insn_p (to->insn))
 351         create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
 352       else if (from->cuid != to->cuid)
 353         create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
 354     }
 355   else
 356     {
 357       if (mem_read_insn_p (to->insn))
 358         return;
 359       else if (from->cuid != to->cuid)
 360         {
 361           create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
 362           create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
 363         }
 364     }
 365
 366 }
 367
 368 /* Perform intra-block Data Dependency analysis and connect the nodes in
 369    the DDG.  We assume the loop has a single basic block.  */
 370 static void
 371 build_intra_loop_deps (ddg_ptr g)
 372 {
 373   int i;
 374   /* Hold the dependency analysis state during dependency calculations.  */
 375   struct deps tmp_deps;
 376   rtx head, tail, link;
 377
 378   /* Build the dependence information, using the sched_analyze function.  */
 379   init_deps_global ();
 380   init_deps (&tmp_deps);
 381
 382   /* Do the intra-block data dependence analysis for the given block.  */
 383   get_block_head_tail (g->bb->index, &head, &tail);
 384   sched_analyze (&tmp_deps, head, tail);
 385
 386   /* Build intra-loop data dependencies using the scheduler dependency
 387      analysis.  */
 388   for (i = 0; i < g->num_nodes; i++)
 389     {
 390       ddg_node_ptr dest_node = &g->nodes[i];
 391
 392       if (! INSN_P (dest_node->insn))
 393         continue;
 394
 395       for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1))
 396         {
 397           ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0));
 398
 399           if (!src_node)
 400             continue;
 401
 402           add_forward_dependence (XEXP (link, 0), dest_node->insn,
 403                                   REG_NOTE_KIND (link));
 404           create_ddg_dependence (g, src_node, dest_node,
 405                                  INSN_DEPEND (src_node->insn));
 406         }
 407
 408       /* If this insn modifies memory, add an edge to all insns that access
 409          memory.  */
 410       if (mem_access_insn_p (dest_node->insn))
 411         {
 412           int j;
 413
 414           for (j = 0; j <= i; j++)
 415             {
 416               ddg_node_ptr j_node = &g->nodes[j];
 417               if (mem_access_insn_p (j_node->insn))
 418                 /* Don't bother calculating inter-loop dep if an intra-loop dep
 419                    already exists.  */
 420                   if (! TEST_BIT (dest_node->successors, j))
 421                     add_inter_loop_mem_dep (g, dest_node, j_node);
 422             }
 423         }
 424     }
 425
 426   /* Free the INSN_LISTs.  */
 427   finish_deps_global ();
 428   free_deps (&tmp_deps);
 429 }
 430
 431
 432 /* Given a basic block, create its DDG and return a pointer to a variable
 433    of ddg type that represents it.
 434    Initialize the ddg structure fields to the appropriate values.  */
 435 ddg_ptr
 436 create_ddg (basic_block bb, struct df *df, int closing_branch_deps)
 437 {
 438   ddg_ptr g;
 439   rtx insn, first_note;
 440   int i;
 441   int num_nodes = 0;
 442
 443   g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
 444
 445   g->bb = bb;
 446   g->closing_branch_deps = closing_branch_deps;
 447
 448   /* Count the number of insns in the BB.  */
 449   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
 450        insn = NEXT_INSN (insn))
 451     {
 452       if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
 453         continue;
 454
 455       if (mem_read_insn_p (insn))
 456         g->num_loads++;
 457       if (mem_write_insn_p (insn))
 458         g->num_stores++;
 459       num_nodes++;
 460     }
 461
 462   /* There is nothing to do for this BB.  */
 463   if (num_nodes <= 1)
 464     {
 465       free (g);
 466       return NULL;
 467     }
 468
 469   /* Allocate the nodes array, and initialize the nodes.  */
 470   g->num_nodes = num_nodes;
 471   g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
 472   g->closing_branch = NULL;
 473   i = 0;
 474   first_note = NULL_RTX;
 475   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
 476        insn = NEXT_INSN (insn))
 477     {
 478       if (! INSN_P (insn))
 479         {
 480           if (! first_note && NOTE_P (insn)
 481               && NOTE_LINE_NUMBER (insn) !=  NOTE_INSN_BASIC_BLOCK)
 482             first_note = insn;
 483           continue;
 484         }
 485       if (JUMP_P (insn))
 486         {
 487           if (g->closing_branch)
 488             abort (); /* Found two branches in DDG.  */
 489           else
 490             g->closing_branch = &g->nodes[i];
 491         }
 492       else if (GET_CODE (PATTERN (insn)) == USE)
 493         {
 494           if (! first_note)
 495             first_note = insn;
 496           continue;
 497         }
 498
 499       g->nodes[i].cuid = i;
 500       g->nodes[i].successors = sbitmap_alloc (num_nodes);
 501       sbitmap_zero (g->nodes[i].successors);
 502       g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
 503       sbitmap_zero (g->nodes[i].predecessors);
 504       g->nodes[i].first_note = (first_note ? first_note : insn);
 505       g->nodes[i++].insn = insn;
 506       first_note = NULL_RTX;
 507     }
 508
 509   if (!g->closing_branch)
 510     abort ();  /* Found no branch in DDG.  */
 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 *dump_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 (dump_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 *dump_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 (dump_file, g->nodes[i].insn);
 578       fprintf (dump_file, "OUT ARCS: ");
 579       for (e = g->nodes[i].out; e; e = e->next_out)
 580         print_ddg_edge (dump_file, e);
 581
 582       fprintf (dump_file, "\nIN ARCS: ");
 583       for (e = g->nodes[i].in; e; e = e->next_in)
 584         print_ddg_edge (dump_file, e);
 585
 586       fprintf (dump_file, "\n");
 587     }
 588 }
 589
 590 /* Print the given DDG in VCG format.  */
 591 void
 592 vcg_print_ddg (FILE *dump_file, ddg_ptr g)
 593 {
 594   int src_cuid;
 595
 596   fprintf (dump_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 (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
 603       print_rtl_single (dump_file, g->nodes[src_cuid].insn);
 604       fprintf (dump_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 (dump_file, "backedge: {color: red ");
 613           else
 614             fprintf (dump_file, "edge: { ");
 615
 616           fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
 617           fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
 618           fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance);
 619         }
 620     }
 621   fprintf (dump_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   if (!src->successors || !dest->predecessors)
 650     abort (); /* Should have allocated the sbitmaps.  */
 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   int u;
 698
 699   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
 700   scc->backarcs = NULL;
 701   scc->num_backarcs = 0;
 702   scc->nodes = sbitmap_alloc (g->num_nodes);
 703   sbitmap_copy (scc->nodes, nodes);
 704
 705   /* Mark the backarcs that belong to this SCC.  */
 706   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
 707     {
 708       ddg_edge_ptr e;
 709       ddg_node_ptr n = &g->nodes[u];
 710
 711       for (e = n->out; e; e = e->next_out)
 712         if (TEST_BIT (nodes, e->dest->cuid))
 713           {
 714             e->aux.count = IN_SCC;
 715             if (e->distance > 0)
 716               add_backarc_to_scc (scc, e);
 717           }
 718     });
 719
 720   set_recurrence_length (scc, g);
 721   return scc;
 722 }
 723
 724 /* Cleans the memory allocation of a given SCC.  */
 725 static void
 726 free_scc (ddg_scc_ptr scc)
 727 {
 728   if (!scc)
 729     return;
 730
 731   sbitmap_free (scc->nodes);
 732   if (scc->num_backarcs > 0)
 733     free (scc->backarcs);
 734   free (scc);
 735 }
 736
 737
 738 /* Add a given edge known to be a backarc to the given DDG.  */
 739 static void
 740 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
 741 {
 742   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 743
 744   add_edge_to_ddg (g, e);
 745   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
 746   g->backarcs[g->num_backarcs++] = e;
 747 }
 748
 749 /* Add backarc to an SCC.  */
 750 static void
 751 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
 752 {
 753   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
 754
 755   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
 756   scc->backarcs[scc->num_backarcs++] = e;
 757 }
 758
 759 /* Add the given SCC to the DDG.  */
 760 static void
 761 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
 762 {
 763   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
 764
 765   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
 766   g->sccs[g->num_sccs++] = scc;
 767 }
 768
 769 /* Given the instruction INSN return the node that represents it.  */
 770 ddg_node_ptr
 771 get_node_of_insn (ddg_ptr g, rtx insn)
 772 {
 773   int i;
 774
 775   for (i = 0; i < g->num_nodes; i++)
 776     if (insn == g->nodes[i].insn)
 777       return &g->nodes[i];
 778   return NULL;
 779 }
 780
 781 /* Given a set OPS of nodes in the DDG, find the set of their successors
 782    which are not in OPS, and set their bits in SUCC.  Bits corresponding to
 783    OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
 784 void
 785 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
 786 {
 787   int i;
 788
 789   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 790     {
 791       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
 792       sbitmap_a_or_b (succ, succ, node_succ);
 793     });
 794
 795   /* We want those that are not in ops.  */
 796   sbitmap_difference (succ, succ, ops);
 797 }
 798
 799 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
 800    which are not in OPS, and set their bits in PREDS.  Bits corresponding to
 801    OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
 802 void
 803 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
 804 {
 805   int i;
 806
 807   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
 808     {
 809       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
 810       sbitmap_a_or_b (preds, preds, node_preds);
 811     });
 812
 813   /* We want those that are not in ops.  */
 814   sbitmap_difference (preds, preds, ops);
 815 }
 816
 817
 818 /* Compare function to be passed to qsort to order the backarcs in descending
 819    recMII order.  */
 820 static int
 821 compare_sccs (const void *s1, const void *s2)
 822 {
 823   int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length;
 824   int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length;
 825   return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
 826
 827 }
 828
 829 /* Order the backarcs in descending recMII order using compare_sccs.  */
 830 static void
 831 order_sccs (ddg_all_sccs_ptr g)
 832 {
 833   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
 834          (int (*) (const void *, const void *)) compare_sccs);
 835 }
 836
 837 /* Perform the Strongly Connected Components decomposing algorithm on the
 838    DDG and return DDG_ALL_SCCS structure that contains them.  */
 839 ddg_all_sccs_ptr
 840 create_ddg_all_sccs (ddg_ptr g)
 841 {
 842   int i;
 843   int num_nodes = g->num_nodes;
 844   sbitmap from = sbitmap_alloc (num_nodes);
 845   sbitmap to = sbitmap_alloc (num_nodes);
 846   sbitmap scc_nodes = sbitmap_alloc (num_nodes);
 847   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
 848                           xmalloc (sizeof (struct ddg_all_sccs));
 849
 850   sccs->ddg = g;
 851   sccs->sccs = NULL;
 852   sccs->num_sccs = 0;
 853
 854   for (i = 0; i < g->num_backarcs; i++)
 855     {
 856       ddg_scc_ptr  scc;
 857       ddg_edge_ptr backarc = g->backarcs[i];
 858       ddg_node_ptr src = backarc->src;
 859       ddg_node_ptr dest = backarc->dest;
 860
 861       /* If the backarc already belongs to an SCC, continue.  */
 862       if (backarc->aux.count == IN_SCC)
 863         continue;
 864
 865       sbitmap_zero (from);
 866       sbitmap_zero (to);
 867       SET_BIT (from, dest->cuid);
 868       SET_BIT (to, src->cuid);
 869
 870       if (find_nodes_on_paths (scc_nodes, g, from, to))
 871         {
 872           scc = create_scc (g, scc_nodes);
 873           add_scc_to_ddg (sccs, scc);
 874         }
 875     }
 876   order_sccs (sccs);
 877   sbitmap_free (from);
 878   sbitmap_free (to);
 879   sbitmap_free (scc_nodes);
 880   return sccs;
 881 }
 882
 883 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
 884 void
 885 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
 886 {
 887   int i;
 888
 889   if (!all_sccs)
 890     return;
 891
 892   for (i = 0; i < all_sccs->num_sccs; i++)
 893     free_scc (all_sccs->sccs[i]);
 894
 895   free (all_sccs);
 896 }
 897
 898 \f
 899 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
 900    nodes - find all nodes that lie on paths from FROM to TO (not excluding
 901    nodes from FROM and TO).  Return non zero if nodes exist.  */
 902 int
 903 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
 904 {
 905   int answer;
 906   int change, u;
 907   int num_nodes = g->num_nodes;
 908   sbitmap workset = sbitmap_alloc (num_nodes);
 909   sbitmap reachable_from = sbitmap_alloc (num_nodes);
 910   sbitmap reach_to = sbitmap_alloc (num_nodes);
 911   sbitmap tmp = sbitmap_alloc (num_nodes);
 912
 913   sbitmap_copy (reachable_from, from);
 914   sbitmap_copy (tmp, from);
 915
 916   change = 1;
 917   while (change)
 918     {
 919       change = 0;
 920       sbitmap_copy (workset, tmp);
 921       sbitmap_zero (tmp);
 922       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 923         {
 924           ddg_edge_ptr e;
 925           ddg_node_ptr u_node = &g->nodes[u];
 926
 927           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
 928             {
 929               ddg_node_ptr v_node = e->dest;
 930               int v = v_node->cuid;
 931
 932               if (!TEST_BIT (reachable_from, v))
 933                 {
 934                   SET_BIT (reachable_from, v);
 935                   SET_BIT (tmp, v);
 936                   change = 1;
 937                 }
 938             }
 939         });
 940     }
 941
 942   sbitmap_copy (reach_to, to);
 943   sbitmap_copy (tmp, to);
 944
 945   change = 1;
 946   while (change)
 947     {
 948       change = 0;
 949       sbitmap_copy (workset, tmp);
 950       sbitmap_zero (tmp);
 951       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
 952         {
 953           ddg_edge_ptr e;
 954           ddg_node_ptr u_node = &g->nodes[u];
 955
 956           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
 957             {
 958               ddg_node_ptr v_node = e->src;
 959               int v = v_node->cuid;
 960
 961               if (!TEST_BIT (reach_to, v))
 962                 {
 963                   SET_BIT (reach_to, v);
 964                   SET_BIT (tmp, v);
 965                   change = 1;
 966                 }
 967             }
 968         });
 969     }
 970
 971   answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
 972   sbitmap_free (workset);
 973   sbitmap_free (reachable_from);
 974   sbitmap_free (reach_to);
 975   sbitmap_free (tmp);
 976   return answer;
 977 }
 978
 979
 980 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
 981    at-least as large as the count of U_NODE plus the latency between them.
 982    Sets a bit in TMP for each successor whose count was changed (increased).
 983    Returns nonzero if any count was changed.  */
 984 static int
 985 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
 986 {
 987   ddg_edge_ptr e;
 988   int result = 0;
 989
 990   for (e = u_node->out; e; e = e->next_out)
 991     {
 992       ddg_node_ptr v_node = e->dest;
 993       int v = v_node->cuid;
 994
 995       if (TEST_BIT (nodes, v)
 996           && (e->distance == 0)
 997           && (v_node->aux.count < u_node->aux.count + e->latency))
 998         {
 999           v_node->aux.count = u_node->aux.count + e->latency;
1000           SET_BIT (tmp, v);
1001           result = 1;
1002         }
1003     }
1004   return result;
1005 }
1006
1007
1008 /* Find the length of a longest path from SRC to DEST in G,
1009    going only through NODES, and disregarding backarcs.  */
1010 int
1011 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1012 {
1013   int i, u;
1014   int change = 1;
1015   int result;
1016   int num_nodes = g->num_nodes;
1017   sbitmap workset = sbitmap_alloc (num_nodes);
1018   sbitmap tmp = sbitmap_alloc (num_nodes);
1019
1020
1021   /* Data will hold the distance of the longest path found so far from
1022      src to each node.  Initialize to -1 = less than minimum.  */
1023   for (i = 0; i < g->num_nodes; i++)
1024     g->nodes[i].aux.count = -1;
1025   g->nodes[src].aux.count = 0;
1026
1027   sbitmap_zero (tmp);
1028   SET_BIT (tmp, src);
1029
1030   while (change)
1031     {
1032       change = 0;
1033       sbitmap_copy (workset, tmp);
1034       sbitmap_zero (tmp);
1035       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
1036         {
1037           ddg_node_ptr u_node = &g->nodes[u];
1038
1039           change |= update_dist_to_successors (u_node, nodes, tmp);
1040         });
1041     }
1042   result = g->nodes[dest].aux.count;
1043   sbitmap_free (workset);
1044   sbitmap_free (tmp);
1045   return result;
1046 }