OSDN Git Service

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