gcc/cfgloopanal.c

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