LCOV - code coverage report
Current view: top level - gcc - ddg.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 0 543 0.0 %
Date: 2020-03-28 11:57:23 Functions: 0 39 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* DDG - Data Dependence Graph implementation.
       2                 :            :    Copyright (C) 2004-2020 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                 :            : 
      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                 :          0 : mark_mem_use (rtx *x, void *)
      53                 :            : {
      54                 :          0 :   subrtx_iterator::array_type array;
      55                 :          0 :   FOR_EACH_SUBRTX (iter, array, *x, NONCONST)
      56                 :          0 :     if (MEM_P (*iter))
      57                 :            :       {
      58                 :          0 :         mem_ref_p = true;
      59                 :          0 :         break;
      60                 :            :       }
      61                 :          0 : }
      62                 :            : 
      63                 :            : /* Returns nonzero if INSN reads from memory.  */
      64                 :            : static bool
      65                 :          0 : mem_read_insn_p (rtx_insn *insn)
      66                 :            : {
      67                 :          0 :   mem_ref_p = false;
      68                 :          0 :   note_uses (&PATTERN (insn), mark_mem_use, NULL);
      69                 :          0 :   return mem_ref_p;
      70                 :            : }
      71                 :            : 
      72                 :            : static void
      73                 :          0 : mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
      74                 :            : {
      75                 :          0 :   if (MEM_P (loc))
      76                 :          0 :     mem_ref_p = true;
      77                 :          0 : }
      78                 :            : 
      79                 :            : /* Returns nonzero if INSN writes to memory.  */
      80                 :            : static bool
      81                 :          0 : mem_write_insn_p (rtx_insn *insn)
      82                 :            : {
      83                 :          0 :   mem_ref_p = false;
      84                 :          0 :   note_stores (insn, mark_mem_store, NULL);
      85                 :          0 :   return mem_ref_p;
      86                 :            : }
      87                 :            : 
      88                 :            : /* Returns nonzero if X has access to memory.  */
      89                 :            : static bool
      90                 :          0 : rtx_mem_access_p (rtx x)
      91                 :            : {
      92                 :          0 :   int i, j;
      93                 :          0 :   const char *fmt;
      94                 :          0 :   enum rtx_code code;
      95                 :            : 
      96                 :          0 :   if (x == 0)
      97                 :            :     return false;
      98                 :            : 
      99                 :          0 :   if (MEM_P (x))
     100                 :            :     return true;
     101                 :            : 
     102                 :          0 :   code = GET_CODE (x);
     103                 :          0 :   fmt = GET_RTX_FORMAT (code);
     104                 :          0 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     105                 :            :     {
     106                 :          0 :       if (fmt[i] == 'e')
     107                 :            :         {
     108                 :          0 :           if (rtx_mem_access_p (XEXP (x, i)))
     109                 :            :             return true;
     110                 :            :         }
     111                 :          0 :       else if (fmt[i] == 'E')
     112                 :          0 :         for (j = 0; j < XVECLEN (x, i); j++)
     113                 :            :           {
     114                 :          0 :             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                 :          0 : mem_access_insn_p (rtx_insn *insn)
     124                 :            : {
     125                 :          0 :   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                 :          0 : autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn)
     138                 :            : {
     139                 :          0 :   rtx note;
     140                 :            : 
     141                 :          0 :   for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
     142                 :          0 :     if (REG_NOTE_KIND (note) == REG_INC
     143                 :          0 :         && 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                 :          0 : def_has_ccmode_p (rtx_insn *insn)
     153                 :            : {
     154                 :          0 :   df_ref def;
     155                 :            : 
     156                 :          0 :   FOR_EACH_INSN_DEF (def, insn)
     157                 :            :     {
     158                 :          0 :       machine_mode mode = GET_MODE (DF_REF_REG (def));
     159                 :            : 
     160                 :          0 :       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                 :          0 : 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                 :          0 :   ddg_edge_ptr e;
     174                 :          0 :   int latency, distance = 0;
     175                 :          0 :   dep_type t = TRUE_DEP;
     176                 :          0 :   dep_data_type dt = (mem_access_insn_p (src_node->insn)
     177                 :          0 :                       && mem_access_insn_p (dest_node->insn) ? MEM_DEP
     178                 :          0 :                                                              : REG_DEP);
     179                 :          0 :   gcc_assert (src_node->cuid < dest_node->cuid);
     180                 :          0 :   gcc_assert (link);
     181                 :            : 
     182                 :            :   /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!!  */
     183                 :          0 :   if (DEP_TYPE (link) == REG_DEP_ANTI)
     184                 :            :     t = ANTI_DEP;
     185                 :          0 :   else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
     186                 :          0 :     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                 :          0 :   if (flag_modulo_sched_allow_regmoves 
     199                 :          0 :       && (t == ANTI_DEP && dt == REG_DEP)
     200                 :          0 :       && !def_has_ccmode_p (dest_node->insn)
     201                 :          0 :       && !autoinc_var_is_used_p (dest_node->insn, src_node->insn))
     202                 :            :     {
     203                 :          0 :       rtx set;
     204                 :            : 
     205                 :          0 :       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                 :          0 :       if (set && REG_P (SET_DEST (set)))
     209                 :            :         {
     210                 :          0 :           int regno = REGNO (SET_DEST (set));
     211                 :          0 :           df_ref first_def;
     212                 :          0 :           class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
     213                 :            : 
     214                 :          0 :           first_def = df_bb_regno_first_def_find (g->bb, regno);
     215                 :          0 :           gcc_assert (first_def);
     216                 :            : 
     217                 :          0 :           if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
     218                 :            :             return;
     219                 :            :         }
     220                 :            :     }
     221                 :            : 
     222                 :          0 :   latency = dep_cost (link);
     223                 :          0 :   e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
     224                 :          0 :   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                 :          0 : 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                 :          0 :   ddg_edge_ptr e;
     233                 :          0 :   int l;
     234                 :          0 :   enum reg_note dep_kind;
     235                 :          0 :   struct _dep _dep, *dep = &_dep;
     236                 :            : 
     237                 :          0 :   if (d_t == ANTI_DEP)
     238                 :            :     dep_kind = REG_DEP_ANTI;
     239                 :          0 :   else if (d_t == OUTPUT_DEP)
     240                 :            :     dep_kind = REG_DEP_OUTPUT;
     241                 :            :   else
     242                 :            :     {
     243                 :          0 :       gcc_assert (d_t == TRUE_DEP);
     244                 :            : 
     245                 :            :       dep_kind = REG_DEP_TRUE;
     246                 :            :     }
     247                 :            : 
     248                 :          0 :   init_dep (dep, from->insn, to->insn, dep_kind);
     249                 :            : 
     250                 :          0 :   l = dep_cost (dep);
     251                 :            : 
     252                 :          0 :   e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
     253                 :          0 :   if (distance > 0)
     254                 :          0 :     add_backarc_to_ddg (g, e);
     255                 :            :   else
     256                 :          0 :     add_edge_to_ddg (g, e);
     257                 :          0 : }
     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                 :          0 : add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
     268                 :            : {
     269                 :          0 :   struct df_link *r_use;
     270                 :          0 :   int has_use_in_bb_p = false;
     271                 :          0 :   int regno = DF_REF_REGNO (last_def);
     272                 :          0 :   ddg_node_ptr last_def_node = get_node_of_insn (g, DF_REF_INSN (last_def));
     273                 :          0 :   df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
     274                 :          0 :   ddg_node_ptr first_def_node = get_node_of_insn (g, DF_REF_INSN (first_def));
     275                 :          0 :   ddg_node_ptr use_node;
     276                 :            : 
     277                 :          0 :   gcc_assert (last_def_node && first_def && first_def_node);
     278                 :            : 
     279                 :          0 :   if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def))
     280                 :            :     {
     281                 :          0 :       class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
     282                 :          0 :       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                 :          0 :   for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
     287                 :            :     {
     288                 :          0 :       if (DF_REF_BB (r_use->ref) != g->bb)
     289                 :          0 :         continue;
     290                 :            : 
     291                 :          0 :       gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use->ref)
     292                 :            :                   && DF_REF_INSN_INFO (r_use->ref) != NULL);
     293                 :            : 
     294                 :          0 :       rtx_insn *use_insn = DF_REF_INSN (r_use->ref);
     295                 :            : 
     296                 :          0 :       if (DEBUG_INSN_P (use_insn))
     297                 :          0 :         continue;
     298                 :            : 
     299                 :            :       /* ??? Do not handle uses with DF_REF_IN_NOTE notes.  */
     300                 :          0 :       use_node = get_node_of_insn (g, use_insn);
     301                 :          0 :       gcc_assert (use_node);
     302                 :          0 :       has_use_in_bb_p = true;
     303                 :          0 :       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                 :          0 :           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                 :          0 :           if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
     325                 :          0 :               || !flag_modulo_sched_allow_regmoves
     326                 :          0 :               || JUMP_P (use_node->insn)
     327                 :          0 :               || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
     328                 :          0 :               || def_has_ccmode_p (DF_REF_INSN (last_def)))
     329                 :          0 :             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                 :          0 :   if (!has_use_in_bb_p && DF_REF_ID (last_def) != DF_REF_ID (first_def))
     341                 :          0 :     create_ddg_dep_no_link (g, last_def_node, first_def_node,
     342                 :            :                             OUTPUT_DEP, REG_DEP, 1);
     343                 :          0 : }
     344                 :            : 
     345                 :            : /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
     346                 :            : static void
     347                 :          0 : build_inter_loop_deps (ddg_ptr g)
     348                 :            : {
     349                 :          0 :   unsigned rd_num;
     350                 :          0 :   class df_rd_bb_info *rd_bb_info;
     351                 :          0 :   bitmap_iterator bi;
     352                 :            : 
     353                 :          0 :   rd_bb_info = DF_RD_BB_INFO (g->bb);
     354                 :            : 
     355                 :            :   /* Find inter-loop register output, true and anti deps.  */
     356                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
     357                 :            :   {
     358                 :          0 :     df_ref rd = DF_DEFS_GET (rd_num);
     359                 :            : 
     360                 :          0 :     add_cross_iteration_register_deps (g, rd);
     361                 :            :   }
     362                 :          0 : }
     363                 :            : 
     364                 :            : 
     365                 :            : /* Return true if two specified instructions have mem expr with conflict
     366                 :            :    alias sets.  */
     367                 :            : static bool
     368                 :          0 : insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2)
     369                 :            : {
     370                 :          0 :   subrtx_iterator::array_type array1;
     371                 :          0 :   subrtx_iterator::array_type array2;
     372                 :          0 :   FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST)
     373                 :            :     {
     374                 :          0 :       const_rtx x1 = *iter1;
     375                 :          0 :       if (MEM_P (x1))
     376                 :          0 :         FOR_EACH_SUBRTX (iter2, array2, PATTERN (insn2), NONCONST)
     377                 :            :           {
     378                 :          0 :             const_rtx x2 = *iter2;
     379                 :          0 :             if (MEM_P (x2) && may_alias_p (x2, x1))
     380                 :          0 :               return true;
     381                 :            :           }
     382                 :            :     }
     383                 :          0 :   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                 :          0 : add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
     390                 :            : {
     391                 :            : 
     392                 :          0 :   if ((from->cuid == to->cuid)
     393                 :          0 :       || !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                 :          0 :     return;
     397                 :            : 
     398                 :          0 :   if (mem_write_insn_p (from->insn))
     399                 :            :     {
     400                 :          0 :       if (mem_read_insn_p (to->insn))
     401                 :          0 :         create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 0);
     402                 :            :       else
     403                 :          0 :         create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 0);
     404                 :            :     }
     405                 :          0 :   else if (!mem_read_insn_p (to->insn))
     406                 :          0 :     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                 :          0 : add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
     413                 :            : {
     414                 :          0 :   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                 :          0 :   if (mem_write_insn_p (from->insn))
     419                 :            :     {
     420                 :          0 :       if (mem_read_insn_p (to->insn))
     421                 :          0 :         create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
     422                 :          0 :       else if (from->cuid != to->cuid)
     423                 :          0 :         create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
     424                 :            :     }
     425                 :            :   else
     426                 :            :     {
     427                 :          0 :       if (mem_read_insn_p (to->insn))
     428                 :            :         return;
     429                 :          0 :       else if (from->cuid != to->cuid)
     430                 :            :         {
     431                 :          0 :           create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
     432                 :          0 :           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                 :          0 : build_intra_loop_deps (ddg_ptr g)
     441                 :            : {
     442                 :          0 :   int i;
     443                 :            :   /* Hold the dependency analysis state during dependency calculations.  */
     444                 :          0 :   class deps_desc tmp_deps;
     445                 :          0 :   rtx_insn *head, *tail;
     446                 :            : 
     447                 :            :   /* Build the dependence information, using the sched_analyze function.  */
     448                 :          0 :   init_deps_global ();
     449                 :          0 :   init_deps (&tmp_deps, false);
     450                 :            : 
     451                 :            :   /* Do the intra-block data dependence analysis for the given block.  */
     452                 :          0 :   get_ebb_head_tail (g->bb, g->bb, &head, &tail);
     453                 :          0 :   sched_analyze (&tmp_deps, head, tail);
     454                 :            : 
     455                 :            :   /* Build intra-loop data dependencies using the scheduler dependency
     456                 :            :      analysis.  */
     457                 :          0 :   for (i = 0; i < g->num_nodes; i++)
     458                 :            :     {
     459                 :          0 :       ddg_node_ptr dest_node = &g->nodes[i];
     460                 :          0 :       sd_iterator_def sd_it;
     461                 :          0 :       dep_t dep;
     462                 :            : 
     463                 :          0 :       FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
     464                 :            :         {
     465                 :          0 :           rtx_insn *src_insn = DEP_PRO (dep);
     466                 :          0 :           ddg_node_ptr src_node = get_node_of_insn (g, src_insn);
     467                 :            : 
     468                 :          0 :           if (!src_node)
     469                 :          0 :             continue;
     470                 :            : 
     471                 :          0 :           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                 :          0 :       if (mem_access_insn_p (dest_node->insn))
     477                 :            :         {
     478                 :            :           int j;
     479                 :            : 
     480                 :          0 :           for (j = 0; j <= i; j++)
     481                 :            :             {
     482                 :          0 :               ddg_node_ptr j_node = &g->nodes[j];
     483                 :            : 
     484                 :          0 :               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                 :          0 :                   if (! bitmap_bit_p (dest_node->successors, j))
     489                 :          0 :                     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                 :          0 :                   if (flag_modulo_sched_allow_regmoves
     498                 :          0 :                       && !bitmap_bit_p (dest_node->predecessors, j))
     499                 :          0 :                     add_intra_loop_mem_dep (g, j_node, dest_node);
     500                 :            :                 }
     501                 :            :             }
     502                 :            :         }
     503                 :            :     }
     504                 :            : 
     505                 :            :   /* Free the INSN_LISTs.  */
     506                 :          0 :   finish_deps_global ();
     507                 :          0 :   free_deps (&tmp_deps);
     508                 :            : 
     509                 :            :   /* Free dependencies.  */
     510                 :          0 :   sched_free_deps (head, tail, false);
     511                 :          0 : }
     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                 :          0 : create_ddg (basic_block bb, int closing_branch_deps)
     519                 :            : {
     520                 :          0 :   ddg_ptr g;
     521                 :          0 :   rtx_insn *insn, *first_note;
     522                 :          0 :   int i, j;
     523                 :          0 :   int num_nodes = 0;
     524                 :            : 
     525                 :          0 :   g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
     526                 :            : 
     527                 :          0 :   g->bb = bb;
     528                 :          0 :   g->closing_branch_deps = closing_branch_deps;
     529                 :            : 
     530                 :            :   /* Count the number of insns in the BB.  */
     531                 :          0 :   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
     532                 :          0 :        insn = NEXT_INSN (insn))
     533                 :            :     {
     534                 :          0 :       if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
     535                 :          0 :         continue;
     536                 :            : 
     537                 :          0 :       if (NONDEBUG_INSN_P (insn))
     538                 :            :         {
     539                 :          0 :           if (mem_read_insn_p (insn))
     540                 :          0 :             g->num_loads++;
     541                 :          0 :           if (mem_write_insn_p (insn))
     542                 :          0 :             g->num_stores++;
     543                 :          0 :           num_nodes++;
     544                 :            :         }
     545                 :            :     }
     546                 :            : 
     547                 :            :   /* There is nothing to do for this BB.  */
     548                 :          0 :   if (num_nodes <= 1)
     549                 :            :     {
     550                 :          0 :       free (g);
     551                 :          0 :       return NULL;
     552                 :            :     }
     553                 :            : 
     554                 :            :   /* Allocate the nodes array, and initialize the nodes.  */
     555                 :          0 :   g->num_nodes = num_nodes;
     556                 :          0 :   g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
     557                 :          0 :   g->closing_branch = NULL;
     558                 :          0 :   i = 0;
     559                 :          0 :   first_note = NULL;
     560                 :          0 :   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
     561                 :          0 :        insn = NEXT_INSN (insn))
     562                 :            :     {
     563                 :          0 :       if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
     564                 :          0 :         continue;
     565                 :            : 
     566                 :          0 :       if (!first_note && (INSN_P (insn) || NOTE_P (insn)))
     567                 :          0 :         first_note = insn;
     568                 :            : 
     569                 :          0 :       if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
     570                 :          0 :         continue;
     571                 :            : 
     572                 :          0 :       if (JUMP_P (insn))
     573                 :            :         {
     574                 :          0 :           gcc_assert (!g->closing_branch);
     575                 :          0 :           g->closing_branch = &g->nodes[i];
     576                 :            :         }
     577                 :            : 
     578                 :          0 :       if (NONDEBUG_INSN_P (insn))
     579                 :            :         {
     580                 :          0 :           g->nodes[i].cuid = i;
     581                 :          0 :           g->nodes[i].successors = sbitmap_alloc (num_nodes);
     582                 :          0 :           bitmap_clear (g->nodes[i].successors);
     583                 :          0 :           g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
     584                 :          0 :           bitmap_clear (g->nodes[i].predecessors);
     585                 :            : 
     586                 :          0 :           gcc_checking_assert (first_note);
     587                 :          0 :           g->nodes[i].first_note = first_note;
     588                 :            : 
     589                 :          0 :           g->nodes[i].aux.count = -1;
     590                 :          0 :           g->nodes[i].max_dist = XCNEWVEC (int, num_nodes);
     591                 :          0 :           for (j = 0; j < num_nodes; j++)
     592                 :          0 :             g->nodes[i].max_dist[j] = -1;
     593                 :            : 
     594                 :          0 :           g->nodes[i++].insn = insn;
     595                 :            :         }
     596                 :            :       first_note = NULL;
     597                 :            :     }
     598                 :            : 
     599                 :            :   /* We must have found a branch in DDG.  */
     600                 :          0 :   gcc_assert (g->closing_branch);
     601                 :            : 
     602                 :            : 
     603                 :            :   /* Build the data dependency graph.  */
     604                 :          0 :   build_intra_loop_deps (g);
     605                 :          0 :   build_inter_loop_deps (g);
     606                 :          0 :   return g;
     607                 :            : }
     608                 :            : 
     609                 :            : /* Free all the memory allocated for the DDG.  */
     610                 :            : void
     611                 :          0 : free_ddg (ddg_ptr g)
     612                 :            : {
     613                 :          0 :   int i;
     614                 :            : 
     615                 :          0 :   if (!g)
     616                 :            :     return;
     617                 :            : 
     618                 :          0 :   for (i = 0; i < g->num_nodes; i++)
     619                 :            :     {
     620                 :          0 :       ddg_edge_ptr e = g->nodes[i].out;
     621                 :            : 
     622                 :          0 :       while (e)
     623                 :            :         {
     624                 :          0 :           ddg_edge_ptr next = e->next_out;
     625                 :            : 
     626                 :          0 :           free (e);
     627                 :          0 :           e = next;
     628                 :            :         }
     629                 :          0 :       sbitmap_free (g->nodes[i].successors);
     630                 :          0 :       sbitmap_free (g->nodes[i].predecessors);
     631                 :          0 :       free (g->nodes[i].max_dist);
     632                 :            :     }
     633                 :          0 :   if (g->num_backarcs > 0)
     634                 :          0 :     free (g->backarcs);
     635                 :          0 :   free (g->nodes);
     636                 :          0 :   free (g);
     637                 :            : }
     638                 :            : 
     639                 :            : void
     640                 :          0 : print_ddg_edge (FILE *file, ddg_edge_ptr e)
     641                 :            : {
     642                 :          0 :   char dep_c;
     643                 :            : 
     644                 :          0 :   switch (e->type)
     645                 :            :     {
     646                 :            :     case OUTPUT_DEP :
     647                 :            :       dep_c = 'O';
     648                 :            :       break;
     649                 :          0 :     case ANTI_DEP :
     650                 :          0 :       dep_c = 'A';
     651                 :          0 :       break;
     652                 :          0 :     default:
     653                 :          0 :       dep_c = 'T';
     654                 :            :     }
     655                 :            : 
     656                 :          0 :   fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
     657                 :          0 :            dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
     658                 :          0 : }
     659                 :            : 
     660                 :            : /* Print the DDG nodes with there in/out edges to the dump file.  */
     661                 :            : void
     662                 :          0 : print_ddg (FILE *file, ddg_ptr g)
     663                 :            : {
     664                 :          0 :   int i;
     665                 :            : 
     666                 :          0 :   for (i = 0; i < g->num_nodes; i++)
     667                 :            :     {
     668                 :          0 :       ddg_edge_ptr e;
     669                 :            : 
     670                 :          0 :       fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
     671                 :          0 :       print_rtl_single (file, g->nodes[i].insn);
     672                 :          0 :       fprintf (file, "OUT ARCS: ");
     673                 :          0 :       for (e = g->nodes[i].out; e; e = e->next_out)
     674                 :          0 :         print_ddg_edge (file, e);
     675                 :            : 
     676                 :          0 :       fprintf (file, "\nIN ARCS: ");
     677                 :          0 :       for (e = g->nodes[i].in; e; e = e->next_in)
     678                 :          0 :         print_ddg_edge (file, e);
     679                 :            : 
     680                 :          0 :       fprintf (file, "\n");
     681                 :            :     }
     682                 :          0 : }
     683                 :            : 
     684                 :            : /* Print the given DDG in VCG format.  */
     685                 :            : DEBUG_FUNCTION void
     686                 :          0 : vcg_print_ddg (FILE *file, ddg_ptr g)
     687                 :            : {
     688                 :          0 :   int src_cuid;
     689                 :            : 
     690                 :          0 :   fprintf (file, "graph: {\n");
     691                 :          0 :   for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
     692                 :            :     {
     693                 :          0 :       ddg_edge_ptr e;
     694                 :          0 :       int src_uid = INSN_UID (g->nodes[src_cuid].insn);
     695                 :            : 
     696                 :          0 :       fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
     697                 :          0 :       print_rtl_single (file, g->nodes[src_cuid].insn);
     698                 :          0 :       fprintf (file, "\"}\n");
     699                 :          0 :       for (e = g->nodes[src_cuid].out; e; e = e->next_out)
     700                 :            :         {
     701                 :          0 :           int dst_uid = INSN_UID (e->dest->insn);
     702                 :          0 :           int dst_cuid = e->dest->cuid;
     703                 :            : 
     704                 :            :           /* Give the backarcs a different color.  */
     705                 :          0 :           if (e->distance > 0)
     706                 :          0 :             fprintf (file, "backedge: {color: red ");
     707                 :            :           else
     708                 :          0 :             fprintf (file, "edge: { ");
     709                 :            : 
     710                 :          0 :           fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
     711                 :          0 :           fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
     712                 :          0 :           fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
     713                 :            :         }
     714                 :            :     }
     715                 :          0 :   fprintf (file, "}\n");
     716                 :          0 : }
     717                 :            : 
     718                 :            : /* Dump the sccs in SCCS.  */
     719                 :            : void
     720                 :          0 : print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
     721                 :            : {
     722                 :          0 :   unsigned int u = 0;
     723                 :          0 :   sbitmap_iterator sbi;
     724                 :          0 :   int i;
     725                 :            : 
     726                 :          0 :   if (!file)
     727                 :          0 :     return;
     728                 :            : 
     729                 :          0 :   fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
     730                 :          0 :   for (i = 0; i < sccs->num_sccs; i++)
     731                 :            :     {
     732                 :          0 :       fprintf (file, "SCC number: %d\n", i);
     733                 :          0 :       EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
     734                 :            :       {
     735                 :          0 :         fprintf (file, "insn num %d\n", u);
     736                 :          0 :         print_rtl_single (file, g->nodes[u].insn);
     737                 :            :       }
     738                 :            :     }
     739                 :          0 :   fprintf (file, "\n");
     740                 :            : }
     741                 :            : 
     742                 :            : /* Create an edge and initialize it with given values.  */
     743                 :            : static ddg_edge_ptr
     744                 :          0 : 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                 :          0 :   ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
     748                 :            : 
     749                 :          0 :   e->src = src;
     750                 :          0 :   e->dest = dest;
     751                 :          0 :   e->type = t;
     752                 :          0 :   e->data_type = dt;
     753                 :          0 :   e->latency = l;
     754                 :          0 :   e->distance = d;
     755                 :          0 :   e->next_in = e->next_out = NULL;
     756                 :          0 :   e->in_scc = false;
     757                 :          0 :   return e;
     758                 :            : }
     759                 :            : 
     760                 :            : /* Add the given edge to the in/out linked lists of the DDG nodes.  */
     761                 :            : static void
     762                 :          0 : add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
     763                 :            : {
     764                 :          0 :   ddg_node_ptr src = e->src;
     765                 :          0 :   ddg_node_ptr dest = e->dest;
     766                 :            : 
     767                 :            :   /* Should have allocated the sbitmaps.  */
     768                 :          0 :   gcc_assert (src->successors && dest->predecessors);
     769                 :            : 
     770                 :          0 :   bitmap_set_bit (src->successors, dest->cuid);
     771                 :          0 :   bitmap_set_bit (dest->predecessors, src->cuid);
     772                 :          0 :   e->next_in = dest->in;
     773                 :          0 :   dest->in = e;
     774                 :          0 :   e->next_out = src->out;
     775                 :          0 :   src->out = e;
     776                 :          0 : }
     777                 :            : 
     778                 :            : 
     779                 :            : 
     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                 :          0 : set_recurrence_length (ddg_scc_ptr scc)
     785                 :            : {
     786                 :          0 :   int j;
     787                 :          0 :   int result = -1;
     788                 :            : 
     789                 :          0 :   for (j = 0; j < scc->num_backarcs; j++)
     790                 :            :     {
     791                 :          0 :       ddg_edge_ptr backarc = scc->backarcs[j];
     792                 :          0 :       int distance = backarc->distance;
     793                 :          0 :       ddg_node_ptr src = backarc->dest;
     794                 :          0 :       ddg_node_ptr dest = backarc->src;
     795                 :          0 :       int length = src->max_dist[dest->cuid];
     796                 :            : 
     797                 :          0 :       if (length < 0)
     798                 :          0 :         continue;
     799                 :            : 
     800                 :          0 :       length += backarc->latency;
     801                 :          0 :       result = MAX (result, (length / distance));
     802                 :            :     }
     803                 :          0 :   scc->recurrence_length = result;
     804                 :          0 : }
     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                 :          0 : create_scc (ddg_ptr g, sbitmap nodes, int id)
     810                 :            : {
     811                 :          0 :   ddg_scc_ptr scc;
     812                 :          0 :   unsigned int u = 0;
     813                 :          0 :   sbitmap_iterator sbi;
     814                 :            : 
     815                 :          0 :   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
     816                 :          0 :   scc->backarcs = NULL;
     817                 :          0 :   scc->num_backarcs = 0;
     818                 :          0 :   scc->nodes = sbitmap_alloc (g->num_nodes);
     819                 :          0 :   bitmap_copy (scc->nodes, nodes);
     820                 :            : 
     821                 :            :   /* Mark the backarcs that belong to this SCC.  */
     822                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
     823                 :            :     {
     824                 :          0 :       ddg_edge_ptr e;
     825                 :          0 :       ddg_node_ptr n = &g->nodes[u];
     826                 :            : 
     827                 :          0 :       gcc_assert (n->aux.count == -1);
     828                 :          0 :       n->aux.count = id;
     829                 :            : 
     830                 :          0 :       for (e = n->out; e; e = e->next_out)
     831                 :          0 :         if (bitmap_bit_p (nodes, e->dest->cuid))
     832                 :            :           {
     833                 :          0 :             e->in_scc = true;
     834                 :          0 :             if (e->distance > 0)
     835                 :          0 :               add_backarc_to_scc (scc, e);
     836                 :            :           }
     837                 :            :     }
     838                 :            : 
     839                 :          0 :   return scc;
     840                 :            : }
     841                 :            : 
     842                 :            : /* Cleans the memory allocation of a given SCC.  */
     843                 :            : static void
     844                 :          0 : free_scc (ddg_scc_ptr scc)
     845                 :            : {
     846                 :          0 :   if (!scc)
     847                 :            :     return;
     848                 :            : 
     849                 :          0 :   sbitmap_free (scc->nodes);
     850                 :          0 :   if (scc->num_backarcs > 0)
     851                 :          0 :     free (scc->backarcs);
     852                 :          0 :   free (scc);
     853                 :            : }
     854                 :            : 
     855                 :            : 
     856                 :            : /* Add a given edge known to be a backarc to the given DDG.  */
     857                 :            : static void
     858                 :          0 : add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
     859                 :            : {
     860                 :          0 :   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
     861                 :            : 
     862                 :          0 :   add_edge_to_ddg (g, e);
     863                 :          0 :   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
     864                 :          0 :   g->backarcs[g->num_backarcs++] = e;
     865                 :          0 : }
     866                 :            : 
     867                 :            : /* Add backarc to an SCC.  */
     868                 :            : static void
     869                 :          0 : add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
     870                 :            : {
     871                 :          0 :   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
     872                 :            : 
     873                 :          0 :   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
     874                 :          0 :   scc->backarcs[scc->num_backarcs++] = e;
     875                 :          0 : }
     876                 :            : 
     877                 :            : /* Add the given SCC to the DDG.  */
     878                 :            : static void
     879                 :          0 : add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
     880                 :            : {
     881                 :          0 :   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
     882                 :            : 
     883                 :          0 :   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
     884                 :          0 :   g->sccs[g->num_sccs++] = scc;
     885                 :          0 : }
     886                 :            : 
     887                 :            : /* Given the instruction INSN return the node that represents it.  */
     888                 :            : ddg_node_ptr
     889                 :          0 : get_node_of_insn (ddg_ptr g, rtx_insn *insn)
     890                 :            : {
     891                 :          0 :   int i;
     892                 :            : 
     893                 :          0 :   for (i = 0; i < g->num_nodes; i++)
     894                 :          0 :     if (insn == g->nodes[i].insn)
     895                 :          0 :       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                 :          0 : find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
     904                 :            : {
     905                 :          0 :   unsigned int i = 0;
     906                 :          0 :   sbitmap_iterator sbi;
     907                 :            : 
     908                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
     909                 :            :     {
     910                 :          0 :       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
     911                 :          0 :       bitmap_ior (succ, succ, node_succ);
     912                 :          0 :     };
     913                 :            : 
     914                 :            :   /* We want those that are not in ops.  */
     915                 :          0 :   bitmap_and_compl (succ, succ, ops);
     916                 :          0 : }
     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                 :          0 : find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
     923                 :            : {
     924                 :          0 :   unsigned int i = 0;
     925                 :          0 :   sbitmap_iterator sbi;
     926                 :            : 
     927                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
     928                 :            :     {
     929                 :          0 :       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
     930                 :          0 :       bitmap_ior (preds, preds, node_preds);
     931                 :          0 :     };
     932                 :            : 
     933                 :            :   /* We want those that are not in ops.  */
     934                 :          0 :   bitmap_and_compl (preds, preds, ops);
     935                 :          0 : }
     936                 :            : 
     937                 :            : 
     938                 :            : /* Compare function to be passed to qsort to order the backarcs in descending
     939                 :            :    recMII order.  */
     940                 :            : static int
     941                 :          0 : compare_sccs (const void *s1, const void *s2)
     942                 :            : {
     943                 :          0 :   const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
     944                 :          0 :   const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
     945                 :          0 :   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                 :          0 : order_sccs (ddg_all_sccs_ptr g)
     952                 :            : {
     953                 :          0 :   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
     954                 :            :          (int (*) (const void *, const void *)) compare_sccs);
     955                 :          0 : }
     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                 :          0 : check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
     961                 :            : {
     962                 :          0 :   int i = 0;
     963                 :          0 :   auto_sbitmap tmp (num_nodes);
     964                 :            : 
     965                 :          0 :   bitmap_clear (tmp);
     966                 :          0 :   for (i = 0; i < sccs->num_sccs; i++)
     967                 :            :     {
     968                 :          0 :       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                 :          0 :       gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes));
     972                 :          0 :       bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes);
     973                 :            :     }
     974                 :          0 : }
     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                 :          0 : create_ddg_all_sccs (ddg_ptr g)
     980                 :            : {
     981                 :          0 :   int i, j, k, scc, way;
     982                 :          0 :   int num_nodes = g->num_nodes;
     983                 :          0 :   auto_sbitmap from (num_nodes);
     984                 :          0 :   auto_sbitmap to (num_nodes);
     985                 :          0 :   auto_sbitmap scc_nodes (num_nodes);
     986                 :          0 :   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
     987                 :          0 :                           xmalloc (sizeof (struct ddg_all_sccs));
     988                 :            : 
     989                 :          0 :   sccs->ddg = g;
     990                 :          0 :   sccs->sccs = NULL;
     991                 :          0 :   sccs->num_sccs = 0;
     992                 :            : 
     993                 :          0 :   for (i = 0; i < g->num_backarcs; i++)
     994                 :            :     {
     995                 :          0 :       ddg_scc_ptr  scc;
     996                 :          0 :       ddg_edge_ptr backarc = g->backarcs[i];
     997                 :          0 :       ddg_node_ptr src = backarc->src;
     998                 :          0 :       ddg_node_ptr dest = backarc->dest;
     999                 :            : 
    1000                 :            :       /* If the backarc already belongs to an SCC, continue.  */
    1001                 :          0 :       if (backarc->in_scc)
    1002                 :          0 :         continue;
    1003                 :            : 
    1004                 :          0 :       bitmap_clear (scc_nodes);
    1005                 :          0 :       bitmap_clear (from);
    1006                 :          0 :       bitmap_clear (to);
    1007                 :          0 :       bitmap_set_bit (from, dest->cuid);
    1008                 :          0 :       bitmap_set_bit (to, src->cuid);
    1009                 :            : 
    1010                 :          0 :       if (find_nodes_on_paths (scc_nodes, g, from, to))
    1011                 :            :         {
    1012                 :          0 :           scc = create_scc (g, scc_nodes, sccs->num_sccs);
    1013                 :          0 :           add_scc_to_ddg (sccs, scc);
    1014                 :            :         }
    1015                 :            :     }
    1016                 :            : 
    1017                 :            :   /* Init max_dist arrays for Floyd–Warshall-like
    1018                 :            :      longest patch calculation algorithm.  */
    1019                 :          0 :   for (k = 0; k < num_nodes; k++)
    1020                 :            :     {
    1021                 :          0 :       ddg_edge_ptr e;
    1022                 :          0 :       ddg_node_ptr n = &g->nodes[k];
    1023                 :            : 
    1024                 :          0 :       if (n->aux.count == -1)
    1025                 :          0 :         continue;
    1026                 :            : 
    1027                 :          0 :       n->max_dist[k] = 0;
    1028                 :          0 :       for (e = n->out; e; e = e->next_out)
    1029                 :          0 :         if (e->distance == 0 && g->nodes[e->dest->cuid].aux.count == n->aux.count)
    1030                 :          0 :           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                 :          0 :   for (k = 0; k < num_nodes; k++)
    1036                 :            :     {
    1037                 :          0 :       scc = g->nodes[k].aux.count;
    1038                 :          0 :       if (scc != -1)
    1039                 :            :         {
    1040                 :          0 :           for (i = 0; i < num_nodes; i++)
    1041                 :          0 :             if (g->nodes[i].aux.count == scc)
    1042                 :          0 :               for (j = 0; j < num_nodes; j++)
    1043                 :          0 :                 if (g->nodes[j].aux.count == scc
    1044                 :          0 :                     && g->nodes[i].max_dist[k] >= 0
    1045                 :          0 :                     && g->nodes[k].max_dist[j] >= 0)
    1046                 :            :                   {
    1047                 :          0 :                     way = g->nodes[i].max_dist[k] + g->nodes[k].max_dist[j];
    1048                 :          0 :                     if (g->nodes[i].max_dist[j] < way)
    1049                 :          0 :                       g->nodes[i].max_dist[j] = way;
    1050                 :            :                   }
    1051                 :            :         }
    1052                 :            :     }
    1053                 :            : 
    1054                 :            :   /* Calculate recurrence_length using max_dist info.  */
    1055                 :          0 :   for (i = 0; i < sccs->num_sccs; i++)
    1056                 :          0 :     set_recurrence_length (sccs->sccs[i]);
    1057                 :            : 
    1058                 :          0 :   order_sccs (sccs);
    1059                 :            : 
    1060                 :          0 :   if (flag_checking)
    1061                 :          0 :     check_sccs (sccs, num_nodes);
    1062                 :            : 
    1063                 :          0 :   return sccs;
    1064                 :            : }
    1065                 :            : 
    1066                 :            : /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
    1067                 :            : void
    1068                 :          0 : free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
    1069                 :            : {
    1070                 :          0 :   int i;
    1071                 :            : 
    1072                 :          0 :   if (!all_sccs)
    1073                 :            :     return;
    1074                 :            : 
    1075                 :          0 :   for (i = 0; i < all_sccs->num_sccs; i++)
    1076                 :          0 :     free_scc (all_sccs->sccs[i]);
    1077                 :            : 
    1078                 :          0 :   free (all_sccs->sccs);
    1079                 :          0 :   free (all_sccs);
    1080                 :            : }
    1081                 :            : 
    1082                 :            : 
    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                 :          0 : find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
    1088                 :            : {
    1089                 :          0 :   int change;
    1090                 :          0 :   unsigned int u = 0;
    1091                 :          0 :   int num_nodes = g->num_nodes;
    1092                 :          0 :   sbitmap_iterator sbi;
    1093                 :            : 
    1094                 :          0 :   auto_sbitmap workset (num_nodes);
    1095                 :          0 :   auto_sbitmap reachable_from (num_nodes);
    1096                 :          0 :   auto_sbitmap reach_to (num_nodes);
    1097                 :          0 :   auto_sbitmap tmp (num_nodes);
    1098                 :            : 
    1099                 :          0 :   bitmap_copy (reachable_from, from);
    1100                 :          0 :   bitmap_copy (tmp, from);
    1101                 :            : 
    1102                 :          0 :   change = 1;
    1103                 :          0 :   while (change)
    1104                 :            :     {
    1105                 :          0 :       change = 0;
    1106                 :          0 :       bitmap_copy (workset, tmp);
    1107                 :          0 :       bitmap_clear (tmp);
    1108                 :          0 :       EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
    1109                 :            :         {
    1110                 :          0 :           ddg_edge_ptr e;
    1111                 :          0 :           ddg_node_ptr u_node = &g->nodes[u];
    1112                 :            : 
    1113                 :          0 :           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
    1114                 :            :             {
    1115                 :          0 :               ddg_node_ptr v_node = e->dest;
    1116                 :          0 :               int v = v_node->cuid;
    1117                 :            : 
    1118                 :          0 :               if (!bitmap_bit_p (reachable_from, v))
    1119                 :            :                 {
    1120                 :          0 :                   bitmap_set_bit (reachable_from, v);
    1121                 :          0 :                   bitmap_set_bit (tmp, v);
    1122                 :          0 :                   change = 1;
    1123                 :            :                 }
    1124                 :            :             }
    1125                 :            :         }
    1126                 :            :     }
    1127                 :            : 
    1128                 :          0 :   bitmap_copy (reach_to, to);
    1129                 :          0 :   bitmap_copy (tmp, to);
    1130                 :            : 
    1131                 :          0 :   change = 1;
    1132                 :          0 :   while (change)
    1133                 :            :     {
    1134                 :          0 :       change = 0;
    1135                 :          0 :       bitmap_copy (workset, tmp);
    1136                 :          0 :       bitmap_clear (tmp);
    1137                 :          0 :       EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
    1138                 :            :         {
    1139                 :          0 :           ddg_edge_ptr e;
    1140                 :          0 :           ddg_node_ptr u_node = &g->nodes[u];
    1141                 :            : 
    1142                 :          0 :           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
    1143                 :            :             {
    1144                 :          0 :               ddg_node_ptr v_node = e->src;
    1145                 :          0 :               int v = v_node->cuid;
    1146                 :            : 
    1147                 :          0 :               if (!bitmap_bit_p (reach_to, v))
    1148                 :            :                 {
    1149                 :          0 :                   bitmap_set_bit (reach_to, v);
    1150                 :          0 :                   bitmap_set_bit (tmp, v);
    1151                 :          0 :                   change = 1;
    1152                 :            :                 }
    1153                 :            :             }
    1154                 :            :         }
    1155                 :            :     }
    1156                 :            : 
    1157                 :          0 :   return bitmap_and (result, reachable_from, reach_to);
    1158                 :            : }
    1159                 :            : 
    1160                 :            : #endif /* INSN_SCHEDULING */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.