gcc/ddg.c

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