1 /* Loop unswitching. 2 Copyright (C) 2004, 2005, 2007, 2008, 2010 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "tm.h" 24 #include "tree.h" 25 #include "tm_p.h" 26 #include "basic-block.h" 27 #include "output.h" 28 #include "tree-flow.h" 29 #include "tree-dump.h" 30 #include "timevar.h" 31 #include "cfgloop.h" 32 #include "params.h" 33 #include "tree-pass.h" 34 #include "tree-inline.h" 35 36 /* This file implements the loop unswitching, i.e. transformation of loops like 37 38 while (A) 39 { 40 if (inv) 41 B; 42 43 X; 44 45 if (!inv) 46 C; 47 } 48 49 where inv is the loop invariant, into 50 51 if (inv) 52 { 53 while (A) 54 { 55 B; 56 X; 57 } 58 } 59 else 60 { 61 while (A) 62 { 63 X; 64 C; 65 } 66 } 67 68 Inv is considered invariant iff the values it compares are both invariant; 69 tree-ssa-loop-im.c ensures that all the suitable conditions are in this 70 shape. */ 71 72 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); 73 static bool tree_unswitch_single_loop (struct loop *, int); 74 static tree tree_may_unswitch_on (basic_block, struct loop *); 75 76 /* Main entry point. Perform loop unswitching on all suitable loops. */ 77 78 unsigned int 79 tree_ssa_unswitch_loops (void) 80 { 81 loop_iterator li; 82 struct loop *loop; 83 bool changed = false; 84 85 /* Go through inner loops (only original ones). */ 86 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) 87 { 88 if (dump_file && (dump_flags & TDF_DETAILS)) 89 fprintf (dump_file, ";; Considering loop %d\n", loop->num); 90 91 /* Do not unswitch in cold regions. */ 92 if (optimize_loop_for_size_p (loop)) 93 { 94 if (dump_file && (dump_flags & TDF_DETAILS)) 95 fprintf (dump_file, ";; Not unswitching cold loops\n"); 96 continue; 97 } 98 99 /* The loop should not be too large, to limit code growth. */ 100 if (tree_num_loop_insns (loop, &eni_size_weights) 101 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) 102 { 103 if (dump_file && (dump_flags & TDF_DETAILS)) 104 fprintf (dump_file, ";; Not unswitching, loop too big\n"); 105 continue; 106 } 107 108 changed |= tree_unswitch_single_loop (loop, 0); 109 } 110 111 if (changed) 112 return TODO_cleanup_cfg; 113 return 0; 114 } 115 116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 117 basic blocks (for what it means see comments below). */ 118 119 static tree 120 tree_may_unswitch_on (basic_block bb, struct loop *loop) 121 { 122 gimple stmt, def; 123 tree cond, use; 124 basic_block def_bb; 125 ssa_op_iter iter; 126 127 /* BB must end in a simple conditional jump. */ 128 stmt = last_stmt (bb); 129 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 130 return NULL_TREE; 131 132 /* To keep the things simple, we do not directly remove the conditions, 133 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite 134 loop where we would unswitch again on such a condition. */ 135 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) 136 return NULL_TREE; 137 138 /* Condition must be invariant. */ 139 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 140 { 141 def = SSA_NAME_DEF_STMT (use); 142 def_bb = gimple_bb (def); 143 if (def_bb 144 && flow_bb_inside_loop_p (loop, def_bb)) 145 return NULL_TREE; 146 } 147 148 cond = build2 (gimple_cond_code (stmt), boolean_type_node, 149 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 150 151 return cond; 152 } 153 154 /* Simplifies COND using checks in front of the entry of the LOOP. Just very 155 simplish (sufficient to prevent us from duplicating loop in unswitching 156 unnecessarily). */ 157 158 static tree 159 simplify_using_entry_checks (struct loop *loop, tree cond) 160 { 161 edge e = loop_preheader_edge (loop); 162 gimple stmt; 163 164 while (1) 165 { 166 stmt = last_stmt (e->src); 167 if (stmt 168 && gimple_code (stmt) == GIMPLE_COND 169 && gimple_cond_code (stmt) == TREE_CODE (cond) 170 && operand_equal_p (gimple_cond_lhs (stmt), 171 TREE_OPERAND (cond, 0), 0) 172 && operand_equal_p (gimple_cond_rhs (stmt), 173 TREE_OPERAND (cond, 1), 0)) 174 return (e->flags & EDGE_TRUE_VALUE 175 ? boolean_true_node 176 : boolean_false_node); 177 178 if (!single_pred_p (e->src)) 179 return cond; 180 181 e = single_pred_edge (e->src); 182 if (e->src == ENTRY_BLOCK_PTR) 183 return cond; 184 } 185 } 186 187 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow 188 it to grow too much, it is too easy to create example on that the code would 189 grow exponentially. */ 190 191 static bool 192 tree_unswitch_single_loop (struct loop *loop, int num) 193 { 194 basic_block *bbs; 195 struct loop *nloop; 196 unsigned i, found; 197 tree cond = NULL_TREE; 198 gimple stmt; 199 bool changed = false; 200 201 i = 0; 202 bbs = get_loop_body (loop); 203 found = loop->num_nodes; 204 205 while (1) 206 { 207 /* Find a bb to unswitch on. */ 208 for (; i < loop->num_nodes; i++) 209 if ((cond = tree_may_unswitch_on (bbs[i], loop))) 210 break; 211 212 if (i == loop->num_nodes) 213 { 214 if (dump_file 215 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) 216 && (dump_flags & TDF_DETAILS)) 217 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); 218 219 if (found == loop->num_nodes) 220 { 221 free (bbs); 222 return changed; 223 } 224 break; 225 } 226 227 cond = simplify_using_entry_checks (loop, cond); 228 stmt = last_stmt (bbs[i]); 229 if (integer_nonzerop (cond)) 230 { 231 /* Remove false path. */ 232 gimple_cond_set_condition_from_tree (stmt, boolean_true_node); 233 changed = true; 234 } 235 else if (integer_zerop (cond)) 236 { 237 /* Remove true path. */ 238 gimple_cond_set_condition_from_tree (stmt, boolean_false_node); 239 changed = true; 240 } 241 /* Do not unswitch too much. */ 242 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) 243 { 244 i++; 245 continue; 246 } 247 /* In nested tree_unswitch_single_loop first optimize all conditions 248 using entry checks, then discover still reachable blocks in the 249 loop and find the condition only among those still reachable bbs. */ 250 else if (num != 0) 251 { 252 if (found == loop->num_nodes) 253 found = i; 254 i++; 255 continue; 256 } 257 else 258 { 259 found = i; 260 break; 261 } 262 263 update_stmt (stmt); 264 i++; 265 } 266 267 if (num != 0) 268 { 269 basic_block *tos, *worklist; 270 271 /* When called recursively, first do a quick discovery 272 of reachable bbs after the above changes and only 273 consider conditions in still reachable bbs. */ 274 tos = worklist = XNEWVEC (basic_block, loop->num_nodes); 275 276 for (i = 0; i < loop->num_nodes; i++) 277 bbs[i]->flags &= ~BB_REACHABLE; 278 279 /* Start with marking header. */ 280 *tos++ = bbs[0]; 281 bbs[0]->flags |= BB_REACHABLE; 282 283 /* Iterate: find everything reachable from what we've already seen 284 within the same innermost loop. Don't look through false edges 285 if condition is always true or true edges if condition is 286 always false. */ 287 while (tos != worklist) 288 { 289 basic_block b = *--tos; 290 edge e; 291 edge_iterator ei; 292 int flags = 0; 293 294 if (EDGE_COUNT (b->succs) == 2) 295 { 296 gimple stmt = last_stmt (b); 297 if (stmt 298 && gimple_code (stmt) == GIMPLE_COND) 299 { 300 if (gimple_cond_true_p (stmt)) 301 flags = EDGE_FALSE_VALUE; 302 else if (gimple_cond_false_p (stmt)) 303 flags = EDGE_TRUE_VALUE; 304 } 305 } 306 307 FOR_EACH_EDGE (e, ei, b->succs) 308 { 309 basic_block dest = e->dest; 310 311 if (dest->loop_father == loop 312 && !(dest->flags & BB_REACHABLE) 313 && !(e->flags & flags)) 314 { 315 *tos++ = dest; 316 dest->flags |= BB_REACHABLE; 317 } 318 } 319 } 320 321 free (worklist); 322 323 /* Find a bb to unswitch on. */ 324 for (; found < loop->num_nodes; found++) 325 if ((bbs[found]->flags & BB_REACHABLE) 326 && (cond = tree_may_unswitch_on (bbs[found], loop))) 327 break; 328 329 if (found == loop->num_nodes) 330 { 331 free (bbs); 332 return changed; 333 } 334 } 335 336 if (dump_file && (dump_flags & TDF_DETAILS)) 337 fprintf (dump_file, ";; Unswitching loop\n"); 338 339 initialize_original_copy_tables (); 340 /* Unswitch the loop on this condition. */ 341 nloop = tree_unswitch_loop (loop, bbs[found], cond); 342 if (!nloop) 343 { 344 free_original_copy_tables (); 345 free (bbs); 346 return changed; 347 } 348 349 /* Update the SSA form after unswitching. */ 350 update_ssa (TODO_update_ssa); 351 free_original_copy_tables (); 352 353 /* Invoke itself on modified loops. */ 354 tree_unswitch_single_loop (nloop, num + 1); 355 tree_unswitch_single_loop (loop, num + 1); 356 free (bbs); 357 return true; 358 } 359 360 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support 361 unswitching of innermost loops. COND is the condition determining which 362 loop is entered -- the new loop is entered if COND is true. Returns NULL 363 if impossible, new loop otherwise. */ 364 365 static struct loop * 366 tree_unswitch_loop (struct loop *loop, 367 basic_block unswitch_on, tree cond) 368 { 369 unsigned prob_true; 370 edge edge_true, edge_false; 371 372 /* Some sanity checking. */ 373 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); 374 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); 375 gcc_assert (loop->inner == NULL); 376 377 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); 378 prob_true = edge_true->probability; 379 return loop_version (loop, unshare_expr (cond), 380 NULL, prob_true, prob_true, 381 REG_BR_PROB_BASE - prob_true, false); 382 } 383