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