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