gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  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
  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, 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 /* Structure representing edge of a graph.  */
  54
  55 struct edge
  56 {
  57   int src, dest;        /* Source and destination.  */
  58   struct edge *pred_next, *succ_next;
  59                         /* Next edge in predecessor and successor lists.  */
  60   void *data;           /* Data attached to the edge.  */
  61 };
  62
  63 /* Structure representing vertex of a graph.  */
  64
  65 struct vertex
  66 {
  67   struct edge *pred, *succ;
  68                         /* Lists of predecessors and successors.  */
  69   int component;        /* Number of dfs restarts before reaching the
  70                            vertex.  */
  71   int post;             /* Postorder number.  */
  72 };
  73
  74 /* Structure representing a graph.  */
  75
  76 struct graph
  77 {
  78   int n_vertices;       /* Number of vertices.  */
  79   struct vertex *vertices;
  80                         /* The vertices.  */
  81 };
  82
  83 /* Dumps graph G into F.  */
  84
  85 extern void dump_graph (FILE *, struct graph *);
  86
  87 void
  88 dump_graph (FILE *f, struct graph *g)
  89 {
  90   int i;
  91   struct edge *e;
  92
  93   for (i = 0; i < g->n_vertices; i++)
  94     {
  95       if (!g->vertices[i].pred
  96           && !g->vertices[i].succ)
  97         continue;
  98
  99       fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
 100       for (e = g->vertices[i].pred; e; e = e->pred_next)
 101         fprintf (f, " %d", e->src);
 102       fprintf (f, "\n");
 103
 104       fprintf (f, "\t->");
 105       for (e = g->vertices[i].succ; e; e = e->succ_next)
 106         fprintf (f, " %d", e->dest);
 107       fprintf (f, "\n");
 108     }
 109 }
 110
 111 /* Creates a new graph with N_VERTICES vertices.  */
 112
 113 static struct graph *
 114 new_graph (int n_vertices)
 115 {
 116   struct graph *g = XNEW (struct graph);
 117
 118   g->n_vertices = n_vertices;
 119   g->vertices = XCNEWVEC (struct vertex, n_vertices);
 120
 121   return g;
 122 }
 123
 124 /* Adds an edge from F to T to graph G, with DATA attached.  */
 125
 126 static void
 127 add_edge (struct graph *g, int f, int t, void *data)
 128 {
 129   struct edge *e = xmalloc (sizeof (struct edge));
 130
 131   e->src = f;
 132   e->dest = t;
 133   e->data = data;
 134
 135   e->pred_next = g->vertices[t].pred;
 136   g->vertices[t].pred = e;
 137
 138   e->succ_next = g->vertices[f].succ;
 139   g->vertices[f].succ = e;
 140 }
 141
 142 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
 143    The vertices in postorder are stored into QT.  If FORWARD is false,
 144    backward dfs is run.  */
 145
 146 static void
 147 dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
 148 {
 149   int i, tick = 0, v, comp = 0, top;
 150   struct edge *e;
 151   struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
 152
 153   for (i = 0; i < g->n_vertices; i++)
 154     {
 155       g->vertices[i].component = -1;
 156       g->vertices[i].post = -1;
 157     }
 158
 159 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
 160 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
 161 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
 162 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
 163
 164   for (i = 0; i < nq; i++)
 165     {
 166       v = qs[i];
 167       if (g->vertices[v].post != -1)
 168         continue;
 169
 170       g->vertices[v].component = comp++;
 171       e = FST_EDGE (v);
 172       top = 0;
 173
 174       while (1)
 175         {
 176           while (e && g->vertices[EDGE_DEST (e)].component != -1)
 177             e = NEXT_EDGE (e);
 178
 179           if (!e)
 180             {
 181               if (qt)
 182                 qt[tick] = v;
 183               g->vertices[v].post = tick++;
 184
 185               if (!top)
 186                 break;
 187
 188               e = stack[--top];
 189               v = EDGE_SRC (e);
 190               e = NEXT_EDGE (e);
 191               continue;
 192             }
 193
 194           stack[top++] = e;
 195           v = EDGE_DEST (e);
 196           e = FST_EDGE (v);
 197           g->vertices[v].component = comp - 1;
 198         }
 199     }
 200
 201   free (stack);
 202 }
 203
 204 /* Marks the edge E in graph G irreducible if it connects two vertices in the
 205    same scc.  */
 206
 207 static void
 208 check_irred (struct graph *g, struct edge *e)
 209 {
 210   edge real = e->data;
 211
 212   /* All edges should lead from a component with higher number to the
 213      one with lower one.  */
 214   gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
 215
 216   if (g->vertices[e->src].component != g->vertices[e->dest].component)
 217     return;
 218
 219   real->flags |= EDGE_IRREDUCIBLE_LOOP;
 220   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
 221     real->src->flags |= BB_IRREDUCIBLE_LOOP;
 222 }
 223
 224 /* Runs CALLBACK for all edges in G.  */
 225
 226 static void
 227 for_each_edge (struct graph *g,
 228                void (callback) (struct graph *, struct edge *))
 229 {
 230   struct edge *e;
 231   int i;
 232
 233   for (i = 0; i < g->n_vertices; i++)
 234     for (e = g->vertices[i].succ; e; e = e->succ_next)
 235       callback (g, e);
 236 }
 237
 238 /* Releases the memory occupied by G.  */
 239
 240 static void
 241 free_graph (struct graph *g)
 242 {
 243   struct edge *e, *n;
 244   int i;
 245
 246   for (i = 0; i < g->n_vertices; i++)
 247     for (e = g->vertices[i].succ; e; e = n)
 248       {
 249         n = e->succ_next;
 250         free (e);
 251       }
 252   free (g->vertices);
 253   free (g);
 254 }
 255
 256 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
 257    throw away all latch edges and mark blocks inside any remaining cycle.
 258    Everything is a bit complicated due to fact we do not want to do this
 259    for parts of cycles that only "pass" through some loop -- i.e. for
 260    each cycle, we want to mark blocks that belong directly to innermost
 261    loop containing the whole cycle.
 262
 263    LOOPS is the loop tree.  */
 264
 265 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
 266 #define BB_REPR(BB) ((BB)->index + 1)
 267
 268 void
 269 mark_irreducible_loops (void)
 270 {
 271   basic_block act;
 272   edge e;
 273   edge_iterator ei;
 274   int i, src, dest;
 275   struct graph *g;
 276   int num = number_of_loops ();
 277   int *queue1 = XNEWVEC (int, last_basic_block + num);
 278   int *queue2 = XNEWVEC (int, last_basic_block + num);
 279   int nq;
 280   unsigned depth;
 281   struct loop *cloop, *loop;
 282   loop_iterator li;
 283
 284   gcc_assert (current_loops != NULL);
 285
 286   /* Reset the flags.  */
 287   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 288     {
 289       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 290       FOR_EACH_EDGE (e, ei, act->succs)
 291         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 292     }
 293
 294   /* Create the edge lists.  */
 295   g = new_graph (last_basic_block + num);
 296
 297   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 298     FOR_EACH_EDGE (e, ei, act->succs)
 299       {
 300         /* Ignore edges to exit.  */
 301         if (e->dest == EXIT_BLOCK_PTR)
 302           continue;
 303
 304         src = BB_REPR (act);
 305         dest = BB_REPR (e->dest);
 306
 307         /* Ignore latch edges.  */
 308         if (e->dest->loop_father->header == e->dest
 309             && e->dest->loop_father->latch == act)
 310           continue;
 311
 312         /* Edges inside a single loop should be left where they are.  Edges
 313            to subloop headers should lead to representative of the subloop,
 314            but from the same place.
 315
 316            Edges exiting loops should lead from representative
 317            of the son of nearest common ancestor of the loops in that
 318            act lays.  */
 319
 320         if (e->dest->loop_father->header == e->dest)
 321           dest = LOOP_REPR (e->dest->loop_father);
 322
 323         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 324           {
 325             depth = 1 + loop_depth (find_common_loop (act->loop_father,
 326                                                       e->dest->loop_father));
 327             if (depth == loop_depth (act->loop_father))
 328               cloop = act->loop_father;
 329             else
 330               cloop = VEC_index (loop_p, act->loop_father->superloops, depth);
 331
 332             src = LOOP_REPR (cloop);
 333           }
 334
 335         add_edge (g, src, dest, e);
 336       }
 337
 338   /* Find the strongly connected components.  Use the algorithm of Tarjan --
 339      first determine the postorder dfs numbering in reversed graph, then
 340      run the dfs on the original graph in the order given by decreasing
 341      numbers assigned by the previous pass.  */
 342   nq = 0;
 343   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 344     {
 345       queue1[nq++] = BB_REPR (act);
 346     }
 347
 348   FOR_EACH_LOOP (li, loop, 0)
 349     {
 350       queue1[nq++] = LOOP_REPR (loop);
 351     }
 352   dfs (g, queue1, nq, queue2, false);
 353   for (i = 0; i < nq; i++)
 354     queue1[i] = queue2[nq - i - 1];
 355   dfs (g, queue1, nq, NULL, true);
 356
 357   /* Mark the irreducible loops.  */
 358   for_each_edge (g, check_irred);
 359
 360   free_graph (g);
 361   free (queue1);
 362   free (queue2);
 363
 364   current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 365 }
 366
 367 /* Counts number of insns inside LOOP.  */
 368 int
 369 num_loop_insns (struct loop *loop)
 370 {
 371   basic_block *bbs, bb;
 372   unsigned i, ninsns = 0;
 373   rtx insn;
 374
 375   bbs = get_loop_body (loop);
 376   for (i = 0; i < loop->num_nodes; i++)
 377     {
 378       bb = bbs[i];
 379       ninsns++;
 380       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 381         if (INSN_P (insn))
 382           ninsns++;
 383     }
 384   free(bbs);
 385
 386   return ninsns;
 387 }
 388
 389 /* Counts number of insns executed on average per iteration LOOP.  */
 390 int
 391 average_num_loop_insns (struct loop *loop)
 392 {
 393   basic_block *bbs, bb;
 394   unsigned i, binsns, ninsns, ratio;
 395   rtx insn;
 396
 397   ninsns = 0;
 398   bbs = get_loop_body (loop);
 399   for (i = 0; i < loop->num_nodes; i++)
 400     {
 401       bb = bbs[i];
 402
 403       binsns = 1;
 404       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 405         if (INSN_P (insn))
 406           binsns++;
 407
 408       ratio = loop->header->frequency == 0
 409               ? BB_FREQ_MAX
 410               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 411       ninsns += binsns * ratio;
 412     }
 413   free(bbs);
 414
 415   ninsns /= BB_FREQ_MAX;
 416   if (!ninsns)
 417     ninsns = 1; /* To avoid division by zero.  */
 418
 419   return ninsns;
 420 }
 421
 422 /* Returns expected number of iterations of LOOP, according to
 423    measured or guessed profile.  No bounding is done on the
 424    value.  */
 425
 426 gcov_type
 427 expected_loop_iterations_unbounded (const struct loop *loop)
 428 {
 429   edge e;
 430   edge_iterator ei;
 431
 432   if (loop->latch->count || loop->header->count)
 433     {
 434       gcov_type count_in, count_latch, expected;
 435
 436       count_in = 0;
 437       count_latch = 0;
 438
 439       FOR_EACH_EDGE (e, ei, loop->header->preds)
 440         if (e->src == loop->latch)
 441           count_latch = e->count;
 442         else
 443           count_in += e->count;
 444
 445       if (count_in == 0)
 446         expected = count_latch * 2;
 447       else
 448         expected = (count_latch + count_in - 1) / count_in;
 449
 450       return expected;
 451     }
 452   else
 453     {
 454       int freq_in, freq_latch;
 455
 456       freq_in = 0;
 457       freq_latch = 0;
 458
 459       FOR_EACH_EDGE (e, ei, loop->header->preds)
 460         if (e->src == loop->latch)
 461           freq_latch = EDGE_FREQUENCY (e);
 462         else
 463           freq_in += EDGE_FREQUENCY (e);
 464
 465       if (freq_in == 0)
 466         return freq_latch * 2;
 467
 468       return (freq_latch + freq_in - 1) / freq_in;
 469     }
 470 }
 471
 472 /* Returns expected number of LOOP iterations.  The returned value is bounded
 473    by REG_BR_PROB_BASE.  */
 474
 475 unsigned
 476 expected_loop_iterations (const struct loop *loop)
 477 {
 478   gcov_type expected = expected_loop_iterations_unbounded (loop);
 479   return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 480 }
 481
 482 /* Returns the maximum level of nesting of subloops of LOOP.  */
 483
 484 unsigned
 485 get_loop_level (const struct loop *loop)
 486 {
 487   const struct loop *ploop;
 488   unsigned mx = 0, l;
 489
 490   for (ploop = loop->inner; ploop; ploop = ploop->next)
 491     {
 492       l = get_loop_level (ploop);
 493       if (l >= mx)
 494         mx = l + 1;
 495     }
 496   return mx;
 497 }
 498
 499 /* Returns estimate on cost of computing SEQ.  */
 500
 501 static unsigned
 502 seq_cost (rtx seq)
 503 {
 504   unsigned cost = 0;
 505   rtx set;
 506
 507   for (; seq; seq = NEXT_INSN (seq))
 508     {
 509       set = single_set (seq);
 510       if (set)
 511         cost += rtx_cost (set, SET);
 512       else
 513         cost++;
 514     }
 515
 516   return cost;
 517 }
 518
 519 /* The properties of the target.  */
 520
 521 unsigned target_avail_regs;     /* Number of available registers.  */
 522 unsigned target_res_regs;       /* Number of registers reserved for temporary
 523                                    expressions.  */
 524 unsigned target_reg_cost;       /* The cost for register when there still
 525                                    is some reserve, but we are approaching
 526                                    the number of available registers.  */
 527 unsigned target_spill_cost;     /* The cost for register when we need
 528                                    to spill.  */
 529
 530 /* Initialize the constants for computing set costs.  */
 531
 532 void
 533 init_set_costs (void)
 534 {
 535   rtx seq;
 536   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 537   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 538   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 539   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 540   unsigned i;
 541
 542   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 543     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 544         && !fixed_regs[i])
 545       target_avail_regs++;
 546
 547   target_res_regs = 3;
 548
 549   /* Set up the costs for using extra registers:
 550
 551      1) If not many free registers remain, we should prefer having an
 552         additional move to decreasing the number of available registers.
 553         (TARGET_REG_COST).
 554      2) If no registers are available, we need to spill, which may require
 555         storing the old value to memory and loading it back
 556         (TARGET_SPILL_COST).  */
 557
 558   start_sequence ();
 559   emit_move_insn (reg1, reg2);
 560   seq = get_insns ();
 561   end_sequence ();
 562   target_reg_cost = seq_cost (seq);
 563
 564   start_sequence ();
 565   emit_move_insn (mem, reg1);
 566   emit_move_insn (reg2, mem);
 567   seq = get_insns ();
 568   end_sequence ();
 569   target_spill_cost = seq_cost (seq);
 570 }
 571
 572 /* Estimates cost of increased register pressure caused by making N_NEW new
 573    registers live around the loop.  N_OLD is the number of registers live
 574    around the loop.  */
 575
 576 unsigned
 577 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old)
 578 {
 579   unsigned regs_needed = n_new + n_old;
 580
 581   /* If we have enough registers, we should use them and not restrict
 582      the transformations unnecessarily.  */
 583   if (regs_needed + target_res_regs <= target_avail_regs)
 584     return 0;
 585
 586   /* If we are close to running out of registers, try to preserve them.  */
 587   if (regs_needed <= target_avail_regs)
 588     return target_reg_cost * n_new;
 589
 590   /* If we run out of registers, it is very expensive to add another one.  */
 591   return target_spill_cost * n_new;
 592 }
 593
 594 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 595
 596 void
 597 mark_loop_exit_edges (void)
 598 {
 599   basic_block bb;
 600   edge e;
 601
 602   if (number_of_loops () <= 1)
 603     return;
 604
 605   FOR_EACH_BB (bb)
 606     {
 607       edge_iterator ei;
 608
 609       FOR_EACH_EDGE (e, ei, bb->succs)
 610         {
 611           if (loop_outer (bb->loop_father)
 612               && loop_exit_edge_p (bb->loop_father, e))
 613             e->flags |= EDGE_LOOP_EXIT;
 614           else
 615             e->flags &= ~EDGE_LOOP_EXIT;
 616         }
 617     }
 618 }
 619