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