Line data Source code
1 : /* Loop distribution.
2 : Copyright (C) 2006-2026 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 9427940 : ddr_hasher::hash (const data_dependence_relation *ddr)
147 : {
148 9427940 : inchash::hash h;
149 9427940 : h.add_ptr (DDR_A (ddr));
150 9427940 : h.add_ptr (DDR_B (ddr));
151 9427940 : return h.end ();
152 : }
153 :
154 : /* Hash table equality function for data dependence. */
155 :
156 : inline bool
157 8429498 : ddr_hasher::equal (const data_dependence_relation *ddr1,
158 : const data_dependence_relation *ddr2)
159 : {
160 8429498 : 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 partition can be distributed into a loop
217 : of memset calls, rather than a single memset call. It's handled just
218 : like a normal partition, 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 partition. */
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 871 : dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
294 : {
295 871 : struct vertex *v = &(rdg->vertices[i]);
296 871 : struct graph_edge *e;
297 :
298 871 : fprintf (file, "(vertex %d: (%s%s) (in:", i,
299 871 : RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
300 871 : RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
301 :
302 871 : if (v->pred)
303 2903 : for (e = v->pred; e; e = e->pred_next)
304 2032 : fprintf (file, " %d", e->src);
305 :
306 871 : fprintf (file, ") (out:");
307 :
308 871 : if (v->succ)
309 2758 : for (e = v->succ; e; e = e->succ_next)
310 2032 : fprintf (file, " %d", e->dest);
311 :
312 871 : fprintf (file, ")\n");
313 871 : print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
314 871 : fprintf (file, ")\n");
315 871 : }
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 70 : dump_rdg (FILE *file, struct graph *rdg)
329 : {
330 70 : fprintf (file, "(rdg\n");
331 1011 : for (int i = 0; i < rdg->n_vertices; i++)
332 871 : dump_rdg_vertex (file, rdg, i);
333 70 : fprintf (file, ")\n");
334 70 : }
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 13529188 : rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple *stmt)
416 : {
417 13529188 : int index = gimple_uid (stmt);
418 13529188 : gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
419 13529188 : 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 1834116 : create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
427 : {
428 1834116 : use_operand_p imm_use_p;
429 1834116 : imm_use_iterator iterator;
430 :
431 4982189 : FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
432 : {
433 3148073 : struct graph_edge *e;
434 3148073 : int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
435 :
436 3148073 : if (use < 0)
437 458901 : continue;
438 :
439 2689172 : e = add_edge (rdg, idef, use);
440 2689172 : e->data = XNEW (struct rdg_edge);
441 2689172 : RDGE_TYPE (e) = flow_dd;
442 1834116 : }
443 1834116 : }
444 :
445 : /* Creates an edge for the control dependences of BB to the vertex V. */
446 :
447 : static void
448 2338218 : create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
449 : int v, control_dependences *cd)
450 : {
451 2338218 : bitmap_iterator bi;
452 2338218 : unsigned edge_n;
453 6646837 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
454 : 0, edge_n, bi)
455 : {
456 4308619 : basic_block cond_bb = cd->get_edge_src (edge_n);
457 4308619 : gimple *stmt = *gsi_last_bb (cond_bb);
458 4308619 : if (stmt && is_ctrl_stmt (stmt))
459 : {
460 3862517 : struct graph_edge *e;
461 3862517 : int c = rdg_vertex_for_stmt (rdg, stmt);
462 3862517 : if (c < 0)
463 1267290 : continue;
464 :
465 2595227 : e = add_edge (rdg, c, v);
466 2595227 : e->data = XNEW (struct rdg_edge);
467 2595227 : RDGE_TYPE (e) = control_dd;
468 : }
469 : }
470 2338218 : }
471 :
472 : /* Creates the edges of the reduced dependence graph RDG. */
473 :
474 : static void
475 150684 : create_rdg_flow_edges (struct graph *rdg)
476 : {
477 150684 : int i;
478 150684 : def_operand_p def_p;
479 150684 : ssa_op_iter iter;
480 :
481 2417100 : for (i = 0; i < rdg->n_vertices; i++)
482 6366948 : FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
483 : iter, SSA_OP_DEF)
484 1834116 : create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
485 150684 : }
486 :
487 : /* Creates the edges of the reduced dependence graph RDG. */
488 :
489 : static void
490 142403 : create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop)
491 : {
492 142403 : int i;
493 :
494 2354739 : for (i = 0; i < rdg->n_vertices; i++)
495 : {
496 2212336 : gimple *stmt = RDG_STMT (rdg, i);
497 2212336 : if (gimple_code (stmt) == GIMPLE_PHI)
498 : {
499 430900 : edge_iterator ei;
500 430900 : edge e;
501 1300175 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
502 869275 : if (flow_bb_inside_loop_p (loop, e->src))
503 556782 : create_edge_for_control_dependence (rdg, e->src, i, cd);
504 : }
505 : else
506 1781436 : create_edge_for_control_dependence (rdg, gimple_bb (stmt), i, cd);
507 : }
508 142403 : }
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 dependences
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 dependences 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 connected components in
639 : PARTITIONS giving reduced dependence 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 3132791 : inline int get_bb_top_order_index_size (void)
675 : {
676 3132791 : return bb_top_order_index_size;
677 : }
678 :
679 6265582 : inline int get_bb_top_order_index (int i)
680 : {
681 6265582 : 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 3132791 : bb_top_order_cmp_r (const void *x, const void *y, void *loop)
692 : {
693 3132791 : loop_distribution *_loop =
694 : (loop_distribution *) loop;
695 :
696 3132791 : basic_block bb1 = *(const basic_block *) x;
697 3132791 : basic_block bb2 = *(const basic_block *) y;
698 :
699 3132791 : int bb_top_order_index_size = _loop->get_bb_top_order_index_size ();
700 :
701 3132791 : gcc_assert (bb1->index < bb_top_order_index_size
702 : && bb2->index < bb_top_order_index_size);
703 3132791 : gcc_assert (bb1 == bb2
704 : || _loop->get_bb_top_order_index(bb1->index)
705 : != _loop->get_bb_top_order_index(bb2->index));
706 :
707 3132791 : return (_loop->get_bb_top_order_index(bb1->index) -
708 3132791 : _loop->get_bb_top_order_index(bb2->index));
709 : }
710 :
711 : bool
712 152312 : loop_distribution::create_rdg_vertices (struct graph *rdg,
713 : const vec<gimple *> &stmts,
714 : loop_p loop)
715 : {
716 152312 : int i;
717 152312 : gimple *stmt;
718 :
719 2436111 : FOR_EACH_VEC_ELT (stmts, i, stmt)
720 : {
721 2285427 : struct vertex *v = &(rdg->vertices[i]);
722 :
723 : /* Record statement to vertex mapping. */
724 2285427 : gimple_set_uid (stmt, i);
725 :
726 2285427 : v->data = XNEW (struct rdg_vertex);
727 2285427 : RDGV_STMT (v) = stmt;
728 2285427 : RDGV_DATAREFS (v).create (0);
729 2285427 : RDGV_HAS_MEM_WRITE (v) = false;
730 2285427 : RDGV_HAS_MEM_READS (v) = false;
731 2285427 : if (gimple_code (stmt) == GIMPLE_PHI)
732 454395 : continue;
733 :
734 1831032 : unsigned drp = datarefs_vec.length ();
735 1831032 : if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec))
736 : return false;
737 2741190 : for (unsigned j = drp; j < datarefs_vec.length (); ++j)
738 : {
739 457391 : data_reference_p dr = datarefs_vec[j];
740 457391 : if (DR_IS_READ (dr))
741 244884 : RDGV_HAS_MEM_READS (v) = true;
742 : else
743 212507 : RDGV_HAS_MEM_WRITE (v) = true;
744 457391 : RDGV_DATAREFS (v).safe_push (dr);
745 457391 : has_nonaddressable_dataref_p |= may_be_nonaddressable_p (dr->ref);
746 : }
747 : }
748 : return true;
749 : }
750 :
751 : void
752 152312 : loop_distribution::stmts_from_loop (class loop *loop, vec<gimple *> *stmts)
753 : {
754 152312 : unsigned int i;
755 152312 : basic_block *bbs = get_loop_body_in_custom_order (loop, this, bb_top_order_cmp_r);
756 :
757 798806 : for (i = 0; i < loop->num_nodes; i++)
758 : {
759 494182 : basic_block bb = bbs[i];
760 :
761 1097853 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
762 603671 : gsi_next (&bsi))
763 1207342 : if (!virtual_operand_p (gimple_phi_result (bsi.phi ())))
764 455636 : stmts->safe_push (bsi.phi ());
765 :
766 4032049 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
767 3043685 : gsi_next (&bsi))
768 : {
769 3043685 : gimple *stmt = gsi_stmt (bsi);
770 3043685 : if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
771 1851412 : stmts->safe_push (stmt);
772 : }
773 : }
774 :
775 152312 : free (bbs);
776 152312 : }
777 :
778 : /* Free the reduced dependence graph RDG. */
779 :
780 : static void
781 152312 : free_rdg (struct graph *rdg, loop_p loop)
782 : {
783 152312 : int i;
784 :
785 2459360 : for (i = 0; i < rdg->n_vertices; i++)
786 : {
787 2307048 : struct vertex *v = &(rdg->vertices[i]);
788 2307048 : struct graph_edge *e;
789 :
790 7591447 : for (e = v->succ; e; e = e->succ_next)
791 5284399 : free (e->data);
792 :
793 2307048 : if (v->data)
794 : {
795 2285427 : (RDGV_DATAREFS (v)).release ();
796 2285427 : free (v->data);
797 : }
798 : }
799 :
800 152312 : free_graph (rdg);
801 :
802 : /* Reset UIDs of stmts still in the loop. */
803 152312 : basic_block *bbs = get_loop_body (loop);
804 798806 : for (unsigned i = 0; i < loop->num_nodes; ++i)
805 : {
806 494182 : basic_block bb = bbs[i];
807 494182 : gimple_stmt_iterator gsi;
808 1097792 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
809 603610 : gimple_set_uid (gsi_stmt (gsi), -1);
810 4028846 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
811 3040482 : gimple_set_uid (gsi_stmt (gsi), -1);
812 : }
813 152312 : free (bbs);
814 152312 : }
815 :
816 : struct graph *
817 152312 : loop_distribution::build_rdg (class loop *loop, control_dependences *cd)
818 : {
819 152312 : struct graph *rdg;
820 :
821 : /* Create the RDG vertices from the stmts of the loop nest. */
822 152312 : auto_vec<gimple *, 10> stmts;
823 152312 : stmts_from_loop (loop, &stmts);
824 304624 : rdg = new_graph (stmts.length ());
825 152312 : if (!create_rdg_vertices (rdg, stmts, loop))
826 : {
827 1628 : free_rdg (rdg, loop);
828 1628 : return NULL;
829 : }
830 150684 : stmts.release ();
831 :
832 150684 : create_rdg_flow_edges (rdg);
833 150684 : if (cd)
834 142403 : create_rdg_cd_edges (rdg, cd, loop);
835 :
836 : return rdg;
837 152312 : }
838 :
839 :
840 : /* Allocate and initialize a partition from BITMAP. */
841 :
842 : static partition *
843 253665 : partition_alloc (void)
844 : {
845 253665 : partition *partition = XCNEW (struct partition);
846 253665 : partition->stmts = BITMAP_ALLOC (NULL);
847 253665 : partition->reduction_p = false;
848 253665 : partition->loc = UNKNOWN_LOCATION;
849 253665 : partition->kind = PKIND_NORMAL;
850 253665 : partition->type = PTYPE_PARALLEL;
851 253665 : partition->datarefs = BITMAP_ALLOC (NULL);
852 253665 : return partition;
853 : }
854 :
855 : /* Free PARTITION. */
856 :
857 : static void
858 253665 : partition_free (partition *partition)
859 : {
860 253665 : BITMAP_FREE (partition->stmts);
861 253665 : BITMAP_FREE (partition->datarefs);
862 253665 : if (partition->builtin)
863 14339 : free (partition->builtin);
864 :
865 253665 : free (partition);
866 253665 : }
867 :
868 : /* Returns true if the partition can be generated as a builtin. */
869 :
870 : static bool
871 364662 : partition_builtin_p (partition *partition)
872 : {
873 364662 : return partition->kind > PKIND_PARTIAL_MEMSET;
874 : }
875 :
876 : /* Returns true if the partition contains a reduction. */
877 :
878 : static bool
879 2083123 : partition_reduction_p (partition *partition)
880 : {
881 2083123 : return partition->reduction_p;
882 : }
883 :
884 : void
885 35064 : loop_distribution::partition_merge_into (struct graph *rdg,
886 : partition *dest, partition *partition, enum fuse_type ft)
887 : {
888 35064 : 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 35064 : dest->kind = PKIND_NORMAL;
898 35064 : if (dest->type == PTYPE_PARALLEL)
899 24733 : dest->type = partition->type;
900 :
901 35064 : bitmap_ior_into (dest->stmts, partition->stmts);
902 35064 : if (partition_reduction_p (partition))
903 3611 : dest->reduction_p = true;
904 :
905 : /* Further check if any data dependence prevents us from executing the
906 : new partition parallelly. */
907 35064 : if (dest->type == PTYPE_PARALLEL && rdg != NULL)
908 6924 : update_type_for_merge (rdg, dest, partition);
909 :
910 35064 : bitmap_ior_into (dest->datarefs, partition->datarefs);
911 35064 : }
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 4966614 : ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
919 : {
920 4966614 : imm_use_iterator imm_iter;
921 4966614 : use_operand_p use_p;
922 :
923 14750107 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
924 : {
925 9920477 : if (is_gimple_debug (USE_STMT (use_p)))
926 991730 : continue;
927 :
928 8928747 : basic_block use_bb = gimple_bb (USE_STMT (use_p));
929 8928747 : if (!flow_bb_inside_loop_p (loop, use_bb))
930 136984 : return true;
931 136984 : }
932 :
933 4829630 : return false;
934 : }
935 :
936 : /* Returns true when STMT defines a scalar variable used after the
937 : loop LOOP. */
938 :
939 : static bool
940 7281394 : stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple *stmt)
941 : {
942 7281394 : def_operand_p def_p;
943 7281394 : ssa_op_iter op_iter;
944 :
945 7281394 : if (gimple_code (stmt) == GIMPLE_PHI)
946 1229510 : return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop);
947 :
948 9713563 : FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
949 3737104 : 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 1201 : copy_loop_before (class loop *loop, bool redirect_lc_phi_defs)
959 : {
960 1201 : class loop *res;
961 1201 : edge preheader = loop_preheader_edge (loop);
962 :
963 1201 : initialize_original_copy_tables ();
964 1201 : res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, single_exit (loop), NULL,
965 : NULL, preheader, NULL, false);
966 1201 : gcc_assert (res != NULL);
967 :
968 : /* When a not last partition is supposed to keep the LC PHIs computed
969 : adjust their definitions. */
970 1201 : 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 1201 : free_original_copy_tables ();
992 1201 : delete_update_ssa ();
993 :
994 1201 : return res;
995 : }
996 :
997 : /* Creates an empty basic block after LOOP. */
998 :
999 : static void
1000 1201 : create_bb_after_loop (class loop *loop)
1001 : {
1002 1201 : edge exit = single_exit (loop);
1003 :
1004 1201 : if (!exit)
1005 : return;
1006 :
1007 1201 : 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 3148 : generate_loops_for_partition (class loop *loop, partition *partition,
1018 : bool copy_p, bool keep_lc_phis_p)
1019 : {
1020 3148 : unsigned i;
1021 3148 : basic_block *bbs;
1022 :
1023 3148 : if (copy_p)
1024 : {
1025 1201 : int orig_loop_num = loop->orig_loop_num;
1026 1201 : loop = copy_loop_before (loop, keep_lc_phis_p);
1027 1201 : gcc_assert (loop != NULL);
1028 1201 : loop->orig_loop_num = orig_loop_num;
1029 1201 : create_preheader (loop, CP_SIMPLE_PREHEADERS);
1030 1201 : create_bb_after_loop (loop);
1031 : }
1032 : else
1033 : {
1034 : /* Origin number is set to the new versioned loop's num. */
1035 1947 : gcc_assert (loop->orig_loop_num != loop->num);
1036 : }
1037 :
1038 : /* Remove stmts not in the PARTITION bitmap. */
1039 3148 : bbs = get_loop_body_in_dom_order (loop);
1040 :
1041 3148 : if (MAY_HAVE_DEBUG_BIND_STMTS)
1042 7931 : for (i = 0; i < loop->num_nodes; i++)
1043 : {
1044 6118 : basic_block bb = bbs[i];
1045 :
1046 11462 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
1047 5344 : gsi_next (&bsi))
1048 : {
1049 5344 : gphi *phi = bsi.phi ();
1050 8866 : if (!virtual_operand_p (gimple_phi_result (phi))
1051 5344 : && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
1052 401 : reset_debug_uses (phi);
1053 : }
1054 :
1055 50001 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1056 : {
1057 37765 : gimple *stmt = gsi_stmt (bsi);
1058 37765 : if (gimple_code (stmt) != GIMPLE_LABEL
1059 37765 : && !is_gimple_debug (stmt)
1060 62197 : && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
1061 6861 : reset_debug_uses (stmt);
1062 : }
1063 : }
1064 :
1065 14149 : for (i = 0; i < loop->num_nodes; i++)
1066 : {
1067 11001 : basic_block bb = bbs[i];
1068 11001 : edge inner_exit = NULL;
1069 :
1070 11001 : if (loop != bb->loop_father)
1071 126 : inner_exit = single_exit (bb->loop_father);
1072 :
1073 20674 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
1074 : {
1075 9673 : gphi *phi = bsi.phi ();
1076 16067 : if (!virtual_operand_p (gimple_phi_result (phi))
1077 9673 : && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
1078 915 : remove_phi_node (&bsi, true);
1079 : else
1080 8758 : gsi_next (&bsi);
1081 : }
1082 :
1083 79877 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
1084 : {
1085 57875 : gimple *stmt = gsi_stmt (bsi);
1086 57875 : if (gimple_code (stmt) != GIMPLE_LABEL
1087 57867 : && !is_gimple_debug (stmt)
1088 102409 : && !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 14392 : if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
1096 : {
1097 716 : if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
1098 5 : gimple_cond_make_true (cond_stmt);
1099 : else
1100 711 : gimple_cond_make_false (cond_stmt);
1101 716 : update_stmt (stmt);
1102 : }
1103 13676 : 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 13676 : unlink_stmt_vdef (stmt);
1113 13676 : gsi_remove (&bsi, true);
1114 13676 : release_defs (stmt);
1115 13676 : continue;
1116 : }
1117 : }
1118 44199 : gsi_next (&bsi);
1119 : }
1120 : }
1121 :
1122 3148 : free (bbs);
1123 3148 : }
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 82852 : const_with_all_bytes_same (tree val)
1132 : {
1133 82852 : unsigned char buf[64];
1134 82852 : int i, len;
1135 :
1136 82852 : if (integer_zerop (val)
1137 82852 : || (TREE_CODE (val) == CONSTRUCTOR
1138 269 : && !TREE_CLOBBER_P (val)
1139 269 : && CONSTRUCTOR_NELTS (val) == 0))
1140 : return 0;
1141 :
1142 50898 : 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 2468 : switch (TREE_CODE (val))
1148 : {
1149 2455 : case REAL_CST:
1150 2455 : if (!real_isneg (TREE_REAL_CST_PTR (val)))
1151 : return 0;
1152 : break;
1153 6 : case COMPLEX_CST:
1154 6 : if (!const_with_all_bytes_same (TREE_REALPART (val))
1155 12 : && !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 48458 : if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
1175 : return -1;
1176 :
1177 48458 : len = native_encode_expr (val, buf, sizeof (buf));
1178 48458 : if (len == 0)
1179 : return -1;
1180 31835 : for (i = 1; i < len; i++)
1181 26460 : if (buf[i] != buf[0])
1182 : return -1;
1183 5375 : return buf[0];
1184 : }
1185 :
1186 : /* Generate a call to memset for PARTITION in LOOP. */
1187 :
1188 : static void
1189 8816 : generate_memset_builtin (class loop *loop, partition *partition)
1190 : {
1191 8816 : gimple_stmt_iterator gsi;
1192 8816 : tree mem, fn, nb_bytes;
1193 8816 : tree val;
1194 8816 : struct builtin_info *builtin = partition->builtin;
1195 8816 : gimple *fn_call;
1196 :
1197 : /* The new statements will be placed before LOOP. */
1198 8816 : gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1199 :
1200 8816 : nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1201 8816 : nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1202 : false, GSI_CONTINUE_LINKING);
1203 8816 : mem = rewrite_to_non_trapping_overflow (builtin->dst_base);
1204 8816 : 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 8816 : 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 8816 : int bytev = const_with_all_bytes_same (val);
1212 8816 : if (bytev != -1)
1213 8715 : val = build_int_cst (integer_type_node, bytev);
1214 101 : else if (TREE_CODE (val) == INTEGER_CST)
1215 0 : val = fold_convert (integer_type_node, val);
1216 101 : else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
1217 : {
1218 101 : tree tem = make_ssa_name (integer_type_node);
1219 101 : gimple *cstmt = gimple_build_assign (tem, NOP_EXPR, val);
1220 101 : gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
1221 101 : val = tem;
1222 : }
1223 :
1224 17632 : fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
1225 8816 : fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
1226 8816 : gimple_set_location (fn_call, partition->loc);
1227 8816 : gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1228 8816 : fold_stmt (&gsi);
1229 :
1230 8816 : if (dump_file && (dump_flags & TDF_DETAILS))
1231 : {
1232 39 : fprintf (dump_file, "generated memset");
1233 39 : if (bytev == 0)
1234 33 : fprintf (dump_file, " zero\n");
1235 : else
1236 6 : fprintf (dump_file, "\n");
1237 : }
1238 8816 : }
1239 :
1240 : /* Generate a call to memcpy for PARTITION in LOOP. */
1241 :
1242 : static void
1243 4772 : generate_memcpy_builtin (class loop *loop, partition *partition)
1244 : {
1245 4772 : gimple_stmt_iterator gsi;
1246 4772 : gimple *fn_call;
1247 4772 : tree dest, src, fn, nb_bytes;
1248 4772 : enum built_in_function kind;
1249 4772 : struct builtin_info *builtin = partition->builtin;
1250 :
1251 : /* The new statements will be placed before LOOP. */
1252 4772 : gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1253 :
1254 4772 : nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1255 4772 : nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1256 : false, GSI_CONTINUE_LINKING);
1257 4772 : dest = rewrite_to_non_trapping_overflow (builtin->dst_base);
1258 4772 : src = rewrite_to_non_trapping_overflow (builtin->src_base);
1259 4772 : if (partition->kind == PKIND_MEMCPY
1260 4772 : || ! ptr_derefs_may_alias_p (dest, src))
1261 : kind = BUILT_IN_MEMCPY;
1262 : else
1263 185 : kind = BUILT_IN_MEMMOVE;
1264 : /* Try harder if we're copying a constant size. */
1265 185 : if (kind == BUILT_IN_MEMMOVE && poly_int_tree_p (nb_bytes))
1266 : {
1267 202 : aff_tree asrc, adest;
1268 101 : tree_to_aff_combination (src, ptr_type_node, &asrc);
1269 101 : tree_to_aff_combination (dest, ptr_type_node, &adest);
1270 101 : aff_combination_scale (&adest, -1);
1271 101 : aff_combination_add (&asrc, &adest);
1272 202 : if (aff_comb_cannot_overlap_p (&asrc, wi::to_poly_widest (nb_bytes),
1273 202 : wi::to_poly_widest (nb_bytes)))
1274 0 : kind = BUILT_IN_MEMCPY;
1275 101 : }
1276 :
1277 4772 : dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
1278 : false, GSI_CONTINUE_LINKING);
1279 4772 : src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
1280 : false, GSI_CONTINUE_LINKING);
1281 4772 : fn = build_fold_addr_expr (builtin_decl_implicit (kind));
1282 4772 : fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
1283 4772 : gimple_set_location (fn_call, partition->loc);
1284 4772 : gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1285 4772 : fold_stmt (&gsi);
1286 :
1287 4772 : 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 4772 : }
1295 :
1296 : /* Remove and destroy the loop LOOP. */
1297 :
1298 : static void
1299 11432 : destroy_loop (class loop *loop)
1300 : {
1301 11432 : unsigned nbbs = loop->num_nodes;
1302 11432 : edge exit = single_exit (loop);
1303 11432 : basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
1304 11432 : basic_block *bbs;
1305 11432 : unsigned i;
1306 :
1307 11432 : bbs = get_loop_body_in_dom_order (loop);
1308 :
1309 11432 : gimple_stmt_iterator dst_gsi = gsi_after_labels (exit->dest);
1310 11432 : bool safe_p = single_pred_p (exit->dest);
1311 35820 : 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 57934 : for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi);
1319 33546 : gsi_next (&gsi))
1320 : {
1321 33546 : gphi *phi = gsi.phi ();
1322 79482 : if (virtual_operand_p (gimple_phi_result (phi)))
1323 12390 : mark_virtual_phi_result_for_renaming (phi);
1324 : }
1325 142880 : for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);)
1326 : {
1327 94104 : gimple *stmt = gsi_stmt (gsi);
1328 94104 : tree vdef = gimple_vdef (stmt);
1329 54123 : if (vdef && TREE_CODE (vdef) == SSA_NAME)
1330 13336 : 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 94104 : if (gimple_debug_bind_p (stmt))
1336 : {
1337 19149 : tree val = gimple_debug_bind_get_value (stmt);
1338 19149 : gsi_move_before (&gsi, &dst_gsi);
1339 19149 : if (val
1340 19149 : && (!safe_p
1341 10307 : || !is_gimple_min_invariant (val)
1342 941 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bbs[i])))
1343 : {
1344 10523 : gimple_debug_bind_reset_value (stmt);
1345 10523 : update_stmt (stmt);
1346 : }
1347 : }
1348 : else
1349 74955 : gsi_next (&gsi);
1350 : }
1351 : }
1352 :
1353 11432 : redirect_edge_pred (exit, src);
1354 11432 : exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
1355 11432 : exit->flags |= EDGE_FALLTHRU;
1356 11432 : exit->probability = profile_probability::always ();
1357 11432 : cancel_loop_tree (loop);
1358 11432 : rescan_loop_exit (exit, false, true);
1359 :
1360 11432 : i = nbbs;
1361 24388 : do
1362 : {
1363 24388 : --i;
1364 24388 : delete_basic_block (bbs[i]);
1365 : }
1366 24388 : while (i != 0);
1367 :
1368 11432 : free (bbs);
1369 :
1370 11432 : set_immediate_dominator (CDI_DOMINATORS, dest,
1371 : recompute_dominator (CDI_DOMINATORS, dest));
1372 11432 : }
1373 :
1374 : /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1375 :
1376 : static bool
1377 16736 : generate_code_for_partition (class loop *loop,
1378 : partition *partition, bool copy_p,
1379 : bool keep_lc_phis_p)
1380 : {
1381 16736 : switch (partition->kind)
1382 : {
1383 3148 : case PKIND_NORMAL:
1384 3148 : case PKIND_PARTIAL_MEMSET:
1385 : /* Reductions all have to be in the last partition. */
1386 3148 : gcc_assert (!partition_reduction_p (partition)
1387 : || !copy_p);
1388 3148 : generate_loops_for_partition (loop, partition, copy_p,
1389 : keep_lc_phis_p);
1390 3148 : return false;
1391 :
1392 8816 : case PKIND_MEMSET:
1393 8816 : generate_memset_builtin (loop, partition);
1394 8816 : break;
1395 :
1396 4772 : case PKIND_MEMCPY:
1397 4772 : case PKIND_MEMMOVE:
1398 4772 : generate_memcpy_builtin (loop, partition);
1399 4772 : break;
1400 :
1401 0 : default:
1402 0 : gcc_unreachable ();
1403 : }
1404 :
1405 : /* Common tail for partitions we turn into a call. If this was the last
1406 : partition for which we generate code, we have to destroy the loop. */
1407 13588 : if (!copy_p)
1408 11403 : return true;
1409 : return false;
1410 : }
1411 :
1412 : data_dependence_relation *
1413 1571087 : loop_distribution::get_data_dependence (struct graph *rdg, data_reference_p a,
1414 : data_reference_p b)
1415 : {
1416 1571087 : struct data_dependence_relation ent, **slot;
1417 1571087 : struct data_dependence_relation *ddr;
1418 :
1419 1571087 : gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
1420 1571087 : gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
1421 : <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
1422 1571087 : ent.a = a;
1423 1571087 : ent.b = b;
1424 1571087 : slot = ddrs_table->find_slot (&ent, INSERT);
1425 1571087 : if (*slot == NULL)
1426 : {
1427 1188294 : ddr = initialize_data_dependence_relation (a, b, loop_nest);
1428 1188294 : compute_affine_dependence (ddr, loop_nest[0]);
1429 1188294 : *slot = ddr;
1430 : }
1431 :
1432 1571087 : return *slot;
1433 : }
1434 :
1435 : bool
1436 260929 : loop_distribution::data_dep_in_cycle_p (struct graph *rdg,
1437 : data_reference_p dr1,
1438 : data_reference_p dr2)
1439 : {
1440 260929 : struct data_dependence_relation *ddr;
1441 :
1442 : /* Re-shuffle data-refs to be in topological order. */
1443 521858 : if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1444 260929 : > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1445 49670 : std::swap (dr1, dr2);
1446 :
1447 260929 : ddr = get_data_dependence (rdg, dr1, dr2);
1448 :
1449 : /* In case of no data dependence. */
1450 260929 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1451 : return false;
1452 : /* For unknown data dependence or known data dependence which can't be
1453 : expressed in classic distance vector, we check if it can be resolved
1454 : by runtime alias check. If yes, we still consider data dependence
1455 : as won't introduce data dependence cycle. */
1456 95402 : else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1457 95402 : || DDR_NUM_DIST_VECTS (ddr) == 0)
1458 51458 : return !runtime_alias_check_p (ddr, NULL, true);
1459 43944 : else if (DDR_NUM_DIST_VECTS (ddr) > 1)
1460 : return true;
1461 39481 : else if (DDR_REVERSED_P (ddr)
1462 116175 : || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)))
1463 34371 : return false;
1464 :
1465 : return true;
1466 : }
1467 :
1468 : void
1469 243975 : loop_distribution::update_type_for_merge (struct graph *rdg,
1470 : partition *partition1,
1471 : partition *partition2)
1472 : {
1473 243975 : unsigned i, j;
1474 243975 : bitmap_iterator bi, bj;
1475 243975 : data_reference_p dr1, dr2;
1476 :
1477 735921 : EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1478 : {
1479 501520 : unsigned start = (partition1 == partition2) ? i + 1 : 0;
1480 :
1481 501520 : dr1 = datarefs_vec[i];
1482 1230642 : EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj)
1483 : {
1484 738696 : dr2 = datarefs_vec[j];
1485 738696 : if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
1486 477767 : continue;
1487 :
1488 : /* Partition can only be executed sequentially if there is any
1489 : data dependence cycle. */
1490 260929 : if (data_dep_in_cycle_p (rdg, dr1, dr2))
1491 : {
1492 9574 : partition1->type = PTYPE_SEQUENTIAL;
1493 9574 : return;
1494 : }
1495 : }
1496 : }
1497 : }
1498 :
1499 : partition *
1500 253665 : loop_distribution::build_rdg_partition_for_vertex (struct graph *rdg, int v)
1501 : {
1502 253665 : partition *partition = partition_alloc ();
1503 253665 : auto_vec<int, 3> nodes;
1504 253665 : unsigned i, j;
1505 253665 : int x;
1506 253665 : data_reference_p dr;
1507 :
1508 253665 : graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
1509 :
1510 3797599 : FOR_EACH_VEC_ELT (nodes, i, x)
1511 : {
1512 3290269 : bitmap_set_bit (partition->stmts, x);
1513 :
1514 7615841 : for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j)
1515 : {
1516 520666 : unsigned idx = (unsigned) DR_INDEX (dr);
1517 520666 : gcc_assert (idx < datarefs_vec.length ());
1518 :
1519 : /* Partition can only be executed sequentially if there is any
1520 : unknown data reference. */
1521 520666 : if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
1522 491947 : || !DR_INIT (dr) || !DR_STEP (dr))
1523 28719 : partition->type = PTYPE_SEQUENTIAL;
1524 :
1525 520666 : bitmap_set_bit (partition->datarefs, idx);
1526 : }
1527 : }
1528 :
1529 253665 : if (partition->type == PTYPE_SEQUENTIAL)
1530 : return partition;
1531 :
1532 : /* Further check if any data dependence prevents us from executing the
1533 : partition parallelly. */
1534 237051 : update_type_for_merge (rdg, partition, partition);
1535 :
1536 237051 : return partition;
1537 253665 : }
1538 :
1539 : /* Given PARTITION of LOOP and RDG, record single load/store data references
1540 : for builtin partition in SRC_DR/DST_DR, return false if there is no such
1541 : data references. */
1542 :
1543 : static bool
1544 234815 : find_single_drs (class loop *loop, struct graph *rdg, const bitmap &partition_stmts,
1545 : data_reference_p *dst_dr, data_reference_p *src_dr)
1546 : {
1547 234815 : unsigned i;
1548 234815 : data_reference_p single_ld = NULL, single_st = NULL;
1549 234815 : bitmap_iterator bi;
1550 :
1551 2404197 : EXECUTE_IF_SET_IN_BITMAP (partition_stmts, 0, i, bi)
1552 : {
1553 2233243 : gimple *stmt = RDG_STMT (rdg, i);
1554 2233243 : data_reference_p dr;
1555 :
1556 2233243 : if (gimple_code (stmt) == GIMPLE_PHI)
1557 510276 : continue;
1558 :
1559 : /* Any scalar stmts are ok. */
1560 3208450 : if (!gimple_vuse (stmt))
1561 1360524 : continue;
1562 :
1563 : /* Otherwise just regular loads/stores. */
1564 362443 : if (!gimple_assign_single_p (stmt))
1565 234815 : return false;
1566 :
1567 : /* But exactly one store and/or load. */
1568 2835819 : for (unsigned j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j)
1569 : {
1570 367876 : tree type = TREE_TYPE (DR_REF (dr));
1571 :
1572 : /* The memset, memcpy and memmove library calls are only
1573 : able to deal with generic address space. */
1574 367876 : if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type)))
1575 : return false;
1576 :
1577 367858 : if (DR_IS_READ (dr))
1578 : {
1579 215381 : if (single_ld != NULL)
1580 : return false;
1581 : single_ld = dr;
1582 : }
1583 : else
1584 : {
1585 152477 : if (single_st != NULL)
1586 : return false;
1587 : single_st = dr;
1588 : }
1589 : }
1590 : }
1591 :
1592 170954 : if (!single_ld && !single_st)
1593 : return false;
1594 :
1595 165053 : basic_block bb_ld = NULL;
1596 165053 : basic_block bb_st = NULL;
1597 165053 : edge exit = single_exit (loop);
1598 :
1599 165053 : if (single_ld)
1600 : {
1601 : /* Bail out if this is a bitfield memory reference. */
1602 87759 : if (TREE_CODE (DR_REF (single_ld)) == COMPONENT_REF
1603 87759 : && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld), 1)))
1604 : return false;
1605 :
1606 : /* Data reference must be executed exactly once per iteration of each
1607 : loop in the loop nest. We only need to check dominance information
1608 : against the outermost one in a perfect loop nest because a bb can't
1609 : dominate outermost loop's latch without dominating inner loop's. */
1610 87759 : bb_ld = gimple_bb (DR_STMT (single_ld));
1611 87759 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld))
1612 : return false;
1613 :
1614 : /* The data reference must also be executed before possibly exiting
1615 : the loop as otherwise we'd for example unconditionally execute
1616 : memset (ptr, 0, n) which even with n == 0 implies ptr is non-NULL. */
1617 81172 : if (bb_ld != loop->header
1618 81172 : && (!exit
1619 10314 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bb_ld)))
1620 : return false;
1621 : }
1622 :
1623 156088 : if (single_st)
1624 : {
1625 : /* Bail out if this is a bitfield memory reference. */
1626 142073 : if (TREE_CODE (DR_REF (single_st)) == COMPONENT_REF
1627 142073 : && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1)))
1628 : return false;
1629 :
1630 : /* Data reference must be executed exactly once per iteration.
1631 : Same as single_ld, we only need to check against the outermost
1632 : loop. */
1633 142073 : bb_st = gimple_bb (DR_STMT (single_st));
1634 142073 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st))
1635 : return false;
1636 :
1637 : /* And before exiting the loop. */
1638 138032 : if (bb_st != loop->header
1639 138032 : && (!exit
1640 18687 : || !dominated_by_p (CDI_DOMINATORS, exit->src, bb_st)))
1641 : return false;
1642 : }
1643 :
1644 150750 : if (single_ld && single_st)
1645 : {
1646 : /* Load and store must be in the same loop nest. */
1647 62935 : if (bb_st->loop_father != bb_ld->loop_father)
1648 : return false;
1649 :
1650 62332 : edge e = single_exit (bb_st->loop_father);
1651 62332 : bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld);
1652 62332 : bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st);
1653 62332 : if (dom_ld != dom_st)
1654 : return false;
1655 : }
1656 :
1657 150147 : *src_dr = single_ld;
1658 150147 : *dst_dr = single_st;
1659 150147 : return true;
1660 : }
1661 :
1662 : /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1663 : loops from inner to outer to see if loop's step equals to access size at
1664 : each level of loop. Return 2 if we can prove this at all level loops;
1665 : record access base and size in BASE and SIZE; save loop's step at each
1666 : level of loop in STEPS if it is not null. For example:
1667 :
1668 : int arr[100][100][100];
1669 : for (i = 0; i < 100; i++) ;steps[2] = 40000
1670 : for (j = 100; j > 0; j--) ;steps[1] = -400
1671 : for (k = 0; k < 100; k++) ;steps[0] = 4
1672 : arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1673 :
1674 : Return 1 if we can prove the equality at the innermost loop, but not all
1675 : level loops. In this case, no information is recorded.
1676 :
1677 : Return 0 if no equality can be proven at any level loops. */
1678 :
1679 : static int
1680 88083 : compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
1681 : tree *size, vec<tree> *steps = NULL)
1682 : {
1683 88083 : location_t loc = gimple_location (DR_STMT (dr));
1684 88083 : basic_block bb = gimple_bb (DR_STMT (dr));
1685 88083 : class loop *loop = bb->loop_father;
1686 88083 : tree ref = DR_REF (dr);
1687 88083 : tree access_base = build_fold_addr_expr (ref);
1688 88083 : tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1689 88083 : int res = 0;
1690 :
1691 89562 : do {
1692 89562 : tree scev_fn = analyze_scalar_evolution (loop, access_base);
1693 89562 : if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
1694 45674 : return res;
1695 :
1696 87672 : access_base = CHREC_LEFT (scev_fn);
1697 87672 : if (tree_contains_chrecs (access_base, NULL))
1698 : return res;
1699 :
1700 87672 : tree scev_step = CHREC_RIGHT (scev_fn);
1701 : /* Only support constant steps. */
1702 87672 : if (TREE_CODE (scev_step) != INTEGER_CST)
1703 : return res;
1704 :
1705 82886 : enum ev_direction access_dir = scev_direction (scev_fn);
1706 82886 : if (access_dir == EV_DIR_UNKNOWN)
1707 : return res;
1708 :
1709 82886 : if (steps != NULL)
1710 53441 : steps->safe_push (scev_step);
1711 :
1712 82886 : scev_step = fold_convert_loc (loc, sizetype, scev_step);
1713 : /* Compute absolute value of scev step. */
1714 82886 : if (access_dir == EV_DIR_DECREASES)
1715 3087 : scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
1716 :
1717 : /* At each level of loop, scev step must equal to access size. In other
1718 : words, DR must access consecutive memory between loop iterations. */
1719 82886 : if (!operand_equal_p (scev_step, access_size, 0))
1720 : return res;
1721 :
1722 : /* Access stride can be computed for data reference at least for the
1723 : innermost loop. */
1724 43888 : res = 1;
1725 :
1726 : /* Compute DR's execution times in loop. */
1727 43888 : tree niters = number_of_latch_executions (loop);
1728 43888 : niters = fold_convert_loc (loc, sizetype, niters);
1729 43888 : if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
1730 43888 : niters = size_binop_loc (loc, PLUS_EXPR, niters, size_one_node);
1731 :
1732 : /* Compute DR's overall access size in loop. */
1733 43888 : access_size = fold_build2_loc (loc, MULT_EXPR, sizetype,
1734 : niters, scev_step);
1735 : /* Adjust base address in case of negative step. */
1736 43888 : if (access_dir == EV_DIR_DECREASES)
1737 : {
1738 2117 : tree adj = fold_build2_loc (loc, MINUS_EXPR, sizetype,
1739 : scev_step, access_size);
1740 2117 : access_base = fold_build_pointer_plus_loc (loc, access_base, adj);
1741 : }
1742 43888 : } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
1743 :
1744 42409 : *base = access_base;
1745 42409 : *size = access_size;
1746 : /* Access stride can be computed for data reference at each level loop. */
1747 42409 : return 2;
1748 : }
1749 :
1750 : /* Allocate and return builtin struct. Record information like DST_DR,
1751 : SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1752 :
1753 : static struct builtin_info *
1754 14339 : alloc_builtin (data_reference_p dst_dr, data_reference_p src_dr,
1755 : tree dst_base, tree src_base, tree size)
1756 : {
1757 0 : struct builtin_info *builtin = XNEW (struct builtin_info);
1758 14339 : builtin->dst_dr = dst_dr;
1759 14339 : builtin->src_dr = src_dr;
1760 14339 : builtin->dst_base = dst_base;
1761 14339 : builtin->src_base = src_base;
1762 14339 : builtin->size = size;
1763 14339 : return builtin;
1764 : }
1765 :
1766 : /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1767 : memset call. */
1768 :
1769 : static void
1770 73790 : classify_builtin_st (loop_p loop, partition *partition, data_reference_p dr)
1771 : {
1772 73790 : gimple *stmt = DR_STMT (dr);
1773 73790 : tree base, size, rhs = gimple_assign_rhs1 (stmt);
1774 :
1775 73790 : if (const_with_all_bytes_same (rhs) == -1
1776 73790 : && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
1777 56076 : || (TYPE_MODE (TREE_TYPE (rhs))
1778 28038 : != TYPE_MODE (unsigned_char_type_node))))
1779 64731 : return;
1780 :
1781 35590 : if (TREE_CODE (rhs) == SSA_NAME
1782 4775 : && !SSA_NAME_IS_DEFAULT_DEF (rhs)
1783 39693 : && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
1784 : return;
1785 :
1786 31632 : int res = compute_access_range (loop, dr, &base, &size);
1787 31632 : if (res == 0)
1788 : return;
1789 9120 : if (res == 1)
1790 : {
1791 61 : partition->kind = PKIND_PARTIAL_MEMSET;
1792 61 : return;
1793 : }
1794 :
1795 9059 : tree base_offset;
1796 9059 : tree base_base;
1797 9059 : split_constant_offset (base, &base_base, &base_offset);
1798 9059 : if (!cst_and_fits_in_hwi (base_offset))
1799 : return;
1800 9059 : unsigned HOST_WIDE_INT const_base_offset = int_cst_value (base_offset);
1801 :
1802 9059 : struct builtin_info *builtin;
1803 9059 : builtin = alloc_builtin (dr, NULL, base, NULL_TREE, size);
1804 9059 : builtin->dst_base_base = base_base;
1805 9059 : builtin->dst_base_offset = const_base_offset;
1806 9059 : partition->builtin = builtin;
1807 9059 : partition->kind = PKIND_MEMSET;
1808 : }
1809 :
1810 : /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1811 : if it forms builtin memcpy or memmove call. */
1812 :
1813 : void
1814 36557 : loop_distribution::classify_builtin_ldst (loop_p loop, struct graph *rdg,
1815 : partition *partition,
1816 : data_reference_p dst_dr,
1817 : data_reference_p src_dr)
1818 : {
1819 36557 : tree base, size, src_base, src_size;
1820 36557 : auto_vec<tree> dst_steps, src_steps;
1821 :
1822 : /* Compute access range of both load and store. */
1823 36557 : int res = compute_access_range (loop, dst_dr, &base, &size, &dst_steps);
1824 36557 : if (res != 2)
1825 : return;
1826 19894 : res = compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps);
1827 19894 : if (res != 2)
1828 : return;
1829 :
1830 : /* They must have the same access size. */
1831 13456 : if (!operand_equal_p (size, src_size, 0))
1832 : return;
1833 :
1834 : /* They must have the same storage order. */
1835 26912 : if (reverse_storage_order_for_component_p (DR_REF (dst_dr))
1836 13456 : != reverse_storage_order_for_component_p (DR_REF (src_dr)))
1837 : return;
1838 :
1839 : /* Load and store in loop nest must access memory in the same way, i.e,
1840 : their must have the same steps in each loop of the nest. */
1841 40368 : if (dst_steps.length () != src_steps.length ())
1842 : return;
1843 27008 : for (unsigned i = 0; i < dst_steps.length (); ++i)
1844 13855 : if (!operand_equal_p (dst_steps[i], src_steps[i], 0))
1845 : return;
1846 :
1847 : /* Now check that if there is a dependence. */
1848 13153 : ddr_p ddr = get_data_dependence (rdg, src_dr, dst_dr);
1849 :
1850 : /* Classify as memcpy if no dependence between load and store. */
1851 13153 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1852 : {
1853 4976 : partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1854 4976 : partition->kind = PKIND_MEMCPY;
1855 4976 : return;
1856 : }
1857 :
1858 : /* Can't do memmove in case of unknown dependence or dependence without
1859 : classical distance vector. */
1860 8177 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1861 37214 : || DDR_NUM_DIST_VECTS (ddr) == 0)
1862 : return;
1863 :
1864 657 : unsigned i;
1865 657 : lambda_vector dist_v;
1866 657 : int num_lev = (DDR_LOOP_NEST (ddr)).length ();
1867 1250 : FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
1868 : {
1869 593 : unsigned dep_lev = dependence_level (dist_v, num_lev);
1870 : /* Can't do memmove if load depends on store. */
1871 637 : if (dep_lev > 0 && dist_v[dep_lev - 1] > 0 && !DDR_REVERSED_P (ddr))
1872 : return;
1873 : }
1874 :
1875 304 : partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1876 304 : partition->kind = PKIND_MEMMOVE;
1877 304 : return;
1878 36557 : }
1879 :
1880 : bool
1881 253665 : loop_distribution::classify_partition (loop_p loop,
1882 : struct graph *rdg, partition *partition,
1883 : bitmap stmt_in_all_partitions)
1884 : {
1885 253665 : bitmap_iterator bi;
1886 253665 : unsigned i;
1887 253665 : data_reference_p single_ld = NULL, single_st = NULL;
1888 253665 : bool volatiles_p = false, has_reduction = false;
1889 :
1890 3543934 : EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1891 : {
1892 3290269 : gimple *stmt = RDG_STMT (rdg, i);
1893 :
1894 5560001 : if (gimple_has_volatile_ops (stmt))
1895 3290269 : volatiles_p = true;
1896 :
1897 : /* If the stmt is not included by all partitions and there is uses
1898 : outside of the loop, then mark the partition as reduction. */
1899 3290269 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
1900 : {
1901 : /* Due to limitation in the transform phase we have to fuse all
1902 : reduction partitions. As a result, this could cancel valid
1903 : loop distribution especially for loop that induction variable
1904 : is used outside of loop. To workaround this issue, we skip
1905 : marking partition as reduction if the reduction stmt belongs
1906 : to all partitions. In such case, reduction will be computed
1907 : correctly no matter how partitions are fused/distributed. */
1908 64673 : if (!bitmap_bit_p (stmt_in_all_partitions, i))
1909 26170 : partition->reduction_p = true;
1910 : else
1911 : has_reduction = true;
1912 : }
1913 : }
1914 :
1915 : /* Simple workaround to prevent classifying the partition as builtin
1916 : if it contains any use outside of loop. For the case where all
1917 : partitions have the reduction this simple workaround is delayed
1918 : to only affect the last partition. */
1919 253665 : if (partition->reduction_p)
1920 : return has_reduction;
1921 :
1922 : /* Perform general partition disqualification for builtins. */
1923 229110 : if (volatiles_p
1924 229110 : || has_nonaddressable_dataref_p
1925 228731 : || !flag_tree_loop_distribute_patterns)
1926 : return has_reduction;
1927 :
1928 : /* Find single load/store data references for builtin partition. */
1929 226534 : if (!find_single_drs (loop, rdg, partition->stmts, &single_st, &single_ld)
1930 226534 : || !single_st)
1931 : return has_reduction;
1932 :
1933 136013 : if (single_ld && single_st)
1934 : {
1935 62223 : gimple *store = DR_STMT (single_st), *load = DR_STMT (single_ld);
1936 : /* Direct aggregate copy or via an SSA name temporary. */
1937 62223 : if (load != store
1938 62223 : && gimple_assign_lhs (load) != gimple_assign_rhs1 (store))
1939 : return has_reduction;
1940 : }
1941 :
1942 110347 : partition->loc = gimple_location (DR_STMT (single_st));
1943 :
1944 : /* Classify the builtin kind. */
1945 110347 : if (single_ld == NULL)
1946 73790 : classify_builtin_st (loop, partition, single_st);
1947 : else
1948 36557 : classify_builtin_ldst (loop, rdg, partition, single_st, single_ld);
1949 : return has_reduction;
1950 : }
1951 :
1952 : bool
1953 872734 : loop_distribution::share_memory_accesses (struct graph *rdg,
1954 : partition *partition1, partition *partition2)
1955 : {
1956 872734 : unsigned i, j;
1957 872734 : bitmap_iterator bi, bj;
1958 872734 : data_reference_p dr1, dr2;
1959 :
1960 : /* First check whether in the intersection of the two partitions are
1961 : any loads or stores. Common loads are the situation that happens
1962 : most often. */
1963 6424253 : EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
1964 5556211 : if (RDG_MEM_WRITE_STMT (rdg, i)
1965 5556211 : || RDG_MEM_READS_STMT (rdg, i))
1966 : return true;
1967 :
1968 : /* Then check whether the two partitions access the same memory object. */
1969 1934550 : EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1970 : {
1971 1069032 : dr1 = datarefs_vec[i];
1972 :
1973 1069032 : if (!DR_BASE_ADDRESS (dr1)
1974 1066951 : || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1))
1975 2081 : continue;
1976 :
1977 2288188 : EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj)
1978 : {
1979 1223761 : dr2 = datarefs_vec[j];
1980 :
1981 1223761 : if (!DR_BASE_ADDRESS (dr2)
1982 1223215 : || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2))
1983 546 : continue;
1984 :
1985 1223215 : if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0)
1986 1069699 : && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0)
1987 1068257 : && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0)
1988 1225770 : && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0))
1989 : return true;
1990 : }
1991 : }
1992 :
1993 : return false;
1994 : }
1995 :
1996 : /* For each seed statement in STARTING_STMTS, this function builds
1997 : partition for it by adding depended statements according to RDG.
1998 : All partitions are recorded in PARTITIONS. */
1999 :
2000 : void
2001 142403 : loop_distribution::rdg_build_partitions (struct graph *rdg,
2002 : vec<gimple *> starting_stmts,
2003 : vec<partition *> *partitions)
2004 : {
2005 142403 : auto_bitmap processed;
2006 142403 : int i;
2007 142403 : gimple *stmt;
2008 :
2009 545362 : FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
2010 : {
2011 260556 : int v = rdg_vertex_for_stmt (rdg, stmt);
2012 :
2013 260556 : if (dump_file && (dump_flags & TDF_DETAILS))
2014 141 : fprintf (dump_file,
2015 : "ldist asked to generate code for vertex %d\n", v);
2016 :
2017 : /* If the vertex is already contained in another partition so
2018 : is the partition rooted at it. */
2019 260556 : if (bitmap_bit_p (processed, v))
2020 6891 : continue;
2021 :
2022 253665 : partition *partition = build_rdg_partition_for_vertex (rdg, v);
2023 253665 : bitmap_ior_into (processed, partition->stmts);
2024 :
2025 253665 : if (dump_file && (dump_flags & TDF_DETAILS))
2026 : {
2027 141 : fprintf (dump_file, "ldist creates useful %s partition:\n",
2028 141 : partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
2029 141 : bitmap_print (dump_file, partition->stmts, " ", "\n");
2030 : }
2031 :
2032 253665 : partitions->safe_push (partition);
2033 : }
2034 :
2035 : /* All vertices should have been assigned to at least one partition now,
2036 : other than vertices belonging to dead code. */
2037 142403 : }
2038 :
2039 : /* Dump to FILE the PARTITIONS. */
2040 :
2041 : static void
2042 42 : dump_rdg_partitions (FILE *file, const vec<partition *> &partitions)
2043 : {
2044 42 : int i;
2045 42 : partition *partition;
2046 :
2047 108 : FOR_EACH_VEC_ELT (partitions, i, partition)
2048 66 : debug_bitmap_file (file, partition->stmts);
2049 42 : }
2050 :
2051 : /* Debug PARTITIONS. */
2052 : extern void debug_rdg_partitions (const vec<partition *> &);
2053 :
2054 : DEBUG_FUNCTION void
2055 0 : debug_rdg_partitions (const vec<partition *> &partitions)
2056 : {
2057 0 : dump_rdg_partitions (stderr, partitions);
2058 0 : }
2059 :
2060 : /* Returns the number of read and write operations in the RDG. */
2061 :
2062 : static int
2063 2925 : number_of_rw_in_rdg (struct graph *rdg)
2064 : {
2065 2925 : int i, res = 0;
2066 :
2067 43117 : for (i = 0; i < rdg->n_vertices; i++)
2068 : {
2069 40192 : if (RDG_MEM_WRITE_STMT (rdg, i))
2070 8151 : ++res;
2071 :
2072 40192 : if (RDG_MEM_READS_STMT (rdg, i))
2073 5716 : ++res;
2074 : }
2075 :
2076 2925 : return res;
2077 : }
2078 :
2079 : /* Returns the number of read and write operations in a PARTITION of
2080 : the RDG. */
2081 :
2082 : static int
2083 6343 : number_of_rw_in_partition (struct graph *rdg, partition *partition)
2084 : {
2085 6343 : int res = 0;
2086 6343 : unsigned i;
2087 6343 : bitmap_iterator ii;
2088 :
2089 60312 : EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
2090 : {
2091 53969 : if (RDG_MEM_WRITE_STMT (rdg, i))
2092 8143 : ++res;
2093 :
2094 53969 : if (RDG_MEM_READS_STMT (rdg, i))
2095 5716 : ++res;
2096 : }
2097 :
2098 6343 : return res;
2099 : }
2100 :
2101 : /* Returns true when one of the PARTITIONS contains all the read or
2102 : write operations of RDG. */
2103 :
2104 : static bool
2105 2925 : partition_contains_all_rw (struct graph *rdg,
2106 : const vec<partition *> &partitions)
2107 : {
2108 2925 : int i;
2109 2925 : partition *partition;
2110 2925 : int nrw = number_of_rw_in_rdg (rdg);
2111 :
2112 9151 : FOR_EACH_VEC_ELT (partitions, i, partition)
2113 6343 : if (nrw == number_of_rw_in_partition (rdg, partition))
2114 : return true;
2115 :
2116 : return false;
2117 : }
2118 :
2119 : int
2120 983360 : loop_distribution::pg_add_dependence_edges (struct graph *rdg, int dir,
2121 : bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs)
2122 : {
2123 983360 : unsigned i, j;
2124 983360 : bitmap_iterator bi, bj;
2125 983360 : data_reference_p dr1, dr2, saved_dr1;
2126 :
2127 : /* dependence direction - 0 is no dependence, -1 is back,
2128 : 1 is forth, 2 is both (we can stop then, merging will occur). */
2129 1891638 : EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi)
2130 : {
2131 1109965 : dr1 = datarefs_vec[i];
2132 :
2133 2316037 : EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj)
2134 : {
2135 1407759 : int res, this_dir = 1;
2136 1407759 : ddr_p ddr;
2137 :
2138 1407759 : dr2 = datarefs_vec[j];
2139 :
2140 : /* Skip all <read, read> data dependence. */
2141 1407759 : if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
2142 110754 : continue;
2143 :
2144 1297005 : saved_dr1 = dr1;
2145 : /* Re-shuffle data-refs to be in topological order. */
2146 2594010 : if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
2147 1297005 : > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
2148 : {
2149 93142 : std::swap (dr1, dr2);
2150 93142 : this_dir = -this_dir;
2151 : }
2152 1297005 : ddr = get_data_dependence (rdg, dr1, dr2);
2153 1297005 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2154 : {
2155 213486 : this_dir = 0;
2156 213486 : res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1),
2157 : DR_BASE_ADDRESS (dr2));
2158 : /* Be conservative. If data references are not well analyzed,
2159 : or the two data references have the same base address and
2160 : offset, add dependence and consider it alias to each other.
2161 : In other words, the dependence cannot be resolved by
2162 : runtime alias check. */
2163 213486 : if (!DR_BASE_ADDRESS (dr1) || !DR_BASE_ADDRESS (dr2)
2164 212958 : || !DR_OFFSET (dr1) || !DR_OFFSET (dr2)
2165 212958 : || !DR_INIT (dr1) || !DR_INIT (dr2)
2166 212958 : || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
2167 204926 : || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
2168 204780 : || res == 0)
2169 : this_dir = 2;
2170 : /* Data dependence could be resolved by runtime alias check,
2171 : record it in ALIAS_DDRS. */
2172 13104 : else if (alias_ddrs != NULL)
2173 6529 : alias_ddrs->safe_push (ddr);
2174 : /* Or simply ignore it. */
2175 : }
2176 1083519 : else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2177 : {
2178 : /* Known dependences can still be unordered throughout the
2179 : iteration space, see gcc.dg/tree-ssa/ldist-16.c and
2180 : gcc.dg/tree-ssa/pr94969.c. */
2181 2183 : if (DDR_NUM_DIST_VECTS (ddr) != 1)
2182 : this_dir = 2;
2183 : else
2184 : {
2185 : /* If the overlap is exact preserve stmt order. */
2186 1838 : if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0),
2187 1838 : DDR_NB_LOOPS (ddr)))
2188 : ;
2189 : /* Else as the distance vector is lexicographic positive swap
2190 : the dependence direction. */
2191 : else
2192 : {
2193 842 : if (DDR_REVERSED_P (ddr))
2194 42 : this_dir = -this_dir;
2195 842 : this_dir = -this_dir;
2196 : }
2197 : /* When then dependence distance of the innermost common
2198 : loop of the DRs is zero we have a conflict. This is
2199 : due to wonky dependence analysis which sometimes
2200 : ends up using a zero distance in place of unknown. */
2201 919 : auto l1 = gimple_bb (DR_STMT (dr1))->loop_father;
2202 919 : auto l2 = gimple_bb (DR_STMT (dr2))->loop_father;
2203 919 : int idx = index_in_loop_nest (find_common_loop (l1, l2)->num,
2204 919 : DDR_LOOP_NEST (ddr));
2205 919 : if (DDR_DIST_VECT (ddr, 0)[idx] == 0
2206 : /* Unless it is the outermost loop which is the one
2207 : we eventually distribute. */
2208 919 : && idx != 0)
2209 : this_dir = 2;
2210 : }
2211 : }
2212 : else
2213 : this_dir = 0;
2214 7465 : if (this_dir == 2)
2215 201687 : return 2;
2216 1095331 : else if (dir == 0)
2217 : dir = this_dir;
2218 7340 : else if (this_dir != 0 && dir != this_dir)
2219 : return 2;
2220 : /* Shuffle "back" dr1. */
2221 1095318 : dr1 = saved_dr1;
2222 : }
2223 : }
2224 : return dir;
2225 : }
2226 :
2227 : /* Compare postorder number of the partition graph vertices V1 and V2. */
2228 :
2229 : static int
2230 807491 : pgcmp (const void *v1_, const void *v2_)
2231 : {
2232 807491 : const vertex *v1 = (const vertex *)v1_;
2233 807491 : const vertex *v2 = (const vertex *)v2_;
2234 807491 : return v2->post - v1->post;
2235 : }
2236 :
2237 : /* Data attached to vertices of partition dependence graph. */
2238 : struct pg_vdata
2239 : {
2240 : /* ID of the corresponding partition. */
2241 : int id;
2242 : /* The partition. */
2243 : struct partition *partition;
2244 : };
2245 :
2246 : /* Data attached to edges of partition dependence graph. */
2247 : struct pg_edata
2248 : {
2249 : /* If the dependence edge can be resolved by runtime alias check,
2250 : this vector contains data dependence relations for runtime alias
2251 : check. On the other hand, if the dependence edge is introduced
2252 : because of compilation time known data dependence, this vector
2253 : contains nothing. */
2254 : vec<ddr_p> alias_ddrs;
2255 : };
2256 :
2257 : /* Callback data for traversing edges in graph. */
2258 : struct pg_edge_callback_data
2259 : {
2260 : /* Bitmap contains strong connected components should be merged. */
2261 : bitmap sccs_to_merge;
2262 : /* Array constains component information for all vertices. */
2263 : int *vertices_component;
2264 : /* Vector to record all data dependence relations which are needed
2265 : to break strong connected components by runtime alias checks. */
2266 : vec<ddr_p> *alias_ddrs;
2267 : };
2268 :
2269 : /* Initialize vertice's data for partition dependence graph PG with
2270 : PARTITIONS. */
2271 :
2272 : static void
2273 13030 : init_partition_graph_vertices (struct graph *pg,
2274 : vec<struct partition *> *partitions)
2275 : {
2276 13030 : int i;
2277 13030 : partition *partition;
2278 13030 : struct pg_vdata *data;
2279 :
2280 71997 : for (i = 0; partitions->iterate (i, &partition); ++i)
2281 : {
2282 58967 : data = new pg_vdata;
2283 58967 : pg->vertices[i].data = data;
2284 58967 : data->id = i;
2285 58967 : data->partition = partition;
2286 : }
2287 13030 : }
2288 :
2289 : /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2290 : dependence relations to the EDGE if DDRS isn't NULL. */
2291 :
2292 : static void
2293 415471 : add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs)
2294 : {
2295 415471 : struct graph_edge *e = add_edge (pg, i, j);
2296 :
2297 : /* If the edge is attached with data dependence relations, it means this
2298 : dependence edge can be resolved by runtime alias checks. */
2299 415471 : if (ddrs != NULL)
2300 : {
2301 10097 : struct pg_edata *data = new pg_edata;
2302 :
2303 10097 : gcc_assert (ddrs->length () > 0);
2304 10097 : e->data = data;
2305 10097 : data->alias_ddrs = vNULL;
2306 10097 : data->alias_ddrs.safe_splice (*ddrs);
2307 : }
2308 415471 : }
2309 :
2310 : /* Callback function for graph traversal algorithm. It returns true
2311 : if edge E should skipped when traversing the graph. */
2312 :
2313 : static bool
2314 1959 : pg_skip_alias_edge (struct graph_edge *e)
2315 : {
2316 1959 : struct pg_edata *data = (struct pg_edata *)e->data;
2317 1959 : return (data != NULL && data->alias_ddrs.length () > 0);
2318 : }
2319 :
2320 : /* Callback function freeing data attached to edge E of graph. */
2321 :
2322 : static void
2323 415471 : free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *)
2324 : {
2325 415471 : if (e->data != NULL)
2326 : {
2327 10096 : struct pg_edata *data = (struct pg_edata *)e->data;
2328 10096 : data->alias_ddrs.release ();
2329 10096 : delete data;
2330 : }
2331 415471 : }
2332 :
2333 : /* Free data attached to vertice of partition dependence graph PG. */
2334 :
2335 : static void
2336 13030 : free_partition_graph_vdata (struct graph *pg)
2337 : {
2338 13030 : int i;
2339 13030 : struct pg_vdata *data;
2340 :
2341 71997 : for (i = 0; i < pg->n_vertices; ++i)
2342 : {
2343 58967 : data = (struct pg_vdata *)pg->vertices[i].data;
2344 58967 : delete data;
2345 : }
2346 13030 : }
2347 :
2348 : /* Build and return partition dependence graph for PARTITIONS. RDG is
2349 : reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2350 : is true, data dependence caused by possible alias between references
2351 : is ignored, as if it doesn't exist at all; otherwise all dependences
2352 : are considered. */
2353 :
2354 : struct graph *
2355 13030 : loop_distribution::build_partition_graph (struct graph *rdg,
2356 : vec<struct partition *> *partitions,
2357 : bool ignore_alias_p)
2358 : {
2359 13030 : int i, j;
2360 13030 : struct partition *partition1, *partition2;
2361 26060 : graph *pg = new_graph (partitions->length ());
2362 13030 : auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p;
2363 :
2364 13030 : alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs;
2365 :
2366 13030 : init_partition_graph_vertices (pg, partitions);
2367 :
2368 85027 : for (i = 0; partitions->iterate (i, &partition1); ++i)
2369 : {
2370 1101294 : for (j = i + 1; partitions->iterate (j, &partition2); ++j)
2371 : {
2372 : /* dependence direction - 0 is no dependence, -1 is back,
2373 : 1 is forth, 2 is both (we can stop then, merging will occur). */
2374 983360 : int dir = 0;
2375 :
2376 : /* If the first partition has reduction, add back edge; if the
2377 : second partition has reduction, add forth edge. This makes
2378 : sure that reduction partition will be sorted as the last one. */
2379 983360 : if (partition_reduction_p (partition1))
2380 : dir = -1;
2381 983163 : else if (partition_reduction_p (partition2))
2382 1487 : dir = 1;
2383 :
2384 : /* Cleanup the temporary vector. */
2385 983360 : alias_ddrs.truncate (0);
2386 :
2387 983360 : dir = pg_add_dependence_edges (rdg, dir, partition1->datarefs,
2388 : partition2->datarefs, alias_ddrs_p);
2389 :
2390 : /* Add edge to partition graph if there exists dependence. There
2391 : are two types of edges. One type edge is caused by compilation
2392 : time known dependence, this type cannot be resolved by runtime
2393 : alias check. The other type can be resolved by runtime alias
2394 : check. */
2395 983360 : if (dir == 1 || dir == 2
2396 990101 : || alias_ddrs.length () > 0)
2397 : {
2398 : /* Attach data dependence relations to edge that can be resolved
2399 : by runtime alias check. */
2400 208458 : bool alias_edge_p = (dir != 1 && dir != 2);
2401 411896 : add_partition_graph_edge (pg, i, j,
2402 : (alias_edge_p) ? &alias_ddrs : NULL);
2403 : }
2404 983360 : if (dir == -1 || dir == 2
2405 1971797 : || alias_ddrs.length () > 0)
2406 : {
2407 : /* Attach data dependence relations to edge that can be resolved
2408 : by runtime alias check. */
2409 207013 : bool alias_edge_p = (dir != -1 && dir != 2);
2410 408949 : add_partition_graph_edge (pg, j, i,
2411 : (alias_edge_p) ? &alias_ddrs : NULL);
2412 : }
2413 : }
2414 : }
2415 13030 : return pg;
2416 13030 : }
2417 :
2418 : /* Sort partitions in PG in descending post order and store them in
2419 : PARTITIONS. */
2420 :
2421 : static void
2422 13030 : sort_partitions_by_post_order (struct graph *pg,
2423 : vec<struct partition *> *partitions)
2424 : {
2425 13030 : int i;
2426 13030 : struct pg_vdata *data;
2427 :
2428 : /* Now order the remaining nodes in descending postorder. */
2429 13030 : qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
2430 13030 : partitions->truncate (0);
2431 85027 : for (i = 0; i < pg->n_vertices; ++i)
2432 : {
2433 58967 : data = (struct pg_vdata *)pg->vertices[i].data;
2434 58967 : if (data->partition)
2435 51167 : partitions->safe_push (data->partition);
2436 : }
2437 13030 : }
2438 :
2439 : void
2440 7090 : loop_distribution::merge_dep_scc_partitions (struct graph *rdg,
2441 : vec<struct partition *> *partitions,
2442 : bool ignore_alias_p)
2443 : {
2444 7090 : struct partition *partition1, *partition2;
2445 7090 : struct pg_vdata *data;
2446 7090 : graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p);
2447 7090 : int i, j, num_sccs = graphds_scc (pg, NULL);
2448 :
2449 : /* Strong connected compoenent means dependence cycle, we cannot distribute
2450 : them. So fuse them together. */
2451 7090 : if ((unsigned) num_sccs < partitions->length ())
2452 : {
2453 1989 : for (i = 0; i < num_sccs; ++i)
2454 : {
2455 2162 : for (j = 0; partitions->iterate (j, &partition1); ++j)
2456 2162 : if (pg->vertices[j].component == i)
2457 : break;
2458 9990 : for (j = j + 1; partitions->iterate (j, &partition2); ++j)
2459 7920 : if (pg->vertices[j].component == i)
2460 : {
2461 6845 : partition_merge_into (NULL, partition1,
2462 : partition2, FUSE_SAME_SCC);
2463 6845 : partition1->type = PTYPE_SEQUENTIAL;
2464 6845 : (*partitions)[j] = NULL;
2465 6845 : partition_free (partition2);
2466 6845 : data = (struct pg_vdata *)pg->vertices[j].data;
2467 6845 : data->partition = NULL;
2468 : }
2469 : }
2470 : }
2471 :
2472 7090 : sort_partitions_by_post_order (pg, partitions);
2473 14180 : gcc_assert (partitions->length () == (unsigned)num_sccs);
2474 7090 : free_partition_graph_vdata (pg);
2475 7090 : for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2476 7090 : free_graph (pg);
2477 7090 : }
2478 :
2479 : /* Callback function for traversing edge E in graph G. DATA is private
2480 : callback data. */
2481 :
2482 : static void
2483 743 : pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data)
2484 : {
2485 743 : int i, j, component;
2486 743 : struct pg_edge_callback_data *cbdata;
2487 743 : struct pg_edata *edata = (struct pg_edata *) e->data;
2488 :
2489 : /* If the edge doesn't have attached data dependence, it represents
2490 : compilation time known dependences. This type dependence cannot
2491 : be resolved by runtime alias check. */
2492 743 : if (edata == NULL || edata->alias_ddrs.length () == 0)
2493 : return;
2494 :
2495 725 : cbdata = (struct pg_edge_callback_data *) data;
2496 725 : i = e->src;
2497 725 : j = e->dest;
2498 725 : component = cbdata->vertices_component[i];
2499 : /* Vertices are topologically sorted according to compilation time
2500 : known dependences, so we can break strong connected components
2501 : by removing edges of the opposite direction, i.e, edges pointing
2502 : from vertice with smaller post number to vertice with bigger post
2503 : number. */
2504 725 : if (g->vertices[i].post < g->vertices[j].post
2505 : /* We only need to remove edges connecting vertices in the same
2506 : strong connected component to break it. */
2507 369 : && component == cbdata->vertices_component[j]
2508 : /* Check if we want to break the strong connected component or not. */
2509 1094 : && !bitmap_bit_p (cbdata->sccs_to_merge, component))
2510 369 : cbdata->alias_ddrs->safe_splice (edata->alias_ddrs);
2511 : }
2512 :
2513 : /* Callback function for traversing edge E. DATA is private
2514 : callback data. */
2515 :
2516 : static void
2517 743 : pg_unmark_merged_alias_ddrs (struct graph *, struct graph_edge *e, void *data)
2518 : {
2519 743 : int i, j, component;
2520 743 : struct pg_edge_callback_data *cbdata;
2521 743 : struct pg_edata *edata = (struct pg_edata *) e->data;
2522 :
2523 743 : if (edata == NULL || edata->alias_ddrs.length () == 0)
2524 : return;
2525 :
2526 726 : cbdata = (struct pg_edge_callback_data *) data;
2527 726 : i = e->src;
2528 726 : j = e->dest;
2529 726 : component = cbdata->vertices_component[i];
2530 : /* Make sure to not skip vertices inside SCCs we are going to merge. */
2531 726 : if (component == cbdata->vertices_component[j]
2532 726 : && bitmap_bit_p (cbdata->sccs_to_merge, component))
2533 : {
2534 1 : edata->alias_ddrs.release ();
2535 1 : delete edata;
2536 1 : e->data = NULL;
2537 : }
2538 : }
2539 :
2540 : /* This is the main function breaking strong connected components in
2541 : PARTITIONS giving reduced dependence graph RDG. Store data dependence
2542 : relations for runtime alias check in ALIAS_DDRS. */
2543 : void
2544 5940 : loop_distribution::break_alias_scc_partitions (struct graph *rdg,
2545 : vec<struct partition *> *partitions,
2546 : vec<ddr_p> *alias_ddrs)
2547 : {
2548 5940 : int i, j, k, num_sccs, num_sccs_no_alias = 0;
2549 : /* Build partition dependence graph. */
2550 5940 : graph *pg = build_partition_graph (rdg, partitions, false);
2551 :
2552 5940 : alias_ddrs->truncate (0);
2553 : /* Find strong connected components in the graph, with all dependence edges
2554 : considered. */
2555 5940 : num_sccs = graphds_scc (pg, NULL);
2556 : /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2557 : compilation time known dependences are merged before this function. */
2558 5940 : if ((unsigned) num_sccs < partitions->length ())
2559 : {
2560 297 : struct pg_edge_callback_data cbdata;
2561 297 : auto_bitmap sccs_to_merge;
2562 297 : auto_vec<enum partition_type> scc_types;
2563 297 : struct partition *partition, *first;
2564 :
2565 : /* If all partitions in a SCC have the same type, we can simply merge the
2566 : SCC. This loop finds out such SCCS and record them in bitmap. */
2567 297 : bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
2568 908 : for (i = 0; i < num_sccs; ++i)
2569 : {
2570 337 : for (j = 0; partitions->iterate (j, &first); ++j)
2571 337 : if (pg->vertices[j].component == i)
2572 : break;
2573 :
2574 314 : bool same_type = true, all_builtins = partition_builtin_p (first);
2575 1552 : for (++j; partitions->iterate (j, &partition); ++j)
2576 : {
2577 1276 : if (pg->vertices[j].component != i)
2578 154 : continue;
2579 :
2580 1122 : if (first->type != partition->type)
2581 : {
2582 : same_type = false;
2583 : break;
2584 : }
2585 1084 : all_builtins &= partition_builtin_p (partition);
2586 : }
2587 : /* Merge SCC if all partitions in SCC have the same type, though the
2588 : result partition is sequential, because vectorizer can do better
2589 : runtime alias check. One expecption is all partitions in SCC are
2590 : builtins. */
2591 314 : if (!same_type || all_builtins)
2592 80 : bitmap_clear_bit (sccs_to_merge, i);
2593 : }
2594 :
2595 : /* Initialize callback data for traversing. */
2596 297 : cbdata.sccs_to_merge = sccs_to_merge;
2597 297 : cbdata.alias_ddrs = alias_ddrs;
2598 297 : cbdata.vertices_component = XNEWVEC (int, pg->n_vertices);
2599 : /* Record the component information which will be corrupted by next
2600 : graph scc finding call. */
2601 1737 : for (i = 0; i < pg->n_vertices; ++i)
2602 1440 : cbdata.vertices_component[i] = pg->vertices[i].component;
2603 :
2604 : /* Collect data dependences for runtime alias checks to break SCCs. */
2605 297 : if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
2606 : {
2607 : /* For SCCs we want to merge clear all alias_ddrs for edges
2608 : inside the component. */
2609 76 : for_each_edge (pg, pg_unmark_merged_alias_ddrs, &cbdata);
2610 :
2611 : /* Run SCC finding algorithm again, with alias dependence edges
2612 : skipped. This is to topologically sort partitions according to
2613 : compilation time known dependence. Note the topological order
2614 : is stored in the form of pg's post order number. */
2615 76 : num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
2616 : /* We cannot assert partitions->length () == num_sccs_no_alias
2617 : since we are not ignoring alias edges in cycles we are
2618 : going to merge. That's required to compute correct postorder. */
2619 : /* With topological order, we can construct two subgraphs L and R.
2620 : L contains edge <x, y> where x < y in terms of post order, while
2621 : R contains edge <x, y> where x > y. Edges for compilation time
2622 : known dependence all fall in R, so we break SCCs by removing all
2623 : (alias) edges of in subgraph L. */
2624 76 : for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);
2625 : }
2626 :
2627 : /* For SCC that doesn't need to be broken, merge it. */
2628 611 : for (i = 0; i < num_sccs; ++i)
2629 : {
2630 314 : if (!bitmap_bit_p (sccs_to_merge, i))
2631 80 : continue;
2632 :
2633 251 : for (j = 0; partitions->iterate (j, &first); ++j)
2634 251 : if (cbdata.vertices_component[j] == i)
2635 : break;
2636 1649 : for (k = j + 1; partitions->iterate (k, &partition); ++k)
2637 : {
2638 1101 : struct pg_vdata *data;
2639 :
2640 1101 : if (cbdata.vertices_component[k] != i)
2641 146 : continue;
2642 :
2643 955 : partition_merge_into (NULL, first, partition, FUSE_SAME_SCC);
2644 955 : (*partitions)[k] = NULL;
2645 955 : partition_free (partition);
2646 955 : data = (struct pg_vdata *)pg->vertices[k].data;
2647 955 : gcc_assert (data->id == k);
2648 955 : data->partition = NULL;
2649 : /* The result partition of merged SCC must be sequential. */
2650 955 : first->type = PTYPE_SEQUENTIAL;
2651 : }
2652 : }
2653 : /* If reduction partition's SCC is broken by runtime alias checks,
2654 : we force a negative post order to it making sure it will be scheduled
2655 : in the last. */
2656 297 : if (num_sccs_no_alias > 0)
2657 : {
2658 : j = -1;
2659 330 : for (i = 0; i < pg->n_vertices; ++i)
2660 : {
2661 254 : struct pg_vdata *data = (struct pg_vdata *)pg->vertices[i].data;
2662 254 : if (data->partition && partition_reduction_p (data->partition))
2663 : {
2664 5 : gcc_assert (j == -1);
2665 : j = i;
2666 : }
2667 : }
2668 76 : if (j >= 0)
2669 5 : pg->vertices[j].post = -1;
2670 : }
2671 :
2672 297 : free (cbdata.vertices_component);
2673 297 : }
2674 :
2675 5940 : sort_partitions_by_post_order (pg, partitions);
2676 5940 : free_partition_graph_vdata (pg);
2677 5940 : for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2678 5940 : free_graph (pg);
2679 :
2680 5940 : if (dump_file && (dump_flags & TDF_DETAILS))
2681 : {
2682 15 : fprintf (dump_file, "Possible alias data dependence to break:\n");
2683 15 : dump_data_dependence_relations (dump_file, *alias_ddrs);
2684 : }
2685 5940 : }
2686 :
2687 : /* Compute and return an expression whose value is the segment length which
2688 : will be accessed by DR in NITERS iterations. */
2689 :
2690 : static tree
2691 1292 : data_ref_segment_size (struct data_reference *dr, tree niters)
2692 : {
2693 1292 : niters = size_binop (MINUS_EXPR,
2694 : fold_convert (sizetype, niters),
2695 : size_one_node);
2696 1292 : return size_binop (MULT_EXPR,
2697 : fold_convert (sizetype, DR_STEP (dr)),
2698 : fold_convert (sizetype, niters));
2699 : }
2700 :
2701 : /* Return true if LOOP's latch is dominated by statement for data reference
2702 : DR. */
2703 :
2704 : static inline bool
2705 1292 : latch_dominated_by_data_ref (class loop *loop, data_reference *dr)
2706 : {
2707 1292 : return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
2708 1292 : gimple_bb (DR_STMT (dr)));
2709 : }
2710 :
2711 : /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2712 : data dependence relations ALIAS_DDRS. */
2713 :
2714 : static void
2715 76 : compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
2716 : vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
2717 : {
2718 76 : unsigned int i;
2719 76 : unsigned HOST_WIDE_INT factor = 1;
2720 76 : tree niters_plus_one, niters = number_of_latch_executions (loop);
2721 :
2722 76 : gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
2723 76 : niters = fold_convert (sizetype, niters);
2724 76 : niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
2725 :
2726 76 : if (dump_file && (dump_flags & TDF_DETAILS))
2727 0 : fprintf (dump_file, "Creating alias check pairs:\n");
2728 :
2729 : /* Iterate all data dependence relations and compute alias check pairs. */
2730 722 : for (i = 0; i < alias_ddrs->length (); i++)
2731 : {
2732 646 : ddr_p ddr = (*alias_ddrs)[i];
2733 646 : struct data_reference *dr_a = DDR_A (ddr);
2734 646 : struct data_reference *dr_b = DDR_B (ddr);
2735 646 : tree seg_length_a, seg_length_b;
2736 :
2737 646 : if (latch_dominated_by_data_ref (loop, dr_a))
2738 642 : seg_length_a = data_ref_segment_size (dr_a, niters_plus_one);
2739 : else
2740 4 : seg_length_a = data_ref_segment_size (dr_a, niters);
2741 :
2742 646 : if (latch_dominated_by_data_ref (loop, dr_b))
2743 642 : seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
2744 : else
2745 4 : seg_length_b = data_ref_segment_size (dr_b, niters);
2746 :
2747 646 : unsigned HOST_WIDE_INT access_size_a
2748 646 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
2749 646 : unsigned HOST_WIDE_INT access_size_b
2750 646 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
2751 646 : unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
2752 646 : unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
2753 :
2754 646 : dr_with_seg_len_pair_t dr_with_seg_len_pair
2755 1292 : (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
2756 1292 : dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b),
2757 : /* ??? Would WELL_ORDERED be safe? */
2758 646 : dr_with_seg_len_pair_t::REORDERED);
2759 :
2760 646 : comp_alias_pairs->safe_push (dr_with_seg_len_pair);
2761 : }
2762 :
2763 76 : if (tree_fits_uhwi_p (niters))
2764 46 : factor = tree_to_uhwi (niters);
2765 :
2766 : /* Prune alias check pairs. */
2767 76 : prune_runtime_alias_test_list (comp_alias_pairs, factor);
2768 76 : if (dump_file && (dump_flags & TDF_DETAILS))
2769 0 : fprintf (dump_file,
2770 : "Improved number of alias checks from %d to %d\n",
2771 : alias_ddrs->length (), comp_alias_pairs->length ());
2772 76 : }
2773 :
2774 : /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2775 : checks and version LOOP under condition of these runtime alias checks. */
2776 :
2777 : static void
2778 76 : version_loop_by_alias_check (vec<struct partition *> *partitions,
2779 : class loop *loop, vec<ddr_p> *alias_ddrs)
2780 : {
2781 76 : profile_probability prob;
2782 76 : basic_block cond_bb;
2783 76 : class loop *nloop;
2784 76 : tree lhs, arg0, cond_expr = NULL_TREE;
2785 76 : gimple_seq cond_stmts = NULL;
2786 76 : gimple *call_stmt = NULL;
2787 76 : auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs;
2788 :
2789 : /* Generate code for runtime alias checks if necessary. */
2790 76 : gcc_assert (alias_ddrs->length () > 0);
2791 :
2792 76 : if (dump_file && (dump_flags & TDF_DETAILS))
2793 0 : fprintf (dump_file,
2794 : "Version loop <%d> with runtime alias check\n", loop->num);
2795 :
2796 76 : compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs);
2797 76 : create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
2798 76 : cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
2799 : is_gimple_val, NULL_TREE);
2800 :
2801 : /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2802 76 : bool cancelable_p = flag_tree_loop_vectorize;
2803 76 : if (cancelable_p)
2804 : {
2805 : unsigned i = 0;
2806 : struct partition *partition;
2807 217 : for (; partitions->iterate (i, &partition); ++i)
2808 183 : if (!partition_builtin_p (partition))
2809 : break;
2810 :
2811 : /* If all partitions are builtins, distributing it would be profitable and
2812 : we don't want to cancel the runtime alias checks. */
2813 144 : if (i == partitions->length ())
2814 : cancelable_p = false;
2815 : }
2816 :
2817 : /* Generate internal function call for loop distribution alias check if the
2818 : runtime alias check should be cancelable. */
2819 42 : if (cancelable_p)
2820 : {
2821 38 : call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
2822 : 2, NULL_TREE, cond_expr);
2823 38 : lhs = make_ssa_name (boolean_type_node);
2824 38 : gimple_call_set_lhs (call_stmt, lhs);
2825 : }
2826 : else
2827 : lhs = cond_expr;
2828 :
2829 76 : prob = profile_probability::guessed_always ().apply_scale (9, 10);
2830 76 : initialize_original_copy_tables ();
2831 76 : nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (),
2832 : prob, prob.invert (), true);
2833 76 : free_original_copy_tables ();
2834 : /* Record the original loop number in newly generated loops. In case of
2835 : distribution, the original loop will be distributed and the new loop
2836 : is kept. */
2837 76 : loop->orig_loop_num = nloop->num;
2838 76 : nloop->orig_loop_num = nloop->num;
2839 76 : nloop->dont_vectorize = true;
2840 76 : nloop->force_vectorize = false;
2841 :
2842 76 : if (call_stmt)
2843 : {
2844 : /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2845 : loop could be destroyed. */
2846 38 : arg0 = build_int_cst (integer_type_node, loop->orig_loop_num);
2847 38 : gimple_call_set_arg (call_stmt, 0, arg0);
2848 38 : gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt);
2849 : }
2850 :
2851 76 : if (cond_stmts)
2852 : {
2853 76 : gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb);
2854 76 : gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT);
2855 : }
2856 76 : update_ssa (TODO_update_ssa_no_phi);
2857 76 : }
2858 :
2859 : /* Return true if loop versioning is needed to distribute PARTITIONS.
2860 : ALIAS_DDRS are data dependence relations for runtime alias check. */
2861 :
2862 : static inline bool
2863 13350 : version_for_distribution_p (vec<struct partition *> *partitions,
2864 : vec<ddr_p> *alias_ddrs)
2865 : {
2866 : /* No need to version loop if we have only one partition. */
2867 16158 : if (partitions->length () == 1)
2868 : return false;
2869 :
2870 : /* Need to version loop if runtime alias check is necessary. */
2871 2808 : return (alias_ddrs->length () > 0);
2872 : }
2873 :
2874 : /* Compare base offset of builtin mem* partitions P1 and P2. */
2875 :
2876 : static int
2877 367 : offset_cmp (const void *vp1, const void *vp2)
2878 : {
2879 367 : struct partition *p1 = *(struct partition *const *) vp1;
2880 367 : struct partition *p2 = *(struct partition *const *) vp2;
2881 367 : unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
2882 367 : unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
2883 367 : return (o2 < o1) - (o1 < o2);
2884 : }
2885 :
2886 : /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2887 : case optimization transforming below code:
2888 :
2889 : __builtin_memset (&obj, 0, 100);
2890 : _1 = &obj + 100;
2891 : __builtin_memset (_1, 0, 200);
2892 : _2 = &obj + 300;
2893 : __builtin_memset (_2, 0, 100);
2894 :
2895 : into:
2896 :
2897 : __builtin_memset (&obj, 0, 400);
2898 :
2899 : Note we don't have dependence information between different partitions
2900 : at this point, as a result, we can't handle nonadjacent memset builtin
2901 : partitions since dependence might be broken. */
2902 :
2903 : static void
2904 2857 : fuse_memset_builtins (vec<struct partition *> *partitions)
2905 : {
2906 2857 : unsigned i, j;
2907 2857 : struct partition *part1, *part2;
2908 2857 : tree rhs1, rhs2;
2909 :
2910 8996 : for (i = 0; partitions->iterate (i, &part1);)
2911 : {
2912 6139 : if (part1->kind != PKIND_MEMSET)
2913 : {
2914 3592 : i++;
2915 3592 : continue;
2916 : }
2917 :
2918 : /* Find sub-array of memset builtins of the same base. Index range
2919 : of the sub-array is [i, j) with "j > i". */
2920 2619 : for (j = i + 1; partitions->iterate (j, &part2); ++j)
2921 : {
2922 1919 : if (part2->kind != PKIND_MEMSET
2923 2642 : || !operand_equal_p (part1->builtin->dst_base_base,
2924 723 : part2->builtin->dst_base_base, 0))
2925 : break;
2926 :
2927 : /* Memset calls setting different values can't be merged. */
2928 118 : rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2929 118 : rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2930 118 : if (!operand_equal_p (rhs1, rhs2, 0))
2931 : break;
2932 : }
2933 :
2934 : /* Stable sort is required in order to avoid breaking dependence. */
2935 2547 : gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
2936 : offset_cmp);
2937 : /* Continue with next partition. */
2938 2547 : i = j;
2939 : }
2940 :
2941 : /* Merge all consecutive memset builtin partitions. */
2942 12422 : for (i = 0; i < partitions->length () - 1;)
2943 : {
2944 3354 : part1 = (*partitions)[i];
2945 3354 : if (part1->kind != PKIND_MEMSET)
2946 : {
2947 1435 : i++;
2948 3326 : continue;
2949 : }
2950 :
2951 1919 : part2 = (*partitions)[i + 1];
2952 : /* Only merge memset partitions of the same base and with constant
2953 : access sizes. */
2954 3728 : if (part2->kind != PKIND_MEMSET
2955 723 : || TREE_CODE (part1->builtin->size) != INTEGER_CST
2956 458 : || TREE_CODE (part2->builtin->size) != INTEGER_CST
2957 2377 : || !operand_equal_p (part1->builtin->dst_base_base,
2958 458 : part2->builtin->dst_base_base, 0))
2959 : {
2960 1809 : i++;
2961 1809 : continue;
2962 : }
2963 110 : rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2964 110 : rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2965 110 : int bytev1 = const_with_all_bytes_same (rhs1);
2966 110 : int bytev2 = const_with_all_bytes_same (rhs2);
2967 : /* Only merge memset partitions of the same value. */
2968 110 : if (bytev1 != bytev2 || bytev1 == -1)
2969 : {
2970 42 : i++;
2971 42 : continue;
2972 : }
2973 136 : wide_int end1 = wi::add (part1->builtin->dst_base_offset,
2974 68 : wi::to_wide (part1->builtin->size));
2975 : /* Only merge adjacent memset partitions. */
2976 68 : if (wi::ne_p (end1, part2->builtin->dst_base_offset))
2977 : {
2978 40 : i++;
2979 40 : continue;
2980 : }
2981 : /* Merge partitions[i] and partitions[i+1]. */
2982 28 : part1->builtin->size = fold_build2 (PLUS_EXPR, sizetype,
2983 : part1->builtin->size,
2984 : part2->builtin->size);
2985 28 : partition_free (part2);
2986 28 : partitions->ordered_remove (i + 1);
2987 68 : }
2988 2857 : }
2989 :
2990 : void
2991 41535 : loop_distribution::finalize_partitions (class loop *loop,
2992 : vec<struct partition *> *partitions,
2993 : vec<ddr_p> *alias_ddrs)
2994 : {
2995 41535 : unsigned i;
2996 41535 : struct partition *partition, *a;
2997 :
2998 47516 : if (partitions->length () == 1
2999 41611 : || alias_ddrs->length () > 0)
3000 41535 : return;
3001 :
3002 5905 : unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
3003 5905 : bool same_type_p = true;
3004 5905 : enum partition_type type = ((*partitions)[0])->type;
3005 30866 : for (i = 0; partitions->iterate (i, &partition); ++i)
3006 : {
3007 24961 : same_type_p &= (type == partition->type);
3008 24961 : if (partition_builtin_p (partition))
3009 : {
3010 2991 : num_builtin++;
3011 2991 : continue;
3012 : }
3013 21970 : num_normal++;
3014 21970 : if (partition->kind == PKIND_PARTIAL_MEMSET)
3015 4 : num_partial_memset++;
3016 : }
3017 :
3018 : /* Don't distribute current loop into too many loops given we don't have
3019 : memory stream cost model. Be even more conservative in case of loop
3020 : nest distribution. */
3021 5905 : if ((same_type_p && num_builtin == 0
3022 3021 : && (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
3023 2888 : || (loop->inner != NULL
3024 74 : && i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
3025 2879 : || (loop->inner == NULL
3026 2814 : && i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
3027 : {
3028 : a = (*partitions)[0];
3029 18750 : for (i = 1; partitions->iterate (i, &partition); ++i)
3030 : {
3031 15702 : partition_merge_into (NULL, a, partition, FUSE_FINALIZE);
3032 15702 : partition_free (partition);
3033 : }
3034 3048 : partitions->truncate (1);
3035 : }
3036 :
3037 : /* Fuse memset builtins if possible. */
3038 5905 : if (partitions->length () > 1)
3039 2857 : fuse_memset_builtins (partitions);
3040 : }
3041 :
3042 : /* Distributes the code from LOOP in such a way that producer statements
3043 : are placed before consumer statements. Tries to separate only the
3044 : statements from STMTS into separate loops. Returns the number of
3045 : distributed loops. Set NB_CALLS to number of generated builtin calls.
3046 : Set *DESTROY_P to whether LOOP needs to be destroyed. */
3047 :
3048 : int
3049 143332 : loop_distribution::distribute_loop (class loop *loop,
3050 : const vec<gimple *> &stmts,
3051 : control_dependences *cd, int *nb_calls, bool *destroy_p,
3052 : bool only_patterns_p)
3053 : {
3054 143332 : ddrs_table = new hash_table<ddr_hasher> (389);
3055 143332 : struct graph *rdg;
3056 143332 : partition *partition;
3057 143332 : int i, nbp;
3058 :
3059 143332 : *destroy_p = false;
3060 143332 : *nb_calls = 0;
3061 143332 : loop_nest.create (0);
3062 143332 : if (!find_loop_nest (loop, &loop_nest))
3063 : {
3064 0 : loop_nest.release ();
3065 0 : delete ddrs_table;
3066 : return 0;
3067 : }
3068 :
3069 143332 : datarefs_vec.create (20);
3070 143332 : has_nonaddressable_dataref_p = false;
3071 143332 : rdg = build_rdg (loop, cd);
3072 143332 : if (!rdg)
3073 : {
3074 929 : if (dump_file && (dump_flags & TDF_DETAILS))
3075 0 : fprintf (dump_file,
3076 : "Loop %d not distributed: failed to build the RDG.\n",
3077 : loop->num);
3078 :
3079 929 : loop_nest.release ();
3080 929 : free_data_refs (datarefs_vec);
3081 929 : delete ddrs_table;
3082 : return 0;
3083 : }
3084 :
3085 284806 : if (datarefs_vec.length () > MAX_DATAREFS_NUM)
3086 : {
3087 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3088 0 : fprintf (dump_file,
3089 : "Loop %d not distributed: too many memory references.\n",
3090 : loop->num);
3091 :
3092 0 : free_rdg (rdg, loop);
3093 0 : loop_nest.release ();
3094 0 : free_data_refs (datarefs_vec);
3095 0 : delete ddrs_table;
3096 : return 0;
3097 : }
3098 :
3099 : data_reference_p dref;
3100 583554 : for (i = 0; datarefs_vec.iterate (i, &dref); ++i)
3101 441151 : dref->aux = (void *) (uintptr_t) i;
3102 :
3103 142403 : if (dump_file && (dump_flags & TDF_DETAILS))
3104 70 : dump_rdg (dump_file, rdg);
3105 :
3106 142403 : auto_vec<struct partition *, 3> partitions;
3107 142403 : rdg_build_partitions (rdg, stmts, &partitions);
3108 :
3109 142403 : auto_vec<ddr_p> alias_ddrs;
3110 :
3111 142403 : auto_bitmap stmt_in_all_partitions;
3112 142403 : bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts);
3113 396068 : for (i = 1; partitions.iterate (i, &partition); ++i)
3114 111262 : bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts);
3115 :
3116 : bool any_builtin = false;
3117 : bool reduction_in_all = false;
3118 396068 : int reduction_partition_num = -1;
3119 538471 : FOR_EACH_VEC_ELT (partitions, i, partition)
3120 : {
3121 253665 : reduction_in_all
3122 253665 : |= classify_partition (loop, rdg, partition, stmt_in_all_partitions);
3123 253665 : any_builtin |= partition_builtin_p (partition);
3124 : }
3125 :
3126 : /* If we are only distributing patterns but did not detect any,
3127 : simply bail out. */
3128 142403 : if (only_patterns_p
3129 142403 : && !any_builtin)
3130 : {
3131 100868 : nbp = 0;
3132 100868 : goto ldist_done;
3133 : }
3134 :
3135 : /* If we are only distributing patterns fuse all partitions that
3136 : were not classified as builtins. This also avoids chopping
3137 : a loop into pieces, separated by builtin calls. That is, we
3138 : only want no or a single loop body remaining. */
3139 41535 : struct partition *into;
3140 41535 : if (only_patterns_p)
3141 : {
3142 20341 : for (i = 0; partitions.iterate (i, &into); ++i)
3143 11970 : if (!partition_builtin_p (into))
3144 : break;
3145 54146 : for (++i; partitions.iterate (i, &partition); ++i)
3146 2667 : if (!partition_builtin_p (partition))
3147 : {
3148 1995 : partition_merge_into (NULL, into, partition, FUSE_NON_BUILTIN);
3149 1995 : partitions.unordered_remove (i);
3150 1995 : partition_free (partition);
3151 1995 : i--;
3152 : }
3153 : }
3154 :
3155 : /* Due to limitations in the transform phase we have to fuse all
3156 : reduction partitions into the last partition so the existing
3157 : loop will contain all loop-closed PHI nodes. */
3158 114941 : for (i = 0; partitions.iterate (i, &into); ++i)
3159 75505 : if (partition_reduction_p (into))
3160 : break;
3161 44165 : for (i = i + 1; partitions.iterate (i, &partition); ++i)
3162 2630 : if (partition_reduction_p (partition))
3163 : {
3164 2351 : partition_merge_into (rdg, into, partition, FUSE_REDUCTION);
3165 2351 : partitions.unordered_remove (i);
3166 2351 : partition_free (partition);
3167 2351 : i--;
3168 : }
3169 :
3170 : /* Apply our simple cost model - fuse partitions with similar
3171 : memory accesses. */
3172 113767 : for (i = 0; partitions.iterate (i, &into); ++i)
3173 : {
3174 72232 : bool changed = false;
3175 1017198 : for (int j = i + 1; partitions.iterate (j, &partition); ++j)
3176 : {
3177 872734 : if (share_memory_accesses (rdg, into, partition))
3178 : {
3179 7216 : partition_merge_into (rdg, into, partition, FUSE_SHARE_REF);
3180 7216 : partitions.unordered_remove (j);
3181 7216 : partition_free (partition);
3182 7216 : j--;
3183 7216 : changed = true;
3184 : }
3185 : }
3186 : /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
3187 : accesses when 1 and 2 have similar accesses but not 0 and 1
3188 : then in the next iteration we will fail to consider merging
3189 : 1 into 0,2. So try again if we did any merging into 0. */
3190 72232 : if (changed)
3191 3664 : i--;
3192 : }
3193 :
3194 : /* Put a non-builtin partition last if we need to preserve a reduction.
3195 : In most cases this helps to keep a normal partition last avoiding to
3196 : spill a reduction result across builtin calls.
3197 : ??? The proper way would be to use dependences to see whether we
3198 : can move builtin partitions earlier during merge_dep_scc_partitions
3199 : and its sort_partitions_by_post_order. Especially when the
3200 : dependence graph is composed of multiple independent subgraphs the
3201 : heuristic does not work reliably. */
3202 41535 : if (reduction_in_all
3203 48709 : && partition_builtin_p (partitions.last()))
3204 140 : FOR_EACH_VEC_ELT (partitions, i, partition)
3205 76 : if (!partition_builtin_p (partition))
3206 : {
3207 11 : partitions.unordered_remove (i);
3208 11 : partitions.quick_push (partition);
3209 11 : break;
3210 : }
3211 :
3212 : /* Build the partition dependency graph and fuse partitions in strong
3213 : connected component. */
3214 41535 : if (partitions.length () > 1)
3215 : {
3216 : /* Don't support loop nest distribution under runtime alias check
3217 : since it's not likely to enable many vectorization opportunities.
3218 : Also if loop has any data reference which may be not addressable
3219 : since alias check needs to take, compare address of the object. */
3220 7090 : if (loop->inner || has_nonaddressable_dataref_p)
3221 379 : merge_dep_scc_partitions (rdg, &partitions, false);
3222 : else
3223 : {
3224 6711 : merge_dep_scc_partitions (rdg, &partitions, true);
3225 6711 : if (partitions.length () > 1)
3226 5940 : break_alias_scc_partitions (rdg, &partitions, &alias_ddrs);
3227 : }
3228 : }
3229 :
3230 41535 : finalize_partitions (loop, &partitions, &alias_ddrs);
3231 :
3232 : /* If there is a reduction in all partitions make sure the last
3233 : non-builtin partition provides the LC PHI defs. */
3234 41535 : if (reduction_in_all)
3235 : {
3236 21570 : FOR_EACH_VEC_ELT (partitions, i, partition)
3237 7222 : if (!partition_builtin_p (partition))
3238 7146 : reduction_partition_num = i;
3239 7174 : if (reduction_partition_num == -1)
3240 : {
3241 : /* If all partitions are builtin, force the last one to
3242 : be code generated as normal partition. */
3243 64 : partition = partitions.last ();
3244 64 : partition->kind = PKIND_NORMAL;
3245 : }
3246 : }
3247 :
3248 41535 : nbp = partitions.length ();
3249 41535 : if (nbp == 0
3250 80145 : || (nbp == 1 && !partition_builtin_p (partitions[0]))
3251 55002 : || (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
3252 : {
3253 28185 : nbp = 0;
3254 28185 : goto ldist_done;
3255 : }
3256 :
3257 13426 : if (version_for_distribution_p (&partitions, &alias_ddrs))
3258 76 : version_loop_by_alias_check (&partitions, loop, &alias_ddrs);
3259 :
3260 13350 : if (dump_file && (dump_flags & TDF_DETAILS))
3261 : {
3262 42 : fprintf (dump_file,
3263 : "distribute loop <%d> into partitions:\n", loop->num);
3264 42 : dump_rdg_partitions (dump_file, partitions);
3265 : }
3266 :
3267 30086 : FOR_EACH_VEC_ELT (partitions, i, partition)
3268 : {
3269 16736 : if (partition_builtin_p (partition))
3270 13588 : (*nb_calls)++;
3271 16736 : *destroy_p |= generate_code_for_partition (loop, partition, i < nbp - 1,
3272 : i == reduction_partition_num);
3273 : }
3274 :
3275 142403 : ldist_done:
3276 142403 : loop_nest.release ();
3277 142403 : free_data_refs (datarefs_vec);
3278 142403 : for (hash_table<ddr_hasher>::iterator iter = ddrs_table->begin ();
3279 1330697 : iter != ddrs_table->end (); ++iter)
3280 : {
3281 1188294 : free_dependence_relation (*iter);
3282 1188294 : *iter = NULL;
3283 : }
3284 142403 : delete ddrs_table;
3285 :
3286 503379 : FOR_EACH_VEC_ELT (partitions, i, partition)
3287 218573 : partition_free (partition);
3288 :
3289 142403 : free_rdg (rdg, loop);
3290 142403 : return nbp - *nb_calls;
3291 142403 : }
3292 :
3293 :
3294 206498 : void loop_distribution::bb_top_order_init (void)
3295 : {
3296 206498 : int rpo_num;
3297 206498 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
3298 206498 : edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3299 206498 : bitmap exit_bbs = BITMAP_ALLOC (NULL);
3300 :
3301 206498 : bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun));
3302 206498 : bb_top_order_index_size = last_basic_block_for_fn (cfun);
3303 :
3304 206498 : entry->flags &= ~EDGE_DFS_BACK;
3305 206498 : bitmap_set_bit (exit_bbs, EXIT_BLOCK);
3306 206498 : rpo_num = rev_post_order_and_mark_dfs_back_seme (cfun, entry, exit_bbs, true,
3307 : rpo, NULL);
3308 206498 : BITMAP_FREE (exit_bbs);
3309 :
3310 7368308 : for (int i = 0; i < rpo_num; i++)
3311 6955312 : bb_top_order_index[rpo[i]] = i;
3312 :
3313 206498 : free (rpo);
3314 206498 : }
3315 :
3316 206498 : void loop_distribution::bb_top_order_destroy ()
3317 : {
3318 206498 : free (bb_top_order_index);
3319 206498 : bb_top_order_index = NULL;
3320 206498 : bb_top_order_index_size = 0;
3321 206498 : }
3322 :
3323 :
3324 : /* Given LOOP, this function records seed statements for distribution in
3325 : WORK_LIST. Return false if there is nothing for distribution. */
3326 :
3327 : static bool
3328 189058 : find_seed_stmts_for_distribution (class loop *loop, vec<gimple *> *work_list)
3329 : {
3330 189058 : basic_block *bbs = get_loop_body_in_dom_order (loop);
3331 :
3332 : /* Initialize the worklist with stmts we seed the partitions with. */
3333 871495 : for (unsigned i = 0; i < loop->num_nodes; ++i)
3334 : {
3335 : /* In irreducible sub-regions we don't know how to redirect
3336 : conditions, so fail. See PR100492. */
3337 538949 : if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
3338 : {
3339 4 : if (dump_file && (dump_flags & TDF_DETAILS))
3340 0 : fprintf (dump_file, "loop %d contains an irreducible region.\n",
3341 : loop->num);
3342 4 : work_list->truncate (0);
3343 4 : break;
3344 : }
3345 538945 : for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
3346 1270519 : !gsi_end_p (gsi); gsi_next (&gsi))
3347 : {
3348 731574 : gphi *phi = gsi.phi ();
3349 1463148 : if (virtual_operand_p (gimple_phi_result (phi)))
3350 195731 : continue;
3351 : /* Distribute stmts which have defs that are used outside of
3352 : the loop. */
3353 535843 : if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
3354 510738 : continue;
3355 25105 : work_list->safe_push (phi);
3356 : }
3357 1077890 : for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
3358 3807560 : !gsi_end_p (gsi); gsi_next (&gsi))
3359 : {
3360 3314181 : gimple *stmt = gsi_stmt (gsi);
3361 :
3362 : /* Ignore clobbers, they do not have true side effects. */
3363 3314181 : if (gimple_clobber_p (stmt))
3364 2991354 : continue;
3365 :
3366 : /* If there is a stmt with side-effects bail out - we
3367 : cannot and should not distribute this loop. */
3368 3306048 : if (gimple_has_side_effects (stmt))
3369 : {
3370 45566 : free (bbs);
3371 45566 : return false;
3372 : }
3373 :
3374 : /* Distribute stmts which have defs that are used outside of
3375 : the loop. */
3376 3260482 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3377 : ;
3378 : /* Otherwise only distribute stores for now. */
3379 5026475 : else if (!gimple_vdef (stmt))
3380 2983221 : continue;
3381 :
3382 277261 : work_list->safe_push (stmt);
3383 : }
3384 : }
3385 143492 : bool res = work_list->length () > 0;
3386 143340 : if (res && !can_copy_bbs_p (bbs, loop->num_nodes))
3387 : {
3388 7 : if (dump_file && (dump_flags & TDF_DETAILS))
3389 0 : fprintf (dump_file, "cannot copy loop %d.\n", loop->num);
3390 : res = false;
3391 : }
3392 143492 : free (bbs);
3393 143492 : return res;
3394 : }
3395 :
3396 : /* A helper function for generate_{rawmemchr,strlen}_builtin functions in order
3397 : to place new statements SEQ before LOOP and replace the old reduction
3398 : variable with the new one. */
3399 :
3400 : static void
3401 29 : generate_reduction_builtin_1 (loop_p loop, gimple_seq &seq,
3402 : tree reduction_var_old, tree reduction_var_new,
3403 : const char *info, machine_mode load_mode)
3404 : {
3405 29 : gcc_assert (flag_tree_loop_distribute_patterns);
3406 :
3407 : /* Place new statements before LOOP. */
3408 29 : gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
3409 29 : gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
3410 :
3411 : /* Replace old reduction variable with new one. */
3412 29 : imm_use_iterator iter;
3413 29 : gimple *stmt;
3414 29 : use_operand_p use_p;
3415 115 : FOR_EACH_IMM_USE_STMT (stmt, iter, reduction_var_old)
3416 : {
3417 172 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3418 86 : SET_USE (use_p, reduction_var_new);
3419 :
3420 86 : update_stmt (stmt);
3421 29 : }
3422 :
3423 29 : if (dump_file && (dump_flags & TDF_DETAILS))
3424 7 : fprintf (dump_file, info, GET_MODE_NAME (load_mode));
3425 29 : }
3426 :
3427 : /* Generate a call to rawmemchr and place it before LOOP. REDUCTION_VAR is
3428 : replaced with a fresh SSA name representing the result of the call. */
3429 :
3430 : static void
3431 0 : generate_rawmemchr_builtin (loop_p loop, tree reduction_var,
3432 : data_reference_p store_dr, tree base, tree pattern,
3433 : location_t loc)
3434 : {
3435 0 : gimple_seq seq = NULL;
3436 :
3437 0 : tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3438 0 : gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, mem, pattern);
3439 0 : tree reduction_var_new = copy_ssa_name (reduction_var);
3440 0 : gimple_call_set_lhs (fn_call, reduction_var_new);
3441 0 : gimple_set_location (fn_call, loc);
3442 0 : gimple_seq_add_stmt (&seq, fn_call);
3443 :
3444 0 : if (store_dr)
3445 : {
3446 0 : gassign *g = gimple_build_assign (DR_REF (store_dr), reduction_var_new);
3447 0 : gimple_seq_add_stmt (&seq, g);
3448 : }
3449 :
3450 0 : generate_reduction_builtin_1 (loop, seq, reduction_var, reduction_var_new,
3451 : "generated rawmemchr%s\n",
3452 0 : TYPE_MODE (TREE_TYPE (TREE_TYPE (base))));
3453 0 : }
3454 :
3455 : /* Helper function for generate_strlen_builtin(,_using_rawmemchr) */
3456 :
3457 : static void
3458 29 : generate_strlen_builtin_1 (loop_p loop, gimple_seq &seq,
3459 : tree reduction_var_old, tree reduction_var_new,
3460 : machine_mode mode, tree start_len)
3461 : {
3462 : /* REDUCTION_VAR_NEW has either size type or ptrdiff type and must be
3463 : converted if types of old and new reduction variable are not compatible. */
3464 29 : reduction_var_new = gimple_convert (&seq, TREE_TYPE (reduction_var_old),
3465 : reduction_var_new);
3466 :
3467 : /* Loops of the form `for (i=42; s[i]; ++i);` have an additional start
3468 : length. */
3469 29 : if (!integer_zerop (start_len))
3470 : {
3471 25 : tree lhs = make_ssa_name (TREE_TYPE (reduction_var_new));
3472 25 : gimple *g = gimple_build_assign (lhs, PLUS_EXPR, reduction_var_new,
3473 : start_len);
3474 25 : gimple_seq_add_stmt (&seq, g);
3475 25 : reduction_var_new = lhs;
3476 : }
3477 :
3478 29 : generate_reduction_builtin_1 (loop, seq, reduction_var_old, reduction_var_new,
3479 : "generated strlen%s\n", mode);
3480 29 : }
3481 :
3482 : /* Generate a call to strlen and place it before LOOP. REDUCTION_VAR is
3483 : replaced with a fresh SSA name representing the result of the call. */
3484 :
3485 : static void
3486 29 : generate_strlen_builtin (loop_p loop, tree reduction_var, tree base,
3487 : tree start_len, location_t loc)
3488 : {
3489 29 : gimple_seq seq = NULL;
3490 :
3491 29 : tree reduction_var_new = make_ssa_name (size_type_node);
3492 :
3493 29 : tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3494 58 : tree fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_STRLEN));
3495 29 : gimple *fn_call = gimple_build_call (fn, 1, mem);
3496 29 : gimple_call_set_lhs (fn_call, reduction_var_new);
3497 29 : gimple_set_location (fn_call, loc);
3498 29 : gimple_seq_add_stmt (&seq, fn_call);
3499 :
3500 29 : generate_strlen_builtin_1 (loop, seq, reduction_var, reduction_var_new,
3501 : QImode, start_len);
3502 29 : }
3503 :
3504 : /* Generate code in order to mimic the behaviour of strlen but this time over
3505 : an array of elements with mode different than QI. REDUCTION_VAR is replaced
3506 : with a fresh SSA name representing the result, i.e., the length. */
3507 :
3508 : static void
3509 0 : generate_strlen_builtin_using_rawmemchr (loop_p loop, tree reduction_var,
3510 : tree base, tree load_type,
3511 : tree start_len, location_t loc)
3512 : {
3513 0 : gimple_seq seq = NULL;
3514 :
3515 0 : tree start = force_gimple_operand (base, &seq, true, NULL_TREE);
3516 0 : tree zero = build_zero_cst (load_type);
3517 0 : gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, start, zero);
3518 0 : tree end = make_ssa_name (TREE_TYPE (base));
3519 0 : gimple_call_set_lhs (fn_call, end);
3520 0 : gimple_set_location (fn_call, loc);
3521 0 : gimple_seq_add_stmt (&seq, fn_call);
3522 :
3523 : /* Determine the number of elements between START and END by
3524 : evaluating (END - START) / sizeof (*START). */
3525 0 : tree diff = make_ssa_name (ptrdiff_type_node);
3526 0 : gimple *diff_stmt = gimple_build_assign (diff, POINTER_DIFF_EXPR, end, start);
3527 0 : gimple_seq_add_stmt (&seq, diff_stmt);
3528 : /* Let SIZE be the size of each character. */
3529 0 : tree size = gimple_convert (&seq, ptrdiff_type_node,
3530 0 : TYPE_SIZE_UNIT (load_type));
3531 0 : tree count = make_ssa_name (ptrdiff_type_node);
3532 0 : gimple *count_stmt = gimple_build_assign (count, TRUNC_DIV_EXPR, diff, size);
3533 0 : gimple_seq_add_stmt (&seq, count_stmt);
3534 :
3535 0 : generate_strlen_builtin_1 (loop, seq, reduction_var, count,
3536 0 : TYPE_MODE (load_type),
3537 : start_len);
3538 0 : }
3539 :
3540 : /* Return true if we can count at least as many characters by taking pointer
3541 : difference as we can count via reduction_var without an overflow. Thus
3542 : compute 2^n < (2^(m-1) / s) where n = TYPE_PRECISION (reduction_var_type),
3543 : m = TYPE_PRECISION (ptrdiff_type_node), and s = size of each character. */
3544 : static bool
3545 0 : reduction_var_overflows_first (tree reduction_var_type, tree load_type)
3546 : {
3547 0 : widest_int n2 = wi::lshift (1, TYPE_PRECISION (reduction_var_type));;
3548 0 : widest_int m2 = wi::lshift (1, TYPE_PRECISION (ptrdiff_type_node) - 1);
3549 0 : widest_int s = wi::to_widest (TYPE_SIZE_UNIT (load_type));
3550 0 : return wi::ltu_p (n2, wi::udiv_trunc (m2, s));
3551 0 : }
3552 :
3553 : static gimple *
3554 25348 : determine_reduction_stmt_1 (const loop_p loop, const basic_block *bbs)
3555 : {
3556 25348 : gimple *reduction_stmt = NULL;
3557 :
3558 92421 : for (unsigned i = 0, ninsns = 0; i < loop->num_nodes; ++i)
3559 : {
3560 72628 : basic_block bb = bbs[i];
3561 :
3562 139667 : for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
3563 67039 : gsi_next (&bsi))
3564 : {
3565 67775 : gphi *phi = bsi.phi ();
3566 135550 : if (virtual_operand_p (gimple_phi_result (phi)))
3567 21082 : continue;
3568 46693 : if (stmt_has_scalar_dependences_outside_loop (loop, phi))
3569 : {
3570 8195 : if (reduction_stmt)
3571 736 : return NULL;
3572 : reduction_stmt = phi;
3573 : }
3574 : }
3575 :
3576 71892 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
3577 224846 : !gsi_end_p (bsi); gsi_next_nondebug (&bsi), ++ninsns)
3578 : {
3579 : /* Bail out early for loops which are unlikely to match. */
3580 157773 : if (ninsns > 16)
3581 4819 : return NULL;
3582 154836 : gimple *stmt = gsi_stmt (bsi);
3583 154836 : if (gimple_clobber_p (stmt))
3584 5687 : continue;
3585 149149 : if (gimple_code (stmt) == GIMPLE_LABEL)
3586 995 : continue;
3587 264142 : if (gimple_has_volatile_ops (stmt))
3588 : return NULL;
3589 148107 : if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3590 : {
3591 6151 : if (reduction_stmt)
3592 : return NULL;
3593 : reduction_stmt = stmt;
3594 : }
3595 : }
3596 : }
3597 :
3598 : return reduction_stmt;
3599 : }
3600 :
3601 : /* If LOOP has a single non-volatile reduction statement, then return a pointer
3602 : to it. Otherwise return NULL. */
3603 : static gimple *
3604 25348 : determine_reduction_stmt (const loop_p loop)
3605 : {
3606 25348 : basic_block *bbs = get_loop_body (loop);
3607 25348 : gimple *reduction_stmt = determine_reduction_stmt_1 (loop, bbs);
3608 25348 : XDELETEVEC (bbs);
3609 25348 : return reduction_stmt;
3610 : }
3611 :
3612 : /* Transform loops which mimic the effects of builtins rawmemchr or strlen and
3613 : replace them accordingly. For example, a loop of the form
3614 :
3615 : for (; *p != 42; ++p);
3616 :
3617 : is replaced by
3618 :
3619 : p = rawmemchr<MODE> (p, 42);
3620 :
3621 : under the assumption that rawmemchr is available for a particular MODE.
3622 : Another example is
3623 :
3624 : int i;
3625 : for (i = 42; s[i]; ++i);
3626 :
3627 : which is replaced by
3628 :
3629 : i = (int)strlen (&s[42]) + 42;
3630 :
3631 : for some character array S. In case array S is not of type character array
3632 : we end up with
3633 :
3634 : i = (int)(rawmemchr<MODE> (&s[42], 0) - &s[42]) + 42;
3635 :
3636 : assuming that rawmemchr is available for a particular MODE. */
3637 :
3638 : bool
3639 85271 : loop_distribution::transform_reduction_loop (loop_p loop)
3640 : {
3641 85271 : gimple *reduction_stmt;
3642 85271 : data_reference_p load_dr = NULL, store_dr = NULL;
3643 :
3644 85271 : edge e = single_exit (loop);
3645 170542 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (e->src));
3646 67761 : if (!cond)
3647 : return false;
3648 : /* Ensure loop condition is an (in)equality test and loop is exited either if
3649 : the inequality test fails or the equality test succeeds. */
3650 52071 : if (!(e->flags & EDGE_FALSE_VALUE && gimple_cond_code (cond) == NE_EXPR)
3651 89444 : && !(e->flags & EDGE_TRUE_VALUE && gimple_cond_code (cond) == EQ_EXPR))
3652 : return false;
3653 : /* A limitation of the current implementation is that we only support
3654 : constant patterns in (in)equality tests. */
3655 33269 : tree pattern = gimple_cond_rhs (cond);
3656 33269 : if (TREE_CODE (pattern) != INTEGER_CST)
3657 : return false;
3658 :
3659 25348 : reduction_stmt = determine_reduction_stmt (loop);
3660 :
3661 : /* A limitation of the current implementation is that we require a reduction
3662 : statement. Therefore, loops without a reduction statement as in the
3663 : following are not recognized:
3664 : int *p;
3665 : void foo (void) { for (; *p; ++p); } */
3666 25348 : if (reduction_stmt == NULL)
3667 : return false;
3668 :
3669 : /* Reduction variables are guaranteed to be SSA names. */
3670 9077 : tree reduction_var;
3671 9077 : switch (gimple_code (reduction_stmt))
3672 : {
3673 8980 : case GIMPLE_ASSIGN:
3674 8980 : case GIMPLE_PHI:
3675 8980 : reduction_var = gimple_get_lhs (reduction_stmt);
3676 8980 : break;
3677 : default:
3678 : /* Bail out e.g. for GIMPLE_CALL. */
3679 : return false;
3680 : }
3681 :
3682 8980 : struct graph *rdg = build_rdg (loop, NULL);
3683 8980 : if (rdg == NULL)
3684 : {
3685 699 : if (dump_file && (dump_flags & TDF_DETAILS))
3686 0 : fprintf (dump_file,
3687 : "Loop %d not transformed: failed to build the RDG.\n",
3688 : loop->num);
3689 :
3690 : return false;
3691 : }
3692 16562 : auto_bitmap partition_stmts;
3693 8281 : bitmap_set_range (partition_stmts, 0, rdg->n_vertices);
3694 8281 : find_single_drs (loop, rdg, partition_stmts, &store_dr, &load_dr);
3695 8281 : free_rdg (rdg, loop);
3696 :
3697 : /* Bail out if there is no single load. */
3698 8281 : if (load_dr == NULL)
3699 : return false;
3700 :
3701 : /* Reaching this point we have a loop with a single reduction variable,
3702 : a single load, and an optional single store. */
3703 :
3704 4421 : tree load_ref = DR_REF (load_dr);
3705 4421 : tree load_type = TREE_TYPE (load_ref);
3706 4421 : tree load_access_base = build_fold_addr_expr (load_ref);
3707 4421 : tree load_access_size = TYPE_SIZE_UNIT (load_type);
3708 4421 : affine_iv load_iv, reduction_iv;
3709 :
3710 4421 : if (!INTEGRAL_TYPE_P (load_type)
3711 4421 : || !type_has_mode_precision_p (load_type))
3712 : return false;
3713 :
3714 : /* We already ensured that the loop condition tests for (in)equality where the
3715 : rhs is a constant pattern. Now ensure that the lhs is the result of the
3716 : load. */
3717 1681 : if (gimple_cond_lhs (cond) != gimple_assign_lhs (DR_STMT (load_dr)))
3718 : return false;
3719 :
3720 : /* Bail out if no affine induction variable with constant step can be
3721 : determined. */
3722 1536 : if (!simple_iv (loop, loop, load_access_base, &load_iv, false))
3723 : return false;
3724 :
3725 : /* Bail out if memory accesses are not consecutive or not growing. */
3726 1515 : if (!operand_equal_p (load_iv.step, load_access_size, 0))
3727 : return false;
3728 :
3729 1487 : if (!simple_iv (loop, loop, reduction_var, &reduction_iv, false))
3730 : return false;
3731 :
3732 : /* Handle rawmemchr like loops. */
3733 1371 : if (operand_equal_p (load_iv.base, reduction_iv.base)
3734 1371 : && operand_equal_p (load_iv.step, reduction_iv.step))
3735 : {
3736 351 : if (store_dr)
3737 : {
3738 : /* Ensure that we store to X and load from X+I where I>0. */
3739 0 : if (TREE_CODE (load_iv.base) != POINTER_PLUS_EXPR
3740 0 : || !integer_onep (TREE_OPERAND (load_iv.base, 1)))
3741 : return false;
3742 0 : tree ptr_base = TREE_OPERAND (load_iv.base, 0);
3743 0 : if (TREE_CODE (ptr_base) != SSA_NAME)
3744 : return false;
3745 0 : gimple *def = SSA_NAME_DEF_STMT (ptr_base);
3746 0 : if (!gimple_assign_single_p (def)
3747 0 : || gimple_assign_rhs1 (def) != DR_REF (store_dr))
3748 : return false;
3749 : /* Ensure that the reduction value is stored. */
3750 0 : if (gimple_assign_rhs1 (DR_STMT (store_dr)) != reduction_var)
3751 : return false;
3752 : }
3753 : /* Bail out if target does not provide rawmemchr for a certain mode. */
3754 351 : machine_mode mode = TYPE_MODE (load_type);
3755 351 : if (direct_optab_handler (rawmemchr_optab, mode) == CODE_FOR_nothing)
3756 : return false;
3757 0 : location_t loc = gimple_location (DR_STMT (load_dr));
3758 0 : generate_rawmemchr_builtin (loop, reduction_var, store_dr, load_iv.base,
3759 : pattern, loc);
3760 0 : return true;
3761 : }
3762 :
3763 : /* Handle strlen like loops. */
3764 1020 : if (store_dr == NULL
3765 1010 : && integer_zerop (pattern)
3766 1010 : && INTEGRAL_TYPE_P (TREE_TYPE (reduction_var))
3767 1000 : && TREE_CODE (reduction_iv.base) == INTEGER_CST
3768 996 : && TREE_CODE (reduction_iv.step) == INTEGER_CST
3769 2016 : && integer_onep (reduction_iv.step))
3770 : {
3771 940 : location_t loc = gimple_location (DR_STMT (load_dr));
3772 940 : tree reduction_var_type = TREE_TYPE (reduction_var);
3773 : /* While determining the length of a string an overflow might occur.
3774 : If an overflow only occurs in the loop implementation and not in the
3775 : strlen implementation, then either the overflow is undefined or the
3776 : truncated result of strlen equals the one of the loop. Otherwise if
3777 : an overflow may also occur in the strlen implementation, then
3778 : replacing a loop by a call to strlen is sound whenever we ensure that
3779 : if an overflow occurs in the strlen implementation, then also an
3780 : overflow occurs in the loop implementation which is undefined. It
3781 : seems reasonable to relax this and assume that the strlen
3782 : implementation cannot overflow in case sizetype is big enough in the
3783 : sense that an overflow can only happen for string objects which are
3784 : bigger than half of the address space; at least for 32-bit targets and
3785 : up.
3786 :
3787 : For strlen which makes use of rawmemchr the maximal length of a string
3788 : which can be determined without an overflow is PTRDIFF_MAX / S where
3789 : each character has size S. Since an overflow for ptrdiff type is
3790 : undefined we have to make sure that if an overflow occurs, then an
3791 : overflow occurs in the loop implementation, too, and this is
3792 : undefined, too. Similar as before we relax this and assume that no
3793 : string object is larger than half of the address space; at least for
3794 : 32-bit targets and up. */
3795 940 : if (TYPE_MODE (load_type) == TYPE_MODE (char_type_node)
3796 656 : && TYPE_PRECISION (load_type) == TYPE_PRECISION (char_type_node)
3797 656 : && ((TYPE_PRECISION (sizetype) >= TYPE_PRECISION (ptr_type_node) - 1
3798 656 : && TYPE_PRECISION (ptr_type_node) >= 32)
3799 0 : || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3800 0 : && TYPE_PRECISION (reduction_var_type) <= TYPE_PRECISION (sizetype)))
3801 969 : && builtin_decl_implicit (BUILT_IN_STRLEN))
3802 29 : generate_strlen_builtin (loop, reduction_var, load_iv.base,
3803 : reduction_iv.base, loc);
3804 911 : else if (direct_optab_handler (rawmemchr_optab, TYPE_MODE (load_type))
3805 : != CODE_FOR_nothing
3806 911 : && ((TYPE_PRECISION (ptrdiff_type_node) == TYPE_PRECISION (ptr_type_node)
3807 0 : && TYPE_PRECISION (ptrdiff_type_node) >= 32)
3808 0 : || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3809 0 : && reduction_var_overflows_first (reduction_var_type, load_type))))
3810 0 : generate_strlen_builtin_using_rawmemchr (loop, reduction_var,
3811 : load_iv.base,
3812 : load_type,
3813 : reduction_iv.base, loc);
3814 : else
3815 : return false;
3816 : return true;
3817 : }
3818 :
3819 : return false;
3820 : }
3821 :
3822 : /* Given innermost LOOP, return the outermost enclosing loop that forms a
3823 : perfect loop nest. */
3824 :
3825 : static class loop *
3826 171908 : prepare_perfect_loop_nest (class loop *loop)
3827 : {
3828 171908 : class loop *outer = loop_outer (loop);
3829 171908 : tree niters = number_of_latch_executions (loop);
3830 :
3831 : /* TODO: We only support the innermost 3-level loop nest distribution
3832 : because of compilation time issue for now. This should be relaxed
3833 : in the future. Note we only allow 3-level loop nest distribution
3834 : when parallelizing loops. */
3835 171908 : while ((loop->inner == NULL
3836 17663 : || (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
3837 171968 : && loop_outer (outer)
3838 41811 : && outer->inner == loop && loop->next == NULL
3839 27077 : && single_exit (outer)
3840 25360 : && !chrec_contains_symbols_defined_in_loop (niters, outer->num)
3841 18598 : && (niters = number_of_latch_executions (outer)) != NULL_TREE
3842 208169 : && niters != chrec_dont_know)
3843 : {
3844 17663 : loop = outer;
3845 17663 : outer = loop_outer (loop);
3846 : }
3847 :
3848 171908 : return loop;
3849 : }
3850 :
3851 :
3852 : unsigned int
3853 206498 : loop_distribution::execute (function *fun)
3854 : {
3855 206498 : bool changed = false;
3856 206498 : basic_block bb;
3857 206498 : control_dependences *cd = NULL;
3858 206498 : auto_vec<loop_p> loops_to_be_destroyed;
3859 :
3860 619494 : if (number_of_loops (fun) <= 1)
3861 : return 0;
3862 :
3863 206498 : bb_top_order_init ();
3864 :
3865 7574806 : FOR_ALL_BB_FN (bb, fun)
3866 : {
3867 7368308 : gimple_stmt_iterator gsi;
3868 11424059 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3869 4055751 : gimple_set_uid (gsi_stmt (gsi), -1);
3870 69339175 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3871 54602559 : gimple_set_uid (gsi_stmt (gsi), -1);
3872 : }
3873 :
3874 : /* We can at the moment only distribute non-nested loops, thus restrict
3875 : walking to innermost loops. */
3876 1050254 : for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
3877 : {
3878 : /* Don't distribute multiple exit edges loop, or cold loop when
3879 : not doing pattern detection. */
3880 430760 : if (!single_exit (loop)
3881 430760 : || (!flag_tree_loop_distribute_patterns
3882 1377 : && !optimize_loop_for_speed_p (loop)))
3883 173357 : continue;
3884 :
3885 : /* If niters is unknown don't distribute loop but rather try to transform
3886 : it to a call to a builtin. */
3887 257403 : tree niters = number_of_latch_executions (loop);
3888 257403 : if (niters == NULL_TREE || niters == chrec_dont_know)
3889 : {
3890 85495 : datarefs_vec.create (20);
3891 85495 : if (flag_tree_loop_distribute_patterns
3892 85495 : && transform_reduction_loop (loop))
3893 : {
3894 29 : changed = true;
3895 29 : loops_to_be_destroyed.safe_push (loop);
3896 29 : if (dump_enabled_p ())
3897 : {
3898 7 : dump_user_location_t loc = find_loop_location (loop);
3899 7 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3900 : loc, "Loop %d transformed into a builtin.\n",
3901 : loop->num);
3902 : }
3903 : }
3904 85495 : free_data_refs (datarefs_vec);
3905 85495 : continue;
3906 85495 : }
3907 :
3908 : /* Get the perfect loop nest for distribution. */
3909 171908 : loop = prepare_perfect_loop_nest (loop);
3910 347616 : for (; loop; loop = loop->inner)
3911 : {
3912 189058 : auto_vec<gimple *> work_list;
3913 189058 : if (!find_seed_stmts_for_distribution (loop, &work_list))
3914 45726 : continue;
3915 :
3916 143332 : const char *str = loop->inner ? " nest" : "";
3917 143332 : dump_user_location_t loc = find_loop_location (loop);
3918 143332 : if (!cd)
3919 : {
3920 63491 : calculate_dominance_info (CDI_DOMINATORS);
3921 63491 : calculate_dominance_info (CDI_POST_DOMINATORS);
3922 63491 : cd = new control_dependences ();
3923 63491 : free_dominance_info (CDI_POST_DOMINATORS);
3924 : }
3925 :
3926 143332 : bool destroy_p;
3927 143332 : int nb_generated_loops, nb_generated_calls;
3928 143332 : bool only_patterns = !optimize_loop_for_speed_p (loop)
3929 143332 : || !flag_tree_loop_distribution;
3930 : /* do not try to distribute loops that are not expected to iterate. */
3931 31890 : if (!only_patterns)
3932 : {
3933 31890 : HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
3934 31890 : if (iterations < 0)
3935 15297 : iterations = likely_max_loop_iterations_int (loop);
3936 31890 : if (!iterations)
3937 111452 : only_patterns = true;
3938 : }
3939 143332 : nb_generated_loops
3940 143332 : = distribute_loop (loop, work_list, cd, &nb_generated_calls,
3941 : &destroy_p, only_patterns);
3942 143332 : if (destroy_p)
3943 11403 : loops_to_be_destroyed.safe_push (loop);
3944 :
3945 143332 : if (nb_generated_loops + nb_generated_calls > 0)
3946 : {
3947 13350 : changed = true;
3948 13350 : if (dump_enabled_p ())
3949 71 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3950 : loc, "Loop%s %d distributed: split to %d loops "
3951 : "and %d library calls.\n", str, loop->num,
3952 : nb_generated_loops, nb_generated_calls);
3953 :
3954 13350 : break;
3955 : }
3956 :
3957 129982 : if (dump_file && (dump_flags & TDF_DETAILS))
3958 28 : fprintf (dump_file, "Loop%s %d not distributed.\n", str, loop->num);
3959 189058 : }
3960 206498 : }
3961 :
3962 206498 : if (cd)
3963 63491 : delete cd;
3964 :
3965 206498 : if (bb_top_order_index != NULL)
3966 206498 : bb_top_order_destroy ();
3967 :
3968 206498 : if (changed)
3969 : {
3970 : /* Destroy loop bodies that could not be reused. Do this late as we
3971 : otherwise can end up referring to stale data in control
3972 : dependences. */
3973 : unsigned i;
3974 : class loop *loop;
3975 19378 : FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
3976 11432 : destroy_loop (loop);
3977 :
3978 : /* Cached scalar evolutions now may refer to wrong or non-existing
3979 : loops. */
3980 7946 : scev_reset ();
3981 7946 : mark_virtual_operands_for_renaming (fun);
3982 7946 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3983 : }
3984 :
3985 206498 : checking_verify_loop_structure ();
3986 :
3987 206498 : return changed ? TODO_cleanup_cfg : 0;
3988 206498 : }
3989 :
3990 :
3991 : /* Distribute all loops in the current function. */
3992 :
3993 : namespace {
3994 :
3995 : const pass_data pass_data_loop_distribution =
3996 : {
3997 : GIMPLE_PASS, /* type */
3998 : "ldist", /* name */
3999 : OPTGROUP_LOOP, /* optinfo_flags */
4000 : TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
4001 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4002 : 0, /* properties_provided */
4003 : 0, /* properties_destroyed */
4004 : 0, /* todo_flags_start */
4005 : 0, /* todo_flags_finish */
4006 : };
4007 :
4008 : class pass_loop_distribution : public gimple_opt_pass
4009 : {
4010 : public:
4011 295358 : pass_loop_distribution (gcc::context *ctxt)
4012 590716 : : gimple_opt_pass (pass_data_loop_distribution, ctxt)
4013 : {}
4014 :
4015 : /* opt_pass methods: */
4016 247323 : bool gate (function *) final override
4017 : {
4018 247323 : return flag_tree_loop_distribution
4019 247323 : || flag_tree_loop_distribute_patterns;
4020 : }
4021 :
4022 : unsigned int execute (function *) final override;
4023 :
4024 : }; // class pass_loop_distribution
4025 :
4026 : unsigned int
4027 206498 : pass_loop_distribution::execute (function *fun)
4028 : {
4029 206498 : return loop_distribution ().execute (fun);
4030 : }
4031 :
4032 : } // anon namespace
4033 :
4034 : gimple_opt_pass *
4035 295358 : make_pass_loop_distribution (gcc::context *ctxt)
4036 : {
4037 295358 : return new pass_loop_distribution (ctxt);
4038 : }
|
