]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-loop-distribution.c
re PR ipa/61659 (Extra undefined symbol because of devirtualization)
[thirdparty/gcc.git] / gcc / tree-loop-distribution.c
CommitLineData
dea61d92 1/* Loop distribution.
23a5b65a 2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
dea61d92
SP
3 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
4 and Sebastian Pop <sebastian.pop@amd.com>.
5
6This file is part of GCC.
b8698a0f 7
dea61d92
SP
8GCC is free software; you can redistribute it and/or modify it
9under the terms of the GNU General Public License as published by the
10Free Software Foundation; either version 3, or (at your option) any
11later version.
b8698a0f 12
dea61d92
SP
13GCC is distributed in the hope that it will be useful, but WITHOUT
14ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
b8698a0f 17
dea61d92
SP
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22/* This pass performs loop distribution: for example, the loop
23
24 |DO I = 2, N
25 | A(I) = B(I) + C
26 | D(I) = A(I-1)*E
27 |ENDDO
28
b8698a0f 29 is transformed to
dea61d92
SP
30
31 |DOALL I = 2, N
32 | A(I) = B(I) + C
33 |ENDDO
34 |
35 |DOALL I = 2, N
36 | D(I) = A(I-1)*E
37 |ENDDO
38
39 This pass uses an RDG, Reduced Dependence Graph built on top of the
40 data dependence relations. The RDG is then topologically sorted to
41 obtain a map of information producers/consumers based on which it
42 generates the new loops. */
43
44#include "config.h"
45#include "system.h"
46#include "coretypes.h"
4d648807 47#include "tree.h"
2fb9a547
AM
48#include "basic-block.h"
49#include "tree-ssa-alias.h"
50#include "internal-fn.h"
51#include "gimple-expr.h"
52#include "is-a.h"
18f429e2 53#include "gimple.h"
5be5c238 54#include "gimple-iterator.h"
18f429e2 55#include "gimplify-me.h"
d8a2d370 56#include "stor-layout.h"
442b4905
AM
57#include "gimple-ssa.h"
58#include "tree-cfg.h"
59#include "tree-phinodes.h"
60#include "ssa-iterators.h"
d8a2d370 61#include "stringpool.h"
442b4905 62#include "tree-ssanames.h"
e28030cf 63#include "tree-ssa-loop-manip.h"
442b4905
AM
64#include "tree-ssa-loop.h"
65#include "tree-into-ssa.h"
7a300452 66#include "tree-ssa.h"
dea61d92 67#include "cfgloop.h"
dea61d92
SP
68#include "tree-chrec.h"
69#include "tree-data-ref.h"
70#include "tree-scalar-evolution.h"
71#include "tree-pass.h"
80ab0b19 72#include "gimple-pretty-print.h"
826a536d 73#include "tree-vectorizer.h"
80ab0b19
RB
74
75
76/* A Reduced Dependence Graph (RDG) vertex representing a statement. */
77typedef struct rdg_vertex
78{
79 /* The statement represented by this vertex. */
80 gimple stmt;
81
82 /* Vector of data-references in this statement. */
83 vec<data_reference_p> datarefs;
84
85 /* True when the statement contains a write to memory. */
86 bool has_mem_write;
87
88 /* True when the statement contains a read from memory. */
89 bool has_mem_reads;
90} *rdg_vertex_p;
91
92#define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
93#define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
94#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
95#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
96#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
97#define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
98#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
99#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
100
101/* Data dependence type. */
102
103enum rdg_dep_type
104{
105 /* Read After Write (RAW). */
106 flow_dd = 'f',
107
36875e8f
RB
108 /* Control dependence (execute conditional on). */
109 control_dd = 'c'
80ab0b19
RB
110};
111
112/* Dependence information attached to an edge of the RDG. */
113
114typedef struct rdg_edge
115{
116 /* Type of the dependence. */
117 enum rdg_dep_type type;
80ab0b19
RB
118} *rdg_edge_p;
119
120#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
80ab0b19 121
80ab0b19
RB
122/* Dump vertex I in RDG to FILE. */
123
124static void
125dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
126{
127 struct vertex *v = &(rdg->vertices[i]);
128 struct graph_edge *e;
129
130 fprintf (file, "(vertex %d: (%s%s) (in:", i,
131 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
132 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
133
134 if (v->pred)
135 for (e = v->pred; e; e = e->pred_next)
136 fprintf (file, " %d", e->src);
137
138 fprintf (file, ") (out:");
139
140 if (v->succ)
141 for (e = v->succ; e; e = e->succ_next)
142 fprintf (file, " %d", e->dest);
143
144 fprintf (file, ")\n");
145 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
146 fprintf (file, ")\n");
147}
148
149/* Call dump_rdg_vertex on stderr. */
150
151DEBUG_FUNCTION void
152debug_rdg_vertex (struct graph *rdg, int i)
153{
154 dump_rdg_vertex (stderr, rdg, i);
155}
156
80ab0b19
RB
157/* Dump the reduced dependence graph RDG to FILE. */
158
159static void
160dump_rdg (FILE *file, struct graph *rdg)
161{
80ab0b19 162 fprintf (file, "(rdg\n");
2fd5894f
RB
163 for (int i = 0; i < rdg->n_vertices; i++)
164 dump_rdg_vertex (file, rdg, i);
80ab0b19 165 fprintf (file, ")\n");
80ab0b19
RB
166}
167
168/* Call dump_rdg on stderr. */
169
170DEBUG_FUNCTION void
171debug_rdg (struct graph *rdg)
172{
173 dump_rdg (stderr, rdg);
174}
175
176static void
177dot_rdg_1 (FILE *file, struct graph *rdg)
178{
179 int i;
174ec470
RB
180 pretty_printer buffer;
181 pp_needs_newline (&buffer) = false;
182 buffer.buffer->stream = file;
80ab0b19
RB
183
184 fprintf (file, "digraph RDG {\n");
185
186 for (i = 0; i < rdg->n_vertices; i++)
187 {
188 struct vertex *v = &(rdg->vertices[i]);
189 struct graph_edge *e;
190
174ec470
RB
191 fprintf (file, "%d [label=\"[%d] ", i, i);
192 pp_gimple_stmt_1 (&buffer, RDGV_STMT (v), 0, TDF_SLIM);
193 pp_flush (&buffer);
194 fprintf (file, "\"]\n");
195
80ab0b19
RB
196 /* Highlight reads from memory. */
197 if (RDG_MEM_READS_STMT (rdg, i))
198 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
199
200 /* Highlight stores to memory. */
201 if (RDG_MEM_WRITE_STMT (rdg, i))
202 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
203
204 if (v->succ)
205 for (e = v->succ; e; e = e->succ_next)
206 switch (RDGE_TYPE (e))
207 {
80ab0b19
RB
208 case flow_dd:
209 /* These are the most common dependences: don't print these. */
210 fprintf (file, "%d -> %d \n", i, e->dest);
211 break;
212
36875e8f
RB
213 case control_dd:
214 fprintf (file, "%d -> %d [label=control] \n", i, e->dest);
215 break;
216
80ab0b19
RB
217 default:
218 gcc_unreachable ();
219 }
220 }
221
222 fprintf (file, "}\n\n");
223}
224
225/* Display the Reduced Dependence Graph using dotty. */
226
227DEBUG_FUNCTION void
228dot_rdg (struct graph *rdg)
229{
174ec470
RB
230 /* When debugging, you may want to enable the following code. */
231#if 1
c3284718 232 FILE *file = popen ("dot -Tx11", "w");
174ec470
RB
233 if (!file)
234 return;
80ab0b19 235 dot_rdg_1 (file, rdg);
174ec470
RB
236 fflush (file);
237 close (fileno (file));
238 pclose (file);
80ab0b19
RB
239#else
240 dot_rdg_1 (stderr, rdg);
241#endif
242}
243
244/* Returns the index of STMT in RDG. */
245
246static int
247rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
248{
249 int index = gimple_uid (stmt);
250 gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
251 return index;
252}
253
80ab0b19
RB
254/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
255 the index of DEF in RDG. */
256
257static void
258create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
259{
260 use_operand_p imm_use_p;
261 imm_use_iterator iterator;
262
263 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
264 {
265 struct graph_edge *e;
266 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
267
268 if (use < 0)
269 continue;
270
271 e = add_edge (rdg, idef, use);
272 e->data = XNEW (struct rdg_edge);
273 RDGE_TYPE (e) = flow_dd;
80ab0b19
RB
274 }
275}
276
36875e8f
RB
277/* Creates an edge for the control dependences of BB to the vertex V. */
278
279static void
280create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
281 int v, control_dependences *cd)
282{
283 bitmap_iterator bi;
284 unsigned edge_n;
285 EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
286 0, edge_n, bi)
287 {
288 basic_block cond_bb = cd->get_edge (edge_n)->src;
289 gimple stmt = last_stmt (cond_bb);
290 if (stmt && is_ctrl_stmt (stmt))
291 {
292 struct graph_edge *e;
293 int c = rdg_vertex_for_stmt (rdg, stmt);
294 if (c < 0)
295 continue;
296
297 e = add_edge (rdg, c, v);
298 e->data = XNEW (struct rdg_edge);
299 RDGE_TYPE (e) = control_dd;
36875e8f
RB
300 }
301 }
302}
303
80ab0b19
RB
304/* Creates the edges of the reduced dependence graph RDG. */
305
306static void
447f3223 307create_rdg_flow_edges (struct graph *rdg)
80ab0b19
RB
308{
309 int i;
80ab0b19
RB
310 def_operand_p def_p;
311 ssa_op_iter iter;
312
80ab0b19
RB
313 for (i = 0; i < rdg->n_vertices; i++)
314 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
315 iter, SSA_OP_DEF)
316 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
447f3223 317}
36875e8f 318
447f3223
RB
319/* Creates the edges of the reduced dependence graph RDG. */
320
321static void
322create_rdg_cd_edges (struct graph *rdg, control_dependences *cd)
323{
324 int i;
325
326 for (i = 0; i < rdg->n_vertices; i++)
327 {
328 gimple stmt = RDG_STMT (rdg, i);
329 if (gimple_code (stmt) == GIMPLE_PHI)
330 {
331 edge_iterator ei;
332 edge e;
333 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
36875e8f 334 create_edge_for_control_dependence (rdg, e->src, i, cd);
447f3223
RB
335 }
336 else
337 create_edge_for_control_dependence (rdg, gimple_bb (stmt), i, cd);
338 }
80ab0b19
RB
339}
340
341/* Build the vertices of the reduced dependence graph RDG. Return false
342 if that failed. */
343
344static bool
345create_rdg_vertices (struct graph *rdg, vec<gimple> stmts, loop_p loop,
346 vec<data_reference_p> *datarefs)
347{
348 int i;
349 gimple stmt;
350
351 FOR_EACH_VEC_ELT (stmts, i, stmt)
352 {
353 struct vertex *v = &(rdg->vertices[i]);
354
355 /* Record statement to vertex mapping. */
356 gimple_set_uid (stmt, i);
357
358 v->data = XNEW (struct rdg_vertex);
359 RDGV_STMT (v) = stmt;
360 RDGV_DATAREFS (v).create (0);
361 RDGV_HAS_MEM_WRITE (v) = false;
362 RDGV_HAS_MEM_READS (v) = false;
363 if (gimple_code (stmt) == GIMPLE_PHI)
364 continue;
365
366 unsigned drp = datarefs->length ();
367 if (!find_data_references_in_stmt (loop, stmt, datarefs))
368 return false;
369 for (unsigned j = drp; j < datarefs->length (); ++j)
370 {
371 data_reference_p dr = (*datarefs)[j];
372 if (DR_IS_READ (dr))
373 RDGV_HAS_MEM_READS (v) = true;
374 else
375 RDGV_HAS_MEM_WRITE (v) = true;
376 RDGV_DATAREFS (v).safe_push (dr);
377 }
378 }
379 return true;
380}
381
2fd5894f 382/* Initialize STMTS with all the statements of LOOP. The order in
80ab0b19
RB
383 which we discover statements is important as
384 generate_loops_for_partition is using the same traversal for
2fd5894f 385 identifying statements in loop copies. */
80ab0b19
RB
386
387static void
388stmts_from_loop (struct loop *loop, vec<gimple> *stmts)
389{
390 unsigned int i;
391 basic_block *bbs = get_loop_body_in_dom_order (loop);
392
393 for (i = 0; i < loop->num_nodes; i++)
394 {
395 basic_block bb = bbs[i];
396 gimple_stmt_iterator bsi;
397 gimple stmt;
398
399 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
83a95546
RB
400 if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi))))
401 stmts->safe_push (gsi_stmt (bsi));
80ab0b19
RB
402
403 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
404 {
405 stmt = gsi_stmt (bsi);
406 if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
407 stmts->safe_push (stmt);
408 }
409 }
410
411 free (bbs);
412}
413
80ab0b19
RB
414/* Free the reduced dependence graph RDG. */
415
416static void
417free_rdg (struct graph *rdg)
418{
419 int i;
420
421 for (i = 0; i < rdg->n_vertices; i++)
422 {
423 struct vertex *v = &(rdg->vertices[i]);
424 struct graph_edge *e;
425
426 for (e = v->succ; e; e = e->succ_next)
447f3223 427 free (e->data);
80ab0b19
RB
428
429 if (v->data)
430 {
431 gimple_set_uid (RDGV_STMT (v), -1);
432 free_data_refs (RDGV_DATAREFS (v));
433 free (v->data);
434 }
435 }
436
437 free_graph (rdg);
438}
439
440/* Build the Reduced Dependence Graph (RDG) with one vertex per
97463b2b 441 statement of the loop nest LOOP_NEST, and one edge per data dependence or
80ab0b19
RB
442 scalar dependence. */
443
444static struct graph *
36875e8f 445build_rdg (vec<loop_p> loop_nest, control_dependences *cd)
80ab0b19
RB
446{
447 struct graph *rdg;
80ab0b19 448 vec<data_reference_p> datarefs;
80ab0b19 449
97463b2b 450 /* Create the RDG vertices from the stmts of the loop nest. */
00f96dc9 451 auto_vec<gimple, 10> stmts;
97463b2b 452 stmts_from_loop (loop_nest[0], &stmts);
24f161fd 453 rdg = new_graph (stmts.length ());
80ab0b19 454 datarefs.create (10);
97463b2b 455 if (!create_rdg_vertices (rdg, stmts, loop_nest[0], &datarefs))
80ab0b19 456 {
97463b2b 457 datarefs.release ();
80ab0b19
RB
458 free_rdg (rdg);
459 return NULL;
460 }
461 stmts.release ();
97463b2b 462
447f3223
RB
463 create_rdg_flow_edges (rdg);
464 if (cd)
465 create_rdg_cd_edges (rdg, cd);
466
97463b2b 467 datarefs.release ();
80ab0b19
RB
468
469 return rdg;
470}
471
80ab0b19 472
dea61d92 473
b9fc0497 474enum partition_kind {
826a536d 475 PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY
b9fc0497 476};
30d55936 477
c61f8985
RG
478typedef struct partition_s
479{
480 bitmap stmts;
80ab0b19 481 bitmap loops;
826a536d 482 bool reduction_p;
30d55936 483 enum partition_kind kind;
d0582dc1
RG
484 /* data-references a kind != PKIND_NORMAL partition is about. */
485 data_reference_p main_dr;
486 data_reference_p secondary_dr;
818625cf 487 tree niter;
d995e887 488 bool plus_one;
c61f8985
RG
489} *partition_t;
490
c61f8985
RG
491
492/* Allocate and initialize a partition from BITMAP. */
493
494static partition_t
80ab0b19 495partition_alloc (bitmap stmts, bitmap loops)
c61f8985
RG
496{
497 partition_t partition = XCNEW (struct partition_s);
498 partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL);
80ab0b19 499 partition->loops = loops ? loops : BITMAP_ALLOC (NULL);
826a536d 500 partition->reduction_p = false;
30d55936 501 partition->kind = PKIND_NORMAL;
c61f8985
RG
502 return partition;
503}
504
505/* Free PARTITION. */
506
507static void
508partition_free (partition_t partition)
509{
510 BITMAP_FREE (partition->stmts);
80ab0b19 511 BITMAP_FREE (partition->loops);
c61f8985
RG
512 free (partition);
513}
514
30d55936
RG
515/* Returns true if the partition can be generated as a builtin. */
516
517static bool
518partition_builtin_p (partition_t partition)
519{
826a536d 520 return partition->kind != PKIND_NORMAL;
30d55936 521}
c61f8985 522
826a536d 523/* Returns true if the partition contains a reduction. */
7ad672e4
RG
524
525static bool
826a536d 526partition_reduction_p (partition_t partition)
7ad672e4 527{
826a536d 528 return partition->reduction_p;
7ad672e4
RG
529}
530
826a536d
RB
531/* Merge PARTITION into the partition DEST. */
532
533static void
534partition_merge_into (partition_t dest, partition_t partition)
535{
536 dest->kind = PKIND_NORMAL;
537 bitmap_ior_into (dest->stmts, partition->stmts);
538 if (partition_reduction_p (partition))
539 dest->reduction_p = true;
540}
541
542
c07a8cb3
RG
543/* Returns true when DEF is an SSA_NAME defined in LOOP and used after
544 the LOOP. */
545
546static bool
547ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
548{
549 imm_use_iterator imm_iter;
550 use_operand_p use_p;
551
552 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
e665269a
RG
553 {
554 gimple use_stmt = USE_STMT (use_p);
555 if (!is_gimple_debug (use_stmt)
556 && loop != loop_containing_stmt (use_stmt))
557 return true;
558 }
c07a8cb3
RG
559
560 return false;
561}
562
563/* Returns true when STMT defines a scalar variable used after the
88af7c1a 564 loop LOOP. */
c07a8cb3
RG
565
566static bool
88af7c1a 567stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple stmt)
c07a8cb3 568{
88af7c1a
RG
569 def_operand_p def_p;
570 ssa_op_iter op_iter;
c07a8cb3 571
9ca86fc3
RG
572 if (gimple_code (stmt) == GIMPLE_PHI)
573 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop);
574
88af7c1a
RG
575 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
576 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop))
577 return true;
c07a8cb3 578
88af7c1a 579 return false;
c07a8cb3
RG
580}
581
dea61d92
SP
582/* Return a copy of LOOP placed before LOOP. */
583
584static struct loop *
585copy_loop_before (struct loop *loop)
586{
587 struct loop *res;
588 edge preheader = loop_preheader_edge (loop);
589
dea61d92 590 initialize_original_copy_tables ();
5ce9450f 591 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, NULL, preheader);
30d55936 592 gcc_assert (res != NULL);
dea61d92 593 free_original_copy_tables ();
2cfc56b9 594 delete_update_ssa ();
dea61d92
SP
595
596 return res;
597}
598
599/* Creates an empty basic block after LOOP. */
600
601static void
602create_bb_after_loop (struct loop *loop)
603{
604 edge exit = single_exit (loop);
605
606 if (!exit)
607 return;
608
609 split_edge (exit);
610}
611
612/* Generate code for PARTITION from the code in LOOP. The loop is
613 copied when COPY_P is true. All the statements not flagged in the
614 PARTITION bitmap are removed from the loop or from its copy. The
615 statements are indexed in sequence inside a basic block, and the
30d55936 616 basic blocks of a loop are taken in dom order. */
dea61d92 617
30d55936 618static void
c61f8985
RG
619generate_loops_for_partition (struct loop *loop, partition_t partition,
620 bool copy_p)
dea61d92 621{
2fd5894f 622 unsigned i;
726a989a 623 gimple_stmt_iterator bsi;
dea61d92
SP
624 basic_block *bbs;
625
626 if (copy_p)
627 {
628 loop = copy_loop_before (loop);
30d55936 629 gcc_assert (loop != NULL);
dea61d92
SP
630 create_preheader (loop, CP_SIMPLE_PREHEADERS);
631 create_bb_after_loop (loop);
632 }
633
2fd5894f 634 /* Remove stmts not in the PARTITION bitmap. */
dea61d92
SP
635 bbs = get_loop_body_in_dom_order (loop);
636
b03c3082 637 if (MAY_HAVE_DEBUG_STMTS)
2fd5894f 638 for (i = 0; i < loop->num_nodes; i++)
b03c3082
JJ
639 {
640 basic_block bb = bbs[i];
641
642 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2fd5894f
RB
643 {
644 gimple phi = gsi_stmt (bsi);
645 if (!virtual_operand_p (gimple_phi_result (phi))
646 && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
647 reset_debug_uses (phi);
648 }
b03c3082
JJ
649
650 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
651 {
652 gimple stmt = gsi_stmt (bsi);
653 if (gimple_code (stmt) != GIMPLE_LABEL
654 && !is_gimple_debug (stmt)
2fd5894f 655 && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
b03c3082
JJ
656 reset_debug_uses (stmt);
657 }
658 }
659
2fd5894f 660 for (i = 0; i < loop->num_nodes; i++)
dea61d92
SP
661 {
662 basic_block bb = bbs[i];
dea61d92 663
726a989a 664 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
2fd5894f
RB
665 {
666 gimple phi = gsi_stmt (bsi);
667 if (!virtual_operand_p (gimple_phi_result (phi))
668 && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
2706a615 669 remove_phi_node (&bsi, true);
2fd5894f
RB
670 else
671 gsi_next (&bsi);
672 }
dea61d92 673
726a989a 674 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
2706a615
RG
675 {
676 gimple stmt = gsi_stmt (bsi);
b03c3082
JJ
677 if (gimple_code (stmt) != GIMPLE_LABEL
678 && !is_gimple_debug (stmt)
2fd5894f 679 && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
2706a615 680 {
36875e8f
RB
681 /* Choose an arbitrary path through the empty CFG part
682 that this unnecessary control stmt controls. */
683 if (gimple_code (stmt) == GIMPLE_COND)
684 {
685 gimple_cond_make_false (stmt);
686 update_stmt (stmt);
687 }
688 else if (gimple_code (stmt) == GIMPLE_SWITCH)
689 {
690 gimple_switch_set_index
691 (stmt, CASE_LOW (gimple_switch_label (stmt, 1)));
692 update_stmt (stmt);
693 }
694 else
695 {
696 unlink_stmt_vdef (stmt);
697 gsi_remove (&bsi, true);
698 release_defs (stmt);
699 continue;
700 }
2706a615 701 }
36875e8f 702 gsi_next (&bsi);
2706a615 703 }
dea61d92
SP
704 }
705
706 free (bbs);
dea61d92
SP
707}
708
d0582dc1 709/* Build the size argument for a memory operation call. */
3661e899 710
d0582dc1 711static tree
d995e887
RB
712build_size_arg_loc (location_t loc, data_reference_p dr, tree nb_iter,
713 bool plus_one)
3661e899 714{
d995e887
RB
715 tree size = fold_convert_loc (loc, sizetype, nb_iter);
716 if (plus_one)
717 size = size_binop (PLUS_EXPR, size, size_one_node);
718 size = fold_build2_loc (loc, MULT_EXPR, sizetype, size,
d0582dc1 719 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
d995e887
RB
720 size = fold_convert_loc (loc, size_type_node, size);
721 return size;
d0582dc1
RG
722}
723
724/* Build an address argument for a memory operation call. */
725
726static tree
727build_addr_arg_loc (location_t loc, data_reference_p dr, tree nb_bytes)
728{
729 tree addr_base;
730
731 addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
732 addr_base = fold_convert_loc (loc, sizetype, addr_base);
733
734 /* Test for a negative stride, iterating over every element. */
735 if (tree_int_cst_sgn (DR_STEP (dr)) == -1)
736 {
737 addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
738 fold_convert_loc (loc, sizetype, nb_bytes));
739 addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
740 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
741 }
742
743 return fold_build_pointer_plus_loc (loc, DR_BASE_ADDRESS (dr), addr_base);
3661e899
TB
744}
745
401f3a81
JJ
746/* If VAL memory representation contains the same value in all bytes,
747 return that value, otherwise return -1.
748 E.g. for 0x24242424 return 0x24, for IEEE double
749 747708026454360457216.0 return 0x44, etc. */
750
751static int
752const_with_all_bytes_same (tree val)
753{
754 unsigned char buf[64];
755 int i, len;
756
757 if (integer_zerop (val)
758 || real_zerop (val)
759 || (TREE_CODE (val) == CONSTRUCTOR
760 && !TREE_CLOBBER_P (val)
761 && CONSTRUCTOR_NELTS (val) == 0))
762 return 0;
763
764 if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
765 return -1;
766
767 len = native_encode_expr (val, buf, sizeof (buf));
768 if (len == 0)
769 return -1;
770 for (i = 1; i < len; i++)
771 if (buf[i] != buf[0])
772 return -1;
773 return buf[0];
774}
775
30d55936 776/* Generate a call to memset for PARTITION in LOOP. */
dea61d92 777
cfee318d 778static void
d0582dc1 779generate_memset_builtin (struct loop *loop, partition_t partition)
dea61d92 780{
30d55936
RG
781 gimple_stmt_iterator gsi;
782 gimple stmt, fn_call;
818625cf 783 tree mem, fn, nb_bytes;
30d55936 784 location_t loc;
b6dd5261 785 tree val;
30d55936 786
d0582dc1 787 stmt = DR_STMT (partition->main_dr);
30d55936 788 loc = gimple_location (stmt);
30d55936
RG
789
790 /* The new statements will be placed before LOOP. */
791 gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
dea61d92 792
d995e887
RB
793 nb_bytes = build_size_arg_loc (loc, partition->main_dr, partition->niter,
794 partition->plus_one);
d0582dc1
RG
795 nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
796 false, GSI_CONTINUE_LINKING);
797 mem = build_addr_arg_loc (loc, partition->main_dr, nb_bytes);
798 mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
799 false, GSI_CONTINUE_LINKING);
dea61d92 800
b6dd5261
RG
801 /* This exactly matches the pattern recognition in classify_partition. */
802 val = gimple_assign_rhs1 (stmt);
401f3a81
JJ
803 /* Handle constants like 0x15151515 and similarly
804 floating point constants etc. where all bytes are the same. */
805 int bytev = const_with_all_bytes_same (val);
806 if (bytev != -1)
807 val = build_int_cst (integer_type_node, bytev);
808 else if (TREE_CODE (val) == INTEGER_CST)
809 val = fold_convert (integer_type_node, val);
810 else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
b6dd5261 811 {
401f3a81
JJ
812 gimple cstmt;
813 tree tem = make_ssa_name (integer_type_node, NULL);
814 cstmt = gimple_build_assign_with_ops (NOP_EXPR, tem, val, NULL_TREE);
815 gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
816 val = tem;
b6dd5261
RG
817 }
818
e79983f4 819 fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
b6dd5261 820 fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
d0582dc1 821 gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
dea61d92
SP
822
823 if (dump_file && (dump_flags & TDF_DETAILS))
b6dd5261
RG
824 {
825 fprintf (dump_file, "generated memset");
401f3a81 826 if (bytev == 0)
b6dd5261 827 fprintf (dump_file, " zero\n");
b6dd5261
RG
828 else
829 fprintf (dump_file, "\n");
830 }
dea61d92
SP
831}
832
d0582dc1
RG
833/* Generate a call to memcpy for PARTITION in LOOP. */
834
835static void
836generate_memcpy_builtin (struct loop *loop, partition_t partition)
837{
838 gimple_stmt_iterator gsi;
839 gimple stmt, fn_call;
818625cf 840 tree dest, src, fn, nb_bytes;
d0582dc1
RG
841 location_t loc;
842 enum built_in_function kind;
843
844 stmt = DR_STMT (partition->main_dr);
845 loc = gimple_location (stmt);
d0582dc1
RG
846
847 /* The new statements will be placed before LOOP. */
848 gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
849
d995e887
RB
850 nb_bytes = build_size_arg_loc (loc, partition->main_dr, partition->niter,
851 partition->plus_one);
d0582dc1
RG
852 nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
853 false, GSI_CONTINUE_LINKING);
854 dest = build_addr_arg_loc (loc, partition->main_dr, nb_bytes);
855 src = build_addr_arg_loc (loc, partition->secondary_dr, nb_bytes);
856 if (ptr_derefs_may_alias_p (dest, src))
857 kind = BUILT_IN_MEMMOVE;
858 else
859 kind = BUILT_IN_MEMCPY;
860
861 dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
862 false, GSI_CONTINUE_LINKING);
863 src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
864 false, GSI_CONTINUE_LINKING);
865 fn = build_fold_addr_expr (builtin_decl_implicit (kind));
866 fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
867 gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
868
869 if (dump_file && (dump_flags & TDF_DETAILS))
870 {
871 if (kind == BUILT_IN_MEMCPY)
872 fprintf (dump_file, "generated memcpy\n");
873 else
874 fprintf (dump_file, "generated memmove\n");
875 }
876}
877
30d55936 878/* Remove and destroy the loop LOOP. */
dea61d92 879
30d55936
RG
880static void
881destroy_loop (struct loop *loop)
dea61d92 882{
30d55936
RG
883 unsigned nbbs = loop->num_nodes;
884 edge exit = single_exit (loop);
885 basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
dea61d92 886 basic_block *bbs;
30d55936 887 unsigned i;
dea61d92
SP
888
889 bbs = get_loop_body_in_dom_order (loop);
890
30d55936
RG
891 redirect_edge_pred (exit, src);
892 exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
893 exit->flags |= EDGE_FALLTHRU;
894 cancel_loop_tree (loop);
895 rescan_loop_exit (exit, false, true);
dea61d92 896
30d55936 897 for (i = 0; i < nbbs; i++)
c014f6f5
RG
898 {
899 /* We have made sure to not leave any dangling uses of SSA
900 names defined in the loop. With the exception of virtuals.
901 Make sure we replace all uses of virtual defs that will remain
902 outside of the loop with the bare symbol as delete_basic_block
903 will release them. */
904 gimple_stmt_iterator gsi;
905 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
906 {
907 gimple phi = gsi_stmt (gsi);
ea057359 908 if (virtual_operand_p (gimple_phi_result (phi)))
c014f6f5
RG
909 mark_virtual_phi_result_for_renaming (phi);
910 }
911 for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
912 {
913 gimple stmt = gsi_stmt (gsi);
914 tree vdef = gimple_vdef (stmt);
915 if (vdef && TREE_CODE (vdef) == SSA_NAME)
916 mark_virtual_operand_for_renaming (vdef);
917 }
918 delete_basic_block (bbs[i]);
919 }
dea61d92 920 free (bbs);
30d55936
RG
921
922 set_immediate_dominator (CDI_DOMINATORS, dest,
923 recompute_dominator (CDI_DOMINATORS, dest));
dea61d92
SP
924}
925
30d55936 926/* Generates code for PARTITION. */
dea61d92 927
30d55936 928static void
d0582dc1 929generate_code_for_partition (struct loop *loop,
be6b029b 930 partition_t partition, bool copy_p)
dea61d92 931{
30d55936
RG
932 switch (partition->kind)
933 {
826a536d
RB
934 case PKIND_NORMAL:
935 /* Reductions all have to be in the last partition. */
936 gcc_assert (!partition_reduction_p (partition)
937 || !copy_p);
938 generate_loops_for_partition (loop, partition, copy_p);
939 return;
940
30d55936 941 case PKIND_MEMSET:
d0582dc1 942 generate_memset_builtin (loop, partition);
d0582dc1
RG
943 break;
944
945 case PKIND_MEMCPY:
946 generate_memcpy_builtin (loop, partition);
30d55936
RG
947 break;
948
949 default:
950 gcc_unreachable ();
951 }
dea61d92 952
826a536d
RB
953 /* Common tail for partitions we turn into a call. If this was the last
954 partition for which we generate code, we have to destroy the loop. */
955 if (!copy_p)
956 destroy_loop (loop);
dea61d92
SP
957}
958
dea61d92 959
24f161fd
RB
960/* Returns a partition with all the statements needed for computing
961 the vertex V of the RDG, also including the loop exit conditions. */
dea61d92 962
24f161fd
RB
963static partition_t
964build_rdg_partition_for_vertex (struct graph *rdg, int v)
dea61d92 965{
24f161fd 966 partition_t partition = partition_alloc (NULL, NULL);
00f96dc9 967 auto_vec<int, 3> nodes;
24f161fd 968 unsigned i;
dea61d92
SP
969 int x;
970
174ec470 971 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
dea61d92 972
9771b263 973 FOR_EACH_VEC_ELT (nodes, i, x)
24f161fd
RB
974 {
975 bitmap_set_bit (partition->stmts, x);
976 bitmap_set_bit (partition->loops,
977 loop_containing_stmt (RDG_STMT (rdg, x))->num);
978 }
dea61d92 979
dea61d92
SP
980 return partition;
981}
982
30d55936
RG
983/* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
984 For the moment we detect only the memset zero pattern. */
cfee318d 985
30d55936
RG
986static void
987classify_partition (loop_p loop, struct graph *rdg, partition_t partition)
cfee318d 988{
cfee318d 989 bitmap_iterator bi;
30d55936
RG
990 unsigned i;
991 tree nb_iter;
d0582dc1 992 data_reference_p single_load, single_store;
b9fc0497 993 bool volatiles_p = false;
d995e887 994 bool plus_one = false;
30d55936
RG
995
996 partition->kind = PKIND_NORMAL;
d0582dc1
RG
997 partition->main_dr = NULL;
998 partition->secondary_dr = NULL;
818625cf 999 partition->niter = NULL_TREE;
d995e887 1000 partition->plus_one = false;
30d55936 1001
c61f8985 1002 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
30d55936
RG
1003 {
1004 gimple stmt = RDG_STMT (rdg, i);
1005
1006 if (gimple_has_volatile_ops (stmt))
b9fc0497 1007 volatiles_p = true;
cfee318d 1008
826a536d 1009 /* If the stmt has uses outside of the loop mark it as reduction. */
9ca86fc3 1010 if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
30d55936 1011 {
826a536d 1012 partition->reduction_p = true;
30d55936
RG
1013 return;
1014 }
1015 }
1016
b9fc0497
RB
1017 /* Perform general partition disqualification for builtins. */
1018 if (volatiles_p
1019 || !flag_tree_loop_distribute_patterns)
1020 return;
1021
d0582dc1
RG
1022 /* Detect memset and memcpy. */
1023 single_load = NULL;
1024 single_store = NULL;
30d55936
RG
1025 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1026 {
1027 gimple stmt = RDG_STMT (rdg, i);
d0582dc1
RG
1028 data_reference_p dr;
1029 unsigned j;
30d55936
RG
1030
1031 if (gimple_code (stmt) == GIMPLE_PHI)
1032 continue;
1033
1034 /* Any scalar stmts are ok. */
1035 if (!gimple_vuse (stmt))
1036 continue;
1037
d0582dc1
RG
1038 /* Otherwise just regular loads/stores. */
1039 if (!gimple_assign_single_p (stmt))
1040 return;
1041
1042 /* But exactly one store and/or load. */
9771b263 1043 for (j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j)
30d55936 1044 {
d0582dc1
RG
1045 if (DR_IS_READ (dr))
1046 {
1047 if (single_load != NULL)
1048 return;
1049 single_load = dr;
1050 }
1051 else
1052 {
1053 if (single_store != NULL)
1054 return;
1055 single_store = dr;
1056 }
30d55936 1057 }
30d55936
RG
1058 }
1059
818625cf
RB
1060 if (!single_store)
1061 return;
1062
d995e887 1063 nb_iter = number_of_latch_executions (loop);
818625cf
RB
1064 if (!nb_iter || nb_iter == chrec_dont_know)
1065 return;
d995e887
RB
1066 if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
1067 gimple_bb (DR_STMT (single_store))))
1068 plus_one = true;
818625cf 1069
d0582dc1
RG
1070 if (single_store && !single_load)
1071 {
1072 gimple stmt = DR_STMT (single_store);
1073 tree rhs = gimple_assign_rhs1 (stmt);
401f3a81
JJ
1074 if (const_with_all_bytes_same (rhs) == -1
1075 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
1076 || (TYPE_MODE (TREE_TYPE (rhs))
1077 != TYPE_MODE (unsigned_char_type_node))))
d0582dc1
RG
1078 return;
1079 if (TREE_CODE (rhs) == SSA_NAME
1080 && !SSA_NAME_IS_DEFAULT_DEF (rhs)
1081 && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
1082 return;
ca406576
RB
1083 if (!adjacent_dr_p (single_store)
1084 || !dominated_by_p (CDI_DOMINATORS,
1085 loop->latch, gimple_bb (stmt)))
d0582dc1
RG
1086 return;
1087 partition->kind = PKIND_MEMSET;
1088 partition->main_dr = single_store;
818625cf 1089 partition->niter = nb_iter;
d995e887 1090 partition->plus_one = plus_one;
d0582dc1
RG
1091 }
1092 else if (single_store && single_load)
1093 {
1094 gimple store = DR_STMT (single_store);
1095 gimple load = DR_STMT (single_load);
1096 /* Direct aggregate copy or via an SSA name temporary. */
1097 if (load != store
1098 && gimple_assign_lhs (load) != gimple_assign_rhs1 (store))
1099 return;
1100 if (!adjacent_dr_p (single_store)
1101 || !adjacent_dr_p (single_load)
1102 || !operand_equal_p (DR_STEP (single_store),
ca406576
RB
1103 DR_STEP (single_load), 0)
1104 || !dominated_by_p (CDI_DOMINATORS,
1105 loop->latch, gimple_bb (store)))
d0582dc1 1106 return;
f20132e7
RG
1107 /* Now check that if there is a dependence this dependence is
1108 of a suitable form for memmove. */
6e1aa848 1109 vec<loop_p> loops = vNULL;
f20132e7 1110 ddr_p ddr;
9771b263 1111 loops.safe_push (loop);
f20132e7
RG
1112 ddr = initialize_data_dependence_relation (single_load, single_store,
1113 loops);
1114 compute_affine_dependence (ddr, loop);
f20132e7
RG
1115 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1116 {
1117 free_dependence_relation (ddr);
9771b263 1118 loops.release ();
f20132e7
RG
1119 return;
1120 }
1121 if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
1122 {
1123 if (DDR_NUM_DIST_VECTS (ddr) == 0)
1124 {
1125 free_dependence_relation (ddr);
9771b263 1126 loops.release ();
f20132e7
RG
1127 return;
1128 }
1129 lambda_vector dist_v;
9771b263 1130 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
f20132e7
RG
1131 {
1132 int dist = dist_v[index_in_loop_nest (loop->num,
1133 DDR_LOOP_NEST (ddr))];
1134 if (dist > 0 && !DDR_REVERSED_P (ddr))
1135 {
1136 free_dependence_relation (ddr);
9771b263 1137 loops.release ();
f20132e7
RG
1138 return;
1139 }
1140 }
1141 }
b7ce70b3 1142 free_dependence_relation (ddr);
9771b263 1143 loops.release ();
d0582dc1
RG
1144 partition->kind = PKIND_MEMCPY;
1145 partition->main_dr = single_store;
1146 partition->secondary_dr = single_load;
818625cf 1147 partition->niter = nb_iter;
d995e887 1148 partition->plus_one = plus_one;
d0582dc1 1149 }
cfee318d
SP
1150}
1151
1fa0c180
RG
1152/* For a data reference REF, return the declaration of its base
1153 address or NULL_TREE if the base is not determined. */
1154
1155static tree
1156ref_base_address (data_reference_p dr)
1157{
1158 tree base_address = DR_BASE_ADDRESS (dr);
1159 if (base_address
1160 && TREE_CODE (base_address) == ADDR_EXPR)
1161 return TREE_OPERAND (base_address, 0);
1162
1163 return base_address;
1164}
1165
cfee318d
SP
1166/* Returns true when PARTITION1 and PARTITION2 have similar memory
1167 accesses in RDG. */
1168
1169static bool
c61f8985
RG
1170similar_memory_accesses (struct graph *rdg, partition_t partition1,
1171 partition_t partition2)
cfee318d 1172{
1fa0c180 1173 unsigned i, j, k, l;
cfee318d 1174 bitmap_iterator bi, bj;
1fa0c180
RG
1175 data_reference_p ref1, ref2;
1176
1177 /* First check whether in the intersection of the two partitions are
1178 any loads or stores. Common loads are the situation that happens
1179 most often. */
1180 EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
1181 if (RDG_MEM_WRITE_STMT (rdg, i)
1182 || RDG_MEM_READS_STMT (rdg, i))
1183 return true;
cfee318d 1184
1fa0c180 1185 /* Then check all data-references against each other. */
c61f8985 1186 EXECUTE_IF_SET_IN_BITMAP (partition1->stmts, 0, i, bi)
cfee318d
SP
1187 if (RDG_MEM_WRITE_STMT (rdg, i)
1188 || RDG_MEM_READS_STMT (rdg, i))
c61f8985 1189 EXECUTE_IF_SET_IN_BITMAP (partition2->stmts, 0, j, bj)
cfee318d
SP
1190 if (RDG_MEM_WRITE_STMT (rdg, j)
1191 || RDG_MEM_READS_STMT (rdg, j))
1fa0c180 1192 {
9771b263 1193 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, i), k, ref1)
1fa0c180
RG
1194 {
1195 tree base1 = ref_base_address (ref1);
1196 if (base1)
9771b263 1197 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, j), l, ref2)
1fa0c180
RG
1198 if (base1 == ref_base_address (ref2))
1199 return true;
1200 }
1201 }
cfee318d
SP
1202
1203 return false;
1204}
1205
dea61d92
SP
1206/* Aggregate several components into a useful partition that is
1207 registered in the PARTITIONS vector. Partitions will be
1208 distributed in different loops. */
1209
1210static void
83a95546 1211rdg_build_partitions (struct graph *rdg,
2fd5894f 1212 vec<gimple> starting_stmts,
83a95546 1213 vec<partition_t> *partitions)
dea61d92 1214{
83a95546 1215 bitmap processed = BITMAP_ALLOC (NULL);
2fd5894f
RB
1216 int i;
1217 gimple stmt;
dea61d92 1218
2fd5894f 1219 FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
dea61d92 1220 {
2fd5894f
RB
1221 int v = rdg_vertex_for_stmt (rdg, stmt);
1222
1223 if (dump_file && (dump_flags & TDF_DETAILS))
1224 fprintf (dump_file,
1225 "ldist asked to generate code for vertex %d\n", v);
b8698a0f 1226
24f161fd
RB
1227 /* If the vertex is already contained in another partition so
1228 is the partition rooted at it. */
dea61d92
SP
1229 if (bitmap_bit_p (processed, v))
1230 continue;
b8698a0f 1231
24f161fd
RB
1232 partition_t partition = build_rdg_partition_for_vertex (rdg, v);
1233 bitmap_ior_into (processed, partition->stmts);
dea61d92 1234
826a536d 1235 if (dump_file && (dump_flags & TDF_DETAILS))
dea61d92 1236 {
826a536d
RB
1237 fprintf (dump_file, "ldist useful partition:\n");
1238 dump_bitmap (dump_file, partition->stmts);
dea61d92 1239 }
826a536d
RB
1240
1241 partitions->safe_push (partition);
dea61d92
SP
1242 }
1243
83a95546
RB
1244 /* All vertices should have been assigned to at least one partition now,
1245 other than vertices belonging to dead code. */
dea61d92 1246
83a95546 1247 BITMAP_FREE (processed);
dea61d92
SP
1248}
1249
1250/* Dump to FILE the PARTITIONS. */
1251
1252static void
9771b263 1253dump_rdg_partitions (FILE *file, vec<partition_t> partitions)
dea61d92
SP
1254{
1255 int i;
c61f8985 1256 partition_t partition;
dea61d92 1257
9771b263 1258 FOR_EACH_VEC_ELT (partitions, i, partition)
c61f8985 1259 debug_bitmap_file (file, partition->stmts);
dea61d92
SP
1260}
1261
1262/* Debug PARTITIONS. */
9771b263 1263extern void debug_rdg_partitions (vec<partition_t> );
dea61d92 1264
24e47c76 1265DEBUG_FUNCTION void
9771b263 1266debug_rdg_partitions (vec<partition_t> partitions)
dea61d92
SP
1267{
1268 dump_rdg_partitions (stderr, partitions);
1269}
1270
2b8aee8e
SP
1271/* Returns the number of read and write operations in the RDG. */
1272
1273static int
1274number_of_rw_in_rdg (struct graph *rdg)
1275{
1276 int i, res = 0;
1277
1278 for (i = 0; i < rdg->n_vertices; i++)
1279 {
1280 if (RDG_MEM_WRITE_STMT (rdg, i))
1281 ++res;
1282
1283 if (RDG_MEM_READS_STMT (rdg, i))
1284 ++res;
1285 }
1286
1287 return res;
1288}
1289
1290/* Returns the number of read and write operations in a PARTITION of
1291 the RDG. */
1292
1293static int
c61f8985 1294number_of_rw_in_partition (struct graph *rdg, partition_t partition)
2b8aee8e
SP
1295{
1296 int res = 0;
1297 unsigned i;
1298 bitmap_iterator ii;
1299
c61f8985 1300 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
2b8aee8e
SP
1301 {
1302 if (RDG_MEM_WRITE_STMT (rdg, i))
1303 ++res;
1304
1305 if (RDG_MEM_READS_STMT (rdg, i))
1306 ++res;
1307 }
1308
1309 return res;
1310}
1311
1312/* Returns true when one of the PARTITIONS contains all the read or
1313 write operations of RDG. */
1314
1315static bool
9771b263
DN
1316partition_contains_all_rw (struct graph *rdg,
1317 vec<partition_t> partitions)
2b8aee8e
SP
1318{
1319 int i;
c61f8985 1320 partition_t partition;
2b8aee8e
SP
1321 int nrw = number_of_rw_in_rdg (rdg);
1322
9771b263 1323 FOR_EACH_VEC_ELT (partitions, i, partition)
2b8aee8e
SP
1324 if (nrw == number_of_rw_in_partition (rdg, partition))
1325 return true;
1326
1327 return false;
1328}
1329
447f3223
RB
1330/* Compute partition dependence created by the data references in DRS1
1331 and DRS2 and modify and return DIR according to that. */
1332
1333static int
1334pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir,
1335 vec<data_reference_p> drs1,
1336 vec<data_reference_p> drs2)
1337{
1338 data_reference_p dr1, dr2;
1339
1340 /* dependence direction - 0 is no dependence, -1 is back,
1341 1 is forth, 2 is both (we can stop then, merging will occur). */
1342 for (int ii = 0; drs1.iterate (ii, &dr1); ++ii)
1343 for (int jj = 0; drs2.iterate (jj, &dr2); ++jj)
1344 {
2cf19e26 1345 int this_dir = 1;
447f3223
RB
1346 ddr_p ddr;
1347 /* Re-shuffle data-refs to be in dominator order. */
1348 if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1349 > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1350 {
1351 data_reference_p tem = dr1;
1352 dr1 = dr2;
1353 dr2 = tem;
1354 this_dir = -this_dir;
1355 }
1356 ddr = initialize_data_dependence_relation (dr1, dr2, loops);
1357 compute_affine_dependence (ddr, loops[0]);
1358 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
1359 this_dir = 2;
1360 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1361 {
1362 if (DDR_REVERSED_P (ddr))
1363 {
1364 data_reference_p tem = dr1;
1365 dr1 = dr2;
1366 dr2 = tem;
1367 this_dir = -this_dir;
1368 }
1369 /* Known dependences can still be unordered througout the
1370 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
2cf19e26 1371 if (DDR_NUM_DIST_VECTS (ddr) != 1)
447f3223 1372 this_dir = 2;
2cf19e26
RB
1373 /* If the overlap is exact preserve stmt order. */
1374 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1))
1375 ;
1376 else
1377 {
1378 /* Else as the distance vector is lexicographic positive
1379 swap the dependence direction. */
1380 this_dir = -this_dir;
1381 }
447f3223
RB
1382 }
1383 else
1384 this_dir = 0;
1385 free_dependence_relation (ddr);
1386 if (dir == 0)
1387 dir = this_dir;
1388 else if (dir != this_dir)
1389 return 2;
1390 }
1391 return dir;
1392}
1393
1394/* Compare postorder number of the partition graph vertices V1 and V2. */
1395
1396static int
1397pgcmp (const void *v1_, const void *v2_)
1398{
1399 const vertex *v1 = (const vertex *)v1_;
1400 const vertex *v2 = (const vertex *)v2_;
1401 return v2->post - v1->post;
1402}
2fd5894f
RB
1403
1404/* Distributes the code from LOOP in such a way that producer
1405 statements are placed before consumer statements. Tries to separate
1406 only the statements from STMTS into separate loops.
1407 Returns the number of distributed loops. */
dea61d92
SP
1408
1409static int
36875e8f 1410distribute_loop (struct loop *loop, vec<gimple> stmts,
826a536d 1411 control_dependences *cd, int *nb_calls)
dea61d92 1412{
2fd5894f 1413 struct graph *rdg;
c61f8985 1414 partition_t partition;
be6b029b 1415 bool any_builtin;
2fd5894f 1416 int i, nbp;
447f3223
RB
1417 graph *pg = NULL;
1418 int num_sccs = 1;
dea61d92 1419
826a536d 1420 *nb_calls = 0;
00f96dc9 1421 auto_vec<loop_p, 3> loop_nest;
2fd5894f 1422 if (!find_loop_nest (loop, &loop_nest))
07687835 1423 return 0;
2fd5894f 1424
36875e8f 1425 rdg = build_rdg (loop_nest, cd);
2fd5894f
RB
1426 if (!rdg)
1427 {
1428 if (dump_file && (dump_flags & TDF_DETAILS))
1429 fprintf (dump_file,
1430 "Loop %d not distributed: failed to build the RDG.\n",
1431 loop->num);
1432
2fd5894f
RB
1433 return 0;
1434 }
1435
1436 if (dump_file && (dump_flags & TDF_DETAILS))
1437 dump_rdg (dump_file, rdg);
1438
00f96dc9 1439 auto_vec<partition_t, 3> partitions;
2fd5894f 1440 rdg_build_partitions (rdg, stmts, &partitions);
dea61d92 1441
be6b029b 1442 any_builtin = false;
9771b263 1443 FOR_EACH_VEC_ELT (partitions, i, partition)
be6b029b
RG
1444 {
1445 classify_partition (loop, rdg, partition);
1446 any_builtin |= partition_builtin_p (partition);
1447 }
30d55936 1448
447f3223
RB
1449 /* If we are only distributing patterns but did not detect any,
1450 simply bail out. */
9fed7f3a
RB
1451 if (!flag_tree_loop_distribution
1452 && !any_builtin)
1453 {
1454 nbp = 0;
1455 goto ldist_done;
1456 }
1457
447f3223
RB
1458 /* If we are only distributing patterns fuse all partitions that
1459 were not classified as builtins. This also avoids chopping
1460 a loop into pieces, separated by builtin calls. That is, we
1461 only want no or a single loop body remaining. */
1462 partition_t into;
1463 if (!flag_tree_loop_distribution)
1464 {
1465 for (i = 0; partitions.iterate (i, &into); ++i)
1466 if (!partition_builtin_p (into))
1467 break;
1468 for (++i; partitions.iterate (i, &partition); ++i)
1469 if (!partition_builtin_p (partition))
1470 {
1471 if (dump_file && (dump_flags & TDF_DETAILS))
1472 {
1473 fprintf (dump_file, "fusing non-builtin partitions\n");
1474 dump_bitmap (dump_file, into->stmts);
1475 dump_bitmap (dump_file, partition->stmts);
1476 }
1477 partition_merge_into (into, partition);
1478 partitions.unordered_remove (i);
1479 partition_free (partition);
1480 i--;
1481 }
1482 }
1483
1484 /* Due to limitations in the transform phase we have to fuse all
1485 reduction partitions into the last partition so the existing
1486 loop will contain all loop-closed PHI nodes. */
1487 for (i = 0; partitions.iterate (i, &into); ++i)
1488 if (partition_reduction_p (into))
1489 break;
1490 for (i = i + 1; partitions.iterate (i, &partition); ++i)
1491 if (partition_reduction_p (partition))
1492 {
1493 if (dump_file && (dump_flags & TDF_DETAILS))
1494 {
1495 fprintf (dump_file, "fusing partitions\n");
1496 dump_bitmap (dump_file, into->stmts);
1497 dump_bitmap (dump_file, partition->stmts);
1498 fprintf (dump_file, "because they have reductions\n");
1499 }
1500 partition_merge_into (into, partition);
1501 partitions.unordered_remove (i);
1502 partition_free (partition);
1503 i--;
1504 }
1505
9fed7f3a
RB
1506 /* Apply our simple cost model - fuse partitions with similar
1507 memory accesses. */
9fed7f3a
RB
1508 for (i = 0; partitions.iterate (i, &into); ++i)
1509 {
1510 if (partition_builtin_p (into))
1511 continue;
1512 for (int j = i + 1;
1513 partitions.iterate (j, &partition); ++j)
1514 {
1515 if (!partition_builtin_p (partition)
1516 && similar_memory_accesses (rdg, into, partition))
1517 {
1518 if (dump_file && (dump_flags & TDF_DETAILS))
1519 {
1520 fprintf (dump_file, "fusing partitions\n");
1521 dump_bitmap (dump_file, into->stmts);
1522 dump_bitmap (dump_file, partition->stmts);
1523 fprintf (dump_file, "because they have similar "
1524 "memory accesses\n");
1525 }
826a536d 1526 partition_merge_into (into, partition);
447f3223 1527 partitions.unordered_remove (j);
9fed7f3a
RB
1528 partition_free (partition);
1529 j--;
1530 }
1531 }
1532 }
1533
447f3223
RB
1534 /* Build the partition dependency graph. */
1535 if (partitions.length () > 1)
c014f6f5 1536 {
447f3223
RB
1537 pg = new_graph (partitions.length ());
1538 struct pgdata {
1539 partition_t partition;
1540 vec<data_reference_p> writes;
1541 vec<data_reference_p> reads;
1542 };
1543#define PGDATA(i) ((pgdata *)(pg->vertices[i].data))
1544 for (i = 0; partitions.iterate (i, &partition); ++i)
1545 {
1546 vertex *v = &pg->vertices[i];
1547 pgdata *data = new pgdata;
1548 data_reference_p dr;
1549 /* FIXME - leaks. */
1550 v->data = data;
1551 bitmap_iterator bi;
1552 unsigned j;
1553 data->partition = partition;
1554 data->reads = vNULL;
1555 data->writes = vNULL;
1556 EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi)
1557 for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k)
1558 if (DR_IS_READ (dr))
1559 data->reads.safe_push (dr);
1560 else
1561 data->writes.safe_push (dr);
1562 }
1563 partition_t partition1, partition2;
1564 for (i = 0; partitions.iterate (i, &partition1); ++i)
1565 for (int j = i + 1; partitions.iterate (j, &partition2); ++j)
1566 {
1567 /* dependence direction - 0 is no dependence, -1 is back,
1568 1 is forth, 2 is both (we can stop then, merging will occur). */
1569 int dir = 0;
1570 dir = pg_add_dependence_edges (rdg, loop_nest, dir,
1571 PGDATA(i)->writes,
1572 PGDATA(j)->reads);
1573 if (dir != 2)
1574 dir = pg_add_dependence_edges (rdg, loop_nest, dir,
1575 PGDATA(i)->reads,
1576 PGDATA(j)->writes);
1577 if (dir != 2)
1578 dir = pg_add_dependence_edges (rdg, loop_nest, dir,
1579 PGDATA(i)->writes,
1580 PGDATA(j)->writes);
1581 if (dir == 1 || dir == 2)
1582 add_edge (pg, i, j);
1583 if (dir == -1 || dir == 2)
1584 add_edge (pg, j, i);
1585 }
1586
1587 /* Add edges to the reduction partition (if any) to force it last. */
1588 unsigned j;
1589 for (j = 0; partitions.iterate (j, &partition); ++j)
1590 if (partition_reduction_p (partition))
1591 break;
1592 if (j < partitions.length ())
38ad2d07 1593 {
447f3223
RB
1594 for (unsigned i = 0; partitions.iterate (i, &partition); ++i)
1595 if (i != j)
1596 add_edge (pg, i, j);
1597 }
1598
1599 /* Compute partitions we cannot separate and fuse them. */
1600 num_sccs = graphds_scc (pg, NULL);
1601 for (i = 0; i < num_sccs; ++i)
1602 {
1603 partition_t first;
1604 int j;
1605 for (j = 0; partitions.iterate (j, &first); ++j)
1606 if (pg->vertices[j].component == i)
38ad2d07 1607 break;
447f3223
RB
1608 for (j = j + 1; partitions.iterate (j, &partition); ++j)
1609 if (pg->vertices[j].component == i)
38ad2d07 1610 {
447f3223
RB
1611 if (dump_file && (dump_flags & TDF_DETAILS))
1612 {
1613 fprintf (dump_file, "fusing partitions\n");
1614 dump_bitmap (dump_file, first->stmts);
1615 dump_bitmap (dump_file, partition->stmts);
1616 fprintf (dump_file, "because they are in the same "
1617 "dependence SCC\n");
1618 }
1619 partition_merge_into (first, partition);
1620 partitions[j] = NULL;
5eb010bc 1621 partition_free (partition);
447f3223 1622 PGDATA (j)->partition = NULL;
38ad2d07 1623 }
38ad2d07 1624 }
30d55936 1625
447f3223
RB
1626 /* Now order the remaining nodes in postorder. */
1627 qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
1628 partitions.truncate (0);
1629 for (i = 0; i < pg->n_vertices; ++i)
b9fc0497 1630 {
447f3223
RB
1631 pgdata *data = PGDATA (i);
1632 if (data->partition)
1633 partitions.safe_push (data->partition);
1634 data->reads.release ();
1635 data->writes.release ();
1636 delete data;
b9fc0497 1637 }
447f3223
RB
1638 gcc_assert (partitions.length () == (unsigned)num_sccs);
1639 free_graph (pg);
b9fc0497
RB
1640 }
1641
9771b263 1642 nbp = partitions.length ();
a4293fa6 1643 if (nbp == 0
9771b263
DN
1644 || (nbp == 1 && !partition_builtin_p (partitions[0]))
1645 || (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
c014f6f5
RG
1646 {
1647 nbp = 0;
1648 goto ldist_done;
1649 }
dea61d92
SP
1650
1651 if (dump_file && (dump_flags & TDF_DETAILS))
1652 dump_rdg_partitions (dump_file, partitions);
1653
9771b263 1654 FOR_EACH_VEC_ELT (partitions, i, partition)
826a536d
RB
1655 {
1656 if (partition_builtin_p (partition))
1657 (*nb_calls)++;
1658 generate_code_for_partition (loop, partition, i < nbp - 1);
1659 }
dea61d92 1660
dea61d92
SP
1661 ldist_done:
1662
9771b263 1663 FOR_EACH_VEC_ELT (partitions, i, partition)
c61f8985 1664 partition_free (partition);
dea61d92 1665
dea61d92 1666 free_rdg (rdg);
826a536d 1667 return nbp - *nb_calls;
dea61d92
SP
1668}
1669
1670/* Distribute all loops in the current function. */
1671
be55bfe6
TS
1672namespace {
1673
1674const pass_data pass_data_loop_distribution =
1675{
1676 GIMPLE_PASS, /* type */
1677 "ldist", /* name */
1678 OPTGROUP_LOOP, /* optinfo_flags */
be55bfe6
TS
1679 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
1680 ( PROP_cfg | PROP_ssa ), /* properties_required */
1681 0, /* properties_provided */
1682 0, /* properties_destroyed */
1683 0, /* todo_flags_start */
3bea341f 1684 0, /* todo_flags_finish */
be55bfe6
TS
1685};
1686
1687class pass_loop_distribution : public gimple_opt_pass
1688{
1689public:
1690 pass_loop_distribution (gcc::context *ctxt)
1691 : gimple_opt_pass (pass_data_loop_distribution, ctxt)
1692 {}
1693
1694 /* opt_pass methods: */
1695 virtual bool gate (function *)
1696 {
1697 return flag_tree_loop_distribution
1698 || flag_tree_loop_distribute_patterns;
1699 }
1700
1701 virtual unsigned int execute (function *);
1702
1703}; // class pass_loop_distribution
1704
1705unsigned int
1706pass_loop_distribution::execute (function *fun)
dea61d92
SP
1707{
1708 struct loop *loop;
c014f6f5 1709 bool changed = false;
1fa0c180 1710 basic_block bb;
36875e8f 1711 control_dependences *cd = NULL;
1fa0c180 1712
be55bfe6 1713 FOR_ALL_BB_FN (bb, fun)
1fa0c180
RG
1714 {
1715 gimple_stmt_iterator gsi;
1716 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1717 gimple_set_uid (gsi_stmt (gsi), -1);
1718 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1719 gimple_set_uid (gsi_stmt (gsi), -1);
1720 }
dea61d92 1721
c014f6f5
RG
1722 /* We can at the moment only distribute non-nested loops, thus restrict
1723 walking to innermost loops. */
f0bd40b1 1724 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
dea61d92 1725 {
ef062b13 1726 auto_vec<gimple> work_list;
be6b029b 1727 basic_block *bbs;
0e20c89f 1728 int num = loop->num;
be6b029b 1729 unsigned int i;
a3357f7d
RG
1730
1731 /* If the loop doesn't have a single exit we will fail anyway,
1732 so do that early. */
1733 if (!single_exit (loop))
1734 continue;
dea61d92 1735
f56f2d33
JH
1736 /* Only optimize hot loops. */
1737 if (!optimize_loop_for_speed_p (loop))
1738 continue;
1739
be6b029b
RG
1740 /* Initialize the worklist with stmts we seed the partitions with. */
1741 bbs = get_loop_body_in_dom_order (loop);
1742 for (i = 0; i < loop->num_nodes; ++i)
1743 {
1744 gimple_stmt_iterator gsi;
deb6c11a
RB
1745 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1746 {
1747 gimple phi = gsi_stmt (gsi);
1748 if (virtual_operand_p (gimple_phi_result (phi)))
1749 continue;
1750 /* Distribute stmts which have defs that are used outside of
be55bfe6 1751 the loop. */
deb6c11a
RB
1752 if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
1753 continue;
1754 work_list.safe_push (phi);
1755 }
be6b029b
RG
1756 for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1757 {
1758 gimple stmt = gsi_stmt (gsi);
83a95546
RB
1759
1760 /* If there is a stmt with side-effects bail out - we
be55bfe6 1761 cannot and should not distribute this loop. */
83a95546
RB
1762 if (gimple_has_side_effects (stmt))
1763 {
1764 work_list.truncate (0);
1765 goto out;
1766 }
1767
b9fc0497 1768 /* Distribute stmts which have defs that are used outside of
be55bfe6 1769 the loop. */
b9fc0497
RB
1770 if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
1771 ;
1772 /* Otherwise only distribute stores for now. */
e179190c 1773 else if (!gimple_vdef (stmt))
be6b029b
RG
1774 continue;
1775
9771b263 1776 work_list.safe_push (stmt);
be6b029b
RG
1777 }
1778 }
83a95546 1779out:
be6b029b 1780 free (bbs);
c014f6f5 1781
826a536d
RB
1782 int nb_generated_loops = 0;
1783 int nb_generated_calls = 0;
1784 location_t loc = find_loop_location (loop);
9771b263 1785 if (work_list.length () > 0)
36875e8f
RB
1786 {
1787 if (!cd)
1788 {
ca406576 1789 calculate_dominance_info (CDI_DOMINATORS);
36875e8f
RB
1790 calculate_dominance_info (CDI_POST_DOMINATORS);
1791 cd = new control_dependences (create_edge_list ());
1792 free_dominance_info (CDI_POST_DOMINATORS);
1793 }
826a536d
RB
1794 nb_generated_loops = distribute_loop (loop, work_list, cd,
1795 &nb_generated_calls);
36875e8f 1796 }
c014f6f5 1797
826a536d 1798 if (nb_generated_loops + nb_generated_calls > 0)
dea61d92 1799 {
826a536d
RB
1800 changed = true;
1801 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
1802 loc, "Loop %d distributed: split to %d loops "
1803 "and %d library calls.\n",
1804 num, nb_generated_loops, nb_generated_calls);
dea61d92 1805 }
826a536d
RB
1806 else if (dump_file && (dump_flags & TDF_DETAILS))
1807 fprintf (dump_file, "Loop %d is the same.\n", num);
dea61d92
SP
1808 }
1809
36875e8f
RB
1810 if (cd)
1811 delete cd;
1812
c014f6f5
RG
1813 if (changed)
1814 {
be55bfe6 1815 mark_virtual_operands_for_renaming (fun);
c014f6f5
RG
1816 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1817 }
1818
1819#ifdef ENABLE_CHECKING
1820 verify_loop_structure ();
1821#endif
1822
5006671f 1823 return 0;
dea61d92
SP
1824}
1825
27a4cd48
DM
1826} // anon namespace
1827
1828gimple_opt_pass *
1829make_pass_loop_distribution (gcc::context *ctxt)
1830{
1831 return new pass_loop_distribution (ctxt);
1832}