OSDN Git Service

* tree-vrp.c (execute_vrp): Do not pass loops structure through
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-ivcanon.c
1 /* Induction variable canonicalization.
2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3    
4 This file is part of GCC.
5    
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10    
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15    
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA.  */
20
21 /* This pass detects the loops that iterate a constant number of times,
22    adds a canonical induction variable (step -1, tested against 0) 
23    and replaces the exit test.  This enables the less powerful rtl
24    level analysis to use this information.
25
26    This might spoil the code in some cases (by increasing register pressure).
27    Note that in the case the new variable is not needed, ivopts will get rid
28    of it, so it might only be a problem when there are no other linear induction
29    variables.  In that case the created optimization possibilities are likely
30    to pay up.
31
32    Additionally in case we detect that it is beneficial to unroll the
33    loop completely, we do it right here to expose the optimization
34    possibilities to the following passes.  */
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "tree.h"
41 #include "rtl.h"
42 #include "tm_p.h"
43 #include "hard-reg-set.h"
44 #include "basic-block.h"
45 #include "output.h"
46 #include "diagnostic.h"
47 #include "tree-flow.h"
48 #include "tree-dump.h"
49 #include "cfgloop.h"
50 #include "tree-pass.h"
51 #include "ggc.h"
52 #include "tree-chrec.h"
53 #include "tree-scalar-evolution.h"
54 #include "params.h"
55 #include "flags.h"
56 #include "tree-inline.h"
57
58 /* Specifies types of loops that may be unrolled.  */
59
60 enum unroll_level
61 {
62   UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
63                            iteration.  */
64   UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
65                            of code size.  */
66   UL_ALL                /* All suitable loops.  */
67 };
68
69 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
70    is the exit edge whose condition is replaced.  */
71
72 static void
73 create_canonical_iv (struct loop *loop, edge exit, tree niter)
74 {
75   edge in;
76   tree cond, type, var;
77   block_stmt_iterator incr_at;
78   enum tree_code cmp;
79
80   if (dump_file && (dump_flags & TDF_DETAILS))
81     {
82       fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
83       print_generic_expr (dump_file, niter, TDF_SLIM);
84       fprintf (dump_file, " iterations.\n");
85     }
86
87   cond = last_stmt (exit->src);
88   in = EDGE_SUCC (exit->src, 0);
89   if (in == exit)
90     in = EDGE_SUCC (exit->src, 1);
91
92   /* Note that we do not need to worry about overflows, since
93      type of niter is always unsigned and all comparisons are
94      just for equality/nonequality -- i.e. everything works
95      with a modulo arithmetics.  */
96
97   type = TREE_TYPE (niter);
98   niter = fold_build2 (PLUS_EXPR, type,
99                        niter,
100                        build_int_cst (type, 1));
101   incr_at = bsi_last (in->src);
102   create_iv (niter,
103              build_int_cst (type, -1),
104              NULL_TREE, loop,
105              &incr_at, false, NULL, &var);
106
107   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
108   COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
109                                   var,
110                                   build_int_cst (type, 0));
111   update_stmt (cond);
112 }
113
114 /* Computes an estimated number of insns in LOOP.  */
115
116 unsigned
117 tree_num_loop_insns (struct loop *loop)
118 {
119   basic_block *body = get_loop_body (loop);
120   block_stmt_iterator bsi;
121   unsigned size = 1, i;
122
123   for (i = 0; i < loop->num_nodes; i++)
124     for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
125       size += estimate_num_insns (bsi_stmt (bsi));
126   free (body);
127
128   return size;
129 }
130
131 /* Estimate number of insns of completely unrolled loop.  We assume
132    that the size of the unrolled loop is decreased in the
133    following way (the numbers of insns are based on what
134    estimate_num_insns returns for appropriate statements):
135
136    1) exit condition gets removed (2 insns)
137    2) increment of the control variable gets removed (2 insns)
138    3) All remaining statements are likely to get simplified
139       due to constant propagation.  Hard to estimate; just
140       as a heuristics we decrease the rest by 1/3.
141
142    NINSNS is the number of insns in the loop before unrolling.
143    NUNROLL is the number of times the loop is unrolled.  */
144
145 static unsigned HOST_WIDE_INT
146 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
147                          unsigned HOST_WIDE_INT nunroll)
148 {
149   HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
150   if (unr_insns <= 0)
151     unr_insns = 1;
152   unr_insns *= (nunroll + 1);
153
154   return unr_insns;
155 }
156
157 /* Tries to unroll LOOP completely, i.e. NITER times.
158    UL determines which loops we are allowed to unroll. 
159    EXIT is the exit of the loop that should be eliminated.  */
160
161 static bool
162 try_unroll_loop_completely (struct loop *loop,
163                             edge exit, tree niter,
164                             enum unroll_level ul)
165 {
166   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
167   tree old_cond, cond, dont_exit, do_exit;
168
169   if (loop->inner)
170     return false;
171
172   if (!host_integerp (niter, 1))
173     return false;
174   n_unroll = tree_low_cst (niter, 1);
175
176   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
177   if (n_unroll > max_unroll)
178     return false;
179
180   if (n_unroll)
181     {
182       if (ul == UL_SINGLE_ITER)
183         return false;
184
185       ninsns = tree_num_loop_insns (loop);
186
187       if (n_unroll * ninsns
188           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
189         return false;
190
191       if (ul == UL_NO_GROWTH)
192         {
193           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
194           
195           if (dump_file && (dump_flags & TDF_DETAILS))
196             {
197               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
198               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
199                        (int) unr_insns);
200             }
201           
202           if (unr_insns > ninsns)
203             {
204               if (dump_file && (dump_flags & TDF_DETAILS))
205                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
206               return false;
207             }
208         }
209     }
210
211   if (exit->flags & EDGE_TRUE_VALUE)
212     {
213       dont_exit = boolean_false_node;
214       do_exit = boolean_true_node;
215     }
216   else
217     {
218       dont_exit = boolean_true_node;
219       do_exit = boolean_false_node;
220     }
221   cond = last_stmt (exit->src);
222     
223   if (n_unroll)
224     {
225       sbitmap wont_exit;
226       edge *edges_to_remove = XNEWVEC (edge, n_unroll);
227       unsigned int n_to_remove = 0;
228
229       old_cond = COND_EXPR_COND (cond);
230       COND_EXPR_COND (cond) = dont_exit;
231       update_stmt (cond);
232       initialize_original_copy_tables ();
233
234       wont_exit = sbitmap_alloc (n_unroll + 1);
235       sbitmap_ones (wont_exit);
236       RESET_BIT (wont_exit, 0);
237
238       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
239                                                n_unroll, wont_exit,
240                                                exit, edges_to_remove,
241                                                &n_to_remove,
242                                                DLTHE_FLAG_UPDATE_FREQ
243                                                | DLTHE_FLAG_COMPLETTE_PEEL))
244         {
245           COND_EXPR_COND (cond) = old_cond;
246           update_stmt (cond);
247           free_original_copy_tables ();
248           free (wont_exit);
249           free (edges_to_remove);
250           return false;
251         }
252       free (wont_exit);
253       free (edges_to_remove);
254       free_original_copy_tables ();
255     }
256   
257   COND_EXPR_COND (cond) = do_exit;
258   update_stmt (cond);
259
260   update_ssa (TODO_update_ssa);
261
262   if (dump_file && (dump_flags & TDF_DETAILS))
263     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
264
265   return true;
266 }
267
268 /* Adds a canonical induction variable to LOOP if suitable.
269    CREATE_IV is true if we may create a new iv.  UL determines 
270    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
271    to determine the number of iterations of a loop by direct evaluation. 
272    Returns true if cfg is changed.  */
273
274 static bool
275 canonicalize_loop_induction_variables (struct loop *loop,
276                                        bool create_iv, enum unroll_level ul,
277                                        bool try_eval)
278 {
279   edge exit = NULL;
280   tree niter;
281
282   niter = number_of_iterations_in_loop (loop);
283   if (TREE_CODE (niter) == INTEGER_CST)
284     {
285       exit = single_exit (loop);
286       if (!just_once_each_iteration_p (loop, exit->src))
287         return false;
288
289       /* The result of number_of_iterations_in_loop is by one higher than
290          we expect (i.e. it returns number of executions of the exit
291          condition, not of the loop latch edge).  */
292       niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
293                            build_int_cst (TREE_TYPE (niter), 1));
294     }
295   else
296     {
297       /* If the loop has more than one exit, try checking all of them
298          for # of iterations determinable through scev.  */
299       if (!single_exit (loop))
300         niter = find_loop_niter (loop, &exit);
301
302       /* Finally if everything else fails, try brute force evaluation.  */
303       if (try_eval
304           && (chrec_contains_undetermined (niter)
305               || TREE_CODE (niter) != INTEGER_CST))
306         niter = find_loop_niter_by_eval (loop, &exit);
307
308       if (chrec_contains_undetermined (niter)
309           || TREE_CODE (niter) != INTEGER_CST)
310         return false;
311     }
312
313   if (dump_file && (dump_flags & TDF_DETAILS))
314     {
315       fprintf (dump_file, "Loop %d iterates ", loop->num);
316       print_generic_expr (dump_file, niter, TDF_SLIM);
317       fprintf (dump_file, " times.\n");
318     }
319
320   if (try_unroll_loop_completely (loop, exit, niter, ul))
321     return true;
322
323   if (create_iv)
324     create_canonical_iv (loop, exit, niter);
325
326   return false;
327 }
328
329 /* The main entry point of the pass.  Adds canonical induction variables
330    to the suitable loops.  */
331
332 unsigned int
333 canonicalize_induction_variables (void)
334 {
335   unsigned i;
336   struct loop *loop;
337   bool changed = false;
338   
339   for (i = 1; i < current_loops->num; i++)
340     {
341       loop = current_loops->parray[i];
342
343       if (loop)
344         changed |= canonicalize_loop_induction_variables (loop,
345                                                           true, UL_SINGLE_ITER,
346                                                           true);
347     }
348
349   /* Clean up the information about numbers of iterations, since brute force
350      evaluation could reveal new information.  */
351   scev_reset ();
352
353   if (changed)
354     return TODO_cleanup_cfg;
355   return 0;
356 }
357
358 /* Unroll LOOPS completely if they iterate just few times.  Unless
359    MAY_INCREASE_SIZE is true, perform the unrolling only if the
360    size of the code does not increase.  */
361
362 unsigned int
363 tree_unroll_loops_completely (bool may_increase_size)
364 {
365   unsigned i;
366   struct loop *loop;
367   bool changed = false;
368   enum unroll_level ul;
369
370   for (i = 1; i < current_loops->num; i++)
371     {
372       loop = current_loops->parray[i];
373
374       if (!loop)
375         continue;
376
377       if (may_increase_size && maybe_hot_bb_p (loop->header))
378         ul = UL_ALL;
379       else
380         ul = UL_NO_GROWTH;
381       changed |= canonicalize_loop_induction_variables (loop,
382                                                         false, ul,
383                                                         !flag_tree_loop_ivcanon);
384     }
385
386   /* Clean up the information about numbers of iterations, since complete
387      unrolling might have invalidated it.  */
388   scev_reset ();
389
390   if (changed)
391     return TODO_cleanup_cfg;
392   return 0;
393 }
394
395 /* Checks whether LOOP is empty.  */
396
397 static bool
398 empty_loop_p (struct loop *loop)
399 {
400   edge exit;
401   struct tree_niter_desc niter;
402   tree phi, def;
403   basic_block *body;
404   block_stmt_iterator bsi;
405   unsigned i;
406   tree stmt;
407
408   /* If the loop has multiple exits, it is too hard for us to handle.
409      Similarly, if the exit is not dominating, we cannot determine
410      whether the loop is not infinite.  */
411   exit = single_dom_exit (loop);
412   if (!exit)
413     return false;
414
415   /* The loop must be finite.  */
416   if (!number_of_iterations_exit (loop, exit, &niter, false))
417     return false;
418
419   /* Values of all loop exit phi nodes must be invariants.  */
420   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
421     {
422       if (!is_gimple_reg (PHI_RESULT (phi)))
423         continue;
424
425       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
426
427       if (!expr_invariant_in_loop_p (loop, def))
428         return false;
429     }
430
431   /* And there should be no memory modifying or from other reasons
432      unremovable statements.  */
433   body = get_loop_body (loop);
434   for (i = 0; i < loop->num_nodes; i++)
435     {
436       /* Irreducible region might be infinite.  */
437       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
438         {
439           free (body);
440           return false;
441         }
442         
443       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
444         {
445           stmt = bsi_stmt (bsi);
446           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
447               || stmt_ann (stmt)->has_volatile_ops)
448             {
449               free (body);
450               return false;
451             }
452
453           /* Also, asm statements and calls may have side effects and we
454              cannot change the number of times they are executed.  */
455           switch (TREE_CODE (stmt))
456             {
457             case RETURN_EXPR:
458             case MODIFY_EXPR:
459               stmt = get_call_expr_in (stmt);
460               if (!stmt)
461                 break;
462
463             case CALL_EXPR:
464               if (TREE_SIDE_EFFECTS (stmt))
465                 {
466                   free (body);
467                   return false;
468                 }
469               break;
470
471             case ASM_EXPR:
472               /* We cannot remove volatile assembler.  */
473               if (ASM_VOLATILE_P (stmt))
474                 {
475                   free (body);
476                   return false;
477                 }
478               break;
479
480             default:
481               break;
482             }
483         }
484       }
485   free (body);
486
487   return true;
488 }
489
490 /* Remove LOOP by making it exit in the first iteration.  */
491
492 static void
493 remove_empty_loop (struct loop *loop)
494 {
495   edge exit = single_dom_exit (loop), non_exit;
496   tree cond_stmt = last_stmt (exit->src);
497   tree do_exit;
498   basic_block *body;
499   unsigned n_before, freq_in, freq_h;
500   gcov_type exit_count = exit->count;
501
502   non_exit = EDGE_SUCC (exit->src, 0);
503   if (non_exit == exit)
504     non_exit = EDGE_SUCC (exit->src, 1);
505
506   if (exit->flags & EDGE_TRUE_VALUE)
507     do_exit = boolean_true_node;
508   else
509     do_exit = boolean_false_node;
510
511   COND_EXPR_COND (cond_stmt) = do_exit;
512   update_stmt (cond_stmt);
513
514   /* Let us set the probabilities of the edges coming from the exit block.  */
515   exit->probability = REG_BR_PROB_BASE;
516   non_exit->probability = 0;
517   non_exit->count = 0;
518
519   /* Update frequencies and counts.  Everything before
520      the exit needs to be scaled FREQ_IN/FREQ_H times,
521      where FREQ_IN is the frequency of the entry edge
522      and FREQ_H is the frequency of the loop header.
523      Everything after the exit has zero frequency.  */
524   freq_h = loop->header->frequency;
525   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
526   if (freq_h != 0)
527     {
528       body = get_loop_body_in_dom_order (loop);
529       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
530         if (body[n_before - 1] == exit->src)
531           break;
532       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
533       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
534                                  0, 1);
535       free (body);
536     }
537
538   /* Number of executions of exit is not changed, thus we need to restore
539      the original value.  */
540   exit->count = exit_count;
541 }
542
543 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
544    is set to true if LOOP or any of its subloops is removed.  */
545
546 static bool
547 try_remove_empty_loop (struct loop *loop, bool *changed)
548 {
549   bool nonempty_subloop = false;
550   struct loop *sub;
551
552   /* First, all subloops must be removed.  */
553   for (sub = loop->inner; sub; sub = sub->next)
554     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
555
556   if (nonempty_subloop || !empty_loop_p (loop))
557     return false;
558
559   remove_empty_loop (loop);
560   *changed = true;
561   return true;
562 }
563
564 /* Remove the empty loops.  */
565
566 unsigned int
567 remove_empty_loops (void)
568 {
569   bool changed = false;
570   struct loop *loop;
571
572   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
573     try_remove_empty_loop (loop, &changed);
574
575   if (changed)
576     {
577       scev_reset ();
578       return TODO_cleanup_cfg;
579     }
580   return 0;
581 }