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