1 /* Induction variable canonicalization.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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
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.
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
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. */
38 #include "coretypes.h"
43 #include "hard-reg-set.h"
44 #include "basic-block.h"
46 #include "diagnostic.h"
47 #include "tree-flow.h"
48 #include "tree-dump.h"
50 #include "tree-pass.h"
52 #include "tree-chrec.h"
53 #include "tree-scalar-evolution.h"
56 #include "tree-inline.h"
58 /* Specifies types of loops that may be unrolled. */
62 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
64 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
66 UL_ALL
/* All suitable loops. */
69 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
70 is the exit edge whose condition is replaced. */
73 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
77 block_stmt_iterator incr_at
;
80 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
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");
87 cond
= last_stmt (exit
->src
);
88 in
= EDGE_SUCC (exit
->src
, 0);
90 in
= EDGE_SUCC (exit
->src
, 1);
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. */
97 type
= TREE_TYPE (niter
);
98 niter
= fold_build2 (PLUS_EXPR
, type
,
100 build_int_cst (type
, 1));
101 incr_at
= bsi_last (in
->src
);
103 build_int_cst (type
, -1),
105 &incr_at
, false, NULL
, &var
);
107 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
108 COND_EXPR_COND (cond
) = build2 (cmp
, boolean_type_node
,
110 build_int_cst (type
, 0));
114 /* Computes an estimated number of insns in LOOP. */
117 tree_num_loop_insns (struct loop
*loop
)
119 basic_block
*body
= get_loop_body (loop
);
120 block_stmt_iterator bsi
;
121 unsigned size
= 1, i
;
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
));
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):
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.
142 NINSNS is the number of insns in the loop before unrolling.
143 NUNROLL is the number of times the loop is unrolled. */
145 static unsigned HOST_WIDE_INT
146 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns
,
147 unsigned HOST_WIDE_INT nunroll
)
149 HOST_WIDE_INT unr_insns
= 2 * ((HOST_WIDE_INT
) ninsns
- 4) / 3;
152 unr_insns
*= (nunroll
+ 1);
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. */
162 try_unroll_loop_completely (struct loop
*loop
,
163 edge exit
, tree niter
,
164 enum unroll_level ul
)
166 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
167 tree old_cond
, cond
, dont_exit
, do_exit
;
172 if (!host_integerp (niter
, 1))
174 n_unroll
= tree_low_cst (niter
, 1);
176 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
177 if (n_unroll
> max_unroll
)
182 if (ul
== UL_SINGLE_ITER
)
185 ninsns
= tree_num_loop_insns (loop
);
187 if (n_unroll
* ninsns
188 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
191 if (ul
== UL_NO_GROWTH
)
193 unr_insns
= estimated_unrolled_size (ninsns
, n_unroll
);
195 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
197 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
198 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
202 if (unr_insns
> ninsns
)
204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
205 fprintf (dump_file
, "Not unrolling loop %d:\n", loop
->num
);
211 if (exit
->flags
& EDGE_TRUE_VALUE
)
213 dont_exit
= boolean_false_node
;
214 do_exit
= boolean_true_node
;
218 dont_exit
= boolean_true_node
;
219 do_exit
= boolean_false_node
;
221 cond
= last_stmt (exit
->src
);
226 edge
*edges_to_remove
= XNEWVEC (edge
, n_unroll
);
227 unsigned int n_to_remove
= 0;
229 old_cond
= COND_EXPR_COND (cond
);
230 COND_EXPR_COND (cond
) = dont_exit
;
232 initialize_original_copy_tables ();
234 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
235 sbitmap_ones (wont_exit
);
236 RESET_BIT (wont_exit
, 0);
238 if (!tree_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
240 exit
, edges_to_remove
,
242 DLTHE_FLAG_UPDATE_FREQ
243 | DLTHE_FLAG_COMPLETTE_PEEL
))
245 COND_EXPR_COND (cond
) = old_cond
;
247 free_original_copy_tables ();
249 free (edges_to_remove
);
253 free (edges_to_remove
);
254 free_original_copy_tables ();
257 COND_EXPR_COND (cond
) = do_exit
;
260 update_ssa (TODO_update_ssa
);
262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
263 fprintf (dump_file
, "Unrolled loop %d completely.\n", loop
->num
);
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. */
275 canonicalize_loop_induction_variables (struct loop
*loop
,
276 bool create_iv
, enum unroll_level ul
,
282 niter
= number_of_iterations_in_loop (loop
);
283 if (TREE_CODE (niter
) == INTEGER_CST
)
285 exit
= single_exit (loop
);
286 if (!just_once_each_iteration_p (loop
, exit
->src
))
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));
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
);
302 /* Finally if everything else fails, try brute force evaluation. */
304 && (chrec_contains_undetermined (niter
)
305 || TREE_CODE (niter
) != INTEGER_CST
))
306 niter
= find_loop_niter_by_eval (loop
, &exit
);
308 if (chrec_contains_undetermined (niter
)
309 || TREE_CODE (niter
) != INTEGER_CST
)
313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
315 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
316 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
317 fprintf (dump_file
, " times.\n");
320 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
))
324 create_canonical_iv (loop
, exit
, niter
);
329 /* The main entry point of the pass. Adds canonical induction variables
330 to the suitable loops. */
333 canonicalize_induction_variables (void)
337 bool changed
= false;
339 for (i
= 1; i
< current_loops
->num
; i
++)
341 loop
= current_loops
->parray
[i
];
344 changed
|= canonicalize_loop_induction_variables (loop
,
345 true, UL_SINGLE_ITER
,
349 /* Clean up the information about numbers of iterations, since brute force
350 evaluation could reveal new information. */
354 return TODO_cleanup_cfg
;
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. */
363 tree_unroll_loops_completely (bool may_increase_size
)
367 bool changed
= false;
368 enum unroll_level ul
;
370 for (i
= 1; i
< current_loops
->num
; i
++)
372 loop
= current_loops
->parray
[i
];
377 if (may_increase_size
&& maybe_hot_bb_p (loop
->header
))
381 changed
|= canonicalize_loop_induction_variables (loop
,
383 !flag_tree_loop_ivcanon
);
386 /* Clean up the information about numbers of iterations, since complete
387 unrolling might have invalidated it. */
391 return TODO_cleanup_cfg
;
395 /* Checks whether LOOP is empty. */
398 empty_loop_p (struct loop
*loop
)
401 struct tree_niter_desc niter
;
404 block_stmt_iterator bsi
;
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
);
415 /* The loop must be finite. */
416 if (!number_of_iterations_exit (loop
, exit
, &niter
, false))
419 /* Values of all loop exit phi nodes must be invariants. */
420 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
422 if (!is_gimple_reg (PHI_RESULT (phi
)))
425 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
427 if (!expr_invariant_in_loop_p (loop
, def
))
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
++)
436 /* Irreducible region might be infinite. */
437 if (body
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
443 for (bsi
= bsi_start (body
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
445 stmt
= bsi_stmt (bsi
);
446 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
)
447 || stmt_ann (stmt
)->has_volatile_ops
)
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
))
458 case GIMPLE_MODIFY_STMT
:
459 stmt
= get_call_expr_in (stmt
);
464 if (TREE_SIDE_EFFECTS (stmt
))
472 /* We cannot remove volatile assembler. */
473 if (ASM_VOLATILE_P (stmt
))
490 /* Remove LOOP by making it exit in the first iteration. */
493 remove_empty_loop (struct loop
*loop
)
495 edge exit
= single_dom_exit (loop
), non_exit
;
496 tree cond_stmt
= last_stmt (exit
->src
);
499 unsigned n_before
, freq_in
, freq_h
;
500 gcov_type exit_count
= exit
->count
;
502 non_exit
= EDGE_SUCC (exit
->src
, 0);
503 if (non_exit
== exit
)
504 non_exit
= EDGE_SUCC (exit
->src
, 1);
506 if (exit
->flags
& EDGE_TRUE_VALUE
)
507 do_exit
= boolean_true_node
;
509 do_exit
= boolean_false_node
;
511 COND_EXPR_COND (cond_stmt
) = do_exit
;
512 update_stmt (cond_stmt
);
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;
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
));
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
)
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
,
538 /* Number of executions of exit is not changed, thus we need to restore
539 the original value. */
540 exit
->count
= exit_count
;
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. */
547 try_remove_empty_loop (struct loop
*loop
, bool *changed
)
549 bool nonempty_subloop
= false;
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
);
556 if (nonempty_subloop
|| !empty_loop_p (loop
))
559 remove_empty_loop (loop
);
564 /* Remove the empty loops. */
567 remove_empty_loops (void)
569 bool changed
= false;
572 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
573 try_remove_empty_loop (loop
, &changed
);
578 return TODO_cleanup_cfg
;