gcc/ddg.c

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