gcc/cfgloopanal.c

   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_clobbered_regs; /* Number of available registers that are
 324                                    call-clobbered.  */
 325 unsigned target_res_regs;       /* Number of registers reserved for temporary
 326                                    expressions.  */
 327 unsigned target_reg_cost[2];    /* The cost for register when there still
 328                                    is some reserve, but we are approaching
 329                                    the number of available registers.  */
 330 unsigned target_spill_cost[2];  /* The cost for register when we need
 331                                    to spill.  */
 332
 333 /* Initialize the constants for computing set costs.  */
 334
 335 void
 336 init_set_costs (void)
 337 {
 338   int speed;
 339   rtx seq;
 340   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 341   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 342   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 343   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 344   unsigned i;
 345
 346   target_avail_regs = 0;
 347   target_clobbered_regs = 0;
 348   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 349     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 350         && !fixed_regs[i])
 351       {
 352         target_avail_regs++;
 353         if (call_used_regs[i])
 354           target_clobbered_regs++;
 355       }
 356
 357   target_res_regs = 3;
 358
 359   for (speed = 0; speed < 2; speed++)
 360      {
 361       crtl->maybe_hot_insn_p = speed;
 362       /* Set up the costs for using extra registers:
 363
 364          1) If not many free registers remain, we should prefer having an
 365             additional move to decreasing the number of available registers.
 366             (TARGET_REG_COST).
 367          2) If no registers are available, we need to spill, which may require
 368             storing the old value to memory and loading it back
 369             (TARGET_SPILL_COST).  */
 370
 371       start_sequence ();
 372       emit_move_insn (reg1, reg2);
 373       seq = get_insns ();
 374       end_sequence ();
 375       target_reg_cost [speed] = seq_cost (seq, speed);
 376
 377       start_sequence ();
 378       emit_move_insn (mem, reg1);
 379       emit_move_insn (reg2, mem);
 380       seq = get_insns ();
 381       end_sequence ();
 382       target_spill_cost [speed] = seq_cost (seq, speed);
 383     }
 384   default_rtl_profile ();
 385 }
 386
 387 /* Estimates cost of increased register pressure caused by making N_NEW new
 388    registers live around the loop.  N_OLD is the number of registers live
 389    around the loop.  If CALL_P is true, also take into account that
 390    call-used registers may be clobbered in the loop body, reducing the
 391    number of available registers before we spill.  */
 392
 393 unsigned
 394 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
 395                             bool call_p)
 396 {
 397   unsigned cost;
 398   unsigned regs_needed = n_new + n_old;
 399   unsigned available_regs = target_avail_regs;
 400
 401   /* If there is a call in the loop body, the call-clobbered registers
 402      are not available for loop invariants.  */
 403   if (call_p)
 404     available_regs = available_regs - target_clobbered_regs;
 405
 406   /* If we have enough registers, we should use them and not restrict
 407      the transformations unnecessarily.  */
 408   if (regs_needed + target_res_regs <= available_regs)
 409     return 0;
 410
 411   if (regs_needed <= available_regs)
 412     /* If we are close to running out of registers, try to preserve
 413        them.  */
 414     cost = target_reg_cost [speed] * n_new;
 415   else
 416     /* If we run out of registers, it is very expensive to add another
 417        one.  */
 418     cost = target_spill_cost [speed] * n_new;
 419
 420   if (optimize && (flag_ira_region == IRA_REGION_ALL
 421                    || flag_ira_region == IRA_REGION_MIXED)
 422       && number_of_loops () <= (unsigned) IRA_MAX_LOOPS_NUM)
 423     /* IRA regional allocation deals with high register pressure
 424        better.  So decrease the cost (to do more accurate the cost
 425        calculation for IRA, we need to know how many registers lives
 426        through the loop transparently).  */
 427     cost /= 2;
 428
 429   return cost;
 430 }
 431
 432 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 433
 434 void
 435 mark_loop_exit_edges (void)
 436 {
 437   basic_block bb;
 438   edge e;
 439
 440   if (number_of_loops () <= 1)
 441     return;
 442
 443   FOR_EACH_BB (bb)
 444     {
 445       edge_iterator ei;
 446
 447       FOR_EACH_EDGE (e, ei, bb->succs)
 448         {
 449           if (loop_outer (bb->loop_father)
 450               && loop_exit_edge_p (bb->loop_father, e))
 451             e->flags |= EDGE_LOOP_EXIT;
 452           else
 453             e->flags &= ~EDGE_LOOP_EXIT;
 454         }
 455     }
 456 }
 457