1 /* Natural loop analysis code for GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 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 "rtl.h" 26 #include "hard-reg-set.h" 27 #include "obstack.h" 28 #include "basic-block.h" 29 #include "cfgloop.h" 30 #include "expr.h" 31 #include "output.h" 32 #include "graphds.h" 33 #include "params.h" 34 35 /* Checks whether BB is executed exactly once in each LOOP iteration. */ 36 37 bool 38 just_once_each_iteration_p (const struct loop *loop, const_basic_block bb) 39 { 40 /* It must be executed at least once each iteration. */ 41 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 42 return false; 43 44 /* And just once. */ 45 if (bb->loop_father != loop) 46 return false; 47 48 /* But this was not enough. We might have some irreducible loop here. */ 49 if (bb->flags & BB_IRREDUCIBLE_LOOP) 50 return false; 51 52 return true; 53 } 54 55 /* Marks blocks and edges that are part of non-recognized loops; i.e. we 56 throw away all latch edges and mark blocks inside any remaining cycle. 57 Everything is a bit complicated due to fact we do not want to do this 58 for parts of cycles that only "pass" through some loop -- i.e. for 59 each cycle, we want to mark blocks that belong directly to innermost 60 loop containing the whole cycle. 61 62 LOOPS is the loop tree. */ 63 64 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block) 65 #define BB_REPR(BB) ((BB)->index + 1) 66 67 bool 68 mark_irreducible_loops (void) 69 { 70 basic_block act; 71 struct graph_edge *ge; 72 edge e; 73 edge_iterator ei; 74 int src, dest; 75 unsigned depth; 76 struct graph *g; 77 int num = number_of_loops (); 78 struct loop *cloop; 79 bool irred_loop_found = false; 80 int i; 81 82 gcc_assert (current_loops != NULL); 83 84 /* Reset the flags. */ 85 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 86 { 87 act->flags &= ~BB_IRREDUCIBLE_LOOP; 88 FOR_EACH_EDGE (e, ei, act->succs) 89 e->flags &= ~EDGE_IRREDUCIBLE_LOOP; 90 } 91 92 /* Create the edge lists. */ 93 g = new_graph (last_basic_block + num); 94 95 FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 96 FOR_EACH_EDGE (e, ei, act->succs) 97 { 98 /* Ignore edges to exit. */ 99 if (e->dest == EXIT_BLOCK_PTR) 100 continue; 101 102 src = BB_REPR (act); 103 dest = BB_REPR (e->dest); 104 105 /* Ignore latch edges. */ 106 if (e->dest->loop_father->header == e->dest 107 && e->dest->loop_father->latch == act) 108 continue; 109 110 /* Edges inside a single loop should be left where they are. Edges 111 to subloop headers should lead to representative of the subloop, 112 but from the same place. 113 114 Edges exiting loops should lead from representative 115 of the son of nearest common ancestor of the loops in that 116 act lays. */ 117 118 if (e->dest->loop_father->header == e->dest) 119 dest = LOOP_REPR (e->dest->loop_father); 120 121 if (!flow_bb_inside_loop_p (act->loop_father, e->dest)) 122 { 123 depth = 1 + loop_depth (find_common_loop (act->loop_father, 124 e->dest->loop_father)); 125 if (depth == loop_depth (act->loop_father)) 126 cloop = act->loop_father; 127 else 128 cloop = VEC_index (loop_p, act->loop_father->superloops, depth); 129 130 src = LOOP_REPR (cloop); 131 } 132 133 add_edge (g, src, dest)->data = e; 134 } 135 136 /* Find the strongly connected components. */ 137 graphds_scc (g, NULL); 138 139 /* Mark the irreducible loops. */ 140 for (i = 0; i < g->n_vertices; i++) 141 for (ge = g->vertices[i].succ; ge; ge = ge->succ_next) 142 { 143 edge real = (edge) ge->data; 144 /* edge E in graph G is irreducible if it connects two vertices in the 145 same scc. */ 146 147 /* All edges should lead from a component with higher number to the 148 one with lower one. */ 149 gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component); 150 151 if (g->vertices[ge->src].component != g->vertices[ge->dest].component) 152 continue; 153 154 real->flags |= EDGE_IRREDUCIBLE_LOOP; 155 irred_loop_found = true; 156 if (flow_bb_inside_loop_p (real->src->loop_father, real->dest)) 157 real->src->flags |= BB_IRREDUCIBLE_LOOP; 158 } 159 160 free_graph (g); 161 162 loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); 163 return irred_loop_found; 164 } 165 166 /* Counts number of insns inside LOOP. */ 167 int 168 num_loop_insns (const struct loop *loop) 169 { 170 basic_block *bbs, bb; 171 unsigned i, ninsns = 0; 172 rtx insn; 173 174 bbs = get_loop_body (loop); 175 for (i = 0; i < loop->num_nodes; i++) 176 { 177 bb = bbs[i]; 178 FOR_BB_INSNS (bb, insn) 179 if (NONDEBUG_INSN_P (insn)) 180 ninsns++; 181 } 182 free (bbs); 183 184 if (!ninsns) 185 ninsns = 1; /* To avoid division by zero. */ 186 187 return ninsns; 188 } 189 190 /* Counts number of insns executed on average per iteration LOOP. */ 191 int 192 average_num_loop_insns (const struct loop *loop) 193 { 194 basic_block *bbs, bb; 195 unsigned i, binsns, ninsns, ratio; 196 rtx insn; 197 198 ninsns = 0; 199 bbs = get_loop_body (loop); 200 for (i = 0; i < loop->num_nodes; i++) 201 { 202 bb = bbs[i]; 203 204 binsns = 0; 205 FOR_BB_INSNS (bb, insn) 206 if (NONDEBUG_INSN_P (insn)) 207 binsns++; 208 209 ratio = loop->header->frequency == 0 210 ? BB_FREQ_MAX 211 : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency; 212 ninsns += binsns * ratio; 213 } 214 free (bbs); 215 216 ninsns /= BB_FREQ_MAX; 217 if (!ninsns) 218 ninsns = 1; /* To avoid division by zero. */ 219 220 return ninsns; 221 } 222 223 /* Returns expected number of iterations of LOOP, according to 224 measured or guessed profile. No bounding is done on the 225 value. */ 226 227 gcov_type 228 expected_loop_iterations_unbounded (const struct loop *loop) 229 { 230 edge e; 231 edge_iterator ei; 232 233 if (loop->latch->count || loop->header->count) 234 { 235 gcov_type count_in, count_latch, expected; 236 237 count_in = 0; 238 count_latch = 0; 239 240 FOR_EACH_EDGE (e, ei, loop->header->preds) 241 if (e->src == loop->latch) 242 count_latch = e->count; 243 else 244 count_in += e->count; 245 246 if (count_in == 0) 247 expected = count_latch * 2; 248 else 249 expected = (count_latch + count_in - 1) / count_in; 250 251 return expected; 252 } 253 else 254 { 255 int freq_in, freq_latch; 256 257 freq_in = 0; 258 freq_latch = 0; 259 260 FOR_EACH_EDGE (e, ei, loop->header->preds) 261 if (e->src == loop->latch) 262 freq_latch = EDGE_FREQUENCY (e); 263 else 264 freq_in += EDGE_FREQUENCY (e); 265 266 if (freq_in == 0) 267 return freq_latch * 2; 268 269 return (freq_latch + freq_in - 1) / freq_in; 270 } 271 } 272 273 /* Returns expected number of LOOP iterations. The returned value is bounded 274 by REG_BR_PROB_BASE. */ 275 276 unsigned 277 expected_loop_iterations (const struct loop *loop) 278 { 279 gcov_type expected = expected_loop_iterations_unbounded (loop); 280 return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); 281 } 282 283 /* Returns the maximum level of nesting of subloops of LOOP. */ 284 285 unsigned 286 get_loop_level (const struct loop *loop) 287 { 288 const struct loop *ploop; 289 unsigned mx = 0, l; 290 291 for (ploop = loop->inner; ploop; ploop = ploop->next) 292 { 293 l = get_loop_level (ploop); 294 if (l >= mx) 295 mx = l + 1; 296 } 297 return mx; 298 } 299 300 /* Returns estimate on cost of computing SEQ. */ 301 302 static unsigned 303 seq_cost (const_rtx seq, bool speed) 304 { 305 unsigned cost = 0; 306 rtx set; 307 308 for (; seq; seq = NEXT_INSN (seq)) 309 { 310 set = single_set (seq); 311 if (set) 312 cost += rtx_cost (set, SET, speed); 313 else 314 cost++; 315 } 316 317 return cost; 318 } 319 320 /* The properties of the target. */ 321 322 unsigned target_avail_regs; /* Number of available registers. */ 323 unsigned target_res_regs; /* Number of registers reserved for temporary 324 expressions. */ 325 unsigned target_reg_cost[2]; /* The cost for register when there still 326 is some reserve, but we are approaching 327 the number of available registers. */ 328 unsigned target_spill_cost[2]; /* The cost for register when we need 329 to spill. */ 330 331 /* Initialize the constants for computing set costs. */ 332 333 void 334 init_set_costs (void) 335 { 336 int speed; 337 rtx seq; 338 rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER); 339 rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1); 340 rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2); 341 rtx mem = validize_mem (gen_rtx_MEM (SImode, addr)); 342 unsigned i; 343 344 target_avail_regs = 0; 345 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 346 if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i) 347 && !fixed_regs[i]) 348 target_avail_regs++; 349 350 target_res_regs = 3; 351 352 for (speed = 0; speed < 2; speed++) 353 { 354 crtl->maybe_hot_insn_p = speed; 355 /* Set up the costs for using extra registers: 356 357 1) If not many free registers remain, we should prefer having an 358 additional move to decreasing the number of available registers. 359 (TARGET_REG_COST). 360 2) If no registers are available, we need to spill, which may require 361 storing the old value to memory and loading it back 362 (TARGET_SPILL_COST). */ 363 364 start_sequence (); 365 emit_move_insn (reg1, reg2); 366 seq = get_insns (); 367 end_sequence (); 368 target_reg_cost [speed] = seq_cost (seq, speed); 369 370 start_sequence (); 371 emit_move_insn (mem, reg1); 372 emit_move_insn (reg2, mem); 373 seq = get_insns (); 374 end_sequence (); 375 target_spill_cost [speed] = seq_cost (seq, speed); 376 } 377 default_rtl_profile (); 378 } 379 380 /* Estimates cost of increased register pressure caused by making N_NEW new 381 registers live around the loop. N_OLD is the number of registers live 382 around the loop. */ 383 384 unsigned 385 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed) 386 { 387 unsigned cost; 388 unsigned regs_needed = n_new + n_old; 389 390 /* If we have enough registers, we should use them and not restrict 391 the transformations unnecessarily. */ 392 if (regs_needed + target_res_regs <= target_avail_regs) 393 return 0; 394 395 if (regs_needed <= target_avail_regs) 396 /* If we are close to running out of registers, try to preserve 397 them. */ 398 cost = target_reg_cost [speed] * n_new; 399 else 400 /* If we run out of registers, it is very expensive to add another 401 one. */ 402 cost = target_spill_cost [speed] * n_new; 403 404 if (optimize && (flag_ira_region == IRA_REGION_ALL 405 || flag_ira_region == IRA_REGION_MIXED) 406 && number_of_loops () <= (unsigned) IRA_MAX_LOOPS_NUM) 407 /* IRA regional allocation deals with high register pressure 408 better. So decrease the cost (to do more accurate the cost 409 calculation for IRA, we need to know how many registers lives 410 through the loop transparently). */ 411 cost /= 2; 412 413 return cost; 414 } 415 416 /* Sets EDGE_LOOP_EXIT flag for all loop exits. */ 417 418 void 419 mark_loop_exit_edges (void) 420 { 421 basic_block bb; 422 edge e; 423 424 if (number_of_loops () <= 1) 425 return; 426 427 FOR_EACH_BB (bb) 428 { 429 edge_iterator ei; 430 431 FOR_EACH_EDGE (e, ei, bb->succs) 432 { 433 if (loop_outer (bb->loop_father) 434 && loop_exit_edge_p (bb->loop_father, e)) 435 e->flags |= EDGE_LOOP_EXIT; 436 else 437 e->flags &= ~EDGE_LOOP_EXIT; 438 } 439 } 440 } 441 442