OSDN Git Service

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