1 /* Loop header copying on trees. 2 Copyright (C) 2004-2018 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 "backend.h" 24 #include "tree.h" 25 #include "gimple.h" 26 #include "cfghooks.h" 27 #include "tree-pass.h" 28 #include "gimple-ssa.h" 29 #include "gimple-iterator.h" 30 #include "tree-cfg.h" 31 #include "tree-into-ssa.h" 32 #include "cfgloop.h" 33 #include "tree-inline.h" 34 #include "tree-ssa-scopedtables.h" 35 #include "tree-ssa-threadedge.h" 36 #include "params.h" 37 38 /* Duplicates headers of loops if they are small enough, so that the statements 39 in the loop body are always executed when the loop is entered. This 40 increases effectiveness of code motion optimizations, and reduces the need 41 for loop preconditioning. */ 42 43 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT 44 instructions should be duplicated, limit is decreased by the actual 45 amount. */ 46 47 static bool 48 should_duplicate_loop_header_p (basic_block header, struct loop *loop, 49 int *limit) 50 { 51 gimple_stmt_iterator bsi; 52 gimple *last; 53 54 gcc_assert (!header->aux); 55 56 /* Loop header copying usually increases size of the code. This used not to 57 be true, since quite often it is possible to verify that the condition is 58 satisfied in the first iteration and therefore to eliminate it. Jump 59 threading handles these cases now. */ 60 if (optimize_loop_for_size_p (loop) 61 && !loop->force_vectorize) 62 { 63 if (dump_file && (dump_flags & TDF_DETAILS)) 64 fprintf (dump_file, 65 " Not duplicating bb %i: optimizing for size.\n", 66 header->index); 67 return false; 68 } 69 70 gcc_assert (EDGE_COUNT (header->succs) > 0); 71 if (single_succ_p (header)) 72 { 73 if (dump_file && (dump_flags & TDF_DETAILS)) 74 fprintf (dump_file, 75 " Not duplicating bb %i: it is single succ.\n", 76 header->index); 77 return false; 78 } 79 80 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) 81 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) 82 { 83 if (dump_file && (dump_flags & TDF_DETAILS)) 84 fprintf (dump_file, 85 " Not duplicating bb %i: both sucessors are in loop.\n", 86 loop->num); 87 return false; 88 } 89 90 /* If this is not the original loop header, we want it to have just 91 one predecessor in order to match the && pattern. */ 92 if (header != loop->header && !single_pred_p (header)) 93 { 94 if (dump_file && (dump_flags & TDF_DETAILS)) 95 fprintf (dump_file, 96 " Not duplicating bb %i: it has mutiple predecestors.\n", 97 header->index); 98 return false; 99 } 100 101 last = last_stmt (header); 102 if (gimple_code (last) != GIMPLE_COND) 103 { 104 if (dump_file && (dump_flags & TDF_DETAILS)) 105 fprintf (dump_file, 106 " Not duplicating bb %i: it does not end by conditional.\n", 107 header->index); 108 return false; 109 } 110 111 /* Count number of instructions and punt on calls. */ 112 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) 113 { 114 last = gsi_stmt (bsi); 115 116 if (gimple_code (last) == GIMPLE_LABEL) 117 continue; 118 119 if (is_gimple_debug (last)) 120 continue; 121 122 if (gimple_code (last) == GIMPLE_CALL 123 && (!gimple_inexpensive_call_p (as_a <gcall *> (last)) 124 /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed 125 at current loop's header. Don't copy in this case. */ 126 || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS))) 127 { 128 if (dump_file && (dump_flags & TDF_DETAILS)) 129 fprintf (dump_file, 130 " Not duplicating bb %i: it contains call.\n", 131 header->index); 132 return false; 133 } 134 135 *limit -= estimate_num_insns (last, &eni_size_weights); 136 if (*limit < 0) 137 { 138 if (dump_file && (dump_flags & TDF_DETAILS)) 139 fprintf (dump_file, 140 " Not duplicating bb %i contains too many insns.\n", 141 header->index); 142 return false; 143 } 144 } 145 if (dump_file && (dump_flags & TDF_DETAILS)) 146 fprintf (dump_file, " Will duplicate bb %i\n", header->index); 147 return true; 148 } 149 150 /* Checks whether LOOP is a do-while style loop. */ 151 152 static bool 153 do_while_loop_p (struct loop *loop) 154 { 155 gimple *stmt = last_stmt (loop->latch); 156 157 /* If the latch of the loop is not empty, it is not a do-while loop. */ 158 if (stmt 159 && gimple_code (stmt) != GIMPLE_LABEL) 160 { 161 if (dump_file && (dump_flags & TDF_DETAILS)) 162 fprintf (dump_file, 163 "Loop %i is not do-while loop: latch is not empty.\n", 164 loop->num); 165 return false; 166 } 167 168 /* If the header contains just a condition, it is not a do-while loop. */ 169 stmt = last_and_only_stmt (loop->header); 170 if (stmt 171 && gimple_code (stmt) == GIMPLE_COND) 172 { 173 if (dump_file && (dump_flags & TDF_DETAILS)) 174 fprintf (dump_file, 175 "Loop %i is not do-while loop: " 176 "header contains just condition.\n", loop->num); 177 return false; 178 } 179 if (dump_file && (dump_flags & TDF_DETAILS)) 180 fprintf (dump_file, "Loop %i is do-while loop\n", loop->num); 181 182 return true; 183 } 184 185 namespace { 186 187 /* Common superclass for both header-copying phases. */ 188 class ch_base : public gimple_opt_pass 189 { 190 protected: 191 ch_base (pass_data data, gcc::context *ctxt) 192 : gimple_opt_pass (data, ctxt) 193 {} 194 195 /* Copies headers of all loops in FUN for which process_loop_p is true. */ 196 unsigned int copy_headers (function *fun); 197 198 /* Return true to copy headers of LOOP or false to skip. */ 199 virtual bool process_loop_p (struct loop *loop) = 0; 200 }; 201 202 const pass_data pass_data_ch = 203 { 204 GIMPLE_PASS, /* type */ 205 "ch", /* name */ 206 OPTGROUP_LOOP, /* optinfo_flags */ 207 TV_TREE_CH, /* tv_id */ 208 ( PROP_cfg | PROP_ssa ), /* properties_required */ 209 0, /* properties_provided */ 210 0, /* properties_destroyed */ 211 0, /* todo_flags_start */ 212 0, /* todo_flags_finish */ 213 }; 214 215 class pass_ch : public ch_base 216 { 217 public: 218 pass_ch (gcc::context *ctxt) 219 : ch_base (pass_data_ch, ctxt) 220 {} 221 222 /* opt_pass methods: */ 223 virtual bool gate (function *) { return flag_tree_ch != 0; } 224 225 /* Initialize and finalize loop structures, copying headers inbetween. */ 226 virtual unsigned int execute (function *); 227 228 opt_pass * clone () { return new pass_ch (m_ctxt); } 229 230 protected: 231 /* ch_base method: */ 232 virtual bool process_loop_p (struct loop *loop); 233 }; // class pass_ch 234 235 const pass_data pass_data_ch_vect = 236 { 237 GIMPLE_PASS, /* type */ 238 "ch_vect", /* name */ 239 OPTGROUP_LOOP, /* optinfo_flags */ 240 TV_TREE_CH, /* tv_id */ 241 ( PROP_cfg | PROP_ssa ), /* properties_required */ 242 0, /* properties_provided */ 243 0, /* properties_destroyed */ 244 0, /* todo_flags_start */ 245 0, /* todo_flags_finish */ 246 }; 247 248 /* This is a more aggressive version of the same pass, designed to run just 249 before if-conversion and vectorization, to put more loops into the form 250 required for those phases. */ 251 class pass_ch_vect : public ch_base 252 { 253 public: 254 pass_ch_vect (gcc::context *ctxt) 255 : ch_base (pass_data_ch_vect, ctxt) 256 {} 257 258 /* opt_pass methods: */ 259 virtual bool gate (function *fun) 260 { 261 return flag_tree_ch != 0 262 && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops); 263 } 264 265 /* Just copy headers, no initialization/finalization of loop structures. */ 266 virtual unsigned int execute (function *); 267 268 protected: 269 /* ch_base method: */ 270 virtual bool process_loop_p (struct loop *loop); 271 }; // class pass_ch_vect 272 273 /* For all loops, copy the condition at the end of the loop body in front 274 of the loop. This is beneficial since it increases efficiency of 275 code motion optimizations. It also saves one jump on entry to the loop. */ 276 277 unsigned int 278 ch_base::copy_headers (function *fun) 279 { 280 struct loop *loop; 281 basic_block header; 282 edge exit, entry; 283 basic_block *bbs, *copied_bbs; 284 unsigned n_bbs; 285 unsigned bbs_size; 286 bool changed = false; 287 288 if (number_of_loops (fun) <= 1) 289 return 0; 290 291 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); 292 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); 293 bbs_size = n_basic_blocks_for_fn (fun); 294 295 FOR_EACH_LOOP (loop, 0) 296 { 297 int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS); 298 int remaining_limit = initial_limit; 299 if (dump_file && (dump_flags & TDF_DETAILS)) 300 fprintf (dump_file, 301 "Analyzing loop %i\n", loop->num); 302 303 header = loop->header; 304 305 /* If the loop is already a do-while style one (either because it was 306 written as such, or because jump threading transformed it into one), 307 we might be in fact peeling the first iteration of the loop. This 308 in general is not a good idea. */ 309 if (!process_loop_p (loop)) 310 continue; 311 312 /* Iterate the header copying up to limit; this takes care of the cases 313 like while (a && b) {...}, where we want to have both of the conditions 314 copied. TODO -- handle while (a || b) - like cases, by not requiring 315 the header to have just a single successor and copying up to 316 postdominator. */ 317 318 exit = NULL; 319 n_bbs = 0; 320 while (should_duplicate_loop_header_p (header, loop, &remaining_limit)) 321 { 322 /* Find a successor of header that is inside a loop; i.e. the new 323 header after the condition is copied. */ 324 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) 325 exit = EDGE_SUCC (header, 0); 326 else 327 exit = EDGE_SUCC (header, 1); 328 bbs[n_bbs++] = header; 329 gcc_assert (bbs_size > n_bbs); 330 header = exit->dest; 331 } 332 333 if (!exit) 334 continue; 335 336 if (dump_file && (dump_flags & TDF_DETAILS)) 337 fprintf (dump_file, 338 "Duplicating header of the loop %d up to edge %d->%d," 339 " %i insns.\n", 340 loop->num, exit->src->index, exit->dest->index, 341 initial_limit - remaining_limit); 342 343 /* Ensure that the header will have just the latch as a predecessor 344 inside the loop. */ 345 if (!single_pred_p (exit->dest)) 346 exit = single_pred_edge (split_edge (exit)); 347 348 entry = loop_preheader_edge (loop); 349 350 propagate_threaded_block_debug_into (exit->dest, entry->dest); 351 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs, 352 true)) 353 { 354 fprintf (dump_file, "Duplication failed.\n"); 355 continue; 356 } 357 358 /* If the loop has the form "for (i = j; i < j + 10; i++)" then 359 this copying can introduce a case where we rely on undefined 360 signed overflow to eliminate the preheader condition, because 361 we assume that "j < j + 10" is true. We don't want to warn 362 about that case for -Wstrict-overflow, because in general we 363 don't warn about overflow involving loops. Prevent the 364 warning by setting the no_warning flag in the condition. */ 365 if (warn_strict_overflow > 0) 366 { 367 unsigned int i; 368 369 for (i = 0; i < n_bbs; ++i) 370 { 371 gimple_stmt_iterator bsi; 372 373 for (bsi = gsi_start_bb (copied_bbs[i]); 374 !gsi_end_p (bsi); 375 gsi_next (&bsi)) 376 { 377 gimple *stmt = gsi_stmt (bsi); 378 if (gimple_code (stmt) == GIMPLE_COND) 379 { 380 tree lhs = gimple_cond_lhs (stmt); 381 if (gimple_cond_code (stmt) != EQ_EXPR 382 && gimple_cond_code (stmt) != NE_EXPR 383 && INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 384 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs))) 385 gimple_set_no_warning (stmt, true); 386 } 387 else if (is_gimple_assign (stmt)) 388 { 389 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 390 tree rhs1 = gimple_assign_rhs1 (stmt); 391 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison 392 && rhs_code != EQ_EXPR 393 && rhs_code != NE_EXPR 394 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) 395 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1))) 396 gimple_set_no_warning (stmt, true); 397 } 398 } 399 } 400 } 401 402 /* Ensure that the latch and the preheader is simple (we know that they 403 are not now, since there was the loop exit condition. */ 404 split_edge (loop_preheader_edge (loop)); 405 split_edge (loop_latch_edge (loop)); 406 407 changed = true; 408 } 409 410 if (changed) 411 update_ssa (TODO_update_ssa); 412 free (bbs); 413 free (copied_bbs); 414 415 return changed ? TODO_cleanup_cfg : 0; 416 } 417 418 /* Initialize the loop structures we need, and finalize after. */ 419 420 unsigned int 421 pass_ch::execute (function *fun) 422 { 423 loop_optimizer_init (LOOPS_HAVE_PREHEADERS 424 | LOOPS_HAVE_SIMPLE_LATCHES); 425 426 unsigned int res = copy_headers (fun); 427 428 loop_optimizer_finalize (); 429 return res; 430 } 431 432 /* Assume an earlier phase has already initialized all the loop structures that 433 we need here (and perhaps others too), and that these will be finalized by 434 a later phase. */ 435 436 unsigned int 437 pass_ch_vect::execute (function *fun) 438 { 439 return copy_headers (fun); 440 } 441 442 /* Apply header copying according to a very simple test of do-while shape. */ 443 444 bool 445 pass_ch::process_loop_p (struct loop *loop) 446 { 447 return !do_while_loop_p (loop); 448 } 449 450 /* Apply header-copying to loops where we might enable vectorization. */ 451 452 bool 453 pass_ch_vect::process_loop_p (struct loop *loop) 454 { 455 if (!flag_tree_loop_vectorize && !loop->force_vectorize) 456 return false; 457 458 if (loop->dont_vectorize) 459 return false; 460 461 if (!do_while_loop_p (loop)) 462 return true; 463 464 /* The vectorizer won't handle anything with multiple exits, so skip. */ 465 edge exit = single_exit (loop); 466 if (!exit) 467 return false; 468 469 /* Copy headers iff there looks to be code in the loop after the exit block, 470 i.e. the exit block has an edge to another block (besides the latch, 471 which should be empty). */ 472 edge_iterator ei; 473 edge e; 474 FOR_EACH_EDGE (e, ei, exit->src->succs) 475 if (!loop_exit_edge_p (loop, e) 476 && e->dest != loop->header 477 && e->dest != loop->latch) 478 return true; 479 480 return false; 481 } 482 483 } // anon namespace 484 485 gimple_opt_pass * 486 make_pass_ch_vect (gcc::context *ctxt) 487 { 488 return new pass_ch_vect (ctxt); 489 } 490 491 gimple_opt_pass * 492 make_pass_ch (gcc::context *ctxt) 493 { 494 return new pass_ch (ctxt); 495 } 496