Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-ivcanon.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Induction variable canonicalization. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2004, 2005, 2007, 2008, 2010 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Free Software Foundation, Inc. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
4 |
| 0 | 5 This file is part of GCC. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
6 |
| 0 | 7 GCC is free software; you can redistribute it and/or modify it |
| 8 under the terms of the GNU General Public License as published by the | |
| 9 Free Software Foundation; either version 3, or (at your option) any | |
| 10 later version. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
11 |
| 0 | 12 GCC is distributed in the hope that it will be useful, but WITHOUT |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
16 |
| 0 | 17 You should have received a copy of the GNU General Public License |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 /* This pass detects the loops that iterate a constant number of times, | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
22 adds a canonical induction variable (step -1, tested against 0) |
| 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 "tm_p.h" | |
| 42 #include "basic-block.h" | |
| 43 #include "diagnostic.h" | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
44 #include "tree-pretty-print.h" |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
45 #include "gimple-pretty-print.h" |
| 0 | 46 #include "tree-flow.h" |
| 47 #include "tree-dump.h" | |
| 48 #include "cfgloop.h" | |
| 49 #include "tree-pass.h" | |
| 50 #include "tree-chrec.h" | |
| 51 #include "tree-scalar-evolution.h" | |
| 52 #include "params.h" | |
| 53 #include "flags.h" | |
| 54 #include "tree-inline.h" | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
55 #include "target.h" |
| 0 | 56 |
| 57 /* Specifies types of loops that may be unrolled. */ | |
| 58 | |
| 59 enum unroll_level | |
| 60 { | |
| 61 UL_SINGLE_ITER, /* Only loops that exit immediately in the first | |
| 62 iteration. */ | |
| 63 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase | |
| 64 of code size. */ | |
| 65 UL_ALL /* All suitable loops. */ | |
| 66 }; | |
| 67 | |
| 68 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT | |
| 69 is the exit edge whose condition is replaced. */ | |
| 70 | |
| 71 static void | |
| 72 create_canonical_iv (struct loop *loop, edge exit, tree niter) | |
| 73 { | |
| 74 edge in; | |
| 75 tree type, var; | |
| 76 gimple cond; | |
| 77 gimple_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 = gsi_last_bb (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 gimple_cond_set_code (cond, cmp); | |
| 109 gimple_cond_set_lhs (cond, var); | |
| 110 gimple_cond_set_rhs (cond, build_int_cst (type, 0)); | |
| 111 update_stmt (cond); | |
| 112 } | |
| 113 | |
| 114 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */ | |
| 115 | |
| 116 unsigned | |
| 117 tree_num_loop_insns (struct loop *loop, eni_weights *weights) | |
| 118 { | |
| 119 basic_block *body = get_loop_body (loop); | |
| 120 gimple_stmt_iterator gsi; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
121 unsigned size = 0, i; |
| 0 | 122 |
| 123 for (i = 0; i < loop->num_nodes; i++) | |
| 124 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 125 size += estimate_num_insns (gsi_stmt (gsi), weights); | |
| 126 free (body); | |
| 127 | |
| 128 return size; | |
| 129 } | |
| 130 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
131 /* Describe size of loop as detected by tree_estimate_loop_size. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
132 struct loop_size |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
133 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
134 /* Number of instructions in the loop. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
135 int overall; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
136 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
137 /* Number of instructions that will be likely optimized out in |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
138 peeled iterations of loop (i.e. computation based on induction |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
139 variable where induction variable starts at known constant.) */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
140 int eliminated_by_peeling; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
141 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
142 /* Same statistics for last iteration of loop: it is smaller because |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
143 instructions after exit are not executed. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
144 int last_iteration; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
145 int last_iteration_eliminated_by_peeling; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
146 }; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
147 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
148 /* Return true if OP in STMT will be constant after peeling LOOP. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
149 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
150 static bool |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
151 constant_after_peeling (tree op, gimple stmt, struct loop *loop) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
152 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
153 affine_iv iv; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
154 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
155 if (is_gimple_min_invariant (op)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
156 return true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
157 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 /* We can still fold accesses to constant arrays when index is known. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
159 if (TREE_CODE (op) != SSA_NAME) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
161 tree base = op; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
162 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 /* First make fast look if we see constant array inside. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
164 while (handled_component_p (base)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
165 base = TREE_OPERAND (base, 0); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
166 if ((DECL_P (base) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
167 && TREE_STATIC (base) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
168 && TREE_READONLY (base) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 && (DECL_INITIAL (base) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
170 || (!DECL_EXTERNAL (base) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
171 && targetm.binds_local_p (base)))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
172 || CONSTANT_CLASS_P (base)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
173 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
174 /* If so, see if we understand all the indices. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
175 base = op; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
176 while (handled_component_p (base)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
177 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
178 if (TREE_CODE (base) == ARRAY_REF |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
179 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
180 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
181 base = TREE_OPERAND (base, 0); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
182 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
183 return true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
186 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
187 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
188 /* Induction variables are constants. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
189 if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
190 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
191 if (!is_gimple_min_invariant (iv.base)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
192 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
193 if (!is_gimple_min_invariant (iv.step)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
194 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
195 return true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
196 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
197 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
198 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
199 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
200 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
201 static void |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 tree_estimate_loop_size (struct loop *loop, edge exit, struct loop_size *size) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
203 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
204 basic_block *body = get_loop_body (loop); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 gimple_stmt_iterator gsi; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 unsigned int i; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 bool after_exit; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
208 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 size->overall = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
210 size->eliminated_by_peeling = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
211 size->last_iteration = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 size->last_iteration_eliminated_by_peeling = 0; |
| 0 | 213 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
214 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
215 fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
216 for (i = 0; i < loop->num_nodes; i++) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
217 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 if (exit && body[i] != exit->src |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 && dominated_by_p (CDI_DOMINATORS, body[i], exit->src)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
220 after_exit = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
221 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 after_exit = false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
223 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
224 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
226 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
227 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 gimple stmt = gsi_stmt (gsi); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 int num = estimate_num_insns (stmt, &eni_size_weights); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 bool likely_eliminated = false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
231 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
234 fprintf (dump_file, " size: %3i ", num); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
235 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
236 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
237 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
238 /* Look for reasons why we might optimize this stmt away. */ |
| 0 | 239 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
240 /* Exit conditional. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
241 if (body[i] == exit->src && stmt == last_stmt (exit->src)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
242 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 fprintf (dump_file, " Exit condition will be eliminated.\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 likely_eliminated = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
246 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
247 /* Sets of IV variables */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
248 else if (gimple_code (stmt) == GIMPLE_ASSIGN |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
249 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
250 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
251 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
252 fprintf (dump_file, " Induction variable computation will" |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
253 " be folded away.\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
254 likely_eliminated = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
255 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
256 /* Assignments of IV variables. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
257 else if (gimple_code (stmt) == GIMPLE_ASSIGN |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
258 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
259 && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt,loop) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
260 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
261 || constant_after_peeling (gimple_assign_rhs2 (stmt), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
262 stmt, loop))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
263 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
264 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
265 fprintf (dump_file, " Constant expression will be folded away.\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
266 likely_eliminated = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
267 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
268 /* Conditionals. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
269 else if (gimple_code (stmt) == GIMPLE_COND |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
270 && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
271 && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
272 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
273 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
274 fprintf (dump_file, " Constant conditional.\n"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
275 likely_eliminated = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
276 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
277 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
278 size->overall += num; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
279 if (likely_eliminated) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
280 size->eliminated_by_peeling += num; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
281 if (!after_exit) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
282 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
283 size->last_iteration += num; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
284 if (likely_eliminated) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
285 size->last_iteration_eliminated_by_peeling += num; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
286 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
287 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
288 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
289 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
290 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
291 size->eliminated_by_peeling, size->last_iteration, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
292 size->last_iteration_eliminated_by_peeling); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
293 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
294 free (body); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
295 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
296 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
297 /* Estimate number of insns of completely unrolled loop. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
298 It is (NUNROLL + 1) * size of loop body with taking into account |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
299 the fact that in last copy everything after exit conditional |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
300 is dead and that some instructions will be eliminated after |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
301 peeling. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
302 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
303 Loop body is likely going to simplify futher, this is difficult |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
304 to guess, we just decrease the result by 1/3. */ |
| 0 | 305 |
| 306 static unsigned HOST_WIDE_INT | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
307 estimated_unrolled_size (struct loop_size *size, |
| 0 | 308 unsigned HOST_WIDE_INT nunroll) |
| 309 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
310 HOST_WIDE_INT unr_insns = ((nunroll) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
311 * (HOST_WIDE_INT) (size->overall |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
312 - size->eliminated_by_peeling)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
313 if (!nunroll) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
314 unr_insns = 0; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
315 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
316 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
317 unr_insns = unr_insns * 2 / 3; |
| 0 | 318 if (unr_insns <= 0) |
| 319 unr_insns = 1; | |
| 320 | |
| 321 return unr_insns; | |
| 322 } | |
| 323 | |
| 324 /* Tries to unroll LOOP completely, i.e. NITER times. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
325 UL determines which loops we are allowed to unroll. |
| 0 | 326 EXIT is the exit of the loop that should be eliminated. */ |
| 327 | |
| 328 static bool | |
| 329 try_unroll_loop_completely (struct loop *loop, | |
| 330 edge exit, tree niter, | |
| 331 enum unroll_level ul) | |
| 332 { | |
| 333 unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; | |
| 334 gimple cond; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
335 struct loop_size size; |
| 0 | 336 |
| 337 if (loop->inner) | |
| 338 return false; | |
| 339 | |
| 340 if (!host_integerp (niter, 1)) | |
| 341 return false; | |
| 342 n_unroll = tree_low_cst (niter, 1); | |
| 343 | |
| 344 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES); | |
| 345 if (n_unroll > max_unroll) | |
| 346 return false; | |
| 347 | |
| 348 if (n_unroll) | |
| 349 { | |
| 350 if (ul == UL_SINGLE_ITER) | |
| 351 return false; | |
| 352 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
353 tree_estimate_loop_size (loop, exit, &size); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
354 ninsns = size.overall; |
| 0 | 355 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
356 unr_insns = estimated_unrolled_size (&size, n_unroll); |
| 0 | 357 if (dump_file && (dump_flags & TDF_DETAILS)) |
| 358 { | |
| 359 fprintf (dump_file, " Loop size: %d\n", (int) ninsns); | |
| 360 fprintf (dump_file, " Estimated size after unrolling: %d\n", | |
| 361 (int) unr_insns); | |
| 362 } | |
| 363 | |
| 364 if (unr_insns > ninsns | |
| 365 && (unr_insns | |
| 366 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))) | |
| 367 { | |
| 368 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 369 fprintf (dump_file, "Not unrolling loop %d " | |
| 370 "(--param max-completely-peeled-insns limit reached).\n", | |
| 371 loop->num); | |
| 372 return false; | |
| 373 } | |
| 374 | |
| 375 if (ul == UL_NO_GROWTH | |
| 376 && unr_insns > ninsns) | |
| 377 { | |
| 378 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 379 fprintf (dump_file, "Not unrolling loop %d.\n", loop->num); | |
| 380 return false; | |
| 381 } | |
| 382 } | |
| 383 | |
| 384 if (n_unroll) | |
| 385 { | |
| 386 sbitmap wont_exit; | |
| 387 edge e; | |
| 388 unsigned i; | |
| 389 VEC (edge, heap) *to_remove = NULL; | |
| 390 | |
| 391 initialize_original_copy_tables (); | |
| 392 wont_exit = sbitmap_alloc (n_unroll + 1); | |
| 393 sbitmap_ones (wont_exit); | |
| 394 RESET_BIT (wont_exit, 0); | |
| 395 | |
| 396 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), | |
| 397 n_unroll, wont_exit, | |
| 398 exit, &to_remove, | |
| 399 DLTHE_FLAG_UPDATE_FREQ | |
| 400 | DLTHE_FLAG_COMPLETTE_PEEL)) | |
| 401 { | |
| 402 free_original_copy_tables (); | |
| 403 free (wont_exit); | |
| 404 return false; | |
| 405 } | |
| 406 | |
| 407 for (i = 0; VEC_iterate (edge, to_remove, i, e); i++) | |
| 408 { | |
| 409 bool ok = remove_path (e); | |
| 410 gcc_assert (ok); | |
| 411 } | |
| 412 | |
| 413 VEC_free (edge, heap, to_remove); | |
| 414 free (wont_exit); | |
| 415 free_original_copy_tables (); | |
| 416 } | |
| 417 | |
| 418 cond = last_stmt (exit->src); | |
| 419 if (exit->flags & EDGE_TRUE_VALUE) | |
| 420 gimple_cond_make_true (cond); | |
| 421 else | |
| 422 gimple_cond_make_false (cond); | |
| 423 update_stmt (cond); | |
| 424 update_ssa (TODO_update_ssa); | |
| 425 | |
| 426 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 427 fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); | |
| 428 | |
| 429 return true; | |
| 430 } | |
| 431 | |
| 432 /* Adds a canonical induction variable to LOOP if suitable. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
433 CREATE_IV is true if we may create a new iv. UL determines |
| 0 | 434 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
435 to determine the number of iterations of a loop by direct evaluation. |
| 0 | 436 Returns true if cfg is changed. */ |
| 437 | |
| 438 static bool | |
| 439 canonicalize_loop_induction_variables (struct loop *loop, | |
| 440 bool create_iv, enum unroll_level ul, | |
| 441 bool try_eval) | |
| 442 { | |
| 443 edge exit = NULL; | |
| 444 tree niter; | |
| 445 | |
| 446 niter = number_of_latch_executions (loop); | |
| 447 if (TREE_CODE (niter) == INTEGER_CST) | |
| 448 { | |
| 449 exit = single_exit (loop); | |
| 450 if (!just_once_each_iteration_p (loop, exit->src)) | |
| 451 return false; | |
| 452 } | |
| 453 else | |
| 454 { | |
| 455 /* If the loop has more than one exit, try checking all of them | |
| 456 for # of iterations determinable through scev. */ | |
| 457 if (!single_exit (loop)) | |
| 458 niter = find_loop_niter (loop, &exit); | |
| 459 | |
| 460 /* Finally if everything else fails, try brute force evaluation. */ | |
| 461 if (try_eval | |
| 462 && (chrec_contains_undetermined (niter) | |
| 463 || TREE_CODE (niter) != INTEGER_CST)) | |
| 464 niter = find_loop_niter_by_eval (loop, &exit); | |
| 465 | |
| 466 if (chrec_contains_undetermined (niter) | |
| 467 || TREE_CODE (niter) != INTEGER_CST) | |
| 468 return false; | |
| 469 } | |
| 470 | |
| 471 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 472 { | |
| 473 fprintf (dump_file, "Loop %d iterates ", loop->num); | |
| 474 print_generic_expr (dump_file, niter, TDF_SLIM); | |
| 475 fprintf (dump_file, " times.\n"); | |
| 476 } | |
| 477 | |
| 478 if (try_unroll_loop_completely (loop, exit, niter, ul)) | |
| 479 return true; | |
| 480 | |
| 481 if (create_iv) | |
| 482 create_canonical_iv (loop, exit, niter); | |
| 483 | |
| 484 return false; | |
| 485 } | |
| 486 | |
| 487 /* The main entry point of the pass. Adds canonical induction variables | |
| 488 to the suitable loops. */ | |
| 489 | |
| 490 unsigned int | |
| 491 canonicalize_induction_variables (void) | |
| 492 { | |
| 493 loop_iterator li; | |
| 494 struct loop *loop; | |
| 495 bool changed = false; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
496 |
| 0 | 497 FOR_EACH_LOOP (li, loop, 0) |
| 498 { | |
| 499 changed |= canonicalize_loop_induction_variables (loop, | |
| 500 true, UL_SINGLE_ITER, | |
| 501 true); | |
| 502 } | |
| 503 | |
| 504 /* Clean up the information about numbers of iterations, since brute force | |
| 505 evaluation could reveal new information. */ | |
| 506 scev_reset (); | |
| 507 | |
| 508 if (changed) | |
| 509 return TODO_cleanup_cfg; | |
| 510 return 0; | |
| 511 } | |
| 512 | |
| 513 /* Unroll LOOPS completely if they iterate just few times. Unless | |
| 514 MAY_INCREASE_SIZE is true, perform the unrolling only if the | |
| 515 size of the code does not increase. */ | |
| 516 | |
| 517 unsigned int | |
| 518 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) | |
| 519 { | |
| 520 loop_iterator li; | |
| 521 struct loop *loop; | |
| 522 bool changed; | |
| 523 enum unroll_level ul; | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
524 int iteration = 0; |
| 0 | 525 |
| 526 do | |
| 527 { | |
| 528 changed = false; | |
| 529 | |
| 530 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) | |
| 531 { | |
| 532 if (may_increase_size && optimize_loop_for_speed_p (loop) | |
| 533 /* Unroll outermost loops only if asked to do so or they do | |
| 534 not cause code growth. */ | |
| 535 && (unroll_outer | |
| 536 || loop_outer (loop_outer (loop)))) | |
| 537 ul = UL_ALL; | |
| 538 else | |
| 539 ul = UL_NO_GROWTH; | |
| 540 changed |= canonicalize_loop_induction_variables | |
| 541 (loop, false, ul, !flag_tree_loop_ivcanon); | |
| 542 } | |
| 543 | |
| 544 if (changed) | |
| 545 { | |
| 546 /* This will take care of removing completely unrolled loops | |
| 547 from the loop structures so we can continue unrolling now | |
| 548 innermost loops. */ | |
| 549 if (cleanup_tree_cfg ()) | |
| 550 update_ssa (TODO_update_ssa_only_virtuals); | |
| 551 | |
| 552 /* Clean up the information about numbers of iterations, since | |
| 553 complete unrolling might have invalidated it. */ | |
| 554 scev_reset (); | |
| 555 } | |
| 556 } | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
557 while (changed |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
558 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS)); |
| 0 | 559 |
| 560 return 0; | |
| 561 } |