1 /* Loop header copying on trees. 2 Copyright (C) 2004-2015 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 "hash-set.h" 25 #include "machmode.h" 26 #include "vec.h" 27 #include "double-int.h" 28 #include "input.h" 29 #include "alias.h" 30 #include "symtab.h" 31 #include "wide-int.h" 32 #include "inchash.h" 33 #include "tree.h" 34 #include "fold-const.h" 35 #include "tm_p.h" 36 #include "predict.h" 37 #include "hard-reg-set.h" 38 #include "input.h" 39 #include "function.h" 40 #include "dominance.h" 41 #include "cfg.h" 42 #include "basic-block.h" 43 #include "tree-ssa-alias.h" 44 #include "internal-fn.h" 45 #include "gimple-expr.h" 46 #include "is-a.h" 47 #include "gimple.h" 48 #include "gimple-iterator.h" 49 #include "gimple-ssa.h" 50 #include "tree-cfg.h" 51 #include "tree-into-ssa.h" 52 #include "tree-pass.h" 53 #include "cfgloop.h" 54 #include "tree-inline.h" 55 #include "flags.h" 56 #include "tree-ssa-threadedge.h" 57 58 /* Duplicates headers of loops if they are small enough, so that the statements 59 in the loop body are always executed when the loop is entered. This 60 increases effectiveness of code motion optimizations, and reduces the need 61 for loop preconditioning. */ 62 63 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT 64 instructions should be duplicated, limit is decreased by the actual 65 amount. */ 66 67 static bool 68 should_duplicate_loop_header_p (basic_block header, struct loop *loop, 69 int *limit) 70 { 71 gimple_stmt_iterator bsi; 72 gimple last; 73 74 /* Do not copy one block more than once (we do not really want to do 75 loop peeling here). */ 76 if (header->aux) 77 return false; 78 79 /* Loop header copying usually increases size of the code. This used not to 80 be true, since quite often it is possible to verify that the condition is 81 satisfied in the first iteration and therefore to eliminate it. Jump 82 threading handles these cases now. */ 83 if (optimize_loop_for_size_p (loop)) 84 return false; 85 86 gcc_assert (EDGE_COUNT (header->succs) > 0); 87 if (single_succ_p (header)) 88 return false; 89 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) 90 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) 91 return false; 92 93 /* If this is not the original loop header, we want it to have just 94 one predecessor in order to match the && pattern. */ 95 if (header != loop->header && !single_pred_p (header)) 96 return false; 97 98 last = last_stmt (header); 99 if (gimple_code (last) != GIMPLE_COND) 100 return false; 101 102 /* Approximately copy the conditions that used to be used in jump.c -- 103 at most 20 insns and no calls. */ 104 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi)) 105 { 106 last = gsi_stmt (bsi); 107 108 if (gimple_code (last) == GIMPLE_LABEL) 109 continue; 110 111 if (is_gimple_debug (last)) 112 continue; 113 114 if (is_gimple_call (last)) 115 return false; 116 117 *limit -= estimate_num_insns (last, &eni_size_weights); 118 if (*limit < 0) 119 return false; 120 } 121 122 return true; 123 } 124 125 /* Checks whether LOOP is a do-while style loop. */ 126 127 static bool 128 do_while_loop_p (struct loop *loop) 129 { 130 gimple stmt = last_stmt (loop->latch); 131 132 /* If the latch of the loop is not empty, it is not a do-while loop. */ 133 if (stmt 134 && gimple_code (stmt) != GIMPLE_LABEL) 135 return false; 136 137 /* If the header contains just a condition, it is not a do-while loop. */ 138 stmt = last_and_only_stmt (loop->header); 139 if (stmt 140 && gimple_code (stmt) == GIMPLE_COND) 141 return false; 142 143 return true; 144 } 145 146 /* For all loops, copy the condition at the end of the loop body in front 147 of the loop. This is beneficial since it increases efficiency of 148 code motion optimizations. It also saves one jump on entry to the loop. */ 149 150 namespace { 151 152 const pass_data pass_data_ch = 153 { 154 GIMPLE_PASS, /* type */ 155 "ch", /* name */ 156 OPTGROUP_LOOP, /* optinfo_flags */ 157 TV_TREE_CH, /* tv_id */ 158 ( PROP_cfg | PROP_ssa ), /* properties_required */ 159 0, /* properties_provided */ 160 0, /* properties_destroyed */ 161 0, /* todo_flags_start */ 162 0, /* todo_flags_finish */ 163 }; 164 165 class pass_ch : public gimple_opt_pass 166 { 167 public: 168 pass_ch (gcc::context *ctxt) 169 : gimple_opt_pass (pass_data_ch, ctxt) 170 {} 171 172 /* opt_pass methods: */ 173 virtual bool gate (function *) { return flag_tree_ch != 0; } 174 virtual unsigned int execute (function *); 175 176 }; // class pass_ch 177 178 unsigned int 179 pass_ch::execute (function *fun) 180 { 181 struct loop *loop; 182 basic_block header; 183 edge exit, entry; 184 basic_block *bbs, *copied_bbs; 185 unsigned n_bbs; 186 unsigned bbs_size; 187 bool changed = false; 188 189 loop_optimizer_init (LOOPS_HAVE_PREHEADERS 190 | LOOPS_HAVE_SIMPLE_LATCHES); 191 if (number_of_loops (fun) <= 1) 192 { 193 loop_optimizer_finalize (); 194 return 0; 195 } 196 197 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); 198 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); 199 bbs_size = n_basic_blocks_for_fn (fun); 200 201 FOR_EACH_LOOP (loop, 0) 202 { 203 /* Copy at most 20 insns. */ 204 int limit = 20; 205 206 header = loop->header; 207 208 /* If the loop is already a do-while style one (either because it was 209 written as such, or because jump threading transformed it into one), 210 we might be in fact peeling the first iteration of the loop. This 211 in general is not a good idea. */ 212 if (do_while_loop_p (loop)) 213 continue; 214 215 /* Iterate the header copying up to limit; this takes care of the cases 216 like while (a && b) {...}, where we want to have both of the conditions 217 copied. TODO -- handle while (a || b) - like cases, by not requiring 218 the header to have just a single successor and copying up to 219 postdominator. */ 220 221 exit = NULL; 222 n_bbs = 0; 223 while (should_duplicate_loop_header_p (header, loop, &limit)) 224 { 225 /* Find a successor of header that is inside a loop; i.e. the new 226 header after the condition is copied. */ 227 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) 228 exit = EDGE_SUCC (header, 0); 229 else 230 exit = EDGE_SUCC (header, 1); 231 bbs[n_bbs++] = header; 232 gcc_assert (bbs_size > n_bbs); 233 header = exit->dest; 234 } 235 236 if (!exit) 237 continue; 238 239 if (dump_file && (dump_flags & TDF_DETAILS)) 240 fprintf (dump_file, 241 "Duplicating header of the loop %d up to edge %d->%d.\n", 242 loop->num, exit->src->index, exit->dest->index); 243 244 /* Ensure that the header will have just the latch as a predecessor 245 inside the loop. */ 246 if (!single_pred_p (exit->dest)) 247 exit = single_pred_edge (split_edge (exit)); 248 249 entry = loop_preheader_edge (loop); 250 251 propagate_threaded_block_debug_into (exit->dest, entry->dest); 252 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs, 253 true)) 254 { 255 fprintf (dump_file, "Duplication failed.\n"); 256 continue; 257 } 258 259 /* If the loop has the form "for (i = j; i < j + 10; i++)" then 260 this copying can introduce a case where we rely on undefined 261 signed overflow to eliminate the preheader condition, because 262 we assume that "j < j + 10" is true. We don't want to warn 263 about that case for -Wstrict-overflow, because in general we 264 don't warn about overflow involving loops. Prevent the 265 warning by setting the no_warning flag in the condition. */ 266 if (warn_strict_overflow > 0) 267 { 268 unsigned int i; 269 270 for (i = 0; i < n_bbs; ++i) 271 { 272 gimple_stmt_iterator bsi; 273 274 for (bsi = gsi_start_bb (copied_bbs[i]); 275 !gsi_end_p (bsi); 276 gsi_next (&bsi)) 277 { 278 gimple stmt = gsi_stmt (bsi); 279 if (gimple_code (stmt) == GIMPLE_COND) 280 gimple_set_no_warning (stmt, true); 281 else if (is_gimple_assign (stmt)) 282 { 283 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 284 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison) 285 gimple_set_no_warning (stmt, true); 286 } 287 } 288 } 289 } 290 291 /* Ensure that the latch and the preheader is simple (we know that they 292 are not now, since there was the loop exit condition. */ 293 split_edge (loop_preheader_edge (loop)); 294 split_edge (loop_latch_edge (loop)); 295 296 changed = true; 297 } 298 299 update_ssa (TODO_update_ssa); 300 free (bbs); 301 free (copied_bbs); 302 303 loop_optimizer_finalize (); 304 return changed ? TODO_cleanup_cfg : 0; 305 } 306 307 } // anon namespace 308 309 gimple_opt_pass * 310 make_pass_ch (gcc::context *ctxt) 311 { 312 return new pass_ch (ctxt); 313 } 314