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