S/390: Fix conditional returns on z196+
[official-gcc.git] / gcc / tree-loop-distribution.c
blobd8db03b545b08929a28cd81fd3308c77bc5e151c
1 /* Loop distribution.
2 Copyright (C) 2006-2018 Free Software Foundation, Inc.
3 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
4 and Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
11 later version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass performs loop distribution: for example, the loop
24 |DO I = 2, N
25 | A(I) = B(I) + C
26 | D(I) = A(I-1)*E
27 |ENDDO
29 is transformed to
31 |DOALL I = 2, N
32 | A(I) = B(I) + C
33 |ENDDO
35 |DOALL I = 2, N
36 | D(I) = A(I-1)*E
37 |ENDDO
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:
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.
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. */
92 #include "config.h"
93 #include "system.h"
94 #include "coretypes.h"
95 #include "backend.h"
96 #include "tree.h"
97 #include "gimple.h"
98 #include "cfghooks.h"
99 #include "tree-pass.h"
100 #include "ssa.h"
101 #include "gimple-pretty-print.h"
102 #include "fold-const.h"
103 #include "cfganal.h"
104 #include "gimple-iterator.h"
105 #include "gimplify-me.h"
106 #include "stor-layout.h"
107 #include "tree-cfg.h"
108 #include "tree-ssa-loop-manip.h"
109 #include "tree-ssa-loop-ivopts.h"
110 #include "tree-ssa-loop.h"
111 #include "tree-into-ssa.h"
112 #include "tree-ssa.h"
113 #include "cfgloop.h"
114 #include "tree-scalar-evolution.h"
115 #include "params.h"
116 #include "tree-vectorizer.h"
119 #define MAX_DATAREFS_NUM \
120 ((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
122 /* Threshold controlling number of distributed partitions. Given it may
123 be unnecessary if a memory stream cost model is invented in the future,
124 we define it as a temporary macro, rather than a parameter. */
125 #define NUM_PARTITION_THRESHOLD (4)
127 /* Hashtable helpers. */
129 struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
131 static inline hashval_t hash (const data_dependence_relation *);
132 static inline bool equal (const data_dependence_relation *,
133 const data_dependence_relation *);
136 /* Hash function for data dependence. */
138 inline hashval_t
139 ddr_hasher::hash (const data_dependence_relation *ddr)
141 inchash::hash h;
142 h.add_ptr (DDR_A (ddr));
143 h.add_ptr (DDR_B (ddr));
144 return h.end ();
147 /* Hash table equality function for data dependence. */
149 inline bool
150 ddr_hasher::equal (const data_dependence_relation *ddr1,
151 const data_dependence_relation *ddr2)
153 return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
156 /* The loop (nest) to be distributed. */
157 static vec<loop_p> loop_nest;
159 /* Vector of data references in the loop to be distributed. */
160 static vec<data_reference_p> datarefs_vec;
162 /* Store index of data reference in aux field. */
163 #define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
165 /* Hash table for data dependence relation in the loop to be distributed. */
166 static hash_table<ddr_hasher> *ddrs_table;
168 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
169 struct rdg_vertex
171 /* The statement represented by this vertex. */
172 gimple *stmt;
174 /* Vector of data-references in this statement. */
175 vec<data_reference_p> datarefs;
177 /* True when the statement contains a write to memory. */
178 bool has_mem_write;
180 /* True when the statement contains a read from memory. */
181 bool has_mem_reads;
184 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
185 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
186 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
187 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
188 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
189 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
190 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
191 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
193 /* Data dependence type. */
195 enum rdg_dep_type
197 /* Read After Write (RAW). */
198 flow_dd = 'f',
200 /* Control dependence (execute conditional on). */
201 control_dd = 'c'
204 /* Dependence information attached to an edge of the RDG. */
206 struct rdg_edge
208 /* Type of the dependence. */
209 enum rdg_dep_type type;
212 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
214 /* Dump vertex I in RDG to FILE. */
216 static void
217 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
219 struct vertex *v = &(rdg->vertices[i]);
220 struct graph_edge *e;
222 fprintf (file, "(vertex %d: (%s%s) (in:", i,
223 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
224 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
226 if (v->pred)
227 for (e = v->pred; e; e = e->pred_next)
228 fprintf (file, " %d", e->src);
230 fprintf (file, ") (out:");
232 if (v->succ)
233 for (e = v->succ; e; e = e->succ_next)
234 fprintf (file, " %d", e->dest);
236 fprintf (file, ")\n");
237 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
238 fprintf (file, ")\n");
241 /* Call dump_rdg_vertex on stderr. */
243 DEBUG_FUNCTION void
244 debug_rdg_vertex (struct graph *rdg, int i)
246 dump_rdg_vertex (stderr, rdg, i);
249 /* Dump the reduced dependence graph RDG to FILE. */
251 static void
252 dump_rdg (FILE *file, struct graph *rdg)
254 fprintf (file, "(rdg\n");
255 for (int i = 0; i < rdg->n_vertices; i++)
256 dump_rdg_vertex (file, rdg, i);
257 fprintf (file, ")\n");
260 /* Call dump_rdg on stderr. */
262 DEBUG_FUNCTION void
263 debug_rdg (struct graph *rdg)
265 dump_rdg (stderr, rdg);
268 static void
269 dot_rdg_1 (FILE *file, struct graph *rdg)
271 int i;
272 pretty_printer buffer;
273 pp_needs_newline (&buffer) = false;
274 buffer.buffer->stream = file;
276 fprintf (file, "digraph RDG {\n");
278 for (i = 0; i < rdg->n_vertices; i++)
280 struct vertex *v = &(rdg->vertices[i]);
281 struct graph_edge *e;
283 fprintf (file, "%d [label=\"[%d] ", i, i);
284 pp_gimple_stmt_1 (&buffer, RDGV_STMT (v), 0, TDF_SLIM);
285 pp_flush (&buffer);
286 fprintf (file, "\"]\n");
288 /* Highlight reads from memory. */
289 if (RDG_MEM_READS_STMT (rdg, i))
290 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
292 /* Highlight stores to memory. */
293 if (RDG_MEM_WRITE_STMT (rdg, i))
294 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
296 if (v->succ)
297 for (e = v->succ; e; e = e->succ_next)
298 switch (RDGE_TYPE (e))
300 case flow_dd:
301 /* These are the most common dependences: don't print these. */
302 fprintf (file, "%d -> %d \n", i, e->dest);
303 break;
305 case control_dd:
306 fprintf (file, "%d -> %d [label=control] \n", i, e->dest);
307 break;
309 default:
310 gcc_unreachable ();
314 fprintf (file, "}\n\n");
317 /* Display the Reduced Dependence Graph using dotty. */
319 DEBUG_FUNCTION void
320 dot_rdg (struct graph *rdg)
322 /* When debugging, you may want to enable the following code. */
323 #ifdef HAVE_POPEN
324 FILE *file = popen ("dot -Tx11", "w");
325 if (!file)
326 return;
327 dot_rdg_1 (file, rdg);
328 fflush (file);
329 close (fileno (file));
330 pclose (file);
331 #else
332 dot_rdg_1 (stderr, rdg);
333 #endif
336 /* Returns the index of STMT in RDG. */
338 static int
339 rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple *stmt)
341 int index = gimple_uid (stmt);
342 gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
343 return index;
346 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
347 the index of DEF in RDG. */
349 static void
350 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
352 use_operand_p imm_use_p;
353 imm_use_iterator iterator;
355 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
357 struct graph_edge *e;
358 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
360 if (use < 0)
361 continue;
363 e = add_edge (rdg, idef, use);
364 e->data = XNEW (struct rdg_edge);
365 RDGE_TYPE (e) = flow_dd;
369 /* Creates an edge for the control dependences of BB to the vertex V. */
371 static void
372 create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
373 int v, control_dependences *cd)
375 bitmap_iterator bi;
376 unsigned edge_n;
377 EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
378 0, edge_n, bi)
380 basic_block cond_bb = cd->get_edge_src (edge_n);
381 gimple *stmt = last_stmt (cond_bb);
382 if (stmt && is_ctrl_stmt (stmt))
384 struct graph_edge *e;
385 int c = rdg_vertex_for_stmt (rdg, stmt);
386 if (c < 0)
387 continue;
389 e = add_edge (rdg, c, v);
390 e->data = XNEW (struct rdg_edge);
391 RDGE_TYPE (e) = control_dd;
396 /* Creates the edges of the reduced dependence graph RDG. */
398 static void
399 create_rdg_flow_edges (struct graph *rdg)
401 int i;
402 def_operand_p def_p;
403 ssa_op_iter iter;
405 for (i = 0; i < rdg->n_vertices; i++)
406 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
407 iter, SSA_OP_DEF)
408 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
411 /* Creates the edges of the reduced dependence graph RDG. */
413 static void
414 create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop)
416 int i;
418 for (i = 0; i < rdg->n_vertices; i++)
420 gimple *stmt = RDG_STMT (rdg, i);
421 if (gimple_code (stmt) == GIMPLE_PHI)
423 edge_iterator ei;
424 edge e;
425 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
426 if (flow_bb_inside_loop_p (loop, e->src))
427 create_edge_for_control_dependence (rdg, e->src, i, cd);
429 else
430 create_edge_for_control_dependence (rdg, gimple_bb (stmt), i, cd);
434 /* Build the vertices of the reduced dependence graph RDG. Return false
435 if that failed. */
437 static bool
438 create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop)
440 int i;
441 gimple *stmt;
443 FOR_EACH_VEC_ELT (stmts, i, stmt)
445 struct vertex *v = &(rdg->vertices[i]);
447 /* Record statement to vertex mapping. */
448 gimple_set_uid (stmt, i);
450 v->data = XNEW (struct rdg_vertex);
451 RDGV_STMT (v) = stmt;
452 RDGV_DATAREFS (v).create (0);
453 RDGV_HAS_MEM_WRITE (v) = false;
454 RDGV_HAS_MEM_READS (v) = false;
455 if (gimple_code (stmt) == GIMPLE_PHI)
456 continue;
458 unsigned drp = datarefs_vec.length ();
459 if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec))
460 return false;
461 for (unsigned j = drp; j < datarefs_vec.length (); ++j)
463 data_reference_p dr = datarefs_vec[j];
464 if (DR_IS_READ (dr))
465 RDGV_HAS_MEM_READS (v) = true;
466 else
467 RDGV_HAS_MEM_WRITE (v) = true;
468 RDGV_DATAREFS (v).safe_push (dr);
471 return true;
474 /* Array mapping basic block's index to its topological order. */
475 static int *bb_top_order_index;
476 /* And size of the array. */
477 static int bb_top_order_index_size;
479 /* If X has a smaller topological sort number than Y, returns -1;
480 if greater, returns 1. */
482 static int
483 bb_top_order_cmp (const void *x, const void *y)
485 basic_block bb1 = *(const basic_block *) x;
486 basic_block bb2 = *(const basic_block *) y;
488 gcc_assert (bb1->index < bb_top_order_index_size
489 && bb2->index < bb_top_order_index_size);
490 gcc_assert (bb1 == bb2
491 || bb_top_order_index[bb1->index]
492 != bb_top_order_index[bb2->index]);
494 return (bb_top_order_index[bb1->index] - bb_top_order_index[bb2->index]);
497 /* Initialize STMTS with all the statements of LOOP. We use topological
498 order to discover all statements. The order is important because
499 generate_loops_for_partition is using the same traversal for identifying
500 statements in loop copies. */
502 static void
503 stmts_from_loop (struct loop *loop, vec<gimple *> *stmts)
505 unsigned int i;
506 basic_block *bbs = get_loop_body_in_custom_order (loop, bb_top_order_cmp);
508 for (i = 0; i < loop->num_nodes; i++)
510 basic_block bb = bbs[i];
512 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
513 gsi_next (&bsi))
514 if (!virtual_operand_p (gimple_phi_result (bsi.phi ())))
515 stmts->safe_push (bsi.phi ());
517 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
518 gsi_next (&bsi))
520 gimple *stmt = gsi_stmt (bsi);
521 if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
522 stmts->safe_push (stmt);
526 free (bbs);
529 /* Free the reduced dependence graph RDG. */
531 static void
532 free_rdg (struct graph *rdg)
534 int i;
536 for (i = 0; i < rdg->n_vertices; i++)
538 struct vertex *v = &(rdg->vertices[i]);
539 struct graph_edge *e;
541 for (e = v->succ; e; e = e->succ_next)
542 free (e->data);
544 if (v->data)
546 gimple_set_uid (RDGV_STMT (v), -1);
547 (RDGV_DATAREFS (v)).release ();
548 free (v->data);
552 free_graph (rdg);
555 /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
556 LOOP, and one edge per flow dependence or control dependence from control
557 dependence CD. During visiting each statement, data references are also
558 collected and recorded in global data DATAREFS_VEC. */
560 static struct graph *
561 build_rdg (struct loop *loop, control_dependences *cd)
563 struct graph *rdg;
565 /* Create the RDG vertices from the stmts of the loop nest. */
566 auto_vec<gimple *, 10> stmts;
567 stmts_from_loop (loop, &stmts);
568 rdg = new_graph (stmts.length ());
569 if (!create_rdg_vertices (rdg, stmts, loop))
571 free_rdg (rdg);
572 return NULL;
574 stmts.release ();
576 create_rdg_flow_edges (rdg);
577 if (cd)
578 create_rdg_cd_edges (rdg, cd, loop);
580 return rdg;
584 /* Kind of distributed loop. */
585 enum partition_kind {
586 PKIND_NORMAL,
587 /* Partial memset stands for a paritition can be distributed into a loop
588 of memset calls, rather than a single memset call. It's handled just
589 like a normal parition, i.e, distributed as separate loop, no memset
590 call is generated.
592 Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
593 loop nest as deep as possible. As a result, parloop achieves better
594 parallelization by parallelizing deeper loop nest. This hack should
595 be unnecessary and removed once distributed memset can be understood
596 and analyzed in data reference analysis. See PR82604 for more. */
597 PKIND_PARTIAL_MEMSET,
598 PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
601 /* Type of distributed loop. */
602 enum partition_type {
603 /* The distributed loop can be executed parallelly. */
604 PTYPE_PARALLEL = 0,
605 /* The distributed loop has to be executed sequentially. */
606 PTYPE_SEQUENTIAL
609 /* Builtin info for loop distribution. */
610 struct builtin_info
612 /* data-references a kind != PKIND_NORMAL partition is about. */
613 data_reference_p dst_dr;
614 data_reference_p src_dr;
615 /* Base address and size of memory objects operated by the builtin. Note
616 both dest and source memory objects must have the same size. */
617 tree dst_base;
618 tree src_base;
619 tree size;
620 /* Base and offset part of dst_base after stripping constant offset. This
621 is only used in memset builtin distribution for now. */
622 tree dst_base_base;
623 unsigned HOST_WIDE_INT dst_base_offset;
626 /* Partition for loop distribution. */
627 struct partition
629 /* Statements of the partition. */
630 bitmap stmts;
631 /* True if the partition defines variable which is used outside of loop. */
632 bool reduction_p;
633 enum partition_kind kind;
634 enum partition_type type;
635 /* Data references in the partition. */
636 bitmap datarefs;
637 /* Information of builtin parition. */
638 struct builtin_info *builtin;
642 /* Allocate and initialize a partition from BITMAP. */
644 static partition *
645 partition_alloc (void)
647 partition *partition = XCNEW (struct partition);
648 partition->stmts = BITMAP_ALLOC (NULL);
649 partition->reduction_p = false;
650 partition->kind = PKIND_NORMAL;
651 partition->datarefs = BITMAP_ALLOC (NULL);
652 return partition;
655 /* Free PARTITION. */
657 static void
658 partition_free (partition *partition)
660 BITMAP_FREE (partition->stmts);
661 BITMAP_FREE (partition->datarefs);
662 if (partition->builtin)
663 free (partition->builtin);
665 free (partition);
668 /* Returns true if the partition can be generated as a builtin. */
670 static bool
671 partition_builtin_p (partition *partition)
673 return partition->kind > PKIND_PARTIAL_MEMSET;
676 /* Returns true if the partition contains a reduction. */
678 static bool
679 partition_reduction_p (partition *partition)
681 return partition->reduction_p;
684 /* Partitions are fused because of different reasons. */
685 enum fuse_type
687 FUSE_NON_BUILTIN = 0,
688 FUSE_REDUCTION = 1,
689 FUSE_SHARE_REF = 2,
690 FUSE_SAME_SCC = 3,
691 FUSE_FINALIZE = 4
694 /* Description on different fusing reason. */
695 static const char *fuse_message[] = {
696 "they are non-builtins",
697 "they have reductions",
698 "they have shared memory refs",
699 "they are in the same dependence scc",
700 "there is no point to distribute loop"};
702 static void
703 update_type_for_merge (struct graph *, partition *, partition *);
705 /* Merge PARTITION into the partition DEST. RDG is the reduced dependence
706 graph and we update type for result partition if it is non-NULL. */
708 static void
709 partition_merge_into (struct graph *rdg, partition *dest,
710 partition *partition, enum fuse_type ft)
712 if (dump_file && (dump_flags & TDF_DETAILS))
714 fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]);
715 fprintf (dump_file, " Part 1: ");
716 dump_bitmap (dump_file, dest->stmts);
717 fprintf (dump_file, " Part 2: ");
718 dump_bitmap (dump_file, partition->stmts);
721 dest->kind = PKIND_NORMAL;
722 if (dest->type == PTYPE_PARALLEL)
723 dest->type = partition->type;
725 bitmap_ior_into (dest->stmts, partition->stmts);
726 if (partition_reduction_p (partition))
727 dest->reduction_p = true;
729 /* Further check if any data dependence prevents us from executing the
730 new partition parallelly. */
731 if (dest->type == PTYPE_PARALLEL && rdg != NULL)
732 update_type_for_merge (rdg, dest, partition);
734 bitmap_ior_into (dest->datarefs, partition->datarefs);
738 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
739 the LOOP. */
741 static bool
742 ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
744 imm_use_iterator imm_iter;
745 use_operand_p use_p;
747 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
749 if (is_gimple_debug (USE_STMT (use_p)))
750 continue;
752 basic_block use_bb = gimple_bb (USE_STMT (use_p));
753 if (!flow_bb_inside_loop_p (loop, use_bb))
754 return true;
757 return false;
760 /* Returns true when STMT defines a scalar variable used after the
761 loop LOOP. */
763 static bool
764 stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple *stmt)
766 def_operand_p def_p;
767 ssa_op_iter op_iter;
769 if (gimple_code (stmt) == GIMPLE_PHI)
770 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop);
772 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
773 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop))
774 return true;
776 return false;
779 /* Return a copy of LOOP placed before LOOP. */
781 static struct loop *
782 copy_loop_before (struct loop *loop)
784 struct loop *res;
785 edge preheader = loop_preheader_edge (loop);
787 initialize_original_copy_tables ();
788 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, NULL, preheader);
789 gcc_assert (res != NULL);
790 free_original_copy_tables ();
791 delete_update_ssa ();
793 return res;
796 /* Creates an empty basic block after LOOP. */
798 static void
799 create_bb_after_loop (struct loop *loop)
801 edge exit = single_exit (loop);
803 if (!exit)
804 return;
806 split_edge (exit);
809 /* Generate code for PARTITION from the code in LOOP. The loop is
810 copied when COPY_P is true. All the statements not flagged in the
811 PARTITION bitmap are removed from the loop or from its copy. The
812 statements are indexed in sequence inside a basic block, and the
813 basic blocks of a loop are taken in dom order. */
815 static void
816 generate_loops_for_partition (struct loop *loop, partition *partition,
817 bool copy_p)
819 unsigned i;
820 basic_block *bbs;
822 if (copy_p)
824 int orig_loop_num = loop->orig_loop_num;
825 loop = copy_loop_before (loop);
826 gcc_assert (loop != NULL);
827 loop->orig_loop_num = orig_loop_num;
828 create_preheader (loop, CP_SIMPLE_PREHEADERS);
829 create_bb_after_loop (loop);
831 else
833 /* Origin number is set to the new versioned loop's num. */
834 gcc_assert (loop->orig_loop_num != loop->num);
837 /* Remove stmts not in the PARTITION bitmap. */
838 bbs = get_loop_body_in_dom_order (loop);
840 if (MAY_HAVE_DEBUG_BIND_STMTS)
841 for (i = 0; i < loop->num_nodes; i++)
843 basic_block bb = bbs[i];
845 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
846 gsi_next (&bsi))
848 gphi *phi = bsi.phi ();
849 if (!virtual_operand_p (gimple_phi_result (phi))
850 && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
851 reset_debug_uses (phi);
854 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
856 gimple *stmt = gsi_stmt (bsi);
857 if (gimple_code (stmt) != GIMPLE_LABEL
858 && !is_gimple_debug (stmt)
859 && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
860 reset_debug_uses (stmt);
864 for (i = 0; i < loop->num_nodes; i++)
866 basic_block bb = bbs[i];
867 edge inner_exit = NULL;
869 if (loop != bb->loop_father)
870 inner_exit = single_exit (bb->loop_father);
872 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
874 gphi *phi = bsi.phi ();
875 if (!virtual_operand_p (gimple_phi_result (phi))
876 && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
877 remove_phi_node (&bsi, true);
878 else
879 gsi_next (&bsi);
882 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
884 gimple *stmt = gsi_stmt (bsi);
885 if (gimple_code (stmt) != GIMPLE_LABEL
886 && !is_gimple_debug (stmt)
887 && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
889 /* In distribution of loop nest, if bb is inner loop's exit_bb,
890 we choose its exit edge/path in order to avoid generating
891 infinite loop. For all other cases, we choose an arbitrary
892 path through the empty CFG part that this unnecessary
893 control stmt controls. */
894 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
896 if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
897 gimple_cond_make_true (cond_stmt);
898 else
899 gimple_cond_make_false (cond_stmt);
900 update_stmt (stmt);
902 else if (gimple_code (stmt) == GIMPLE_SWITCH)
904 gswitch *switch_stmt = as_a <gswitch *> (stmt);
905 gimple_switch_set_index
906 (switch_stmt, CASE_LOW (gimple_switch_label (switch_stmt, 1)));
907 update_stmt (stmt);
909 else
911 unlink_stmt_vdef (stmt);
912 gsi_remove (&bsi, true);
913 release_defs (stmt);
914 continue;
917 gsi_next (&bsi);
921 free (bbs);
924 /* If VAL memory representation contains the same value in all bytes,
925 return that value, otherwise return -1.
926 E.g. for 0x24242424 return 0x24, for IEEE double
927 747708026454360457216.0 return 0x44, etc. */
929 static int
930 const_with_all_bytes_same (tree val)
932 unsigned char buf[64];
933 int i, len;
935 if (integer_zerop (val)
936 || (TREE_CODE (val) == CONSTRUCTOR
937 && !TREE_CLOBBER_P (val)
938 && CONSTRUCTOR_NELTS (val) == 0))
939 return 0;
941 if (real_zerop (val))
943 /* Only return 0 for +0.0, not for -0.0, which doesn't have
944 an all bytes same memory representation. Don't transform
945 -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
946 switch (TREE_CODE (val))
948 case REAL_CST:
949 if (!real_isneg (TREE_REAL_CST_PTR (val)))
950 return 0;
951 break;
952 case COMPLEX_CST:
953 if (!const_with_all_bytes_same (TREE_REALPART (val))
954 && !const_with_all_bytes_same (TREE_IMAGPART (val)))
955 return 0;
956 break;
957 case VECTOR_CST:
959 unsigned int count = vector_cst_encoded_nelts (val);
960 unsigned int j;
961 for (j = 0; j < count; ++j)
962 if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val, j)))
963 break;
964 if (j == count)
965 return 0;
966 break;
968 default:
969 break;
973 if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
974 return -1;
976 len = native_encode_expr (val, buf, sizeof (buf));
977 if (len == 0)
978 return -1;
979 for (i = 1; i < len; i++)
980 if (buf[i] != buf[0])
981 return -1;
982 return buf[0];
985 /* Generate a call to memset for PARTITION in LOOP. */
987 static void
988 generate_memset_builtin (struct loop *loop, partition *partition)
990 gimple_stmt_iterator gsi;
991 tree mem, fn, nb_bytes;
992 tree val;
993 struct builtin_info *builtin = partition->builtin;
994 gimple *fn_call;
996 /* The new statements will be placed before LOOP. */
997 gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
999 nb_bytes = builtin->size;
1000 nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1001 false, GSI_CONTINUE_LINKING);
1002 mem = builtin->dst_base;
1003 mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
1004 false, GSI_CONTINUE_LINKING);
1006 /* This exactly matches the pattern recognition in classify_partition. */
1007 val = gimple_assign_rhs1 (DR_STMT (builtin->dst_dr));
1008 /* Handle constants like 0x15151515 and similarly
1009 floating point constants etc. where all bytes are the same. */
1010 int bytev = const_with_all_bytes_same (val);
1011 if (bytev != -1)
1012 val = build_int_cst (integer_type_node, bytev);
1013 else if (TREE_CODE (val) == INTEGER_CST)
1014 val = fold_convert (integer_type_node, val);
1015 else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
1017 tree tem = make_ssa_name (integer_type_node);
1018 gimple *cstmt = gimple_build_assign (tem, NOP_EXPR, val);
1019 gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
1020 val = tem;
1023 fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
1024 fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
1025 gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1027 if (dump_file && (dump_flags & TDF_DETAILS))
1029 fprintf (dump_file, "generated memset");
1030 if (bytev == 0)
1031 fprintf (dump_file, " zero\n");
1032 else
1033 fprintf (dump_file, "\n");
1037 /* Generate a call to memcpy for PARTITION in LOOP. */
1039 static void
1040 generate_memcpy_builtin (struct loop *loop, partition *partition)
1042 gimple_stmt_iterator gsi;
1043 gimple *fn_call;
1044 tree dest, src, fn, nb_bytes;
1045 enum built_in_function kind;
1046 struct builtin_info *builtin = partition->builtin;
1048 /* The new statements will be placed before LOOP. */
1049 gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1051 nb_bytes = builtin->size;
1052 nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1053 false, GSI_CONTINUE_LINKING);
1054 dest = builtin->dst_base;
1055 src = builtin->src_base;
1056 if (partition->kind == PKIND_MEMCPY
1057 || ! ptr_derefs_may_alias_p (dest, src))
1058 kind = BUILT_IN_MEMCPY;
1059 else
1060 kind = BUILT_IN_MEMMOVE;
1062 dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
1063 false, GSI_CONTINUE_LINKING);
1064 src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
1065 false, GSI_CONTINUE_LINKING);
1066 fn = build_fold_addr_expr (builtin_decl_implicit (kind));
1067 fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
1068 gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1072 if (kind == BUILT_IN_MEMCPY)
1073 fprintf (dump_file, "generated memcpy\n");
1074 else
1075 fprintf (dump_file, "generated memmove\n");
1079 /* Remove and destroy the loop LOOP. */
1081 static void
1082 destroy_loop (struct loop *loop)
1084 unsigned nbbs = loop->num_nodes;
1085 edge exit = single_exit (loop);
1086 basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
1087 basic_block *bbs;
1088 unsigned i;
1090 bbs = get_loop_body_in_dom_order (loop);
1092 redirect_edge_pred (exit, src);
1093 exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
1094 exit->flags |= EDGE_FALLTHRU;
1095 cancel_loop_tree (loop);
1096 rescan_loop_exit (exit, false, true);
1098 i = nbbs;
1101 /* We have made sure to not leave any dangling uses of SSA
1102 names defined in the loop. With the exception of virtuals.
1103 Make sure we replace all uses of virtual defs that will remain
1104 outside of the loop with the bare symbol as delete_basic_block
1105 will release them. */
1106 --i;
1107 for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi);
1108 gsi_next (&gsi))
1110 gphi *phi = gsi.phi ();
1111 if (virtual_operand_p (gimple_phi_result (phi)))
1112 mark_virtual_phi_result_for_renaming (phi);
1114 for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
1115 gsi_next (&gsi))
1117 gimple *stmt = gsi_stmt (gsi);
1118 tree vdef = gimple_vdef (stmt);
1119 if (vdef && TREE_CODE (vdef) == SSA_NAME)
1120 mark_virtual_operand_for_renaming (vdef);
1122 delete_basic_block (bbs[i]);
1124 while (i != 0);
1126 free (bbs);
1128 set_immediate_dominator (CDI_DOMINATORS, dest,
1129 recompute_dominator (CDI_DOMINATORS, dest));
1132 /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1134 static bool
1135 generate_code_for_partition (struct loop *loop,
1136 partition *partition, bool copy_p)
1138 switch (partition->kind)
1140 case PKIND_NORMAL:
1141 case PKIND_PARTIAL_MEMSET:
1142 /* Reductions all have to be in the last partition. */
1143 gcc_assert (!partition_reduction_p (partition)
1144 || !copy_p);
1145 generate_loops_for_partition (loop, partition, copy_p);
1146 return false;
1148 case PKIND_MEMSET:
1149 generate_memset_builtin (loop, partition);
1150 break;
1152 case PKIND_MEMCPY:
1153 case PKIND_MEMMOVE:
1154 generate_memcpy_builtin (loop, partition);
1155 break;
1157 default:
1158 gcc_unreachable ();
1161 /* Common tail for partitions we turn into a call. If this was the last
1162 partition for which we generate code, we have to destroy the loop. */
1163 if (!copy_p)
1164 return true;
1165 return false;
1168 /* Return data dependence relation for data references A and B. The two
1169 data references must be in lexicographic order wrto reduced dependence
1170 graph RDG. We firstly try to find ddr from global ddr hash table. If
1171 it doesn't exist, compute the ddr and cache it. */
1173 static data_dependence_relation *
1174 get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)
1176 struct data_dependence_relation ent, **slot;
1177 struct data_dependence_relation *ddr;
1179 gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
1180 gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
1181 <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
1182 ent.a = a;
1183 ent.b = b;
1184 slot = ddrs_table->find_slot (&ent, INSERT);
1185 if (*slot == NULL)
1187 ddr = initialize_data_dependence_relation (a, b, loop_nest);
1188 compute_affine_dependence (ddr, loop_nest[0]);
1189 *slot = ddr;
1192 return *slot;
1195 /* In reduced dependence graph RDG for loop distribution, return true if
1196 dependence between references DR1 and DR2 leads to a dependence cycle
1197 and such dependence cycle can't be resolved by runtime alias check. */
1199 static bool
1200 data_dep_in_cycle_p (struct graph *rdg,
1201 data_reference_p dr1, data_reference_p dr2)
1203 struct data_dependence_relation *ddr;
1205 /* Re-shuffle data-refs to be in topological order. */
1206 if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1207 > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1208 std::swap (dr1, dr2);
1210 ddr = get_data_dependence (rdg, dr1, dr2);
1212 /* In case of no data dependence. */
1213 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1214 return false;
1215 /* For unknown data dependence or known data dependence which can't be
1216 expressed in classic distance vector, we check if it can be resolved
1217 by runtime alias check. If yes, we still consider data dependence
1218 as won't introduce data dependence cycle. */
1219 else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1220 || DDR_NUM_DIST_VECTS (ddr) == 0)
1221 return !runtime_alias_check_p (ddr, NULL, true);
1222 else if (DDR_NUM_DIST_VECTS (ddr) > 1)
1223 return true;
1224 else if (DDR_REVERSED_P (ddr)
1225 || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
1226 return false;
1228 return true;
1231 /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
1232 PARTITION1's type after merging PARTITION2 into PARTITION1. */
1234 static void
1235 update_type_for_merge (struct graph *rdg,
1236 partition *partition1, partition *partition2)
1238 unsigned i, j;
1239 bitmap_iterator bi, bj;
1240 data_reference_p dr1, dr2;
1242 EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1244 unsigned start = (partition1 == partition2) ? i + 1 : 0;
1246 dr1 = datarefs_vec[i];
1247 EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj)
1249 dr2 = datarefs_vec[j];
1250 if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
1251 continue;
1253 /* Partition can only be executed sequentially if there is any
1254 data dependence cycle. */
1255 if (data_dep_in_cycle_p (rdg, dr1, dr2))
1257 partition1->type = PTYPE_SEQUENTIAL;
1258 return;
1264 /* Returns a partition with all the statements needed for computing
1265 the vertex V of the RDG, also including the loop exit conditions. */
1267 static partition *
1268 build_rdg_partition_for_vertex (struct graph *rdg, int v)
1270 partition *partition = partition_alloc ();
1271 auto_vec<int, 3> nodes;
1272 unsigned i, j;
1273 int x;
1274 data_reference_p dr;
1276 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
1278 FOR_EACH_VEC_ELT (nodes, i, x)
1280 bitmap_set_bit (partition->stmts, x);
1282 for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j)
1284 unsigned idx = (unsigned) DR_INDEX (dr);
1285 gcc_assert (idx < datarefs_vec.length ());
1287 /* Partition can only be executed sequentially if there is any
1288 unknown data reference. */
1289 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
1290 || !DR_INIT (dr) || !DR_STEP (dr))
1291 partition->type = PTYPE_SEQUENTIAL;
1293 bitmap_set_bit (partition->datarefs, idx);
1297 if (partition->type == PTYPE_SEQUENTIAL)
1298 return partition;
1300 /* Further check if any data dependence prevents us from executing the
1301 partition parallelly. */
1302 update_type_for_merge (rdg, partition, partition);
1304 return partition;
1307 /* Given PARTITION of LOOP and RDG, record single load/store data references
1308 for builtin partition in SRC_DR/DST_DR, return false if there is no such
1309 data references. */
1311 static bool
1312 find_single_drs (struct loop *loop, struct graph *rdg, partition *partition,
1313 data_reference_p *dst_dr, data_reference_p *src_dr)
1315 unsigned i;
1316 data_reference_p single_ld = NULL, single_st = NULL;
1317 bitmap_iterator bi;
1319 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1321 gimple *stmt = RDG_STMT (rdg, i);
1322 data_reference_p dr;
1324 if (gimple_code (stmt) == GIMPLE_PHI)
1325 continue;
1327 /* Any scalar stmts are ok. */
1328 if (!gimple_vuse (stmt))
1329 continue;
1331 /* Otherwise just regular loads/stores. */
1332 if (!gimple_assign_single_p (stmt))
1333 return false;
1335 /* But exactly one store and/or load. */
1336 for (unsigned j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j)
1338 tree type = TREE_TYPE (DR_REF (dr));
1340 /* The memset, memcpy and memmove library calls are only
1341 able to deal with generic address space. */
1342 if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type)))
1343 return false;
1345 if (DR_IS_READ (dr))
1347 if (single_ld != NULL)
1348 return false;
1349 single_ld = dr;
1351 else
1353 if (single_st != NULL)
1354 return false;
1355 single_st = dr;
1360 if (!single_st)
1361 return false;
1363 /* Bail out if this is a bitfield memory reference. */
1364 if (TREE_CODE (DR_REF (single_st)) == COMPONENT_REF
1365 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1)))
1366 return false;
1368 /* Data reference must be executed exactly once per iteration of each
1369 loop in the loop nest. We only need to check dominance information
1370 against the outermost one in a perfect loop nest because a bb can't
1371 dominate outermost loop's latch without dominating inner loop's. */
1372 basic_block bb_st = gimple_bb (DR_STMT (single_st));
1373 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st))
1374 return false;
1376 if (single_ld)
1378 gimple *store = DR_STMT (single_st), *load = DR_STMT (single_ld);
1379 /* Direct aggregate copy or via an SSA name temporary. */
1380 if (load != store
1381 && gimple_assign_lhs (load) != gimple_assign_rhs1 (store))
1382 return false;
1384 /* Bail out if this is a bitfield memory reference. */
1385 if (TREE_CODE (DR_REF (single_ld)) == COMPONENT_REF
1386 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld), 1)))
1387 return false;
1389 /* Load and store must be in the same loop nest. */
1390 basic_block bb_ld = gimple_bb (DR_STMT (single_ld));
1391 if (bb_st->loop_father != bb_ld->loop_father)
1392 return false;
1394 /* Data reference must be executed exactly once per iteration.
1395 Same as single_st, we only need to check against the outermost
1396 loop. */
1397 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld))
1398 return false;
1400 edge e = single_exit (bb_st->loop_father);
1401 bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld);
1402 bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st);
1403 if (dom_ld != dom_st)
1404 return false;
1407 *src_dr = single_ld;
1408 *dst_dr = single_st;
1409 return true;
1412 /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1413 loops from inner to outer to see if loop's step equals to access size at
1414 each level of loop. Return 2 if we can prove this at all level loops;
1415 record access base and size in BASE and SIZE; save loop's step at each
1416 level of loop in STEPS if it is not null. For example:
1418 int arr[100][100][100];
1419 for (i = 0; i < 100; i++) ;steps[2] = 40000
1420 for (j = 100; j > 0; j--) ;steps[1] = -400
1421 for (k = 0; k < 100; k++) ;steps[0] = 4
1422 arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1424 Return 1 if we can prove the equality at the innermost loop, but not all
1425 level loops. In this case, no information is recorded.
1427 Return 0 if no equality can be proven at any level loops. */
1429 static int
1430 compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
1431 tree *size, vec<tree> *steps = NULL)
1433 location_t loc = gimple_location (DR_STMT (dr));
1434 basic_block bb = gimple_bb (DR_STMT (dr));
1435 struct loop *loop = bb->loop_father;
1436 tree ref = DR_REF (dr);
1437 tree access_base = build_fold_addr_expr (ref);
1438 tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1439 int res = 0;
1441 do {
1442 tree scev_fn = analyze_scalar_evolution (loop, access_base);
1443 if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
1444 return res;
1446 access_base = CHREC_LEFT (scev_fn);
1447 if (tree_contains_chrecs (access_base, NULL))
1448 return res;
1450 tree scev_step = CHREC_RIGHT (scev_fn);
1451 /* Only support constant steps. */
1452 if (TREE_CODE (scev_step) != INTEGER_CST)
1453 return res;
1455 enum ev_direction access_dir = scev_direction (scev_fn);
1456 if (access_dir == EV_DIR_UNKNOWN)
1457 return res;
1459 if (steps != NULL)
1460 steps->safe_push (scev_step);
1462 scev_step = fold_convert_loc (loc, sizetype, scev_step);
1463 /* Compute absolute value of scev step. */
1464 if (access_dir == EV_DIR_DECREASES)
1465 scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
1467 /* At each level of loop, scev step must equal to access size. In other
1468 words, DR must access consecutive memory between loop iterations. */
1469 if (!operand_equal_p (scev_step, access_size, 0))
1470 return res;
1472 /* Access stride can be computed for data reference at least for the
1473 innermost loop. */
1474 res = 1;
1476 /* Compute DR's execution times in loop. */
1477 tree niters = number_of_latch_executions (loop);
1478 niters = fold_convert_loc (loc, sizetype, niters);
1479 if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
1480 niters = size_binop_loc (loc, PLUS_EXPR, niters, size_one_node);
1482 /* Compute DR's overall access size in loop. */
1483 access_size = fold_build2_loc (loc, MULT_EXPR, sizetype,
1484 niters, scev_step);
1485 /* Adjust base address in case of negative step. */
1486 if (access_dir == EV_DIR_DECREASES)
1488 tree adj = fold_build2_loc (loc, MINUS_EXPR, sizetype,
1489 scev_step, access_size);
1490 access_base = fold_build_pointer_plus_loc (loc, access_base, adj);
1492 } while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
1494 *base = access_base;
1495 *size = access_size;
1496 /* Access stride can be computed for data reference at each level loop. */
1497 return 2;
1500 /* Allocate and return builtin struct. Record information like DST_DR,
1501 SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1503 static struct builtin_info *
1504 alloc_builtin (data_reference_p dst_dr, data_reference_p src_dr,
1505 tree dst_base, tree src_base, tree size)
1507 struct builtin_info *builtin = XNEW (struct builtin_info);
1508 builtin->dst_dr = dst_dr;
1509 builtin->src_dr = src_dr;
1510 builtin->dst_base = dst_base;
1511 builtin->src_base = src_base;
1512 builtin->size = size;
1513 return builtin;
1516 /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1517 memset call. */
1519 static void
1520 classify_builtin_st (loop_p loop, partition *partition, data_reference_p dr)
1522 gimple *stmt = DR_STMT (dr);
1523 tree base, size, rhs = gimple_assign_rhs1 (stmt);
1525 if (const_with_all_bytes_same (rhs) == -1
1526 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
1527 || (TYPE_MODE (TREE_TYPE (rhs))
1528 != TYPE_MODE (unsigned_char_type_node))))
1529 return;
1531 if (TREE_CODE (rhs) == SSA_NAME
1532 && !SSA_NAME_IS_DEFAULT_DEF (rhs)
1533 && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
1534 return;
1536 int res = compute_access_range (loop, dr, &base, &size);
1537 if (res == 0)
1538 return;
1539 if (res == 1)
1541 partition->kind = PKIND_PARTIAL_MEMSET;
1542 return;
1545 poly_uint64 base_offset;
1546 unsigned HOST_WIDE_INT const_base_offset;
1547 tree base_base = strip_offset (base, &base_offset);
1548 if (!base_offset.is_constant (&const_base_offset))
1549 return;
1551 struct builtin_info *builtin;
1552 builtin = alloc_builtin (dr, NULL, base, NULL_TREE, size);
1553 builtin->dst_base_base = base_base;
1554 builtin->dst_base_offset = const_base_offset;
1555 partition->builtin = builtin;
1556 partition->kind = PKIND_MEMSET;
1559 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1560 if it forms builtin memcpy or memmove call. */
1562 static void
1563 classify_builtin_ldst (loop_p loop, struct graph *rdg, partition *partition,
1564 data_reference_p dst_dr, data_reference_p src_dr)
1566 tree base, size, src_base, src_size;
1567 auto_vec<tree> dst_steps, src_steps;
1569 /* Compute access range of both load and store. */
1570 int res = compute_access_range (loop, dst_dr, &base, &size, &dst_steps);
1571 if (res != 2)
1572 return;
1573 res = compute_access_range (loop, src_dr, &src_base, &src_size, &src_steps);
1574 if (res != 2)
1575 return;
1577 /* They much have the same access size. */
1578 if (!operand_equal_p (size, src_size, 0))
1579 return;
1581 /* Load and store in loop nest must access memory in the same way, i.e,
1582 their must have the same steps in each loop of the nest. */
1583 if (dst_steps.length () != src_steps.length ())
1584 return;
1585 for (unsigned i = 0; i < dst_steps.length (); ++i)
1586 if (!operand_equal_p (dst_steps[i], src_steps[i], 0))
1587 return;
1589 /* Now check that if there is a dependence. */
1590 ddr_p ddr = get_data_dependence (rdg, src_dr, dst_dr);
1592 /* Classify as memcpy if no dependence between load and store. */
1593 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1595 partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1596 partition->kind = PKIND_MEMCPY;
1597 return;
1600 /* Can't do memmove in case of unknown dependence or dependence without
1601 classical distance vector. */
1602 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1603 || DDR_NUM_DIST_VECTS (ddr) == 0)
1604 return;
1606 unsigned i;
1607 lambda_vector dist_v;
1608 int num_lev = (DDR_LOOP_NEST (ddr)).length ();
1609 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
1611 unsigned dep_lev = dependence_level (dist_v, num_lev);
1612 /* Can't do memmove if load depends on store. */
1613 if (dep_lev > 0 && dist_v[dep_lev - 1] > 0 && !DDR_REVERSED_P (ddr))
1614 return;
1617 partition->builtin = alloc_builtin (dst_dr, src_dr, base, src_base, size);
1618 partition->kind = PKIND_MEMMOVE;
1619 return;
1622 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
1623 For the moment we detect memset, memcpy and memmove patterns. Bitmap
1624 STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions. */
1626 static void
1627 classify_partition (loop_p loop, struct graph *rdg, partition *partition,
1628 bitmap stmt_in_all_partitions)
1630 bitmap_iterator bi;
1631 unsigned i;
1632 data_reference_p single_ld = NULL, single_st = NULL;
1633 bool volatiles_p = false, has_reduction = false;
1635 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1637 gimple *stmt = RDG_STMT (rdg, i);
1639 if (gimple_has_volatile_ops (stmt))
1640 volatiles_p = true;
1642 /* If the stmt is not included by all partitions and there is uses
1643 outside of the loop, then mark the partition as reduction. */
1644 if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
1646 /* Due to limitation in the transform phase we have to fuse all
1647 reduction partitions. As a result, this could cancel valid
1648 loop distribution especially for loop that induction variable
1649 is used outside of loop. To workaround this issue, we skip
1650 marking partition as reudction if the reduction stmt belongs
1651 to all partitions. In such case, reduction will be computed
1652 correctly no matter how partitions are fused/distributed. */
1653 if (!bitmap_bit_p (stmt_in_all_partitions, i))
1655 partition->reduction_p = true;
1656 return;
1658 has_reduction = true;
1662 /* Perform general partition disqualification for builtins. */
1663 if (volatiles_p
1664 /* Simple workaround to prevent classifying the partition as builtin
1665 if it contains any use outside of loop. */
1666 || has_reduction
1667 || !flag_tree_loop_distribute_patterns)
1668 return;
1670 /* Find single load/store data references for builtin partition. */
1671 if (!find_single_drs (loop, rdg, partition, &single_st, &single_ld))
1672 return;
1674 /* Classify the builtin kind. */
1675 if (single_ld == NULL)
1676 classify_builtin_st (loop, partition, single_st);
1677 else
1678 classify_builtin_ldst (loop, rdg, partition, single_st, single_ld);
1681 /* Returns true when PARTITION1 and PARTITION2 access the same memory
1682 object in RDG. */
1684 static bool
1685 share_memory_accesses (struct graph *rdg,
1686 partition *partition1, partition *partition2)
1688 unsigned i, j;
1689 bitmap_iterator bi, bj;
1690 data_reference_p dr1, dr2;
1692 /* First check whether in the intersection of the two partitions are
1693 any loads or stores. Common loads are the situation that happens
1694 most often. */
1695 EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
1696 if (RDG_MEM_WRITE_STMT (rdg, i)
1697 || RDG_MEM_READS_STMT (rdg, i))
1698 return true;
1700 /* Then check whether the two partitions access the same memory object. */
1701 EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1703 dr1 = datarefs_vec[i];
1705 if (!DR_BASE_ADDRESS (dr1)
1706 || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1))
1707 continue;
1709 EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj)
1711 dr2 = datarefs_vec[j];
1713 if (!DR_BASE_ADDRESS (dr2)
1714 || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2))
1715 continue;
1717 if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0)
1718 && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0)
1719 && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0)
1720 && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0))
1721 return true;
1725 return false;
1728 /* For each seed statement in STARTING_STMTS, this function builds
1729 partition for it by adding depended statements according to RDG.
1730 All partitions are recorded in PARTITIONS. */
1732 static void
1733 rdg_build_partitions (struct graph *rdg,
1734 vec<gimple *> starting_stmts,
1735 vec<partition *> *partitions)
1737 auto_bitmap processed;
1738 int i;
1739 gimple *stmt;
1741 FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
1743 int v = rdg_vertex_for_stmt (rdg, stmt);
1745 if (dump_file && (dump_flags & TDF_DETAILS))
1746 fprintf (dump_file,
1747 "ldist asked to generate code for vertex %d\n", v);
1749 /* If the vertex is already contained in another partition so
1750 is the partition rooted at it. */
1751 if (bitmap_bit_p (processed, v))
1752 continue;
1754 partition *partition = build_rdg_partition_for_vertex (rdg, v);
1755 bitmap_ior_into (processed, partition->stmts);
1757 if (dump_file && (dump_flags & TDF_DETAILS))
1759 fprintf (dump_file, "ldist creates useful %s partition:\n",
1760 partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
1761 bitmap_print (dump_file, partition->stmts, " ", "\n");
1764 partitions->safe_push (partition);
1767 /* All vertices should have been assigned to at least one partition now,
1768 other than vertices belonging to dead code. */
1771 /* Dump to FILE the PARTITIONS. */
1773 static void
1774 dump_rdg_partitions (FILE *file, vec<partition *> partitions)
1776 int i;
1777 partition *partition;
1779 FOR_EACH_VEC_ELT (partitions, i, partition)
1780 debug_bitmap_file (file, partition->stmts);
1783 /* Debug PARTITIONS. */
1784 extern void debug_rdg_partitions (vec<partition *> );
1786 DEBUG_FUNCTION void
1787 debug_rdg_partitions (vec<partition *> partitions)
1789 dump_rdg_partitions (stderr, partitions);
1792 /* Returns the number of read and write operations in the RDG. */
1794 static int
1795 number_of_rw_in_rdg (struct graph *rdg)
1797 int i, res = 0;
1799 for (i = 0; i < rdg->n_vertices; i++)
1801 if (RDG_MEM_WRITE_STMT (rdg, i))
1802 ++res;
1804 if (RDG_MEM_READS_STMT (rdg, i))
1805 ++res;
1808 return res;
1811 /* Returns the number of read and write operations in a PARTITION of
1812 the RDG. */
1814 static int
1815 number_of_rw_in_partition (struct graph *rdg, partition *partition)
1817 int res = 0;
1818 unsigned i;
1819 bitmap_iterator ii;
1821 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
1823 if (RDG_MEM_WRITE_STMT (rdg, i))
1824 ++res;
1826 if (RDG_MEM_READS_STMT (rdg, i))
1827 ++res;
1830 return res;
1833 /* Returns true when one of the PARTITIONS contains all the read or
1834 write operations of RDG. */
1836 static bool
1837 partition_contains_all_rw (struct graph *rdg,
1838 vec<partition *> partitions)
1840 int i;
1841 partition *partition;
1842 int nrw = number_of_rw_in_rdg (rdg);
1844 FOR_EACH_VEC_ELT (partitions, i, partition)
1845 if (nrw == number_of_rw_in_partition (rdg, partition))
1846 return true;
1848 return false;
1851 /* Compute partition dependence created by the data references in DRS1
1852 and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
1853 not NULL, we record dependence introduced by possible alias between
1854 two data references in ALIAS_DDRS; otherwise, we simply ignore such
1855 dependence as if it doesn't exist at all. */
1857 static int
1858 pg_add_dependence_edges (struct graph *rdg, int dir,
1859 bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs)
1861 unsigned i, j;
1862 bitmap_iterator bi, bj;
1863 data_reference_p dr1, dr2, saved_dr1;
1865 /* dependence direction - 0 is no dependence, -1 is back,
1866 1 is forth, 2 is both (we can stop then, merging will occur). */
1867 EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi)
1869 dr1 = datarefs_vec[i];
1871 EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj)
1873 int res, this_dir = 1;
1874 ddr_p ddr;
1876 dr2 = datarefs_vec[j];
1878 /* Skip all <read, read> data dependence. */
1879 if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
1880 continue;
1882 saved_dr1 = dr1;
1883 /* Re-shuffle data-refs to be in topological order. */
1884 if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1885 > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1887 std::swap (dr1, dr2);
1888 this_dir = -this_dir;
1890 ddr = get_data_dependence (rdg, dr1, dr2);
1891 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1893 this_dir = 0;
1894 res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1),
1895 DR_BASE_ADDRESS (dr2));
1896 /* Be conservative. If data references are not well analyzed,
1897 or the two data references have the same base address and
1898 offset, add dependence and consider it alias to each other.
1899 In other words, the dependence can not be resolved by
1900 runtime alias check. */
1901 if (!DR_BASE_ADDRESS (dr1) || !DR_BASE_ADDRESS (dr2)
1902 || !DR_OFFSET (dr1) || !DR_OFFSET (dr2)
1903 || !DR_INIT (dr1) || !DR_INIT (dr2)
1904 || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
1905 || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
1906 || res == 0)
1907 this_dir = 2;
1908 /* Data dependence could be resolved by runtime alias check,
1909 record it in ALIAS_DDRS. */
1910 else if (alias_ddrs != NULL)
1911 alias_ddrs->safe_push (ddr);
1912 /* Or simply ignore it. */
1914 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1916 if (DDR_REVERSED_P (ddr))
1917 this_dir = -this_dir;
1919 /* Known dependences can still be unordered througout the
1920 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1921 if (DDR_NUM_DIST_VECTS (ddr) != 1)
1922 this_dir = 2;
1923 /* If the overlap is exact preserve stmt order. */
1924 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
1926 /* Else as the distance vector is lexicographic positive swap
1927 the dependence direction. */
1928 else
1929 this_dir = -this_dir;
1931 else
1932 this_dir = 0;
1933 if (this_dir == 2)
1934 return 2;
1935 else if (dir == 0)
1936 dir = this_dir;
1937 else if (this_dir != 0 && dir != this_dir)
1938 return 2;
1939 /* Shuffle "back" dr1. */
1940 dr1 = saved_dr1;
1943 return dir;
1946 /* Compare postorder number of the partition graph vertices V1 and V2. */
1948 static int
1949 pgcmp (const void *v1_, const void *v2_)
1951 const vertex *v1 = (const vertex *)v1_;
1952 const vertex *v2 = (const vertex *)v2_;
1953 return v2->post - v1->post;
1956 /* Data attached to vertices of partition dependence graph. */
1957 struct pg_vdata
1959 /* ID of the corresponding partition. */
1960 int id;
1961 /* The partition. */
1962 struct partition *partition;
1965 /* Data attached to edges of partition dependence graph. */
1966 struct pg_edata
1968 /* If the dependence edge can be resolved by runtime alias check,
1969 this vector contains data dependence relations for runtime alias
1970 check. On the other hand, if the dependence edge is introduced
1971 because of compilation time known data dependence, this vector
1972 contains nothing. */
1973 vec<ddr_p> alias_ddrs;
1976 /* Callback data for traversing edges in graph. */
1977 struct pg_edge_callback_data
1979 /* Bitmap contains strong connected components should be merged. */
1980 bitmap sccs_to_merge;
1981 /* Array constains component information for all vertices. */
1982 int *vertices_component;
1983 /* Vector to record all data dependence relations which are needed
1984 to break strong connected components by runtime alias checks. */
1985 vec<ddr_p> *alias_ddrs;
1988 /* Initialize vertice's data for partition dependence graph PG with
1989 PARTITIONS. */
1991 static void
1992 init_partition_graph_vertices (struct graph *pg,
1993 vec<struct partition *> *partitions)
1995 int i;
1996 partition *partition;
1997 struct pg_vdata *data;
1999 for (i = 0; partitions->iterate (i, &partition); ++i)
2001 data = new pg_vdata;
2002 pg->vertices[i].data = data;
2003 data->id = i;
2004 data->partition = partition;
2008 /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2009 dependence relations to the EDGE if DDRS isn't NULL. */
2011 static void
2012 add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs)
2014 struct graph_edge *e = add_edge (pg, i, j);
2016 /* If the edge is attached with data dependence relations, it means this
2017 dependence edge can be resolved by runtime alias checks. */
2018 if (ddrs != NULL)
2020 struct pg_edata *data = new pg_edata;
2022 gcc_assert (ddrs->length () > 0);
2023 e->data = data;
2024 data->alias_ddrs = vNULL;
2025 data->alias_ddrs.safe_splice (*ddrs);
2029 /* Callback function for graph travesal algorithm. It returns true
2030 if edge E should skipped when traversing the graph. */
2032 static bool
2033 pg_skip_alias_edge (struct graph_edge *e)
2035 struct pg_edata *data = (struct pg_edata *)e->data;
2036 return (data != NULL && data->alias_ddrs.length () > 0);
2039 /* Callback function freeing data attached to edge E of graph. */
2041 static void
2042 free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *)
2044 if (e->data != NULL)
2046 struct pg_edata *data = (struct pg_edata *)e->data;
2047 data->alias_ddrs.release ();
2048 delete data;
2052 /* Free data attached to vertice of partition dependence graph PG. */
2054 static void
2055 free_partition_graph_vdata (struct graph *pg)
2057 int i;
2058 struct pg_vdata *data;
2060 for (i = 0; i < pg->n_vertices; ++i)
2062 data = (struct pg_vdata *)pg->vertices[i].data;
2063 delete data;
2067 /* Build and return partition dependence graph for PARTITIONS. RDG is
2068 reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2069 is true, data dependence caused by possible alias between references
2070 is ignored, as if it doesn't exist at all; otherwise all depdendences
2071 are considered. */
2073 static struct graph *
2074 build_partition_graph (struct graph *rdg,
2075 vec<struct partition *> *partitions,
2076 bool ignore_alias_p)
2078 int i, j;
2079 struct partition *partition1, *partition2;
2080 graph *pg = new_graph (partitions->length ());
2081 auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p;
2083 alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs;
2085 init_partition_graph_vertices (pg, partitions);
2087 for (i = 0; partitions->iterate (i, &partition1); ++i)
2089 for (j = i + 1; partitions->iterate (j, &partition2); ++j)
2091 /* dependence direction - 0 is no dependence, -1 is back,
2092 1 is forth, 2 is both (we can stop then, merging will occur). */
2093 int dir = 0;
2095 /* If the first partition has reduction, add back edge; if the
2096 second partition has reduction, add forth edge. This makes
2097 sure that reduction partition will be sorted as the last one. */
2098 if (partition_reduction_p (partition1))
2099 dir = -1;
2100 else if (partition_reduction_p (partition2))
2101 dir = 1;
2103 /* Cleanup the temporary vector. */
2104 alias_ddrs.truncate (0);
2106 dir = pg_add_dependence_edges (rdg, dir, partition1->datarefs,
2107 partition2->datarefs, alias_ddrs_p);
2109 /* Add edge to partition graph if there exists dependence. There
2110 are two types of edges. One type edge is caused by compilation
2111 time known dependence, this type can not be resolved by runtime
2112 alias check. The other type can be resolved by runtime alias
2113 check. */
2114 if (dir == 1 || dir == 2
2115 || alias_ddrs.length () > 0)
2117 /* Attach data dependence relations to edge that can be resolved
2118 by runtime alias check. */
2119 bool alias_edge_p = (dir != 1 && dir != 2);
2120 add_partition_graph_edge (pg, i, j,
2121 (alias_edge_p) ? &alias_ddrs : NULL);
2123 if (dir == -1 || dir == 2
2124 || alias_ddrs.length () > 0)
2126 /* Attach data dependence relations to edge that can be resolved
2127 by runtime alias check. */
2128 bool alias_edge_p = (dir != -1 && dir != 2);
2129 add_partition_graph_edge (pg, j, i,
2130 (alias_edge_p) ? &alias_ddrs : NULL);
2134 return pg;
2137 /* Sort partitions in PG in descending post order and store them in
2138 PARTITIONS. */
2140 static void
2141 sort_partitions_by_post_order (struct graph *pg,
2142 vec<struct partition *> *partitions)
2144 int i;
2145 struct pg_vdata *data;
2147 /* Now order the remaining nodes in descending postorder. */
2148 qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
2149 partitions->truncate (0);
2150 for (i = 0; i < pg->n_vertices; ++i)
2152 data = (struct pg_vdata *)pg->vertices[i].data;
2153 if (data->partition)
2154 partitions->safe_push (data->partition);
2158 /* Given reduced dependence graph RDG merge strong connected components
2159 of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
2160 possible alias between references is ignored, as if it doesn't exist
2161 at all; otherwise all depdendences are considered. */
2163 static void
2164 merge_dep_scc_partitions (struct graph *rdg,
2165 vec<struct partition *> *partitions,
2166 bool ignore_alias_p)
2168 struct partition *partition1, *partition2;
2169 struct pg_vdata *data;
2170 graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p);
2171 int i, j, num_sccs = graphds_scc (pg, NULL);
2173 /* Strong connected compoenent means dependence cycle, we cannot distribute
2174 them. So fuse them together. */
2175 if ((unsigned) num_sccs < partitions->length ())
2177 for (i = 0; i < num_sccs; ++i)
2179 for (j = 0; partitions->iterate (j, &partition1); ++j)
2180 if (pg->vertices[j].component == i)
2181 break;
2182 for (j = j + 1; partitions->iterate (j, &partition2); ++j)
2183 if (pg->vertices[j].component == i)
2185 partition_merge_into (NULL, partition1,
2186 partition2, FUSE_SAME_SCC);
2187 partition1->type = PTYPE_SEQUENTIAL;
2188 (*partitions)[j] = NULL;
2189 partition_free (partition2);
2190 data = (struct pg_vdata *)pg->vertices[j].data;
2191 data->partition = NULL;
2196 sort_partitions_by_post_order (pg, partitions);
2197 gcc_assert (partitions->length () == (unsigned)num_sccs);
2198 free_partition_graph_vdata (pg);
2199 free_graph (pg);
2202 /* Callback function for traversing edge E in graph G. DATA is private
2203 callback data. */
2205 static void
2206 pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data)
2208 int i, j, component;
2209 struct pg_edge_callback_data *cbdata;
2210 struct pg_edata *edata = (struct pg_edata *) e->data;
2212 /* If the edge doesn't have attached data dependence, it represents
2213 compilation time known dependences. This type dependence cannot
2214 be resolved by runtime alias check. */
2215 if (edata == NULL || edata->alias_ddrs.length () == 0)
2216 return;
2218 cbdata = (struct pg_edge_callback_data *) data;
2219 i = e->src;
2220 j = e->dest;
2221 component = cbdata->vertices_component[i];
2222 /* Vertices are topologically sorted according to compilation time
2223 known dependences, so we can break strong connected components
2224 by removing edges of the opposite direction, i.e, edges pointing
2225 from vertice with smaller post number to vertice with bigger post
2226 number. */
2227 if (g->vertices[i].post < g->vertices[j].post
2228 /* We only need to remove edges connecting vertices in the same
2229 strong connected component to break it. */
2230 && component == cbdata->vertices_component[j]
2231 /* Check if we want to break the strong connected component or not. */
2232 && !bitmap_bit_p (cbdata->sccs_to_merge, component))
2233 cbdata->alias_ddrs->safe_splice (edata->alias_ddrs);
2236 /* This is the main function breaking strong conected components in
2237 PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2238 relations for runtime alias check in ALIAS_DDRS. */
2240 static void
2241 break_alias_scc_partitions (struct graph *rdg,
2242 vec<struct partition *> *partitions,
2243 vec<ddr_p> *alias_ddrs)
2245 int i, j, k, num_sccs, num_sccs_no_alias;
2246 /* Build partition dependence graph. */
2247 graph *pg = build_partition_graph (rdg, partitions, false);
2249 alias_ddrs->truncate (0);
2250 /* Find strong connected components in the graph, with all dependence edges
2251 considered. */
2252 num_sccs = graphds_scc (pg, NULL);
2253 /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2254 compilation time known dependences are merged before this function. */
2255 if ((unsigned) num_sccs < partitions->length ())
2257 struct pg_edge_callback_data cbdata;
2258 auto_bitmap sccs_to_merge;
2259 auto_vec<enum partition_type> scc_types;
2260 struct partition *partition, *first;
2262 /* If all partitions in a SCC have the same type, we can simply merge the
2263 SCC. This loop finds out such SCCS and record them in bitmap. */
2264 bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
2265 for (i = 0; i < num_sccs; ++i)
2267 for (j = 0; partitions->iterate (j, &first); ++j)
2268 if (pg->vertices[j].component == i)
2269 break;
2271 bool same_type = true, all_builtins = partition_builtin_p (first);
2272 for (++j; partitions->iterate (j, &partition); ++j)
2274 if (pg->vertices[j].component != i)
2275 continue;
2277 if (first->type != partition->type)
2279 same_type = false;
2280 break;
2282 all_builtins &= partition_builtin_p (partition);
2284 /* Merge SCC if all partitions in SCC have the same type, though the
2285 result partition is sequential, because vectorizer can do better
2286 runtime alias check. One expecption is all partitions in SCC are
2287 builtins. */
2288 if (!same_type || all_builtins)
2289 bitmap_clear_bit (sccs_to_merge, i);
2292 /* Initialize callback data for traversing. */
2293 cbdata.sccs_to_merge = sccs_to_merge;
2294 cbdata.alias_ddrs = alias_ddrs;
2295 cbdata.vertices_component = XNEWVEC (int, pg->n_vertices);
2296 /* Record the component information which will be corrupted by next
2297 graph scc finding call. */
2298 for (i = 0; i < pg->n_vertices; ++i)
2299 cbdata.vertices_component[i] = pg->vertices[i].component;
2301 /* Collect data dependences for runtime alias checks to break SCCs. */
2302 if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
2304 /* Run SCC finding algorithm again, with alias dependence edges
2305 skipped. This is to topologically sort partitions according to
2306 compilation time known dependence. Note the topological order
2307 is stored in the form of pg's post order number. */
2308 num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
2309 gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias);
2310 /* With topological order, we can construct two subgraphs L and R.
2311 L contains edge <x, y> where x < y in terms of post order, while
2312 R contains edge <x, y> where x > y. Edges for compilation time
2313 known dependence all fall in R, so we break SCCs by removing all
2314 (alias) edges of in subgraph L. */
2315 for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);
2318 /* For SCC that doesn't need to be broken, merge it. */
2319 for (i = 0; i < num_sccs; ++i)
2321 if (!bitmap_bit_p (sccs_to_merge, i))
2322 continue;
2324 for (j = 0; partitions->iterate (j, &first); ++j)
2325 if (cbdata.vertices_component[j] == i)
2326 break;
2327 for (k = j + 1; partitions->iterate (k, &partition); ++k)
2329 struct pg_vdata *data;
2331 if (cbdata.vertices_component[k] != i)
2332 continue;
2334 /* Update postorder number so that merged reduction partition is
2335 sorted after other partitions. */
2336 if (!partition_reduction_p (first)
2337 && partition_reduction_p (partition))
2339 gcc_assert (pg->vertices[k].post < pg->vertices[j].post);
2340 pg->vertices[j].post = pg->vertices[k].post;
2342 partition_merge_into (NULL, first, partition, FUSE_SAME_SCC);
2343 (*partitions)[k] = NULL;
2344 partition_free (partition);
2345 data = (struct pg_vdata *)pg->vertices[k].data;
2346 gcc_assert (data->id == k);
2347 data->partition = NULL;
2348 /* The result partition of merged SCC must be sequential. */
2349 first->type = PTYPE_SEQUENTIAL;
2354 sort_partitions_by_post_order (pg, partitions);
2355 free_partition_graph_vdata (pg);
2356 for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2357 free_graph (pg);
2359 if (dump_file && (dump_flags & TDF_DETAILS))
2361 fprintf (dump_file, "Possible alias data dependence to break:\n");
2362 dump_data_dependence_relations (dump_file, *alias_ddrs);
2366 /* Compute and return an expression whose value is the segment length which
2367 will be accessed by DR in NITERS iterations. */
2369 static tree
2370 data_ref_segment_size (struct data_reference *dr, tree niters)
2372 niters = size_binop (MINUS_EXPR,
2373 fold_convert (sizetype, niters),
2374 size_one_node);
2375 return size_binop (MULT_EXPR,
2376 fold_convert (sizetype, DR_STEP (dr)),
2377 fold_convert (sizetype, niters));
2380 /* Return true if LOOP's latch is dominated by statement for data reference
2381 DR. */
2383 static inline bool
2384 latch_dominated_by_data_ref (struct loop *loop, data_reference *dr)
2386 return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
2387 gimple_bb (DR_STMT (dr)));
2390 /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2391 data dependence relations ALIAS_DDRS. */
2393 static void
2394 compute_alias_check_pairs (struct loop *loop, vec<ddr_p> *alias_ddrs,
2395 vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
2397 unsigned int i;
2398 unsigned HOST_WIDE_INT factor = 1;
2399 tree niters_plus_one, niters = number_of_latch_executions (loop);
2401 gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
2402 niters = fold_convert (sizetype, niters);
2403 niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
2405 if (dump_file && (dump_flags & TDF_DETAILS))
2406 fprintf (dump_file, "Creating alias check pairs:\n");
2408 /* Iterate all data dependence relations and compute alias check pairs. */
2409 for (i = 0; i < alias_ddrs->length (); i++)
2411 ddr_p ddr = (*alias_ddrs)[i];
2412 struct data_reference *dr_a = DDR_A (ddr);
2413 struct data_reference *dr_b = DDR_B (ddr);
2414 tree seg_length_a, seg_length_b;
2415 int comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (dr_a),
2416 DR_BASE_ADDRESS (dr_b));
2418 if (comp_res == 0)
2419 comp_res = data_ref_compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b));
2420 gcc_assert (comp_res != 0);
2422 if (latch_dominated_by_data_ref (loop, dr_a))
2423 seg_length_a = data_ref_segment_size (dr_a, niters_plus_one);
2424 else
2425 seg_length_a = data_ref_segment_size (dr_a, niters);
2427 if (latch_dominated_by_data_ref (loop, dr_b))
2428 seg_length_b = data_ref_segment_size (dr_b, niters_plus_one);
2429 else
2430 seg_length_b = data_ref_segment_size (dr_b, niters);
2432 unsigned HOST_WIDE_INT access_size_a
2433 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
2434 unsigned HOST_WIDE_INT access_size_b
2435 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
2436 unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
2437 unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
2439 dr_with_seg_len_pair_t dr_with_seg_len_pair
2440 (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
2441 dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b));
2443 /* Canonicalize pairs by sorting the two DR members. */
2444 if (comp_res > 0)
2445 std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second);
2447 comp_alias_pairs->safe_push (dr_with_seg_len_pair);
2450 if (tree_fits_uhwi_p (niters))
2451 factor = tree_to_uhwi (niters);
2453 /* Prune alias check pairs. */
2454 prune_runtime_alias_test_list (comp_alias_pairs, factor);
2455 if (dump_file && (dump_flags & TDF_DETAILS))
2456 fprintf (dump_file,
2457 "Improved number of alias checks from %d to %d\n",
2458 alias_ddrs->length (), comp_alias_pairs->length ());
2461 /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2462 checks and version LOOP under condition of these runtime alias checks. */
2464 static void
2465 version_loop_by_alias_check (vec<struct partition *> *partitions,
2466 struct loop *loop, vec<ddr_p> *alias_ddrs)
2468 profile_probability prob;
2469 basic_block cond_bb;
2470 struct loop *nloop;
2471 tree lhs, arg0, cond_expr = NULL_TREE;
2472 gimple_seq cond_stmts = NULL;
2473 gimple *call_stmt = NULL;
2474 auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs;
2476 /* Generate code for runtime alias checks if necessary. */
2477 gcc_assert (alias_ddrs->length () > 0);
2479 if (dump_file && (dump_flags & TDF_DETAILS))
2480 fprintf (dump_file,
2481 "Version loop <%d> with runtime alias check\n", loop->num);
2483 compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs);
2484 create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
2485 cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
2486 is_gimple_val, NULL_TREE);
2488 /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2489 bool cancelable_p = flag_tree_loop_vectorize;
2490 if (cancelable_p)
2492 unsigned i = 0;
2493 struct partition *partition;
2494 for (; partitions->iterate (i, &partition); ++i)
2495 if (!partition_builtin_p (partition))
2496 break;
2498 /* If all partitions are builtins, distributing it would be profitable and
2499 we don't want to cancel the runtime alias checks. */
2500 if (i == partitions->length ())
2501 cancelable_p = false;
2504 /* Generate internal function call for loop distribution alias check if the
2505 runtime alias check should be cancelable. */
2506 if (cancelable_p)
2508 call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
2509 2, NULL_TREE, cond_expr);
2510 lhs = make_ssa_name (boolean_type_node);
2511 gimple_call_set_lhs (call_stmt, lhs);
2513 else
2514 lhs = cond_expr;
2516 prob = profile_probability::guessed_always ().apply_scale (9, 10);
2517 initialize_original_copy_tables ();
2518 nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (),
2519 prob, prob.invert (), true);
2520 free_original_copy_tables ();
2521 /* Record the original loop number in newly generated loops. In case of
2522 distribution, the original loop will be distributed and the new loop
2523 is kept. */
2524 loop->orig_loop_num = nloop->num;
2525 nloop->orig_loop_num = nloop->num;
2526 nloop->dont_vectorize = true;
2527 nloop->force_vectorize = false;
2529 if (call_stmt)
2531 /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2532 loop could be destroyed. */
2533 arg0 = build_int_cst (integer_type_node, loop->orig_loop_num);
2534 gimple_call_set_arg (call_stmt, 0, arg0);
2535 gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt);
2538 if (cond_stmts)
2540 gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb);
2541 gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT);
2543 update_ssa (TODO_update_ssa);
2546 /* Return true if loop versioning is needed to distrubute PARTITIONS.
2547 ALIAS_DDRS are data dependence relations for runtime alias check. */
2549 static inline bool
2550 version_for_distribution_p (vec<struct partition *> *partitions,
2551 vec<ddr_p> *alias_ddrs)
2553 /* No need to version loop if we have only one partition. */
2554 if (partitions->length () == 1)
2555 return false;
2557 /* Need to version loop if runtime alias check is necessary. */
2558 return (alias_ddrs->length () > 0);
2561 /* Compare base offset of builtin mem* partitions P1 and P2. */
2563 static int
2564 offset_cmp (const void *vp1, const void *vp2)
2566 struct partition *p1 = *(struct partition *const *) vp1;
2567 struct partition *p2 = *(struct partition *const *) vp2;
2568 unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
2569 unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
2570 return (o2 < o1) - (o1 < o2);
2573 /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2574 case optimization transforming below code:
2576 __builtin_memset (&obj, 0, 100);
2577 _1 = &obj + 100;
2578 __builtin_memset (_1, 0, 200);
2579 _2 = &obj + 300;
2580 __builtin_memset (_2, 0, 100);
2582 into:
2584 __builtin_memset (&obj, 0, 400);
2586 Note we don't have dependence information between different partitions
2587 at this point, as a result, we can't handle nonadjacent memset builtin
2588 partitions since dependence might be broken. */
2590 static void
2591 fuse_memset_builtins (vec<struct partition *> *partitions)
2593 unsigned i, j;
2594 struct partition *part1, *part2;
2595 tree rhs1, rhs2;
2597 for (i = 0; partitions->iterate (i, &part1);)
2599 if (part1->kind != PKIND_MEMSET)
2601 i++;
2602 continue;
2605 /* Find sub-array of memset builtins of the same base. Index range
2606 of the sub-array is [i, j) with "j > i". */
2607 for (j = i + 1; partitions->iterate (j, &part2); ++j)
2609 if (part2->kind != PKIND_MEMSET
2610 || !operand_equal_p (part1->builtin->dst_base_base,
2611 part2->builtin->dst_base_base, 0))
2612 break;
2614 /* Memset calls setting different values can't be merged. */
2615 rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2616 rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2617 if (!operand_equal_p (rhs1, rhs2, 0))
2618 break;
2621 /* Stable sort is required in order to avoid breaking dependence. */
2622 gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
2623 offset_cmp);
2624 /* Continue with next partition. */
2625 i = j;
2628 /* Merge all consecutive memset builtin partitions. */
2629 for (i = 0; i < partitions->length () - 1;)
2631 part1 = (*partitions)[i];
2632 if (part1->kind != PKIND_MEMSET)
2634 i++;
2635 continue;
2638 part2 = (*partitions)[i + 1];
2639 /* Only merge memset partitions of the same base and with constant
2640 access sizes. */
2641 if (part2->kind != PKIND_MEMSET
2642 || TREE_CODE (part1->builtin->size) != INTEGER_CST
2643 || TREE_CODE (part2->builtin->size) != INTEGER_CST
2644 || !operand_equal_p (part1->builtin->dst_base_base,
2645 part2->builtin->dst_base_base, 0))
2647 i++;
2648 continue;
2650 rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2651 rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2652 int bytev1 = const_with_all_bytes_same (rhs1);
2653 int bytev2 = const_with_all_bytes_same (rhs2);
2654 /* Only merge memset partitions of the same value. */
2655 if (bytev1 != bytev2 || bytev1 == -1)
2657 i++;
2658 continue;
2660 wide_int end1 = wi::add (part1->builtin->dst_base_offset,
2661 wi::to_wide (part1->builtin->size));
2662 /* Only merge adjacent memset partitions. */
2663 if (wi::ne_p (end1, part2->builtin->dst_base_offset))
2665 i++;
2666 continue;
2668 /* Merge partitions[i] and partitions[i+1]. */
2669 part1->builtin->size = fold_build2 (PLUS_EXPR, sizetype,
2670 part1->builtin->size,
2671 part2->builtin->size);
2672 partition_free (part2);
2673 partitions->ordered_remove (i + 1);
2677 /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
2678 ALIAS_DDRS contains ddrs which need runtime alias check. */
2680 static void
2681 finalize_partitions (struct loop *loop, vec<struct partition *> *partitions,
2682 vec<ddr_p> *alias_ddrs)
2684 unsigned i;
2685 struct partition *partition, *a;
2687 if (partitions->length () == 1
2688 || alias_ddrs->length () > 0)
2689 return;
2691 unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
2692 bool same_type_p = true;
2693 enum partition_type type = ((*partitions)[0])->type;
2694 for (i = 0; partitions->iterate (i, &partition); ++i)
2696 same_type_p &= (type == partition->type);
2697 if (partition_builtin_p (partition))
2699 num_builtin++;
2700 continue;
2702 num_normal++;
2703 if (partition->kind == PKIND_PARTIAL_MEMSET)
2704 num_partial_memset++;
2707 /* Don't distribute current loop into too many loops given we don't have
2708 memory stream cost model. Be even more conservative in case of loop
2709 nest distribution. */
2710 if ((same_type_p && num_builtin == 0
2711 && (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
2712 || (loop->inner != NULL
2713 && i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
2714 || (loop->inner == NULL
2715 && i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
2717 a = (*partitions)[0];
2718 for (i = 1; partitions->iterate (i, &partition); ++i)
2720 partition_merge_into (NULL, a, partition, FUSE_FINALIZE);
2721 partition_free (partition);
2723 partitions->truncate (1);
2726 /* Fuse memset builtins if possible. */
2727 if (partitions->length () > 1)
2728 fuse_memset_builtins (partitions);
2731 /* Distributes the code from LOOP in such a way that producer statements
2732 are placed before consumer statements. Tries to separate only the
2733 statements from STMTS into separate loops. Returns the number of
2734 distributed loops. Set NB_CALLS to number of generated builtin calls.
2735 Set *DESTROY_P to whether LOOP needs to be destroyed. */
2737 static int
2738 distribute_loop (struct loop *loop, vec<gimple *> stmts,
2739 control_dependences *cd, int *nb_calls, bool *destroy_p)
2741 ddrs_table = new hash_table<ddr_hasher> (389);
2742 struct graph *rdg;
2743 partition *partition;
2744 bool any_builtin;
2745 int i, nbp;
2747 *destroy_p = false;
2748 *nb_calls = 0;
2749 loop_nest.create (0);
2750 if (!find_loop_nest (loop, &loop_nest))
2752 loop_nest.release ();
2753 delete ddrs_table;
2754 return 0;
2757 datarefs_vec.create (20);
2758 rdg = build_rdg (loop, cd);
2759 if (!rdg)
2761 if (dump_file && (dump_flags & TDF_DETAILS))
2762 fprintf (dump_file,
2763 "Loop %d not distributed: failed to build the RDG.\n",
2764 loop->num);
2766 loop_nest.release ();
2767 free_data_refs (datarefs_vec);
2768 delete ddrs_table;
2769 return 0;
2772 if (datarefs_vec.length () > MAX_DATAREFS_NUM)
2774 if (dump_file && (dump_flags & TDF_DETAILS))
2775 fprintf (dump_file,
2776 "Loop %d not distributed: too many memory references.\n",
2777 loop->num);
2779 free_rdg (rdg);
2780 loop_nest.release ();
2781 free_data_refs (datarefs_vec);
2782 delete ddrs_table;
2783 return 0;
2786 data_reference_p dref;
2787 for (i = 0; datarefs_vec.iterate (i, &dref); ++i)
2788 dref->aux = (void *) (uintptr_t) i;
2790 if (dump_file && (dump_flags & TDF_DETAILS))
2791 dump_rdg (dump_file, rdg);
2793 auto_vec<struct partition *, 3> partitions;
2794 rdg_build_partitions (rdg, stmts, &partitions);
2796 auto_vec<ddr_p> alias_ddrs;
2798 auto_bitmap stmt_in_all_partitions;
2799 bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts);
2800 for (i = 1; partitions.iterate (i, &partition); ++i)
2801 bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts);
2803 any_builtin = false;
2804 FOR_EACH_VEC_ELT (partitions, i, partition)
2806 classify_partition (loop, rdg, partition, stmt_in_all_partitions);
2807 any_builtin |= partition_builtin_p (partition);
2810 /* If we are only distributing patterns but did not detect any,
2811 simply bail out. */
2812 if (!flag_tree_loop_distribution
2813 && !any_builtin)
2815 nbp = 0;
2816 goto ldist_done;
2819 /* If we are only distributing patterns fuse all partitions that
2820 were not classified as builtins. This also avoids chopping
2821 a loop into pieces, separated by builtin calls. That is, we
2822 only want no or a single loop body remaining. */
2823 struct partition *into;
2824 if (!flag_tree_loop_distribution)
2826 for (i = 0; partitions.iterate (i, &into); ++i)
2827 if (!partition_builtin_p (into))
2828 break;
2829 for (++i; partitions.iterate (i, &partition); ++i)
2830 if (!partition_builtin_p (partition))
2832 partition_merge_into (NULL, into, partition, FUSE_NON_BUILTIN);
2833 partitions.unordered_remove (i);
2834 partition_free (partition);
2835 i--;
2839 /* Due to limitations in the transform phase we have to fuse all
2840 reduction partitions into the last partition so the existing
2841 loop will contain all loop-closed PHI nodes. */
2842 for (i = 0; partitions.iterate (i, &into); ++i)
2843 if (partition_reduction_p (into))
2844 break;
2845 for (i = i + 1; partitions.iterate (i, &partition); ++i)
2846 if (partition_reduction_p (partition))
2848 partition_merge_into (rdg, into, partition, FUSE_REDUCTION);
2849 partitions.unordered_remove (i);
2850 partition_free (partition);
2851 i--;
2854 /* Apply our simple cost model - fuse partitions with similar
2855 memory accesses. */
2856 for (i = 0; partitions.iterate (i, &into); ++i)
2858 bool changed = false;
2859 if (partition_builtin_p (into) || into->kind == PKIND_PARTIAL_MEMSET)
2860 continue;
2861 for (int j = i + 1;
2862 partitions.iterate (j, &partition); ++j)
2864 if (share_memory_accesses (rdg, into, partition))
2866 partition_merge_into (rdg, into, partition, FUSE_SHARE_REF);
2867 partitions.unordered_remove (j);
2868 partition_free (partition);
2869 j--;
2870 changed = true;
2873 /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
2874 accesses when 1 and 2 have similar accesses but not 0 and 1
2875 then in the next iteration we will fail to consider merging
2876 1 into 0,2. So try again if we did any merging into 0. */
2877 if (changed)
2878 i--;
2881 /* Build the partition dependency graph and fuse partitions in strong
2882 connected component. */
2883 if (partitions.length () > 1)
2885 /* Don't support loop nest distribution under runtime alias check
2886 since it's not likely to enable many vectorization opportunities. */
2887 if (loop->inner)
2888 merge_dep_scc_partitions (rdg, &partitions, false);
2889 else
2891 merge_dep_scc_partitions (rdg, &partitions, true);
2892 if (partitions.length () > 1)
2893 break_alias_scc_partitions (rdg, &partitions, &alias_ddrs);
2897 finalize_partitions (loop, &partitions, &alias_ddrs);
2899 nbp = partitions.length ();
2900 if (nbp == 0
2901 || (nbp == 1 && !partition_builtin_p (partitions[0]))
2902 || (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
2904 nbp = 0;
2905 goto ldist_done;
2908 if (version_for_distribution_p (&partitions, &alias_ddrs))
2909 version_loop_by_alias_check (&partitions, loop, &alias_ddrs);
2911 if (dump_file && (dump_flags & TDF_DETAILS))
2913 fprintf (dump_file,
2914 "distribute loop <%d> into partitions:\n", loop->num);
2915 dump_rdg_partitions (dump_file, partitions);
2918 FOR_EACH_VEC_ELT (partitions, i, partition)
2920 if (partition_builtin_p (partition))
2921 (*nb_calls)++;
2922 *destroy_p |= generate_code_for_partition (loop, partition, i < nbp - 1);
2925 ldist_done:
2926 loop_nest.release ();
2927 free_data_refs (datarefs_vec);
2928 for (hash_table<ddr_hasher>::iterator iter = ddrs_table->begin ();
2929 iter != ddrs_table->end (); ++iter)
2931 free_dependence_relation (*iter);
2932 *iter = NULL;
2934 delete ddrs_table;
2936 FOR_EACH_VEC_ELT (partitions, i, partition)
2937 partition_free (partition);
2939 free_rdg (rdg);
2940 return nbp - *nb_calls;
2943 /* Distribute all loops in the current function. */
2945 namespace {
2947 const pass_data pass_data_loop_distribution =
2949 GIMPLE_PASS, /* type */
2950 "ldist", /* name */
2951 OPTGROUP_LOOP, /* optinfo_flags */
2952 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
2953 ( PROP_cfg | PROP_ssa ), /* properties_required */
2954 0, /* properties_provided */
2955 0, /* properties_destroyed */
2956 0, /* todo_flags_start */
2957 0, /* todo_flags_finish */
2960 class pass_loop_distribution : public gimple_opt_pass
2962 public:
2963 pass_loop_distribution (gcc::context *ctxt)
2964 : gimple_opt_pass (pass_data_loop_distribution, ctxt)
2967 /* opt_pass methods: */
2968 virtual bool gate (function *)
2970 return flag_tree_loop_distribution
2971 || flag_tree_loop_distribute_patterns;
2974 virtual unsigned int execute (function *);
2976 }; // class pass_loop_distribution
2979 /* Given LOOP, this function records seed statements for distribution in
2980 WORK_LIST. Return false if there is nothing for distribution. */
2982 static bool
2983 find_seed_stmts_for_distribution (struct loop *loop, vec<gimple *> *work_list)
2985 basic_block *bbs = get_loop_body_in_dom_order (loop);
2987 /* Initialize the worklist with stmts we seed the partitions with. */
2988 for (unsigned i = 0; i < loop->num_nodes; ++i)
2990 for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
2991 !gsi_end_p (gsi); gsi_next (&gsi))
2993 gphi *phi = gsi.phi ();
2994 if (virtual_operand_p (gimple_phi_result (phi)))
2995 continue;
2996 /* Distribute stmts which have defs that are used outside of
2997 the loop. */
2998 if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
2999 continue;
3000 work_list->safe_push (phi);
3002 for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
3003 !gsi_end_p (gsi); gsi_next (&gsi))
3005 gimple *stmt = gsi_stmt (gsi);
3007 /* If there is a stmt with side-effects bail out - we
3008 cannot and should not distribute this loop. */
3009 if (gimple_has_side_effects (stmt))
3011 free (bbs);
3012 return false;
3015 /* Distribute stmts which have defs that are used outside of
3016 the loop. */
3017 if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3019 /* Otherwise only distribute stores for now. */
3020 else if (!gimple_vdef (stmt))
3021 continue;
3023 work_list->safe_push (stmt);
3026 free (bbs);
3027 return work_list->length () > 0;
3030 /* Given innermost LOOP, return the outermost enclosing loop that forms a
3031 perfect loop nest. */
3033 static struct loop *
3034 prepare_perfect_loop_nest (struct loop *loop)
3036 struct loop *outer = loop_outer (loop);
3037 tree niters = number_of_latch_executions (loop);
3039 /* TODO: We only support the innermost 3-level loop nest distribution
3040 because of compilation time issue for now. This should be relaxed
3041 in the future. Note we only allow 3-level loop nest distribution
3042 when parallelizing loops. */
3043 while ((loop->inner == NULL
3044 || (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
3045 && loop_outer (outer)
3046 && outer->inner == loop && loop->next == NULL
3047 && single_exit (outer)
3048 && optimize_loop_for_speed_p (outer)
3049 && !chrec_contains_symbols_defined_in_loop (niters, outer->num)
3050 && (niters = number_of_latch_executions (outer)) != NULL_TREE
3051 && niters != chrec_dont_know)
3053 loop = outer;
3054 outer = loop_outer (loop);
3057 return loop;
3060 unsigned int
3061 pass_loop_distribution::execute (function *fun)
3063 struct loop *loop;
3064 bool changed = false;
3065 basic_block bb;
3066 control_dependences *cd = NULL;
3067 auto_vec<loop_p> loops_to_be_destroyed;
3069 if (number_of_loops (fun) <= 1)
3070 return 0;
3072 /* Compute topological order for basic blocks. Topological order is
3073 needed because data dependence is computed for data references in
3074 lexicographical order. */
3075 if (bb_top_order_index == NULL)
3077 int rpo_num;
3078 int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
3080 bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun));
3081 bb_top_order_index_size = last_basic_block_for_fn (cfun);
3082 rpo_num = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true);
3083 for (int i = 0; i < rpo_num; i++)
3084 bb_top_order_index[rpo[i]] = i;
3086 free (rpo);
3089 FOR_ALL_BB_FN (bb, fun)
3091 gimple_stmt_iterator gsi;
3092 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3093 gimple_set_uid (gsi_stmt (gsi), -1);
3094 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3095 gimple_set_uid (gsi_stmt (gsi), -1);
3098 /* We can at the moment only distribute non-nested loops, thus restrict
3099 walking to innermost loops. */
3100 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
3102 /* Don't distribute multiple exit edges loop, or cold loop. */
3103 if (!single_exit (loop)
3104 || !optimize_loop_for_speed_p (loop))
3105 continue;
3107 /* Don't distribute loop if niters is unknown. */
3108 tree niters = number_of_latch_executions (loop);
3109 if (niters == NULL_TREE || niters == chrec_dont_know)
3110 continue;
3112 /* Get the perfect loop nest for distribution. */
3113 loop = prepare_perfect_loop_nest (loop);
3114 for (; loop; loop = loop->inner)
3116 auto_vec<gimple *> work_list;
3117 if (!find_seed_stmts_for_distribution (loop, &work_list))
3118 break;
3120 const char *str = loop->inner ? " nest" : "";
3121 dump_user_location_t loc = find_loop_location (loop);
3122 if (!cd)
3124 calculate_dominance_info (CDI_DOMINATORS);
3125 calculate_dominance_info (CDI_POST_DOMINATORS);
3126 cd = new control_dependences ();
3127 free_dominance_info (CDI_POST_DOMINATORS);
3130 bool destroy_p;
3131 int nb_generated_loops, nb_generated_calls;
3132 nb_generated_loops = distribute_loop (loop, work_list, cd,
3133 &nb_generated_calls,
3134 &destroy_p);
3135 if (destroy_p)
3136 loops_to_be_destroyed.safe_push (loop);
3138 if (nb_generated_loops + nb_generated_calls > 0)
3140 changed = true;
3141 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3142 loc, "Loop%s %d distributed: split to %d loops "
3143 "and %d library calls.\n", str, loop->num,
3144 nb_generated_loops, nb_generated_calls);
3146 break;
3149 if (dump_file && (dump_flags & TDF_DETAILS))
3150 fprintf (dump_file, "Loop%s %d not distributed.\n", str, loop->num);
3154 if (cd)
3155 delete cd;
3157 if (bb_top_order_index != NULL)
3159 free (bb_top_order_index);
3160 bb_top_order_index = NULL;
3161 bb_top_order_index_size = 0;
3164 if (changed)
3166 /* Destroy loop bodies that could not be reused. Do this late as we
3167 otherwise can end up refering to stale data in control dependences. */
3168 unsigned i;
3169 FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
3170 destroy_loop (loop);
3172 /* Cached scalar evolutions now may refer to wrong or non-existing
3173 loops. */
3174 scev_reset_htab ();
3175 mark_virtual_operands_for_renaming (fun);
3176 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3179 checking_verify_loop_structure ();
3181 return changed ? TODO_cleanup_cfg : 0;
3184 } // anon namespace
3186 gimple_opt_pass *
3187 make_pass_loop_distribution (gcc::context *ctxt)
3189 return new pass_loop_distribution (ctxt);