OSDN Git Service

67c3c4149eb7a589095dbfeecef0de00655265a5
[pf3gnuchains/gcc-fork.git] / gcc / tree-loop-distribution.c
1 /* Loop distribution.
2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4    Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
5    and Sebastian Pop <sebastian.pop@amd.com>.
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
12 later version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23 /* This pass performs loop distribution: for example, the loop
24
25    |DO I = 2, N
26    |    A(I) = B(I) + C
27    |    D(I) = A(I-1)*E
28    |ENDDO
29
30    is transformed to
31
32    |DOALL I = 2, N
33    |   A(I) = B(I) + C
34    |ENDDO
35    |
36    |DOALL I = 2, N
37    |   D(I) = A(I-1)*E
38    |ENDDO
39
40    This pass uses an RDG, Reduced Dependence Graph built on top of the
41    data dependence relations.  The RDG is then topologically sorted to
42    obtain a map of information producers/consumers based on which it
43    generates the new loops.  */
44
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "tree-flow.h"
49 #include "cfgloop.h"
50 #include "tree-chrec.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-pass.h"
54
55 /* If bit I is not set, it means that this node represents an
56    operation that has already been performed, and that should not be
57    performed again.  This is the subgraph of remaining important
58    computations that is passed to the DFS algorithm for avoiding to
59    include several times the same stores in different loops.  */
60 static bitmap remaining_stmts;
61
62 /* A node of the RDG is marked in this bitmap when it has as a
63    predecessor a node that writes to memory.  */
64 static bitmap upstream_mem_writes;
65
66 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
67    the LOOP.  */
68
69 static bool
70 ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
71 {
72   imm_use_iterator imm_iter;
73   use_operand_p use_p;
74
75   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
76     if (loop != loop_containing_stmt (USE_STMT (use_p)))
77       return true;
78
79   return false;
80 }
81
82 /* Returns true when STMT defines a scalar variable used after the
83    loop.  */
84
85 static bool
86 stmt_has_scalar_dependences_outside_loop (gimple stmt)
87 {
88   tree name;
89
90   switch (gimple_code (stmt))
91     {
92     case GIMPLE_CALL:
93     case GIMPLE_ASSIGN:
94       name = gimple_get_lhs (stmt);
95       break;
96
97     case GIMPLE_PHI:
98       name = gimple_phi_result (stmt);
99       break;
100
101     default:
102       return false;
103     }
104
105   return (name
106           && TREE_CODE (name) == SSA_NAME
107           && ssa_name_has_uses_outside_loop_p (name,
108                                                loop_containing_stmt (stmt)));
109 }
110
111 /* Update the PHI nodes of NEW_LOOP.  NEW_LOOP is a duplicate of
112    ORIG_LOOP.  */
113
114 static void
115 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
116 {
117   tree new_ssa_name;
118   gimple_stmt_iterator si_new, si_orig;
119   edge orig_loop_latch = loop_latch_edge (orig_loop);
120   edge orig_entry_e = loop_preheader_edge (orig_loop);
121   edge new_loop_entry_e = loop_preheader_edge (new_loop);
122
123   /* Scan the phis in the headers of the old and new loops
124      (they are organized in exactly the same order).  */
125   for (si_new = gsi_start_phis (new_loop->header),
126        si_orig = gsi_start_phis (orig_loop->header);
127        !gsi_end_p (si_new) && !gsi_end_p (si_orig);
128        gsi_next (&si_new), gsi_next (&si_orig))
129     {
130       tree def;
131       source_location locus;
132       gimple phi_new = gsi_stmt (si_new);
133       gimple phi_orig = gsi_stmt (si_orig);
134
135       /* Add the first phi argument for the phi in NEW_LOOP (the one
136          associated with the entry of NEW_LOOP)  */
137       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
138       locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
139       add_phi_arg (phi_new, def, new_loop_entry_e, locus);
140
141       /* Add the second phi argument for the phi in NEW_LOOP (the one
142          associated with the latch of NEW_LOOP)  */
143       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
144       locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
145
146       if (TREE_CODE (def) == SSA_NAME)
147         {
148           new_ssa_name = get_current_def (def);
149
150           if (!new_ssa_name)
151             /* This only happens if there are no definitions inside the
152                loop.  Use the the invariant in the new loop as is.  */
153             new_ssa_name = def;
154         }
155       else
156         /* Could be an integer.  */
157         new_ssa_name = def;
158
159       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
160     }
161 }
162
163 /* Return a copy of LOOP placed before LOOP.  */
164
165 static struct loop *
166 copy_loop_before (struct loop *loop)
167 {
168   struct loop *res;
169   edge preheader = loop_preheader_edge (loop);
170
171   if (!single_exit (loop))
172     return NULL;
173
174   initialize_original_copy_tables ();
175   res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
176   free_original_copy_tables ();
177
178   if (!res)
179     return NULL;
180
181   update_phis_for_loop_copy (loop, res);
182   rename_variables_in_loop (res);
183
184   return res;
185 }
186
187 /* Creates an empty basic block after LOOP.  */
188
189 static void
190 create_bb_after_loop (struct loop *loop)
191 {
192   edge exit = single_exit (loop);
193
194   if (!exit)
195     return;
196
197   split_edge (exit);
198 }
199
200 /* Generate code for PARTITION from the code in LOOP.  The loop is
201    copied when COPY_P is true.  All the statements not flagged in the
202    PARTITION bitmap are removed from the loop or from its copy.  The
203    statements are indexed in sequence inside a basic block, and the
204    basic blocks of a loop are taken in dom order.  Returns true when
205    the code gen succeeded. */
206
207 static bool
208 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
209 {
210   unsigned i, x;
211   gimple_stmt_iterator bsi;
212   basic_block *bbs;
213
214   if (copy_p)
215     {
216       loop = copy_loop_before (loop);
217       create_preheader (loop, CP_SIMPLE_PREHEADERS);
218       create_bb_after_loop (loop);
219     }
220
221   if (loop == NULL)
222     return false;
223
224   /* Remove stmts not in the PARTITION bitmap.  The order in which we
225      visit the phi nodes and the statements is exactly as in
226      stmts_from_loop.  */
227   bbs = get_loop_body_in_dom_order (loop);
228
229   if (MAY_HAVE_DEBUG_STMTS)
230     for (x = 0, i = 0; i < loop->num_nodes; i++)
231       {
232         basic_block bb = bbs[i];
233
234         for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
235           if (!bitmap_bit_p (partition, x++))
236             reset_debug_uses (gsi_stmt (bsi));
237
238         for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
239           {
240             gimple stmt = gsi_stmt (bsi);
241             if (gimple_code (stmt) != GIMPLE_LABEL
242                 && !is_gimple_debug (stmt)
243                 && !bitmap_bit_p (partition, x++))
244               reset_debug_uses (stmt);
245           }
246       }
247
248   for (x = 0, i = 0; i < loop->num_nodes; i++)
249     {
250       basic_block bb = bbs[i];
251
252       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
253         if (!bitmap_bit_p (partition, x++))
254           {
255             gimple phi = gsi_stmt (bsi);
256             if (!is_gimple_reg (gimple_phi_result (phi)))
257               mark_virtual_phi_result_for_renaming (phi);
258             remove_phi_node (&bsi, true);
259           }
260         else
261           gsi_next (&bsi);
262
263       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
264         {
265           gimple stmt = gsi_stmt (bsi);
266           if (gimple_code (stmt) != GIMPLE_LABEL
267               && !is_gimple_debug (stmt)
268               && !bitmap_bit_p (partition, x++))
269             {
270               unlink_stmt_vdef (stmt);
271               gsi_remove (&bsi, true);
272               release_defs (stmt);
273             }
274           else
275             gsi_next (&bsi);
276         }
277     }
278
279   free (bbs);
280   return true;
281 }
282
283 /* Build the size argument for a memset call.  */
284
285 static inline tree
286 build_size_arg_loc (location_t loc, tree nb_iter, tree op,
287                     gimple_seq *stmt_list)
288 {
289   gimple_seq stmts;
290   tree x = fold_build2_loc (loc, MULT_EXPR, size_type_node,
291                             fold_convert_loc (loc, size_type_node, nb_iter),
292                             fold_convert_loc (loc, size_type_node,
293                                               TYPE_SIZE_UNIT (TREE_TYPE (op))));
294   x = force_gimple_operand (x, &stmts, true, NULL);
295   gimple_seq_add_seq (stmt_list, stmts);
296
297   return x;
298 }
299
300 /* Generate a call to memset.  Return true when the operation succeeded.  */
301
302 static void
303 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
304                       gimple_stmt_iterator bsi)
305 {
306   tree addr_base, nb_bytes;
307   bool res = false;
308   gimple_seq stmt_list = NULL, stmts;
309   gimple fn_call;
310   tree mem, fn;
311   struct data_reference *dr = XCNEW (struct data_reference);
312   location_t loc = gimple_location (stmt);
313
314   DR_STMT (dr) = stmt;
315   DR_REF (dr) = op0;
316   res = dr_analyze_innermost (dr, loop_containing_stmt (stmt));
317   gcc_assert (res && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0)));
318
319   nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
320   addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
321   addr_base = fold_convert_loc (loc, sizetype, addr_base);
322
323   /* Test for a negative stride, iterating over every element.  */
324   if (tree_int_cst_sgn (DR_STEP (dr)) == -1)
325     {
326       addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
327                                   fold_convert_loc (loc, sizetype, nb_bytes));
328       addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
329                                   TYPE_SIZE_UNIT (TREE_TYPE (op0)));
330     }
331
332   addr_base = fold_build_pointer_plus_loc (loc,
333                                            DR_BASE_ADDRESS (dr), addr_base);
334   mem = force_gimple_operand (addr_base, &stmts, true, NULL);
335   gimple_seq_add_seq (&stmt_list, stmts);
336
337   fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
338   fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
339   gimple_seq_add_stmt (&stmt_list, fn_call);
340   gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
341
342   if (dump_file && (dump_flags & TDF_DETAILS))
343     fprintf (dump_file, "generated memset zero\n");
344
345   free_data_ref (dr);
346 }
347
348 /* Tries to generate a builtin function for the instructions of LOOP
349    pointed to by the bits set in PARTITION.  Returns true when the
350    operation succeeded.  */
351
352 static bool
353 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
354 {
355   bool res = false;
356   unsigned i, x = 0;
357   basic_block *bbs;
358   gimple write = NULL;
359   gimple_stmt_iterator bsi;
360   tree nb_iter = number_of_exit_cond_executions (loop);
361
362   if (!nb_iter || nb_iter == chrec_dont_know)
363     return false;
364
365   bbs = get_loop_body_in_dom_order (loop);
366
367   for (i = 0; i < loop->num_nodes; i++)
368     {
369       basic_block bb = bbs[i];
370
371       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
372         x++;
373
374       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
375         {
376           gimple stmt = gsi_stmt (bsi);
377
378           if (gimple_code (stmt) == GIMPLE_LABEL
379               || is_gimple_debug (stmt))
380             continue;
381
382           if (!bitmap_bit_p (partition, x++))
383             continue;
384
385           /* If the stmt has uses outside of the loop fail.  */
386           if (stmt_has_scalar_dependences_outside_loop (stmt))
387             goto end;
388
389           if (is_gimple_assign (stmt)
390               && !is_gimple_reg (gimple_assign_lhs (stmt)))
391             {
392               /* Don't generate the builtins when there are more than
393                  one memory write.  */
394               if (write != NULL)
395                 goto end;
396
397               write = stmt;
398               if (bb == loop->latch)
399                 nb_iter = number_of_latch_executions (loop);
400             }
401         }
402     }
403
404   if (!stmt_with_adjacent_zero_store_dr_p (write))
405     goto end;
406
407   /* The new statements will be placed before LOOP.  */
408   bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
409   generate_memset_zero (write, gimple_assign_lhs (write), nb_iter, bsi);
410   res = true;
411
412   /* If this is the last partition for which we generate code, we have
413      to destroy the loop.  */
414   if (!copy_p)
415     {
416       unsigned nbbs = loop->num_nodes;
417       edge exit = single_exit (loop);
418       basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
419       redirect_edge_pred (exit, src);
420       exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
421       exit->flags |= EDGE_FALLTHRU;
422       cancel_loop_tree (loop);
423       rescan_loop_exit (exit, false, true);
424
425       for (i = 0; i < nbbs; i++)
426         delete_basic_block (bbs[i]);
427
428       set_immediate_dominator (CDI_DOMINATORS, dest,
429                                recompute_dominator (CDI_DOMINATORS, dest));
430     }
431
432  end:
433   free (bbs);
434   return res;
435 }
436
437 /* Generates code for PARTITION.  For simple loops, this function can
438    generate a built-in.  */
439
440 static bool
441 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
442 {
443   if (generate_builtin (loop, partition, copy_p))
444     return true;
445
446   return generate_loops_for_partition (loop, partition, copy_p);
447 }
448
449
450 /* Returns true if the node V of RDG cannot be recomputed.  */
451
452 static bool
453 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
454 {
455   if (RDG_MEM_WRITE_STMT (rdg, v))
456     return true;
457
458   return false;
459 }
460
461 /* Returns true when the vertex V has already been generated in the
462    current partition (V is in PROCESSED), or when V belongs to another
463    partition and cannot be recomputed (V is not in REMAINING_STMTS).  */
464
465 static inline bool
466 already_processed_vertex_p (bitmap processed, int v)
467 {
468   return (bitmap_bit_p (processed, v)
469           || !bitmap_bit_p (remaining_stmts, v));
470 }
471
472 /* Returns NULL when there is no anti-dependence among the successors
473    of vertex V, otherwise returns the edge with the anti-dep.  */
474
475 static struct graph_edge *
476 has_anti_dependence (struct vertex *v)
477 {
478   struct graph_edge *e;
479
480   if (v->succ)
481     for (e = v->succ; e; e = e->succ_next)
482       if (RDGE_TYPE (e) == anti_dd)
483         return e;
484
485   return NULL;
486 }
487
488 /* Returns true when V has an anti-dependence edge among its successors.  */
489
490 static bool
491 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
492 {
493   struct graph_edge *e;
494
495   if (v->pred)
496     for (e = v->pred; e; e = e->pred_next)
497       if (bitmap_bit_p (upstream_mem_writes, e->src)
498           /* Don't consider flow channels: a write to memory followed
499              by a read from memory.  These channels allow the split of
500              the RDG in different partitions.  */
501           && !RDG_MEM_WRITE_STMT (rdg, e->src))
502         return true;
503
504   return false;
505 }
506
507 /* Initializes the upstream_mem_writes bitmap following the
508    information from RDG.  */
509
510 static void
511 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
512 {
513   int v, x;
514   bitmap seen = BITMAP_ALLOC (NULL);
515
516   for (v = rdg->n_vertices - 1; v >= 0; v--)
517     if (!bitmap_bit_p (seen, v))
518       {
519         unsigned i;
520         VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
521
522         graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
523
524         FOR_EACH_VEC_ELT (int, nodes, i, x)
525           {
526             if (!bitmap_set_bit (seen, x))
527               continue;
528
529             if (RDG_MEM_WRITE_STMT (rdg, x)
530                 || predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
531                 /* In anti dependences the read should occur before
532                    the write, this is why both the read and the write
533                    should be placed in the same partition.  */
534                 || has_anti_dependence (&(rdg->vertices[x])))
535               {
536                 bitmap_set_bit (upstream_mem_writes, x);
537               }
538           }
539
540         VEC_free (int, heap, nodes);
541       }
542 }
543
544 /* Returns true when vertex u has a memory write node as a predecessor
545    in RDG.  */
546
547 static bool
548 has_upstream_mem_writes (int u)
549 {
550   return bitmap_bit_p (upstream_mem_writes, u);
551 }
552
553 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
554                                            bitmap, bool *);
555
556 /* Flag the uses of U stopping following the information from
557    upstream_mem_writes.  */
558
559 static void
560 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
561                bitmap processed, bool *part_has_writes)
562 {
563   use_operand_p use_p;
564   struct vertex *x = &(rdg->vertices[u]);
565   gimple stmt = RDGV_STMT (x);
566   struct graph_edge *anti_dep = has_anti_dependence (x);
567
568   /* Keep in the same partition the destination of an antidependence,
569      because this is a store to the exact same location.  Putting this
570      in another partition is bad for cache locality.  */
571   if (anti_dep)
572     {
573       int v = anti_dep->dest;
574
575       if (!already_processed_vertex_p (processed, v))
576         rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
577                                        processed, part_has_writes);
578     }
579
580   if (gimple_code (stmt) != GIMPLE_PHI)
581     {
582       if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)
583         {
584           tree use = USE_FROM_PTR (use_p);
585
586           if (TREE_CODE (use) == SSA_NAME)
587             {
588               gimple def_stmt = SSA_NAME_DEF_STMT (use);
589               int v = rdg_vertex_for_stmt (rdg, def_stmt);
590
591               if (v >= 0
592                   && !already_processed_vertex_p (processed, v))
593                 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
594                                                processed, part_has_writes);
595             }
596         }
597     }
598
599   if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
600     {
601       tree op0 = gimple_assign_lhs (stmt);
602
603       /* Scalar channels don't have enough space for transmitting data
604          between tasks, unless we add more storage by privatizing.  */
605       if (is_gimple_reg (op0))
606         {
607           use_operand_p use_p;
608           imm_use_iterator iter;
609
610           FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
611             {
612               int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
613
614               if (!already_processed_vertex_p (processed, v))
615                 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
616                                                processed, part_has_writes);
617             }
618         }
619     }
620 }
621
622 /* Flag V from RDG as part of PARTITION, and also flag its loop number
623    in LOOPS.  */
624
625 static void
626 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
627                  bool *part_has_writes)
628 {
629   struct loop *loop;
630
631   if (!bitmap_set_bit (partition, v))
632     return;
633
634   loop = loop_containing_stmt (RDG_STMT (rdg, v));
635   bitmap_set_bit (loops, loop->num);
636
637   if (rdg_cannot_recompute_vertex_p (rdg, v))
638     {
639       *part_has_writes = true;
640       bitmap_clear_bit (remaining_stmts, v);
641     }
642 }
643
644 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
645    Also flag their loop number in LOOPS.  */
646
647 static void
648 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
649                                bitmap loops, bitmap processed,
650                                bool *part_has_writes)
651 {
652   unsigned i;
653   VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
654   int x;
655
656   bitmap_set_bit (processed, v);
657   rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
658   graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
659   rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
660
661   FOR_EACH_VEC_ELT (int, nodes, i, x)
662     if (!already_processed_vertex_p (processed, x))
663       rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
664                                      part_has_writes);
665
666   VEC_free (int, heap, nodes);
667 }
668
669 /* Initialize CONDS with all the condition statements from the basic
670    blocks of LOOP.  */
671
672 static void
673 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
674 {
675   unsigned i;
676   edge e;
677   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
678
679   FOR_EACH_VEC_ELT (edge, exits, i, e)
680     {
681       gimple cond = last_stmt (e->src);
682
683       if (cond)
684         VEC_safe_push (gimple, heap, *conds, cond);
685     }
686
687   VEC_free (edge, heap, exits);
688 }
689
690 /* Add to PARTITION all the exit condition statements for LOOPS
691    together with all their dependent statements determined from
692    RDG.  */
693
694 static void
695 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
696                      bitmap processed, bool *part_has_writes)
697 {
698   unsigned i;
699   bitmap_iterator bi;
700   VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
701
702   EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
703     collect_condition_stmts (get_loop (i), &conds);
704
705   while (!VEC_empty (gimple, conds))
706     {
707       gimple cond = VEC_pop (gimple, conds);
708       int v = rdg_vertex_for_stmt (rdg, cond);
709       bitmap new_loops = BITMAP_ALLOC (NULL);
710
711       if (!already_processed_vertex_p (processed, v))
712         rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
713                                        part_has_writes);
714
715       EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
716         if (bitmap_set_bit (loops, i))
717           collect_condition_stmts (get_loop (i), &conds);
718
719       BITMAP_FREE (new_loops);
720     }
721
722   VEC_free (gimple, heap, conds);
723 }
724
725 /* Returns a bitmap in which all the statements needed for computing
726    the strongly connected component C of the RDG are flagged, also
727    including the loop exit conditions.  */
728
729 static bitmap
730 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
731                                    bool *part_has_writes)
732 {
733   int i, v;
734   bitmap partition = BITMAP_ALLOC (NULL);
735   bitmap loops = BITMAP_ALLOC (NULL);
736   bitmap processed = BITMAP_ALLOC (NULL);
737
738   FOR_EACH_VEC_ELT (int, c->vertices, i, v)
739     if (!already_processed_vertex_p (processed, v))
740       rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
741                                      part_has_writes);
742
743   rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
744
745   BITMAP_FREE (processed);
746   BITMAP_FREE (loops);
747   return partition;
748 }
749
750 /* Free memory for COMPONENTS.  */
751
752 static void
753 free_rdg_components (VEC (rdgc, heap) *components)
754 {
755   int i;
756   rdgc x;
757
758   FOR_EACH_VEC_ELT (rdgc, components, i, x)
759     {
760       VEC_free (int, heap, x->vertices);
761       free (x);
762     }
763
764   VEC_free (rdgc, heap, components);
765 }
766
767 /* Build the COMPONENTS vector with the strongly connected components
768    of RDG in which the STARTING_VERTICES occur.  */
769
770 static void
771 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
772                       VEC (rdgc, heap) **components)
773 {
774   int i, v;
775   bitmap saved_components = BITMAP_ALLOC (NULL);
776   int n_components = graphds_scc (rdg, NULL);
777   VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
778
779   for (i = 0; i < n_components; i++)
780     all_components[i] = VEC_alloc (int, heap, 3);
781
782   for (i = 0; i < rdg->n_vertices; i++)
783     VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
784
785   FOR_EACH_VEC_ELT (int, starting_vertices, i, v)
786     {
787       int c = rdg->vertices[v].component;
788
789       if (bitmap_set_bit (saved_components, c))
790         {
791           rdgc x = XCNEW (struct rdg_component);
792           x->num = c;
793           x->vertices = all_components[c];
794
795           VEC_safe_push (rdgc, heap, *components, x);
796         }
797     }
798
799   for (i = 0; i < n_components; i++)
800     if (!bitmap_bit_p (saved_components, i))
801       VEC_free (int, heap, all_components[i]);
802
803   free (all_components);
804   BITMAP_FREE (saved_components);
805 }
806
807 /* Returns true when it is possible to generate a builtin pattern for
808    the PARTITION of RDG.  For the moment we detect only the memset
809    zero pattern.  */
810
811 static bool
812 can_generate_builtin (struct graph *rdg, bitmap partition)
813 {
814   unsigned i;
815   bitmap_iterator bi;
816   int nb_reads = 0;
817   int nb_writes = 0;
818   int stores_zero = 0;
819
820   EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, bi)
821     if (RDG_MEM_READS_STMT (rdg, i))
822       nb_reads++;
823     else if (RDG_MEM_WRITE_STMT (rdg, i))
824       {
825         nb_writes++;
826         if (stmt_with_adjacent_zero_store_dr_p (RDG_STMT (rdg, i)))
827           stores_zero++;
828       }
829
830   return stores_zero == 1 && nb_writes == 1 && nb_reads == 0;
831 }
832
833 /* Returns true when PARTITION1 and PARTITION2 have similar memory
834    accesses in RDG.  */
835
836 static bool
837 similar_memory_accesses (struct graph *rdg, bitmap partition1,
838                          bitmap partition2)
839 {
840   unsigned i, j;
841   bitmap_iterator bi, bj;
842
843   EXECUTE_IF_SET_IN_BITMAP (partition1, 0, i, bi)
844     if (RDG_MEM_WRITE_STMT (rdg, i)
845         || RDG_MEM_READS_STMT (rdg, i))
846       EXECUTE_IF_SET_IN_BITMAP (partition2, 0, j, bj)
847         if (RDG_MEM_WRITE_STMT (rdg, j)
848             || RDG_MEM_READS_STMT (rdg, j))
849           if (rdg_has_similar_memory_accesses (rdg, i, j))
850             return true;
851
852   return false;
853 }
854
855 /* Fuse all the partitions from PARTITIONS that contain similar memory
856    references, i.e., we're taking care of cache locality.  This
857    function does not fuse those partitions that contain patterns that
858    can be code generated with builtins.  */
859
860 static void
861 fuse_partitions_with_similar_memory_accesses (struct graph *rdg,
862                                               VEC (bitmap, heap) **partitions)
863 {
864   int p1, p2;
865   bitmap partition1, partition2;
866
867   FOR_EACH_VEC_ELT (bitmap, *partitions, p1, partition1)
868     if (!can_generate_builtin (rdg, partition1))
869       FOR_EACH_VEC_ELT (bitmap, *partitions, p2, partition2)
870         if (p1 != p2
871             && !can_generate_builtin (rdg, partition2)
872             && similar_memory_accesses (rdg, partition1, partition2))
873           {
874             bitmap_ior_into (partition1, partition2);
875             VEC_ordered_remove (bitmap, *partitions, p2);
876             p2--;
877           }
878 }
879
880 /* Returns true when STMT will be code generated in a partition of RDG
881    different than PART and that will not be code generated as a
882    builtin.  */
883
884 static bool
885 stmt_generated_in_another_partition (struct graph *rdg, gimple stmt, int part,
886                                      VEC (bitmap, heap) *partitions)
887 {
888   int p;
889   bitmap pp;
890   unsigned i;
891   bitmap_iterator bi;
892
893   FOR_EACH_VEC_ELT (bitmap, partitions, p, pp)
894     if (p != part
895         && !can_generate_builtin (rdg, pp))
896       EXECUTE_IF_SET_IN_BITMAP (pp, 0, i, bi)
897         if (stmt == RDG_STMT (rdg, i))
898           return true;
899
900   return false;
901 }
902
903 /* For each partition in PARTITIONS that will be code generated using
904    a builtin, add its scalar computations used after the loop to
905    PARTITION.  */
906
907 static void
908 add_scalar_computations_to_partition (struct graph *rdg,
909                                       VEC (bitmap, heap) *partitions,
910                                       bitmap partition)
911 {
912   int p;
913   bitmap pp;
914   unsigned i;
915   bitmap_iterator bi;
916   bitmap l = BITMAP_ALLOC (NULL);
917   bitmap pr = BITMAP_ALLOC (NULL);
918   bool f = false;
919
920   FOR_EACH_VEC_ELT (bitmap, partitions, p, pp)
921     if (can_generate_builtin (rdg, pp))
922       EXECUTE_IF_SET_IN_BITMAP (pp, 0, i, bi)
923         if (stmt_has_scalar_dependences_outside_loop (RDG_STMT (rdg, i))
924             && !stmt_generated_in_another_partition (rdg, RDG_STMT (rdg, i), p,
925                                                      partitions))
926           rdg_flag_vertex_and_dependent (rdg, i, partition, l, pr, &f);
927
928   rdg_flag_loop_exits (rdg, l, partition, pr, &f);
929
930   BITMAP_FREE (pr);
931   BITMAP_FREE (l);
932 }
933
934 /* Aggregate several components into a useful partition that is
935    registered in the PARTITIONS vector.  Partitions will be
936    distributed in different loops.  */
937
938 static void
939 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
940                       VEC (int, heap) **other_stores,
941                       VEC (bitmap, heap) **partitions, bitmap processed)
942 {
943   int i;
944   rdgc x;
945   bitmap partition = BITMAP_ALLOC (NULL);
946
947   FOR_EACH_VEC_ELT (rdgc, components, i, x)
948     {
949       bitmap np;
950       bool part_has_writes = false;
951       int v = VEC_index (int, x->vertices, 0);
952
953       if (bitmap_bit_p (processed, v))
954         continue;
955
956       np = build_rdg_partition_for_component (rdg, x, &part_has_writes);
957       bitmap_ior_into (partition, np);
958       bitmap_ior_into (processed, np);
959       BITMAP_FREE (np);
960
961       if (part_has_writes)
962         {
963           if (dump_file && (dump_flags & TDF_DETAILS))
964             {
965               fprintf (dump_file, "ldist useful partition:\n");
966               dump_bitmap (dump_file, partition);
967             }
968
969           VEC_safe_push (bitmap, heap, *partitions, partition);
970           partition = BITMAP_ALLOC (NULL);
971         }
972     }
973
974   /* Add the nodes from the RDG that were not marked as processed, and
975      that are used outside the current loop.  These are scalar
976      computations that are not yet part of previous partitions.  */
977   for (i = 0; i < rdg->n_vertices; i++)
978     if (!bitmap_bit_p (processed, i)
979         && rdg_defs_used_in_other_loops_p (rdg, i))
980       VEC_safe_push (int, heap, *other_stores, i);
981
982   /* If there are still statements left in the OTHER_STORES array,
983      create other components and partitions with these stores and
984      their dependences.  */
985   if (VEC_length (int, *other_stores) > 0)
986     {
987       VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
988       VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
989
990       rdg_build_components (rdg, *other_stores, &comps);
991       rdg_build_partitions (rdg, comps, &foo, partitions, processed);
992
993       VEC_free (int, heap, foo);
994       free_rdg_components (comps);
995     }
996
997   add_scalar_computations_to_partition (rdg, *partitions, partition);
998
999   /* If there is something left in the last partition, save it.  */
1000   if (bitmap_count_bits (partition) > 0)
1001     VEC_safe_push (bitmap, heap, *partitions, partition);
1002   else
1003     BITMAP_FREE (partition);
1004
1005   fuse_partitions_with_similar_memory_accesses (rdg, partitions);
1006 }
1007
1008 /* Dump to FILE the PARTITIONS.  */
1009
1010 static void
1011 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
1012 {
1013   int i;
1014   bitmap partition;
1015
1016   FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1017     debug_bitmap_file (file, partition);
1018 }
1019
1020 /* Debug PARTITIONS.  */
1021 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
1022
1023 DEBUG_FUNCTION void
1024 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
1025 {
1026   dump_rdg_partitions (stderr, partitions);
1027 }
1028
1029 /* Returns the number of read and write operations in the RDG.  */
1030
1031 static int
1032 number_of_rw_in_rdg (struct graph *rdg)
1033 {
1034   int i, res = 0;
1035
1036   for (i = 0; i < rdg->n_vertices; i++)
1037     {
1038       if (RDG_MEM_WRITE_STMT (rdg, i))
1039         ++res;
1040
1041       if (RDG_MEM_READS_STMT (rdg, i))
1042         ++res;
1043     }
1044
1045   return res;
1046 }
1047
1048 /* Returns the number of read and write operations in a PARTITION of
1049    the RDG.  */
1050
1051 static int
1052 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
1053 {
1054   int res = 0;
1055   unsigned i;
1056   bitmap_iterator ii;
1057
1058   EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
1059     {
1060       if (RDG_MEM_WRITE_STMT (rdg, i))
1061         ++res;
1062
1063       if (RDG_MEM_READS_STMT (rdg, i))
1064         ++res;
1065     }
1066
1067   return res;
1068 }
1069
1070 /* Returns true when one of the PARTITIONS contains all the read or
1071    write operations of RDG.  */
1072
1073 static bool
1074 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
1075 {
1076   int i;
1077   bitmap partition;
1078   int nrw = number_of_rw_in_rdg (rdg);
1079
1080   FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1081     if (nrw == number_of_rw_in_partition (rdg, partition))
1082       return true;
1083
1084   return false;
1085 }
1086
1087 /* Generate code from STARTING_VERTICES in RDG.  Returns the number of
1088    distributed loops.  */
1089
1090 static int
1091 ldist_gen (struct loop *loop, struct graph *rdg,
1092            VEC (int, heap) *starting_vertices)
1093 {
1094   int i, nbp;
1095   VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
1096   VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
1097   VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
1098   bitmap partition, processed = BITMAP_ALLOC (NULL);
1099
1100   remaining_stmts = BITMAP_ALLOC (NULL);
1101   upstream_mem_writes = BITMAP_ALLOC (NULL);
1102
1103   for (i = 0; i < rdg->n_vertices; i++)
1104     {
1105       bitmap_set_bit (remaining_stmts, i);
1106
1107       /* Save in OTHER_STORES all the memory writes that are not in
1108          STARTING_VERTICES.  */
1109       if (RDG_MEM_WRITE_STMT (rdg, i))
1110         {
1111           int v;
1112           unsigned j;
1113           bool found = false;
1114
1115           FOR_EACH_VEC_ELT (int, starting_vertices, j, v)
1116             if (i == v)
1117               {
1118                 found = true;
1119                 break;
1120               }
1121
1122           if (!found)
1123             VEC_safe_push (int, heap, other_stores, i);
1124         }
1125     }
1126
1127   mark_nodes_having_upstream_mem_writes (rdg);
1128   rdg_build_components (rdg, starting_vertices, &components);
1129   rdg_build_partitions (rdg, components, &other_stores, &partitions,
1130                         processed);
1131   BITMAP_FREE (processed);
1132   nbp = VEC_length (bitmap, partitions);
1133
1134   if (nbp <= 1
1135       || partition_contains_all_rw (rdg, partitions))
1136     goto ldist_done;
1137
1138   if (dump_file && (dump_flags & TDF_DETAILS))
1139     dump_rdg_partitions (dump_file, partitions);
1140
1141   FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1142     if (!generate_code_for_partition (loop, partition, i < nbp - 1))
1143       goto ldist_done;
1144
1145   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1146   update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
1147
1148  ldist_done:
1149
1150   BITMAP_FREE (remaining_stmts);
1151   BITMAP_FREE (upstream_mem_writes);
1152
1153   FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1154     BITMAP_FREE (partition);
1155
1156   VEC_free (int, heap, other_stores);
1157   VEC_free (bitmap, heap, partitions);
1158   free_rdg_components (components);
1159   return nbp;
1160 }
1161
1162 /* Distributes the code from LOOP in such a way that producer
1163    statements are placed before consumer statements.  When STMTS is
1164    NULL, performs the maximal distribution, if STMTS is not NULL,
1165    tries to separate only these statements from the LOOP's body.
1166    Returns the number of distributed loops.  */
1167
1168 static int
1169 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
1170 {
1171   int res = 0;
1172   struct graph *rdg;
1173   gimple s;
1174   unsigned i;
1175   VEC (int, heap) *vertices;
1176   VEC (ddr_p, heap) *dependence_relations;
1177   VEC (data_reference_p, heap) *datarefs;
1178   VEC (loop_p, heap) *loop_nest;
1179
1180   if (loop->num_nodes > 2)
1181     {
1182       if (dump_file && (dump_flags & TDF_DETAILS))
1183         fprintf (dump_file,
1184                  "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1185                  loop->num);
1186
1187       return res;
1188     }
1189
1190   datarefs = VEC_alloc (data_reference_p, heap, 10);
1191   dependence_relations = VEC_alloc (ddr_p, heap, 100);
1192   loop_nest = VEC_alloc (loop_p, heap, 3);
1193   rdg = build_rdg (loop, &loop_nest, &dependence_relations, &datarefs);
1194
1195   if (!rdg)
1196     {
1197       if (dump_file && (dump_flags & TDF_DETAILS))
1198         fprintf (dump_file,
1199                  "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1200                  loop->num);
1201
1202       free_dependence_relations (dependence_relations);
1203       free_data_refs (datarefs);
1204       VEC_free (loop_p, heap, loop_nest);
1205       return res;
1206     }
1207
1208   vertices = VEC_alloc (int, heap, 3);
1209
1210   if (dump_file && (dump_flags & TDF_DETAILS))
1211     dump_rdg (dump_file, rdg);
1212
1213   FOR_EACH_VEC_ELT (gimple, stmts, i, s)
1214     {
1215       int v = rdg_vertex_for_stmt (rdg, s);
1216
1217       if (v >= 0)
1218         {
1219           VEC_safe_push (int, heap, vertices, v);
1220
1221           if (dump_file && (dump_flags & TDF_DETAILS))
1222             fprintf (dump_file,
1223                      "ldist asked to generate code for vertex %d\n", v);
1224         }
1225     }
1226
1227   res = ldist_gen (loop, rdg, vertices);
1228   VEC_free (int, heap, vertices);
1229   free_rdg (rdg);
1230   free_dependence_relations (dependence_relations);
1231   free_data_refs (datarefs);
1232   VEC_free (loop_p, heap, loop_nest);
1233   return res;
1234 }
1235
1236 /* Distribute all loops in the current function.  */
1237
1238 static unsigned int
1239 tree_loop_distribution (void)
1240 {
1241   struct loop *loop;
1242   loop_iterator li;
1243   int nb_generated_loops = 0;
1244
1245   FOR_EACH_LOOP (li, loop, 0)
1246     {
1247       VEC (gimple, heap) *work_list = NULL;
1248       int num = loop->num;
1249
1250       /* If the loop doesn't have a single exit we will fail anyway,
1251          so do that early.  */
1252       if (!single_exit (loop))
1253         continue;
1254
1255       /* If both flag_tree_loop_distribute_patterns and
1256          flag_tree_loop_distribution are set, then only
1257          distribute_patterns is executed.  */
1258       if (flag_tree_loop_distribute_patterns)
1259         {
1260           /* With the following working list, we're asking
1261              distribute_loop to separate from the rest of the loop the
1262              stores of the form "A[i] = 0".  */
1263           stores_zero_from_loop (loop, &work_list);
1264
1265           /* Do nothing if there are no patterns to be distributed.  */
1266           if (VEC_length (gimple, work_list) > 0)
1267             nb_generated_loops = distribute_loop (loop, work_list);
1268         }
1269       else if (flag_tree_loop_distribution)
1270         {
1271           /* With the following working list, we're asking
1272              distribute_loop to separate the stores of the loop: when
1273              dependences allow, it will end on having one store per
1274              loop.  */
1275           stores_from_loop (loop, &work_list);
1276
1277           /* A simple heuristic for cache locality is to not split
1278              stores to the same array.  Without this call, an unrolled
1279              loop would be split into as many loops as unroll factor,
1280              each loop storing in the same array.  */
1281           remove_similar_memory_refs (&work_list);
1282
1283           nb_generated_loops = distribute_loop (loop, work_list);
1284         }
1285
1286       if (dump_file && (dump_flags & TDF_DETAILS))
1287         {
1288           if (nb_generated_loops > 1)
1289             fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
1290                      num, nb_generated_loops);
1291           else
1292             fprintf (dump_file, "Loop %d is the same.\n", num);
1293         }
1294
1295       verify_loop_structure ();
1296
1297       VEC_free (gimple, heap, work_list);
1298     }
1299
1300   return 0;
1301 }
1302
1303 static bool
1304 gate_tree_loop_distribution (void)
1305 {
1306   return flag_tree_loop_distribution
1307     || flag_tree_loop_distribute_patterns;
1308 }
1309
1310 struct gimple_opt_pass pass_loop_distribution =
1311 {
1312  {
1313   GIMPLE_PASS,
1314   "ldist",                      /* name */
1315   gate_tree_loop_distribution,  /* gate */
1316   tree_loop_distribution,       /* execute */
1317   NULL,                         /* sub */
1318   NULL,                         /* next */
1319   0,                            /* static_pass_number */
1320   TV_TREE_LOOP_DISTRIBUTION,    /* tv_id */
1321   PROP_cfg | PROP_ssa,          /* properties_required */
1322   0,                            /* properties_provided */
1323   0,                            /* properties_destroyed */
1324   0,                            /* todo_flags_start */
1325   TODO_ggc_collect
1326   | TODO_verify_ssa             /* todo_flags_finish */
1327  }
1328 };