gcc/ddg.cc

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