LCOV - code coverage report
Current view: top level - gcc - tree-loop-distribution.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1305 1383 94.4 %
Date: 2020-03-28 11:57:23 Functions: 66 75 88.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Loop distribution.
       2                 :            :    Copyright (C) 2006-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
       4                 :            :    and Sebastian Pop <sebastian.pop@amd.com>.
       5                 :            : 
       6                 :            : This file is part of GCC.
       7                 :            : 
       8                 :            : GCC is free software; you can redistribute it and/or modify it
       9                 :            : under the terms of the GNU General Public License as published by the
      10                 :            : Free Software Foundation; either version 3, or (at your option) any
      11                 :            : later version.
      12                 :            : 
      13                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT
      14                 :            : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      15                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      16                 :            : for more details.
      17                 :            : 
      18                 :            : You should have received a copy of the GNU General Public License
      19                 :            : along with GCC; see the file COPYING3.  If not see
      20                 :            : <http://www.gnu.org/licenses/>.  */
      21                 :            : 
      22                 :            : /* This pass performs loop distribution: for example, the loop
      23                 :            : 
      24                 :            :    |DO I = 2, N
      25                 :            :    |    A(I) = B(I) + C
      26                 :            :    |    D(I) = A(I-1)*E
      27                 :            :    |ENDDO
      28                 :            : 
      29                 :            :    is transformed to
      30                 :            : 
      31                 :            :    |DOALL I = 2, N
      32                 :            :    |   A(I) = B(I) + C
      33                 :            :    |ENDDO
      34                 :            :    |
      35                 :            :    |DOALL I = 2, N
      36                 :            :    |   D(I) = A(I-1)*E
      37                 :            :    |ENDDO
      38                 :            : 
      39                 :            :    Loop distribution is the dual of loop fusion.  It separates statements
      40                 :            :    of a loop (or loop nest) into multiple loops (or loop nests) with the
      41                 :            :    same loop header.  The major goal is to separate statements which may
      42                 :            :    be vectorized from those that can't.  This pass implements distribution
      43                 :            :    in the following steps:
      44                 :            : 
      45                 :            :      1) Seed partitions with specific type statements.  For now we support
      46                 :            :         two types seed statements: statement defining variable used outside
      47                 :            :         of loop; statement storing to memory.
      48                 :            :      2) Build reduced dependence graph (RDG) for loop to be distributed.
      49                 :            :         The vertices (RDG:V) model all statements in the loop and the edges
      50                 :            :         (RDG:E) model flow and control dependencies between statements.
      51                 :            :      3) Apart from RDG, compute data dependencies between memory references.
      52                 :            :      4) Starting from seed statement, build up partition by adding depended
      53                 :            :         statements according to RDG's dependence information.  Partition is
      54                 :            :         classified as parallel type if it can be executed paralleled; or as
      55                 :            :         sequential type if it can't.  Parallel type partition is further
      56                 :            :         classified as different builtin kinds if it can be implemented as
      57                 :            :         builtin function calls.
      58                 :            :      5) Build partition dependence graph (PG) based on data dependencies.
      59                 :            :         The vertices (PG:V) model all partitions and the edges (PG:E) model
      60                 :            :         all data dependencies between every partitions pair.  In general,
      61                 :            :         data dependence is either compilation time known or unknown.  In C
      62                 :            :         family languages, there exists quite amount compilation time unknown
      63                 :            :         dependencies because of possible alias relation of data references.
      64                 :            :         We categorize PG's edge to two types: "true" edge that represents
      65                 :            :         compilation time known data dependencies; "alias" edge for all other
      66                 :            :         data dependencies.
      67                 :            :      6) Traverse subgraph of PG as if all "alias" edges don't exist.  Merge
      68                 :            :         partitions in each strong connected component (SCC) correspondingly.
      69                 :            :         Build new PG for merged partitions.
      70                 :            :      7) Traverse PG again and this time with both "true" and "alias" edges
      71                 :            :         included.  We try to break SCCs by removing some edges.  Because
      72                 :            :         SCCs by "true" edges are all fused in step 6), we can break SCCs
      73                 :            :         by removing some "alias" edges.  It's NP-hard to choose optimal
      74                 :            :         edge set, fortunately simple approximation is good enough for us
      75                 :            :         given the small problem scale.
      76                 :            :      8) Collect all data dependencies of the removed "alias" edges.  Create
      77                 :            :         runtime alias checks for collected data dependencies.
      78                 :            :      9) Version loop under the condition of runtime alias checks.  Given
      79                 :            :         loop distribution generally introduces additional overhead, it is
      80                 :            :         only useful if vectorization is achieved in distributed loop.  We
      81                 :            :         version loop with internal function call IFN_LOOP_DIST_ALIAS.  If
      82                 :            :         no distributed loop can be vectorized, we simply remove distributed
      83                 :            :         loops and recover to the original one.
      84                 :            : 
      85                 :            :    TODO:
      86                 :            :      1) We only distribute innermost two-level loop nest now.  We should
      87                 :            :         extend it for arbitrary loop nests in the future.
      88                 :            :      2) We only fuse partitions in SCC now.  A better fusion algorithm is
      89                 :            :         desired to minimize loop overhead, maximize parallelism and maximize
      90                 :            :         data reuse.  */
      91                 :            : 
      92                 :            : #include "config.h"
      93                 :            : #include "system.h"
      94                 :            : #include "coretypes.h"
      95                 :            : #include "backend.h"
      96                 :            : #include "tree.h"
      97                 :            : #include "gimple.h"
      98                 :            : #include "cfghooks.h"
      99                 :            : #include "tree-pass.h"
     100                 :            : #include "ssa.h"
     101                 :            : #include "gimple-pretty-print.h"
     102                 :            : #include "fold-const.h"
     103                 :            : #include "cfganal.h"
     104                 :            : #include "gimple-iterator.h"
     105                 :            : #include "gimplify-me.h"
     106                 :            : #include "stor-layout.h"
     107                 :            : #include "tree-cfg.h"
     108                 :            : #include "tree-ssa-loop-manip.h"
     109                 :            : #include "tree-ssa-loop-ivopts.h"
     110                 :            : #include "tree-ssa-loop.h"
     111                 :            : #include "tree-into-ssa.h"
     112                 :            : #include "tree-ssa.h"
     113                 :            : #include "cfgloop.h"
     114                 :            : #include "tree-scalar-evolution.h"
     115                 :            : #include "tree-vectorizer.h"
     116                 :            : #include "tree-eh.h"
     117                 :            : #include "gimple-fold.h"
     118                 :            : 
     119                 :            : 
     120                 :            : #define MAX_DATAREFS_NUM \
     121                 :            :         ((unsigned) param_loop_max_datarefs_for_datadeps)
     122                 :            : 
     123                 :            : /* Threshold controlling number of distributed partitions.  Given it may
     124                 :            :    be unnecessary if a memory stream cost model is invented in the future,
     125                 :            :    we define it as a temporary macro, rather than a parameter.  */
     126                 :            : #define NUM_PARTITION_THRESHOLD (4)
     127                 :            : 
     128                 :            : /* Hashtable helpers.  */
     129                 :            : 
     130                 :            : struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
     131                 :            : {
     132                 :            :   static inline hashval_t hash (const data_dependence_relation *);
     133                 :            :   static inline bool equal (const data_dependence_relation *,
     134                 :            :                             const data_dependence_relation *);
     135                 :            : };
     136                 :            : 
     137                 :            : /* Hash function for data dependence.  */
     138                 :            : 
     139                 :            : inline hashval_t
     140                 :            : ddr_hasher::hash (const data_dependence_relation *ddr)
     141                 :            : {
     142                 :            :   inchash::hash h;
     143                 :            :   h.add_ptr (DDR_A (ddr));
     144                 :            :   h.add_ptr (DDR_B (ddr));
     145                 :            :   return h.end ();
     146                 :            : }
     147                 :            : 
     148                 :            : /* Hash table equality function for data dependence.  */
     149                 :            : 
     150                 :            : inline bool
     151                 :    2985840 : ddr_hasher::equal (const data_dependence_relation *ddr1,
     152                 :            :                    const data_dependence_relation *ddr2)
     153                 :            : {
     154                 :    2985840 :   return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
     155                 :            : }
     156                 :            : 
     157                 :            : 
     158                 :            : 
     159                 :            : #define DR_INDEX(dr)      ((uintptr_t) (dr)->aux)
     160                 :            : 
     161                 :            : /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
     162                 :            : struct rdg_vertex
     163                 :            : {
     164                 :            :   /* The statement represented by this vertex.  */
     165                 :            :   gimple *stmt;
     166                 :            : 
     167                 :            :   /* Vector of data-references in this statement.  */
     168                 :            :   vec<data_reference_p> datarefs;
     169                 :            : 
     170                 :            :   /* True when the statement contains a write to memory.  */
     171                 :            :   bool has_mem_write;
     172                 :            : 
     173                 :            :   /* True when the statement contains a read from memory.  */
     174                 :            :   bool has_mem_reads;
     175                 :            : };
     176                 :            : 
     177                 :            : #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
     178                 :            : #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
     179                 :            : #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
     180                 :            : #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
     181                 :            : #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
     182                 :            : #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
     183                 :            : #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
     184                 :            : #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
     185                 :            : 
     186                 :            : /* Data dependence type.  */
     187                 :            : 
     188                 :            : enum rdg_dep_type
     189                 :            : {
     190                 :            :   /* Read After Write (RAW).  */
     191                 :            :   flow_dd = 'f',
     192                 :            : 
     193                 :            :   /* Control dependence (execute conditional on).  */
     194                 :            :   control_dd = 'c'
     195                 :            : };
     196                 :            : 
     197                 :            : /* Dependence information attached to an edge of the RDG.  */
     198                 :            : 
     199                 :            : struct rdg_edge
     200                 :            : {
     201                 :            :   /* Type of the dependence.  */
     202                 :            :   enum rdg_dep_type type;
     203                 :            : };
     204                 :            : 
     205                 :            : #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
     206                 :            : 
     207                 :            : /* Kind of distributed loop.  */
     208                 :            : enum partition_kind {
     209                 :            :     PKIND_NORMAL,
     210                 :            :     /* Partial memset stands for a paritition can be distributed into a loop
     211                 :            :        of memset calls, rather than a single memset call.  It's handled just
     212                 :            :        like a normal parition, i.e, distributed as separate loop, no memset
     213                 :            :        call is generated.
     214                 :            : 
     215                 :            :        Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
     216                 :            :        loop nest as deep as possible.  As a result, parloop achieves better
     217                 :            :        parallelization by parallelizing deeper loop nest.  This hack should
     218                 :            :        be unnecessary and removed once distributed memset can be understood
     219                 :            :        and analyzed in data reference analysis.  See PR82604 for more.  */
     220                 :            :     PKIND_PARTIAL_MEMSET,
     221                 :            :     PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
     222                 :            : };
     223                 :            : 
     224                 :            : /* Type of distributed loop.  */
     225                 :            : enum partition_type {
     226                 :            :     /* The distributed loop can be executed parallelly.  */
     227                 :            :     PTYPE_PARALLEL = 0,
     228                 :            :     /* The distributed loop has to be executed sequentially.  */
     229                 :            :     PTYPE_SEQUENTIAL
     230                 :            : };
     231                 :            : 
     232                 :            : /* Builtin info for loop distribution.  */
     233                 :            : struct builtin_info
     234                 :            : {
     235                 :            :   /* data-references a kind != PKIND_NORMAL partition is about.  */
     236                 :            :   data_reference_p dst_dr;
     237                 :            :   data_reference_p src_dr;
     238                 :            :   /* Base address and size of memory objects operated by the builtin.  Note
     239                 :            :      both dest and source memory objects must have the same size.  */
     240                 :            :   tree dst_base;
     241                 :            :   tree src_base;
     242                 :            :   tree size;
     243                 :            :   /* Base and offset part of dst_base after stripping constant offset.  This
     244                 :            :      is only used in memset builtin distribution for now.  */
     245                 :            :   tree dst_base_base;
     246                 :            :   unsigned HOST_WIDE_INT dst_base_offset;
     247                 :            : };
     248                 :            : 
     249                 :            : /* Partition for loop distribution.  */
     250                 :            : struct partition
     251                 :            : {
     252                 :            :   /* Statements of the partition.  */
     253                 :            :   bitmap stmts;
     254                 :            :   /* True if the partition defines variable which is used outside of loop.  */
     255                 :            :   bool reduction_p;
     256                 :            :   location_t loc;
     257                 :            :   enum partition_kind kind;
     258                 :            :   enum partition_type type;
     259                 :            :   /* Data references in the partition.  */
     260                 :            :   bitmap datarefs;
     261                 :            :   /* Information of builtin parition.  */
     262                 :            :   struct builtin_info *builtin;
     263                 :            : };
     264                 :            : 
     265                 :            : /* Partitions are fused because of different reasons.  */
     266                 :            : enum fuse_type
     267                 :            : {
     268                 :            :   FUSE_NON_BUILTIN = 0,
     269                 :            :   FUSE_REDUCTION = 1,
     270                 :            :   FUSE_SHARE_REF = 2,
     271                 :            :   FUSE_SAME_SCC = 3,
     272                 :            :   FUSE_FINALIZE = 4
     273                 :            : };
     274                 :            : 
     275                 :            : /* Description on different fusing reason.  */
     276                 :            : static const char *fuse_message[] = {
     277                 :            :   "they are non-builtins",
     278                 :            :   "they have reductions",
     279                 :            :   "they have shared memory refs",
     280                 :            :   "they are in the same dependence scc",
     281                 :            :   "there is no point to distribute loop"};
     282                 :            : 
     283                 :            : 
     284                 :            : /* Dump vertex I in RDG to FILE.  */
     285                 :            : 
     286                 :            : static void
     287                 :        849 : dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
     288                 :            : {
     289                 :        849 :   struct vertex *v = &(rdg->vertices[i]);
     290                 :        849 :   struct graph_edge *e;
     291                 :            : 
     292                 :        849 :   fprintf (file, "(vertex %d: (%s%s) (in:", i,
     293                 :        849 :            RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
     294                 :        849 :            RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
     295                 :            : 
     296                 :        849 :   if (v->pred)
     297                 :       2842 :     for (e = v->pred; e; e = e->pred_next)
     298                 :       1993 :       fprintf (file, " %d", e->src);
     299                 :            : 
     300                 :        849 :   fprintf (file, ") (out:");
     301                 :            : 
     302                 :        849 :   if (v->succ)
     303                 :       2699 :     for (e = v->succ; e; e = e->succ_next)
     304                 :       1993 :       fprintf (file, " %d", e->dest);
     305                 :            : 
     306                 :        849 :   fprintf (file, ")\n");
     307                 :        849 :   print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
     308                 :        849 :   fprintf (file, ")\n");
     309                 :        849 : }
     310                 :            : 
     311                 :            : /* Call dump_rdg_vertex on stderr.  */
     312                 :            : 
     313                 :            : DEBUG_FUNCTION void
     314                 :          0 : debug_rdg_vertex (struct graph *rdg, int i)
     315                 :            : {
     316                 :          0 :   dump_rdg_vertex (stderr, rdg, i);
     317                 :          0 : }
     318                 :            : 
     319                 :            : /* Dump the reduced dependence graph RDG to FILE.  */
     320                 :            : 
     321                 :            : static void
     322                 :         65 : dump_rdg (FILE *file, struct graph *rdg)
     323                 :            : {
     324                 :         65 :   fprintf (file, "(rdg\n");
     325                 :        914 :   for (int i = 0; i < rdg->n_vertices; i++)
     326                 :        849 :     dump_rdg_vertex (file, rdg, i);
     327                 :         65 :   fprintf (file, ")\n");
     328                 :         65 : }
     329                 :            : 
     330                 :            : /* Call dump_rdg on stderr.  */
     331                 :            : 
     332                 :            : DEBUG_FUNCTION void
     333                 :          0 : debug_rdg (struct graph *rdg)
     334                 :            : {
     335                 :          0 :   dump_rdg (stderr, rdg);
     336                 :          0 : }
     337                 :            : 
     338                 :            : static void
     339                 :          0 : dot_rdg_1 (FILE *file, struct graph *rdg)
     340                 :            : {
     341                 :          0 :   int i;
     342                 :          0 :   pretty_printer buffer;
     343                 :          0 :   pp_needs_newline (&buffer) = false;
     344                 :          0 :   buffer.buffer->stream = file;
     345                 :            : 
     346                 :          0 :   fprintf (file, "digraph RDG {\n");
     347                 :            : 
     348                 :          0 :   for (i = 0; i < rdg->n_vertices; i++)
     349                 :            :     {
     350                 :          0 :       struct vertex *v = &(rdg->vertices[i]);
     351                 :          0 :       struct graph_edge *e;
     352                 :            : 
     353                 :          0 :       fprintf (file, "%d [label=\"[%d] ", i, i);
     354                 :          0 :       pp_gimple_stmt_1 (&buffer, RDGV_STMT (v), 0, TDF_SLIM);
     355                 :          0 :       pp_flush (&buffer);
     356                 :          0 :       fprintf (file, "\"]\n");
     357                 :            : 
     358                 :            :       /* Highlight reads from memory.  */
     359                 :          0 :       if (RDG_MEM_READS_STMT (rdg, i))
     360                 :          0 :        fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
     361                 :            : 
     362                 :            :       /* Highlight stores to memory.  */
     363                 :          0 :       if (RDG_MEM_WRITE_STMT (rdg, i))
     364                 :          0 :        fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
     365                 :            : 
     366                 :          0 :       if (v->succ)
     367                 :          0 :        for (e = v->succ; e; e = e->succ_next)
     368                 :          0 :          switch (RDGE_TYPE (e))
     369                 :            :            {
     370                 :          0 :            case flow_dd:
     371                 :            :              /* These are the most common dependences: don't print these. */
     372                 :          0 :              fprintf (file, "%d -> %d \n", i, e->dest);
     373                 :          0 :              break;
     374                 :            : 
     375                 :          0 :            case control_dd:
     376                 :          0 :              fprintf (file, "%d -> %d [label=control] \n", i, e->dest);
     377                 :          0 :              break;
     378                 :            : 
     379                 :          0 :            default:
     380                 :          0 :              gcc_unreachable ();
     381                 :            :            }
     382                 :            :     }
     383                 :            : 
     384                 :          0 :   fprintf (file, "}\n\n");
     385                 :          0 : }
     386                 :            : 
     387                 :            : /* Display the Reduced Dependence Graph using dotty.  */
     388                 :            : 
     389                 :            : DEBUG_FUNCTION void
     390                 :          0 : dot_rdg (struct graph *rdg)
     391                 :            : {
     392                 :            :   /* When debugging, you may want to enable the following code.  */
     393                 :            : #ifdef HAVE_POPEN
     394                 :          0 :   FILE *file = popen ("dot -Tx11", "w");
     395                 :          0 :   if (!file)
     396                 :            :     return;
     397                 :          0 :   dot_rdg_1 (file, rdg);
     398                 :          0 :   fflush (file);
     399                 :          0 :   close (fileno (file));
     400                 :          0 :   pclose (file);
     401                 :            : #else
     402                 :            :   dot_rdg_1 (stderr, rdg);
     403                 :            : #endif
     404                 :            : }
     405                 :            : 
     406                 :            : /* Returns the index of STMT in RDG.  */
     407                 :            : 
     408                 :            : static int
     409                 :    7483300 : rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple *stmt)
     410                 :            : {
     411                 :    7483300 :   int index = gimple_uid (stmt);
     412                 :    7483300 :   gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
     413                 :    7483300 :   return index;
     414                 :            : }
     415                 :            : 
     416                 :            : /* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
     417                 :            :    the index of DEF in RDG.  */
     418                 :            : 
     419                 :            : static void
     420                 :    1245990 : create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
     421                 :            : {
     422                 :    1245990 :   use_operand_p imm_use_p;
     423                 :    1245990 :   imm_use_iterator iterator;
     424                 :            : 
     425                 :    3401330 :   FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
     426                 :            :     {
     427                 :    2155340 :       struct graph_edge *e;
     428                 :    2155340 :       int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
     429                 :            : 
     430                 :    2155340 :       if (use < 0)
     431                 :     323086 :         continue;
     432                 :            : 
     433                 :    1832260 :       e = add_edge (rdg, idef, use);
     434                 :    1832260 :       e->data = XNEW (struct rdg_edge);
     435                 :    1832260 :       RDGE_TYPE (e) = flow_dd;
     436                 :            :     }
     437                 :    1245990 : }
     438                 :            : 
     439                 :            : /* Creates an edge for the control dependences of BB to the vertex V.  */
     440                 :            : 
     441                 :            : static void
     442                 :    1602970 : create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
     443                 :            :                                     int v, control_dependences *cd)
     444                 :            : {
     445                 :    1602970 :   bitmap_iterator bi;
     446                 :    1602970 :   unsigned edge_n;
     447                 :    4239520 :   EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
     448                 :            :                             0, edge_n, bi)
     449                 :            :     {
     450                 :    2636550 :       basic_block cond_bb = cd->get_edge_src (edge_n);
     451                 :    2636550 :       gimple *stmt = last_stmt (cond_bb);
     452                 :    2636550 :       if (stmt && is_ctrl_stmt (stmt))
     453                 :            :         {
     454                 :    2630870 :           struct graph_edge *e;
     455                 :    2630870 :           int c = rdg_vertex_for_stmt (rdg, stmt);
     456                 :    2630870 :           if (c < 0)
     457                 :     828282 :             continue;
     458                 :            : 
     459                 :    1802590 :           e = add_edge (rdg, c, v);
     460                 :    1802590 :           e->data = XNEW (struct rdg_edge);
     461                 :    1802590 :           RDGE_TYPE (e) = control_dd;
     462                 :            :         }
     463                 :            :     }
     464                 :    1602970 : }
     465                 :            : 
     466                 :            : /* Creates the edges of the reduced dependence graph RDG.  */
     467                 :            : 
     468                 :            : static void
     469                 :      91814 : create_rdg_flow_edges (struct graph *rdg)
     470                 :            : {
     471                 :      91814 :   int i;
     472                 :      91814 :   def_operand_p def_p;
     473                 :      91814 :   ssa_op_iter iter;
     474                 :            : 
     475                 :    1608990 :   for (i = 0; i < rdg->n_vertices; i++)
     476                 :    4280340 :     FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
     477                 :            :                               iter, SSA_OP_DEF)
     478                 :    1245990 :       create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
     479                 :      91814 : }
     480                 :            : 
     481                 :            : /* Creates the edges of the reduced dependence graph RDG.  */
     482                 :            : 
     483                 :            : static void
     484                 :      91814 : create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop)
     485                 :            : {
     486                 :      91814 :   int i;
     487                 :            : 
     488                 :    1608990 :   for (i = 0; i < rdg->n_vertices; i++)
     489                 :            :     {
     490                 :    1517170 :       gimple *stmt = RDG_STMT (rdg, i);
     491                 :    1517170 :       if (gimple_code (stmt) == GIMPLE_PHI)
     492                 :            :         {
     493                 :     299719 :           edge_iterator ei;
     494                 :     299719 :           edge e;
     495                 :     897715 :           FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
     496                 :     597996 :             if (flow_bb_inside_loop_p (loop, e->src))
     497                 :     385516 :               create_edge_for_control_dependence (rdg, e->src, i, cd);
     498                 :            :         }
     499                 :            :       else
     500                 :    1217460 :         create_edge_for_control_dependence (rdg, gimple_bb (stmt), i, cd);
     501                 :            :     }
     502                 :      91814 : }
     503                 :            : 
     504                 :            : 
     505                 :            : class loop_distribution
     506                 :            : {
     507                 :            :   private:
     508                 :            :   /* The loop (nest) to be distributed.  */
     509                 :            :   vec<loop_p> loop_nest;
     510                 :            : 
     511                 :            :   /* Vector of data references in the loop to be distributed.  */
     512                 :            :   vec<data_reference_p> datarefs_vec;
     513                 :            : 
     514                 :            :   /* If there is nonaddressable data reference in above vector.  */
     515                 :            :   bool has_nonaddressable_dataref_p;
     516                 :            : 
     517                 :            :   /* Store index of data reference in aux field.  */
     518                 :            : 
     519                 :            :   /* Hash table for data dependence relation in the loop to be distributed.  */
     520                 :            :   hash_table<ddr_hasher> *ddrs_table;
     521                 :            : 
     522                 :            :   /* Array mapping basic block's index to its topological order.  */
     523                 :            :   int *bb_top_order_index;
     524                 :            :   /* And size of the array.  */
     525                 :            :   int bb_top_order_index_size;
     526                 :            : 
     527                 :            :   /* Build the vertices of the reduced dependence graph RDG.  Return false
     528                 :            :      if that failed.  */
     529                 :            :   bool create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop);
     530                 :            : 
     531                 :            :   /* Initialize STMTS with all the statements of LOOP.  We use topological
     532                 :            :      order to discover all statements.  The order is important because
     533                 :            :      generate_loops_for_partition is using the same traversal for identifying
     534                 :            :      statements in loop copies.  */
     535                 :            :   void stmts_from_loop (class loop *loop, vec<gimple *> *stmts);
     536                 :            : 
     537                 :            : 
     538                 :            :   /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
     539                 :            :      LOOP, and one edge per flow dependence or control dependence from control
     540                 :            :      dependence CD.  During visiting each statement, data references are also
     541                 :            :      collected and recorded in global data DATAREFS_VEC.  */
     542                 :            :   struct graph * build_rdg (class loop *loop, control_dependences *cd);
     543                 :            : 
     544                 :            : /* Merge PARTITION into the partition DEST.  RDG is the reduced dependence
     545                 :            :    graph and we update type for result partition if it is non-NULL.  */
     546                 :            :   void partition_merge_into (struct graph *rdg,
     547                 :            :                              partition *dest, partition *partition,
     548                 :            :                              enum fuse_type ft);
     549                 :            : 
     550                 :            : 
     551                 :            :   /* Return data dependence relation for data references A and B.  The two
     552                 :            :      data references must be in lexicographic order wrto reduced dependence
     553                 :            :      graph RDG.  We firstly try to find ddr from global ddr hash table.  If
     554                 :            :      it doesn't exist, compute the ddr and cache it.  */
     555                 :            :   data_dependence_relation * get_data_dependence (struct graph *rdg,
     556                 :            :                                                   data_reference_p a,
     557                 :            :                                                   data_reference_p b);
     558                 :            : 
     559                 :            : 
     560                 :            :   /* In reduced dependence graph RDG for loop distribution, return true if
     561                 :            :      dependence between references DR1 and DR2 leads to a dependence cycle
     562                 :            :      and such dependence cycle can't be resolved by runtime alias check.  */
     563                 :            :   bool data_dep_in_cycle_p (struct graph *rdg, data_reference_p dr1,
     564                 :            :                             data_reference_p dr2);
     565                 :            : 
     566                 :            : 
     567                 :            :   /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
     568                 :            :      PARTITION1's type after merging PARTITION2 into PARTITION1.  */
     569                 :            :   void update_type_for_merge (struct graph *rdg,
     570                 :            :                               partition *partition1, partition *partition2);
     571                 :            : 
     572                 :            : 
     573                 :            :   /* Returns a partition with all the statements needed for computing
     574                 :            :      the vertex V of the RDG, also including the loop exit conditions.  */
     575                 :            :   partition *build_rdg_partition_for_vertex (struct graph *rdg, int v);
     576                 :            : 
     577                 :            :   /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
     578                 :            :      if it forms builtin memcpy or memmove call.  */
     579                 :            :   void classify_builtin_ldst (loop_p loop, struct graph *rdg, partition *partition,
     580                 :            :                               data_reference_p dst_dr, data_reference_p src_dr);
     581                 :            : 
     582                 :            :   /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
     583                 :            :      For the moment we detect memset, memcpy and memmove patterns.  Bitmap
     584                 :            :      STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions.
     585                 :            :      Returns true if there is a reduction in all partitions and we
     586                 :            :      possibly did not mark PARTITION as having one for this reason.  */
     587                 :            : 
     588                 :            :   bool
     589                 :            :   classify_partition (loop_p loop,
     590                 :            :                       struct graph *rdg, partition *partition,
     591                 :            :                       bitmap stmt_in_all_partitions);
     592                 :            : 
     593                 :            : 
     594                 :            :   /* Returns true when PARTITION1 and PARTITION2 access the same memory
     595                 :            :      object in RDG.  */
     596                 :            :   bool share_memory_accesses (struct graph *rdg,
     597                 :            :                               partition *partition1, partition *partition2);
     598                 :            : 
     599                 :            :   /* For each seed statement in STARTING_STMTS, this function builds
     600                 :            :      partition for it by adding depended statements according to RDG.
     601                 :            :      All partitions are recorded in PARTITIONS.  */
     602                 :            :   void rdg_build_partitions (struct graph *rdg,
     603                 :            :                              vec<gimple *> starting_stmts,
     604                 :            :                              vec<partition *> *partitions);
     605                 :            : 
     606                 :            :   /* Compute partition dependence created by the data references in DRS1
     607                 :            :      and DRS2, modify and return DIR according to that.  IF ALIAS_DDR is
     608                 :            :      not NULL, we record dependence introduced by possible alias between
     609                 :            :      two data references in ALIAS_DDRS; otherwise, we simply ignore such
     610                 :            :      dependence as if it doesn't exist at all.  */
     611                 :            :   int pg_add_dependence_edges (struct graph *rdg, int dir, bitmap drs1,
     612                 :            :                                bitmap drs2, vec<ddr_p> *alias_ddrs);
     613                 :            : 
     614                 :            : 
     615                 :            :   /* Build and return partition dependence graph for PARTITIONS.  RDG is
     616                 :            :      reduced dependence graph for the loop to be distributed.  If IGNORE_ALIAS_P
     617                 :            :      is true, data dependence caused by possible alias between references
     618                 :            :      is ignored, as if it doesn't exist at all; otherwise all depdendences
     619                 :            :      are considered.  */
     620                 :            :   struct graph *build_partition_graph (struct graph *rdg,
     621                 :            :                                        vec<struct partition *> *partitions,
     622                 :            :                                        bool ignore_alias_p);
     623                 :            : 
     624                 :            :   /* Given reduced dependence graph RDG merge strong connected components
     625                 :            :      of PARTITIONS.  If IGNORE_ALIAS_P is true, data dependence caused by
     626                 :            :      possible alias between references is ignored, as if it doesn't exist
     627                 :            :      at all; otherwise all depdendences are considered.  */
     628                 :            :   void merge_dep_scc_partitions (struct graph *rdg, vec<struct partition *>
     629                 :            :                                  *partitions, bool ignore_alias_p);
     630                 :            : 
     631                 :            : /* This is the main function breaking strong conected components in
     632                 :            :    PARTITIONS giving reduced depdendence graph RDG.  Store data dependence
     633                 :            :    relations for runtime alias check in ALIAS_DDRS.  */
     634                 :            :   void break_alias_scc_partitions (struct graph *rdg, vec<struct partition *>
     635                 :            :                                    *partitions, vec<ddr_p> *alias_ddrs);
     636                 :            : 
     637                 :            : 
     638                 :            :   /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
     639                 :            :      ALIAS_DDRS contains ddrs which need runtime alias check.  */
     640                 :            :   void finalize_partitions (class loop *loop, vec<struct partition *>
     641                 :            :                             *partitions, vec<ddr_p> *alias_ddrs);
     642                 :            : 
     643                 :            :   /* Distributes the code from LOOP in such a way that producer statements
     644                 :            :      are placed before consumer statements.  Tries to separate only the
     645                 :            :      statements from STMTS into separate loops.  Returns the number of
     646                 :            :      distributed loops.  Set NB_CALLS to number of generated builtin calls.
     647                 :            :      Set *DESTROY_P to whether LOOP needs to be destroyed.  */
     648                 :            :   int distribute_loop (class loop *loop, vec<gimple *> stmts,
     649                 :            :                        control_dependences *cd, int *nb_calls, bool *destroy_p,
     650                 :            :                        bool only_patterns_p);
     651                 :            : 
     652                 :            :   /* Compute topological order for basic blocks.  Topological order is
     653                 :            :      needed because data dependence is computed for data references in
     654                 :            :      lexicographical order.  */
     655                 :            :   void bb_top_order_init (void);
     656                 :            : 
     657                 :            :   void bb_top_order_destroy (void);
     658                 :            : 
     659                 :            :   public:
     660                 :            : 
     661                 :            :   /* Getter for bb_top_order.  */
     662                 :            : 
     663                 :    1924830 :   inline int get_bb_top_order_index_size (void)
     664                 :            :     {
     665                 :    1924830 :       return bb_top_order_index_size;
     666                 :            :     }
     667                 :            : 
     668                 :    3849670 :   inline int get_bb_top_order_index (int i)
     669                 :            :     {
     670                 :    3849670 :       return bb_top_order_index[i];
     671                 :            :     }
     672                 :            : 
     673                 :            :   unsigned int execute (function *fun);
     674                 :            : };
     675                 :            : 
     676                 :            : 
     677                 :            : /* If X has a smaller topological sort number than Y, returns -1;
     678                 :            :    if greater, returns 1.  */
     679                 :            : static int
     680                 :    1924830 : bb_top_order_cmp_r (const void *x, const void *y, void *loop)
     681                 :            : {
     682                 :    1924830 :   loop_distribution *_loop =
     683                 :            :     (loop_distribution *) loop;
     684                 :            : 
     685                 :    1924830 :   basic_block bb1 = *(const basic_block *) x;
     686                 :    1924830 :   basic_block bb2 = *(const basic_block *) y;
     687                 :            : 
     688                 :    1924830 :   int bb_top_order_index_size = _loop->get_bb_top_order_index_size ();
     689                 :            : 
     690                 :    1924830 :   gcc_assert (bb1->index < bb_top_order_index_size
     691                 :            :               && bb2->index < bb_top_order_index_size);
     692                 :    1924830 :   gcc_assert (bb1 == bb2
     693                 :            :               || _loop->get_bb_top_order_index(bb1->index)
     694                 :            :                  != _loop->get_bb_top_order_index(bb2->index));
     695                 :            : 
     696                 :    1924830 :   return (_loop->get_bb_top_order_index(bb1->index) - 
     697                 :    1924830 :           _loop->get_bb_top_order_index(bb2->index));
     698                 :            : }
     699                 :            : 
     700                 :            : bool
     701                 :      92477 : loop_distribution::create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts,
     702                 :            :                                         loop_p loop)
     703                 :            : {
     704                 :      92477 :   int i;
     705                 :      92477 :   gimple *stmt;
     706                 :            : 
     707                 :    1618440 :   FOR_EACH_VEC_ELT (stmts, i, stmt)
     708                 :            :     {
     709                 :    1526630 :       struct vertex *v = &(rdg->vertices[i]);
     710                 :            : 
     711                 :            :       /* Record statement to vertex mapping.  */
     712                 :    1526630 :       gimple_set_uid (stmt, i);
     713                 :            : 
     714                 :    1526630 :       v->data = XNEW (struct rdg_vertex);
     715                 :    1526630 :       RDGV_STMT (v) = stmt;
     716                 :    1526630 :       RDGV_DATAREFS (v).create (0);
     717                 :    1526630 :       RDGV_HAS_MEM_WRITE (v) = false;
     718                 :    1526630 :       RDGV_HAS_MEM_READS (v) = false;
     719                 :    1526630 :       if (gimple_code (stmt) == GIMPLE_PHI)
     720                 :     301595 :         continue;
     721                 :            : 
     722                 :    1225040 :       unsigned drp = datarefs_vec.length ();
     723                 :    1225040 :       if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec))
     724                 :            :         return false;
     725                 :    3022520 :       for (unsigned j = drp; j < datarefs_vec.length (); ++j)
     726                 :            :         {
     727                 :     286886 :           data_reference_p dr = datarefs_vec[j];
     728                 :     286886 :           if (DR_IS_READ (dr))
     729                 :     154677 :             RDGV_HAS_MEM_READS (v) = true;
     730                 :            :           else
     731                 :     132209 :             RDGV_HAS_MEM_WRITE (v) = true;
     732                 :     286886 :           RDGV_DATAREFS (v).safe_push (dr);
     733                 :     286886 :           has_nonaddressable_dataref_p |= may_be_nonaddressable_p (dr->ref);
     734                 :            :         }
     735                 :            :     }
     736                 :            :   return true;
     737                 :            : }
     738                 :            : 
     739                 :            : void
     740                 :      92477 : loop_distribution::stmts_from_loop (class loop *loop, vec<gimple *> *stmts)
     741                 :            : {
     742                 :      92477 :   unsigned int i;
     743                 :      92477 :   basic_block *bbs = get_loop_body_in_custom_order (loop, this, bb_top_order_cmp_r);
     744                 :            : 
     745                 :     396480 :   for (i = 0; i < loop->num_nodes; i++)
     746                 :            :     {
     747                 :     304003 :       basic_block bb = bbs[i];
     748                 :            : 
     749                 :     698440 :       for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
     750                 :     394437 :            gsi_next (&bsi))
     751                 :     788874 :         if (!virtual_operand_p (gimple_phi_result (bsi.phi ())))
     752                 :     302304 :           stmts->safe_push (bsi.phi ());
     753                 :            : 
     754                 :    2721420 :       for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
     755                 :    2113420 :            gsi_next (&bsi))
     756                 :            :         {
     757                 :    2113420 :           gimple *stmt = gsi_stmt (bsi);
     758                 :    2113420 :           if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
     759                 :    1233820 :             stmts->safe_push (stmt);
     760                 :            :         }
     761                 :            :     }
     762                 :            : 
     763                 :      92477 :   free (bbs);
     764                 :      92477 : }
     765                 :            : 
     766                 :            : /* Free the reduced dependence graph RDG.  */
     767                 :            : 
     768                 :            : static void
     769                 :      92477 : free_rdg (struct graph *rdg)
     770                 :            : {
     771                 :      92477 :   int i;
     772                 :            : 
     773                 :    1628600 :   for (i = 0; i < rdg->n_vertices; i++)
     774                 :            :     {
     775                 :    1536130 :       struct vertex *v = &(rdg->vertices[i]);
     776                 :    1536130 :       struct graph_edge *e;
     777                 :            : 
     778                 :    5170980 :       for (e = v->succ; e; e = e->succ_next)
     779                 :    3634850 :         free (e->data);
     780                 :            : 
     781                 :    1536130 :       if (v->data)
     782                 :            :         {
     783                 :    1526630 :           gimple_set_uid (RDGV_STMT (v), -1);
     784                 :    1526630 :           (RDGV_DATAREFS (v)).release ();
     785                 :    1526630 :           free (v->data);
     786                 :            :         }
     787                 :            :     }
     788                 :            : 
     789                 :      92477 :   free_graph (rdg);
     790                 :      92477 : }
     791                 :            : 
     792                 :            : struct graph *
     793                 :      92477 : loop_distribution::build_rdg (class loop *loop, control_dependences *cd)
     794                 :            : {
     795                 :      92477 :   struct graph *rdg;
     796                 :            : 
     797                 :            :   /* Create the RDG vertices from the stmts of the loop nest.  */
     798                 :      92477 :   auto_vec<gimple *, 10> stmts;
     799                 :      92477 :   stmts_from_loop (loop, &stmts);
     800                 :     184954 :   rdg = new_graph (stmts.length ());
     801                 :      92477 :   if (!create_rdg_vertices (rdg, stmts, loop))
     802                 :            :     {
     803                 :        663 :       free_rdg (rdg);
     804                 :        663 :       return NULL;
     805                 :            :     }
     806                 :      91814 :   stmts.release ();
     807                 :            : 
     808                 :      91814 :   create_rdg_flow_edges (rdg);
     809                 :      91814 :   if (cd)
     810                 :      91814 :     create_rdg_cd_edges (rdg, cd, loop);
     811                 :            : 
     812                 :            :   return rdg;
     813                 :            : }
     814                 :            : 
     815                 :            : 
     816                 :            : /* Allocate and initialize a partition from BITMAP.  */
     817                 :            : 
     818                 :            : static partition *
     819                 :     164175 : partition_alloc (void)
     820                 :            : {
     821                 :     164175 :   partition *partition = XCNEW (struct partition);
     822                 :     164175 :   partition->stmts = BITMAP_ALLOC (NULL);
     823                 :     164175 :   partition->reduction_p = false;
     824                 :     164175 :   partition->loc = UNKNOWN_LOCATION;
     825                 :     164175 :   partition->kind = PKIND_NORMAL;
     826                 :     164175 :   partition->type = PTYPE_PARALLEL;
     827                 :     164175 :   partition->datarefs = BITMAP_ALLOC (NULL);
     828                 :     164175 :   return partition;
     829                 :            : }
     830                 :            : 
     831                 :            : /* Free PARTITION.  */
     832                 :            : 
     833                 :            : static void
     834                 :     164175 : partition_free (partition *partition)
     835                 :            : {
     836                 :     164175 :   BITMAP_FREE (partition->stmts);
     837                 :     164175 :   BITMAP_FREE (partition->datarefs);
     838                 :     164175 :   if (partition->builtin)
     839                 :       9333 :     free (partition->builtin);
     840                 :            : 
     841                 :     164175 :   free (partition);
     842                 :     164175 : }
     843                 :            : 
     844                 :            : /* Returns true if the partition can be generated as a builtin.  */
     845                 :            : 
     846                 :            : static bool
     847                 :     264647 : partition_builtin_p (partition *partition)
     848                 :            : {
     849                 :          0 :   return partition->kind > PKIND_PARTIAL_MEMSET;
     850                 :            : }
     851                 :            : 
     852                 :            : /* Returns true if the partition contains a reduction.  */
     853                 :            : 
     854                 :            : static bool
     855                 :     565215 : partition_reduction_p (partition *partition)
     856                 :            : {
     857                 :     565215 :   return partition->reduction_p;
     858                 :            : }
     859                 :            : 
     860                 :            : void
     861                 :      17015 : loop_distribution::partition_merge_into (struct graph *rdg,
     862                 :            :                       partition *dest, partition *partition, enum fuse_type ft)
     863                 :            : {
     864                 :      17015 :   if (dump_file && (dump_flags & TDF_DETAILS))
     865                 :            :     {
     866                 :         41 :       fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]);
     867                 :         41 :       fprintf (dump_file, "  Part 1: ");
     868                 :         41 :       dump_bitmap (dump_file, dest->stmts);
     869                 :         41 :       fprintf (dump_file, "  Part 2: ");
     870                 :         41 :       dump_bitmap (dump_file, partition->stmts);
     871                 :            :     }
     872                 :            : 
     873                 :      17015 :   dest->kind = PKIND_NORMAL;
     874                 :      17015 :   if (dest->type == PTYPE_PARALLEL)
     875                 :      12863 :     dest->type = partition->type;
     876                 :            : 
     877                 :      17015 :   bitmap_ior_into (dest->stmts, partition->stmts);
     878                 :      17015 :   if (partition_reduction_p (partition))
     879                 :       1945 :     dest->reduction_p = true;
     880                 :            : 
     881                 :            :   /* Further check if any data dependence prevents us from executing the
     882                 :            :      new partition parallelly.  */
     883                 :      17015 :   if (dest->type == PTYPE_PARALLEL && rdg != NULL)
     884                 :       4235 :     update_type_for_merge (rdg, dest, partition);
     885                 :            : 
     886                 :      17015 :   bitmap_ior_into (dest->datarefs, partition->datarefs);
     887                 :      17015 : }
     888                 :            : 
     889                 :            : 
     890                 :            : /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
     891                 :            :    the LOOP.  */
     892                 :            : 
     893                 :            : static bool
     894                 :    3347730 : ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
     895                 :            : {
     896                 :    3347730 :   imm_use_iterator imm_iter;
     897                 :    3347730 :   use_operand_p use_p;
     898                 :            : 
     899                 :   10287500 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
     900                 :            :     {
     901                 :    7024920 :       if (is_gimple_debug (USE_STMT (use_p)))
     902                 :     790525 :         continue;
     903                 :            : 
     904                 :    6234400 :       basic_block use_bb = gimple_bb (USE_STMT (use_p));
     905                 :    6234400 :       if (!flow_bb_inside_loop_p (loop, use_bb))
     906                 :            :         return true;
     907                 :            :     }
     908                 :            : 
     909                 :            :   return false;
     910                 :            : }
     911                 :            : 
     912                 :            : /* Returns true when STMT defines a scalar variable used after the
     913                 :            :    loop LOOP.  */
     914                 :            : 
     915                 :            : static bool
     916                 :    5022290 : stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple *stmt)
     917                 :            : {
     918                 :    5022290 :   def_operand_p def_p;
     919                 :    5022290 :   ssa_op_iter op_iter;
     920                 :            : 
     921                 :    5022290 :   if (gimple_code (stmt) == GIMPLE_PHI)
     922                 :     794842 :     return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop);
     923                 :            : 
     924                 :    6729150 :   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
     925                 :    2552890 :     if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop))
     926                 :            :       return true;
     927                 :            : 
     928                 :            :   return false;
     929                 :            : }
     930                 :            : 
     931                 :            : /* Return a copy of LOOP placed before LOOP.  */
     932                 :            : 
     933                 :            : static class loop *
     934                 :        646 : copy_loop_before (class loop *loop)
     935                 :            : {
     936                 :        646 :   class loop *res;
     937                 :        646 :   edge preheader = loop_preheader_edge (loop);
     938                 :            : 
     939                 :        646 :   initialize_original_copy_tables ();
     940                 :        646 :   res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, NULL, preheader);
     941                 :        646 :   gcc_assert (res != NULL);
     942                 :        646 :   free_original_copy_tables ();
     943                 :        646 :   delete_update_ssa ();
     944                 :            : 
     945                 :        646 :   return res;
     946                 :            : }
     947                 :            : 
     948                 :            : /* Creates an empty basic block after LOOP.  */
     949                 :            : 
     950                 :            : static void
     951                 :        646 : create_bb_after_loop (class loop *loop)
     952                 :            : {
     953                 :        646 :   edge exit = single_exit (loop);
     954                 :            : 
     955                 :        646 :   if (!exit)
     956                 :            :     return;
     957                 :            : 
     958                 :        646 :   split_edge (exit);
     959                 :            : }
     960                 :            : 
     961                 :            : /* Generate code for PARTITION from the code in LOOP.  The loop is
     962                 :            :    copied when COPY_P is true.  All the statements not flagged in the
     963                 :            :    PARTITION bitmap are removed from the loop or from its copy.  The
     964                 :            :    statements are indexed in sequence inside a basic block, and the
     965                 :            :    basic blocks of a loop are taken in dom order.  */
     966                 :            : 
     967                 :            : static void
     968                 :       2063 : generate_loops_for_partition (class loop *loop, partition *partition,
     969                 :            :                               bool copy_p)
     970                 :            : {
     971                 :       2063 :   unsigned i;
     972                 :       2063 :   basic_block *bbs;
     973                 :            : 
     974                 :       2063 :   if (copy_p)
     975                 :            :     {
     976                 :        646 :       int orig_loop_num = loop->orig_loop_num;
     977                 :        646 :       loop = copy_loop_before (loop);
     978                 :        646 :       gcc_assert (loop != NULL);
     979                 :        646 :       loop->orig_loop_num = orig_loop_num;
     980                 :        646 :       create_preheader (loop, CP_SIMPLE_PREHEADERS);
     981                 :        646 :       create_bb_after_loop (loop);
     982                 :            :     }
     983                 :            :   else
     984                 :            :     {
     985                 :            :       /* Origin number is set to the new versioned loop's num.  */
     986                 :       1417 :       gcc_assert (loop->orig_loop_num != loop->num);
     987                 :            :     }
     988                 :            : 
     989                 :            :   /* Remove stmts not in the PARTITION bitmap.  */
     990                 :       2063 :   bbs = get_loop_body_in_dom_order (loop);
     991                 :            : 
     992                 :       2063 :   if (MAY_HAVE_DEBUG_BIND_STMTS)
     993                 :       4460 :     for (i = 0; i < loop->num_nodes; i++)
     994                 :            :       {
     995                 :       3145 :         basic_block bb = bbs[i];
     996                 :            : 
     997                 :       6837 :         for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
     998                 :       3692 :              gsi_next (&bsi))
     999                 :            :           {
    1000                 :       3692 :             gphi *phi = bsi.phi ();
    1001                 :       3692 :             if (!virtual_operand_p (gimple_phi_result (phi))
    1002                 :       3692 :                 && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
    1003                 :         18 :               reset_debug_uses (phi);
    1004                 :            :           }
    1005                 :            : 
    1006                 :      34465 :         for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1007                 :            :           {
    1008                 :      28175 :             gimple *stmt = gsi_stmt (bsi);
    1009                 :      28175 :             if (gimple_code (stmt) != GIMPLE_LABEL
    1010                 :      28175 :                 && !is_gimple_debug (stmt)
    1011                 :      43746 :                 && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
    1012                 :       3092 :               reset_debug_uses (stmt);
    1013                 :            :           }
    1014                 :            :       }
    1015                 :            : 
    1016                 :       6898 :   for (i = 0; i < loop->num_nodes; i++)
    1017                 :            :     {
    1018                 :       4835 :       basic_block bb = bbs[i];
    1019                 :       4835 :       edge inner_exit = NULL;
    1020                 :            : 
    1021                 :       4835 :       if (loop != bb->loop_father)
    1022                 :         79 :         inner_exit = single_exit (bb->loop_father);
    1023                 :            : 
    1024                 :      10558 :       for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
    1025                 :            :         {
    1026                 :       5723 :           gphi *phi = bsi.phi ();
    1027                 :       5723 :           if (!virtual_operand_p (gimple_phi_result (phi))
    1028                 :       5723 :               && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
    1029                 :         69 :             remove_phi_node (&bsi, true);
    1030                 :            :           else
    1031                 :       5654 :             gsi_next (&bsi);
    1032                 :            :         }
    1033                 :            : 
    1034                 :      46970 :       for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
    1035                 :            :         {
    1036                 :      37300 :           gimple *stmt = gsi_stmt (bsi);
    1037                 :      37300 :           if (gimple_code (stmt) != GIMPLE_LABEL
    1038                 :      37300 :               && !is_gimple_debug (stmt)
    1039                 :      61996 :               && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
    1040                 :            :             {
    1041                 :            :               /* In distribution of loop nest, if bb is inner loop's exit_bb,
    1042                 :            :                  we choose its exit edge/path in order to avoid generating
    1043                 :            :                  infinite loop.  For all other cases, we choose an arbitrary
    1044                 :            :                  path through the empty CFG part that this unnecessary
    1045                 :            :                  control stmt controls.  */
    1046                 :       6040 :               if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
    1047                 :            :                 {
    1048                 :         17 :                   if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
    1049                 :          1 :                     gimple_cond_make_true (cond_stmt);
    1050                 :            :                   else
    1051                 :         16 :                     gimple_cond_make_false (cond_stmt);
    1052                 :         17 :                   update_stmt (stmt);
    1053                 :            :                 }
    1054                 :       6023 :               else if (gimple_code (stmt) == GIMPLE_SWITCH)
    1055                 :            :                 {
    1056                 :          0 :                   gswitch *switch_stmt = as_a <gswitch *> (stmt);
    1057                 :          0 :                   gimple_switch_set_index
    1058                 :          0 :                       (switch_stmt, CASE_LOW (gimple_switch_label (switch_stmt, 1)));
    1059                 :          0 :                   update_stmt (stmt);
    1060                 :            :                 }
    1061                 :            :               else
    1062                 :            :                 {
    1063                 :       6023 :                   unlink_stmt_vdef (stmt);
    1064                 :       6023 :                   gsi_remove (&bsi, true);
    1065                 :       6023 :                   release_defs (stmt);
    1066                 :       6023 :                   continue;
    1067                 :            :                 }
    1068                 :            :             }
    1069                 :      31277 :           gsi_next (&bsi);
    1070                 :            :         }
    1071                 :            :     }
    1072                 :            : 
    1073                 :       2063 :   free (bbs);
    1074                 :       2063 : }
    1075                 :            : 
    1076                 :            : /* If VAL memory representation contains the same value in all bytes,
    1077                 :            :    return that value, otherwise return -1.
    1078                 :            :    E.g. for 0x24242424 return 0x24, for IEEE double
    1079                 :            :    747708026454360457216.0 return 0x44, etc.  */
    1080                 :            : 
    1081                 :            : static int
    1082                 :      46666 : const_with_all_bytes_same (tree val)
    1083                 :            : {
    1084                 :      46666 :   unsigned char buf[64];
    1085                 :      46666 :   int i, len;
    1086                 :            : 
    1087                 :      46666 :   if (integer_zerop (val)
    1088                 :      46666 :       || (TREE_CODE (val) == CONSTRUCTOR
    1089                 :        287 :           && !TREE_CLOBBER_P (val)
    1090                 :        287 :           && CONSTRUCTOR_NELTS (val) == 0))
    1091                 :            :     return 0;
    1092                 :            : 
    1093                 :      32646 :   if (real_zerop (val))
    1094                 :            :     {
    1095                 :            :       /* Only return 0 for +0.0, not for -0.0, which doesn't have
    1096                 :            :          an all bytes same memory representation.  Don't transform
    1097                 :            :          -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS.  */
    1098                 :       3341 :       switch (TREE_CODE (val))
    1099                 :            :         {
    1100                 :       2976 :         case REAL_CST:
    1101                 :       2976 :           if (!real_isneg (TREE_REAL_CST_PTR (val)))
    1102                 :            :             return 0;
    1103                 :            :           break;
    1104                 :        358 :         case COMPLEX_CST:
    1105                 :        358 :           if (!const_with_all_bytes_same (TREE_REALPART (val))
    1106                 :        716 :               && !const_with_all_bytes_same (TREE_IMAGPART (val)))
    1107                 :            :             return 0;
    1108                 :            :           break;
    1109                 :          7 :         case VECTOR_CST:
    1110                 :          7 :           {
    1111                 :          7 :             unsigned int count = vector_cst_encoded_nelts (val);
    1112                 :          7 :             unsigned int j;
    1113                 :         14 :             for (j = 0; j < count; ++j)
    1114                 :         14 :               if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val, j)))
    1115                 :            :                 break;
    1116                 :          7 :             if (j == count)
    1117                 :            :               return 0;
    1118                 :            :             break;
    1119                 :            :           }
    1120                 :            :         default:
    1121                 :            :           break;
    1122                 :            :         }
    1123                 :            :     }
    1124                 :            : 
    1125                 :      29326 :   if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
    1126                 :            :     return -1;
    1127                 :            : 
    1128                 :      29326 :   len = native_encode_expr (val, buf, sizeof (buf));
    1129                 :      29326 :   if (len == 0)
    1130                 :            :     return -1;
    1131                 :      22345 :   for (i = 1; i < len; i++)
    1132                 :      19870 :     if (buf[i] != buf[0])
    1133                 :            :       return -1;
    1134                 :       2475 :   return buf[0];
    1135                 :            : }
    1136                 :            : 
    1137                 :            : /* Generate a call to memset for PARTITION in LOOP.  */
    1138                 :            : 
    1139                 :            : static void
    1140                 :       6441 : generate_memset_builtin (class loop *loop, partition *partition)
    1141                 :            : {
    1142                 :       6441 :   gimple_stmt_iterator gsi;
    1143                 :       6441 :   tree mem, fn, nb_bytes;
    1144                 :       6441 :   tree val;
    1145                 :       6441 :   struct builtin_info *builtin = partition->builtin;
    1146                 :       6441 :   gimple *fn_call;
    1147                 :            : 
    1148                 :            :   /* The new statements will be placed before LOOP.  */
    1149                 :       6441 :   gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
    1150                 :            : 
    1151                 :       6441 :   nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
    1152                 :       6441 :   nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
    1153                 :            :                                        false, GSI_CONTINUE_LINKING);
    1154                 :       6441 :   mem = rewrite_to_non_trapping_overflow (builtin->dst_base);
    1155                 :       6441 :   mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
    1156                 :            :                                   false, GSI_CONTINUE_LINKING);
    1157                 :            : 
    1158                 :            :   /* This exactly matches the pattern recognition in classify_partition.  */
    1159                 :       6441 :   val = gimple_assign_rhs1 (DR_STMT (builtin->dst_dr));
    1160                 :            :   /* Handle constants like 0x15151515 and similarly
    1161                 :            :      floating point constants etc. where all bytes are the same.  */
    1162                 :       6441 :   int bytev = const_with_all_bytes_same (val);
    1163                 :       6441 :   if (bytev != -1)
    1164                 :       6342 :     val = build_int_cst (integer_type_node, bytev);
    1165                 :         99 :   else if (TREE_CODE (val) == INTEGER_CST)
    1166                 :          0 :     val = fold_convert (integer_type_node, val);
    1167                 :         99 :   else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
    1168                 :            :     {
    1169                 :         99 :       tree tem = make_ssa_name (integer_type_node);
    1170                 :         99 :       gimple *cstmt = gimple_build_assign (tem, NOP_EXPR, val);
    1171                 :         99 :       gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
    1172                 :         99 :       val = tem;
    1173                 :            :     }
    1174                 :            : 
    1175                 :      12882 :   fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
    1176                 :       6441 :   fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
    1177                 :       6441 :   gimple_set_location (fn_call, partition->loc);
    1178                 :       6441 :   gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
    1179                 :       6441 :   fold_stmt (&gsi);
    1180                 :            : 
    1181                 :       6441 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1182                 :            :     {
    1183                 :         37 :       fprintf (dump_file, "generated memset");
    1184                 :         37 :       if (bytev == 0)
    1185                 :         31 :         fprintf (dump_file, " zero\n");
    1186                 :            :       else
    1187                 :          6 :         fprintf (dump_file, "\n");
    1188                 :            :     }
    1189                 :       6441 : }
    1190                 :            : 
    1191                 :            : /* Generate a call to memcpy for PARTITION in LOOP.  */
    1192                 :            : 
    1193                 :            : static void
    1194                 :       2726 : generate_memcpy_builtin (class loop *loop, partition *partition)
    1195                 :            : {
    1196                 :       2726 :   gimple_stmt_iterator gsi;
    1197                 :       2726 :   gimple *fn_call;
    1198                 :       2726 :   tree dest, src, fn, nb_bytes;
    1199                 :       2726 :   enum built_in_function kind;
    1200                 :       2726 :   struct builtin_info *builtin = partition->builtin;
    1201                 :            : 
    1202                 :            :   /* The new statements will be placed before LOOP.  */
    1203                 :       2726 :   gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
    1204                 :            : 
    1205                 :       2726 :   nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
    1206                 :       2726 :   nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
    1207                 :            :                                        false, GSI_CONTINUE_LINKING);
    1208                 :       2726 :   dest = rewrite_to_non_trapping_overflow (builtin->dst_base);
    1209                 :       2726 :   src = rewrite_to_non_trapping_overflow (builtin->src_base);
    1210                 :       2726 :   if (partition->kind == PKIND_MEMCPY
    1211                 :       2726 :       || ! ptr_derefs_may_alias_p (dest, src))
    1212                 :            :     kind = BUILT_IN_MEMCPY;
    1213                 :            :   else
    1214                 :            :     kind = BUILT_IN_MEMMOVE;
    1215                 :            : 
    1216                 :       2726 :   dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
    1217                 :            :                                    false, GSI_CONTINUE_LINKING);
    1218                 :       2726 :   src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
    1219                 :            :                                   false, GSI_CONTINUE_LINKING);
    1220                 :       2726 :   fn = build_fold_addr_expr (builtin_decl_implicit (kind));
    1221                 :       2726 :   fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
    1222                 :       2726 :   gimple_set_location (fn_call, partition->loc);
    1223                 :       2726 :   gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
    1224                 :       2726 :   fold_stmt (&gsi);
    1225                 :            : 
    1226                 :       2726 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1227                 :            :     {
    1228                 :         15 :       if (kind == BUILT_IN_MEMCPY)
    1229                 :         12 :         fprintf (dump_file, "generated memcpy\n");
    1230                 :            :       else
    1231                 :          3 :         fprintf (dump_file, "generated memmove\n");
    1232                 :            :     }
    1233                 :       2726 : }
    1234                 :            : 
    1235                 :            : /* Remove and destroy the loop LOOP.  */
    1236                 :            : 
    1237                 :            : static void
    1238                 :       7497 : destroy_loop (class loop *loop)
    1239                 :            : {
    1240                 :       7497 :   unsigned nbbs = loop->num_nodes;
    1241                 :       7497 :   edge exit = single_exit (loop);
    1242                 :       7497 :   basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
    1243                 :       7497 :   basic_block *bbs;
    1244                 :       7497 :   unsigned i;
    1245                 :            : 
    1246                 :       7497 :   bbs = get_loop_body_in_dom_order (loop);
    1247                 :            : 
    1248                 :       7497 :   gimple_stmt_iterator dst_gsi = gsi_after_labels (exit->dest);
    1249                 :       7497 :   bool safe_p = single_pred_p (exit->dest);
    1250                 :      23847 :   for (unsigned i = 0; i < nbbs; ++i)
    1251                 :            :     {
    1252                 :            :       /* We have made sure to not leave any dangling uses of SSA
    1253                 :            :          names defined in the loop.  With the exception of virtuals.
    1254                 :            :          Make sure we replace all uses of virtual defs that will remain
    1255                 :            :          outside of the loop with the bare symbol as delete_basic_block
    1256                 :            :          will release them.  */
    1257                 :      37867 :       for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi);
    1258                 :      21517 :            gsi_next (&gsi))
    1259                 :            :         {
    1260                 :      21517 :           gphi *phi = gsi.phi ();
    1261                 :      50979 :           if (virtual_operand_p (gimple_phi_result (phi)))
    1262                 :       7945 :             mark_virtual_phi_result_for_renaming (phi);
    1263                 :            :         }
    1264                 :      16350 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);)
    1265                 :            :         {
    1266                 :      88156 :           gimple *stmt = gsi_stmt (gsi);
    1267                 :      88156 :           tree vdef = gimple_vdef (stmt);
    1268                 :      33918 :           if (vdef && TREE_CODE (vdef) == SSA_NAME)
    1269                 :       8831 :             mark_virtual_operand_for_renaming (vdef);
    1270                 :            :           /* Also move and eventually reset debug stmts.  We can leave
    1271                 :            :              constant values in place in case the stmt dominates the exit.
    1272                 :            :              ???  Non-constant values from the last iteration can be
    1273                 :            :              replaced with final values if we can compute them.  */
    1274                 :      88156 :           if (gimple_debug_bind_p (stmt))
    1275                 :            :             {
    1276                 :      35921 :               tree val = gimple_debug_bind_get_value (stmt);
    1277                 :      35921 :               gsi_move_before (&gsi, &dst_gsi);
    1278                 :      35921 :               if (val
    1279                 :      35921 :                   && (!safe_p
    1280                 :      11968 :                       || !is_gimple_min_invariant (val)
    1281                 :        970 :                       || !dominated_by_p (CDI_DOMINATORS, exit->src, bbs[i])))
    1282                 :            :                 {
    1283                 :      12956 :                   gimple_debug_bind_reset_value (stmt);
    1284                 :     117462 :                   update_stmt (stmt);
    1285                 :            :                 }
    1286                 :            :             }
    1287                 :            :           else
    1288                 :      52235 :             gsi_next (&gsi);
    1289                 :            :         }
    1290                 :            :     }
    1291                 :            : 
    1292                 :       7497 :   redirect_edge_pred (exit, src);
    1293                 :       7497 :   exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
    1294                 :       7497 :   exit->flags |= EDGE_FALLTHRU;
    1295                 :       7497 :   cancel_loop_tree (loop);
    1296                 :       7497 :   rescan_loop_exit (exit, false, true);
    1297                 :            : 
    1298                 :       7497 :   i = nbbs;
    1299                 :      16350 :   do
    1300                 :            :     {
    1301                 :      16350 :       --i;
    1302                 :      16350 :       delete_basic_block (bbs[i]);
    1303                 :            :     }
    1304                 :      16350 :   while (i != 0);
    1305                 :            : 
    1306                 :       7497 :   free (bbs);
    1307                 :            : 
    1308                 :       7497 :   set_immediate_dominator (CDI_DOMINATORS, dest,
    1309                 :            :                            recompute_dominator (CDI_DOMINATORS, dest));
    1310                 :       7497 : }
    1311                 :            : 
    1312                 :            : /* Generates code for PARTITION.  Return whether LOOP needs to be destroyed.  */
    1313                 :            : 
    1314                 :            : static bool 
    1315                 :      11230 : generate_code_for_partition (class loop *loop,
    1316                 :            :                              partition *partition, bool copy_p)
    1317                 :            : {
    1318                 :      11230 :   switch (partition->kind)
    1319                 :            :     {
    1320                 :       2063 :     case PKIND_NORMAL:
    1321                 :       2063 :     case PKIND_PARTIAL_MEMSET:
    1322                 :            :       /* Reductions all have to be in the last partition.  */
    1323                 :       2063 :       gcc_assert (!partition_reduction_p (partition)
    1324                 :            :                   || !copy_p);
    1325                 :       2063 :       generate_loops_for_partition (loop, partition, copy_p);
    1326                 :       2063 :       return false;
    1327                 :            : 
    1328                 :       6441 :     case PKIND_MEMSET:
    1329                 :       6441 :       generate_memset_builtin (loop, partition);
    1330                 :       6441 :       break;
    1331                 :            : 
    1332                 :       2726 :     case PKIND_MEMCPY:
    1333                 :       2726 :     case PKIND_MEMMOVE:
    1334                 :       2726 :       generate_memcpy_builtin (loop, partition);
    1335                 :       2726 :       break;
    1336                 :            : 
    1337                 :          0 :     default:
    1338                 :          0 :       gcc_unreachable ();
    1339                 :            :     }
    1340                 :            : 
    1341                 :            :   /* Common tail for partitions we turn into a call.  If this was the last
    1342                 :            :      partition for which we generate code, we have to destroy the loop.  */
    1343                 :       9167 :   if (!copy_p)
    1344                 :       7497 :     return true;
    1345                 :            :   return false;
    1346                 :            : }
    1347                 :            : 
    1348                 :            : data_dependence_relation *
    1349                 :     635623 : loop_distribution::get_data_dependence (struct graph *rdg, data_reference_p a,
    1350                 :            :                                         data_reference_p b)
    1351                 :            : {
    1352                 :     635623 :   struct data_dependence_relation ent, **slot;
    1353                 :     635623 :   struct data_dependence_relation *ddr;
    1354                 :            : 
    1355                 :     635623 :   gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
    1356                 :     635623 :   gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
    1357                 :            :               <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
    1358                 :     635623 :   ent.a = a;
    1359                 :     635623 :   ent.b = b;
    1360                 :     635623 :   slot = ddrs_table->find_slot (&ent, INSERT);
    1361                 :     635623 :   if (*slot == NULL)
    1362                 :            :     {
    1363                 :     407848 :       ddr = initialize_data_dependence_relation (a, b, loop_nest);
    1364                 :     407848 :       compute_affine_dependence (ddr, loop_nest[0]);
    1365                 :     407848 :       *slot = ddr;
    1366                 :            :     }
    1367                 :            : 
    1368                 :     635623 :   return *slot;
    1369                 :            : }
    1370                 :            : 
    1371                 :            : bool
    1372                 :     247034 : loop_distribution::data_dep_in_cycle_p (struct graph *rdg,
    1373                 :            :                                         data_reference_p dr1,
    1374                 :            :                                         data_reference_p dr2)
    1375                 :            : {
    1376                 :     247034 :   struct data_dependence_relation *ddr;
    1377                 :            : 
    1378                 :            :   /* Re-shuffle data-refs to be in topological order.  */
    1379                 :     494068 :   if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
    1380                 :     247034 :       > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
    1381                 :      90038 :     std::swap (dr1, dr2);
    1382                 :            : 
    1383                 :     247034 :   ddr = get_data_dependence (rdg, dr1, dr2);
    1384                 :            : 
    1385                 :            :   /* In case of no data dependence.  */
    1386                 :     247034 :   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
    1387                 :            :     return false;
    1388                 :            :   /* For unknown data dependence or known data dependence which can't be
    1389                 :            :      expressed in classic distance vector, we check if it can be resolved
    1390                 :            :      by runtime alias check.  If yes, we still consider data dependence
    1391                 :            :      as won't introduce data dependence cycle.  */
    1392                 :      70951 :   else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
    1393                 :      70951 :            || DDR_NUM_DIST_VECTS (ddr) == 0)
    1394                 :      37557 :     return !runtime_alias_check_p (ddr, NULL, true);
    1395                 :      33394 :   else if (DDR_NUM_DIST_VECTS (ddr) > 1)
    1396                 :            :     return true;
    1397                 :      30069 :   else if (DDR_REVERSED_P (ddr)
    1398                 :      59668 :            || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
    1399                 :      28300 :     return false;
    1400                 :            : 
    1401                 :            :   return true;
    1402                 :            : }
    1403                 :            : 
    1404                 :            : void
    1405                 :     157357 : loop_distribution::update_type_for_merge (struct graph *rdg,
    1406                 :            :                                            partition *partition1,
    1407                 :            :                                            partition *partition2)
    1408                 :            : {
    1409                 :     157357 :   unsigned i, j;
    1410                 :     157357 :   bitmap_iterator bi, bj;
    1411                 :     157357 :   data_reference_p dr1, dr2;
    1412                 :            : 
    1413                 :     528037 :   EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
    1414                 :            :     {
    1415                 :     375774 :       unsigned start = (partition1 == partition2) ? i + 1 : 0;
    1416                 :            : 
    1417                 :     375774 :       dr1 = datarefs_vec[i];
    1418                 :     932447 :       EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj)
    1419                 :            :         {
    1420                 :     561767 :           dr2 = datarefs_vec[j];
    1421                 :     561767 :           if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
    1422                 :     314733 :             continue;
    1423                 :            : 
    1424                 :            :           /* Partition can only be executed sequentially if there is any
    1425                 :            :              data dependence cycle.  */
    1426                 :     247034 :           if (data_dep_in_cycle_p (rdg, dr1, dr2))
    1427                 :            :             {
    1428                 :       5094 :               partition1->type = PTYPE_SEQUENTIAL;
    1429                 :       5094 :               return;
    1430                 :            :             }
    1431                 :            :         }
    1432                 :            :     }
    1433                 :            : }
    1434                 :            : 
    1435                 :            : partition *
    1436                 :     164175 : loop_distribution::build_rdg_partition_for_vertex (struct graph *rdg, int v)
    1437                 :            : {
    1438                 :     164175 :   partition *partition = partition_alloc ();
    1439                 :     164175 :   auto_vec<int, 3> nodes;
    1440                 :     164175 :   unsigned i, j;
    1441                 :     164175 :   int x;
    1442                 :     164175 :   data_reference_p dr;
    1443                 :            : 
    1444                 :     164175 :   graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
    1445                 :            : 
    1446                 :    2485220 :   FOR_EACH_VEC_ELT (nodes, i, x)
    1447                 :            :     {
    1448                 :    2321040 :       bitmap_set_bit (partition->stmts, x);
    1449                 :            : 
    1450                 :    3033550 :       for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j)
    1451                 :            :         {
    1452                 :     357800 :           unsigned idx = (unsigned) DR_INDEX (dr);
    1453                 :     715600 :           gcc_assert (idx < datarefs_vec.length ());
    1454                 :            : 
    1455                 :            :           /* Partition can only be executed sequentially if there is any
    1456                 :            :              unknown data reference.  */
    1457                 :     357800 :           if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
    1458                 :     337291 :               || !DR_INIT (dr) || !DR_STEP (dr))
    1459                 :      20509 :             partition->type = PTYPE_SEQUENTIAL;
    1460                 :            : 
    1461                 :     357800 :           bitmap_set_bit (partition->datarefs, idx);
    1462                 :            :         }
    1463                 :            :     }
    1464                 :            : 
    1465                 :     164175 :   if (partition->type == PTYPE_SEQUENTIAL)
    1466                 :            :     return partition;
    1467                 :            : 
    1468                 :            :   /* Further check if any data dependence prevents us from executing the
    1469                 :            :      partition parallelly.  */
    1470                 :     153122 :   update_type_for_merge (rdg, partition, partition);
    1471                 :            : 
    1472                 :     153122 :   return partition;
    1473                 :            : }
    1474                 :            : 
    1475                 :            : /* Given PARTITION of LOOP and RDG, record single load/store data references
    1476                 :            :    for builtin partition in SRC_DR/DST_DR, return false if there is no such
    1477                 :            :    data references.  */
    1478                 :            : 
    1479                 :            : static bool
    1480                 :     143682 : find_single_drs (class loop *loop, struct graph *rdg, partition *partition,
    1481                 :            :                  data_reference_p *dst_dr, data_reference_p *src_dr)
    1482                 :            : {
    1483                 :     143682 :   unsigned i;
    1484                 :     143682 :   data_reference_p single_ld = NULL, single_st = NULL;
    1485                 :     143682 :   bitmap_iterator bi;
    1486                 :            : 
    1487                 :    1563520 :   EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
    1488                 :            :     {
    1489                 :    1464220 :       gimple *stmt = RDG_STMT (rdg, i);
    1490                 :    1464220 :       data_reference_p dr;
    1491                 :            : 
    1492                 :    1464220 :       if (gimple_code (stmt) == GIMPLE_PHI)
    1493                 :     325183 :         continue;
    1494                 :            : 
    1495                 :            :       /* Any scalar stmts are ok.  */
    1496                 :    2129310 :       if (!gimple_vuse (stmt))
    1497                 :     910032 :         continue;
    1498                 :            : 
    1499                 :            :       /* Otherwise just regular loads/stores.  */
    1500                 :     229008 :       if (!gimple_assign_single_p (stmt))
    1501                 :     143682 :         return false;
    1502                 :            : 
    1503                 :            :       /* But exactly one store and/or load.  */
    1504                 :    1836170 :       for (unsigned j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j)
    1505                 :            :         {
    1506                 :     231705 :           tree type = TREE_TYPE (DR_REF (dr));
    1507                 :            : 
    1508                 :            :           /* The memset, memcpy and memmove library calls are only
    1509                 :            :              able to deal with generic address space.  */
    1510                 :     231705 :           if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type)))
    1511                 :            :             return false;
    1512                 :            : 
    1513                 :     231693 :           if (DR_IS_READ (dr))
    1514                 :            :             {
    1515                 :     142695 :               if (single_ld != NULL)
    1516                 :            :                 return false;
    1517                 :            :               single_ld = dr;
    1518                 :            :             }
    1519                 :            :           else
    1520                 :            :             {
    1521                 :      88998 :               if (single_st != NULL)
    1522                 :            :                 return false;
    1523                 :            :               single_st = dr;
    1524                 :            :             }
    1525                 :            :         }
    1526                 :            :     }
    1527                 :            : 
    1528                 :      99300 :   if (!single_st)
    1529                 :            :     return false;
    1530                 :            : 
    1531                 :            :   /* Bail out if this is a bitfield memory reference.  */
    1532                 :      87609 :   if (TREE_CODE (DR_REF (single_st)) == COMPONENT_REF
    1533                 :      87609 :       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1)))
    1534                 :            :     return false;
    1535                 :            : 
    1536                 :            :   /* Data reference must be executed exactly once per iteration of each
    1537                 :            :      loop in the loop nest.  We only need to check dominance information
    1538                 :            :      against the outermost one in a perfect loop nest because a bb can't
    1539                 :            :      dominate outermost loop's latch without dominating inner loop's.  */
    1540                 :      87473 :   basic_block bb_st = gimple_bb (DR_STMT (single_st));
    1541                 :      87473 :   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st))
    1542                 :            :     return false;
    1543                 :            : 
    1544                 :      79746 :   if (single_ld)
    1545                 :            :     {
    1546                 :      40333 :       gimple *store = DR_STMT (single_st), *load = DR_STMT (single_ld);
    1547                 :            :       /* Direct aggregate copy or via an SSA name temporary.  */
    1548                 :      40333 :       if (load != store
    1549                 :      77988 :           && gimple_assign_lhs (load) != gimple_assign_rhs1 (store))
    1550                 :            :         return false;
    1551                 :            : 
    1552                 :            :       /* Bail out if this is a bitfield memory reference.  */
    1553                 :      17992 :       if (TREE_CODE (DR_REF (single_ld)) == COMPONENT_REF
    1554                 :      17992 :           && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld), 1)))
    1555                 :            :         return false;
    1556                 :            : 
    1557                 :            :       /* Load and store must be in the same loop nest.  */
    1558                 :      17992 :       basic_block bb_ld = gimple_bb (DR_STMT (single_ld));
    1559                 :      17992 :       if (bb_st->loop_father != bb_ld->loop_father)
    1560                 :            :         return false;
    1561                 :            : 
    1562                 :            :       /* Data reference must be executed exactly once per iteration.
    1563                 :            :          Same as single_st, we only need to check against the outermost
    1564                 :            :          loop.  */
    1565                 :      17985 :       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld))
    1566                 :            :         return false;
    1567                 :            : 
    1568                 :      17985 :       edge e = single_exit (bb_st->loop_father);
    1569                 :      17985 :       bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld);
    1570                 :      17985 :       bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st);
    1571                 :      17985 :       if (dom_ld != dom_st)
    1572                 :            :         return false;
    1573                 :            :     }
    1574                 :            : 
    1575                 :      57398 :   *src_dr = single_ld;
    1576                 :      57398 :   *dst_dr = single_st;
    1577                 :      57398 :   return true;
    1578                 :            : }
    1579                 :            : 
    1580                 :            : /* Given data reference DR in LOOP_NEST, this function checks the enclosing
    1581                 :            :    loops from inner to outer to see if loop's step equals to access size at
    1582                 :            :    each level of loop.  Return 2 if we can prove this at all level loops;
    1583                 :            :    record access base and size in BASE and SIZE; save loop's step at each
    1584                 :            :    level of loop in STEPS if it is not null.  For example:
    1585                 :            : 
    1586                 :            :      int arr[100][100][100];
    1587                 :            :      for (i = 0; i < 100; i++)       ;steps[2] = 40000
    1588                 :            :        for (j = 100; j > 0; j--)     ;steps[1] = -400
    1589                 :            :          for (k = 0; k < 100; k++)   ;steps[0] = 4
    1590                 :            :            arr[i][j - 1][k] = 0;     ;base = &arr, size = 4000000
    1591                 :            : 
    1592                 :            :    Return 1 if we can prove the equality at the innermost loop, but not all
    1593                 :            :    level loops.  In this case, no information is recorded.
    1594                 :            : 
    1595                 :            :    Return 0 if no equality can be proven at any level loops.  */
    1596                 :            : 
    1597                 :            : static int
    1598                 :      41860 : compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
    1599                 :            :                       tree *size, vec<tree> *steps = NULL)
    1600                 :            : {
    1601                 :      41860 :   location_t loc = gimple_location (DR_STMT (dr));
    1602                 :      41860 :   basic_block bb = gimple_bb (DR_STMT (dr));
    1603                 :      41860 :   class loop *loop = bb->loop_father;
    1604                 :      41860 :   tree ref = DR_REF (dr);
    1605                 :      41860 :   tree access_base = build_fold_addr_expr (ref);
    1606                 :      41860 :   tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
    1607                 :      41860 :   int res = 0;
    1608                 :            : 
    1609                 :      42920 :   do {
    1610                 :      42920 :       tree scev_fn = analyze_scalar_evolution (loop, access_base);
    1611                 :      42920 :       if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
    1612                 :      17680 :         return res;
    1613                 :            : 
    1614                 :      42073 :       access_base = CHREC_LEFT (scev_fn);
    1615                 :      42073 :       if (tree_contains_chrecs (access_base, NULL))
    1616                 :          0 :         return res;
    1617                 :            : 
    1618                 :      42073 :       tree scev_step = CHREC_RIGHT (scev_fn);
    1619                 :            :       /* Only support constant steps.  */
    1620                 :      42073 :       if (TREE_CODE (scev_step) != INTEGER_CST)
    1621                 :       2819 :         return res;
    1622                 :            : 
    1623                 :      39254 :       enum ev_direction access_dir = scev_direction (scev_fn);
    1624                 :      39254 :       if (access_dir == EV_DIR_UNKNOWN)
    1625                 :          0 :         return res;
    1626                 :            : 
    1627                 :      39254 :       if (steps != NULL)
    1628                 :      27770 :         steps->safe_push (scev_step);
    1629                 :            : 
    1630                 :      39254 :       scev_step = fold_convert_loc (loc, sizetype, scev_step);
    1631                 :            :       /* Compute absolute value of scev step.  */
    1632                 :      39254 :       if (access_dir == EV_DIR_DECREASES)
    1633                 :        705 :         scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
    1634                 :            : 
    1635                 :            :       /* At each level of loop, scev step must equal to access size.  In other
    1636                 :            :          words, DR must access consecutive memory between loop iterations.  */
    1637                 :      39254 :       if (!operand_equal_p (scev_step, access_size, 0))
    1638                 :      14014 :         return res;
    1639                 :            : 
    1640                 :            :       /* Access stride can be computed for data reference at least for the
    1641                 :            :          innermost loop.  */
    1642                 :      25240 :       res = 1;
    1643                 :            : 
    1644                 :            :       /* Compute DR's execution times in loop.  */
    1645                 :      25240 :       tree niters = number_of_latch_executions (loop);
    1646                 :      25240 :       niters = fold_convert_loc (loc, sizetype, niters);
    1647                 :      25240 :       if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
    1648                 :      24576 :         niters = size_binop_loc (loc, PLUS_EXPR, niters, size_one_node);
    1649                 :            : 
    1650                 :            :       /* Compute DR's overall access size in loop.  */
    1651                 :      25240 :       access_size = fold_build2_loc (loc, MULT_EXPR, sizetype,
    1652                 :            :                                      niters, scev_step);
    1653                 :            :       /* Adjust base address in case of negative step.  */
    1654                 :      25240 :       if (access_dir == EV_DIR_DECREASES)
    1655                 :            :         {
    1656                 :        588 :           tree adj = fold_build2_loc (loc, MINUS_EXPR, sizetype,
    1657                 :            :                                       scev_step, access_size);
    1658                 :        588 :           access_base = fold_build_pointer_plus_loc (loc, access_base, adj);
    1659                 :            :         }
    1660                 :      26300 :   } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
    1661                 :            : 
    1662                 :      24180 :   *base = access_base;
    1663                 :      24180 :   *size = access_size;
    1664                 :            :   /* Access stride can be computed for data reference at each level loop.  */
    1665                 :      24180 :   return 2;
    1666                 :            : }
    1667                 :            : 
    1668                 :            : /* Allocate and return builtin struct.  Record information like DST_DR,
    1669                 :            :    SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct.  */
    1670                 :            : 
    1671                 :            : static struct builtin_info *
    1672                 :       9333 : alloc_builtin (data_reference_p dst_dr, data_reference_p src_dr,
    1673                 :            :                tree dst_base, tree src_base, tree size)
    1674                 :            : {
    1675                 :          0 :   struct builtin_info *builtin = XNEW (struct builtin_info);
    1676                 :       9333 :   builtin->dst_dr = dst_dr;
    1677                 :       9333 :   builtin->src_dr = src_dr;
    1678                 :       9333 :   builtin->dst_base = dst_base;
    1679                 :       9333 :   builtin->src_base = src_base;
    1680                 :       9333 :   builtin->size = size;
    1681                 :       9333 :   return builtin;
    1682                 :            : }
    1683                 :            : 
    1684                 :            : /* Given data reference DR in loop nest LOOP, classify if it forms builtin
    1685                 :            :    memset call.  */
    1686                 :            : 
    1687                 :            : static void
    1688                 :      39413 : classify_builtin_st (loop_p loop, partition *partition, data_reference_p dr)
    1689                 :            : {
    1690                 :      39413 :   gimple *stmt = DR_STMT (dr);
    1691                 :      39413 :   tree base, size, rhs = gimple_assign_rhs1 (stmt);
    1692                 :            : 
    1693                 :      39413 :   if (const_with_all_bytes_same (rhs) == -1
    1694                 :      66158 :       && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
    1695                 :      33488 :           || (TYPE_MODE (TREE_TYPE (rhs))
    1696                 :      16744 :               != TYPE_MODE (unsigned_char_type_node))))
    1697                 :      32847 :     return;
    1698                 :            : 
    1699                 :      15059 :   if (TREE_CODE (rhs) == SSA_NAME
    1700                 :       2391 :       && !SSA_NAME_IS_DEFAULT_DEF (rhs)
    1701                 :      17329 :       && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
    1702                 :            :     return;
    1703                 :            : 
    1704                 :      12917 :   int res = compute_access_range (loop, dr, &base, &size);
    1705                 :      12917 :   if (res == 0)
    1706                 :            :     return;
    1707                 :       6641 :   if (res == 1)
    1708                 :            :     {
    1709                 :         75 :       partition->kind = PKIND_PARTIAL_MEMSET;
    1710                 :         75 :       return;
    1711                 :            :     }
    1712                 :            : 
    1713                 :       6566 :   poly_uint64 base_offset;
    1714                 :       6566 :   unsigned HOST_WIDE_INT const_base_offset;
    1715                 :       6566 :   tree base_base = strip_offset (base, &base_offset);
    1716                 :       6566 :   if (!base_offset.is_constant (&const_base_offset))
    1717                 :            :     return;
    1718                 :            : 
    1719                 :       6566 :   struct builtin_info *builtin;
    1720                 :       6566 :   builtin = alloc_builtin (dr, NULL, base, NULL_TREE, size);
    1721                 :       6566 :   builtin->dst_base_base = base_base;
    1722                 :       6566 :   builtin->dst_base_offset = const_base_offset;
    1723                 :       6566 :   partition->builtin = builtin;
    1724                 :       6566 :   partition->kind = PKIND_MEMSET;
    1725                 :            : }
    1726                 :            : 
    1727                 :            : /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
    1728                 :            :    if it forms builtin memcpy or memmove call.  */
    1729                 :            : 
    1730                 :            : void
    1731                 :      17985 : loop_distribution::classify_builtin_ldst (loop_p loop, struct graph *rdg,
    1732                 :            :                                           partition *partition,
    1733                 :            :                                           data_reference_p dst_dr,
    1734                 :            :                                           data_reference_p src_dr)
    1735                 :            : {
    1736                 :      17985 :   tree base, size, src_base, src_size;
    1737                 :      35970 :   auto_vec<tree> dst_steps, src_steps;
    1738                 :            : 
    1739                 :            :   /* Compute access range of both load and store.  */
    1740                 :      17985 :   int res = compute_access_range (loop, dst_dr, &base, &size, &dst_steps);
    1741                 :      17985 :   if (res != 2)
    1742                 :            :     return;
    1743                 :      10958 :   res = compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps);
    1744                 :      10958 :   if (res != 2)
    1745                 :            :     return;
    1746                 :            : 
    1747                 :            :   /* They much have the same access size.  */
    1748                 :       6656 :   if (!operand_equal_p (size, src_size, 0))
    1749                 :            :     return;
    1750                 :            : 
    1751                 :            :   /* Load and store in loop nest must access memory in the same way, i.e,
    1752                 :            :      their must have the same steps in each loop of the nest.  */
    1753                 :      19968 :   if (dst_steps.length () != src_steps.length ())
    1754                 :            :     return;
    1755                 :      26966 :   for (unsigned i = 0; i < dst_steps.length (); ++i)
    1756                 :       6995 :     if (!operand_equal_p (dst_steps[i], src_steps[i], 0))
    1757                 :            :       return;
    1758                 :            : 
    1759                 :            :   /* Now check that if there is a dependence.  */
    1760                 :       6488 :   ddr_p ddr = get_data_dependence (rdg, src_dr, dst_dr);
    1761                 :            : 
    1762                 :            :   /* Classify as memcpy if no dependence between load and store.  */
    1763                 :       6488 :   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
    1764                 :            :     {
    1765                 :       2668 :       partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
    1766                 :       2668 :       partition->kind = PKIND_MEMCPY;
    1767                 :       2668 :       return;
    1768                 :            :     }
    1769                 :            : 
    1770                 :            :   /* Can't do memmove in case of unknown dependence or dependence without
    1771                 :            :      classical distance vector.  */
    1772                 :       3820 :   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
    1773                 :       3820 :       || DDR_NUM_DIST_VECTS (ddr) == 0)
    1774                 :            :     return;
    1775                 :            : 
    1776                 :        147 :   unsigned i;
    1777                 :        147 :   lambda_vector dist_v;
    1778                 :        147 :   int num_lev = (DDR_LOOP_NEST (ddr)).length ();
    1779                 :        279 :   FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
    1780                 :            :     {
    1781                 :        229 :       unsigned dep_lev = dependence_level (dist_v, num_lev);
    1782                 :            :       /* Can't do memmove if load depends on store.  */
    1783                 :        180 :       if (dep_lev > 0 && dist_v[dep_lev - 1] > 0 && !DDR_REVERSED_P (ddr))
    1784                 :            :         return;
    1785                 :            :     }
    1786                 :            : 
    1787                 :         99 :   partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
    1788                 :         99 :   partition->kind = PKIND_MEMMOVE;
    1789                 :         99 :   return;
    1790                 :            : }
    1791                 :            : 
    1792                 :            : bool
    1793                 :     164175 : loop_distribution::classify_partition (loop_p loop,
    1794                 :            :                                        struct graph *rdg, partition *partition,
    1795                 :            :                                        bitmap stmt_in_all_partitions)
    1796                 :            : {
    1797                 :     164175 :   bitmap_iterator bi;
    1798                 :     164175 :   unsigned i;
    1799                 :     164175 :   data_reference_p single_ld = NULL, single_st = NULL;
    1800                 :     164175 :   bool volatiles_p = false, has_reduction = false;
    1801                 :            : 
    1802                 :    2485220 :   EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
    1803                 :            :     {
    1804                 :    2321040 :       gimple *stmt = RDG_STMT (rdg, i);
    1805                 :            : 
    1806                 :    3948140 :       if (gimple_has_volatile_ops (stmt))
    1807                 :          0 :         volatiles_p = true;
    1808                 :            : 
    1809                 :            :       /* If the stmt is not included by all partitions and there is uses
    1810                 :            :          outside of the loop, then mark the partition as reduction.  */
    1811                 :    2321040 :       if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
    1812                 :            :         {
    1813                 :            :           /* Due to limitation in the transform phase we have to fuse all
    1814                 :            :              reduction partitions.  As a result, this could cancel valid
    1815                 :            :              loop distribution especially for loop that induction variable
    1816                 :            :              is used outside of loop.  To workaround this issue, we skip
    1817                 :            :              marking partition as reudction if the reduction stmt belongs
    1818                 :            :              to all partitions.  In such case, reduction will be computed
    1819                 :            :              correctly no matter how partitions are fused/distributed.  */
    1820                 :      44253 :           if (!bitmap_bit_p (stmt_in_all_partitions, i))
    1821                 :      20004 :             partition->reduction_p = true;
    1822                 :            :           else
    1823                 :            :             has_reduction = true;
    1824                 :            :         }
    1825                 :            :     }
    1826                 :            : 
    1827                 :            :   /* Simple workaround to prevent classifying the partition as builtin
    1828                 :            :      if it contains any use outside of loop.  For the case where all
    1829                 :            :      partitions have the reduction this simple workaround is delayed
    1830                 :            :      to only affect the last partition.  */
    1831                 :     164175 :   if (partition->reduction_p)
    1832                 :            :      return has_reduction;
    1833                 :            : 
    1834                 :            :   /* Perform general partition disqualification for builtins.  */
    1835                 :     145039 :   if (volatiles_p
    1836                 :     145039 :       || !flag_tree_loop_distribute_patterns)
    1837                 :            :     return has_reduction;
    1838                 :            : 
    1839                 :            :   /* Find single load/store data references for builtin partition.  */
    1840                 :     143682 :   if (!find_single_drs (loop, rdg, partition, &single_st, &single_ld))
    1841                 :            :     return has_reduction;
    1842                 :            : 
    1843                 :      57398 :   partition->loc = gimple_location (DR_STMT (single_st));
    1844                 :            : 
    1845                 :            :   /* Classify the builtin kind.  */
    1846                 :      57398 :   if (single_ld == NULL)
    1847                 :      39413 :     classify_builtin_st (loop, partition, single_st);
    1848                 :            :   else
    1849                 :      17985 :     classify_builtin_ldst (loop, rdg, partition, single_st, single_ld);
    1850                 :            :   return has_reduction;
    1851                 :            : }
    1852                 :            : 
    1853                 :            : bool
    1854                 :     148592 : loop_distribution::share_memory_accesses (struct graph *rdg,
    1855                 :            :                        partition *partition1, partition *partition2)
    1856                 :            : {
    1857                 :     148592 :   unsigned i, j;
    1858                 :     148592 :   bitmap_iterator bi, bj;
    1859                 :     148592 :   data_reference_p dr1, dr2;
    1860                 :            : 
    1861                 :            :   /* First check whether in the intersection of the two partitions are
    1862                 :            :      any loads or stores.  Common loads are the situation that happens
    1863                 :            :      most often.  */
    1864                 :    1145580 :   EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
    1865                 :     999593 :     if (RDG_MEM_WRITE_STMT (rdg, i)
    1866                 :     999593 :         || RDG_MEM_READS_STMT (rdg, i))
    1867                 :            :       return true;
    1868                 :            : 
    1869                 :            :   /* Then check whether the two partitions access the same memory object.  */
    1870                 :     346362 :   EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
    1871                 :            :     {
    1872                 :     202106 :       dr1 = datarefs_vec[i];
    1873                 :            : 
    1874                 :     202106 :       if (!DR_BASE_ADDRESS (dr1)
    1875                 :     200867 :           || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1))
    1876                 :       1239 :         continue;
    1877                 :            : 
    1878                 :     470571 :       EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj)
    1879                 :            :         {
    1880                 :     271436 :           dr2 = datarefs_vec[j];
    1881                 :            : 
    1882                 :     271436 :           if (!DR_BASE_ADDRESS (dr2)
    1883                 :     271284 :               || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2))
    1884                 :        152 :             continue;
    1885                 :            : 
    1886                 :     271284 :           if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0)
    1887                 :     213341 :               && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0)
    1888                 :     203461 :               && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0)
    1889                 :     273063 :               && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0))
    1890                 :            :             return true;
    1891                 :            :         }
    1892                 :            :     }
    1893                 :            : 
    1894                 :            :   return false;
    1895                 :            : }
    1896                 :            : 
    1897                 :            : /* For each seed statement in STARTING_STMTS, this function builds
    1898                 :            :    partition for it by adding depended statements according to RDG.
    1899                 :            :    All partitions are recorded in PARTITIONS.  */
    1900                 :            : 
    1901                 :            : void
    1902                 :      91814 : loop_distribution::rdg_build_partitions (struct graph *rdg,
    1903                 :            :                                          vec<gimple *> starting_stmts,
    1904                 :            :                                          vec<partition *> *partitions)
    1905                 :            : {
    1906                 :      91814 :   auto_bitmap processed;
    1907                 :      91814 :   int i;
    1908                 :      91814 :   gimple *stmt;
    1909                 :            : 
    1910                 :     351198 :   FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
    1911                 :            :     {
    1912                 :     167570 :       int v = rdg_vertex_for_stmt (rdg, stmt);
    1913                 :            : 
    1914                 :     167570 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1915                 :        138 :         fprintf (dump_file,
    1916                 :            :                  "ldist asked to generate code for vertex %d\n", v);
    1917                 :            : 
    1918                 :            :       /* If the vertex is already contained in another partition so
    1919                 :            :          is the partition rooted at it.  */
    1920                 :     167570 :       if (bitmap_bit_p (processed, v))
    1921                 :       3395 :         continue;
    1922                 :            : 
    1923                 :     164175 :       partition *partition = build_rdg_partition_for_vertex (rdg, v);
    1924                 :     164175 :       bitmap_ior_into (processed, partition->stmts);
    1925                 :            : 
    1926                 :     164175 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1927                 :            :         {
    1928                 :        137 :           fprintf (dump_file, "ldist creates useful %s partition:\n",
    1929                 :        137 :                    partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
    1930                 :        137 :           bitmap_print (dump_file, partition->stmts, "  ", "\n");
    1931                 :            :         }
    1932                 :            : 
    1933                 :     164175 :       partitions->safe_push (partition);
    1934                 :            :     }
    1935                 :            : 
    1936                 :            :   /* All vertices should have been assigned to at least one partition now,
    1937                 :            :      other than vertices belonging to dead code.  */
    1938                 :      91814 : }
    1939                 :            : 
    1940                 :            : /* Dump to FILE the PARTITIONS.  */
    1941                 :            : 
    1942                 :            : static void
    1943                 :         39 : dump_rdg_partitions (FILE *file, vec<partition *> partitions)
    1944                 :            : {
    1945                 :         39 :   int i;
    1946                 :         39 :   partition *partition;
    1947                 :            : 
    1948                 :        104 :   FOR_EACH_VEC_ELT (partitions, i, partition)
    1949                 :         65 :     debug_bitmap_file (file, partition->stmts);
    1950                 :         39 : }
    1951                 :            : 
    1952                 :            : /* Debug PARTITIONS.  */
    1953                 :            : extern void debug_rdg_partitions (vec<partition *> );
    1954                 :            : 
    1955                 :            : DEBUG_FUNCTION void
    1956                 :          0 : debug_rdg_partitions (vec<partition *> partitions)
    1957                 :            : {
    1958                 :          0 :   dump_rdg_partitions (stderr, partitions);
    1959                 :          0 : }
    1960                 :            : 
    1961                 :            : /* Returns the number of read and write operations in the RDG.  */
    1962                 :            : 
    1963                 :            : static int
    1964                 :       2008 : number_of_rw_in_rdg (struct graph *rdg)
    1965                 :            : {
    1966                 :       2008 :   int i, res = 0;
    1967                 :            : 
    1968                 :      27837 :   for (i = 0; i < rdg->n_vertices; i++)
    1969                 :            :     {
    1970                 :      25829 :       if (RDG_MEM_WRITE_STMT (rdg, i))
    1971                 :       5876 :         ++res;
    1972                 :            : 
    1973                 :      25829 :       if (RDG_MEM_READS_STMT (rdg, i))
    1974                 :       4075 :         ++res;
    1975                 :            :     }
    1976                 :            : 
    1977                 :          0 :   return res;
    1978                 :            : }
    1979                 :            : 
    1980                 :            : /* Returns the number of read and write operations in a PARTITION of
    1981                 :            :    the RDG.  */
    1982                 :            : 
    1983                 :            : static int
    1984                 :       4334 : number_of_rw_in_partition (struct graph *rdg, partition *partition)
    1985                 :            : {
    1986                 :       4334 :   int res = 0;
    1987                 :       4334 :   unsigned i;
    1988                 :       4334 :   bitmap_iterator ii;
    1989                 :            : 
    1990                 :      39182 :   EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
    1991                 :            :     {
    1992                 :      34848 :       if (RDG_MEM_WRITE_STMT (rdg, i))
    1993                 :       5843 :         ++res;
    1994                 :            : 
    1995                 :      34848 :       if (RDG_MEM_READS_STMT (rdg, i))
    1996                 :       4099 :         ++res;
    1997                 :            :     }
    1998                 :            : 
    1999                 :       4334 :   return res;
    2000                 :            : }
    2001                 :            : 
    2002                 :            : /* Returns true when one of the PARTITIONS contains all the read or
    2003                 :            :    write operations of RDG.  */
    2004                 :            : 
    2005                 :            : static bool
    2006                 :       2008 : partition_contains_all_rw (struct graph *rdg,
    2007                 :            :                            vec<partition *> partitions)
    2008                 :            : {
    2009                 :       2008 :   int i;
    2010                 :       2008 :   partition *partition;
    2011                 :       2008 :   int nrw = number_of_rw_in_rdg (rdg);
    2012                 :            : 
    2013                 :       6303 :   FOR_EACH_VEC_ELT (partitions, i, partition)
    2014                 :       4334 :     if (nrw == number_of_rw_in_partition (rdg, partition))
    2015                 :            :       return true;
    2016                 :            : 
    2017                 :            :   return false;
    2018                 :            : }
    2019                 :            : 
    2020                 :            : int
    2021                 :     251970 : loop_distribution::pg_add_dependence_edges (struct graph *rdg, int dir,
    2022                 :            :                          bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs)
    2023                 :            : {
    2024                 :     251970 :   unsigned i, j;
    2025                 :     251970 :   bitmap_iterator bi, bj;
    2026                 :     251970 :   data_reference_p dr1, dr2, saved_dr1;
    2027                 :            : 
    2028                 :            :   /* dependence direction - 0 is no dependence, -1 is back,
    2029                 :            :      1 is forth, 2 is both (we can stop then, merging will occur).  */
    2030                 :     533298 :   EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi)
    2031                 :            :     {
    2032                 :     296252 :       dr1 = datarefs_vec[i];
    2033                 :            : 
    2034                 :     713813 :       EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj)
    2035                 :            :         {
    2036                 :     432485 :           int res, this_dir = 1;
    2037                 :     432485 :           ddr_p ddr;
    2038                 :            : 
    2039                 :     432485 :           dr2 = datarefs_vec[j];
    2040                 :            : 
    2041                 :            :           /* Skip all <read, read> data dependence.  */
    2042                 :     432485 :           if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
    2043                 :      50384 :             continue;
    2044                 :            : 
    2045                 :     382101 :           saved_dr1 = dr1;
    2046                 :            :           /* Re-shuffle data-refs to be in topological order.  */
    2047                 :     764202 :           if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
    2048                 :     382101 :               > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
    2049                 :            :             {
    2050                 :      25748 :               std::swap (dr1, dr2);
    2051                 :      25748 :               this_dir = -this_dir;
    2052                 :            :             }
    2053                 :     382101 :           ddr = get_data_dependence (rdg, dr1, dr2);
    2054                 :     382101 :           if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
    2055                 :            :             {
    2056                 :      18365 :               this_dir = 0;
    2057                 :      18365 :               res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1),
    2058                 :            :                                            DR_BASE_ADDRESS (dr2));
    2059                 :            :               /* Be conservative.  If data references are not well analyzed,
    2060                 :            :                  or the two data references have the same base address and
    2061                 :            :                  offset, add dependence and consider it alias to each other.
    2062                 :            :                  In other words, the dependence cannot be resolved by
    2063                 :            :                  runtime alias check.  */
    2064                 :      18365 :               if (!DR_BASE_ADDRESS (dr1) || !DR_BASE_ADDRESS (dr2)
    2065                 :      18116 :                   || !DR_OFFSET (dr1) || !DR_OFFSET (dr2)
    2066                 :      18116 :                   || !DR_INIT (dr1) || !DR_INIT (dr2)
    2067                 :      18116 :                   || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
    2068                 :      11343 :                   || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
    2069                 :      11340 :                   || res == 0)
    2070                 :            :                 this_dir = 2;
    2071                 :            :               /* Data dependence could be resolved by runtime alias check,
    2072                 :            :                  record it in ALIAS_DDRS.  */
    2073                 :       3532 :               else if (alias_ddrs != NULL)
    2074                 :       1700 :                 alias_ddrs->safe_push (ddr);
    2075                 :            :               /* Or simply ignore it.  */
    2076                 :            :             }
    2077                 :     363736 :           else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
    2078                 :            :             {
    2079                 :        317 :               if (DDR_REVERSED_P (ddr))
    2080                 :         42 :                 this_dir = -this_dir;
    2081                 :            : 
    2082                 :            :               /* Known dependences can still be unordered througout the
    2083                 :            :                  iteration space, see gcc.dg/tree-ssa/ldist-16.c.  */
    2084                 :        317 :               if (DDR_NUM_DIST_VECTS (ddr) != 1)
    2085                 :            :                 this_dir = 2;
    2086                 :            :               /* If the overlap is exact preserve stmt order.  */
    2087                 :        480 :               else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0),
    2088                 :        240 :                                             DDR_NB_LOOPS (ddr)))
    2089                 :            :                 ;
    2090                 :            :               /* Else as the distance vector is lexicographic positive swap
    2091                 :            :                  the dependence direction.  */
    2092                 :            :               else
    2093                 :        165 :                 this_dir = -this_dir;
    2094                 :            :             }
    2095                 :            :           else
    2096                 :            :             this_dir = 0;
    2097                 :       2008 :           if (this_dir == 2)
    2098                 :      14924 :             return 2;
    2099                 :     367191 :           else if (dir == 0)
    2100                 :            :             dir = this_dir;
    2101                 :       6098 :           else if (this_dir != 0 && dir != this_dir)
    2102                 :            :             return 2;
    2103                 :            :           /* Shuffle "back" dr1.  */
    2104                 :     367177 :           dr1 = saved_dr1;
    2105                 :            :         }
    2106                 :            :     }
    2107                 :            :   return dir;
    2108                 :            : }
    2109                 :            : 
    2110                 :            : /* Compare postorder number of the partition graph vertices V1 and V2.  */
    2111                 :            : 
    2112                 :            : static int
    2113                 :     311751 : pgcmp (const void *v1_, const void *v2_)
    2114                 :            : {
    2115                 :     311751 :   const vertex *v1 = (const vertex *)v1_;
    2116                 :     311751 :   const vertex *v2 = (const vertex *)v2_;
    2117                 :     311751 :   return v2->post - v1->post;
    2118                 :            : }
    2119                 :            : 
    2120                 :            : /* Data attached to vertices of partition dependence graph.  */
    2121                 :            : struct pg_vdata
    2122                 :            : {
    2123                 :            :   /* ID of the corresponding partition.  */
    2124                 :            :   int id;
    2125                 :            :   /* The partition.  */
    2126                 :            :   struct partition *partition;
    2127                 :            : };
    2128                 :            : 
    2129                 :            : /* Data attached to edges of partition dependence graph.  */
    2130                 :            : struct pg_edata
    2131                 :            : {
    2132                 :            :   /* If the dependence edge can be resolved by runtime alias check,
    2133                 :            :      this vector contains data dependence relations for runtime alias
    2134                 :            :      check.  On the other hand, if the dependence edge is introduced
    2135                 :            :      because of compilation time known data dependence, this vector
    2136                 :            :      contains nothing.  */
    2137                 :            :   vec<ddr_p> alias_ddrs;
    2138                 :            : };
    2139                 :            : 
    2140                 :            : /* Callback data for traversing edges in graph.  */
    2141                 :            : struct pg_edge_callback_data
    2142                 :            : {
    2143                 :            :   /* Bitmap contains strong connected components should be merged.  */
    2144                 :            :   bitmap sccs_to_merge;
    2145                 :            :   /* Array constains component information for all vertices.  */
    2146                 :            :   int *vertices_component;
    2147                 :            :   /* Vector to record all data dependence relations which are needed
    2148                 :            :      to break strong connected components by runtime alias checks.  */
    2149                 :            :   vec<ddr_p> *alias_ddrs;
    2150                 :            : };
    2151                 :            : 
    2152                 :            : /* Initialize vertice's data for partition dependence graph PG with
    2153                 :            :    PARTITIONS.  */
    2154                 :            : 
    2155                 :            : static void
    2156                 :       7461 : init_partition_graph_vertices (struct graph *pg,
    2157                 :            :                                vec<struct partition *> *partitions)
    2158                 :            : {
    2159                 :       7461 :   int i;
    2160                 :       7461 :   partition *partition;
    2161                 :       7461 :   struct pg_vdata *data;
    2162                 :            : 
    2163                 :      36417 :   for (i = 0; partitions->iterate (i, &partition); ++i)
    2164                 :            :     {
    2165                 :      28956 :       data = new pg_vdata;
    2166                 :      28956 :       pg->vertices[i].data = data;
    2167                 :      28956 :       data->id = i;
    2168                 :      28956 :       data->partition = partition;
    2169                 :            :     }
    2170                 :       7461 : }
    2171                 :            : 
    2172                 :            : /* Add edge <I, J> to partition dependence graph PG.  Attach vector of data
    2173                 :            :    dependence relations to the EDGE if DDRS isn't NULL.  */
    2174                 :            : 
    2175                 :            : static void
    2176                 :      32444 : add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs)
    2177                 :            : {
    2178                 :      32444 :   struct graph_edge *e = add_edge (pg, i, j);
    2179                 :            : 
    2180                 :            :   /* If the edge is attached with data dependence relations, it means this
    2181                 :            :      dependence edge can be resolved by runtime alias checks.  */
    2182                 :      32444 :   if (ddrs != NULL)
    2183                 :            :     {
    2184                 :       1143 :       struct pg_edata *data = new pg_edata;
    2185                 :            : 
    2186                 :       1143 :       gcc_assert (ddrs->length () > 0);
    2187                 :       1143 :       e->data = data;
    2188                 :       1143 :       data->alias_ddrs = vNULL;
    2189                 :       1143 :       data->alias_ddrs.safe_splice (*ddrs);
    2190                 :            :     }
    2191                 :      32444 : }
    2192                 :            : 
    2193                 :            : /* Callback function for graph travesal algorithm.  It returns true
    2194                 :            :    if edge E should skipped when traversing the graph.  */
    2195                 :            : 
    2196                 :            : static bool
    2197                 :        348 : pg_skip_alias_edge (struct graph_edge *e)
    2198                 :            : {
    2199                 :        348 :   struct pg_edata *data = (struct pg_edata *)e->data;
    2200                 :        348 :   return (data != NULL && data->alias_ddrs.length () > 0);
    2201                 :            : }
    2202                 :            : 
    2203                 :            : /* Callback function freeing data attached to edge E of graph.  */
    2204                 :            : 
    2205                 :            : static void
    2206                 :       1761 : free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *)
    2207                 :            : {
    2208                 :       1761 :   if (e->data != NULL)
    2209                 :            :     {
    2210                 :       1096 :       struct pg_edata *data = (struct pg_edata *)e->data;
    2211                 :       1096 :       data->alias_ddrs.release ();
    2212                 :       1096 :       delete data;
    2213                 :            :     }
    2214                 :       1761 : }
    2215                 :            : 
    2216                 :            : /* Free data attached to vertice of partition dependence graph PG.  */
    2217                 :            : 
    2218                 :            : static void
    2219                 :       7461 : free_partition_graph_vdata (struct graph *pg)
    2220                 :            : {
    2221                 :       7461 :   int i;
    2222                 :       7461 :   struct pg_vdata *data;
    2223                 :            : 
    2224                 :      36417 :   for (i = 0; i < pg->n_vertices; ++i)
    2225                 :            :     {
    2226                 :      28956 :       data = (struct pg_vdata *)pg->vertices[i].data;
    2227                 :      28956 :       delete data;
    2228                 :            :     }
    2229                 :       7461 : }
    2230                 :            : 
    2231                 :            : /* Build and return partition dependence graph for PARTITIONS.  RDG is
    2232                 :            :    reduced dependence graph for the loop to be distributed.  If IGNORE_ALIAS_P
    2233                 :            :    is true, data dependence caused by possible alias between references
    2234                 :            :    is ignored, as if it doesn't exist at all; otherwise all depdendences
    2235                 :            :    are considered.  */
    2236                 :            : 
    2237                 :            : struct graph *
    2238                 :       7461 : loop_distribution::build_partition_graph (struct graph *rdg,
    2239                 :            :                                           vec<struct partition *> *partitions,
    2240                 :            :                                           bool ignore_alias_p)
    2241                 :            : {
    2242                 :       7461 :   int i, j;
    2243                 :       7461 :   struct partition *partition1, *partition2;
    2244                 :      14922 :   graph *pg = new_graph (partitions->length ());
    2245                 :       7461 :   auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p;
    2246                 :            : 
    2247                 :       7461 :   alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs;
    2248                 :            : 
    2249                 :       7461 :   init_partition_graph_vertices (pg, partitions);
    2250                 :            : 
    2251                 :       7461 :   for (i = 0; partitions->iterate (i, &partition1); ++i)
    2252                 :            :     {
    2253                 :     317343 :       for (j = i + 1; partitions->iterate (j, &partition2); ++j)
    2254                 :            :         {
    2255                 :            :           /* dependence direction - 0 is no dependence, -1 is back,
    2256                 :            :              1 is forth, 2 is both (we can stop then, merging will occur).  */
    2257                 :     251970 :           int dir = 0;
    2258                 :            : 
    2259                 :            :           /* If the first partition has reduction, add back edge; if the
    2260                 :            :              second partition has reduction, add forth edge.  This makes
    2261                 :            :              sure that reduction partition will be sorted as the last one.  */
    2262                 :     251970 :           if (partition_reduction_p (partition1))
    2263                 :            :             dir = -1;
    2264                 :     251863 :           else if (partition_reduction_p (partition2))
    2265                 :       1248 :             dir = 1;
    2266                 :            : 
    2267                 :            :           /* Cleanup the temporary vector.  */
    2268                 :     251970 :           alias_ddrs.truncate (0);
    2269                 :            : 
    2270                 :     251970 :           dir = pg_add_dependence_edges (rdg, dir, partition1->datarefs,
    2271                 :            :                                          partition2->datarefs, alias_ddrs_p);
    2272                 :            : 
    2273                 :            :           /* Add edge to partition graph if there exists dependence.  There
    2274                 :            :              are two types of edges.  One type edge is caused by compilation
    2275                 :            :              time known dependence, this type cannot be resolved by runtime
    2276                 :            :              alias check.  The other type can be resolved by runtime alias
    2277                 :            :              check.  */
    2278                 :     251970 :           if (dir == 1 || dir == 2
    2279                 :     251970 :               || alias_ddrs.length () > 0)
    2280                 :            :             {
    2281                 :            :               /* Attach data dependence relations to edge that can be resolved
    2282                 :            :                  by runtime alias check.  */
    2283                 :      16802 :               bool alias_edge_p = (dir != 1 && dir != 2);
    2284                 :      33046 :               add_partition_graph_edge (pg, i, j,
    2285                 :            :                                         (alias_edge_p) ? &alias_ddrs : NULL);
    2286                 :            :             }
    2287                 :     251970 :           if (dir == -1 || dir == 2
    2288                 :     251970 :               || alias_ddrs.length () > 0)
    2289                 :            :             {
    2290                 :            :               /* Attach data dependence relations to edge that can be resolved
    2291                 :            :                  by runtime alias check.  */
    2292                 :      15642 :               bool alias_edge_p = (dir != -1 && dir != 2);
    2293                 :      30699 :               add_partition_graph_edge (pg, j, i,
    2294                 :            :                                         (alias_edge_p) ? &alias_ddrs : NULL);
    2295                 :            :             }
    2296                 :            :         }
    2297                 :            :     }
    2298                 :       7461 :   return pg;
    2299                 :            : }
    2300                 :            : 
    2301                 :            : /* Sort partitions in PG in descending post order and store them in
    2302                 :            :    PARTITIONS.  */
    2303                 :            : 
    2304                 :            : static void
    2305                 :       7461 : sort_partitions_by_post_order (struct graph *pg,
    2306                 :            :                                vec<struct partition *> *partitions)
    2307                 :            : {
    2308                 :       7461 :   int i;
    2309                 :       7461 :   struct pg_vdata *data;
    2310                 :            : 
    2311                 :            :   /* Now order the remaining nodes in descending postorder.  */
    2312                 :       7461 :   qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
    2313                 :       7461 :   partitions->truncate (0);
    2314                 :      36417 :   for (i = 0; i < pg->n_vertices; ++i)
    2315                 :            :     {
    2316                 :      28956 :       data = (struct pg_vdata *)pg->vertices[i].data;
    2317                 :      28956 :       if (data->partition)
    2318                 :      26107 :         partitions->safe_push (data->partition);
    2319                 :            :     }
    2320                 :       7461 : }
    2321                 :            : 
    2322                 :            : void
    2323                 :       4062 : loop_distribution::merge_dep_scc_partitions (struct graph *rdg,
    2324                 :            :                                              vec<struct partition *> *partitions,
    2325                 :            :                                              bool ignore_alias_p)
    2326                 :            : {
    2327                 :       4062 :   struct partition *partition1, *partition2;
    2328                 :       4062 :   struct pg_vdata *data;
    2329                 :       4062 :   graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p);
    2330                 :       4062 :   int i, j, num_sccs = graphds_scc (pg, NULL);
    2331                 :            : 
    2332                 :            :   /* Strong connected compoenent means dependence cycle, we cannot distribute
    2333                 :            :      them.  So fuse them together.  */
    2334                 :       8124 :   if ((unsigned) num_sccs < partitions->length ())
    2335                 :            :     {
    2336                 :       1156 :       for (i = 0; i < num_sccs; ++i)
    2337                 :            :         {
    2338                 :        634 :           for (j = 0; partitions->iterate (j, &partition1); ++j)
    2339                 :        634 :             if (pg->vertices[j].component == i)
    2340                 :            :               break;
    2341                 :       4023 :           for (j = j + 1; partitions->iterate (j, &partition2); ++j)
    2342                 :       2843 :             if (pg->vertices[j].component == i)
    2343                 :            :               {
    2344                 :       2592 :                 partition_merge_into (NULL, partition1,
    2345                 :            :                                       partition2, FUSE_SAME_SCC);
    2346                 :       2592 :                 partition1->type = PTYPE_SEQUENTIAL;
    2347                 :       2592 :                 (*partitions)[j] = NULL;
    2348                 :       2592 :                 partition_free (partition2);
    2349                 :       2592 :                 data = (struct pg_vdata *)pg->vertices[j].data;
    2350                 :       2592 :                 data->partition = NULL;
    2351                 :            :               }
    2352                 :            :         }
    2353                 :            :     }
    2354                 :            : 
    2355                 :       4062 :   sort_partitions_by_post_order (pg, partitions);
    2356                 :       8124 :   gcc_assert (partitions->length () == (unsigned)num_sccs);
    2357                 :       4062 :   free_partition_graph_vdata (pg);
    2358                 :       4062 :   free_graph (pg);
    2359                 :       4062 : }
    2360                 :            : 
    2361                 :            : /* Callback function for traversing edge E in graph G.  DATA is private
    2362                 :            :    callback data.  */
    2363                 :            : 
    2364                 :            : static void
    2365                 :        106 : pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data)
    2366                 :            : {
    2367                 :        106 :   int i, j, component;
    2368                 :        106 :   struct pg_edge_callback_data *cbdata;
    2369                 :        106 :   struct pg_edata *edata = (struct pg_edata *) e->data;
    2370                 :            : 
    2371                 :            :   /* If the edge doesn't have attached data dependence, it represents
    2372                 :            :      compilation time known dependences.  This type dependence cannot
    2373                 :            :      be resolved by runtime alias check.  */
    2374                 :        106 :   if (edata == NULL || edata->alias_ddrs.length () == 0)
    2375                 :            :     return;
    2376                 :            : 
    2377                 :         98 :   cbdata = (struct pg_edge_callback_data *) data;
    2378                 :         98 :   i = e->src;
    2379                 :         98 :   j = e->dest;
    2380                 :         98 :   component = cbdata->vertices_component[i];
    2381                 :            :   /* Vertices are topologically sorted according to compilation time
    2382                 :            :      known dependences, so we can break strong connected components
    2383                 :            :      by removing edges of the opposite direction, i.e, edges pointing
    2384                 :            :      from vertice with smaller post number to vertice with bigger post
    2385                 :            :      number.  */
    2386                 :         98 :   if (g->vertices[i].post < g->vertices[j].post
    2387                 :            :       /* We only need to remove edges connecting vertices in the same
    2388                 :            :          strong connected component to break it.  */
    2389                 :         51 :       && component == cbdata->vertices_component[j]
    2390                 :            :       /* Check if we want to break the strong connected component or not.  */
    2391                 :        149 :       && !bitmap_bit_p (cbdata->sccs_to_merge, component))
    2392                 :         48 :     cbdata->alias_ddrs->safe_splice (edata->alias_ddrs);
    2393                 :            : }
    2394                 :            : 
    2395                 :            : /* This is the main function breaking strong conected components in
    2396                 :            :    PARTITIONS giving reduced depdendence graph RDG.  Store data dependence
    2397                 :            :    relations for runtime alias check in ALIAS_DDRS.  */
    2398                 :            : void
    2399                 :       3399 : loop_distribution::break_alias_scc_partitions (struct graph *rdg,
    2400                 :            :                                                vec<struct partition *> *partitions,
    2401                 :            :                                                vec<ddr_p> *alias_ddrs)
    2402                 :            : {
    2403                 :       3399 :   int i, j, k, num_sccs, num_sccs_no_alias;
    2404                 :            :   /* Build partition dependence graph.  */
    2405                 :       3399 :   graph *pg = build_partition_graph (rdg, partitions, false);
    2406                 :            : 
    2407                 :       3399 :   alias_ddrs->truncate (0);
    2408                 :            :   /* Find strong connected components in the graph, with all dependence edges
    2409                 :            :      considered.  */
    2410                 :       3399 :   num_sccs = graphds_scc (pg, NULL);
    2411                 :            :   /* All SCCs now can be broken by runtime alias checks because SCCs caused by
    2412                 :            :      compilation time known dependences are merged before this function.  */
    2413                 :       6798 :   if ((unsigned) num_sccs < partitions->length ())
    2414                 :            :     {
    2415                 :        157 :       struct pg_edge_callback_data cbdata;
    2416                 :        314 :       auto_bitmap sccs_to_merge;
    2417                 :        314 :       auto_vec<enum partition_type> scc_types;
    2418                 :        157 :       struct partition *partition, *first;
    2419                 :            : 
    2420                 :            :       /* If all partitions in a SCC have the same type, we can simply merge the
    2421                 :            :          SCC.  This loop finds out such SCCS and record them in bitmap.  */
    2422                 :        157 :       bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
    2423                 :        322 :       for (i = 0; i < num_sccs; ++i)
    2424                 :            :         {
    2425                 :        174 :           for (j = 0; partitions->iterate (j, &first); ++j)
    2426                 :        174 :             if (pg->vertices[j].component == i)
    2427                 :            :               break;
    2428                 :            : 
    2429                 :        165 :           bool same_type = true, all_builtins = partition_builtin_p (first);
    2430                 :        497 :           for (++j; partitions->iterate (j, &partition); ++j)
    2431                 :            :             {
    2432                 :        340 :               if (pg->vertices[j].component != i)
    2433                 :         45 :                 continue;
    2434                 :            : 
    2435                 :        295 :               if (first->type != partition->type)
    2436                 :            :                 {
    2437                 :            :                   same_type = false;
    2438                 :            :                   break;
    2439                 :            :                 }
    2440                 :        287 :               all_builtins &= partition_builtin_p (partition);
    2441                 :            :             }
    2442                 :            :           /* Merge SCC if all partitions in SCC have the same type, though the
    2443                 :            :              result partition is sequential, because vectorizer can do better
    2444                 :            :              runtime alias check.  One expecption is all partitions in SCC are
    2445                 :            :              builtins.  */
    2446                 :        165 :           if (!same_type || all_builtins)
    2447                 :         30 :             bitmap_clear_bit (sccs_to_merge, i);
    2448                 :            :         }
    2449                 :            : 
    2450                 :            :       /* Initialize callback data for traversing.  */
    2451                 :        157 :       cbdata.sccs_to_merge = sccs_to_merge;
    2452                 :        157 :       cbdata.alias_ddrs = alias_ddrs;
    2453                 :        157 :       cbdata.vertices_component = XNEWVEC (int, pg->n_vertices);
    2454                 :            :       /* Record the component information which will be corrupted by next
    2455                 :            :          graph scc finding call.  */
    2456                 :        617 :       for (i = 0; i < pg->n_vertices; ++i)
    2457                 :        460 :         cbdata.vertices_component[i] = pg->vertices[i].component;
    2458                 :            : 
    2459                 :            :       /* Collect data dependences for runtime alias checks to break SCCs.  */
    2460                 :        157 :       if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
    2461                 :            :         {
    2462                 :            :           /* Run SCC finding algorithm again, with alias dependence edges
    2463                 :            :              skipped.  This is to topologically sort partitions according to
    2464                 :            :              compilation time known dependence.  Note the topological order
    2465                 :            :              is stored in the form of pg's post order number.  */
    2466                 :         30 :           num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
    2467                 :         60 :           gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias);
    2468                 :            :           /* With topological order, we can construct two subgraphs L and R.
    2469                 :            :              L contains edge <x, y> where x < y in terms of post order, while
    2470                 :            :              R contains edge <x, y> where x > y.  Edges for compilation time
    2471                 :            :              known dependence all fall in R, so we break SCCs by removing all
    2472                 :            :              (alias) edges of in subgraph L.  */
    2473                 :         30 :           for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);
    2474                 :            :         }
    2475                 :            : 
    2476                 :            :       /* For SCC that doesn't need to be broken, merge it.  */
    2477                 :        322 :       for (i = 0; i < num_sccs; ++i)
    2478                 :            :         {
    2479                 :        165 :           if (!bitmap_bit_p (sccs_to_merge, i))
    2480                 :         30 :             continue;
    2481                 :            : 
    2482                 :        140 :           for (j = 0; partitions->iterate (j, &first); ++j)
    2483                 :        140 :             if (cbdata.vertices_component[j] == i)
    2484                 :            :               break;
    2485                 :        601 :           for (k = j + 1; partitions->iterate (k, &partition); ++k)
    2486                 :            :             {
    2487                 :        301 :               struct pg_vdata *data;
    2488                 :            : 
    2489                 :        301 :               if (cbdata.vertices_component[k] != i)
    2490                 :         44 :                 continue;
    2491                 :            : 
    2492                 :            :               /* Update to the minimal postordeer number of vertices in scc so
    2493                 :            :                  that merged partition is sorted correctly against others.  */
    2494                 :        257 :               if (pg->vertices[j].post > pg->vertices[k].post)
    2495                 :        197 :                 pg->vertices[j].post = pg->vertices[k].post;
    2496                 :            : 
    2497                 :        257 :               partition_merge_into (NULL, first, partition, FUSE_SAME_SCC);
    2498                 :        257 :               (*partitions)[k] = NULL;
    2499                 :        257 :               partition_free (partition);
    2500                 :        257 :               data = (struct pg_vdata *)pg->vertices[k].data;
    2501                 :        257 :               gcc_assert (data->id == k);
    2502                 :        257 :               data->partition = NULL;
    2503                 :            :               /* The result partition of merged SCC must be sequential.  */
    2504                 :        257 :               first->type = PTYPE_SEQUENTIAL;
    2505                 :            :             }
    2506                 :            :         }
    2507                 :            :     }
    2508                 :            : 
    2509                 :       3399 :   sort_partitions_by_post_order (pg, partitions);
    2510                 :       3399 :   free_partition_graph_vdata (pg);
    2511                 :       3399 :   for_each_edge (pg, free_partition_graph_edata_cb, NULL);
    2512                 :       3399 :   free_graph (pg);
    2513                 :            : 
    2514                 :       3399 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2515                 :            :     {
    2516                 :         16 :       fprintf (dump_file, "Possible alias data dependence to break:\n");
    2517                 :         16 :       dump_data_dependence_relations (dump_file, *alias_ddrs);
    2518                 :            :     }
    2519                 :       3399 : }
    2520                 :            : 
    2521                 :            : /* Compute and return an expression whose value is the segment length which
    2522                 :            :    will be accessed by DR in NITERS iterations.  */
    2523                 :            : 
    2524                 :            : static tree
    2525                 :        904 : data_ref_segment_size (struct data_reference *dr, tree niters)
    2526                 :            : {
    2527                 :        904 :   niters = size_binop (MINUS_EXPR,
    2528                 :            :                        fold_convert (sizetype, niters),
    2529                 :            :                        size_one_node);
    2530                 :        904 :   return size_binop (MULT_EXPR,
    2531                 :            :                      fold_convert (sizetype, DR_STEP (dr)),
    2532                 :            :                      fold_convert (sizetype, niters));
    2533                 :            : }
    2534                 :            : 
    2535                 :            : /* Return true if LOOP's latch is dominated by statement for data reference
    2536                 :            :    DR.  */
    2537                 :            : 
    2538                 :            : static inline bool
    2539                 :            : latch_dominated_by_data_ref (class loop *loop, data_reference *dr)
    2540                 :            : {
    2541                 :            :   return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
    2542                 :            :                          gimple_bb (DR_STMT (dr)));
    2543                 :            : }
    2544                 :            : 
    2545                 :            : /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
    2546                 :            :    data dependence relations ALIAS_DDRS.  */
    2547                 :            : 
    2548                 :            : static void
    2549                 :         28 : compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
    2550                 :            :                            vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
    2551                 :            : {
    2552                 :         28 :   unsigned int i;
    2553                 :         28 :   unsigned HOST_WIDE_INT factor = 1;
    2554                 :         28 :   tree niters_plus_one, niters = number_of_latch_executions (loop);
    2555                 :            : 
    2556                 :         28 :   gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
    2557                 :         28 :   niters = fold_convert (sizetype, niters);
    2558                 :         28 :   niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
    2559                 :            : 
    2560                 :         28 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2561                 :          0 :     fprintf (dump_file, "Creating alias check pairs:\n");
    2562                 :            : 
    2563                 :            :   /* Iterate all data dependence relations and compute alias check pairs.  */
    2564                 :        960 :   for (i = 0; i < alias_ddrs->length (); i++)
    2565                 :            :     {
    2566                 :        452 :       ddr_p ddr = (*alias_ddrs)[i];
    2567                 :        452 :       struct data_reference *dr_a = DDR_A (ddr);
    2568                 :        452 :       struct data_reference *dr_b = DDR_B (ddr);
    2569                 :        452 :       tree seg_length_a, seg_length_b;
    2570                 :            : 
    2571                 :        452 :       if (latch_dominated_by_data_ref (loop, dr_a))
    2572                 :        452 :         seg_length_a = data_ref_segment_size (dr_a, niters_plus_one);
    2573                 :            :       else
    2574                 :          0 :         seg_length_a = data_ref_segment_size (dr_a, niters);
    2575                 :            : 
    2576                 :        452 :       if (latch_dominated_by_data_ref (loop, dr_b))
    2577                 :        451 :         seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
    2578                 :            :       else
    2579                 :          1 :         seg_length_b = data_ref_segment_size (dr_b, niters);
    2580                 :            : 
    2581                 :        452 :       unsigned HOST_WIDE_INT access_size_a
    2582                 :        452 :         = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
    2583                 :        452 :       unsigned HOST_WIDE_INT access_size_b
    2584                 :        452 :         = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
    2585                 :        452 :       unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
    2586                 :        452 :       unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
    2587                 :            : 
    2588                 :        452 :       dr_with_seg_len_pair_t dr_with_seg_len_pair
    2589                 :        904 :         (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
    2590                 :        904 :          dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b),
    2591                 :            :          /* ??? Would WELL_ORDERED be safe?  */
    2592                 :        452 :          dr_with_seg_len_pair_t::REORDERED);
    2593                 :            : 
    2594                 :        452 :       comp_alias_pairs->safe_push (dr_with_seg_len_pair);
    2595                 :            :     }
    2596                 :            : 
    2597                 :         28 :   if (tree_fits_uhwi_p (niters))
    2598                 :         25 :     factor = tree_to_uhwi (niters);
    2599                 :            : 
    2600                 :            :   /* Prune alias check pairs.  */
    2601                 :         28 :   prune_runtime_alias_test_list (comp_alias_pairs, factor);
    2602                 :         28 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2603                 :          0 :     fprintf (dump_file,
    2604                 :            :              "Improved number of alias checks from %d to %d\n",
    2605                 :            :              alias_ddrs->length (), comp_alias_pairs->length ());
    2606                 :         28 : }
    2607                 :            : 
    2608                 :            : /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
    2609                 :            :    checks and version LOOP under condition of these runtime alias checks.  */
    2610                 :            : 
    2611                 :            : static void
    2612                 :         28 : version_loop_by_alias_check (vec<struct partition *> *partitions,
    2613                 :            :                              class loop *loop, vec<ddr_p> *alias_ddrs)
    2614                 :            : {
    2615                 :         28 :   profile_probability prob;
    2616                 :         28 :   basic_block cond_bb;
    2617                 :         28 :   class loop *nloop;
    2618                 :         28 :   tree lhs, arg0, cond_expr = NULL_TREE;
    2619                 :         28 :   gimple_seq cond_stmts = NULL;
    2620                 :         28 :   gimple *call_stmt = NULL;
    2621                 :         28 :   auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs;
    2622                 :            : 
    2623                 :            :   /* Generate code for runtime alias checks if necessary.  */
    2624                 :         28 :   gcc_assert (alias_ddrs->length () > 0);
    2625                 :            : 
    2626                 :         28 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2627                 :          0 :     fprintf (dump_file,
    2628                 :            :              "Version loop <%d> with runtime alias check\n", loop->num);
    2629                 :            : 
    2630                 :         28 :   compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs);
    2631                 :         28 :   create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
    2632                 :         28 :   cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
    2633                 :            :                                       is_gimple_val, NULL_TREE);
    2634                 :            : 
    2635                 :            :   /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS.  */
    2636                 :         28 :   bool cancelable_p = flag_tree_loop_vectorize;
    2637                 :         28 :   if (cancelable_p)
    2638                 :            :     {
    2639                 :            :       unsigned i = 0;
    2640                 :         27 :       struct partition *partition;
    2641                 :         27 :       for (; partitions->iterate (i, &partition); ++i)
    2642                 :         21 :         if (!partition_builtin_p (partition))
    2643                 :            :           break;
    2644                 :            : 
    2645                 :            :      /* If all partitions are builtins, distributing it would be profitable and
    2646                 :            :         we don't want to cancel the runtime alias checks.  */
    2647                 :         26 :       if (i == partitions->length ())
    2648                 :            :         cancelable_p = false;
    2649                 :            :     }
    2650                 :            : 
    2651                 :            :   /* Generate internal function call for loop distribution alias check if the
    2652                 :            :      runtime alias check should be cancelable.  */
    2653                 :         22 :   if (cancelable_p)
    2654                 :            :     {
    2655                 :          7 :       call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
    2656                 :            :                                               2, NULL_TREE, cond_expr);
    2657                 :          7 :       lhs = make_ssa_name (boolean_type_node);
    2658                 :          7 :       gimple_call_set_lhs (call_stmt, lhs);
    2659                 :            :     }
    2660                 :            :   else
    2661                 :            :     lhs = cond_expr;
    2662                 :            : 
    2663                 :         28 :   prob = profile_probability::guessed_always ().apply_scale (9, 10);
    2664                 :         28 :   initialize_original_copy_tables ();
    2665                 :         28 :   nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (),
    2666                 :            :                         prob, prob.invert (), true);
    2667                 :         28 :   free_original_copy_tables ();
    2668                 :            :   /* Record the original loop number in newly generated loops.  In case of
    2669                 :            :      distribution, the original loop will be distributed and the new loop
    2670                 :            :      is kept.  */
    2671                 :         28 :   loop->orig_loop_num = nloop->num;
    2672                 :         28 :   nloop->orig_loop_num = nloop->num;
    2673                 :         28 :   nloop->dont_vectorize = true;
    2674                 :         28 :   nloop->force_vectorize = false;
    2675                 :            : 
    2676                 :         28 :   if (call_stmt)
    2677                 :            :     {
    2678                 :            :       /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
    2679                 :            :          loop could be destroyed.  */
    2680                 :          7 :       arg0 = build_int_cst (integer_type_node, loop->orig_loop_num);
    2681                 :          7 :       gimple_call_set_arg (call_stmt, 0, arg0);
    2682                 :          7 :       gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt);
    2683                 :            :     }
    2684                 :            : 
    2685                 :         28 :   if (cond_stmts)
    2686                 :            :     {
    2687                 :         28 :       gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb);
    2688                 :         28 :       gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT);
    2689                 :            :     }
    2690                 :         28 :   update_ssa (TODO_update_ssa);
    2691                 :         28 : }
    2692                 :            : 
    2693                 :            : /* Return true if loop versioning is needed to distrubute PARTITIONS.
    2694                 :            :    ALIAS_DDRS are data dependence relations for runtime alias check.  */
    2695                 :            : 
    2696                 :            : static inline bool
    2697                 :       8914 : version_for_distribution_p (vec<struct partition *> *partitions,
    2698                 :            :                             vec<ddr_p> *alias_ddrs)
    2699                 :            : {
    2700                 :            :   /* No need to version loop if we have only one partition.  */
    2701                 :       8914 :   if (partitions->length () == 1)
    2702                 :            :     return false;
    2703                 :            : 
    2704                 :            :   /* Need to version loop if runtime alias check is necessary.  */
    2705                 :       1969 :   return (alias_ddrs->length () > 0);
    2706                 :            : }
    2707                 :            : 
    2708                 :            : /* Compare base offset of builtin mem* partitions P1 and P2.  */
    2709                 :            : 
    2710                 :            : static int
    2711                 :        206 : offset_cmp (const void *vp1, const void *vp2)
    2712                 :            : {
    2713                 :        206 :   struct partition *p1 = *(struct partition *const *) vp1;
    2714                 :        206 :   struct partition *p2 = *(struct partition *const *) vp2;
    2715                 :        206 :   unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
    2716                 :        206 :   unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
    2717                 :        206 :   return (o2 < o1) - (o1 < o2);
    2718                 :            : }
    2719                 :            : 
    2720                 :            : /* Fuse adjacent memset builtin PARTITIONS if possible.  This is a special
    2721                 :            :    case optimization transforming below code:
    2722                 :            : 
    2723                 :            :      __builtin_memset (&obj, 0, 100);
    2724                 :            :      _1 = &obj + 100;
    2725                 :            :      __builtin_memset (_1, 0, 200);
    2726                 :            :      _2 = &obj + 300;
    2727                 :            :      __builtin_memset (_2, 0, 100);
    2728                 :            : 
    2729                 :            :    into:
    2730                 :            : 
    2731                 :            :      __builtin_memset (&obj, 0, 400);
    2732                 :            : 
    2733                 :            :    Note we don't have dependence information between different partitions
    2734                 :            :    at this point, as a result, we can't handle nonadjacent memset builtin
    2735                 :            :    partitions since dependence might be broken.  */
    2736                 :            : 
    2737                 :            : static void
    2738                 :       1987 : fuse_memset_builtins (vec<struct partition *> *partitions)
    2739                 :            : {
    2740                 :       1987 :   unsigned i, j;
    2741                 :       1987 :   struct partition *part1, *part2;
    2742                 :       1987 :   tree rhs1, rhs2;
    2743                 :            : 
    2744                 :       6282 :   for (i = 0; partitions->iterate (i, &part1);)
    2745                 :            :     {
    2746                 :       4295 :       if (part1->kind != PKIND_MEMSET)
    2747                 :            :         {
    2748                 :       2465 :           i++;
    2749                 :       2465 :           continue;
    2750                 :            :         }
    2751                 :            : 
    2752                 :            :       /* Find sub-array of memset builtins of the same base.  Index range
    2753                 :            :          of the sub-array is [i, j) with "j > i".  */
    2754                 :       1865 :       for (j = i + 1; partitions->iterate (j, &part2); ++j)
    2755                 :            :         {
    2756                 :       1428 :           if (part2->kind != PKIND_MEMSET
    2757                 :       1867 :               || !operand_equal_p (part1->builtin->dst_base_base,
    2758                 :        439 :                                    part2->builtin->dst_base_base, 0))
    2759                 :            :             break;
    2760                 :            : 
    2761                 :            :           /* Memset calls setting different values can't be merged.  */
    2762                 :         45 :           rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
    2763                 :         45 :           rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
    2764                 :         45 :           if (!operand_equal_p (rhs1, rhs2, 0))
    2765                 :            :             break;
    2766                 :            :         }
    2767                 :            : 
    2768                 :            :       /* Stable sort is required in order to avoid breaking dependence.  */
    2769                 :       1830 :       gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
    2770                 :            :                       offset_cmp);
    2771                 :            :       /* Continue with next partition.  */
    2772                 :       1830 :       i = j;
    2773                 :            :     }
    2774                 :            : 
    2775                 :            :   /* Merge all consecutive memset builtin partitions.  */
    2776                 :       8660 :   for (i = 0; i < partitions->length () - 1;)
    2777                 :            :     {
    2778                 :       2343 :       part1 = (*partitions)[i];
    2779                 :       2343 :       if (part1->kind != PKIND_MEMSET)
    2780                 :            :         {
    2781                 :        915 :           i++;
    2782                 :       2316 :           continue;
    2783                 :            :         }
    2784                 :            : 
    2785                 :       1428 :       part2 = (*partitions)[i + 1];
    2786                 :            :       /* Only merge memset partitions of the same base and with constant
    2787                 :            :          access sizes.  */
    2788                 :       2815 :       if (part2->kind != PKIND_MEMSET
    2789                 :        439 :           || TREE_CODE (part1->builtin->size) != INTEGER_CST
    2790                 :        179 :           || TREE_CODE (part2->builtin->size) != INTEGER_CST
    2791                 :       1607 :           || !operand_equal_p (part1->builtin->dst_base_base,
    2792                 :        179 :                                part2->builtin->dst_base_base, 0))
    2793                 :            :         {
    2794                 :       1387 :           i++;
    2795                 :       1387 :           continue;
    2796                 :            :         }
    2797                 :         41 :       rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
    2798                 :         41 :       rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
    2799                 :         41 :       int bytev1 = const_with_all_bytes_same (rhs1);
    2800                 :         41 :       int bytev2 = const_with_all_bytes_same (rhs2);
    2801                 :            :       /* Only merge memset partitions of the same value.  */
    2802                 :         41 :       if (bytev1 != bytev2 || bytev1 == -1)
    2803                 :            :         {
    2804                 :          6 :           i++;
    2805                 :          6 :           continue;
    2806                 :            :         }
    2807                 :         70 :       wide_int end1 = wi::add (part1->builtin->dst_base_offset,
    2808                 :         35 :                                wi::to_wide (part1->builtin->size));
    2809                 :            :       /* Only merge adjacent memset partitions.  */
    2810                 :         35 :       if (wi::ne_p (end1, part2->builtin->dst_base_offset))
    2811                 :            :         {
    2812                 :          8 :           i++;
    2813                 :          8 :           continue;
    2814                 :            :         }
    2815                 :            :       /* Merge partitions[i] and partitions[i+1].  */
    2816                 :         27 :       part1->builtin->size = fold_build2 (PLUS_EXPR, sizetype,
    2817                 :            :                                           part1->builtin->size,
    2818                 :            :                                           part2->builtin->size);
    2819                 :         27 :       partition_free (part2);
    2820                 :         27 :       partitions->ordered_remove (i + 1);
    2821                 :            :     }
    2822                 :       1987 : }
    2823                 :            : 
    2824                 :            : void
    2825                 :      24797 : loop_distribution::finalize_partitions (class loop *loop,
    2826                 :            :                                         vec<struct partition *> *partitions,
    2827                 :            :                                         vec<ddr_p> *alias_ddrs)
    2828                 :            : {
    2829                 :      24797 :   unsigned i;
    2830                 :      24797 :   struct partition *partition, *a;
    2831                 :            : 
    2832                 :      24797 :   if (partitions->length () == 1
    2833                 :      24797 :       || alias_ddrs->length () > 0)
    2834                 :      24797 :     return;
    2835                 :            : 
    2836                 :       3370 :   unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
    2837                 :       3370 :   bool same_type_p = true;
    2838                 :       3370 :   enum partition_type type = ((*partitions)[0])->type;
    2839                 :      16064 :   for (i = 0; partitions->iterate (i, &partition); ++i)
    2840                 :            :     {
    2841                 :      12694 :       same_type_p &= (type == partition->type);
    2842                 :      12694 :       if (partition_builtin_p (partition))
    2843                 :            :         {
    2844                 :       2230 :           num_builtin++;
    2845                 :       2230 :           continue;
    2846                 :            :         }
    2847                 :      10464 :       num_normal++;
    2848                 :      10464 :       if (partition->kind == PKIND_PARTIAL_MEMSET)
    2849                 :          0 :         num_partial_memset++;
    2850                 :            :     }
    2851                 :            : 
    2852                 :            :   /* Don't distribute current loop into too many loops given we don't have
    2853                 :            :      memory stream cost model.  Be even more conservative in case of loop
    2854                 :            :      nest distribution.  */
    2855                 :       3370 :   if ((same_type_p && num_builtin == 0
    2856                 :       1365 :        && (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
    2857                 :       2005 :       || (loop->inner != NULL
    2858                 :         48 :           && i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
    2859                 :       1998 :       || (loop->inner == NULL
    2860                 :       1957 :           && i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
    2861                 :            :     {
    2862                 :       8364 :       a = (*partitions)[0];
    2863                 :       8364 :       for (i = 1; partitions->iterate (i, &partition); ++i)
    2864                 :            :         {
    2865                 :       6981 :           partition_merge_into (NULL, a, partition, FUSE_FINALIZE);
    2866                 :       6981 :           partition_free (partition);
    2867                 :            :         }
    2868                 :       1383 :       partitions->truncate (1);
    2869                 :            :     }
    2870                 :            : 
    2871                 :            :   /* Fuse memset builtins if possible.  */
    2872                 :       3370 :   if (partitions->length () > 1)
    2873                 :       1987 :     fuse_memset_builtins (partitions);
    2874                 :            : }
    2875                 :            : 
    2876                 :            : /* Distributes the code from LOOP in such a way that producer statements
    2877                 :            :    are placed before consumer statements.  Tries to separate only the
    2878                 :            :    statements from STMTS into separate loops.  Returns the number of
    2879                 :            :    distributed loops.  Set NB_CALLS to number of generated builtin calls.
    2880                 :            :    Set *DESTROY_P to whether LOOP needs to be destroyed.  */
    2881                 :            : 
    2882                 :            : int
    2883                 :      92477 : loop_distribution::distribute_loop (class loop *loop, vec<gimple *> stmts,
    2884                 :            :                  control_dependences *cd, int *nb_calls, bool *destroy_p,
    2885                 :            :                  bool only_patterns_p)
    2886                 :            : {
    2887                 :      92477 :   ddrs_table = new hash_table<ddr_hasher> (389);
    2888                 :      92477 :   struct graph *rdg;
    2889                 :      92477 :   partition *partition;
    2890                 :      92477 :   int i, nbp;
    2891                 :            : 
    2892                 :      92477 :   *destroy_p = false;
    2893                 :      92477 :   *nb_calls = 0;
    2894                 :      92477 :   loop_nest.create (0);
    2895                 :      92477 :   if (!find_loop_nest (loop, &loop_nest))
    2896                 :            :     {
    2897                 :          0 :       loop_nest.release ();
    2898                 :          0 :       delete ddrs_table;
    2899                 :          0 :       return 0;
    2900                 :            :     }
    2901                 :            : 
    2902                 :      92477 :   datarefs_vec.create (20);
    2903                 :      92477 :   has_nonaddressable_dataref_p = false;
    2904                 :      92477 :   rdg = build_rdg (loop, cd);
    2905                 :      92477 :   if (!rdg)
    2906                 :            :     {
    2907                 :        663 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2908                 :          0 :         fprintf (dump_file,
    2909                 :            :                  "Loop %d not distributed: failed to build the RDG.\n",
    2910                 :            :                  loop->num);
    2911                 :            : 
    2912                 :        663 :       loop_nest.release ();
    2913                 :        663 :       free_data_refs (datarefs_vec);
    2914                 :        663 :       delete ddrs_table;
    2915                 :        663 :       return 0;
    2916                 :            :     }
    2917                 :            : 
    2918                 :     183628 :   if (datarefs_vec.length () > MAX_DATAREFS_NUM)
    2919                 :            :     {
    2920                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2921                 :          0 :         fprintf (dump_file,
    2922                 :            :                  "Loop %d not distributed: too many memory references.\n",
    2923                 :            :                  loop->num);
    2924                 :            : 
    2925                 :          0 :       free_rdg (rdg);
    2926                 :          0 :       loop_nest.release ();
    2927                 :          0 :       free_data_refs (datarefs_vec);
    2928                 :          0 :       delete ddrs_table;
    2929                 :          0 :       return 0;
    2930                 :            :     }
    2931                 :            : 
    2932                 :            :   data_reference_p dref;
    2933                 :     376433 :   for (i = 0; datarefs_vec.iterate (i, &dref); ++i)
    2934                 :     284619 :     dref->aux = (void *) (uintptr_t) i;
    2935                 :            : 
    2936                 :      91814 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2937                 :         65 :     dump_rdg (dump_file, rdg);
    2938                 :            : 
    2939                 :      91814 :   auto_vec<struct partition *, 3> partitions;
    2940                 :      91814 :   rdg_build_partitions (rdg, stmts, &partitions);
    2941                 :            : 
    2942                 :     183628 :   auto_vec<ddr_p> alias_ddrs;
    2943                 :            : 
    2944                 :     183628 :   auto_bitmap stmt_in_all_partitions;
    2945                 :      91814 :   bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts);
    2946                 :     164175 :   for (i = 1; partitions.iterate (i, &partition); ++i)
    2947                 :      72361 :     bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts);
    2948                 :            : 
    2949                 :            :   bool any_builtin = false;
    2950                 :            :   bool reduction_in_all = false;
    2951                 :     255989 :   FOR_EACH_VEC_ELT (partitions, i, partition)
    2952                 :            :     {
    2953                 :     164175 :       reduction_in_all
    2954                 :     164175 :         |= classify_partition (loop, rdg, partition, stmt_in_all_partitions);
    2955                 :     164175 :       any_builtin |= partition_builtin_p (partition);
    2956                 :            :     }
    2957                 :            : 
    2958                 :            :   /* If we are only distributing patterns but did not detect any,
    2959                 :            :      simply bail out.  */
    2960                 :      91814 :   if (only_patterns_p
    2961                 :      91814 :       && !any_builtin)
    2962                 :            :     {
    2963                 :      67017 :       nbp = 0;
    2964                 :      67017 :       goto ldist_done;
    2965                 :            :     }
    2966                 :            : 
    2967                 :            :   /* If we are only distributing patterns fuse all partitions that
    2968                 :            :      were not classified as builtins.  This also avoids chopping
    2969                 :            :      a loop into pieces, separated by builtin calls.  That is, we
    2970                 :            :      only want no or a single loop body remaining.  */
    2971                 :      24797 :   struct partition *into;
    2972                 :      24797 :   if (only_patterns_p)
    2973                 :            :     {
    2974                 :      13452 :       for (i = 0; partitions.iterate (i, &into); ++i)
    2975                 :       8110 :         if (!partition_builtin_p (into))
    2976                 :            :           break;
    2977                 :       9004 :       for (++i; partitions.iterate (i, &partition); ++i)
    2978                 :       2342 :         if (!partition_builtin_p (partition))
    2979                 :            :           {
    2980                 :       1890 :             partition_merge_into (NULL, into, partition, FUSE_NON_BUILTIN);
    2981                 :       1890 :             partitions.unordered_remove (i);
    2982                 :       1890 :             partition_free (partition);
    2983                 :       1890 :             i--;
    2984                 :            :           }
    2985                 :            :     }
    2986                 :            : 
    2987                 :            :   /* Due to limitations in the transform phase we have to fuse all
    2988                 :            :      reduction partitions into the last partition so the existing
    2989                 :            :      loop will contain all loop-closed PHI nodes.  */
    2990                 :      64756 :   for (i = 0; partitions.iterate (i, &into); ++i)
    2991                 :      41082 :     if (partition_reduction_p (into))
    2992                 :            :       break;
    2993                 :      26019 :   for (i = i + 1; partitions.iterate (i, &partition); ++i)
    2994                 :       1222 :     if (partition_reduction_p (partition))
    2995                 :            :       {
    2996                 :        959 :         partition_merge_into (rdg, into, partition, FUSE_REDUCTION);
    2997                 :        959 :         partitions.unordered_remove (i);
    2998                 :        959 :         partition_free (partition);
    2999                 :        959 :         i--;
    3000                 :            :       }
    3001                 :            : 
    3002                 :            :   /* Apply our simple cost model - fuse partitions with similar
    3003                 :            :      memory accesses.  */
    3004                 :      63744 :   for (i = 0; partitions.iterate (i, &into); ++i)
    3005                 :            :     {
    3006                 :      38947 :       bool changed = false;
    3007                 :      38947 :       if (partition_builtin_p (into) || into->kind == PKIND_PARTIAL_MEMSET)
    3008                 :       9326 :         continue;
    3009                 :     178213 :       for (int j = i + 1;
    3010                 :     178213 :            partitions.iterate (j, &partition); ++j)
    3011                 :            :         {
    3012                 :     148592 :           if (share_memory_accesses (rdg, into, partition))
    3013                 :            :             {
    3014                 :       4336 :               partition_merge_into (rdg, into, partition, FUSE_SHARE_REF);
    3015                 :       4336 :               partitions.unordered_remove (j);
    3016                 :       4336 :               partition_free (partition);
    3017                 :       4336 :               j--;
    3018                 :       4336 :               changed = true;
    3019                 :            :             }
    3020                 :            :         }
    3021                 :            :       /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
    3022                 :            :          accesses when 1 and 2 have similar accesses but not 0 and 1
    3023                 :            :          then in the next iteration we will fail to consider merging
    3024                 :            :          1 into 0,2.  So try again if we did any merging into 0.  */
    3025                 :      29621 :       if (changed)
    3026                 :       1938 :         i--;
    3027                 :            :     }
    3028                 :            : 
    3029                 :            :   /* Put a non-builtin partition last if we need to preserve a reduction.
    3030                 :            :      ???  This is a workaround that makes sort_partitions_by_post_order do
    3031                 :            :      the correct thing while in reality it should sort each component
    3032                 :            :      separately and then put the component with a reduction or a non-builtin
    3033                 :            :      last.  */
    3034                 :      24797 :   if (reduction_in_all
    3035                 :      24797 :       && partition_builtin_p (partitions.last()))
    3036                 :          8 :     FOR_EACH_VEC_ELT (partitions, i, partition)
    3037                 :          5 :       if (!partition_builtin_p (partition))
    3038                 :            :         {
    3039                 :          1 :           partitions.unordered_remove (i);
    3040                 :          1 :           partitions.quick_push (partition);
    3041                 :            :           break;
    3042                 :            :         }
    3043                 :            : 
    3044                 :            :   /* Build the partition dependency graph and fuse partitions in strong
    3045                 :            :      connected component.  */
    3046                 :      24797 :   if (partitions.length () > 1)
    3047                 :            :     {
    3048                 :            :       /* Don't support loop nest distribution under runtime alias check
    3049                 :            :          since it's not likely to enable many vectorization opportunities.
    3050                 :            :          Also if loop has any data reference which may be not addressable
    3051                 :            :          since alias check needs to take, compare address of the object.  */
    3052                 :       4062 :       if (loop->inner || has_nonaddressable_dataref_p)
    3053                 :        181 :         merge_dep_scc_partitions (rdg, &partitions, false);
    3054                 :            :       else
    3055                 :            :         {
    3056                 :       3881 :           merge_dep_scc_partitions (rdg, &partitions, true);
    3057                 :       3881 :           if (partitions.length () > 1)
    3058                 :       3399 :             break_alias_scc_partitions (rdg, &partitions, &alias_ddrs);
    3059                 :            :         }
    3060                 :            :     }
    3061                 :            : 
    3062                 :      24797 :   finalize_partitions (loop, &partitions, &alias_ddrs);
    3063                 :            : 
    3064                 :            :   /* If there is a reduction in all partitions make sure the last one
    3065                 :            :      is not classified for builtin code generation.  */
    3066                 :      24797 :   if (reduction_in_all)
    3067                 :            :     {
    3068                 :       3882 :       partition = partitions.last ();
    3069                 :       3882 :       if (only_patterns_p
    3070                 :          0 :           && partition_builtin_p (partition)
    3071                 :       3882 :           && !partition_builtin_p (partitions[0]))
    3072                 :            :         {
    3073                 :          0 :           nbp = 0;
    3074                 :          0 :           goto ldist_done;
    3075                 :            :         }
    3076                 :       3882 :       partition->kind = PKIND_NORMAL;
    3077                 :            :     }
    3078                 :            : 
    3079                 :      24797 :   nbp = partitions.length ();
    3080                 :      24797 :   if (nbp == 0
    3081                 :      24797 :       || (nbp == 1 && !partition_builtin_p (partitions[0]))
    3082                 :      33750 :       || (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
    3083                 :            :     {
    3084                 :      15883 :       nbp = 0;
    3085                 :      15883 :       goto ldist_done;
    3086                 :            :     }
    3087                 :            : 
    3088                 :      10883 :   if (version_for_distribution_p (&partitions, &alias_ddrs))
    3089                 :         28 :     version_loop_by_alias_check (&partitions, loop, &alias_ddrs);
    3090                 :            : 
    3091                 :       8914 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3092                 :            :     {
    3093                 :         39 :       fprintf (dump_file,
    3094                 :            :                "distribute loop <%d> into partitions:\n", loop->num);
    3095                 :         39 :       dump_rdg_partitions (dump_file, partitions);
    3096                 :            :     }
    3097                 :            : 
    3098                 :      20144 :   FOR_EACH_VEC_ELT (partitions, i, partition)
    3099                 :            :     {
    3100                 :      11230 :       if (partition_builtin_p (partition))
    3101                 :       9167 :         (*nb_calls)++;
    3102                 :      11230 :       *destroy_p |= generate_code_for_partition (loop, partition, i < nbp - 1);
    3103                 :            :     }
    3104                 :            : 
    3105                 :      91814 :  ldist_done:
    3106                 :      91814 :   loop_nest.release ();
    3107                 :      91814 :   free_data_refs (datarefs_vec);
    3108                 :     499662 :   for (hash_table<ddr_hasher>::iterator iter = ddrs_table->begin ();
    3109                 :     499662 :        iter != ddrs_table->end (); ++iter)
    3110                 :            :     {
    3111                 :     407848 :       free_dependence_relation (*iter);
    3112                 :     407848 :       *iter = NULL;
    3113                 :            :     }
    3114                 :      91814 :   delete ddrs_table;
    3115                 :            : 
    3116                 :     238947 :   FOR_EACH_VEC_ELT (partitions, i, partition)
    3117                 :     147133 :     partition_free (partition);
    3118                 :            : 
    3119                 :      91814 :   free_rdg (rdg);
    3120                 :      91814 :   return nbp - *nb_calls;
    3121                 :            : }
    3122                 :            : 
    3123                 :            : 
    3124                 :     139049 : void loop_distribution::bb_top_order_init (void)
    3125                 :            : {
    3126                 :     139049 :   int rpo_num;
    3127                 :     139049 :   int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
    3128                 :            : 
    3129                 :     139049 :   bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun));
    3130                 :     139049 :   bb_top_order_index_size = last_basic_block_for_fn (cfun);
    3131                 :     139049 :   rpo_num = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true);
    3132                 :    4855610 :   for (int i = 0; i < rpo_num; i++)
    3133                 :    4716560 :     bb_top_order_index[rpo[i]] = i;
    3134                 :            : 
    3135                 :     139049 :   free (rpo);
    3136                 :     139049 : }
    3137                 :            : 
    3138                 :     139049 : void loop_distribution::bb_top_order_destroy ()
    3139                 :            : {
    3140                 :     139049 :   free (bb_top_order_index);
    3141                 :     139049 :   bb_top_order_index = NULL;
    3142                 :     139049 :   bb_top_order_index_size = 0;
    3143                 :     139049 : }
    3144                 :            : 
    3145                 :            : 
    3146                 :            : /* Given LOOP, this function records seed statements for distribution in
    3147                 :            :    WORK_LIST.  Return false if there is nothing for distribution.  */
    3148                 :            : 
    3149                 :            : static bool
    3150                 :     117615 : find_seed_stmts_for_distribution (class loop *loop, vec<gimple *> *work_list)
    3151                 :            : {
    3152                 :     117615 :   basic_block *bbs = get_loop_body_in_dom_order (loop);
    3153                 :            : 
    3154                 :            :   /* Initialize the worklist with stmts we seed the partitions with.  */
    3155                 :     437471 :   for (unsigned i = 0; i < loop->num_nodes; ++i)
    3156                 :            :     {
    3157                 :     344865 :       for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
    3158                 :     823167 :            !gsi_end_p (gsi); gsi_next (&gsi))
    3159                 :            :         {
    3160                 :     478302 :           gphi *phi = gsi.phi ();
    3161                 :     956604 :           if (virtual_operand_p (gimple_phi_result (phi)))
    3162                 :     118713 :             continue;
    3163                 :            :           /* Distribute stmts which have defs that are used outside of
    3164                 :            :              the loop.  */
    3165                 :     359589 :           if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
    3166                 :     343538 :             continue;
    3167                 :      16051 :           work_list->safe_push (phi);
    3168                 :            :         }
    3169                 :     344865 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
    3170                 :    2691670 :            !gsi_end_p (gsi); gsi_next (&gsi))
    3171                 :            :         {
    3172                 :    2371820 :           gimple *stmt = gsi_stmt (gsi);
    3173                 :            : 
    3174                 :            :           /* Ignore clobbers, they do not have true side effects.  */
    3175                 :    2371820 :           if (gimple_clobber_p (stmt))
    3176                 :    2171120 :             continue;
    3177                 :            : 
    3178                 :            :           /* If there is a stmt with side-effects bail out - we
    3179                 :            :              cannot and should not distribute this loop.  */
    3180                 :    2366670 :           if (gimple_has_side_effects (stmt))
    3181                 :            :             {
    3182                 :      25009 :               free (bbs);
    3183                 :      25009 :               return false;
    3184                 :            :             }
    3185                 :            : 
    3186                 :            :           /* Distribute stmts which have defs that are used outside of
    3187                 :            :              the loop.  */
    3188                 :    2341660 :           if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
    3189                 :            :             ;
    3190                 :            :           /* Otherwise only distribute stores for now.  */
    3191                 :    3495900 :           else if (!gimple_vdef (stmt))
    3192                 :    2165980 :             continue;
    3193                 :            : 
    3194                 :     175683 :           work_list->safe_push (stmt);
    3195                 :            :         }
    3196                 :            :     }
    3197                 :      92606 :   free (bbs);
    3198                 :     185083 :   return work_list->length () > 0;
    3199                 :            : }
    3200                 :            : 
    3201                 :            : /* Given innermost LOOP, return the outermost enclosing loop that forms a
    3202                 :            :    perfect loop nest.  */
    3203                 :            : 
    3204                 :            : static class loop *
    3205                 :     107588 : prepare_perfect_loop_nest (class loop *loop)
    3206                 :            : {
    3207                 :     107588 :   class loop *outer = loop_outer (loop);
    3208                 :     107588 :   tree niters = number_of_latch_executions (loop);
    3209                 :            : 
    3210                 :            :   /* TODO: We only support the innermost 3-level loop nest distribution
    3211                 :            :      because of compilation time issue for now.  This should be relaxed
    3212                 :            :      in the future.  Note we only allow 3-level loop nest distribution
    3213                 :            :      when parallelizing loops.  */
    3214                 :     119468 :   while ((loop->inner == NULL
    3215                 :      11880 :           || (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
    3216                 :     134195 :          && loop_outer (outer)
    3217                 :      26539 :          && outer->inner == loop && loop->next == NULL
    3218                 :      17639 :          && single_exit (outer)
    3219                 :      16690 :          && !chrec_contains_symbols_defined_in_loop (niters, outer->num)
    3220                 :      12192 :          && (niters = number_of_latch_executions (outer)) != NULL_TREE
    3221                 :     131660 :          && niters != chrec_dont_know)
    3222                 :            :     {
    3223                 :      11880 :       loop = outer;
    3224                 :      11880 :       outer = loop_outer (loop);
    3225                 :            :     }
    3226                 :            : 
    3227                 :     107588 :   return loop;
    3228                 :            : }
    3229                 :            : 
    3230                 :            : 
    3231                 :            : unsigned int
    3232                 :     139049 : loop_distribution::execute (function *fun)
    3233                 :            : {
    3234                 :     139049 :   class loop *loop;
    3235                 :     139049 :   bool changed = false;
    3236                 :     139049 :   basic_block bb;
    3237                 :     139049 :   control_dependences *cd = NULL;
    3238                 :     139049 :   auto_vec<loop_p> loops_to_be_destroyed;
    3239                 :            : 
    3240                 :     417147 :   if (number_of_loops (fun) <= 1)
    3241                 :            :     return 0;
    3242                 :            : 
    3243                 :     139049 :   bb_top_order_init ();
    3244                 :            : 
    3245                 :    4855610 :   FOR_ALL_BB_FN (bb, fun)
    3246                 :            :     {
    3247                 :    4716560 :       gimple_stmt_iterator gsi;
    3248                 :    6907020 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3249                 :    2190460 :         gimple_set_uid (gsi_stmt (gsi), -1);
    3250                 :   38863800 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3251                 :   29430600 :         gimple_set_uid (gsi_stmt (gsi), -1);
    3252                 :            :     }
    3253                 :            : 
    3254                 :            :   /* We can at the moment only distribute non-nested loops, thus restrict
    3255                 :            :      walking to innermost loops.  */
    3256                 :     406872 :   FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
    3257                 :            :     {
    3258                 :            :       /* Don't distribute multiple exit edges loop, or cold loop when
    3259                 :            :          not doing pattern detection.  */
    3260                 :     267823 :       if (!single_exit (loop)
    3261                 :     267823 :           || (!flag_tree_loop_distribute_patterns
    3262                 :        812 :               && !optimize_loop_for_speed_p (loop)))
    3263                 :      98124 :         continue;
    3264                 :            : 
    3265                 :            :       /* Don't distribute loop if niters is unknown.  */
    3266                 :     169699 :       tree niters = number_of_latch_executions (loop);
    3267                 :     169699 :       if (niters == NULL_TREE || niters == chrec_dont_know)
    3268                 :      62111 :         continue;
    3269                 :            : 
    3270                 :            :       /* Get the perfect loop nest for distribution.  */
    3271                 :     107588 :       loop = prepare_perfect_loop_nest (loop);
    3272                 :     191151 :       for (; loop; loop = loop->inner)
    3273                 :            :         {
    3274                 :     201178 :           auto_vec<gimple *> work_list;
    3275                 :     117615 :           if (!find_seed_stmts_for_distribution (loop, &work_list))
    3276                 :            :             break;
    3277                 :            : 
    3278                 :      92477 :           const char *str = loop->inner ? " nest" : "";
    3279                 :      92477 :           dump_user_location_t loc = find_loop_location (loop);
    3280                 :      92477 :           if (!cd)
    3281                 :            :             {
    3282                 :      42217 :               calculate_dominance_info (CDI_DOMINATORS);
    3283                 :      42217 :               calculate_dominance_info (CDI_POST_DOMINATORS);
    3284                 :      42217 :               cd = new control_dependences ();
    3285                 :      42217 :               free_dominance_info (CDI_POST_DOMINATORS);
    3286                 :            :             }
    3287                 :            : 
    3288                 :      92477 :           bool destroy_p;
    3289                 :      92477 :           int nb_generated_loops, nb_generated_calls;
    3290                 :      92477 :           nb_generated_loops
    3291                 :      92477 :             = distribute_loop (loop, work_list, cd, &nb_generated_calls,
    3292                 :      92477 :                                &destroy_p, (!optimize_loop_for_speed_p (loop)
    3293                 :      92477 :                                             || !flag_tree_loop_distribution));
    3294                 :      92477 :           if (destroy_p)
    3295                 :       7497 :             loops_to_be_destroyed.safe_push (loop);
    3296                 :            : 
    3297                 :      92477 :           if (nb_generated_loops + nb_generated_calls > 0)
    3298                 :            :             {
    3299                 :       8914 :               changed = true;
    3300                 :       8914 :               if (dump_enabled_p ())
    3301                 :         67 :                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
    3302                 :            :                                  loc, "Loop%s %d distributed: split to %d loops "
    3303                 :            :                                  "and %d library calls.\n", str, loop->num,
    3304                 :            :                                  nb_generated_loops, nb_generated_calls);
    3305                 :            : 
    3306                 :            :               break;
    3307                 :            :             }
    3308                 :            : 
    3309                 :      83563 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3310                 :         26 :             fprintf (dump_file, "Loop%s %d not distributed.\n", str, loop->num);
    3311                 :            :         }
    3312                 :            :     }
    3313                 :            : 
    3314                 :     139049 :   if (cd)
    3315                 :      42217 :     delete cd;
    3316                 :            : 
    3317                 :     139049 :   if (bb_top_order_index != NULL)
    3318                 :     139049 :     bb_top_order_destroy ();
    3319                 :            : 
    3320                 :     139049 :   if (changed)
    3321                 :            :     {
    3322                 :            :       /* Destroy loop bodies that could not be reused.  Do this late as we
    3323                 :            :          otherwise can end up refering to stale data in control dependences.  */
    3324                 :            :       unsigned i;
    3325                 :      18237 :       FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
    3326                 :       7497 :         destroy_loop (loop);
    3327                 :            : 
    3328                 :            :       /* Cached scalar evolutions now may refer to wrong or non-existing
    3329                 :            :          loops.  */
    3330                 :       5941 :       scev_reset_htab ();
    3331                 :       5941 :       mark_virtual_operands_for_renaming (fun);
    3332                 :       5941 :       rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    3333                 :            :     }
    3334                 :            : 
    3335                 :     139049 :   checking_verify_loop_structure ();
    3336                 :            : 
    3337                 :     139049 :   return changed ? TODO_cleanup_cfg : 0;
    3338                 :            : }
    3339                 :            : 
    3340                 :            : 
    3341                 :            : /* Distribute all loops in the current function.  */
    3342                 :            : 
    3343                 :            : namespace {
    3344                 :            : 
    3345                 :            : const pass_data pass_data_loop_distribution =
    3346                 :            : {
    3347                 :            :   GIMPLE_PASS, /* type */
    3348                 :            :   "ldist", /* name */
    3349                 :            :   OPTGROUP_LOOP, /* optinfo_flags */
    3350                 :            :   TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
    3351                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3352                 :            :   0, /* properties_provided */
    3353                 :            :   0, /* properties_destroyed */
    3354                 :            :   0, /* todo_flags_start */
    3355                 :            :   0, /* todo_flags_finish */
    3356                 :            : };
    3357                 :            : 
    3358                 :            : class pass_loop_distribution : public gimple_opt_pass
    3359                 :            : {
    3360                 :            : public:
    3361                 :     200540 :   pass_loop_distribution (gcc::context *ctxt)
    3362                 :     401080 :     : gimple_opt_pass (pass_data_loop_distribution, ctxt)
    3363                 :            :   {}
    3364                 :            : 
    3365                 :            :   /* opt_pass methods: */
    3366                 :     157439 :   virtual bool gate (function *)
    3367                 :            :     {
    3368                 :     157439 :       return flag_tree_loop_distribution
    3369                 :     157439 :         || flag_tree_loop_distribute_patterns;
    3370                 :            :     }
    3371                 :            : 
    3372                 :            :   virtual unsigned int execute (function *);
    3373                 :            : 
    3374                 :            : }; // class pass_loop_distribution
    3375                 :            : 
    3376                 :            : unsigned int
    3377                 :     139049 : pass_loop_distribution::execute (function *fun)
    3378                 :            : {
    3379                 :     139049 :   return loop_distribution ().execute (fun);
    3380                 :            : }
    3381                 :            : 
    3382                 :            : } // anon namespace
    3383                 :            : 
    3384                 :            : gimple_opt_pass *
    3385                 :     200540 : make_pass_loop_distribution (gcc::context *ctxt)
    3386                 :            : {
    3387                 :     200540 :   return new pass_loop_distribution (ctxt);
    3388                 :            : }

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.