gcc/ddg.c

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