Branch data Line data Source code
1 : : /* Loop distribution.
2 : : Copyright (C) 2006-2025 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 : : #include "tree-affine.h"
119 : : #include "intl.h"
120 : : #include "rtl.h"
121 : : #include "memmodel.h"
122 : : #include "optabs.h"
123 : : #include "tree-ssa-loop-niter.h"
124 : :
125 : :
126 : : #define MAX_DATAREFS_NUM \
127 : : ((unsigned) param_loop_max_datarefs_for_datadeps)
128 : :
129 : : /* Threshold controlling number of distributed partitions. Given it may
130 : : be unnecessary if a memory stream cost model is invented in the future,
131 : : we define it as a temporary macro, rather than a parameter. */
132 : : #define NUM_PARTITION_THRESHOLD (4)
133 : :
134 : : /* Hashtable helpers. */
135 : :
136 : : struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
137 : : {
138 : : static inline hashval_t hash (const data_dependence_relation *);
139 : : static inline bool equal (const data_dependence_relation *,
140 : : const data_dependence_relation *);
141 : : };
142 : :
143 : : /* Hash function for data dependence. */
144 : :
145 : : inline hashval_t
146 : 9926170 : ddr_hasher::hash (const data_dependence_relation *ddr)
147 : : {
148 : 9926170 : inchash::hash h;
149 : 9926170 : h.add_ptr (DDR_A (ddr));
150 : 9926170 : h.add_ptr (DDR_B (ddr));
151 : 9926170 : return h.end ();
152 : : }
153 : :
154 : : /* Hash table equality function for data dependence. */
155 : :
156 : : inline bool
157 : 9145318 : ddr_hasher::equal (const data_dependence_relation *ddr1,
158 : : const data_dependence_relation *ddr2)
159 : : {
160 : 9145318 : return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
161 : : }
162 : :
163 : :
164 : :
165 : : #define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
166 : :
167 : : /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
168 : : struct rdg_vertex
169 : : {
170 : : /* The statement represented by this vertex. */
171 : : gimple *stmt;
172 : :
173 : : /* Vector of data-references in this statement. */
174 : : vec<data_reference_p> datarefs;
175 : :
176 : : /* True when the statement contains a write to memory. */
177 : : bool has_mem_write;
178 : :
179 : : /* True when the statement contains a read from memory. */
180 : : bool has_mem_reads;
181 : : };
182 : :
183 : : #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
184 : : #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
185 : : #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
186 : : #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
187 : : #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
188 : : #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
189 : : #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
190 : : #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
191 : :
192 : : /* Data dependence type. */
193 : :
194 : : enum rdg_dep_type
195 : : {
196 : : /* Read After Write (RAW). */
197 : : flow_dd = 'f',
198 : :
199 : : /* Control dependence (execute conditional on). */
200 : : control_dd = 'c'
201 : : };
202 : :
203 : : /* Dependence information attached to an edge of the RDG. */
204 : :
205 : : struct rdg_edge
206 : : {
207 : : /* Type of the dependence. */
208 : : enum rdg_dep_type type;
209 : : };
210 : :
211 : : #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
212 : :
213 : : /* Kind of distributed loop. */
214 : : enum partition_kind {
215 : : PKIND_NORMAL,
216 : : /* Partial memset stands for a paritition can be distributed into a loop
217 : : of memset calls, rather than a single memset call. It's handled just
218 : : like a normal parition, i.e, distributed as separate loop, no memset
219 : : call is generated.
220 : :
221 : : Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
222 : : loop nest as deep as possible. As a result, parloop achieves better
223 : : parallelization by parallelizing deeper loop nest. This hack should
224 : : be unnecessary and removed once distributed memset can be understood
225 : : and analyzed in data reference analysis. See PR82604 for more. */
226 : : PKIND_PARTIAL_MEMSET,
227 : : PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
228 : : };
229 : :
230 : : /* Type of distributed loop. */
231 : : enum partition_type {
232 : : /* The distributed loop can be executed parallelly. */
233 : : PTYPE_PARALLEL = 0,
234 : : /* The distributed loop has to be executed sequentially. */
235 : : PTYPE_SEQUENTIAL
236 : : };
237 : :
238 : : /* Builtin info for loop distribution. */
239 : : struct builtin_info
240 : : {
241 : : /* data-references a kind != PKIND_NORMAL partition is about. */
242 : : data_reference_p dst_dr;
243 : : data_reference_p src_dr;
244 : : /* Base address and size of memory objects operated by the builtin. Note
245 : : both dest and source memory objects must have the same size. */
246 : : tree dst_base;
247 : : tree src_base;
248 : : tree size;
249 : : /* Base and offset part of dst_base after stripping constant offset. This
250 : : is only used in memset builtin distribution for now. */
251 : : tree dst_base_base;
252 : : unsigned HOST_WIDE_INT dst_base_offset;
253 : : };
254 : :
255 : : /* Partition for loop distribution. */
256 : : struct partition
257 : : {
258 : : /* Statements of the partition. */
259 : : bitmap stmts;
260 : : /* True if the partition defines variable which is used outside of loop. */
261 : : bool reduction_p;
262 : : location_t loc;
263 : : enum partition_kind kind;
264 : : enum partition_type type;
265 : : /* Data references in the partition. */
266 : : bitmap datarefs;
267 : : /* Information of builtin parition. */
268 : : struct builtin_info *builtin;
269 : : };
270 : :
271 : : /* Partitions are fused because of different reasons. */
272 : : enum fuse_type
273 : : {
274 : : FUSE_NON_BUILTIN = 0,
275 : : FUSE_REDUCTION = 1,
276 : : FUSE_SHARE_REF = 2,
277 : : FUSE_SAME_SCC = 3,
278 : : FUSE_FINALIZE = 4
279 : : };
280 : :
281 : : /* Description on different fusing reason. */
282 : : static const char *fuse_message[] = {
283 : : "they are non-builtins",
284 : : "they have reductions",
285 : : "they have shared memory refs",
286 : : "they are in the same dependence scc",
287 : : "there is no point to distribute loop"};
288 : :
289 : :
290 : : /* Dump vertex I in RDG to FILE. */
291 : :
292 : : static void
293 : 850 : dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
294 : : {
295 : 850 : struct vertex *v = &(rdg->vertices[i]);
296 : 850 : struct graph_edge *e;
297 : :
298 : 850 : fprintf (file, "(vertex %d: (%s%s) (in:", i,
299 : 850 : RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
300 : 850 : RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
301 : :
302 : 850 : if (v->pred)
303 : 2840 : for (e = v->pred; e; e = e->pred_next)
304 : 1990 : fprintf (file, " %d", e->src);
305 : :
306 : 850 : fprintf (file, ") (out:");
307 : :
308 : 850 : if (v->succ)
309 : 2698 : for (e = v->succ; e; e = e->succ_next)
310 : 1990 : fprintf (file, " %d", e->dest);
311 : :
312 : 850 : fprintf (file, ")\n");
313 : 850 : print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
314 : 850 : fprintf (file, ")\n");
315 : 850 : }
316 : :
317 : : /* Call dump_rdg_vertex on stderr. */
318 : :
319 : : DEBUG_FUNCTION void
320 : 0 : debug_rdg_vertex (struct graph *rdg, int i)
321 : : {
322 : 0 : dump_rdg_vertex (stderr, rdg, i);
323 : 0 : }
324 : :
325 : : /* Dump the reduced dependence graph RDG to FILE. */
326 : :
327 : : static void
328 : 67 : dump_rdg (FILE *file, struct graph *rdg)
329 : : {
330 : 67 : fprintf (file, "(rdg\n");
331 : 917 : for (int i = 0; i < rdg->n_vertices; i++)
332 : 850 : dump_rdg_vertex (file, rdg, i);
333 : 67 : fprintf (file, ")\n");
334 : 67 : }
335 : :
336 : : /* Call dump_rdg on stderr. */
337 : :
338 : : DEBUG_FUNCTION void
339 : 0 : debug_rdg (struct graph *rdg)
340 : : {
341 : 0 : dump_rdg (stderr, rdg);
342 : 0 : }
343 : :
344 : : static void
345 : 0 : dot_rdg_1 (FILE *file, struct graph *rdg)
346 : : {
347 : 0 : int i;
348 : 0 : pretty_printer pp;
349 : 0 : pp_needs_newline (&pp) = false;
350 : 0 : pp.set_output_stream (file);
351 : :
352 : 0 : fprintf (file, "digraph RDG {\n");
353 : :
354 : 0 : for (i = 0; i < rdg->n_vertices; i++)
355 : : {
356 : 0 : struct vertex *v = &(rdg->vertices[i]);
357 : 0 : struct graph_edge *e;
358 : :
359 : 0 : fprintf (file, "%d [label=\"[%d] ", i, i);
360 : 0 : pp_gimple_stmt_1 (&pp, RDGV_STMT (v), 0, TDF_SLIM);
361 : 0 : pp_flush (&pp);
362 : 0 : fprintf (file, "\"]\n");
363 : :
364 : : /* Highlight reads from memory. */
365 : 0 : if (RDG_MEM_READS_STMT (rdg, i))
366 : 0 : fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
367 : :
368 : : /* Highlight stores to memory. */
369 : 0 : if (RDG_MEM_WRITE_STMT (rdg, i))
370 : 0 : fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
371 : :
372 : 0 : if (v->succ)
373 : 0 : for (e = v->succ; e; e = e->succ_next)
374 : 0 : switch (RDGE_TYPE (e))
375 : : {
376 : 0 : case flow_dd:
377 : : /* These are the most common dependences: don't print these. */
378 : 0 : fprintf (file, "%d -> %d \n", i, e->dest);
379 : 0 : break;
380 : :
381 : 0 : case control_dd:
382 : 0 : fprintf (file, "%d -> %d [label=control] \n", i, e->dest);
383 : 0 : break;
384 : :
385 : 0 : default:
386 : 0 : gcc_unreachable ();
387 : : }
388 : : }
389 : :
390 : 0 : fprintf (file, "}\n\n");
391 : 0 : }
392 : :
393 : : /* Display the Reduced Dependence Graph using dotty. */
394 : :
395 : : DEBUG_FUNCTION void
396 : 0 : dot_rdg (struct graph *rdg)
397 : : {
398 : : /* When debugging, you may want to enable the following code. */
399 : : #ifdef HAVE_POPEN
400 : 0 : FILE *file = popen ("dot -Tx11", "w");
401 : 0 : if (!file)
402 : : return;
403 : 0 : dot_rdg_1 (file, rdg);
404 : 0 : fflush (file);
405 : 0 : close (fileno (file));
406 : 0 : pclose (file);
407 : : #else
408 : : dot_rdg_1 (stderr, rdg);
409 : : #endif
410 : : }
411 : :
412 : : /* Returns the index of STMT in RDG. */
413 : :
414 : : static int
415 : 13566956 : rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple *stmt)
416 : : {
417 : 13566956 : int index = gimple_uid (stmt);
418 : 13566956 : gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
419 : 13566956 : return index;
420 : : }
421 : :
422 : : /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
423 : : the index of DEF in RDG. */
424 : :
425 : : static void
426 : 1679297 : create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
427 : : {
428 : 1679297 : use_operand_p imm_use_p;
429 : 1679297 : imm_use_iterator iterator;
430 : :
431 : 4521815 : FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
432 : : {
433 : 2842518 : struct graph_edge *e;
434 : 2842518 : int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
435 : :
436 : 2842518 : if (use < 0)
437 : 390328 : continue;
438 : :
439 : 2452190 : e = add_edge (rdg, idef, use);
440 : 2452190 : e->data = XNEW (struct rdg_edge);
441 : 2452190 : RDGE_TYPE (e) = flow_dd;
442 : : }
443 : 1679297 : }
444 : :
445 : : /* Creates an edge for the control dependences of BB to the vertex V. */
446 : :
447 : : static void
448 : 2116182 : create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
449 : : int v, control_dependences *cd)
450 : : {
451 : 2116182 : bitmap_iterator bi;
452 : 2116182 : unsigned edge_n;
453 : 6037086 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
454 : : 0, edge_n, bi)
455 : : {
456 : 3920904 : basic_block cond_bb = cd->get_edge_src (edge_n);
457 : 3920904 : gimple *stmt = *gsi_last_bb (cond_bb);
458 : 3920904 : if (stmt && is_ctrl_stmt (stmt))
459 : : {
460 : 3515933 : struct graph_edge *e;
461 : 3515933 : int c = rdg_vertex_for_stmt (rdg, stmt);
462 : 3515933 : if (c < 0)
463 : 1151209 : continue;
464 : :
465 : 2364724 : e = add_edge (rdg, c, v);
466 : 2364724 : e->data = XNEW (struct rdg_edge);
467 : 2364724 : RDGE_TYPE (e) = control_dd;
468 : : }
469 : : }
470 : 2116182 : }
471 : :
472 : : /* Creates the edges of the reduced dependence graph RDG. */
473 : :
474 : : static void
475 : 133950 : create_rdg_flow_edges (struct graph *rdg)
476 : : {
477 : 133950 : int i;
478 : 133950 : def_operand_p def_p;
479 : 133950 : ssa_op_iter iter;
480 : :
481 : 2191968 : for (i = 0; i < rdg->n_vertices; i++)
482 : 5795333 : FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
483 : : iter, SSA_OP_DEF)
484 : 1679297 : create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
485 : 133950 : }
486 : :
487 : : /* Creates the edges of the reduced dependence graph RDG. */
488 : :
489 : : static void
490 : 126362 : create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop)
491 : : {
492 : 126362 : int i;
493 : :
494 : 2133239 : for (i = 0; i < rdg->n_vertices; i++)
495 : : {
496 : 2006877 : gimple *stmt = RDG_STMT (rdg, i);
497 : 2006877 : if (gimple_code (stmt) == GIMPLE_PHI)
498 : : {
499 : 390002 : edge_iterator ei;
500 : 390002 : edge e;
501 : 1166017 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
502 : 776015 : if (flow_bb_inside_loop_p (loop, e->src))
503 : 499307 : create_edge_for_control_dependence (rdg, e->src, i, cd);
504 : : }
505 : : else
506 : 1616875 : create_edge_for_control_dependence (rdg, gimple_bb (stmt), i, cd);
507 : : }
508 : 126362 : }
509 : :
510 : :
511 : : class loop_distribution
512 : : {
513 : : private:
514 : : /* The loop (nest) to be distributed. */
515 : : vec<loop_p> loop_nest;
516 : :
517 : : /* Vector of data references in the loop to be distributed. */
518 : : vec<data_reference_p> datarefs_vec;
519 : :
520 : : /* If there is nonaddressable data reference in above vector. */
521 : : bool has_nonaddressable_dataref_p;
522 : :
523 : : /* Store index of data reference in aux field. */
524 : :
525 : : /* Hash table for data dependence relation in the loop to be distributed. */
526 : : hash_table<ddr_hasher> *ddrs_table;
527 : :
528 : : /* Array mapping basic block's index to its topological order. */
529 : : int *bb_top_order_index;
530 : : /* And size of the array. */
531 : : int bb_top_order_index_size;
532 : :
533 : : /* Build the vertices of the reduced dependence graph RDG. Return false
534 : : if that failed. */
535 : : bool create_rdg_vertices (struct graph *rdg, const vec<gimple *> &stmts,
536 : : loop_p loop);
537 : :
538 : : /* Initialize STMTS with all the statements of LOOP. We use topological
539 : : order to discover all statements. The order is important because
540 : : generate_loops_for_partition is using the same traversal for identifying
541 : : statements in loop copies. */
542 : : void stmts_from_loop (class loop *loop, vec<gimple *> *stmts);
543 : :
544 : :
545 : : /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
546 : : LOOP, and one edge per flow dependence or control dependence from control
547 : : dependence CD. During visiting each statement, data references are also
548 : : collected and recorded in global data DATAREFS_VEC. */
549 : : struct graph * build_rdg (class loop *loop, control_dependences *cd);
550 : :
551 : : /* Merge PARTITION into the partition DEST. RDG is the reduced dependence
552 : : graph and we update type for result partition if it is non-NULL. */
553 : : void partition_merge_into (struct graph *rdg,
554 : : partition *dest, partition *partition,
555 : : enum fuse_type ft);
556 : :
557 : :
558 : : /* Return data dependence relation for data references A and B. The two
559 : : data references must be in lexicographic order wrto reduced dependence
560 : : graph RDG. We firstly try to find ddr from global ddr hash table. If
561 : : it doesn't exist, compute the ddr and cache it. */
562 : : data_dependence_relation * get_data_dependence (struct graph *rdg,
563 : : data_reference_p a,
564 : : data_reference_p b);
565 : :
566 : :
567 : : /* In reduced dependence graph RDG for loop distribution, return true if
568 : : dependence between references DR1 and DR2 leads to a dependence cycle
569 : : and such dependence cycle can't be resolved by runtime alias check. */
570 : : bool data_dep_in_cycle_p (struct graph *rdg, data_reference_p dr1,
571 : : data_reference_p dr2);
572 : :
573 : :
574 : : /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
575 : : PARTITION1's type after merging PARTITION2 into PARTITION1. */
576 : : void update_type_for_merge (struct graph *rdg,
577 : : partition *partition1, partition *partition2);
578 : :
579 : :
580 : : /* Returns a partition with all the statements needed for computing
581 : : the vertex V of the RDG, also including the loop exit conditions. */
582 : : partition *build_rdg_partition_for_vertex (struct graph *rdg, int v);
583 : :
584 : : /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
585 : : if it forms builtin memcpy or memmove call. */
586 : : void classify_builtin_ldst (loop_p loop, struct graph *rdg, partition *partition,
587 : : data_reference_p dst_dr, data_reference_p src_dr);
588 : :
589 : : /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
590 : : For the moment we detect memset, memcpy and memmove patterns. Bitmap
591 : : STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions.
592 : : Returns true if there is a reduction in all partitions and we
593 : : possibly did not mark PARTITION as having one for this reason. */
594 : :
595 : : bool
596 : : classify_partition (loop_p loop,
597 : : struct graph *rdg, partition *partition,
598 : : bitmap stmt_in_all_partitions);
599 : :
600 : :
601 : : /* Returns true when PARTITION1 and PARTITION2 access the same memory
602 : : object in RDG. */
603 : : bool share_memory_accesses (struct graph *rdg,
604 : : partition *partition1, partition *partition2);
605 : :
606 : : /* For each seed statement in STARTING_STMTS, this function builds
607 : : partition for it by adding depended statements according to RDG.
608 : : All partitions are recorded in PARTITIONS. */
609 : : void rdg_build_partitions (struct graph *rdg,
610 : : vec<gimple *> starting_stmts,
611 : : vec<partition *> *partitions);
612 : :
613 : : /* Compute partition dependence created by the data references in DRS1
614 : : and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
615 : : not NULL, we record dependence introduced by possible alias between
616 : : two data references in ALIAS_DDRS; otherwise, we simply ignore such
617 : : dependence as if it doesn't exist at all. */
618 : : int pg_add_dependence_edges (struct graph *rdg, int dir, bitmap drs1,
619 : : bitmap drs2, vec<ddr_p> *alias_ddrs);
620 : :
621 : :
622 : : /* Build and return partition dependence graph for PARTITIONS. RDG is
623 : : reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
624 : : is true, data dependence caused by possible alias between references
625 : : is ignored, as if it doesn't exist at all; otherwise all depdendences
626 : : are considered. */
627 : : struct graph *build_partition_graph (struct graph *rdg,
628 : : vec<struct partition *> *partitions,
629 : : bool ignore_alias_p);
630 : :
631 : : /* Given reduced dependence graph RDG merge strong connected components
632 : : of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
633 : : possible alias between references is ignored, as if it doesn't exist
634 : : at all; otherwise all depdendences are considered. */
635 : : void merge_dep_scc_partitions (struct graph *rdg, vec<struct partition *>
636 : : *partitions, bool ignore_alias_p);
637 : :
638 : : /* This is the main function breaking strong conected components in
639 : : PARTITIONS giving reduced depdendence graph RDG. Store data dependence
640 : : relations for runtime alias check in ALIAS_DDRS. */
641 : : void break_alias_scc_partitions (struct graph *rdg, vec<struct partition *>
642 : : *partitions, vec<ddr_p> *alias_ddrs);
643 : :
644 : :
645 : : /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
646 : : ALIAS_DDRS contains ddrs which need runtime alias check. */
647 : : void finalize_partitions (class loop *loop, vec<struct partition *>
648 : : *partitions, vec<ddr_p> *alias_ddrs);
649 : :
650 : : /* Distributes the code from LOOP in such a way that producer statements
651 : : are placed before consumer statements. Tries to separate only the
652 : : statements from STMTS into separate loops. Returns the number of
653 : : distributed loops. Set NB_CALLS to number of generated builtin calls.
654 : : Set *DESTROY_P to whether LOOP needs to be destroyed. */
655 : : int distribute_loop (class loop *loop, const vec<gimple *> &stmts,
656 : : control_dependences *cd, int *nb_calls, bool *destroy_p,
657 : : bool only_patterns_p);
658 : :
659 : : /* Transform loops which mimic the effects of builtins rawmemchr or strlen and
660 : : replace them accordingly. */
661 : : bool transform_reduction_loop (loop_p loop);
662 : :
663 : : /* Compute topological order for basic blocks. Topological order is
664 : : needed because data dependence is computed for data references in
665 : : lexicographical order. */
666 : : void bb_top_order_init (void);
667 : :
668 : : void bb_top_order_destroy (void);
669 : :
670 : : public:
671 : :
672 : : /* Getter for bb_top_order. */
673 : :
674 : 2800032 : inline int get_bb_top_order_index_size (void)
675 : : {
676 : 2800032 : return bb_top_order_index_size;
677 : : }
678 : :
679 : 5600064 : inline int get_bb_top_order_index (int i)
680 : : {
681 : 5600064 : return bb_top_order_index[i];
682 : : }
683 : :
684 : : unsigned int execute (function *fun);
685 : : };
686 : :
687 : :
688 : : /* If X has a smaller topological sort number than Y, returns -1;
689 : : if greater, returns 1. */
690 : : static int
691 : 2800032 : bb_top_order_cmp_r (const void *x, const void *y, void *loop)
692 : : {
693 : 2800032 : loop_distribution *_loop =
694 : : (loop_distribution *) loop;
695 : :
696 : 2800032 : basic_block bb1 = *(const basic_block *) x;
697 : 2800032 : basic_block bb2 = *(const basic_block *) y;
698 : :
699 : 2800032 : int bb_top_order_index_size = _loop->get_bb_top_order_index_size ();
700 : :
701 : 2800032 : gcc_assert (bb1->index < bb_top_order_index_size
702 : : && bb2->index < bb_top_order_index_size);
703 : 2800032 : gcc_assert (bb1 == bb2
704 : : || _loop->get_bb_top_order_index(bb1->index)
705 : : != _loop->get_bb_top_order_index(bb2->index));
706 : :
707 : 2800032 : return (_loop->get_bb_top_order_index(bb1->index) -
708 : 2800032 : _loop->get_bb_top_order_index(bb2->index));
709 : : }
710 : :
711 : : bool
712 : 137122 : loop_distribution::create_rdg_vertices (struct graph *rdg,
713 : : const vec<gimple *> &stmts,
714 : : loop_p loop)
715 : : {
716 : 137122 : int i;
717 : 137122 : gimple *stmt;
718 : :
719 : 2216625 : FOR_EACH_VEC_ELT (stmts, i, stmt)
720 : : {
721 : 2082675 : struct vertex *v = &(rdg->vertices[i]);
722 : :
723 : : /* Record statement to vertex mapping. */
724 : 2082675 : gimple_set_uid (stmt, i);
725 : :
726 : 2082675 : v->data = XNEW (struct rdg_vertex);
727 : 2082675 : RDGV_STMT (v) = stmt;
728 : 2082675 : RDGV_DATAREFS (v).create (0);
729 : 2082675 : RDGV_HAS_MEM_WRITE (v) = false;
730 : 2082675 : RDGV_HAS_MEM_READS (v) = false;
731 : 2082675 : if (gimple_code (stmt) == GIMPLE_PHI)
732 : 413715 : continue;
733 : :
734 : 1668960 : unsigned drp = datarefs_vec.length ();
735 : 1668960 : if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec))
736 : : return false;
737 : 2483511 : for (unsigned j = drp; j < datarefs_vec.length (); ++j)
738 : : {
739 : 404008 : data_reference_p dr = datarefs_vec[j];
740 : 404008 : if (DR_IS_READ (dr))
741 : 225630 : RDGV_HAS_MEM_READS (v) = true;
742 : : else
743 : 178378 : RDGV_HAS_MEM_WRITE (v) = true;
744 : 404008 : RDGV_DATAREFS (v).safe_push (dr);
745 : 404008 : has_nonaddressable_dataref_p |= may_be_nonaddressable_p (dr->ref);
746 : : }
747 : : }
748 : : return true;
749 : : }
750 : :
751 : : void
752 : 137122 : loop_distribution::stmts_from_loop (class loop *loop, vec<gimple *> *stmts)
753 : : {
754 : 137122 : unsigned int i;
755 : 137122 : basic_block *bbs = get_loop_body_in_custom_order (loop, this, bb_top_order_cmp_r);
756 : :
757 : 586360 : for (i = 0; i < loop->num_nodes; i++)
758 : : {
759 : 449238 : basic_block bb = bbs[i];
760 : :
761 : 999873 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
762 : 550635 : gsi_next (&bsi))
763 : 1101270 : if (!virtual_operand_p (gimple_phi_result (bsi.phi ())))
764 : 414908 : stmts->safe_push (bsi.phi ());
765 : :
766 : 3457001 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
767 : 2558525 : gsi_next (&bsi))
768 : : {
769 : 2558525 : gimple *stmt = gsi_stmt (bsi);
770 : 2558525 : if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
771 : 1693775 : stmts->safe_push (stmt);
772 : : }
773 : : }
774 : :
775 : 137122 : free (bbs);
776 : 137122 : }
777 : :
778 : : /* Free the reduced dependence graph RDG. */
779 : :
780 : : static void
781 : 137122 : free_rdg (struct graph *rdg, loop_p loop)
782 : : {
783 : 137122 : int i;
784 : :
785 : 2245805 : for (i = 0; i < rdg->n_vertices; i++)
786 : : {
787 : 2108683 : struct vertex *v = &(rdg->vertices[i]);
788 : 2108683 : struct graph_edge *e;
789 : :
790 : 6925597 : for (e = v->succ; e; e = e->succ_next)
791 : 4816914 : free (e->data);
792 : :
793 : 2108683 : if (v->data)
794 : : {
795 : 2082675 : (RDGV_DATAREFS (v)).release ();
796 : 2082675 : free (v->data);
797 : : }
798 : : }
799 : :
800 : 137122 : free_graph (rdg);
801 : :
802 : : /* Reset UIDs of stmts still in the loop. */
803 : 137122 : basic_block *bbs = get_loop_body (loop);
804 : 586360 : for (unsigned i = 0; i < loop->num_nodes; ++i)
805 : : {
806 : 449238 : basic_block bb = bbs[i];
807 : 449238 : gimple_stmt_iterator gsi;
808 : 999824 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
809 : 550586 : gimple_set_uid (gsi_stmt (gsi), -1);
810 : 3454235 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
811 : 2555759 : gimple_set_uid (gsi_stmt (gsi), -1);
812 : : }
813 : 137122 : free (bbs);
814 : 137122 : }
815 : :
816 : : struct graph *
817 : 137122 : loop_distribution::build_rdg (class loop *loop, control_dependences *cd)
818 : : {
819 : 137122 : struct graph *rdg;
820 : :
821 : : /* Create the RDG vertices from the stmts of the loop nest. */
822 : 137122 : auto_vec<gimple *, 10> stmts;
823 : 137122 : stmts_from_loop (loop, &stmts);
824 : 274244 : rdg = new_graph (stmts.length ());
825 : 137122 : if (!create_rdg_vertices (rdg, stmts, loop))
826 : : {
827 : 3172 : free_rdg (rdg, loop);
828 : 3172 : return NULL;
829 : : }
830 : 133950 : stmts.release ();
831 : :
832 : 133950 : create_rdg_flow_edges (rdg);
833 : 133950 : if (cd)
834 : 126362 : create_rdg_cd_edges (rdg, cd, loop);
835 : :
836 : : return rdg;
837 : 137122 : }
838 : :
839 : :
840 : : /* Allocate and initialize a partition from BITMAP. */
841 : :
842 : : static partition *
843 : 221264 : partition_alloc (void)
844 : : {
845 : 221264 : partition *partition = XCNEW (struct partition);
846 : 221264 : partition->stmts = BITMAP_ALLOC (NULL);
847 : 221264 : partition->reduction_p = false;
848 : 221264 : partition->loc = UNKNOWN_LOCATION;
849 : 221264 : partition->kind = PKIND_NORMAL;
850 : 221264 : partition->type = PTYPE_PARALLEL;
851 : 221264 : partition->datarefs = BITMAP_ALLOC (NULL);
852 : 221264 : return partition;
853 : : }
854 : :
855 : : /* Free PARTITION. */
856 : :
857 : : static void
858 : 221264 : partition_free (partition *partition)
859 : : {
860 : 221264 : BITMAP_FREE (partition->stmts);
861 : 221264 : BITMAP_FREE (partition->datarefs);
862 : 221264 : if (partition->builtin)
863 : 12067 : free (partition->builtin);
864 : :
865 : 221264 : free (partition);
866 : 221264 : }
867 : :
868 : : /* Returns true if the partition can be generated as a builtin. */
869 : :
870 : : static bool
871 : 320551 : partition_builtin_p (partition *partition)
872 : : {
873 : 320551 : return partition->kind > PKIND_PARTIAL_MEMSET;
874 : : }
875 : :
876 : : /* Returns true if the partition contains a reduction. */
877 : :
878 : : static bool
879 : 2685567 : partition_reduction_p (partition *partition)
880 : : {
881 : 2685567 : return partition->reduction_p;
882 : : }
883 : :
884 : : void
885 : 30014 : loop_distribution::partition_merge_into (struct graph *rdg,
886 : : partition *dest, partition *partition, enum fuse_type ft)
887 : : {
888 : 30014 : if (dump_file && (dump_flags & TDF_DETAILS))
889 : : {
890 : 42 : fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]);
891 : 42 : fprintf (dump_file, " Part 1: ");
892 : 42 : dump_bitmap (dump_file, dest->stmts);
893 : 42 : fprintf (dump_file, " Part 2: ");
894 : 42 : dump_bitmap (dump_file, partition->stmts);
895 : : }
896 : :
897 : 30014 : dest->kind = PKIND_NORMAL;
898 : 30014 : if (dest->type == PTYPE_PARALLEL)
899 : 24338 : dest->type = partition->type;
900 : :
901 : 30014 : bitmap_ior_into (dest->stmts, partition->stmts);
902 : 30014 : if (partition_reduction_p (partition))
903 : 3192 : dest->reduction_p = true;
904 : :
905 : : /* Further check if any data dependence prevents us from executing the
906 : : new partition parallelly. */
907 : 30014 : if (dest->type == PTYPE_PARALLEL && rdg != NULL)
908 : 5912 : update_type_for_merge (rdg, dest, partition);
909 : :
910 : 30014 : bitmap_ior_into (dest->datarefs, partition->datarefs);
911 : 30014 : }
912 : :
913 : :
914 : : /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
915 : : the LOOP. */
916 : :
917 : : static bool
918 : 4504834 : ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
919 : : {
920 : 4504834 : imm_use_iterator imm_iter;
921 : 4504834 : use_operand_p use_p;
922 : :
923 : 13173651 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
924 : : {
925 : 8796618 : if (is_gimple_debug (USE_STMT (use_p)))
926 : 840852 : continue;
927 : :
928 : 7955766 : basic_block use_bb = gimple_bb (USE_STMT (use_p));
929 : 7955766 : if (!flow_bb_inside_loop_p (loop, use_bb))
930 : : return true;
931 : : }
932 : :
933 : : return false;
934 : : }
935 : :
936 : : /* Returns true when STMT defines a scalar variable used after the
937 : : loop LOOP. */
938 : :
939 : : static bool
940 : 6329617 : stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple *stmt)
941 : : {
942 : 6329617 : def_operand_p def_p;
943 : 6329617 : ssa_op_iter op_iter;
944 : :
945 : 6329617 : if (gimple_code (stmt) == GIMPLE_PHI)
946 : 1095855 : return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop);
947 : :
948 : 8570697 : FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
949 : 3408979 : if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop))
950 : : return true;
951 : :
952 : : return false;
953 : : }
954 : :
955 : : /* Return a copy of LOOP placed before LOOP. */
956 : :
957 : : static class loop *
958 : 1007 : copy_loop_before (class loop *loop, bool redirect_lc_phi_defs)
959 : : {
960 : 1007 : class loop *res;
961 : 1007 : edge preheader = loop_preheader_edge (loop);
962 : :
963 : 1007 : initialize_original_copy_tables ();
964 : 1007 : res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, single_exit (loop), NULL,
965 : : NULL, preheader, NULL, false);
966 : 1007 : gcc_assert (res != NULL);
967 : :
968 : : /* When a not last partition is supposed to keep the LC PHIs computed
969 : : adjust their definitions. */
970 : 1007 : if (redirect_lc_phi_defs)
971 : : {
972 : 3 : edge exit = single_exit (loop);
973 : 14 : for (gphi_iterator si = gsi_start_phis (exit->dest); !gsi_end_p (si);
974 : 11 : gsi_next (&si))
975 : : {
976 : 11 : gphi *phi = si.phi ();
977 : 22 : if (virtual_operand_p (gimple_phi_result (phi)))
978 : 3 : continue;
979 : 8 : use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
980 : 8 : if (TREE_CODE (USE_FROM_PTR (use_p)) == SSA_NAME)
981 : : {
982 : 5 : tree new_def = get_current_def (USE_FROM_PTR (use_p));
983 : 5 : if (!new_def)
984 : : /* Something defined outside of the loop. */
985 : 2 : continue;
986 : 3 : SET_USE (use_p, new_def);
987 : : }
988 : : }
989 : : }
990 : :
991 : 1007 : free_original_copy_tables ();
992 : 1007 : delete_update_ssa ();
993 : :
994 : 1007 : return res;
995 : : }
996 : :
997 : : /* Creates an empty basic block after LOOP. */
998 : :
999 : : static void
1000 : 1007 : create_bb_after_loop (class loop *loop)
1001 : : {
1002 : 1007 : edge exit = single_exit (loop);
1003 : :
1004 : 1007 : if (!exit)
1005 : : return;
1006 : :
1007 : 1007 : split_edge (exit);
1008 : : }
1009 : :
1010 : : /* Generate code for PARTITION from the code in LOOP. The loop is
1011 : : copied when COPY_P is true. All the statements not flagged in the
1012 : : PARTITION bitmap are removed from the loop or from its copy. The
1013 : : statements are indexed in sequence inside a basic block, and the
1014 : : basic blocks of a loop are taken in dom order. */
1015 : :
1016 : : static void
1017 : 2767 : generate_loops_for_partition (class loop *loop, partition *partition,
1018 : : bool copy_p, bool keep_lc_phis_p)
1019 : : {
1020 : 2767 : unsigned i;
1021 : 2767 : basic_block *bbs;
1022 : :
1023 : 2767 : if (copy_p)
1024 : : {
1025 : 1007 : int orig_loop_num = loop->orig_loop_num;
1026 : 1007 : loop = copy_loop_before (loop, keep_lc_phis_p);
1027 : 1007 : gcc_assert (loop != NULL);
1028 : 1007 : loop->orig_loop_num = orig_loop_num;
1029 : 1007 : create_preheader (loop, CP_SIMPLE_PREHEADERS);
1030 : 1007 : create_bb_after_loop (loop);
1031 : : }
1032 : : else
1033 : : {
1034 : : /* Origin number is set to the new versioned loop's num. */
1035 : 1760 : gcc_assert (loop->orig_loop_num != loop->num);
1036 : : }
1037 : :
1038 : : /* Remove stmts not in the PARTITION bitmap. */
1039 : 2767 : bbs = get_loop_body_in_dom_order (loop);
1040 : :
1041 : 2767 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1042 : 7039 : for (i = 0; i < loop->num_nodes; i++)
1043 : : {
1044 : 5403 : basic_block bb = bbs[i];
1045 : :
1046 : 10238 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
1047 : 4835 : gsi_next (&bsi))
1048 : : {
1049 : 4835 : gphi *phi = bsi.phi ();
1050 : 8024 : if (!virtual_operand_p (gimple_phi_result (phi))
1051 : 4835 : && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
1052 : 320 : reset_debug_uses (phi);
1053 : : }
1054 : :
1055 : 44796 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1056 : : {
1057 : 33990 : gimple *stmt = gsi_stmt (bsi);
1058 : 33990 : if (gimple_code (stmt) != GIMPLE_LABEL
1059 : 33990 : && !is_gimple_debug (stmt)
1060 : 55472 : && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
1061 : 5627 : reset_debug_uses (stmt);
1062 : : }
1063 : : }
1064 : :
1065 : 12257 : for (i = 0; i < loop->num_nodes; i++)
1066 : : {
1067 : 9490 : basic_block bb = bbs[i];
1068 : 9490 : edge inner_exit = NULL;
1069 : :
1070 : 9490 : if (loop != bb->loop_father)
1071 : 116 : inner_exit = single_exit (bb->loop_father);
1072 : :
1073 : 18029 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
1074 : : {
1075 : 8539 : gphi *phi = bsi.phi ();
1076 : 14189 : if (!virtual_operand_p (gimple_phi_result (phi))
1077 : 8539 : && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
1078 : 752 : remove_phi_node (&bsi, true);
1079 : : else
1080 : 7787 : gsi_next (&bsi);
1081 : : }
1082 : :
1083 : 69702 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
1084 : : {
1085 : 50722 : gimple *stmt = gsi_stmt (bsi);
1086 : 50722 : if (gimple_code (stmt) != GIMPLE_LABEL
1087 : 50714 : && !is_gimple_debug (stmt)
1088 : 88928 : && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
1089 : : {
1090 : : /* In distribution of loop nest, if bb is inner loop's exit_bb,
1091 : : we choose its exit edge/path in order to avoid generating
1092 : : infinite loop. For all other cases, we choose an arbitrary
1093 : : path through the empty CFG part that this unnecessary
1094 : : control stmt controls. */
1095 : 11752 : if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1096 : : {
1097 : 572 : if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
1098 : 5 : gimple_cond_make_true (cond_stmt);
1099 : : else
1100 : 567 : gimple_cond_make_false (cond_stmt);
1101 : 572 : update_stmt (stmt);
1102 : : }
1103 : 11180 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1104 : : {
1105 : 0 : gswitch *switch_stmt = as_a <gswitch *> (stmt);
1106 : 0 : gimple_switch_set_index
1107 : 0 : (switch_stmt, CASE_LOW (gimple_switch_label (switch_stmt, 1)));
1108 : 0 : update_stmt (stmt);
1109 : : }
1110 : : else
1111 : : {
1112 : 11180 : unlink_stmt_vdef (stmt);
1113 : 11180 : gsi_remove (&bsi, true);
1114 : 11180 : release_defs (stmt);
1115 : 11180 : continue;
1116 : : }
1117 : : }
1118 : 39542 : gsi_next (&bsi);
1119 : : }
1120 : : }
1121 : :
1122 : 2767 : free (bbs);
1123 : 2767 : }
1124 : :
1125 : : /* If VAL memory representation contains the same value in all bytes,
1126 : : return that value, otherwise return -1.
1127 : : E.g. for 0x24242424 return 0x24, for IEEE double
1128 : : 747708026454360457216.0 return 0x44, etc. */
1129 : :
1130 : : static int
1131 : 64837 : const_with_all_bytes_same (tree val)
1132 : : {
1133 : 64837 : unsigned char buf[64];
1134 : 64837 : int i, len;
1135 : :
1136 : 64837 : if (integer_zerop (val)
1137 : 64837 : || (TREE_CODE (val) == CONSTRUCTOR
1138 : 1052 : && !TREE_CLOBBER_P (val)
1139 : 23037 : && CONSTRUCTOR_NELTS (val) == 0))
1140 : : return 0;
1141 : :
1142 : 43957 : if (real_zerop (val))
1143 : : {
1144 : : /* Only return 0 for +0.0, not for -0.0, which doesn't have
1145 : : an all bytes same memory representation. Don't transform
1146 : : -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
1147 : 2185 : switch (TREE_CODE (val))
1148 : : {
1149 : 2178 : case REAL_CST:
1150 : 2178 : if (!real_isneg (TREE_REAL_CST_PTR (val)))
1151 : : return 0;
1152 : : break;
1153 : 0 : case COMPLEX_CST:
1154 : 0 : if (!const_with_all_bytes_same (TREE_REALPART (val))
1155 : 0 : && !const_with_all_bytes_same (TREE_IMAGPART (val)))
1156 : : return 0;
1157 : : break;
1158 : 7 : case VECTOR_CST:
1159 : 7 : {
1160 : 7 : unsigned int count = vector_cst_encoded_nelts (val);
1161 : 7 : unsigned int j;
1162 : 21 : for (j = 0; j < count; ++j)
1163 : 14 : if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val, j)))
1164 : : break;
1165 : 7 : if (j == count)
1166 : : return 0;
1167 : : break;
1168 : : }
1169 : : default:
1170 : : break;
1171 : : }
1172 : : }
1173 : :
1174 : 41800 : if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
1175 : : return -1;
1176 : :
1177 : 41800 : len = native_encode_expr (val, buf, sizeof (buf));
1178 : 41800 : if (len == 0)
1179 : : return -1;
1180 : 26807 : for (i = 1; i < len; i++)
1181 : 23520 : if (buf[i] != buf[0])
1182 : : return -1;
1183 : 3287 : return buf[0];
1184 : : }
1185 : :
1186 : : /* Generate a call to memset for PARTITION in LOOP. */
1187 : :
1188 : : static void
1189 : 7218 : generate_memset_builtin (class loop *loop, partition *partition)
1190 : : {
1191 : 7218 : gimple_stmt_iterator gsi;
1192 : 7218 : tree mem, fn, nb_bytes;
1193 : 7218 : tree val;
1194 : 7218 : struct builtin_info *builtin = partition->builtin;
1195 : 7218 : gimple *fn_call;
1196 : :
1197 : : /* The new statements will be placed before LOOP. */
1198 : 7218 : gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1199 : :
1200 : 7218 : nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1201 : 7218 : nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1202 : : false, GSI_CONTINUE_LINKING);
1203 : 7218 : mem = rewrite_to_non_trapping_overflow (builtin->dst_base);
1204 : 7218 : mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
1205 : : false, GSI_CONTINUE_LINKING);
1206 : :
1207 : : /* This exactly matches the pattern recognition in classify_partition. */
1208 : 7218 : val = gimple_assign_rhs1 (DR_STMT (builtin->dst_dr));
1209 : : /* Handle constants like 0x15151515 and similarly
1210 : : floating point constants etc. where all bytes are the same. */
1211 : 7218 : int bytev = const_with_all_bytes_same (val);
1212 : 7218 : if (bytev != -1)
1213 : 7119 : val = build_int_cst (integer_type_node, bytev);
1214 : 99 : else if (TREE_CODE (val) == INTEGER_CST)
1215 : 0 : val = fold_convert (integer_type_node, val);
1216 : 99 : else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
1217 : : {
1218 : 99 : tree tem = make_ssa_name (integer_type_node);
1219 : 99 : gimple *cstmt = gimple_build_assign (tem, NOP_EXPR, val);
1220 : 99 : gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
1221 : 99 : val = tem;
1222 : : }
1223 : :
1224 : 14436 : fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
1225 : 7218 : fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
1226 : 7218 : gimple_set_location (fn_call, partition->loc);
1227 : 7218 : gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1228 : 7218 : fold_stmt (&gsi);
1229 : :
1230 : 7218 : if (dump_file && (dump_flags & TDF_DETAILS))
1231 : : {
1232 : 36 : fprintf (dump_file, "generated memset");
1233 : 36 : if (bytev == 0)
1234 : 30 : fprintf (dump_file, " zero\n");
1235 : : else
1236 : 6 : fprintf (dump_file, "\n");
1237 : : }
1238 : 7218 : }
1239 : :
1240 : : /* Generate a call to memcpy for PARTITION in LOOP. */
1241 : :
1242 : : static void
1243 : 4343 : generate_memcpy_builtin (class loop *loop, partition *partition)
1244 : : {
1245 : 4343 : gimple_stmt_iterator gsi;
1246 : 4343 : gimple *fn_call;
1247 : 4343 : tree dest, src, fn, nb_bytes;
1248 : 4343 : enum built_in_function kind;
1249 : 4343 : struct builtin_info *builtin = partition->builtin;
1250 : :
1251 : : /* The new statements will be placed before LOOP. */
1252 : 4343 : gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1253 : :
1254 : 4343 : nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1255 : 4343 : nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1256 : : false, GSI_CONTINUE_LINKING);
1257 : 4343 : dest = rewrite_to_non_trapping_overflow (builtin->dst_base);
1258 : 4343 : src = rewrite_to_non_trapping_overflow (builtin->src_base);
1259 : 4343 : if (partition->kind == PKIND_MEMCPY
1260 : 4343 : || ! ptr_derefs_may_alias_p (dest, src))
1261 : : kind = BUILT_IN_MEMCPY;
1262 : : else
1263 : 170 : kind = BUILT_IN_MEMMOVE;
1264 : : /* Try harder if we're copying a constant size. */
1265 : 170 : if (kind == BUILT_IN_MEMMOVE && poly_int_tree_p (nb_bytes))
1266 : : {
1267 : 178 : aff_tree asrc, adest;
1268 : 89 : tree_to_aff_combination (src, ptr_type_node, &asrc);
1269 : 89 : tree_to_aff_combination (dest, ptr_type_node, &adest);
1270 : 89 : aff_combination_scale (&adest, -1);
1271 : 89 : aff_combination_add (&asrc, &adest);
1272 : 178 : if (aff_comb_cannot_overlap_p (&asrc, wi::to_poly_widest (nb_bytes),
1273 : 178 : wi::to_poly_widest (nb_bytes)))
1274 : 0 : kind = BUILT_IN_MEMCPY;
1275 : 89 : }
1276 : :
1277 : 4343 : dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
1278 : : false, GSI_CONTINUE_LINKING);
1279 : 4343 : src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
1280 : : false, GSI_CONTINUE_LINKING);
1281 : 4343 : fn = build_fold_addr_expr (builtin_decl_implicit (kind));
1282 : 4343 : fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
1283 : 4343 : gimple_set_location (fn_call, partition->loc);
1284 : 4343 : gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1285 : 4343 : fold_stmt (&gsi);
1286 : :
1287 : 4343 : if (dump_file && (dump_flags & TDF_DETAILS))
1288 : : {
1289 : 13 : if (kind == BUILT_IN_MEMCPY)
1290 : 10 : fprintf (dump_file, "generated memcpy\n");
1291 : : else
1292 : 3 : fprintf (dump_file, "generated memmove\n");
1293 : : }
1294 : 4343 : }
1295 : :
1296 : : /* Remove and destroy the loop LOOP. */
1297 : :
1298 : : static void
1299 : 9721 : destroy_loop (class loop *loop)
1300 : : {
1301 : 9721 : unsigned nbbs = loop->num_nodes;
1302 : 9721 : edge exit = single_exit (loop);
1303 : 9721 : basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
1304 : 9721 : basic_block *bbs;
1305 : 9721 : unsigned i;
1306 : :
1307 : 9721 : bbs = get_loop_body_in_dom_order (loop);
1308 : :
1309 : 9721 : gimple_stmt_iterator dst_gsi = gsi_after_labels (exit->dest);
1310 : 9721 : bool safe_p = single_pred_p (exit->dest);
1311 : 30548 : for (unsigned i = 0; i < nbbs; ++i)
1312 : : {
1313 : : /* We have made sure to not leave any dangling uses of SSA
1314 : : names defined in the loop. With the exception of virtuals.
1315 : : Make sure we replace all uses of virtual defs that will remain
1316 : : outside of the loop with the bare symbol as delete_basic_block
1317 : : will release them. */
1318 : 49344 : for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi);
1319 : 28517 : gsi_next (&gsi))
1320 : : {
1321 : 28517 : gphi *phi = gsi.phi ();
1322 : 67626 : if (virtual_operand_p (gimple_phi_result (phi)))
1323 : 10592 : mark_virtual_phi_result_for_renaming (phi);
1324 : : }
1325 : 122287 : for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);)
1326 : : {
1327 : 80633 : gimple *stmt = gsi_stmt (gsi);
1328 : 80633 : tree vdef = gimple_vdef (stmt);
1329 : 46293 : if (vdef && TREE_CODE (vdef) == SSA_NAME)
1330 : 11076 : mark_virtual_operand_for_renaming (vdef);
1331 : : /* Also move and eventually reset debug stmts. We can leave
1332 : : constant values in place in case the stmt dominates the exit.
1333 : : ??? Non-constant values from the last iteration can be
1334 : : replaced with final values if we can compute them. */
1335 : 80633 : if (gimple_debug_bind_p (stmt))
1336 : : {
1337 : 16527 : tree val = gimple_debug_bind_get_value (stmt);
1338 : 16527 : gsi_move_before (&gsi, &dst_gsi);
1339 : 16527 : if (val
1340 : 16527 : && (!safe_p
1341 : 9696 : || !is_gimple_min_invariant (val)
1342 : 682 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bbs[i])))
1343 : : {
1344 : 9037 : gimple_debug_bind_reset_value (stmt);
1345 : 9037 : update_stmt (stmt);
1346 : : }
1347 : : }
1348 : : else
1349 : 64106 : gsi_next (&gsi);
1350 : : }
1351 : : }
1352 : :
1353 : 9721 : redirect_edge_pred (exit, src);
1354 : 9721 : exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
1355 : 9721 : exit->flags |= EDGE_FALLTHRU;
1356 : 9721 : cancel_loop_tree (loop);
1357 : 9721 : rescan_loop_exit (exit, false, true);
1358 : :
1359 : 9721 : i = nbbs;
1360 : 20827 : do
1361 : : {
1362 : 20827 : --i;
1363 : 20827 : delete_basic_block (bbs[i]);
1364 : : }
1365 : 20827 : while (i != 0);
1366 : :
1367 : 9721 : free (bbs);
1368 : :
1369 : 9721 : set_immediate_dominator (CDI_DOMINATORS, dest,
1370 : : recompute_dominator (CDI_DOMINATORS, dest));
1371 : 9721 : }
1372 : :
1373 : : /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1374 : :
1375 : : static bool
1376 : 14328 : generate_code_for_partition (class loop *loop,
1377 : : partition *partition, bool copy_p,
1378 : : bool keep_lc_phis_p)
1379 : : {
1380 : 14328 : switch (partition->kind)
1381 : : {
1382 : 2767 : case PKIND_NORMAL:
1383 : 2767 : case PKIND_PARTIAL_MEMSET:
1384 : : /* Reductions all have to be in the last partition. */
1385 : 2767 : gcc_assert (!partition_reduction_p (partition)
1386 : : || !copy_p);
1387 : 2767 : generate_loops_for_partition (loop, partition, copy_p,
1388 : : keep_lc_phis_p);
1389 : 2767 : return false;
1390 : :
1391 : 7218 : case PKIND_MEMSET:
1392 : 7218 : generate_memset_builtin (loop, partition);
1393 : 7218 : break;
1394 : :
1395 : 4343 : case PKIND_MEMCPY:
1396 : 4343 : case PKIND_MEMMOVE:
1397 : 4343 : generate_memcpy_builtin (loop, partition);
1398 : 4343 : break;
1399 : :
1400 : 0 : default:
1401 : 0 : gcc_unreachable ();
1402 : : }
1403 : :
1404 : : /* Common tail for partitions we turn into a call. If this was the last
1405 : : partition for which we generate code, we have to destroy the loop. */
1406 : 11561 : if (!copy_p)
1407 : : return true;
1408 : : return false;
1409 : : }
1410 : :
1411 : : data_dependence_relation *
1412 : 1750288 : loop_distribution::get_data_dependence (struct graph *rdg, data_reference_p a,
1413 : : data_reference_p b)
1414 : : {
1415 : 1750288 : struct data_dependence_relation ent, **slot;
1416 : 1750288 : struct data_dependence_relation *ddr;
1417 : :
1418 : 1750288 : gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
1419 : 1750288 : gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
1420 : : <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
1421 : 1750288 : ent.a = a;
1422 : 1750288 : ent.b = b;
1423 : 1750288 : slot = ddrs_table->find_slot (&ent, INSERT);
1424 : 1750288 : if (*slot == NULL)
1425 : : {
1426 : 992018 : ddr = initialize_data_dependence_relation (a, b, loop_nest);
1427 : 992018 : compute_affine_dependence (ddr, loop_nest[0]);
1428 : 992018 : *slot = ddr;
1429 : : }
1430 : :
1431 : 1750288 : return *slot;
1432 : : }
1433 : :
1434 : : bool
1435 : 245041 : loop_distribution::data_dep_in_cycle_p (struct graph *rdg,
1436 : : data_reference_p dr1,
1437 : : data_reference_p dr2)
1438 : : {
1439 : 245041 : struct data_dependence_relation *ddr;
1440 : :
1441 : : /* Re-shuffle data-refs to be in topological order. */
1442 : 490082 : if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1443 : 245041 : > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1444 : 48175 : std::swap (dr1, dr2);
1445 : :
1446 : 245041 : ddr = get_data_dependence (rdg, dr1, dr2);
1447 : :
1448 : : /* In case of no data dependence. */
1449 : 245041 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1450 : : return false;
1451 : : /* For unknown data dependence or known data dependence which can't be
1452 : : expressed in classic distance vector, we check if it can be resolved
1453 : : by runtime alias check. If yes, we still consider data dependence
1454 : : as won't introduce data dependence cycle. */
1455 : 86147 : else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1456 : 86147 : || DDR_NUM_DIST_VECTS (ddr) == 0)
1457 : 45945 : return !runtime_alias_check_p (ddr, NULL, true);
1458 : 40202 : else if (DDR_NUM_DIST_VECTS (ddr) > 1)
1459 : : return true;
1460 : 35718 : else if (DDR_REVERSED_P (ddr)
1461 : 104992 : || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)))
1462 : 31377 : return false;
1463 : :
1464 : : return true;
1465 : : }
1466 : :
1467 : : void
1468 : 213062 : loop_distribution::update_type_for_merge (struct graph *rdg,
1469 : : partition *partition1,
1470 : : partition *partition2)
1471 : : {
1472 : 213062 : unsigned i, j;
1473 : 213062 : bitmap_iterator bi, bj;
1474 : 213062 : data_reference_p dr1, dr2;
1475 : :
1476 : 656192 : EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1477 : : {
1478 : 451956 : unsigned start = (partition1 == partition2) ? i + 1 : 0;
1479 : :
1480 : 451956 : dr1 = datarefs_vec[i];
1481 : 1092420 : EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj)
1482 : : {
1483 : 649290 : dr2 = datarefs_vec[j];
1484 : 649290 : if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
1485 : 404249 : continue;
1486 : :
1487 : : /* Partition can only be executed sequentially if there is any
1488 : : data dependence cycle. */
1489 : 245041 : if (data_dep_in_cycle_p (rdg, dr1, dr2))
1490 : : {
1491 : 8826 : partition1->type = PTYPE_SEQUENTIAL;
1492 : 8826 : return;
1493 : : }
1494 : : }
1495 : : }
1496 : : }
1497 : :
1498 : : partition *
1499 : 221264 : loop_distribution::build_rdg_partition_for_vertex (struct graph *rdg, int v)
1500 : : {
1501 : 221264 : partition *partition = partition_alloc ();
1502 : 221264 : auto_vec<int, 3> nodes;
1503 : 221264 : unsigned i, j;
1504 : 221264 : int x;
1505 : 221264 : data_reference_p dr;
1506 : :
1507 : 221264 : graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
1508 : :
1509 : 3175037 : FOR_EACH_VEC_ELT (nodes, i, x)
1510 : : {
1511 : 2953773 : bitmap_set_bit (partition->stmts, x);
1512 : :
1513 : 3878955 : for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j)
1514 : : {
1515 : 464507 : unsigned idx = (unsigned) DR_INDEX (dr);
1516 : 464507 : gcc_assert (idx < datarefs_vec.length ());
1517 : :
1518 : : /* Partition can only be executed sequentially if there is any
1519 : : unknown data reference. */
1520 : 464507 : if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
1521 : 439632 : || !DR_INIT (dr) || !DR_STEP (dr))
1522 : 24875 : partition->type = PTYPE_SEQUENTIAL;
1523 : :
1524 : 464507 : bitmap_set_bit (partition->datarefs, idx);
1525 : : }
1526 : : }
1527 : :
1528 : 221264 : if (partition->type == PTYPE_SEQUENTIAL)
1529 : : return partition;
1530 : :
1531 : : /* Further check if any data dependence prevents us from executing the
1532 : : partition parallelly. */
1533 : 207150 : update_type_for_merge (rdg, partition, partition);
1534 : :
1535 : 207150 : return partition;
1536 : 221264 : }
1537 : :
1538 : : /* Given PARTITION of LOOP and RDG, record single load/store data references
1539 : : for builtin partition in SRC_DR/DST_DR, return false if there is no such
1540 : : data references. */
1541 : :
1542 : : static bool
1543 : 203439 : find_single_drs (class loop *loop, struct graph *rdg, const bitmap &partition_stmts,
1544 : : data_reference_p *dst_dr, data_reference_p *src_dr)
1545 : : {
1546 : 203439 : unsigned i;
1547 : 203439 : data_reference_p single_ld = NULL, single_st = NULL;
1548 : 203439 : bitmap_iterator bi;
1549 : :
1550 : 2109596 : EXECUTE_IF_SET_IN_BITMAP (partition_stmts, 0, i, bi)
1551 : : {
1552 : 1965138 : gimple *stmt = RDG_STMT (rdg, i);
1553 : 1965138 : data_reference_p dr;
1554 : :
1555 : 1965138 : if (gimple_code (stmt) == GIMPLE_PHI)
1556 : 440678 : continue;
1557 : :
1558 : : /* Any scalar stmts are ok. */
1559 : 2843774 : if (!gimple_vuse (stmt))
1560 : 1205162 : continue;
1561 : :
1562 : : /* Otherwise just regular loads/stores. */
1563 : 319298 : if (!gimple_assign_single_p (stmt))
1564 : 203439 : return false;
1565 : :
1566 : : /* But exactly one store and/or load. */
1567 : 2488954 : for (unsigned j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j)
1568 : : {
1569 : 322501 : tree type = TREE_TYPE (DR_REF (dr));
1570 : :
1571 : : /* The memset, memcpy and memmove library calls are only
1572 : : able to deal with generic address space. */
1573 : 322501 : if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type)))
1574 : : return false;
1575 : :
1576 : 322483 : if (DR_IS_READ (dr))
1577 : : {
1578 : 195710 : if (single_ld != NULL)
1579 : : return false;
1580 : : single_ld = dr;
1581 : : }
1582 : : else
1583 : : {
1584 : 126773 : if (single_st != NULL)
1585 : : return false;
1586 : : single_st = dr;
1587 : : }
1588 : : }
1589 : : }
1590 : :
1591 : 144458 : if (!single_ld && !single_st)
1592 : : return false;
1593 : :
1594 : 138933 : basic_block bb_ld = NULL;
1595 : 138933 : basic_block bb_st = NULL;
1596 : 138933 : edge exit = single_exit (loop);
1597 : :
1598 : 138933 : if (single_ld)
1599 : : {
1600 : : /* Bail out if this is a bitfield memory reference. */
1601 : 77843 : if (TREE_CODE (DR_REF (single_ld)) == COMPONENT_REF
1602 : 77843 : && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld), 1)))
1603 : : return false;
1604 : :
1605 : : /* Data reference must be executed exactly once per iteration of each
1606 : : loop in the loop nest. We only need to check dominance information
1607 : : against the outermost one in a perfect loop nest because a bb can't
1608 : : dominate outermost loop's latch without dominating inner loop's. */
1609 : 77776 : bb_ld = gimple_bb (DR_STMT (single_ld));
1610 : 77776 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld))
1611 : : return false;
1612 : :
1613 : : /* The data reference must also be executed before possibly exiting
1614 : : the loop as otherwise we'd for example unconditionally execute
1615 : : memset (ptr, 0, n) which even with n == 0 implies ptr is non-NULL. */
1616 : 71551 : if (bb_ld != loop->header
1617 : 71551 : && (!exit
1618 : 9609 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bb_ld)))
1619 : 1983 : return false;
1620 : : }
1621 : :
1622 : 130658 : if (single_st)
1623 : : {
1624 : : /* Bail out if this is a bitfield memory reference. */
1625 : 117768 : if (TREE_CODE (DR_REF (single_st)) == COMPONENT_REF
1626 : 117768 : && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1)))
1627 : : return false;
1628 : :
1629 : : /* Data reference must be executed exactly once per iteration.
1630 : : Same as single_ld, we only need to check against the outermost
1631 : : loop. */
1632 : 117683 : bb_st = gimple_bb (DR_STMT (single_st));
1633 : 117683 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st))
1634 : : return false;
1635 : :
1636 : : /* And before exiting the loop. */
1637 : 113477 : if (bb_st != loop->header
1638 : 113477 : && (!exit
1639 : 16318 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bb_st)))
1640 : 1008 : return false;
1641 : : }
1642 : :
1643 : 125359 : if (single_ld && single_st)
1644 : : {
1645 : : /* Load and store must be in the same loop nest. */
1646 : 54993 : if (bb_st->loop_father != bb_ld->loop_father)
1647 : : return false;
1648 : :
1649 : 54443 : edge e = single_exit (bb_st->loop_father);
1650 : 54443 : bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld);
1651 : 54443 : bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st);
1652 : 54443 : if (dom_ld != dom_st)
1653 : : return false;
1654 : : }
1655 : :
1656 : 124809 : *src_dr = single_ld;
1657 : 124809 : *dst_dr = single_st;
1658 : 124809 : return true;
1659 : : }
1660 : :
1661 : : /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1662 : : loops from inner to outer to see if loop's step equals to access size at
1663 : : each level of loop. Return 2 if we can prove this at all level loops;
1664 : : record access base and size in BASE and SIZE; save loop's step at each
1665 : : level of loop in STEPS if it is not null. For example:
1666 : :
1667 : : int arr[100][100][100];
1668 : : for (i = 0; i < 100; i++) ;steps[2] = 40000
1669 : : for (j = 100; j > 0; j--) ;steps[1] = -400
1670 : : for (k = 0; k < 100; k++) ;steps[0] = 4
1671 : : arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1672 : :
1673 : : Return 1 if we can prove the equality at the innermost loop, but not all
1674 : : level loops. In this case, no information is recorded.
1675 : :
1676 : : Return 0 if no equality can be proven at any level loops. */
1677 : :
1678 : : static int
1679 : 66866 : compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
1680 : : tree *size, vec<tree> *steps = NULL)
1681 : : {
1682 : 66866 : location_t loc = gimple_location (DR_STMT (dr));
1683 : 66866 : basic_block bb = gimple_bb (DR_STMT (dr));
1684 : 66866 : class loop *loop = bb->loop_father;
1685 : 66866 : tree ref = DR_REF (dr);
1686 : 66866 : tree access_base = build_fold_addr_expr (ref);
1687 : 66866 : tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1688 : 66866 : int res = 0;
1689 : :
1690 : 68253 : do {
1691 : 68253 : tree scev_fn = analyze_scalar_evolution (loop, access_base);
1692 : 68253 : if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
1693 : 33743 : return res;
1694 : :
1695 : 66794 : access_base = CHREC_LEFT (scev_fn);
1696 : 66794 : if (tree_contains_chrecs (access_base, NULL))
1697 : : return res;
1698 : :
1699 : 66794 : tree scev_step = CHREC_RIGHT (scev_fn);
1700 : : /* Only support constant steps. */
1701 : 66794 : if (TREE_CODE (scev_step) != INTEGER_CST)
1702 : : return res;
1703 : :
1704 : 62209 : enum ev_direction access_dir = scev_direction (scev_fn);
1705 : 62209 : if (access_dir == EV_DIR_UNKNOWN)
1706 : : return res;
1707 : :
1708 : 62209 : if (steps != NULL)
1709 : 44603 : steps->safe_push (scev_step);
1710 : :
1711 : 62209 : scev_step = fold_convert_loc (loc, sizetype, scev_step);
1712 : : /* Compute absolute value of scev step. */
1713 : 62209 : if (access_dir == EV_DIR_DECREASES)
1714 : 2070 : scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
1715 : :
1716 : : /* At each level of loop, scev step must equal to access size. In other
1717 : : words, DR must access consecutive memory between loop iterations. */
1718 : 62209 : if (!operand_equal_p (scev_step, access_size, 0))
1719 : : return res;
1720 : :
1721 : : /* Access stride can be computed for data reference at least for the
1722 : : innermost loop. */
1723 : 34510 : res = 1;
1724 : :
1725 : : /* Compute DR's execution times in loop. */
1726 : 34510 : tree niters = number_of_latch_executions (loop);
1727 : 34510 : niters = fold_convert_loc (loc, sizetype, niters);
1728 : 34510 : if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
1729 : 34510 : niters = size_binop_loc (loc, PLUS_EXPR, niters, size_one_node);
1730 : :
1731 : : /* Compute DR's overall access size in loop. */
1732 : 34510 : access_size = fold_build2_loc (loc, MULT_EXPR, sizetype,
1733 : : niters, scev_step);
1734 : : /* Adjust base address in case of negative step. */
1735 : 34510 : if (access_dir == EV_DIR_DECREASES)
1736 : : {
1737 : 1069 : tree adj = fold_build2_loc (loc, MINUS_EXPR, sizetype,
1738 : : scev_step, access_size);
1739 : 1069 : access_base = fold_build_pointer_plus_loc (loc, access_base, adj);
1740 : : }
1741 : 34510 : } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
1742 : :
1743 : 33123 : *base = access_base;
1744 : 33123 : *size = access_size;
1745 : : /* Access stride can be computed for data reference at each level loop. */
1746 : 33123 : return 2;
1747 : : }
1748 : :
1749 : : /* Allocate and return builtin struct. Record information like DST_DR,
1750 : : SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1751 : :
1752 : : static struct builtin_info *
1753 : 12067 : alloc_builtin (data_reference_p dst_dr, data_reference_p src_dr,
1754 : : tree dst_base, tree src_base, tree size)
1755 : : {
1756 : 0 : struct builtin_info *builtin = XNEW (struct builtin_info);
1757 : 12067 : builtin->dst_dr = dst_dr;
1758 : 12067 : builtin->src_dr = src_dr;
1759 : 12067 : builtin->dst_base = dst_base;
1760 : 12067 : builtin->src_base = src_base;
1761 : 12067 : builtin->size = size;
1762 : 12067 : return builtin;
1763 : : }
1764 : :
1765 : : /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1766 : : memset call. */
1767 : :
1768 : : static void
1769 : 57459 : classify_builtin_st (loop_p loop, partition *partition, data_reference_p dr)
1770 : : {
1771 : 57459 : gimple *stmt = DR_STMT (dr);
1772 : 57459 : tree base, size, rhs = gimple_assign_rhs1 (stmt);
1773 : :
1774 : 57459 : if (const_with_all_bytes_same (rhs) == -1
1775 : 57459 : && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
1776 : 49892 : || (TYPE_MODE (TREE_TYPE (rhs))
1777 : 24946 : != TYPE_MODE (unsigned_char_type_node))))
1778 : 50111 : return;
1779 : :
1780 : 23876 : if (TREE_CODE (rhs) == SSA_NAME
1781 : 4824 : && !SSA_NAME_IS_DEFAULT_DEF (rhs)
1782 : 28172 : && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
1783 : : return;
1784 : :
1785 : 19721 : int res = compute_access_range (loop, dr, &base, &size);
1786 : 19721 : if (res == 0)
1787 : : return;
1788 : 7408 : if (res == 1)
1789 : : {
1790 : 60 : partition->kind = PKIND_PARTIAL_MEMSET;
1791 : 60 : return;
1792 : : }
1793 : :
1794 : 7348 : tree base_offset;
1795 : 7348 : tree base_base;
1796 : 7348 : split_constant_offset (base, &base_base, &base_offset);
1797 : 7348 : if (!cst_and_fits_in_hwi (base_offset))
1798 : : return;
1799 : 7348 : unsigned HOST_WIDE_INT const_base_offset = int_cst_value (base_offset);
1800 : :
1801 : 7348 : struct builtin_info *builtin;
1802 : 7348 : builtin = alloc_builtin (dr, NULL, base, NULL_TREE, size);
1803 : 7348 : builtin->dst_base_base = base_base;
1804 : 7348 : builtin->dst_base_offset = const_base_offset;
1805 : 7348 : partition->builtin = builtin;
1806 : 7348 : partition->kind = PKIND_MEMSET;
1807 : : }
1808 : :
1809 : : /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1810 : : if it forms builtin memcpy or memmove call. */
1811 : :
1812 : : void
1813 : 31540 : loop_distribution::classify_builtin_ldst (loop_p loop, struct graph *rdg,
1814 : : partition *partition,
1815 : : data_reference_p dst_dr,
1816 : : data_reference_p src_dr)
1817 : : {
1818 : 31540 : tree base, size, src_base, src_size;
1819 : 31540 : auto_vec<tree> dst_steps, src_steps;
1820 : :
1821 : : /* Compute access range of both load and store. */
1822 : 31540 : int res = compute_access_range (loop, dst_dr, &base, &size, &dst_steps);
1823 : 31540 : if (res != 2)
1824 : : return;
1825 : 15605 : res = compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps);
1826 : 15605 : if (res != 2)
1827 : : return;
1828 : :
1829 : : /* They must have the same access size. */
1830 : 10170 : if (!operand_equal_p (size, src_size, 0))
1831 : : return;
1832 : :
1833 : : /* They must have the same storage order. */
1834 : 20340 : if (reverse_storage_order_for_component_p (DR_REF (dst_dr))
1835 : 10170 : != reverse_storage_order_for_component_p (DR_REF (src_dr)))
1836 : : return;
1837 : :
1838 : : /* Load and store in loop nest must access memory in the same way, i.e,
1839 : : their must have the same steps in each loop of the nest. */
1840 : 30510 : if (dst_steps.length () != src_steps.length ())
1841 : : return;
1842 : 20443 : for (unsigned i = 0; i < dst_steps.length (); ++i)
1843 : 10559 : if (!operand_equal_p (dst_steps[i], src_steps[i], 0))
1844 : : return;
1845 : :
1846 : : /* Now check that if there is a dependence. */
1847 : 9884 : ddr_p ddr = get_data_dependence (rdg, src_dr, dst_dr);
1848 : :
1849 : : /* Classify as memcpy if no dependence between load and store. */
1850 : 9884 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1851 : : {
1852 : 4546 : partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1853 : 4546 : partition->kind = PKIND_MEMCPY;
1854 : 4546 : return;
1855 : : }
1856 : :
1857 : : /* Can't do memmove in case of unknown dependence or dependence without
1858 : : classical distance vector. */
1859 : 5338 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1860 : 31920 : || DDR_NUM_DIST_VECTS (ddr) == 0)
1861 : : return;
1862 : :
1863 : 380 : unsigned i;
1864 : 380 : lambda_vector dist_v;
1865 : 380 : int num_lev = (DDR_LOOP_NEST (ddr)).length ();
1866 : 711 : FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
1867 : : {
1868 : 331 : unsigned dep_lev = dependence_level (dist_v, num_lev);
1869 : : /* Can't do memmove if load depends on store. */
1870 : 363 : if (dep_lev > 0 && dist_v[dep_lev - 1] > 0 && !DDR_REVERSED_P (ddr))
1871 : : return;
1872 : : }
1873 : :
1874 : 173 : partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1875 : 173 : partition->kind = PKIND_MEMMOVE;
1876 : 173 : return;
1877 : 31540 : }
1878 : :
1879 : : bool
1880 : 221264 : loop_distribution::classify_partition (loop_p loop,
1881 : : struct graph *rdg, partition *partition,
1882 : : bitmap stmt_in_all_partitions)
1883 : : {
1884 : 221264 : bitmap_iterator bi;
1885 : 221264 : unsigned i;
1886 : 221264 : data_reference_p single_ld = NULL, single_st = NULL;
1887 : 221264 : bool volatiles_p = false, has_reduction = false;
1888 : :
1889 : 3175037 : EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1890 : : {
1891 : 2953773 : gimple *stmt = RDG_STMT (rdg, i);
1892 : :
1893 : 5006988 : if (gimple_has_volatile_ops (stmt))
1894 : 2953773 : volatiles_p = true;
1895 : :
1896 : : /* If the stmt is not included by all partitions and there is uses
1897 : : outside of the loop, then mark the partition as reduction. */
1898 : 2953773 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
1899 : : {
1900 : : /* Due to limitation in the transform phase we have to fuse all
1901 : : reduction partitions. As a result, this could cancel valid
1902 : : loop distribution especially for loop that induction variable
1903 : : is used outside of loop. To workaround this issue, we skip
1904 : : marking partition as reudction if the reduction stmt belongs
1905 : : to all partitions. In such case, reduction will be computed
1906 : : correctly no matter how partitions are fused/distributed. */
1907 : 59958 : if (!bitmap_bit_p (stmt_in_all_partitions, i))
1908 : 24779 : partition->reduction_p = true;
1909 : : else
1910 : : has_reduction = true;
1911 : : }
1912 : : }
1913 : :
1914 : : /* Simple workaround to prevent classifying the partition as builtin
1915 : : if it contains any use outside of loop. For the case where all
1916 : : partitions have the reduction this simple workaround is delayed
1917 : : to only affect the last partition. */
1918 : 221264 : if (partition->reduction_p)
1919 : : return has_reduction;
1920 : :
1921 : : /* Perform general partition disqualification for builtins. */
1922 : 197649 : if (volatiles_p
1923 : 197649 : || !flag_tree_loop_distribute_patterns)
1924 : : return has_reduction;
1925 : :
1926 : : /* Find single load/store data references for builtin partition. */
1927 : 195851 : if (!find_single_drs (loop, rdg, partition->stmts, &single_st, &single_ld)
1928 : 195851 : || !single_st)
1929 : : return has_reduction;
1930 : :
1931 : 111786 : if (single_ld && single_st)
1932 : : {
1933 : 54327 : gimple *store = DR_STMT (single_st), *load = DR_STMT (single_ld);
1934 : : /* Direct aggregate copy or via an SSA name temporary. */
1935 : 54327 : if (load != store
1936 : 54327 : && gimple_assign_lhs (load) != gimple_assign_rhs1 (store))
1937 : : return has_reduction;
1938 : : }
1939 : :
1940 : 88999 : partition->loc = gimple_location (DR_STMT (single_st));
1941 : :
1942 : : /* Classify the builtin kind. */
1943 : 88999 : if (single_ld == NULL)
1944 : 57459 : classify_builtin_st (loop, partition, single_st);
1945 : : else
1946 : 31540 : classify_builtin_ldst (loop, rdg, partition, single_st, single_ld);
1947 : : return has_reduction;
1948 : : }
1949 : :
1950 : : bool
1951 : 671644 : loop_distribution::share_memory_accesses (struct graph *rdg,
1952 : : partition *partition1, partition *partition2)
1953 : : {
1954 : 671644 : unsigned i, j;
1955 : 671644 : bitmap_iterator bi, bj;
1956 : 671644 : data_reference_p dr1, dr2;
1957 : :
1958 : : /* First check whether in the intersection of the two partitions are
1959 : : any loads or stores. Common loads are the situation that happens
1960 : : most often. */
1961 : 4926691 : EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
1962 : 4258952 : if (RDG_MEM_WRITE_STMT (rdg, i)
1963 : 4258952 : || RDG_MEM_READS_STMT (rdg, i))
1964 : : return true;
1965 : :
1966 : : /* Then check whether the two partitions access the same memory object. */
1967 : 1411552 : EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1968 : : {
1969 : 745832 : dr1 = datarefs_vec[i];
1970 : :
1971 : 745832 : if (!DR_BASE_ADDRESS (dr1)
1972 : 745092 : || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1))
1973 : 740 : continue;
1974 : :
1975 : 1633787 : EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj)
1976 : : {
1977 : 890714 : dr2 = datarefs_vec[j];
1978 : :
1979 : 890714 : if (!DR_BASE_ADDRESS (dr2)
1980 : 890215 : || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2))
1981 : 499 : continue;
1982 : :
1983 : 890215 : if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0)
1984 : 756528 : && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0)
1985 : 755079 : && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0)
1986 : 892265 : && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0))
1987 : : return true;
1988 : : }
1989 : : }
1990 : :
1991 : : return false;
1992 : : }
1993 : :
1994 : : /* For each seed statement in STARTING_STMTS, this function builds
1995 : : partition for it by adding depended statements according to RDG.
1996 : : All partitions are recorded in PARTITIONS. */
1997 : :
1998 : : void
1999 : 126362 : loop_distribution::rdg_build_partitions (struct graph *rdg,
2000 : : vec<gimple *> starting_stmts,
2001 : : vec<partition *> *partitions)
2002 : : {
2003 : 126362 : auto_bitmap processed;
2004 : 126362 : int i;
2005 : 126362 : gimple *stmt;
2006 : :
2007 : 479845 : FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
2008 : : {
2009 : 227121 : int v = rdg_vertex_for_stmt (rdg, stmt);
2010 : :
2011 : 227121 : if (dump_file && (dump_flags & TDF_DETAILS))
2012 : 138 : fprintf (dump_file,
2013 : : "ldist asked to generate code for vertex %d\n", v);
2014 : :
2015 : : /* If the vertex is already contained in another partition so
2016 : : is the partition rooted at it. */
2017 : 227121 : if (bitmap_bit_p (processed, v))
2018 : 5857 : continue;
2019 : :
2020 : 221264 : partition *partition = build_rdg_partition_for_vertex (rdg, v);
2021 : 221264 : bitmap_ior_into (processed, partition->stmts);
2022 : :
2023 : 221264 : if (dump_file && (dump_flags & TDF_DETAILS))
2024 : : {
2025 : 138 : fprintf (dump_file, "ldist creates useful %s partition:\n",
2026 : 138 : partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
2027 : 138 : bitmap_print (dump_file, partition->stmts, " ", "\n");
2028 : : }
2029 : :
2030 : 221264 : partitions->safe_push (partition);
2031 : : }
2032 : :
2033 : : /* All vertices should have been assigned to at least one partition now,
2034 : : other than vertices belonging to dead code. */
2035 : 126362 : }
2036 : :
2037 : : /* Dump to FILE the PARTITIONS. */
2038 : :
2039 : : static void
2040 : 39 : dump_rdg_partitions (FILE *file, const vec<partition *> &partitions)
2041 : : {
2042 : 39 : int i;
2043 : 39 : partition *partition;
2044 : :
2045 : 102 : FOR_EACH_VEC_ELT (partitions, i, partition)
2046 : 63 : debug_bitmap_file (file, partition->stmts);
2047 : 39 : }
2048 : :
2049 : : /* Debug PARTITIONS. */
2050 : : extern void debug_rdg_partitions (const vec<partition *> &);
2051 : :
2052 : : DEBUG_FUNCTION void
2053 : 0 : debug_rdg_partitions (const vec<partition *> &partitions)
2054 : : {
2055 : 0 : dump_rdg_partitions (stderr, partitions);
2056 : 0 : }
2057 : :
2058 : : /* Returns the number of read and write operations in the RDG. */
2059 : :
2060 : : static int
2061 : 2459 : number_of_rw_in_rdg (struct graph *rdg)
2062 : : {
2063 : 2459 : int i, res = 0;
2064 : :
2065 : 36988 : for (i = 0; i < rdg->n_vertices; i++)
2066 : : {
2067 : 34529 : if (RDG_MEM_WRITE_STMT (rdg, i))
2068 : 7017 : ++res;
2069 : :
2070 : 34529 : if (RDG_MEM_READS_STMT (rdg, i))
2071 : 5052 : ++res;
2072 : : }
2073 : :
2074 : 2459 : return res;
2075 : : }
2076 : :
2077 : : /* Returns the number of read and write operations in a PARTITION of
2078 : : the RDG. */
2079 : :
2080 : : static int
2081 : 5348 : number_of_rw_in_partition (struct graph *rdg, partition *partition)
2082 : : {
2083 : 5348 : int res = 0;
2084 : 5348 : unsigned i;
2085 : 5348 : bitmap_iterator ii;
2086 : :
2087 : 51107 : EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
2088 : : {
2089 : 45759 : if (RDG_MEM_WRITE_STMT (rdg, i))
2090 : 6997 : ++res;
2091 : :
2092 : 45759 : if (RDG_MEM_READS_STMT (rdg, i))
2093 : 5052 : ++res;
2094 : : }
2095 : :
2096 : 5348 : return res;
2097 : : }
2098 : :
2099 : : /* Returns true when one of the PARTITIONS contains all the read or
2100 : : write operations of RDG. */
2101 : :
2102 : : static bool
2103 : 2459 : partition_contains_all_rw (struct graph *rdg,
2104 : : const vec<partition *> &partitions)
2105 : : {
2106 : 2459 : int i;
2107 : 2459 : partition *partition;
2108 : 2459 : int nrw = number_of_rw_in_rdg (rdg);
2109 : :
2110 : 7751 : FOR_EACH_VEC_ELT (partitions, i, partition)
2111 : 5348 : if (nrw == number_of_rw_in_partition (rdg, partition))
2112 : : return true;
2113 : :
2114 : : return false;
2115 : : }
2116 : :
2117 : : int
2118 : 1292798 : loop_distribution::pg_add_dependence_edges (struct graph *rdg, int dir,
2119 : : bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs)
2120 : : {
2121 : 1292798 : unsigned i, j;
2122 : 1292798 : bitmap_iterator bi, bj;
2123 : 1292798 : data_reference_p dr1, dr2, saved_dr1;
2124 : :
2125 : : /* dependence direction - 0 is no dependence, -1 is back,
2126 : : 1 is forth, 2 is both (we can stop then, merging will occur). */
2127 : 2647100 : EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi)
2128 : : {
2129 : 1367296 : dr1 = datarefs_vec[i];
2130 : :
2131 : 2952326 : EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj)
2132 : : {
2133 : 1598024 : int res, this_dir = 1;
2134 : 1598024 : ddr_p ddr;
2135 : :
2136 : 1598024 : dr2 = datarefs_vec[j];
2137 : :
2138 : : /* Skip all <read, read> data dependence. */
2139 : 1598024 : if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
2140 : 102661 : continue;
2141 : :
2142 : 1495363 : saved_dr1 = dr1;
2143 : : /* Re-shuffle data-refs to be in topological order. */
2144 : 2990726 : if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
2145 : 1495363 : > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
2146 : : {
2147 : 30015 : std::swap (dr1, dr2);
2148 : 30015 : this_dir = -this_dir;
2149 : : }
2150 : 1495363 : ddr = get_data_dependence (rdg, dr1, dr2);
2151 : 1495363 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2152 : : {
2153 : 24041 : this_dir = 0;
2154 : 24041 : res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1),
2155 : : DR_BASE_ADDRESS (dr2));
2156 : : /* Be conservative. If data references are not well analyzed,
2157 : : or the two data references have the same base address and
2158 : : offset, add dependence and consider it alias to each other.
2159 : : In other words, the dependence cannot be resolved by
2160 : : runtime alias check. */
2161 : 24041 : if (!DR_BASE_ADDRESS (dr1) || !DR_BASE_ADDRESS (dr2)
2162 : 23683 : || !DR_OFFSET (dr1) || !DR_OFFSET (dr2)
2163 : 23683 : || !DR_INIT (dr1) || !DR_INIT (dr2)
2164 : 23683 : || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
2165 : 15821 : || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
2166 : 15675 : || res == 0)
2167 : : this_dir = 2;
2168 : : /* Data dependence could be resolved by runtime alias check,
2169 : : record it in ALIAS_DDRS. */
2170 : 12268 : else if (alias_ddrs != NULL)
2171 : 6082 : alias_ddrs->safe_push (ddr);
2172 : : /* Or simply ignore it. */
2173 : : }
2174 : 1471322 : else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2175 : : {
2176 : : /* Known dependences can still be unordered througout the
2177 : : iteration space, see gcc.dg/tree-ssa/ldist-16.c and
2178 : : gcc.dg/tree-ssa/pr94969.c. */
2179 : 2075 : if (DDR_NUM_DIST_VECTS (ddr) != 1)
2180 : : this_dir = 2;
2181 : : else
2182 : : {
2183 : : /* If the overlap is exact preserve stmt order. */
2184 : 1790 : if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0),
2185 : 1790 : DDR_NB_LOOPS (ddr)))
2186 : : ;
2187 : : /* Else as the distance vector is lexicographic positive swap
2188 : : the dependence direction. */
2189 : : else
2190 : : {
2191 : 842 : if (DDR_REVERSED_P (ddr))
2192 : 42 : this_dir = -this_dir;
2193 : 842 : this_dir = -this_dir;
2194 : : }
2195 : : /* When then dependence distance of the innermost common
2196 : : loop of the DRs is zero we have a conflict. This is
2197 : : due to wonky dependence analysis which sometimes
2198 : : ends up using a zero distance in place of unknown. */
2199 : 895 : auto l1 = gimple_bb (DR_STMT (dr1))->loop_father;
2200 : 895 : auto l2 = gimple_bb (DR_STMT (dr2))->loop_father;
2201 : 895 : int idx = index_in_loop_nest (find_common_loop (l1, l2)->num,
2202 : 895 : DDR_LOOP_NEST (ddr));
2203 : 895 : if (DDR_DIST_VECT (ddr, 0)[idx] == 0
2204 : : /* Unless it is the outermost loop which is the one
2205 : : we eventually distribute. */
2206 : 895 : && idx != 0)
2207 : : this_dir = 2;
2208 : : }
2209 : : }
2210 : : else
2211 : : this_dir = 0;
2212 : 6994 : if (this_dir == 2)
2213 : 12994 : return 2;
2214 : 1482382 : else if (dir == 0)
2215 : : dir = this_dir;
2216 : 7255 : else if (this_dir != 0 && dir != this_dir)
2217 : : return 2;
2218 : : /* Shuffle "back" dr1. */
2219 : 1482369 : dr1 = saved_dr1;
2220 : : }
2221 : : }
2222 : : return dir;
2223 : : }
2224 : :
2225 : : /* Compare postorder number of the partition graph vertices V1 and V2. */
2226 : :
2227 : : static int
2228 : 761650 : pgcmp (const void *v1_, const void *v2_)
2229 : : {
2230 : 761650 : const vertex *v1 = (const vertex *)v1_;
2231 : 761650 : const vertex *v2 = (const vertex *)v2_;
2232 : 761650 : return v2->post - v1->post;
2233 : : }
2234 : :
2235 : : /* Data attached to vertices of partition dependence graph. */
2236 : : struct pg_vdata
2237 : : {
2238 : : /* ID of the corresponding partition. */
2239 : : int id;
2240 : : /* The partition. */
2241 : : struct partition *partition;
2242 : : };
2243 : :
2244 : : /* Data attached to edges of partition dependence graph. */
2245 : : struct pg_edata
2246 : : {
2247 : : /* If the dependence edge can be resolved by runtime alias check,
2248 : : this vector contains data dependence relations for runtime alias
2249 : : check. On the other hand, if the dependence edge is introduced
2250 : : because of compilation time known data dependence, this vector
2251 : : contains nothing. */
2252 : : vec<ddr_p> alias_ddrs;
2253 : : };
2254 : :
2255 : : /* Callback data for traversing edges in graph. */
2256 : : struct pg_edge_callback_data
2257 : : {
2258 : : /* Bitmap contains strong connected components should be merged. */
2259 : : bitmap sccs_to_merge;
2260 : : /* Array constains component information for all vertices. */
2261 : : int *vertices_component;
2262 : : /* Vector to record all data dependence relations which are needed
2263 : : to break strong connected components by runtime alias checks. */
2264 : : vec<ddr_p> *alias_ddrs;
2265 : : };
2266 : :
2267 : : /* Initialize vertice's data for partition dependence graph PG with
2268 : : PARTITIONS. */
2269 : :
2270 : : static void
2271 : 11444 : init_partition_graph_vertices (struct graph *pg,
2272 : : vec<struct partition *> *partitions)
2273 : : {
2274 : 11444 : int i;
2275 : 11444 : partition *partition;
2276 : 11444 : struct pg_vdata *data;
2277 : :
2278 : 65086 : for (i = 0; partitions->iterate (i, &partition); ++i)
2279 : : {
2280 : 53642 : data = new pg_vdata;
2281 : 53642 : pg->vertices[i].data = data;
2282 : 53642 : data->id = i;
2283 : 53642 : data->partition = partition;
2284 : : }
2285 : 11444 : }
2286 : :
2287 : : /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2288 : : dependence relations to the EDGE if DDRS isn't NULL. */
2289 : :
2290 : : static void
2291 : 37211 : add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs)
2292 : : {
2293 : 37211 : struct graph_edge *e = add_edge (pg, i, j);
2294 : :
2295 : : /* If the edge is attached with data dependence relations, it means this
2296 : : dependence edge can be resolved by runtime alias checks. */
2297 : 37211 : if (ddrs != NULL)
2298 : : {
2299 : 9346 : struct pg_edata *data = new pg_edata;
2300 : :
2301 : 9346 : gcc_assert (ddrs->length () > 0);
2302 : 9346 : e->data = data;
2303 : 9346 : data->alias_ddrs = vNULL;
2304 : 9346 : data->alias_ddrs.safe_splice (*ddrs);
2305 : : }
2306 : 37211 : }
2307 : :
2308 : : /* Callback function for graph travesal algorithm. It returns true
2309 : : if edge E should skipped when traversing the graph. */
2310 : :
2311 : : static bool
2312 : 771 : pg_skip_alias_edge (struct graph_edge *e)
2313 : : {
2314 : 771 : struct pg_edata *data = (struct pg_edata *)e->data;
2315 : 771 : return (data != NULL && data->alias_ddrs.length () > 0);
2316 : : }
2317 : :
2318 : : /* Callback function freeing data attached to edge E of graph. */
2319 : :
2320 : : static void
2321 : 37211 : free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *)
2322 : : {
2323 : 37211 : if (e->data != NULL)
2324 : : {
2325 : 9345 : struct pg_edata *data = (struct pg_edata *)e->data;
2326 : 9345 : data->alias_ddrs.release ();
2327 : 9345 : delete data;
2328 : : }
2329 : 37211 : }
2330 : :
2331 : : /* Free data attached to vertice of partition dependence graph PG. */
2332 : :
2333 : : static void
2334 : 11444 : free_partition_graph_vdata (struct graph *pg)
2335 : : {
2336 : 11444 : int i;
2337 : 11444 : struct pg_vdata *data;
2338 : :
2339 : 65086 : for (i = 0; i < pg->n_vertices; ++i)
2340 : : {
2341 : 53642 : data = (struct pg_vdata *)pg->vertices[i].data;
2342 : 53642 : delete data;
2343 : : }
2344 : 11444 : }
2345 : :
2346 : : /* Build and return partition dependence graph for PARTITIONS. RDG is
2347 : : reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2348 : : is true, data dependence caused by possible alias between references
2349 : : is ignored, as if it doesn't exist at all; otherwise all depdendences
2350 : : are considered. */
2351 : :
2352 : : struct graph *
2353 : 11444 : loop_distribution::build_partition_graph (struct graph *rdg,
2354 : : vec<struct partition *> *partitions,
2355 : : bool ignore_alias_p)
2356 : : {
2357 : 11444 : int i, j;
2358 : 11444 : struct partition *partition1, *partition2;
2359 : 22888 : graph *pg = new_graph (partitions->length ());
2360 : 11444 : auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p;
2361 : :
2362 : 11444 : alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs;
2363 : :
2364 : 11444 : init_partition_graph_vertices (pg, partitions);
2365 : :
2366 : 11444 : for (i = 0; partitions->iterate (i, &partition1); ++i)
2367 : : {
2368 : 1411526 : for (j = i + 1; partitions->iterate (j, &partition2); ++j)
2369 : : {
2370 : : /* dependence direction - 0 is no dependence, -1 is back,
2371 : : 1 is forth, 2 is both (we can stop then, merging will occur). */
2372 : 1292798 : int dir = 0;
2373 : :
2374 : : /* If the first partition has reduction, add back edge; if the
2375 : : second partition has reduction, add forth edge. This makes
2376 : : sure that reduction partition will be sorted as the last one. */
2377 : 1292798 : if (partition_reduction_p (partition1))
2378 : : dir = -1;
2379 : 1292668 : else if (partition_reduction_p (partition2))
2380 : 1461 : dir = 1;
2381 : :
2382 : : /* Cleanup the temporary vector. */
2383 : 1292798 : alias_ddrs.truncate (0);
2384 : :
2385 : 1292798 : dir = pg_add_dependence_edges (rdg, dir, partition1->datarefs,
2386 : : partition2->datarefs, alias_ddrs_p);
2387 : :
2388 : : /* Add edge to partition graph if there exists dependence. There
2389 : : are two types of edges. One type edge is caused by compilation
2390 : : time known dependence, this type cannot be resolved by runtime
2391 : : alias check. The other type can be resolved by runtime alias
2392 : : check. */
2393 : 1292798 : if (dir == 1 || dir == 2
2394 : 1298269 : || alias_ddrs.length () > 0)
2395 : : {
2396 : : /* Attach data dependence relations to edge that can be resolved
2397 : : by runtime alias check. */
2398 : 19337 : bool alias_edge_p = (dir != 1 && dir != 2);
2399 : 34024 : add_partition_graph_edge (pg, i, j,
2400 : : (alias_edge_p) ? &alias_ddrs : NULL);
2401 : : }
2402 : 1292798 : if (dir == -1 || dir == 2
2403 : 2590292 : || alias_ddrs.length () > 0)
2404 : : {
2405 : : /* Attach data dependence relations to edge that can be resolved
2406 : : by runtime alias check. */
2407 : 17874 : bool alias_edge_p = (dir != -1 && dir != 2);
2408 : 31052 : add_partition_graph_edge (pg, j, i,
2409 : : (alias_edge_p) ? &alias_ddrs : NULL);
2410 : : }
2411 : : }
2412 : : }
2413 : 11444 : return pg;
2414 : 11444 : }
2415 : :
2416 : : /* Sort partitions in PG in descending post order and store them in
2417 : : PARTITIONS. */
2418 : :
2419 : : static void
2420 : 11444 : sort_partitions_by_post_order (struct graph *pg,
2421 : : vec<struct partition *> *partitions)
2422 : : {
2423 : 11444 : int i;
2424 : 11444 : struct pg_vdata *data;
2425 : :
2426 : : /* Now order the remaining nodes in descending postorder. */
2427 : 11444 : qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
2428 : 11444 : partitions->truncate (0);
2429 : 76530 : for (i = 0; i < pg->n_vertices; ++i)
2430 : : {
2431 : 53642 : data = (struct pg_vdata *)pg->vertices[i].data;
2432 : 53642 : if (data->partition)
2433 : 49983 : partitions->safe_push (data->partition);
2434 : : }
2435 : 11444 : }
2436 : :
2437 : : void
2438 : 6179 : loop_distribution::merge_dep_scc_partitions (struct graph *rdg,
2439 : : vec<struct partition *> *partitions,
2440 : : bool ignore_alias_p)
2441 : : {
2442 : 6179 : struct partition *partition1, *partition2;
2443 : 6179 : struct pg_vdata *data;
2444 : 6179 : graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p);
2445 : 6179 : int i, j, num_sccs = graphds_scc (pg, NULL);
2446 : :
2447 : : /* Strong connected compoenent means dependence cycle, we cannot distribute
2448 : : them. So fuse them together. */
2449 : 6179 : if ((unsigned) num_sccs < partitions->length ())
2450 : : {
2451 : 1544 : for (i = 0; i < num_sccs; ++i)
2452 : : {
2453 : 878 : for (j = 0; partitions->iterate (j, &partition1); ++j)
2454 : 878 : if (pg->vertices[j].component == i)
2455 : : break;
2456 : 4672 : for (j = j + 1; partitions->iterate (j, &partition2); ++j)
2457 : 3076 : if (pg->vertices[j].component == i)
2458 : : {
2459 : 2755 : partition_merge_into (NULL, partition1,
2460 : : partition2, FUSE_SAME_SCC);
2461 : 2755 : partition1->type = PTYPE_SEQUENTIAL;
2462 : 2755 : (*partitions)[j] = NULL;
2463 : 2755 : partition_free (partition2);
2464 : 2755 : data = (struct pg_vdata *)pg->vertices[j].data;
2465 : 2755 : data->partition = NULL;
2466 : : }
2467 : : }
2468 : : }
2469 : :
2470 : 6179 : sort_partitions_by_post_order (pg, partitions);
2471 : 12358 : gcc_assert (partitions->length () == (unsigned)num_sccs);
2472 : 6179 : free_partition_graph_vdata (pg);
2473 : 6179 : for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2474 : 6179 : free_graph (pg);
2475 : 6179 : }
2476 : :
2477 : : /* Callback function for traversing edge E in graph G. DATA is private
2478 : : callback data. */
2479 : :
2480 : : static void
2481 : 249 : pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data)
2482 : : {
2483 : 249 : int i, j, component;
2484 : 249 : struct pg_edge_callback_data *cbdata;
2485 : 249 : struct pg_edata *edata = (struct pg_edata *) e->data;
2486 : :
2487 : : /* If the edge doesn't have attached data dependence, it represents
2488 : : compilation time known dependences. This type dependence cannot
2489 : : be resolved by runtime alias check. */
2490 : 249 : if (edata == NULL || edata->alias_ddrs.length () == 0)
2491 : : return;
2492 : :
2493 : 239 : cbdata = (struct pg_edge_callback_data *) data;
2494 : 239 : i = e->src;
2495 : 239 : j = e->dest;
2496 : 239 : component = cbdata->vertices_component[i];
2497 : : /* Vertices are topologically sorted according to compilation time
2498 : : known dependences, so we can break strong connected components
2499 : : by removing edges of the opposite direction, i.e, edges pointing
2500 : : from vertice with smaller post number to vertice with bigger post
2501 : : number. */
2502 : 239 : if (g->vertices[i].post < g->vertices[j].post
2503 : : /* We only need to remove edges connecting vertices in the same
2504 : : strong connected component to break it. */
2505 : 122 : && component == cbdata->vertices_component[j]
2506 : : /* Check if we want to break the strong connected component or not. */
2507 : 361 : && !bitmap_bit_p (cbdata->sccs_to_merge, component))
2508 : 122 : cbdata->alias_ddrs->safe_splice (edata->alias_ddrs);
2509 : : }
2510 : :
2511 : : /* Callback function for traversing edge E. DATA is private
2512 : : callback data. */
2513 : :
2514 : : static void
2515 : 249 : pg_unmark_merged_alias_ddrs (struct graph *, struct graph_edge *e, void *data)
2516 : : {
2517 : 249 : int i, j, component;
2518 : 249 : struct pg_edge_callback_data *cbdata;
2519 : 249 : struct pg_edata *edata = (struct pg_edata *) e->data;
2520 : :
2521 : 249 : if (edata == NULL || edata->alias_ddrs.length () == 0)
2522 : : return;
2523 : :
2524 : 240 : cbdata = (struct pg_edge_callback_data *) data;
2525 : 240 : i = e->src;
2526 : 240 : j = e->dest;
2527 : 240 : component = cbdata->vertices_component[i];
2528 : : /* Make sure to not skip vertices inside SCCs we are going to merge. */
2529 : 240 : if (component == cbdata->vertices_component[j]
2530 : 240 : && bitmap_bit_p (cbdata->sccs_to_merge, component))
2531 : : {
2532 : 1 : edata->alias_ddrs.release ();
2533 : 1 : delete edata;
2534 : 1 : e->data = NULL;
2535 : : }
2536 : : }
2537 : :
2538 : : /* This is the main function breaking strong conected components in
2539 : : PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2540 : : relations for runtime alias check in ALIAS_DDRS. */
2541 : : void
2542 : 5265 : loop_distribution::break_alias_scc_partitions (struct graph *rdg,
2543 : : vec<struct partition *> *partitions,
2544 : : vec<ddr_p> *alias_ddrs)
2545 : : {
2546 : 5265 : int i, j, k, num_sccs, num_sccs_no_alias = 0;
2547 : : /* Build partition dependence graph. */
2548 : 5265 : graph *pg = build_partition_graph (rdg, partitions, false);
2549 : :
2550 : 5265 : alias_ddrs->truncate (0);
2551 : : /* Find strong connected components in the graph, with all dependence edges
2552 : : considered. */
2553 : 5265 : num_sccs = graphds_scc (pg, NULL);
2554 : : /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2555 : : compilation time known dependences are merged before this function. */
2556 : 5265 : if ((unsigned) num_sccs < partitions->length ())
2557 : : {
2558 : 276 : struct pg_edge_callback_data cbdata;
2559 : 276 : auto_bitmap sccs_to_merge;
2560 : 276 : auto_vec<enum partition_type> scc_types;
2561 : 276 : struct partition *partition, *first;
2562 : :
2563 : : /* If all partitions in a SCC have the same type, we can simply merge the
2564 : : SCC. This loop finds out such SCCS and record them in bitmap. */
2565 : 276 : bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
2566 : 567 : for (i = 0; i < num_sccs; ++i)
2567 : : {
2568 : 312 : for (j = 0; partitions->iterate (j, &first); ++j)
2569 : 312 : if (pg->vertices[j].component == i)
2570 : : break;
2571 : :
2572 : 291 : bool same_type = true, all_builtins = partition_builtin_p (first);
2573 : 1334 : for (++j; partitions->iterate (j, &partition); ++j)
2574 : : {
2575 : 1078 : if (pg->vertices[j].component != i)
2576 : 90 : continue;
2577 : :
2578 : 988 : if (first->type != partition->type)
2579 : : {
2580 : : same_type = false;
2581 : : break;
2582 : : }
2583 : 953 : all_builtins &= partition_builtin_p (partition);
2584 : : }
2585 : : /* Merge SCC if all partitions in SCC have the same type, though the
2586 : : result partition is sequential, because vectorizer can do better
2587 : : runtime alias check. One expecption is all partitions in SCC are
2588 : : builtins. */
2589 : 291 : if (!same_type || all_builtins)
2590 : 61 : bitmap_clear_bit (sccs_to_merge, i);
2591 : : }
2592 : :
2593 : : /* Initialize callback data for traversing. */
2594 : 276 : cbdata.sccs_to_merge = sccs_to_merge;
2595 : 276 : cbdata.alias_ddrs = alias_ddrs;
2596 : 276 : cbdata.vertices_component = XNEWVEC (int, pg->n_vertices);
2597 : : /* Record the component information which will be corrupted by next
2598 : : graph scc finding call. */
2599 : 1555 : for (i = 0; i < pg->n_vertices; ++i)
2600 : 1279 : cbdata.vertices_component[i] = pg->vertices[i].component;
2601 : :
2602 : : /* Collect data dependences for runtime alias checks to break SCCs. */
2603 : 276 : if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
2604 : : {
2605 : : /* For SCCs we want to merge clear all alias_ddrs for edges
2606 : : inside the component. */
2607 : 57 : for_each_edge (pg, pg_unmark_merged_alias_ddrs, &cbdata);
2608 : :
2609 : : /* Run SCC finding algorithm again, with alias dependence edges
2610 : : skipped. This is to topologically sort partitions according to
2611 : : compilation time known dependence. Note the topological order
2612 : : is stored in the form of pg's post order number. */
2613 : 57 : num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
2614 : : /* We cannot assert partitions->length () == num_sccs_no_alias
2615 : : since we are not ignoring alias edges in cycles we are
2616 : : going to merge. That's required to compute correct postorder. */
2617 : : /* With topological order, we can construct two subgraphs L and R.
2618 : : L contains edge <x, y> where x < y in terms of post order, while
2619 : : R contains edge <x, y> where x > y. Edges for compilation time
2620 : : known dependence all fall in R, so we break SCCs by removing all
2621 : : (alias) edges of in subgraph L. */
2622 : 57 : for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);
2623 : : }
2624 : :
2625 : : /* For SCC that doesn't need to be broken, merge it. */
2626 : 567 : for (i = 0; i < num_sccs; ++i)
2627 : : {
2628 : 291 : if (!bitmap_bit_p (sccs_to_merge, i))
2629 : 61 : continue;
2630 : :
2631 : 245 : for (j = 0; partitions->iterate (j, &first); ++j)
2632 : 245 : if (cbdata.vertices_component[j] == i)
2633 : : break;
2634 : 1507 : for (k = j + 1; partitions->iterate (k, &partition); ++k)
2635 : : {
2636 : 986 : struct pg_vdata *data;
2637 : :
2638 : 986 : if (cbdata.vertices_component[k] != i)
2639 : 82 : continue;
2640 : :
2641 : 904 : partition_merge_into (NULL, first, partition, FUSE_SAME_SCC);
2642 : 904 : (*partitions)[k] = NULL;
2643 : 904 : partition_free (partition);
2644 : 904 : data = (struct pg_vdata *)pg->vertices[k].data;
2645 : 904 : gcc_assert (data->id == k);
2646 : 904 : data->partition = NULL;
2647 : : /* The result partition of merged SCC must be sequential. */
2648 : 904 : first->type = PTYPE_SEQUENTIAL;
2649 : : }
2650 : : }
2651 : : /* If reduction partition's SCC is broken by runtime alias checks,
2652 : : we force a negative post order to it making sure it will be scheduled
2653 : : in the last. */
2654 : 276 : if (num_sccs_no_alias > 0)
2655 : : {
2656 : : j = -1;
2657 : 205 : for (i = 0; i < pg->n_vertices; ++i)
2658 : : {
2659 : 148 : struct pg_vdata *data = (struct pg_vdata *)pg->vertices[i].data;
2660 : 148 : if (data->partition && partition_reduction_p (data->partition))
2661 : : {
2662 : 5 : gcc_assert (j == -1);
2663 : : j = i;
2664 : : }
2665 : : }
2666 : 57 : if (j >= 0)
2667 : 5 : pg->vertices[j].post = -1;
2668 : : }
2669 : :
2670 : 276 : free (cbdata.vertices_component);
2671 : 276 : }
2672 : :
2673 : 5265 : sort_partitions_by_post_order (pg, partitions);
2674 : 5265 : free_partition_graph_vdata (pg);
2675 : 5265 : for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2676 : 5265 : free_graph (pg);
2677 : :
2678 : 5265 : if (dump_file && (dump_flags & TDF_DETAILS))
2679 : : {
2680 : 15 : fprintf (dump_file, "Possible alias data dependence to break:\n");
2681 : 15 : dump_data_dependence_relations (dump_file, *alias_ddrs);
2682 : : }
2683 : 5265 : }
2684 : :
2685 : : /* Compute and return an expression whose value is the segment length which
2686 : : will be accessed by DR in NITERS iterations. */
2687 : :
2688 : : static tree
2689 : 746 : data_ref_segment_size (struct data_reference *dr, tree niters)
2690 : : {
2691 : 746 : niters = size_binop (MINUS_EXPR,
2692 : : fold_convert (sizetype, niters),
2693 : : size_one_node);
2694 : 746 : return size_binop (MULT_EXPR,
2695 : : fold_convert (sizetype, DR_STEP (dr)),
2696 : : fold_convert (sizetype, niters));
2697 : : }
2698 : :
2699 : : /* Return true if LOOP's latch is dominated by statement for data reference
2700 : : DR. */
2701 : :
2702 : : static inline bool
2703 : 746 : latch_dominated_by_data_ref (class loop *loop, data_reference *dr)
2704 : : {
2705 : 746 : return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
2706 : 746 : gimple_bb (DR_STMT (dr)));
2707 : : }
2708 : :
2709 : : /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2710 : : data dependence relations ALIAS_DDRS. */
2711 : :
2712 : : static void
2713 : 57 : compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
2714 : : vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
2715 : : {
2716 : 57 : unsigned int i;
2717 : 57 : unsigned HOST_WIDE_INT factor = 1;
2718 : 57 : tree niters_plus_one, niters = number_of_latch_executions (loop);
2719 : :
2720 : 57 : gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
2721 : 57 : niters = fold_convert (sizetype, niters);
2722 : 57 : niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
2723 : :
2724 : 57 : if (dump_file && (dump_flags & TDF_DETAILS))
2725 : 0 : fprintf (dump_file, "Creating alias check pairs:\n");
2726 : :
2727 : : /* Iterate all data dependence relations and compute alias check pairs. */
2728 : 430 : for (i = 0; i < alias_ddrs->length (); i++)
2729 : : {
2730 : 373 : ddr_p ddr = (*alias_ddrs)[i];
2731 : 373 : struct data_reference *dr_a = DDR_A (ddr);
2732 : 373 : struct data_reference *dr_b = DDR_B (ddr);
2733 : 373 : tree seg_length_a, seg_length_b;
2734 : :
2735 : 373 : if (latch_dominated_by_data_ref (loop, dr_a))
2736 : 369 : seg_length_a = data_ref_segment_size (dr_a, niters_plus_one);
2737 : : else
2738 : 4 : seg_length_a = data_ref_segment_size (dr_a, niters);
2739 : :
2740 : 373 : if (latch_dominated_by_data_ref (loop, dr_b))
2741 : 369 : seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
2742 : : else
2743 : 4 : seg_length_b = data_ref_segment_size (dr_b, niters);
2744 : :
2745 : 373 : unsigned HOST_WIDE_INT access_size_a
2746 : 373 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
2747 : 373 : unsigned HOST_WIDE_INT access_size_b
2748 : 373 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
2749 : 373 : unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
2750 : 373 : unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
2751 : :
2752 : 373 : dr_with_seg_len_pair_t dr_with_seg_len_pair
2753 : 746 : (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
2754 : 746 : dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b),
2755 : : /* ??? Would WELL_ORDERED be safe? */
2756 : 373 : dr_with_seg_len_pair_t::REORDERED);
2757 : :
2758 : 373 : comp_alias_pairs->safe_push (dr_with_seg_len_pair);
2759 : : }
2760 : :
2761 : 57 : if (tree_fits_uhwi_p (niters))
2762 : 28 : factor = tree_to_uhwi (niters);
2763 : :
2764 : : /* Prune alias check pairs. */
2765 : 57 : prune_runtime_alias_test_list (comp_alias_pairs, factor);
2766 : 57 : if (dump_file && (dump_flags & TDF_DETAILS))
2767 : 0 : fprintf (dump_file,
2768 : : "Improved number of alias checks from %d to %d\n",
2769 : : alias_ddrs->length (), comp_alias_pairs->length ());
2770 : 57 : }
2771 : :
2772 : : /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2773 : : checks and version LOOP under condition of these runtime alias checks. */
2774 : :
2775 : : static void
2776 : 57 : version_loop_by_alias_check (vec<struct partition *> *partitions,
2777 : : class loop *loop, vec<ddr_p> *alias_ddrs)
2778 : : {
2779 : 57 : profile_probability prob;
2780 : 57 : basic_block cond_bb;
2781 : 57 : class loop *nloop;
2782 : 57 : tree lhs, arg0, cond_expr = NULL_TREE;
2783 : 57 : gimple_seq cond_stmts = NULL;
2784 : 57 : gimple *call_stmt = NULL;
2785 : 57 : auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs;
2786 : :
2787 : : /* Generate code for runtime alias checks if necessary. */
2788 : 57 : gcc_assert (alias_ddrs->length () > 0);
2789 : :
2790 : 57 : if (dump_file && (dump_flags & TDF_DETAILS))
2791 : 0 : fprintf (dump_file,
2792 : : "Version loop <%d> with runtime alias check\n", loop->num);
2793 : :
2794 : 57 : compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs);
2795 : 57 : create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
2796 : 57 : cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
2797 : : is_gimple_val, NULL_TREE);
2798 : :
2799 : : /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2800 : 57 : bool cancelable_p = flag_tree_loop_vectorize;
2801 : 57 : if (cancelable_p)
2802 : : {
2803 : : unsigned i = 0;
2804 : : struct partition *partition;
2805 : 102 : for (; partitions->iterate (i, &partition); ++i)
2806 : 84 : if (!partition_builtin_p (partition))
2807 : : break;
2808 : :
2809 : : /* If all partitions are builtins, distributing it would be profitable and
2810 : : we don't want to cancel the runtime alias checks. */
2811 : 106 : if (i == partitions->length ())
2812 : : cancelable_p = false;
2813 : : }
2814 : :
2815 : : /* Generate internal function call for loop distribution alias check if the
2816 : : runtime alias check should be cancelable. */
2817 : 39 : if (cancelable_p)
2818 : : {
2819 : 35 : call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
2820 : : 2, NULL_TREE, cond_expr);
2821 : 35 : lhs = make_ssa_name (boolean_type_node);
2822 : 35 : gimple_call_set_lhs (call_stmt, lhs);
2823 : : }
2824 : : else
2825 : : lhs = cond_expr;
2826 : :
2827 : 57 : prob = profile_probability::guessed_always ().apply_scale (9, 10);
2828 : 57 : initialize_original_copy_tables ();
2829 : 57 : nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (),
2830 : : prob, prob.invert (), true);
2831 : 57 : free_original_copy_tables ();
2832 : : /* Record the original loop number in newly generated loops. In case of
2833 : : distribution, the original loop will be distributed and the new loop
2834 : : is kept. */
2835 : 57 : loop->orig_loop_num = nloop->num;
2836 : 57 : nloop->orig_loop_num = nloop->num;
2837 : 57 : nloop->dont_vectorize = true;
2838 : 57 : nloop->force_vectorize = false;
2839 : :
2840 : 57 : if (call_stmt)
2841 : : {
2842 : : /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2843 : : loop could be destroyed. */
2844 : 35 : arg0 = build_int_cst (integer_type_node, loop->orig_loop_num);
2845 : 35 : gimple_call_set_arg (call_stmt, 0, arg0);
2846 : 35 : gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt);
2847 : : }
2848 : :
2849 : 57 : if (cond_stmts)
2850 : : {
2851 : 57 : gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb);
2852 : 57 : gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT);
2853 : : }
2854 : 57 : update_ssa (TODO_update_ssa_no_phi);
2855 : 57 : }
2856 : :
2857 : : /* Return true if loop versioning is needed to distrubute PARTITIONS.
2858 : : ALIAS_DDRS are data dependence relations for runtime alias check. */
2859 : :
2860 : : static inline bool
2861 : 11457 : version_for_distribution_p (vec<struct partition *> *partitions,
2862 : : vec<ddr_p> *alias_ddrs)
2863 : : {
2864 : : /* No need to version loop if we have only one partition. */
2865 : 13860 : if (partitions->length () == 1)
2866 : : return false;
2867 : :
2868 : : /* Need to version loop if runtime alias check is necessary. */
2869 : 2403 : return (alias_ddrs->length () > 0);
2870 : : }
2871 : :
2872 : : /* Compare base offset of builtin mem* partitions P1 and P2. */
2873 : :
2874 : : static int
2875 : 291 : offset_cmp (const void *vp1, const void *vp2)
2876 : : {
2877 : 291 : struct partition *p1 = *(struct partition *const *) vp1;
2878 : 291 : struct partition *p2 = *(struct partition *const *) vp2;
2879 : 291 : unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
2880 : 291 : unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
2881 : 291 : return (o2 < o1) - (o1 < o2);
2882 : : }
2883 : :
2884 : : /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2885 : : case optimization transforming below code:
2886 : :
2887 : : __builtin_memset (&obj, 0, 100);
2888 : : _1 = &obj + 100;
2889 : : __builtin_memset (_1, 0, 200);
2890 : : _2 = &obj + 300;
2891 : : __builtin_memset (_2, 0, 100);
2892 : :
2893 : : into:
2894 : :
2895 : : __builtin_memset (&obj, 0, 400);
2896 : :
2897 : : Note we don't have dependence information between different partitions
2898 : : at this point, as a result, we can't handle nonadjacent memset builtin
2899 : : partitions since dependence might be broken. */
2900 : :
2901 : : static void
2902 : 2409 : fuse_memset_builtins (vec<struct partition *> *partitions)
2903 : : {
2904 : 2409 : unsigned i, j;
2905 : 2409 : struct partition *part1, *part2;
2906 : 2409 : tree rhs1, rhs2;
2907 : :
2908 : 7629 : for (i = 0; partitions->iterate (i, &part1);)
2909 : : {
2910 : 5220 : if (part1->kind != PKIND_MEMSET)
2911 : : {
2912 : 3131 : i++;
2913 : 3131 : continue;
2914 : : }
2915 : :
2916 : : /* Find sub-array of memset builtins of the same base. Index range
2917 : : of the sub-array is [i, j) with "j > i". */
2918 : 2142 : for (j = i + 1; partitions->iterate (j, &part2); ++j)
2919 : : {
2920 : 1645 : if (part2->kind != PKIND_MEMSET
2921 : 2155 : || !operand_equal_p (part1->builtin->dst_base_base,
2922 : 510 : part2->builtin->dst_base_base, 0))
2923 : : break;
2924 : :
2925 : : /* Memset calls setting different values can't be merged. */
2926 : 81 : rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2927 : 81 : rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2928 : 81 : if (!operand_equal_p (rhs1, rhs2, 0))
2929 : : break;
2930 : : }
2931 : :
2932 : : /* Stable sort is required in order to avoid breaking dependence. */
2933 : 2089 : gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
2934 : : offset_cmp);
2935 : : /* Continue with next partition. */
2936 : 2089 : i = j;
2937 : : }
2938 : :
2939 : : /* Merge all consecutive memset builtin partitions. */
2940 : 10546 : for (i = 0; i < partitions->length () - 1;)
2941 : : {
2942 : 2864 : part1 = (*partitions)[i];
2943 : 2864 : if (part1->kind != PKIND_MEMSET)
2944 : : {
2945 : 1219 : i++;
2946 : 2837 : continue;
2947 : : }
2948 : :
2949 : 1645 : part2 = (*partitions)[i + 1];
2950 : : /* Only merge memset partitions of the same base and with constant
2951 : : access sizes. */
2952 : 3217 : if (part2->kind != PKIND_MEMSET
2953 : 510 : || TREE_CODE (part1->builtin->size) != INTEGER_CST
2954 : 247 : || TREE_CODE (part2->builtin->size) != INTEGER_CST
2955 : 1892 : || !operand_equal_p (part1->builtin->dst_base_base,
2956 : 247 : part2->builtin->dst_base_base, 0))
2957 : : {
2958 : 1572 : i++;
2959 : 1572 : continue;
2960 : : }
2961 : 73 : rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2962 : 73 : rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2963 : 73 : int bytev1 = const_with_all_bytes_same (rhs1);
2964 : 73 : int bytev2 = const_with_all_bytes_same (rhs2);
2965 : : /* Only merge memset partitions of the same value. */
2966 : 73 : if (bytev1 != bytev2 || bytev1 == -1)
2967 : : {
2968 : 24 : i++;
2969 : 24 : continue;
2970 : : }
2971 : 98 : wide_int end1 = wi::add (part1->builtin->dst_base_offset,
2972 : 49 : wi::to_wide (part1->builtin->size));
2973 : : /* Only merge adjacent memset partitions. */
2974 : 49 : if (wi::ne_p (end1, part2->builtin->dst_base_offset))
2975 : : {
2976 : 22 : i++;
2977 : 22 : continue;
2978 : : }
2979 : : /* Merge partitions[i] and partitions[i+1]. */
2980 : 27 : part1->builtin->size = fold_build2 (PLUS_EXPR, sizetype,
2981 : : part1->builtin->size,
2982 : : part2->builtin->size);
2983 : 27 : partition_free (part2);
2984 : 27 : partitions->ordered_remove (i + 1);
2985 : 49 : }
2986 : 2409 : }
2987 : :
2988 : : void
2989 : 36206 : loop_distribution::finalize_partitions (class loop *loop,
2990 : : vec<struct partition *> *partitions,
2991 : : vec<ddr_p> *alias_ddrs)
2992 : : {
2993 : 36206 : unsigned i;
2994 : 36206 : struct partition *partition, *a;
2995 : :
2996 : 41475 : if (partitions->length () == 1
2997 : 36263 : || alias_ddrs->length () > 0)
2998 : 36206 : return;
2999 : :
3000 : 5212 : unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
3001 : 5212 : bool same_type_p = true;
3002 : 5212 : enum partition_type type = ((*partitions)[0])->type;
3003 : 29786 : for (i = 0; partitions->iterate (i, &partition); ++i)
3004 : : {
3005 : 24574 : same_type_p &= (type == partition->type);
3006 : 24574 : if (partition_builtin_p (partition))
3007 : : {
3008 : 2501 : num_builtin++;
3009 : 2501 : continue;
3010 : : }
3011 : 22073 : num_normal++;
3012 : 22073 : if (partition->kind == PKIND_PARTIAL_MEMSET)
3013 : 4 : num_partial_memset++;
3014 : : }
3015 : :
3016 : : /* Don't distribute current loop into too many loops given we don't have
3017 : : memory stream cost model. Be even more conservative in case of loop
3018 : : nest distribution. */
3019 : 5212 : if ((same_type_p && num_builtin == 0
3020 : 2782 : && (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
3021 : 2434 : || (loop->inner != NULL
3022 : 61 : && i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
3023 : 2425 : || (loop->inner == NULL
3024 : 2373 : && i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
3025 : : {
3026 : : a = (*partitions)[0];
3027 : 19301 : for (i = 1; partitions->iterate (i, &partition); ++i)
3028 : : {
3029 : 16498 : partition_merge_into (NULL, a, partition, FUSE_FINALIZE);
3030 : 16498 : partition_free (partition);
3031 : : }
3032 : 2803 : partitions->truncate (1);
3033 : : }
3034 : :
3035 : : /* Fuse memset builtins if possible. */
3036 : 5212 : if (partitions->length () > 1)
3037 : 2409 : fuse_memset_builtins (partitions);
3038 : : }
3039 : :
3040 : : /* Distributes the code from LOOP in such a way that producer statements
3041 : : are placed before consumer statements. Tries to separate only the
3042 : : statements from STMTS into separate loops. Returns the number of
3043 : : distributed loops. Set NB_CALLS to number of generated builtin calls.
3044 : : Set *DESTROY_P to whether LOOP needs to be destroyed. */
3045 : :
3046 : : int
3047 : 128820 : loop_distribution::distribute_loop (class loop *loop,
3048 : : const vec<gimple *> &stmts,
3049 : : control_dependences *cd, int *nb_calls, bool *destroy_p,
3050 : : bool only_patterns_p)
3051 : : {
3052 : 128820 : ddrs_table = new hash_table<ddr_hasher> (389);
3053 : 128820 : struct graph *rdg;
3054 : 128820 : partition *partition;
3055 : 128820 : int i, nbp;
3056 : :
3057 : 128820 : *destroy_p = false;
3058 : 128820 : *nb_calls = 0;
3059 : 128820 : loop_nest.create (0);
3060 : 128820 : if (!find_loop_nest (loop, &loop_nest))
3061 : : {
3062 : 0 : loop_nest.release ();
3063 : 0 : delete ddrs_table;
3064 : 0 : return 0;
3065 : : }
3066 : :
3067 : 128820 : datarefs_vec.create (20);
3068 : 128820 : has_nonaddressable_dataref_p = false;
3069 : 128820 : rdg = build_rdg (loop, cd);
3070 : 128820 : if (!rdg)
3071 : : {
3072 : 2458 : if (dump_file && (dump_flags & TDF_DETAILS))
3073 : 0 : fprintf (dump_file,
3074 : : "Loop %d not distributed: failed to build the RDG.\n",
3075 : : loop->num);
3076 : :
3077 : 2458 : loop_nest.release ();
3078 : 2458 : free_data_refs (datarefs_vec);
3079 : 2458 : delete ddrs_table;
3080 : 2458 : return 0;
3081 : : }
3082 : :
3083 : 252724 : if (datarefs_vec.length () > MAX_DATAREFS_NUM)
3084 : : {
3085 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3086 : 0 : fprintf (dump_file,
3087 : : "Loop %d not distributed: too many memory references.\n",
3088 : : loop->num);
3089 : :
3090 : 0 : free_rdg (rdg, loop);
3091 : 0 : loop_nest.release ();
3092 : 0 : free_data_refs (datarefs_vec);
3093 : 0 : delete ddrs_table;
3094 : 0 : return 0;
3095 : : }
3096 : :
3097 : : data_reference_p dref;
3098 : 513747 : for (i = 0; datarefs_vec.iterate (i, &dref); ++i)
3099 : 387385 : dref->aux = (void *) (uintptr_t) i;
3100 : :
3101 : 126362 : if (dump_file && (dump_flags & TDF_DETAILS))
3102 : 67 : dump_rdg (dump_file, rdg);
3103 : :
3104 : 126362 : auto_vec<struct partition *, 3> partitions;
3105 : 126362 : rdg_build_partitions (rdg, stmts, &partitions);
3106 : :
3107 : 126362 : auto_vec<ddr_p> alias_ddrs;
3108 : :
3109 : 126362 : auto_bitmap stmt_in_all_partitions;
3110 : 126362 : bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts);
3111 : 347626 : for (i = 1; partitions.iterate (i, &partition); ++i)
3112 : 94902 : bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts);
3113 : :
3114 : : bool any_builtin = false;
3115 : : bool reduction_in_all = false;
3116 : 347626 : int reduction_partition_num = -1;
3117 : 347626 : FOR_EACH_VEC_ELT (partitions, i, partition)
3118 : : {
3119 : 221264 : reduction_in_all
3120 : 221264 : |= classify_partition (loop, rdg, partition, stmt_in_all_partitions);
3121 : 221264 : any_builtin |= partition_builtin_p (partition);
3122 : : }
3123 : :
3124 : : /* If we are only distributing patterns but did not detect any,
3125 : : simply bail out. */
3126 : 126362 : if (only_patterns_p
3127 : 126362 : && !any_builtin)
3128 : : {
3129 : 90156 : nbp = 0;
3130 : 90156 : goto ldist_done;
3131 : : }
3132 : :
3133 : : /* If we are only distributing patterns fuse all partitions that
3134 : : were not classified as builtins. This also avoids chopping
3135 : : a loop into pieces, separated by builtin calls. That is, we
3136 : : only want no or a single loop body remaining. */
3137 : 36206 : struct partition *into;
3138 : 36206 : if (only_patterns_p)
3139 : : {
3140 : 16788 : for (i = 0; partitions.iterate (i, &into); ++i)
3141 : 9936 : if (!partition_builtin_p (into))
3142 : : break;
3143 : 10814 : for (++i; partitions.iterate (i, &partition); ++i)
3144 : 2540 : if (!partition_builtin_p (partition))
3145 : : {
3146 : 2001 : partition_merge_into (NULL, into, partition, FUSE_NON_BUILTIN);
3147 : 2001 : partitions.unordered_remove (i);
3148 : 2001 : partition_free (partition);
3149 : 2001 : i--;
3150 : : }
3151 : : }
3152 : :
3153 : : /* Due to limitations in the transform phase we have to fuse all
3154 : : reduction partitions into the last partition so the existing
3155 : : loop will contain all loop-closed PHI nodes. */
3156 : 99367 : for (i = 0; partitions.iterate (i, &into); ++i)
3157 : 65034 : if (partition_reduction_p (into))
3158 : : break;
3159 : 38345 : for (i = i + 1; partitions.iterate (i, &partition); ++i)
3160 : 2139 : if (partition_reduction_p (partition))
3161 : : {
3162 : 1932 : partition_merge_into (rdg, into, partition, FUSE_REDUCTION);
3163 : 1932 : partitions.unordered_remove (i);
3164 : 1932 : partition_free (partition);
3165 : 1932 : i--;
3166 : : }
3167 : :
3168 : : /* Apply our simple cost model - fuse partitions with similar
3169 : : memory accesses. */
3170 : 98514 : for (i = 0; partitions.iterate (i, &into); ++i)
3171 : : {
3172 : 62308 : bool changed = false;
3173 : 733952 : for (int j = i + 1; partitions.iterate (j, &partition); ++j)
3174 : : {
3175 : 671644 : if (share_memory_accesses (rdg, into, partition))
3176 : : {
3177 : 5924 : partition_merge_into (rdg, into, partition, FUSE_SHARE_REF);
3178 : 5924 : partitions.unordered_remove (j);
3179 : 5924 : partition_free (partition);
3180 : 5924 : j--;
3181 : 5924 : changed = true;
3182 : : }
3183 : : }
3184 : : /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
3185 : : accesses when 1 and 2 have similar accesses but not 0 and 1
3186 : : then in the next iteration we will fail to consider merging
3187 : : 1 into 0,2. So try again if we did any merging into 0. */
3188 : 62308 : if (changed)
3189 : 2991 : i--;
3190 : : }
3191 : :
3192 : : /* Put a non-builtin partition last if we need to preserve a reduction.
3193 : : In most cases this helps to keep a normal partition last avoiding to
3194 : : spill a reduction result across builtin calls.
3195 : : ??? The proper way would be to use dependences to see whether we
3196 : : can move builtin partitions earlier during merge_dep_scc_partitions
3197 : : and its sort_partitions_by_post_order. Especially when the
3198 : : dependence graph is composed of multiple independent subgraphs the
3199 : : heuristic does not work reliably. */
3200 : 36206 : if (reduction_in_all
3201 : 42564 : && partition_builtin_p (partitions.last()))
3202 : 144 : FOR_EACH_VEC_ELT (partitions, i, partition)
3203 : 80 : if (!partition_builtin_p (partition))
3204 : : {
3205 : 15 : partitions.unordered_remove (i);
3206 : 15 : partitions.quick_push (partition);
3207 : 15 : break;
3208 : : }
3209 : :
3210 : : /* Build the partition dependency graph and fuse partitions in strong
3211 : : connected component. */
3212 : 36206 : if (partitions.length () > 1)
3213 : : {
3214 : : /* Don't support loop nest distribution under runtime alias check
3215 : : since it's not likely to enable many vectorization opportunities.
3216 : : Also if loop has any data reference which may be not addressable
3217 : : since alias check needs to take, compare address of the object. */
3218 : 6179 : if (loop->inner || has_nonaddressable_dataref_p)
3219 : 331 : merge_dep_scc_partitions (rdg, &partitions, false);
3220 : : else
3221 : : {
3222 : 5848 : merge_dep_scc_partitions (rdg, &partitions, true);
3223 : 5848 : if (partitions.length () > 1)
3224 : 5265 : break_alias_scc_partitions (rdg, &partitions, &alias_ddrs);
3225 : : }
3226 : : }
3227 : :
3228 : 36206 : finalize_partitions (loop, &partitions, &alias_ddrs);
3229 : :
3230 : : /* If there is a reduction in all partitions make sure the last
3231 : : non-builtin partition provides the LC PHI defs. */
3232 : 36206 : if (reduction_in_all)
3233 : : {
3234 : 12754 : FOR_EACH_VEC_ELT (partitions, i, partition)
3235 : 6396 : if (!partition_builtin_p (partition))
3236 : 6316 : reduction_partition_num = i;
3237 : 6358 : if (reduction_partition_num == -1)
3238 : : {
3239 : : /* If all partitions are builtin, force the last one to
3240 : : be code generated as normal partition. */
3241 : 64 : partition = partitions.last ();
3242 : 64 : partition->kind = PKIND_NORMAL;
3243 : : }
3244 : : }
3245 : :
3246 : 36206 : nbp = partitions.length ();
3247 : 36206 : if (nbp == 0
3248 : 69953 : || (nbp == 1 && !partition_builtin_p (partitions[0]))
3249 : 47719 : || (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
3250 : : {
3251 : 24749 : nbp = 0;
3252 : 24749 : goto ldist_done;
3253 : : }
3254 : :
3255 : 11514 : if (version_for_distribution_p (&partitions, &alias_ddrs))
3256 : 57 : version_loop_by_alias_check (&partitions, loop, &alias_ddrs);
3257 : :
3258 : 11457 : if (dump_file && (dump_flags & TDF_DETAILS))
3259 : : {
3260 : 39 : fprintf (dump_file,
3261 : : "distribute loop <%d> into partitions:\n", loop->num);
3262 : 39 : dump_rdg_partitions (dump_file, partitions);
3263 : : }
3264 : :
3265 : 25785 : FOR_EACH_VEC_ELT (partitions, i, partition)
3266 : : {
3267 : 14328 : if (partition_builtin_p (partition))
3268 : 11561 : (*nb_calls)++;
3269 : 14328 : *destroy_p |= generate_code_for_partition (loop, partition, i < nbp - 1,
3270 : : i == reduction_partition_num);
3271 : : }
3272 : :
3273 : 126362 : ldist_done:
3274 : 126362 : loop_nest.release ();
3275 : 126362 : free_data_refs (datarefs_vec);
3276 : 126362 : for (hash_table<ddr_hasher>::iterator iter = ddrs_table->begin ();
3277 : 2110398 : iter != ddrs_table->end (); ++iter)
3278 : : {
3279 : 992018 : free_dependence_relation (*iter);
3280 : 992018 : *iter = NULL;
3281 : : }
3282 : 126362 : delete ddrs_table;
3283 : :
3284 : 317585 : FOR_EACH_VEC_ELT (partitions, i, partition)
3285 : 191223 : partition_free (partition);
3286 : :
3287 : 126362 : free_rdg (rdg, loop);
3288 : 126362 : return nbp - *nb_calls;
3289 : 126362 : }
3290 : :
3291 : :
3292 : 192204 : void loop_distribution::bb_top_order_init (void)
3293 : : {
3294 : 192204 : int rpo_num;
3295 : 192204 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
3296 : 192204 : edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3297 : 192204 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
3298 : :
3299 : 192204 : bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun));
3300 : 192204 : bb_top_order_index_size = last_basic_block_for_fn (cfun);
3301 : :
3302 : 192204 : entry->flags &= ~EDGE_DFS_BACK;
3303 : 192204 : bitmap_set_bit (exit_bbs, EXIT_BLOCK);
3304 : 192204 : rpo_num = rev_post_order_and_mark_dfs_back_seme (cfun, entry, exit_bbs, true,
3305 : : rpo, NULL);
3306 : 192204 : BITMAP_FREE (exit_bbs);
3307 : :
3308 : 6747876 : for (int i = 0; i < rpo_num; i++)
3309 : 6555672 : bb_top_order_index[rpo[i]] = i;
3310 : :
3311 : 192204 : free (rpo);
3312 : 192204 : }
3313 : :
3314 : 192204 : void loop_distribution::bb_top_order_destroy ()
3315 : : {
3316 : 192204 : free (bb_top_order_index);
3317 : 192204 : bb_top_order_index = NULL;
3318 : 192204 : bb_top_order_index_size = 0;
3319 : 192204 : }
3320 : :
3321 : :
3322 : : /* Given LOOP, this function records seed statements for distribution in
3323 : : WORK_LIST. Return false if there is nothing for distribution. */
3324 : :
3325 : : static bool
3326 : 168889 : find_seed_stmts_for_distribution (class loop *loop, vec<gimple *> *work_list)
3327 : : {
3328 : 168889 : basic_block *bbs = get_loop_body_in_dom_order (loop);
3329 : :
3330 : : /* Initialize the worklist with stmts we seed the partitions with. */
3331 : 616399 : for (unsigned i = 0; i < loop->num_nodes; ++i)
3332 : : {
3333 : : /* In irreducible sub-regions we don't know how to redirect
3334 : : conditions, so fail. See PR100492. */
3335 : 487439 : if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
3336 : : {
3337 : 4 : if (dump_file && (dump_flags & TDF_DETAILS))
3338 : 0 : fprintf (dump_file, "loop %d contains an irreducible region.\n",
3339 : : loop->num);
3340 : 4 : work_list->truncate (0);
3341 : 4 : break;
3342 : : }
3343 : 487435 : for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
3344 : 1150025 : !gsi_end_p (gsi); gsi_next (&gsi))
3345 : : {
3346 : 662590 : gphi *phi = gsi.phi ();
3347 : 1325180 : if (virtual_operand_p (gimple_phi_result (phi)))
3348 : 177757 : continue;
3349 : : /* Distribute stmts which have defs that are used outside of
3350 : : the loop. */
3351 : 484833 : if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
3352 : 462346 : continue;
3353 : 22487 : work_list->safe_push (phi);
3354 : : }
3355 : 974870 : for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
3356 : 3212108 : !gsi_end_p (gsi); gsi_next (&gsi))
3357 : : {
3358 : 2764598 : gimple *stmt = gsi_stmt (gsi);
3359 : :
3360 : : /* Ignore clobbers, they do not have true side effects. */
3361 : 2764598 : if (gimple_clobber_p (stmt))
3362 : 2485143 : continue;
3363 : :
3364 : : /* If there is a stmt with side-effects bail out - we
3365 : : cannot and should not distribute this loop. */
3366 : 2760713 : if (gimple_has_side_effects (stmt))
3367 : : {
3368 : 39925 : free (bbs);
3369 : 39925 : return false;
3370 : : }
3371 : :
3372 : : /* Distribute stmts which have defs that are used outside of
3373 : : the loop. */
3374 : 2720788 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3375 : : ;
3376 : : /* Otherwise only distribute stores for now. */
3377 : 4323375 : else if (!gimple_vdef (stmt))
3378 : 2481258 : continue;
3379 : :
3380 : 239530 : work_list->safe_push (stmt);
3381 : : }
3382 : : }
3383 : 128964 : bool res = work_list->length () > 0;
3384 : 128829 : if (res && !can_copy_bbs_p (bbs, loop->num_nodes))
3385 : : {
3386 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
3387 : 0 : fprintf (dump_file, "cannot copy loop %d.\n", loop->num);
3388 : : res = false;
3389 : : }
3390 : 128964 : free (bbs);
3391 : 128964 : return res;
3392 : : }
3393 : :
3394 : : /* A helper function for generate_{rawmemchr,strlen}_builtin functions in order
3395 : : to place new statements SEQ before LOOP and replace the old reduction
3396 : : variable with the new one. */
3397 : :
3398 : : static void
3399 : 24 : generate_reduction_builtin_1 (loop_p loop, gimple_seq &seq,
3400 : : tree reduction_var_old, tree reduction_var_new,
3401 : : const char *info, machine_mode load_mode)
3402 : : {
3403 : 24 : gcc_assert (flag_tree_loop_distribute_patterns);
3404 : :
3405 : : /* Place new statements before LOOP. */
3406 : 24 : gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
3407 : 24 : gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
3408 : :
3409 : : /* Replace old reduction variable with new one. */
3410 : 24 : imm_use_iterator iter;
3411 : 24 : gimple *stmt;
3412 : 24 : use_operand_p use_p;
3413 : 94 : FOR_EACH_IMM_USE_STMT (stmt, iter, reduction_var_old)
3414 : : {
3415 : 280 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3416 : 70 : SET_USE (use_p, reduction_var_new);
3417 : :
3418 : 70 : update_stmt (stmt);
3419 : 24 : }
3420 : :
3421 : 24 : if (dump_file && (dump_flags & TDF_DETAILS))
3422 : 7 : fprintf (dump_file, info, GET_MODE_NAME (load_mode));
3423 : 24 : }
3424 : :
3425 : : /* Generate a call to rawmemchr and place it before LOOP. REDUCTION_VAR is
3426 : : replaced with a fresh SSA name representing the result of the call. */
3427 : :
3428 : : static void
3429 : 0 : generate_rawmemchr_builtin (loop_p loop, tree reduction_var,
3430 : : data_reference_p store_dr, tree base, tree pattern,
3431 : : location_t loc)
3432 : : {
3433 : 0 : gimple_seq seq = NULL;
3434 : :
3435 : 0 : tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3436 : 0 : gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, mem, pattern);
3437 : 0 : tree reduction_var_new = copy_ssa_name (reduction_var);
3438 : 0 : gimple_call_set_lhs (fn_call, reduction_var_new);
3439 : 0 : gimple_set_location (fn_call, loc);
3440 : 0 : gimple_seq_add_stmt (&seq, fn_call);
3441 : :
3442 : 0 : if (store_dr)
3443 : : {
3444 : 0 : gassign *g = gimple_build_assign (DR_REF (store_dr), reduction_var_new);
3445 : 0 : gimple_seq_add_stmt (&seq, g);
3446 : : }
3447 : :
3448 : 0 : generate_reduction_builtin_1 (loop, seq, reduction_var, reduction_var_new,
3449 : : "generated rawmemchr%s\n",
3450 : 0 : TYPE_MODE (TREE_TYPE (TREE_TYPE (base))));
3451 : 0 : }
3452 : :
3453 : : /* Helper function for generate_strlen_builtin(,_using_rawmemchr) */
3454 : :
3455 : : static void
3456 : 24 : generate_strlen_builtin_1 (loop_p loop, gimple_seq &seq,
3457 : : tree reduction_var_old, tree reduction_var_new,
3458 : : machine_mode mode, tree start_len)
3459 : : {
3460 : : /* REDUCTION_VAR_NEW has either size type or ptrdiff type and must be
3461 : : converted if types of old and new reduction variable are not compatible. */
3462 : 24 : reduction_var_new = gimple_convert (&seq, TREE_TYPE (reduction_var_old),
3463 : : reduction_var_new);
3464 : :
3465 : : /* Loops of the form `for (i=42; s[i]; ++i);` have an additional start
3466 : : length. */
3467 : 24 : if (!integer_zerop (start_len))
3468 : : {
3469 : 20 : tree lhs = make_ssa_name (TREE_TYPE (reduction_var_new));
3470 : 20 : gimple *g = gimple_build_assign (lhs, PLUS_EXPR, reduction_var_new,
3471 : : start_len);
3472 : 20 : gimple_seq_add_stmt (&seq, g);
3473 : 20 : reduction_var_new = lhs;
3474 : : }
3475 : :
3476 : 24 : generate_reduction_builtin_1 (loop, seq, reduction_var_old, reduction_var_new,
3477 : : "generated strlen%s\n", mode);
3478 : 24 : }
3479 : :
3480 : : /* Generate a call to strlen and place it before LOOP. REDUCTION_VAR is
3481 : : replaced with a fresh SSA name representing the result of the call. */
3482 : :
3483 : : static void
3484 : 24 : generate_strlen_builtin (loop_p loop, tree reduction_var, tree base,
3485 : : tree start_len, location_t loc)
3486 : : {
3487 : 24 : gimple_seq seq = NULL;
3488 : :
3489 : 24 : tree reduction_var_new = make_ssa_name (size_type_node);
3490 : :
3491 : 24 : tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3492 : 48 : tree fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_STRLEN));
3493 : 24 : gimple *fn_call = gimple_build_call (fn, 1, mem);
3494 : 24 : gimple_call_set_lhs (fn_call, reduction_var_new);
3495 : 24 : gimple_set_location (fn_call, loc);
3496 : 24 : gimple_seq_add_stmt (&seq, fn_call);
3497 : :
3498 : 24 : generate_strlen_builtin_1 (loop, seq, reduction_var, reduction_var_new,
3499 : : QImode, start_len);
3500 : 24 : }
3501 : :
3502 : : /* Generate code in order to mimic the behaviour of strlen but this time over
3503 : : an array of elements with mode different than QI. REDUCTION_VAR is replaced
3504 : : with a fresh SSA name representing the result, i.e., the length. */
3505 : :
3506 : : static void
3507 : 0 : generate_strlen_builtin_using_rawmemchr (loop_p loop, tree reduction_var,
3508 : : tree base, tree load_type,
3509 : : tree start_len, location_t loc)
3510 : : {
3511 : 0 : gimple_seq seq = NULL;
3512 : :
3513 : 0 : tree start = force_gimple_operand (base, &seq, true, NULL_TREE);
3514 : 0 : tree zero = build_zero_cst (load_type);
3515 : 0 : gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, start, zero);
3516 : 0 : tree end = make_ssa_name (TREE_TYPE (base));
3517 : 0 : gimple_call_set_lhs (fn_call, end);
3518 : 0 : gimple_set_location (fn_call, loc);
3519 : 0 : gimple_seq_add_stmt (&seq, fn_call);
3520 : :
3521 : : /* Determine the number of elements between START and END by
3522 : : evaluating (END - START) / sizeof (*START). */
3523 : 0 : tree diff = make_ssa_name (ptrdiff_type_node);
3524 : 0 : gimple *diff_stmt = gimple_build_assign (diff, POINTER_DIFF_EXPR, end, start);
3525 : 0 : gimple_seq_add_stmt (&seq, diff_stmt);
3526 : : /* Let SIZE be the size of each character. */
3527 : 0 : tree size = gimple_convert (&seq, ptrdiff_type_node,
3528 : 0 : TYPE_SIZE_UNIT (load_type));
3529 : 0 : tree count = make_ssa_name (ptrdiff_type_node);
3530 : 0 : gimple *count_stmt = gimple_build_assign (count, TRUNC_DIV_EXPR, diff, size);
3531 : 0 : gimple_seq_add_stmt (&seq, count_stmt);
3532 : :
3533 : 0 : generate_strlen_builtin_1 (loop, seq, reduction_var, count,
3534 : 0 : TYPE_MODE (load_type),
3535 : : start_len);
3536 : 0 : }
3537 : :
3538 : : /* Return true if we can count at least as many characters by taking pointer
3539 : : difference as we can count via reduction_var without an overflow. Thus
3540 : : compute 2^n < (2^(m-1) / s) where n = TYPE_PRECISION (reduction_var_type),
3541 : : m = TYPE_PRECISION (ptrdiff_type_node), and s = size of each character. */
3542 : : static bool
3543 : 0 : reduction_var_overflows_first (tree reduction_var_type, tree load_type)
3544 : : {
3545 : 0 : widest_int n2 = wi::lshift (1, TYPE_PRECISION (reduction_var_type));;
3546 : 0 : widest_int m2 = wi::lshift (1, TYPE_PRECISION (ptrdiff_type_node) - 1);
3547 : 0 : widest_int s = wi::to_widest (TYPE_SIZE_UNIT (load_type));
3548 : 0 : return wi::ltu_p (n2, wi::udiv_trunc (m2, s));
3549 : 0 : }
3550 : :
3551 : : static gimple *
3552 : 22983 : determine_reduction_stmt_1 (const loop_p loop, const basic_block *bbs)
3553 : : {
3554 : 22983 : gimple *reduction_stmt = NULL;
3555 : :
3556 : 82881 : for (unsigned i = 0, ninsns = 0; i < loop->num_nodes; ++i)
3557 : : {
3558 : 64784 : basic_block bb = bbs[i];
3559 : :
3560 : 125665 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
3561 : 60881 : gsi_next (&bsi))
3562 : : {
3563 : 61795 : gphi *phi = bsi.phi ();
3564 : 123590 : if (virtual_operand_p (gimple_phi_result (phi)))
3565 : 19280 : continue;
3566 : 42515 : if (stmt_has_scalar_dependences_outside_loop (loop, phi))
3567 : : {
3568 : 7871 : if (reduction_stmt)
3569 : 914 : return NULL;
3570 : : reduction_stmt = phi;
3571 : : }
3572 : : }
3573 : :
3574 : 63870 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
3575 : 195168 : !gsi_end_p (bsi); gsi_next_nondebug (&bsi), ++ninsns)
3576 : : {
3577 : : /* Bail out early for loops which are unlikely to match. */
3578 : 135270 : if (ninsns > 16)
3579 : 3972 : return NULL;
3580 : 133130 : gimple *stmt = gsi_stmt (bsi);
3581 : 133130 : if (gimple_clobber_p (stmt))
3582 : 4651 : continue;
3583 : 128479 : if (gimple_code (stmt) == GIMPLE_LABEL)
3584 : 732 : continue;
3585 : 227142 : if (gimple_has_volatile_ops (stmt))
3586 : : return NULL;
3587 : 127708 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3588 : : {
3589 : 6146 : if (reduction_stmt)
3590 : : return NULL;
3591 : : reduction_stmt = stmt;
3592 : : }
3593 : : }
3594 : : }
3595 : :
3596 : : return reduction_stmt;
3597 : : }
3598 : :
3599 : : /* If LOOP has a single non-volatile reduction statement, then return a pointer
3600 : : to it. Otherwise return NULL. */
3601 : : static gimple *
3602 : 22983 : determine_reduction_stmt (const loop_p loop)
3603 : : {
3604 : 22983 : basic_block *bbs = get_loop_body (loop);
3605 : 22983 : gimple *reduction_stmt = determine_reduction_stmt_1 (loop, bbs);
3606 : 22983 : XDELETEVEC (bbs);
3607 : 22983 : return reduction_stmt;
3608 : : }
3609 : :
3610 : : /* Transform loops which mimic the effects of builtins rawmemchr or strlen and
3611 : : replace them accordingly. For example, a loop of the form
3612 : :
3613 : : for (; *p != 42; ++p);
3614 : :
3615 : : is replaced by
3616 : :
3617 : : p = rawmemchr<MODE> (p, 42);
3618 : :
3619 : : under the assumption that rawmemchr is available for a particular MODE.
3620 : : Another example is
3621 : :
3622 : : int i;
3623 : : for (i = 42; s[i]; ++i);
3624 : :
3625 : : which is replaced by
3626 : :
3627 : : i = (int)strlen (&s[42]) + 42;
3628 : :
3629 : : for some character array S. In case array S is not of type character array
3630 : : we end up with
3631 : :
3632 : : i = (int)(rawmemchr<MODE> (&s[42], 0) - &s[42]) + 42;
3633 : :
3634 : : assuming that rawmemchr is available for a particular MODE. */
3635 : :
3636 : : bool
3637 : 79481 : loop_distribution::transform_reduction_loop (loop_p loop)
3638 : : {
3639 : 79481 : gimple *reduction_stmt;
3640 : 79481 : data_reference_p load_dr = NULL, store_dr = NULL;
3641 : :
3642 : 79481 : edge e = single_exit (loop);
3643 : 230855 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (e->src));
3644 : 62010 : if (!cond)
3645 : : return false;
3646 : : /* Ensure loop condition is an (in)equality test and loop is exited either if
3647 : : the inequality test fails or the equality test succeeds. */
3648 : 46915 : if (!(e->flags & EDGE_FALSE_VALUE && gimple_cond_code (cond) == NE_EXPR)
3649 : 81174 : && !(e->flags & EDGE_TRUE_VALUE && gimple_cond_code (cond) == EQ_EXPR))
3650 : : return false;
3651 : : /* A limitation of the current implementation is that we only support
3652 : : constant patterns in (in)equality tests. */
3653 : 30268 : tree pattern = gimple_cond_rhs (cond);
3654 : 30268 : if (TREE_CODE (pattern) != INTEGER_CST)
3655 : : return false;
3656 : :
3657 : 22983 : reduction_stmt = determine_reduction_stmt (loop);
3658 : :
3659 : : /* A limitation of the current implementation is that we require a reduction
3660 : : statement. Therefore, loops without a reduction statement as in the
3661 : : following are not recognized:
3662 : : int *p;
3663 : : void foo (void) { for (; *p; ++p); } */
3664 : 22983 : if (reduction_stmt == NULL)
3665 : : return false;
3666 : :
3667 : : /* Reduction variables are guaranteed to be SSA names. */
3668 : 8436 : tree reduction_var;
3669 : 8436 : switch (gimple_code (reduction_stmt))
3670 : : {
3671 : 8302 : case GIMPLE_ASSIGN:
3672 : 8302 : case GIMPLE_PHI:
3673 : 8302 : reduction_var = gimple_get_lhs (reduction_stmt);
3674 : 8302 : break;
3675 : : default:
3676 : : /* Bail out e.g. for GIMPLE_CALL. */
3677 : : return false;
3678 : : }
3679 : :
3680 : 8302 : struct graph *rdg = build_rdg (loop, NULL);
3681 : 8302 : if (rdg == NULL)
3682 : : {
3683 : 714 : if (dump_file && (dump_flags & TDF_DETAILS))
3684 : 0 : fprintf (dump_file,
3685 : : "Loop %d not transformed: failed to build the RDG.\n",
3686 : : loop->num);
3687 : :
3688 : 714 : return false;
3689 : : }
3690 : 15176 : auto_bitmap partition_stmts;
3691 : 7588 : bitmap_set_range (partition_stmts, 0, rdg->n_vertices);
3692 : 7588 : find_single_drs (loop, rdg, partition_stmts, &store_dr, &load_dr);
3693 : 7588 : free_rdg (rdg, loop);
3694 : :
3695 : : /* Bail out if there is no single load. */
3696 : 7588 : if (load_dr == NULL)
3697 : : return false;
3698 : :
3699 : : /* Reaching this point we have a loop with a single reduction variable,
3700 : : a single load, and an optional single store. */
3701 : :
3702 : 3741 : tree load_ref = DR_REF (load_dr);
3703 : 3741 : tree load_type = TREE_TYPE (load_ref);
3704 : 3741 : tree load_access_base = build_fold_addr_expr (load_ref);
3705 : 3741 : tree load_access_size = TYPE_SIZE_UNIT (load_type);
3706 : 3741 : affine_iv load_iv, reduction_iv;
3707 : :
3708 : 3741 : if (!INTEGRAL_TYPE_P (load_type)
3709 : 3741 : || !type_has_mode_precision_p (load_type))
3710 : 2424 : return false;
3711 : :
3712 : : /* We already ensured that the loop condition tests for (in)equality where the
3713 : : rhs is a constant pattern. Now ensure that the lhs is the result of the
3714 : : load. */
3715 : 1317 : if (gimple_cond_lhs (cond) != gimple_assign_lhs (DR_STMT (load_dr)))
3716 : : return false;
3717 : :
3718 : : /* Bail out if no affine induction variable with constant step can be
3719 : : determined. */
3720 : 1151 : if (!simple_iv (loop, loop, load_access_base, &load_iv, false))
3721 : : return false;
3722 : :
3723 : : /* Bail out if memory accesses are not consecutive or not growing. */
3724 : 1142 : if (!operand_equal_p (load_iv.step, load_access_size, 0))
3725 : : return false;
3726 : :
3727 : 1122 : if (!simple_iv (loop, loop, reduction_var, &reduction_iv, false))
3728 : : return false;
3729 : :
3730 : : /* Handle rawmemchr like loops. */
3731 : 1010 : if (operand_equal_p (load_iv.base, reduction_iv.base)
3732 : 1010 : && operand_equal_p (load_iv.step, reduction_iv.step))
3733 : : {
3734 : 270 : if (store_dr)
3735 : : {
3736 : : /* Ensure that we store to X and load from X+I where I>0. */
3737 : 0 : if (TREE_CODE (load_iv.base) != POINTER_PLUS_EXPR
3738 : 0 : || !integer_onep (TREE_OPERAND (load_iv.base, 1)))
3739 : 0 : return false;
3740 : 0 : tree ptr_base = TREE_OPERAND (load_iv.base, 0);
3741 : 0 : if (TREE_CODE (ptr_base) != SSA_NAME)
3742 : : return false;
3743 : 0 : gimple *def = SSA_NAME_DEF_STMT (ptr_base);
3744 : 0 : if (!gimple_assign_single_p (def)
3745 : 0 : || gimple_assign_rhs1 (def) != DR_REF (store_dr))
3746 : : return false;
3747 : : /* Ensure that the reduction value is stored. */
3748 : 0 : if (gimple_assign_rhs1 (DR_STMT (store_dr)) != reduction_var)
3749 : : return false;
3750 : : }
3751 : : /* Bail out if target does not provide rawmemchr for a certain mode. */
3752 : 270 : machine_mode mode = TYPE_MODE (load_type);
3753 : 270 : if (direct_optab_handler (rawmemchr_optab, mode) == CODE_FOR_nothing)
3754 : : return false;
3755 : 0 : location_t loc = gimple_location (DR_STMT (load_dr));
3756 : 0 : generate_rawmemchr_builtin (loop, reduction_var, store_dr, load_iv.base,
3757 : : pattern, loc);
3758 : 0 : return true;
3759 : : }
3760 : :
3761 : : /* Handle strlen like loops. */
3762 : 740 : if (store_dr == NULL
3763 : 730 : && integer_zerop (pattern)
3764 : 730 : && INTEGRAL_TYPE_P (TREE_TYPE (reduction_var))
3765 : 720 : && TREE_CODE (reduction_iv.base) == INTEGER_CST
3766 : 716 : && TREE_CODE (reduction_iv.step) == INTEGER_CST
3767 : 1456 : && integer_onep (reduction_iv.step))
3768 : : {
3769 : 683 : location_t loc = gimple_location (DR_STMT (load_dr));
3770 : 683 : tree reduction_var_type = TREE_TYPE (reduction_var);
3771 : : /* While determining the length of a string an overflow might occur.
3772 : : If an overflow only occurs in the loop implementation and not in the
3773 : : strlen implementation, then either the overflow is undefined or the
3774 : : truncated result of strlen equals the one of the loop. Otherwise if
3775 : : an overflow may also occur in the strlen implementation, then
3776 : : replacing a loop by a call to strlen is sound whenever we ensure that
3777 : : if an overflow occurs in the strlen implementation, then also an
3778 : : overflow occurs in the loop implementation which is undefined. It
3779 : : seems reasonable to relax this and assume that the strlen
3780 : : implementation cannot overflow in case sizetype is big enough in the
3781 : : sense that an overflow can only happen for string objects which are
3782 : : bigger than half of the address space; at least for 32-bit targets and
3783 : : up.
3784 : :
3785 : : For strlen which makes use of rawmemchr the maximal length of a string
3786 : : which can be determined without an overflow is PTRDIFF_MAX / S where
3787 : : each character has size S. Since an overflow for ptrdiff type is
3788 : : undefined we have to make sure that if an overflow occurs, then an
3789 : : overflow occurs in the loop implementation, too, and this is
3790 : : undefined, too. Similar as before we relax this and assume that no
3791 : : string object is larger than half of the address space; at least for
3792 : : 32-bit targets and up. */
3793 : 683 : if (TYPE_MODE (load_type) == TYPE_MODE (char_type_node)
3794 : 355 : && TYPE_PRECISION (load_type) == TYPE_PRECISION (char_type_node)
3795 : 355 : && ((TYPE_PRECISION (sizetype) >= TYPE_PRECISION (ptr_type_node) - 1
3796 : 355 : && TYPE_PRECISION (ptr_type_node) >= 32)
3797 : 0 : || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3798 : 0 : && TYPE_PRECISION (reduction_var_type) <= TYPE_PRECISION (sizetype)))
3799 : 707 : && builtin_decl_implicit (BUILT_IN_STRLEN))
3800 : 24 : generate_strlen_builtin (loop, reduction_var, load_iv.base,
3801 : : reduction_iv.base, loc);
3802 : 659 : else if (direct_optab_handler (rawmemchr_optab, TYPE_MODE (load_type))
3803 : : != CODE_FOR_nothing
3804 : 659 : && ((TYPE_PRECISION (ptrdiff_type_node) == TYPE_PRECISION (ptr_type_node)
3805 : 0 : && TYPE_PRECISION (ptrdiff_type_node) >= 32)
3806 : 0 : || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3807 : 0 : && reduction_var_overflows_first (reduction_var_type, load_type))))
3808 : 0 : generate_strlen_builtin_using_rawmemchr (loop, reduction_var,
3809 : : load_iv.base,
3810 : : load_type,
3811 : : reduction_iv.base, loc);
3812 : : else
3813 : 659 : return false;
3814 : 24 : return true;
3815 : : }
3816 : :
3817 : : return false;
3818 : : }
3819 : :
3820 : : /* Given innermost LOOP, return the outermost enclosing loop that forms a
3821 : : perfect loop nest. */
3822 : :
3823 : : static class loop *
3824 : 152684 : prepare_perfect_loop_nest (class loop *loop)
3825 : : {
3826 : 152684 : class loop *outer = loop_outer (loop);
3827 : 152684 : tree niters = number_of_latch_executions (loop);
3828 : :
3829 : : /* TODO: We only support the innermost 3-level loop nest distribution
3830 : : because of compilation time issue for now. This should be relaxed
3831 : : in the future. Note we only allow 3-level loop nest distribution
3832 : : when parallelizing loops. */
3833 : 152684 : while ((loop->inner == NULL
3834 : 16672 : || (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
3835 : 152754 : && loop_outer (outer)
3836 : 37935 : && outer->inner == loop && loop->next == NULL
3837 : 25281 : && single_exit (outer)
3838 : 23879 : && !chrec_contains_symbols_defined_in_loop (niters, outer->num)
3839 : 17601 : && (niters = number_of_latch_executions (outer)) != NULL_TREE
3840 : 186957 : && niters != chrec_dont_know)
3841 : : {
3842 : 16672 : loop = outer;
3843 : 16672 : outer = loop_outer (loop);
3844 : : }
3845 : :
3846 : 152684 : return loop;
3847 : : }
3848 : :
3849 : :
3850 : : unsigned int
3851 : 192204 : loop_distribution::execute (function *fun)
3852 : : {
3853 : 192204 : bool changed = false;
3854 : 192204 : basic_block bb;
3855 : 192204 : control_dependences *cd = NULL;
3856 : 192204 : auto_vec<loop_p> loops_to_be_destroyed;
3857 : :
3858 : 569005 : if (number_of_loops (fun) <= 1)
3859 : : return 0;
3860 : :
3861 : 192204 : bb_top_order_init ();
3862 : :
3863 : 7132284 : FOR_ALL_BB_FN (bb, fun)
3864 : : {
3865 : 6940080 : gimple_stmt_iterator gsi;
3866 : 10926396 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3867 : 3986316 : gimple_set_uid (gsi_stmt (gsi), -1);
3868 : 57519769 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3869 : 43639609 : gimple_set_uid (gsi_stmt (gsi), -1);
3870 : : }
3871 : :
3872 : : /* We can at the moment only distribute non-nested loops, thus restrict
3873 : : walking to innermost loops. */
3874 : 966307 : for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
3875 : : {
3876 : : /* Don't distribute multiple exit edges loop, or cold loop when
3877 : : not doing pattern detection. */
3878 : 389695 : if (!single_exit (loop)
3879 : 389695 : || (!flag_tree_loop_distribute_patterns
3880 : 1141 : && !optimize_loop_for_speed_p (loop)))
3881 : 157314 : continue;
3882 : :
3883 : : /* If niters is unknown don't distribute loop but rather try to transform
3884 : : it to a call to a builtin. */
3885 : 232381 : tree niters = number_of_latch_executions (loop);
3886 : 232381 : if (niters == NULL_TREE || niters == chrec_dont_know)
3887 : : {
3888 : 79697 : datarefs_vec.create (20);
3889 : 79697 : if (flag_tree_loop_distribute_patterns
3890 : 79697 : && transform_reduction_loop (loop))
3891 : : {
3892 : 24 : changed = true;
3893 : 24 : loops_to_be_destroyed.safe_push (loop);
3894 : 24 : if (dump_enabled_p ())
3895 : : {
3896 : 7 : dump_user_location_t loc = find_loop_location (loop);
3897 : 7 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3898 : : loc, "Loop %d transformed into a builtin.\n",
3899 : : loop->num);
3900 : : }
3901 : : }
3902 : 79697 : free_data_refs (datarefs_vec);
3903 : 79697 : continue;
3904 : 79697 : }
3905 : :
3906 : : /* Get the perfect loop nest for distribution. */
3907 : 152684 : loop = prepare_perfect_loop_nest (loop);
3908 : 310116 : for (; loop; loop = loop->inner)
3909 : : {
3910 : 168889 : auto_vec<gimple *> work_list;
3911 : 168889 : if (!find_seed_stmts_for_distribution (loop, &work_list))
3912 : 40069 : continue;
3913 : :
3914 : 128820 : const char *str = loop->inner ? " nest" : "";
3915 : 128820 : dump_user_location_t loc = find_loop_location (loop);
3916 : 128820 : if (!cd)
3917 : : {
3918 : 57901 : calculate_dominance_info (CDI_DOMINATORS);
3919 : 57901 : calculate_dominance_info (CDI_POST_DOMINATORS);
3920 : 57901 : cd = new control_dependences ();
3921 : 57901 : free_dominance_info (CDI_POST_DOMINATORS);
3922 : : }
3923 : :
3924 : 128820 : bool destroy_p;
3925 : 128820 : int nb_generated_loops, nb_generated_calls;
3926 : 128820 : bool only_patterns = !optimize_loop_for_speed_p (loop)
3927 : 128820 : || !flag_tree_loop_distribution;
3928 : : /* do not try to distribute loops that are not expected to iterate. */
3929 : 28175 : if (!only_patterns)
3930 : : {
3931 : 28175 : HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
3932 : 28175 : if (iterations < 0)
3933 : 13251 : iterations = likely_max_loop_iterations_int (loop);
3934 : 28175 : if (!iterations)
3935 : 100655 : only_patterns = true;
3936 : : }
3937 : 128820 : nb_generated_loops
3938 : 128820 : = distribute_loop (loop, work_list, cd, &nb_generated_calls,
3939 : : &destroy_p, only_patterns);
3940 : 128820 : if (destroy_p)
3941 : 9697 : loops_to_be_destroyed.safe_push (loop);
3942 : :
3943 : 128820 : if (nb_generated_loops + nb_generated_calls > 0)
3944 : : {
3945 : 11457 : changed = true;
3946 : 11457 : if (dump_enabled_p ())
3947 : 68 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3948 : : loc, "Loop%s %d distributed: split to %d loops "
3949 : : "and %d library calls.\n", str, loop->num,
3950 : : nb_generated_loops, nb_generated_calls);
3951 : :
3952 : 11457 : break;
3953 : : }
3954 : :
3955 : 117363 : if (dump_file && (dump_flags & TDF_DETAILS))
3956 : 28 : fprintf (dump_file, "Loop%s %d not distributed.\n", str, loop->num);
3957 : 168889 : }
3958 : 192204 : }
3959 : :
3960 : 192204 : if (cd)
3961 : 57901 : delete cd;
3962 : :
3963 : 192204 : if (bb_top_order_index != NULL)
3964 : 192204 : bb_top_order_destroy ();
3965 : :
3966 : 192204 : if (changed)
3967 : : {
3968 : : /* Destroy loop bodies that could not be reused. Do this late as we
3969 : : otherwise can end up refering to stale data in control dependences. */
3970 : : unsigned i;
3971 : : class loop *loop;
3972 : 17328 : FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
3973 : 9721 : destroy_loop (loop);
3974 : :
3975 : : /* Cached scalar evolutions now may refer to wrong or non-existing
3976 : : loops. */
3977 : 7607 : scev_reset ();
3978 : 7607 : mark_virtual_operands_for_renaming (fun);
3979 : 7607 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3980 : : }
3981 : :
3982 : 192204 : checking_verify_loop_structure ();
3983 : :
3984 : 192204 : return changed ? TODO_cleanup_cfg : 0;
3985 : 192204 : }
3986 : :
3987 : :
3988 : : /* Distribute all loops in the current function. */
3989 : :
3990 : : namespace {
3991 : :
3992 : : const pass_data pass_data_loop_distribution =
3993 : : {
3994 : : GIMPLE_PASS, /* type */
3995 : : "ldist", /* name */
3996 : : OPTGROUP_LOOP, /* optinfo_flags */
3997 : : TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
3998 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
3999 : : 0, /* properties_provided */
4000 : : 0, /* properties_destroyed */
4001 : : 0, /* todo_flags_start */
4002 : : 0, /* todo_flags_finish */
4003 : : };
4004 : :
4005 : : class pass_loop_distribution : public gimple_opt_pass
4006 : : {
4007 : : public:
4008 : 283157 : pass_loop_distribution (gcc::context *ctxt)
4009 : 566314 : : gimple_opt_pass (pass_data_loop_distribution, ctxt)
4010 : : {}
4011 : :
4012 : : /* opt_pass methods: */
4013 : 230065 : bool gate (function *) final override
4014 : : {
4015 : 230065 : return flag_tree_loop_distribution
4016 : 230065 : || flag_tree_loop_distribute_patterns;
4017 : : }
4018 : :
4019 : : unsigned int execute (function *) final override;
4020 : :
4021 : : }; // class pass_loop_distribution
4022 : :
4023 : : unsigned int
4024 : 192204 : pass_loop_distribution::execute (function *fun)
4025 : : {
4026 : 192204 : return loop_distribution ().execute (fun);
4027 : : }
4028 : :
4029 : : } // anon namespace
4030 : :
4031 : : gimple_opt_pass *
4032 : 283157 : make_pass_loop_distribution (gcc::context *ctxt)
4033 : : {
4034 : 283157 : return new pass_loop_distribution (ctxt);
4035 : : }
|
