OSDN Git Service

PR tree-optimization/22236
[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              fold_convert (type, integer_minus_one_node),
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.  LOOPS is the
158    loop tree.  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 loops *loops ATTRIBUTE_UNUSED,
163                             struct loop *loop,
164                             edge exit, tree niter,
165                             enum unroll_level ul)
166 {
167   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
168   tree old_cond, cond, dont_exit, do_exit;
169
170   if (loop->inner)
171     return false;
172
173   if (!host_integerp (niter, 1))
174     return false;
175   n_unroll = tree_low_cst (niter, 1);
176
177   max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
178   if (n_unroll > max_unroll)
179     return false;
180
181   if (n_unroll)
182     {
183       if (ul == UL_SINGLE_ITER)
184         return false;
185
186       ninsns = tree_num_loop_insns (loop);
187
188       if (n_unroll * ninsns
189           > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
190         return false;
191
192       if (ul == UL_NO_GROWTH)
193         {
194           unr_insns = estimated_unrolled_size (ninsns, n_unroll);
195           
196           if (dump_file && (dump_flags & TDF_DETAILS))
197             {
198               fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
199               fprintf (dump_file, "  Estimated size after unrolling: %d\n",
200                        (int) unr_insns);
201             }
202           
203           if (unr_insns > ninsns)
204             {
205               if (dump_file && (dump_flags & TDF_DETAILS))
206                 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
207               return false;
208             }
209         }
210     }
211
212   if (exit->flags & EDGE_TRUE_VALUE)
213     {
214       dont_exit = boolean_false_node;
215       do_exit = boolean_true_node;
216     }
217   else
218     {
219       dont_exit = boolean_true_node;
220       do_exit = boolean_false_node;
221     }
222   cond = last_stmt (exit->src);
223     
224   if (n_unroll)
225     {
226       sbitmap wont_exit;
227       edge *edges_to_remove = xmalloc (sizeof (edge *) * n_unroll);
228       unsigned int n_to_remove = 0;
229
230       old_cond = COND_EXPR_COND (cond);
231       COND_EXPR_COND (cond) = dont_exit;
232       update_stmt (cond);
233       initialize_original_copy_tables ();
234
235       wont_exit = sbitmap_alloc (n_unroll + 1);
236       sbitmap_ones (wont_exit);
237       RESET_BIT (wont_exit, 0);
238
239       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
240                                                loops, n_unroll, wont_exit,
241                                                exit, edges_to_remove,
242                                                &n_to_remove,
243                                                DLTHE_FLAG_UPDATE_FREQ
244                                                | DLTHE_FLAG_COMPLETTE_PEEL))
245         {
246           COND_EXPR_COND (cond) = old_cond;
247           update_stmt (cond);
248           free_original_copy_tables ();
249           free (wont_exit);
250           free (edges_to_remove);
251           return false;
252         }
253       free (wont_exit);
254       free (edges_to_remove);
255       free_original_copy_tables ();
256     }
257   
258   COND_EXPR_COND (cond) = do_exit;
259   update_stmt (cond);
260
261   update_ssa (TODO_update_ssa);
262
263   if (dump_file && (dump_flags & TDF_DETAILS))
264     fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
265
266   return true;
267 }
268
269 /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
270    tree.  CREATE_IV is true if we may create a new iv.  UL determines 
271    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
272    to determine the number of iterations of a loop by direct evaluation. 
273    Returns true if cfg is changed.  */
274
275 static bool
276 canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
277                                        bool create_iv, enum unroll_level ul,
278                                        bool try_eval)
279 {
280   edge exit = NULL;
281   tree niter;
282
283   niter = number_of_iterations_in_loop (loop);
284   if (TREE_CODE (niter) == INTEGER_CST)
285     {
286       exit = loop->single_exit;
287       if (!just_once_each_iteration_p (loop, exit->src))
288         return false;
289
290       /* The result of number_of_iterations_in_loop is by one higher than
291          we expect (i.e. it returns number of executions of the exit
292          condition, not of the loop latch edge).  */
293       niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
294                            build_int_cst (TREE_TYPE (niter), 1));
295     }
296   else
297     {
298       /* If the loop has more than one exit, try checking all of them
299          for # of iterations determinable through scev.  */
300       if (!loop->single_exit)
301         niter = find_loop_niter (loop, &exit);
302
303       /* Finally if everything else fails, try brute force evaluation.  */
304       if (try_eval
305           && (chrec_contains_undetermined (niter)
306               || TREE_CODE (niter) != INTEGER_CST))
307         niter = find_loop_niter_by_eval (loop, &exit);
308
309       if (chrec_contains_undetermined (niter)
310           || TREE_CODE (niter) != INTEGER_CST)
311         return false;
312     }
313
314   if (dump_file && (dump_flags & TDF_DETAILS))
315     {
316       fprintf (dump_file, "Loop %d iterates ", loop->num);
317       print_generic_expr (dump_file, niter, TDF_SLIM);
318       fprintf (dump_file, " times.\n");
319     }
320
321   if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
322     return true;
323
324   if (create_iv)
325     create_canonical_iv (loop, exit, niter);
326
327   return false;
328 }
329
330 /* The main entry point of the pass.  Adds canonical induction variables
331    to the suitable LOOPS.  */
332
333 void
334 canonicalize_induction_variables (struct loops *loops)
335 {
336   unsigned i;
337   struct loop *loop;
338   bool changed = false;
339   
340   for (i = 1; i < loops->num; i++)
341     {
342       loop = loops->parray[i];
343
344       if (loop)
345         changed |= canonicalize_loop_induction_variables (loops, loop,
346                                                           true, UL_SINGLE_ITER,
347                                                           true);
348     }
349
350   /* Clean up the information about numbers of iterations, since brute force
351      evaluation could reveal new information.  */
352   scev_reset ();
353
354   if (changed)
355     cleanup_tree_cfg_loop ();
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 void
363 tree_unroll_loops_completely (struct loops *loops, 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 < loops->num; i++)
371     {
372       loop = 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 (loops, 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     cleanup_tree_cfg_loop ();
392 }
393
394 /* Checks whether LOOP is empty.  */
395
396 static bool
397 empty_loop_p (struct loop *loop)
398 {
399   edge exit;
400   struct tree_niter_desc niter;
401   tree phi, def;
402   basic_block *body;
403   block_stmt_iterator bsi;
404   unsigned i;
405   tree stmt;
406
407   /* If the loop has multiple exits, it is too hard for us to handle.
408      Similarly, if the exit is not dominating, we cannot determine
409      whether the loop is not infinite.  */
410   exit = single_dom_exit (loop);
411   if (!exit)
412     return false;
413
414   /* The loop must be finite.  */
415   if (!number_of_iterations_exit (loop, exit, &niter, false))
416     return false;
417
418   /* Values of all loop exit phi nodes must be invariants.  */
419   for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
420     {
421       if (!is_gimple_reg (PHI_RESULT (phi)))
422         continue;
423
424       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
425
426       if (!expr_invariant_in_loop_p (loop, def))
427         return false;
428     }
429
430   /* And there should be no memory modifying or from other reasons
431      unremovable statements.  */
432   body = get_loop_body (loop);
433   for (i = 0; i < loop->num_nodes; i++)
434     {
435       /* Irreducible region might be infinite.  */
436       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
437         {
438           free (body);
439           return false;
440         }
441         
442       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
443         {
444           stmt = bsi_stmt (bsi);
445           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
446               || stmt_ann (stmt)->has_volatile_ops)
447             {
448               free (body);
449               return false;
450             }
451
452           /* Also, asm statements and calls may have side effects and we
453              cannot change the number of times they are executed.  */
454           switch (TREE_CODE (stmt))
455             {
456             case RETURN_EXPR:
457             case MODIFY_EXPR:
458               stmt = get_call_expr_in (stmt);
459               if (!stmt)
460                 break;
461
462             case CALL_EXPR:
463               if (TREE_SIDE_EFFECTS (stmt))
464                 {
465                   free (body);
466                   return false;
467                 }
468               break;
469
470             case ASM_EXPR:
471               /* We cannot remove volatile assembler.  */
472               if (ASM_VOLATILE_P (stmt))
473                 {
474                   free (body);
475                   return false;
476                 }
477               break;
478
479             default:
480               break;
481             }
482         }
483       }
484   free (body);
485
486   return true;
487 }
488
489 /* Remove LOOP by making it exit in the first iteration.  */
490
491 static void
492 remove_empty_loop (struct loop *loop)
493 {
494   edge exit = single_dom_exit (loop);
495   tree cond_stmt = last_stmt (exit->src);
496   tree do_exit;
497
498   if (exit->flags & EDGE_TRUE_VALUE)
499     do_exit = boolean_true_node;
500   else
501     do_exit = boolean_false_node;
502
503   COND_EXPR_COND (cond_stmt) = do_exit;
504   update_stmt (cond_stmt);
505 }
506
507 /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
508    is set to true if LOOP or any of its subloops is removed.  */
509
510 static bool
511 try_remove_empty_loop (struct loop *loop, bool *changed)
512 {
513   bool nonempty_subloop = false;
514   struct loop *sub;
515
516   /* First, all subloops must be removed.  */
517   for (sub = loop->inner; sub; sub = sub->next)
518     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
519
520   if (nonempty_subloop || !empty_loop_p (loop))
521     return false;
522
523   remove_empty_loop (loop);
524   *changed = true;
525   return true;
526 }
527
528 /* Remove the empty LOOPS.  */
529
530 void
531 remove_empty_loops (struct loops *loops)
532 {
533   bool changed = false;
534   struct loop *loop;
535
536   for (loop = loops->tree_root->inner; loop; loop = loop->next)
537     try_remove_empty_loop (loop, &changed);
538
539   if (changed)
540     {
541       scev_reset ();
542       cleanup_tree_cfg_loop ();
543     }
544 }