Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-unswitch.c @ 143:76e1cf5455ef
add cbc_gc test
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 23 Dec 2018 19:24:05 +0900 |
| parents | 84e7813d76e9 |
| children | 1830386684a0 |
| rev | line source |
|---|---|
| 0 | 1 /* Loop unswitching. |
| 131 | 2 Copyright (C) 2004-2018 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
|
3 |
| 0 | 4 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
|
5 |
| 0 | 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 3, or (at your option) any | |
| 9 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
|
10 |
| 0 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
15 |
| 0 | 16 You should have received a copy of the GNU General Public License |
| 17 along with GCC; see the file COPYING3. If not see | |
| 18 <http://www.gnu.org/licenses/>. */ | |
| 19 | |
| 20 #include "config.h" | |
| 21 #include "system.h" | |
| 22 #include "coretypes.h" | |
| 111 | 23 #include "backend.h" |
| 0 | 24 #include "tree.h" |
| 111 | 25 #include "gimple.h" |
| 26 #include "tree-pass.h" | |
| 27 #include "ssa.h" | |
| 28 #include "fold-const.h" | |
| 29 #include "gimplify.h" | |
| 30 #include "tree-cfg.h" | |
| 31 #include "tree-ssa.h" | |
| 32 #include "tree-ssa-loop-niter.h" | |
| 33 #include "tree-ssa-loop.h" | |
| 34 #include "tree-into-ssa.h" | |
| 0 | 35 #include "cfgloop.h" |
| 36 #include "params.h" | |
| 37 #include "tree-inline.h" | |
| 111 | 38 #include "gimple-iterator.h" |
| 39 #include "cfghooks.h" | |
| 40 #include "tree-ssa-loop-manip.h" | |
| 0 | 41 |
| 42 /* This file implements the loop unswitching, i.e. transformation of loops like | |
| 43 | |
| 44 while (A) | |
| 45 { | |
| 46 if (inv) | |
| 47 B; | |
| 48 | |
| 49 X; | |
| 50 | |
| 51 if (!inv) | |
| 52 C; | |
| 53 } | |
| 54 | |
| 55 where inv is the loop invariant, into | |
| 56 | |
| 57 if (inv) | |
| 58 { | |
| 59 while (A) | |
| 60 { | |
| 61 B; | |
| 62 X; | |
| 63 } | |
| 64 } | |
| 65 else | |
| 66 { | |
| 67 while (A) | |
| 68 { | |
| 69 X; | |
| 70 C; | |
| 71 } | |
| 72 } | |
| 73 | |
| 74 Inv is considered invariant iff the values it compares are both invariant; | |
| 75 tree-ssa-loop-im.c ensures that all the suitable conditions are in this | |
| 76 shape. */ | |
| 77 | |
| 78 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); | |
| 79 static bool tree_unswitch_single_loop (struct loop *, int); | |
| 80 static tree tree_may_unswitch_on (basic_block, struct loop *); | |
| 111 | 81 static bool tree_unswitch_outer_loop (struct loop *); |
| 82 static edge find_loop_guard (struct loop *); | |
| 83 static bool empty_bb_without_guard_p (struct loop *, basic_block); | |
| 84 static bool used_outside_loop_p (struct loop *, tree); | |
| 85 static void hoist_guard (struct loop *, edge); | |
| 86 static bool check_exit_phi (struct loop *); | |
| 87 static tree get_vop_from_header (struct loop *); | |
| 0 | 88 |
| 89 /* Main entry point. Perform loop unswitching on all suitable loops. */ | |
| 90 | |
| 91 unsigned int | |
| 92 tree_ssa_unswitch_loops (void) | |
| 93 { | |
| 94 struct loop *loop; | |
| 95 bool changed = false; | |
| 96 | |
| 111 | 97 /* Go through all loops starting from innermost. */ |
| 98 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) | |
| 0 | 99 { |
| 111 | 100 if (!loop->inner) |
| 101 /* Unswitch innermost loop. */ | |
| 102 changed |= tree_unswitch_single_loop (loop, 0); | |
| 103 else | |
| 104 changed |= tree_unswitch_outer_loop (loop); | |
| 0 | 105 } |
| 106 | |
| 107 if (changed) | |
| 108 return TODO_cleanup_cfg; | |
| 109 return 0; | |
| 110 } | |
| 111 | |
| 111 | 112 /* Return TRUE if an SSA_NAME maybe undefined and is therefore |
| 113 unsuitable for unswitching. STMT is the statement we are | |
| 114 considering for unswitching and LOOP is the loop it appears in. */ | |
| 115 | |
| 116 static bool | |
| 117 is_maybe_undefined (const tree name, gimple *stmt, struct loop *loop) | |
| 118 { | |
| 119 /* The loop header is the only block we can trivially determine that | |
| 120 will always be executed. If the comparison is in the loop | |
| 121 header, we know it's OK to unswitch on it. */ | |
| 122 if (gimple_bb (stmt) == loop->header) | |
| 123 return false; | |
| 124 | |
| 125 auto_bitmap visited_ssa; | |
| 126 auto_vec<tree> worklist; | |
| 127 worklist.safe_push (name); | |
| 128 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); | |
| 129 while (!worklist.is_empty ()) | |
| 130 { | |
| 131 tree t = worklist.pop (); | |
| 132 | |
| 133 /* If it's obviously undefined, avoid further computations. */ | |
| 134 if (ssa_undefined_value_p (t, true)) | |
| 135 return true; | |
| 136 | |
| 137 if (ssa_defined_default_def_p (t)) | |
| 138 continue; | |
| 139 | |
| 140 gimple *def = SSA_NAME_DEF_STMT (t); | |
| 141 | |
| 142 /* Check that all the PHI args are fully defined. */ | |
| 143 if (gphi *phi = dyn_cast <gphi *> (def)) | |
| 144 { | |
| 145 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) | |
| 146 { | |
| 147 tree t = gimple_phi_arg_def (phi, i); | |
| 148 /* If an SSA has already been seen, it may be a loop, | |
| 149 but we can continue and ignore this use. Otherwise, | |
| 150 add the SSA_NAME to the queue and visit it later. */ | |
| 151 if (TREE_CODE (t) == SSA_NAME | |
| 152 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) | |
| 153 worklist.safe_push (t); | |
| 154 } | |
| 155 continue; | |
| 156 } | |
| 157 | |
| 158 /* Uses in stmts always executed when the region header executes | |
| 159 are fine. */ | |
| 160 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def))) | |
| 161 continue; | |
| 162 | |
| 163 /* Handle calls and memory loads conservatively. */ | |
| 164 if (!is_gimple_assign (def) | |
| 165 || (gimple_assign_single_p (def) | |
| 166 && gimple_vuse (def))) | |
| 167 return true; | |
| 168 | |
| 169 /* Check that any SSA names used to define NAME are also fully | |
| 170 defined. */ | |
| 171 use_operand_p use_p; | |
| 172 ssa_op_iter iter; | |
| 173 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) | |
| 174 { | |
| 175 tree t = USE_FROM_PTR (use_p); | |
| 176 /* If an SSA has already been seen, it may be a loop, | |
| 177 but we can continue and ignore this use. Otherwise, | |
| 178 add the SSA_NAME to the queue and visit it later. */ | |
| 179 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) | |
| 180 worklist.safe_push (t); | |
| 181 } | |
| 182 } | |
| 183 return false; | |
| 184 } | |
| 185 | |
| 0 | 186 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its |
| 187 basic blocks (for what it means see comments below). */ | |
| 188 | |
| 189 static tree | |
| 190 tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
| 191 { | |
| 111 | 192 gimple *last, *def; |
| 193 gcond *stmt; | |
| 0 | 194 tree cond, use; |
| 195 basic_block def_bb; | |
| 196 ssa_op_iter iter; | |
| 197 | |
| 198 /* BB must end in a simple conditional jump. */ | |
| 111 | 199 last = last_stmt (bb); |
| 200 if (!last || gimple_code (last) != GIMPLE_COND) | |
| 0 | 201 return NULL_TREE; |
| 111 | 202 stmt = as_a <gcond *> (last); |
| 0 | 203 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
204 /* To keep the things simple, we do not directly remove the conditions, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
205 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
206 loop where we would unswitch again on such a condition. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
207 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
208 return NULL_TREE; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
209 |
| 0 | 210 /* Condition must be invariant. */ |
| 211 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
| 212 { | |
| 213 def = SSA_NAME_DEF_STMT (use); | |
| 214 def_bb = gimple_bb (def); | |
| 215 if (def_bb | |
| 216 && flow_bb_inside_loop_p (loop, def_bb)) | |
| 217 return NULL_TREE; | |
| 111 | 218 /* Unswitching on undefined values would introduce undefined |
| 219 behavior that the original program might never exercise. */ | |
| 220 if (is_maybe_undefined (use, stmt, loop)) | |
| 221 return NULL_TREE; | |
| 0 | 222 } |
| 223 | |
| 224 cond = build2 (gimple_cond_code (stmt), boolean_type_node, | |
| 225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | |
| 226 | |
| 227 return cond; | |
| 228 } | |
| 229 | |
| 230 /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
| 231 simplish (sufficient to prevent us from duplicating loop in unswitching | |
| 232 unnecessarily). */ | |
| 233 | |
| 234 static tree | |
| 235 simplify_using_entry_checks (struct loop *loop, tree cond) | |
| 236 { | |
| 237 edge e = loop_preheader_edge (loop); | |
| 111 | 238 gimple *stmt; |
| 0 | 239 |
| 240 while (1) | |
| 241 { | |
| 242 stmt = last_stmt (e->src); | |
| 243 if (stmt | |
| 244 && gimple_code (stmt) == GIMPLE_COND | |
| 245 && gimple_cond_code (stmt) == TREE_CODE (cond) | |
| 246 && operand_equal_p (gimple_cond_lhs (stmt), | |
| 247 TREE_OPERAND (cond, 0), 0) | |
| 248 && operand_equal_p (gimple_cond_rhs (stmt), | |
| 249 TREE_OPERAND (cond, 1), 0)) | |
| 250 return (e->flags & EDGE_TRUE_VALUE | |
| 251 ? boolean_true_node | |
| 252 : boolean_false_node); | |
| 253 | |
| 254 if (!single_pred_p (e->src)) | |
| 255 return cond; | |
| 256 | |
| 257 e = single_pred_edge (e->src); | |
| 111 | 258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
| 0 | 259 return cond; |
| 260 } | |
| 261 } | |
| 262 | |
| 263 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
| 264 it to grow too much, it is too easy to create example on that the code would | |
| 265 grow exponentially. */ | |
| 266 | |
| 267 static bool | |
| 268 tree_unswitch_single_loop (struct loop *loop, int num) | |
| 269 { | |
| 270 basic_block *bbs; | |
| 271 struct loop *nloop; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
272 unsigned i, found; |
| 0 | 273 tree cond = NULL_TREE; |
| 111 | 274 gimple *stmt; |
| 0 | 275 bool changed = false; |
| 111 | 276 HOST_WIDE_INT iterations; |
| 277 | |
| 278 /* Perform initial tests if unswitch is eligible. */ | |
| 279 if (num == 0) | |
| 280 { | |
| 281 /* Do not unswitch in cold regions. */ | |
| 282 if (optimize_loop_for_size_p (loop)) | |
| 283 { | |
| 284 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 285 fprintf (dump_file, ";; Not unswitching cold loops\n"); | |
| 286 return false; | |
| 287 } | |
| 288 | |
| 289 /* The loop should not be too large, to limit code growth. */ | |
| 290 if (tree_num_loop_insns (loop, &eni_size_weights) | |
| 291 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) | |
| 292 { | |
| 293 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 294 fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
| 295 return false; | |
| 296 } | |
| 297 | |
| 298 /* If the loop is not expected to iterate, there is no need | |
| 299 for unswitching. */ | |
| 300 iterations = estimated_loop_iterations_int (loop); | |
| 301 if (iterations < 0) | |
| 302 iterations = likely_max_loop_iterations_int (loop); | |
| 303 if (iterations >= 0 && iterations <= 1) | |
| 304 { | |
| 305 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 306 fprintf (dump_file, ";; Not unswitching, loop is not expected" | |
| 307 " to iterate\n"); | |
| 308 return false; | |
| 309 } | |
| 310 } | |
| 0 | 311 |
| 312 i = 0; | |
| 313 bbs = get_loop_body (loop); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
314 found = loop->num_nodes; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
315 |
| 0 | 316 while (1) |
| 317 { | |
| 318 /* Find a bb to unswitch on. */ | |
| 319 for (; i < loop->num_nodes; i++) | |
| 320 if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
| 321 break; | |
| 322 | |
| 323 if (i == loop->num_nodes) | |
| 324 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
325 if (dump_file |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
326 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
327 && (dump_flags & TDF_DETAILS)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
328 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
329 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
330 if (found == loop->num_nodes) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
331 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
332 free (bbs); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
333 return changed; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
334 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
335 break; |
| 0 | 336 } |
| 337 | |
| 338 cond = simplify_using_entry_checks (loop, cond); | |
| 339 stmt = last_stmt (bbs[i]); | |
| 340 if (integer_nonzerop (cond)) | |
| 341 { | |
| 342 /* Remove false path. */ | |
| 111 | 343 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), |
| 344 boolean_true_node); | |
| 0 | 345 changed = true; |
| 346 } | |
| 347 else if (integer_zerop (cond)) | |
| 348 { | |
| 349 /* Remove true path. */ | |
| 111 | 350 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt), |
| 351 boolean_false_node); | |
| 0 | 352 changed = true; |
| 353 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
354 /* Do not unswitch too much. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
355 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
356 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
357 i++; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
358 continue; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
359 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
360 /* In nested tree_unswitch_single_loop first optimize all conditions |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
361 using entry checks, then discover still reachable blocks in the |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
362 loop and find the condition only among those still reachable bbs. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
363 else if (num != 0) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
364 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
365 if (found == loop->num_nodes) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
366 found = i; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
367 i++; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
368 continue; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
369 } |
| 0 | 370 else |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
371 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
372 found = i; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
373 break; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
374 } |
| 0 | 375 |
| 376 update_stmt (stmt); | |
| 377 i++; | |
| 378 } | |
| 379 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
380 if (num != 0) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
381 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
382 basic_block *tos, *worklist; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
383 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
384 /* When called recursively, first do a quick discovery |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
385 of reachable bbs after the above changes and only |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
386 consider conditions in still reachable bbs. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
387 tos = worklist = XNEWVEC (basic_block, loop->num_nodes); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
388 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
389 for (i = 0; i < loop->num_nodes; i++) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
390 bbs[i]->flags &= ~BB_REACHABLE; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
391 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
392 /* Start with marking header. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
393 *tos++ = bbs[0]; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
394 bbs[0]->flags |= BB_REACHABLE; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
395 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
396 /* Iterate: find everything reachable from what we've already seen |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
397 within the same innermost loop. Don't look through false edges |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
398 if condition is always true or true edges if condition is |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
399 always false. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
400 while (tos != worklist) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
401 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
402 basic_block b = *--tos; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
403 edge e; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
404 edge_iterator ei; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
405 int flags = 0; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
406 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
407 if (EDGE_COUNT (b->succs) == 2) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
408 { |
| 111 | 409 gimple *stmt = last_stmt (b); |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
410 if (stmt |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
411 && gimple_code (stmt) == GIMPLE_COND) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
412 { |
| 111 | 413 gcond *cond_stmt = as_a <gcond *> (stmt); |
| 414 if (gimple_cond_true_p (cond_stmt)) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
415 flags = EDGE_FALSE_VALUE; |
| 111 | 416 else if (gimple_cond_false_p (cond_stmt)) |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
417 flags = EDGE_TRUE_VALUE; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
418 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
419 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
420 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
421 FOR_EACH_EDGE (e, ei, b->succs) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
422 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
423 basic_block dest = e->dest; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
424 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
425 if (dest->loop_father == loop |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
426 && !(dest->flags & BB_REACHABLE) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
427 && !(e->flags & flags)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
428 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
429 *tos++ = dest; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
430 dest->flags |= BB_REACHABLE; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
431 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
432 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
433 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
434 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
435 free (worklist); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
436 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
437 /* Find a bb to unswitch on. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
438 for (; found < loop->num_nodes; found++) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
439 if ((bbs[found]->flags & BB_REACHABLE) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
440 && (cond = tree_may_unswitch_on (bbs[found], loop))) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
441 break; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
442 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
443 if (found == loop->num_nodes) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
444 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
445 free (bbs); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
446 return changed; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
447 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
448 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
449 |
| 0 | 450 if (dump_file && (dump_flags & TDF_DETAILS)) |
| 451 fprintf (dump_file, ";; Unswitching loop\n"); | |
| 452 | |
| 453 initialize_original_copy_tables (); | |
| 454 /* Unswitch the loop on this condition. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
455 nloop = tree_unswitch_loop (loop, bbs[found], cond); |
| 0 | 456 if (!nloop) |
| 457 { | |
| 458 free_original_copy_tables (); | |
| 459 free (bbs); | |
| 460 return changed; | |
| 461 } | |
| 462 | |
| 463 /* Update the SSA form after unswitching. */ | |
| 464 update_ssa (TODO_update_ssa); | |
| 465 free_original_copy_tables (); | |
| 466 | |
| 467 /* Invoke itself on modified loops. */ | |
| 468 tree_unswitch_single_loop (nloop, num + 1); | |
| 469 tree_unswitch_single_loop (loop, num + 1); | |
| 470 free (bbs); | |
| 471 return true; | |
| 472 } | |
| 473 | |
| 474 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
| 475 unswitching of innermost loops. COND is the condition determining which | |
| 476 loop is entered -- the new loop is entered if COND is true. Returns NULL | |
| 477 if impossible, new loop otherwise. */ | |
| 478 | |
| 479 static struct loop * | |
| 480 tree_unswitch_loop (struct loop *loop, | |
| 481 basic_block unswitch_on, tree cond) | |
| 482 { | |
| 111 | 483 profile_probability prob_true; |
| 0 | 484 edge edge_true, edge_false; |
| 485 | |
| 486 /* Some sanity checking. */ | |
| 487 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
| 488 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); | |
| 489 gcc_assert (loop->inner == NULL); | |
| 490 | |
| 491 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); | |
| 492 prob_true = edge_true->probability; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
493 return loop_version (loop, unshare_expr (cond), |
| 111 | 494 NULL, prob_true, |
| 495 prob_true.invert (), | |
| 496 prob_true, prob_true.invert (), | |
| 497 false); | |
| 498 } | |
| 499 | |
| 500 /* Unswitch outer loops by hoisting invariant guard on | |
| 501 inner loop without code duplication. */ | |
| 502 static bool | |
| 503 tree_unswitch_outer_loop (struct loop *loop) | |
| 504 { | |
| 505 edge exit, guard; | |
| 506 HOST_WIDE_INT iterations; | |
| 507 | |
| 508 gcc_assert (loop->inner); | |
| 509 if (loop->inner->next) | |
| 510 return false; | |
| 511 /* Accept loops with single exit only which is not from inner loop. */ | |
| 512 exit = single_exit (loop); | |
| 513 if (!exit || exit->src->loop_father != loop) | |
| 514 return false; | |
| 515 /* Check that phi argument of exit edge is not defined inside loop. */ | |
| 516 if (!check_exit_phi (loop)) | |
| 517 return false; | |
| 518 /* If the loop is not expected to iterate, there is no need | |
| 519 for unswitching. */ | |
| 520 iterations = estimated_loop_iterations_int (loop); | |
| 521 if (iterations < 0) | |
| 522 iterations = likely_max_loop_iterations_int (loop); | |
| 523 if (iterations >= 0 && iterations <= 1) | |
| 524 { | |
| 525 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 526 fprintf (dump_file, ";; Not unswitching, loop is not expected" | |
| 527 " to iterate\n"); | |
| 528 return false; | |
| 529 } | |
| 530 | |
| 531 bool changed = false; | |
| 532 while ((guard = find_loop_guard (loop))) | |
| 533 { | |
| 534 if (! changed) | |
| 535 rewrite_virtuals_into_loop_closed_ssa (loop); | |
| 536 hoist_guard (loop, guard); | |
| 537 changed = true; | |
| 538 } | |
| 539 return changed; | |
| 540 } | |
| 541 | |
| 542 /* Checks if the body of the LOOP is within an invariant guard. If this | |
| 543 is the case, returns the edge that jumps over the real body of the loop, | |
| 544 otherwise returns NULL. */ | |
| 545 | |
| 546 static edge | |
| 547 find_loop_guard (struct loop *loop) | |
| 548 { | |
| 549 basic_block header = loop->header; | |
| 550 edge guard_edge, te, fe; | |
| 551 basic_block *body = NULL; | |
| 552 unsigned i; | |
| 553 tree use; | |
| 554 ssa_op_iter iter; | |
| 555 | |
| 556 /* We check for the following situation: | |
| 557 | |
| 558 while (1) | |
| 559 { | |
| 560 [header]] | |
| 561 loop_phi_nodes; | |
| 562 something1; | |
| 563 if (cond1) | |
| 564 body; | |
| 565 nvar = phi(orig, bvar) ... for all variables changed in body; | |
| 566 [guard_end] | |
| 567 something2; | |
| 568 if (cond2) | |
| 569 break; | |
| 570 something3; | |
| 571 } | |
| 572 | |
| 573 where: | |
| 574 | |
| 575 1) cond1 is loop invariant | |
| 576 2) If cond1 is false, then the loop is essentially empty; i.e., | |
| 577 a) nothing in something1, something2 and something3 has side | |
| 578 effects | |
| 579 b) anything defined in something1, something2 and something3 | |
| 580 is not used outside of the loop. */ | |
| 581 | |
| 582 gcond *cond; | |
| 583 do | |
| 584 { | |
| 585 basic_block next = NULL; | |
| 586 if (single_succ_p (header)) | |
| 587 next = single_succ (header); | |
| 588 else | |
| 589 { | |
| 590 cond = dyn_cast <gcond *> (last_stmt (header)); | |
| 591 if (! cond) | |
| 592 return NULL; | |
| 593 extract_true_false_edges_from_block (header, &te, &fe); | |
| 594 /* Make sure to skip earlier hoisted guards that are left | |
| 595 in place as if (true). */ | |
| 596 if (gimple_cond_true_p (cond)) | |
| 597 next = te->dest; | |
| 598 else if (gimple_cond_false_p (cond)) | |
| 599 next = fe->dest; | |
| 600 else | |
| 601 break; | |
| 602 } | |
| 603 /* Never traverse a backedge. */ | |
| 604 if (header->loop_father->header == next) | |
| 605 return NULL; | |
| 606 header = next; | |
| 607 } | |
| 608 while (1); | |
| 609 if (!flow_bb_inside_loop_p (loop, te->dest) | |
| 610 || !flow_bb_inside_loop_p (loop, fe->dest)) | |
| 611 return NULL; | |
| 612 | |
| 613 if (just_once_each_iteration_p (loop, te->dest) | |
| 614 || (single_succ_p (te->dest) | |
| 615 && just_once_each_iteration_p (loop, single_succ (te->dest)))) | |
| 616 { | |
| 617 if (just_once_each_iteration_p (loop, fe->dest)) | |
| 618 return NULL; | |
| 619 guard_edge = te; | |
| 620 } | |
| 621 else if (just_once_each_iteration_p (loop, fe->dest) | |
| 622 || (single_succ_p (fe->dest) | |
| 623 && just_once_each_iteration_p (loop, single_succ (fe->dest)))) | |
| 624 guard_edge = fe; | |
| 625 else | |
| 626 return NULL; | |
| 627 | |
| 628 /* Guard edge must skip inner loop. */ | |
| 629 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header, | |
| 630 guard_edge == fe ? te->dest : fe->dest)) | |
| 631 { | |
| 632 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 633 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n", | |
| 634 guard_edge->src->index, guard_edge->dest->index); | |
| 635 return NULL; | |
| 636 } | |
| 637 if (guard_edge->dest == loop->latch) | |
| 638 { | |
| 639 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 640 fprintf (dump_file, "Guard edge destination is loop latch.\n"); | |
| 641 return NULL; | |
| 642 } | |
| 643 | |
| 644 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 645 fprintf (dump_file, | |
| 646 "Considering guard %d -> %d in loop %d\n", | |
| 647 guard_edge->src->index, guard_edge->dest->index, loop->num); | |
| 648 /* Check if condition operands do not have definitions inside loop since | |
| 649 any bb copying is not performed. */ | |
| 650 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE) | |
| 651 { | |
| 652 gimple *def = SSA_NAME_DEF_STMT (use); | |
| 653 basic_block def_bb = gimple_bb (def); | |
| 654 if (def_bb | |
| 655 && flow_bb_inside_loop_p (loop, def_bb)) | |
| 656 { | |
| 657 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 658 fprintf (dump_file, " guard operands have definitions" | |
| 659 " inside loop\n"); | |
| 660 return NULL; | |
| 661 } | |
| 662 } | |
| 663 | |
| 664 body = get_loop_body (loop); | |
| 665 for (i = 0; i < loop->num_nodes; i++) | |
| 666 { | |
| 667 basic_block bb = body[i]; | |
| 668 if (bb->loop_father != loop) | |
| 669 continue; | |
| 670 if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
| 671 { | |
| 672 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 673 fprintf (dump_file, "Block %d is marked as irreducible in loop\n", | |
| 674 bb->index); | |
| 675 guard_edge = NULL; | |
| 676 goto end; | |
| 677 } | |
| 678 if (!empty_bb_without_guard_p (loop, bb)) | |
| 679 { | |
| 680 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 681 fprintf (dump_file, " block %d has side effects\n", bb->index); | |
| 682 guard_edge = NULL; | |
| 683 goto end; | |
| 684 } | |
| 685 } | |
| 686 | |
| 687 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 688 fprintf (dump_file, " suitable to hoist\n"); | |
| 689 end: | |
| 690 if (body) | |
| 691 free (body); | |
| 692 return guard_edge; | |
| 693 } | |
| 694 | |
| 695 /* Returns true if | |
| 696 1) no statement in BB has side effects | |
| 697 2) assuming that edge GUARD is always taken, all definitions in BB | |
| 698 are noy used outside of the loop. | |
| 699 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and | |
| 700 PROCESSED is a set of ssa names for that we already tested whether they | |
| 701 are invariant or not. */ | |
| 702 | |
| 703 static bool | |
| 704 empty_bb_without_guard_p (struct loop *loop, basic_block bb) | |
| 705 { | |
| 706 basic_block exit_bb = single_exit (loop)->src; | |
| 707 bool may_be_used_outside = (bb == exit_bb | |
| 708 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)); | |
| 709 tree name; | |
| 710 ssa_op_iter op_iter; | |
| 711 | |
| 712 /* Phi nodes do not have side effects, but their results might be used | |
| 713 outside of the loop. */ | |
| 714 if (may_be_used_outside) | |
| 715 { | |
| 716 for (gphi_iterator gsi = gsi_start_phis (bb); | |
| 717 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 718 { | |
| 719 gphi *phi = gsi.phi (); | |
| 720 name = PHI_RESULT (phi); | |
| 721 if (virtual_operand_p (name)) | |
| 722 continue; | |
| 723 | |
| 724 if (used_outside_loop_p (loop, name)) | |
| 725 return false; | |
| 726 } | |
| 727 } | |
| 728 | |
| 729 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); | |
| 730 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 731 { | |
| 732 gimple *stmt = gsi_stmt (gsi); | |
| 733 if (gimple_has_side_effects (stmt)) | |
| 734 return false; | |
| 735 | |
| 736 if (gimple_vdef(stmt)) | |
| 737 return false; | |
| 738 | |
| 739 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF) | |
| 740 { | |
| 741 if (may_be_used_outside | |
| 742 && used_outside_loop_p (loop, name)) | |
| 743 return false; | |
| 744 } | |
| 745 } | |
| 746 return true; | |
| 0 | 747 } |
| 111 | 748 |
| 749 /* Return true if NAME is used outside of LOOP. */ | |
| 750 | |
| 751 static bool | |
| 752 used_outside_loop_p (struct loop *loop, tree name) | |
| 753 { | |
| 754 imm_use_iterator it; | |
| 755 use_operand_p use; | |
| 756 | |
| 757 FOR_EACH_IMM_USE_FAST (use, it, name) | |
| 758 { | |
| 759 gimple *stmt = USE_STMT (use); | |
| 760 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
| 761 return true; | |
| 762 } | |
| 763 | |
| 764 return false; | |
| 765 } | |
| 766 | |
| 767 /* Return argument for loop preheader edge in header virtual phi if any. */ | |
| 768 | |
| 769 static tree | |
| 770 get_vop_from_header (struct loop *loop) | |
| 771 { | |
| 772 for (gphi_iterator gsi = gsi_start_phis (loop->header); | |
| 773 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 774 { | |
| 775 gphi *phi = gsi.phi (); | |
| 776 if (!virtual_operand_p (gimple_phi_result (phi))) | |
| 777 continue; | |
| 778 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
| 779 } | |
| 780 return NULL_TREE; | |
| 781 } | |
| 782 | |
| 783 /* Move the check of GUARD outside of LOOP. */ | |
| 784 | |
| 785 static void | |
| 786 hoist_guard (struct loop *loop, edge guard) | |
| 787 { | |
| 788 edge exit = single_exit (loop); | |
| 789 edge preh = loop_preheader_edge (loop); | |
| 790 basic_block pre_header = preh->src; | |
| 791 basic_block bb; | |
| 792 edge te, fe, e, new_edge; | |
| 793 gimple *stmt; | |
| 794 basic_block guard_bb = guard->src; | |
| 795 edge not_guard; | |
| 796 gimple_stmt_iterator gsi; | |
| 797 int flags = 0; | |
| 798 bool fix_dom_of_exit; | |
| 799 gcond *cond_stmt, *new_cond_stmt; | |
| 800 | |
| 801 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest); | |
| 802 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb); | |
| 803 gsi = gsi_last_bb (guard_bb); | |
| 804 stmt = gsi_stmt (gsi); | |
| 805 gcc_assert (gimple_code (stmt) == GIMPLE_COND); | |
| 806 cond_stmt = as_a <gcond *> (stmt); | |
| 807 extract_true_false_edges_from_block (guard_bb, &te, &fe); | |
| 808 /* Insert guard to PRE_HEADER. */ | |
| 809 if (!empty_block_p (pre_header)) | |
| 810 gsi = gsi_last_bb (pre_header); | |
| 811 else | |
| 812 gsi = gsi_start_bb (pre_header); | |
| 813 /* Create copy of COND_STMT. */ | |
| 814 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt), | |
| 815 gimple_cond_lhs (cond_stmt), | |
| 816 gimple_cond_rhs (cond_stmt), | |
| 817 NULL_TREE, NULL_TREE); | |
| 818 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT); | |
| 819 /* Convert COND_STMT to true/false conditional. */ | |
| 820 if (guard == te) | |
| 821 gimple_cond_make_false (cond_stmt); | |
| 822 else | |
| 823 gimple_cond_make_true (cond_stmt); | |
| 824 update_stmt (cond_stmt); | |
| 825 /* Create new loop pre-header. */ | |
| 826 e = split_block (pre_header, last_stmt (pre_header)); | |
| 827 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 828 { | |
| 829 fprintf (dump_file, " Moving guard %i->%i (prob ", | |
| 830 guard->src->index, guard->dest->index); | |
| 831 guard->probability.dump (dump_file); | |
| 832 fprintf (dump_file, ") to bb %i, new preheader is %i\n", | |
| 833 e->src->index, e->dest->index); | |
| 834 } | |
| 835 | |
| 836 gcc_assert (loop_preheader_edge (loop)->src == e->dest); | |
| 837 | |
| 838 if (guard == fe) | |
| 839 { | |
| 840 e->flags = EDGE_TRUE_VALUE; | |
| 841 flags |= EDGE_FALSE_VALUE; | |
| 842 not_guard = te; | |
| 843 } | |
| 844 else | |
| 845 { | |
| 846 e->flags = EDGE_FALSE_VALUE; | |
| 847 flags |= EDGE_TRUE_VALUE; | |
| 848 not_guard = fe; | |
| 849 } | |
| 850 new_edge = make_edge (pre_header, exit->dest, flags); | |
| 851 | |
| 852 /* Determine the probability that we skip the loop. Assume that loop has | |
| 853 same average number of iterations regardless outcome of guard. */ | |
| 854 new_edge->probability = guard->probability; | |
| 131 | 855 profile_count skip_count = guard->src->count.nonzero_p () |
| 111 | 856 ? guard->count ().apply_scale (pre_header->count, |
| 857 guard->src->count) | |
| 858 : guard->count ().apply_probability (new_edge->probability); | |
| 859 | |
| 860 if (skip_count > e->count ()) | |
| 861 { | |
| 862 fprintf (dump_file, " Capping count; expect profile inconsistency\n"); | |
| 863 skip_count = e->count (); | |
| 864 } | |
| 865 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 866 { | |
| 867 fprintf (dump_file, " Estimated probability of skipping loop is "); | |
| 868 new_edge->probability.dump (dump_file); | |
| 869 fprintf (dump_file, "\n"); | |
| 870 } | |
| 871 | |
| 872 /* Update profile after the transform: | |
| 873 | |
| 874 First decrease count of path from newly hoisted loop guard | |
| 875 to loop header... */ | |
| 876 e->probability = new_edge->probability.invert (); | |
| 877 e->dest->count = e->count (); | |
| 878 | |
| 879 /* ... now update profile to represent that original guard will be optimized | |
| 880 away ... */ | |
| 881 guard->probability = profile_probability::never (); | |
| 882 not_guard->probability = profile_probability::always (); | |
| 883 | |
| 884 /* ... finally scale everything in the loop except for guarded basic blocks | |
| 885 where profile does not change. */ | |
| 886 basic_block *body = get_loop_body (loop); | |
| 887 | |
| 888 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 889 fprintf (dump_file, " Scaling nonguarded BBs in loop:"); | |
| 890 for (unsigned int i = 0; i < loop->num_nodes; i++) | |
| 891 { | |
| 892 basic_block bb = body[i]; | |
| 893 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest)) | |
| 894 { | |
| 895 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 896 fprintf (dump_file, " %i", bb->index); | |
| 897 if (e->probability.initialized_p ()) | |
| 898 scale_bbs_frequencies (&bb, 1, e->probability); | |
| 899 } | |
| 900 } | |
| 901 | |
| 902 if (fix_dom_of_exit) | |
| 903 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header); | |
| 904 /* Add NEW_ADGE argument for all phi in post-header block. */ | |
| 905 bb = exit->dest; | |
| 906 for (gphi_iterator gsi = gsi_start_phis (bb); | |
| 907 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 908 { | |
| 909 gphi *phi = gsi.phi (); | |
| 910 tree arg; | |
| 911 if (virtual_operand_p (gimple_phi_result (phi))) | |
| 912 { | |
| 913 arg = get_vop_from_header (loop); | |
| 914 if (arg == NULL_TREE) | |
| 915 /* Use exit edge argument. */ | |
| 916 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
| 917 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); | |
| 918 } | |
| 919 else | |
| 920 { | |
| 921 /* Use exit edge argument. */ | |
| 922 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
| 923 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); | |
| 924 } | |
| 925 } | |
| 926 | |
| 927 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 928 fprintf (dump_file, "\n guard hoisted.\n"); | |
| 929 | |
| 930 free (body); | |
| 931 } | |
| 932 | |
| 933 /* Return true if phi argument for exit edge can be used | |
| 934 for edge around loop. */ | |
| 935 | |
| 936 static bool | |
| 937 check_exit_phi (struct loop *loop) | |
| 938 { | |
| 939 edge exit = single_exit (loop); | |
| 940 basic_block pre_header = loop_preheader_edge (loop)->src; | |
| 941 | |
| 942 for (gphi_iterator gsi = gsi_start_phis (exit->dest); | |
| 943 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 944 { | |
| 945 gphi *phi = gsi.phi (); | |
| 946 tree arg; | |
| 947 gimple *def; | |
| 948 basic_block def_bb; | |
| 949 if (virtual_operand_p (gimple_phi_result (phi))) | |
| 950 continue; | |
| 951 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); | |
| 952 if (TREE_CODE (arg) != SSA_NAME) | |
| 953 continue; | |
| 954 def = SSA_NAME_DEF_STMT (arg); | |
| 955 if (!def) | |
| 956 continue; | |
| 957 def_bb = gimple_bb (def); | |
| 958 if (!def_bb) | |
| 959 continue; | |
| 960 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb)) | |
| 961 /* Definition inside loop! */ | |
| 962 return false; | |
| 963 /* Check loop closed phi invariant. */ | |
| 964 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header)) | |
| 965 return false; | |
| 966 } | |
| 967 return true; | |
| 968 } | |
| 969 | |
| 970 /* Loop unswitching pass. */ | |
| 971 | |
| 972 namespace { | |
| 973 | |
| 974 const pass_data pass_data_tree_unswitch = | |
| 975 { | |
| 976 GIMPLE_PASS, /* type */ | |
| 977 "unswitch", /* name */ | |
| 978 OPTGROUP_LOOP, /* optinfo_flags */ | |
| 979 TV_TREE_LOOP_UNSWITCH, /* tv_id */ | |
| 980 PROP_cfg, /* properties_required */ | |
| 981 0, /* properties_provided */ | |
| 982 0, /* properties_destroyed */ | |
| 983 0, /* todo_flags_start */ | |
| 984 0, /* todo_flags_finish */ | |
| 985 }; | |
| 986 | |
| 987 class pass_tree_unswitch : public gimple_opt_pass | |
| 988 { | |
| 989 public: | |
| 990 pass_tree_unswitch (gcc::context *ctxt) | |
| 991 : gimple_opt_pass (pass_data_tree_unswitch, ctxt) | |
| 992 {} | |
| 993 | |
| 994 /* opt_pass methods: */ | |
| 995 virtual bool gate (function *) { return flag_unswitch_loops != 0; } | |
| 996 virtual unsigned int execute (function *); | |
| 997 | |
| 998 }; // class pass_tree_unswitch | |
| 999 | |
| 1000 unsigned int | |
| 1001 pass_tree_unswitch::execute (function *fun) | |
| 1002 { | |
| 1003 if (number_of_loops (fun) <= 1) | |
| 1004 return 0; | |
| 1005 | |
| 1006 return tree_ssa_unswitch_loops (); | |
| 1007 } | |
| 1008 | |
| 1009 } // anon namespace | |
| 1010 | |
| 1011 gimple_opt_pass * | |
| 1012 make_pass_tree_unswitch (gcc::context *ctxt) | |
| 1013 { | |
| 1014 return new pass_tree_unswitch (ctxt); | |
| 1015 } | |
| 1016 | |
| 1017 |