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 = current_loops ? number_of_loops () : 1;
 277   int *queue1 = XNEWVEC (int, last_basic_block + num);
 278   int *queue2 = XNEWVEC (int, last_basic_block + num);
 279   int nq, depth;
 280   struct loop *cloop, *loop;
 281   loop_iterator li;
 282
 283   /* Reset the flags.  */
 284   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 285     {
 286       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 287       FOR_EACH_EDGE (e, ei, act->succs)
 288         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 289     }
 290
 291   /* Create the edge lists.  */
 292   g = new_graph (last_basic_block + num);
 293
 294   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 295     FOR_EACH_EDGE (e, ei, act->succs)
 296       {
 297         /* Ignore edges to exit.  */
 298         if (e->dest == EXIT_BLOCK_PTR)
 299           continue;
 300
 301         src = BB_REPR (act);
 302         dest = BB_REPR (e->dest);
 303
 304         if (current_loops)
 305           {
 306             /* Ignore latch edges.  */
 307             if (e->dest->loop_father->header == e->dest
 308                 && e->dest->loop_father->latch == act)
 309               continue;
 310
 311             /* Edges inside a single loop should be left where they are.  Edges
 312                to subloop headers should lead to representative of the subloop,
 313                but from the same place.
 314
 315                Edges exiting loops should lead from representative
 316                of the son of nearest common ancestor of the loops in that
 317                act lays.  */
 318
 319             if (e->dest->loop_father->header == e->dest)
 320               dest = LOOP_REPR (e->dest->loop_father);
 321
 322             if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 323               {
 324                 depth = find_common_loop (act->loop_father,
 325                                           e->dest->loop_father)->depth + 1;
 326                 if (depth == act->loop_father->depth)
 327                   cloop = act->loop_father;
 328                 else
 329                   cloop = act->loop_father->pred[depth];
 330
 331                 src = LOOP_REPR (cloop);
 332               }
 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   if (current_loops)
 349     {
 350       FOR_EACH_LOOP (li, loop, 0)
 351         {
 352           queue1[nq++] = LOOP_REPR (loop);
 353         }
 354     }
 355   dfs (g, queue1, nq, queue2, false);
 356   for (i = 0; i < nq; i++)
 357     queue1[i] = queue2[nq - i - 1];
 358   dfs (g, queue1, nq, NULL, true);
 359
 360   /* Mark the irreducible loops.  */
 361   for_each_edge (g, check_irred);
 362
 363   free_graph (g);
 364   free (queue1);
 365   free (queue2);
 366
 367   if (current_loops)
 368     current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 369 }
 370
 371 /* Counts number of insns inside LOOP.  */
 372 int
 373 num_loop_insns (struct loop *loop)
 374 {
 375   basic_block *bbs, bb;
 376   unsigned i, ninsns = 0;
 377   rtx insn;
 378
 379   bbs = get_loop_body (loop);
 380   for (i = 0; i < loop->num_nodes; i++)
 381     {
 382       bb = bbs[i];
 383       ninsns++;
 384       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 385         if (INSN_P (insn))
 386           ninsns++;
 387     }
 388   free(bbs);
 389
 390   return ninsns;
 391 }
 392
 393 /* Counts number of insns executed on average per iteration LOOP.  */
 394 int
 395 average_num_loop_insns (struct loop *loop)
 396 {
 397   basic_block *bbs, bb;
 398   unsigned i, binsns, ninsns, ratio;
 399   rtx insn;
 400
 401   ninsns = 0;
 402   bbs = get_loop_body (loop);
 403   for (i = 0; i < loop->num_nodes; i++)
 404     {
 405       bb = bbs[i];
 406
 407       binsns = 1;
 408       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 409         if (INSN_P (insn))
 410           binsns++;
 411
 412       ratio = loop->header->frequency == 0
 413               ? BB_FREQ_MAX
 414               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 415       ninsns += binsns * ratio;
 416     }
 417   free(bbs);
 418
 419   ninsns /= BB_FREQ_MAX;
 420   if (!ninsns)
 421     ninsns = 1; /* To avoid division by zero.  */
 422
 423   return ninsns;
 424 }
 425
 426 /* Returns expected number of LOOP iterations.
 427    Compute upper bound on number of iterations in case they do not fit integer
 428    to help loop peeling heuristics.  Use exact counts if at all possible.  */
 429 unsigned
 430 expected_loop_iterations (const struct loop *loop)
 431 {
 432   edge e;
 433   edge_iterator ei;
 434
 435   if (loop->latch->count || loop->header->count)
 436     {
 437       gcov_type count_in, count_latch, expected;
 438
 439       count_in = 0;
 440       count_latch = 0;
 441
 442       FOR_EACH_EDGE (e, ei, loop->header->preds)
 443         if (e->src == loop->latch)
 444           count_latch = e->count;
 445         else
 446           count_in += e->count;
 447
 448       if (count_in == 0)
 449         expected = count_latch * 2;
 450       else
 451         expected = (count_latch + count_in - 1) / count_in;
 452
 453       /* Avoid overflows.  */
 454       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 455     }
 456   else
 457     {
 458       int freq_in, freq_latch;
 459
 460       freq_in = 0;
 461       freq_latch = 0;
 462
 463       FOR_EACH_EDGE (e, ei, loop->header->preds)
 464         if (e->src == loop->latch)
 465           freq_latch = EDGE_FREQUENCY (e);
 466         else
 467           freq_in += EDGE_FREQUENCY (e);
 468
 469       if (freq_in == 0)
 470         return freq_latch * 2;
 471
 472       return (freq_latch + freq_in - 1) / freq_in;
 473     }
 474 }
 475
 476 /* Returns the maximum level of nesting of subloops of LOOP.  */
 477
 478 unsigned
 479 get_loop_level (const struct loop *loop)
 480 {
 481   const struct loop *ploop;
 482   unsigned mx = 0, l;
 483
 484   for (ploop = loop->inner; ploop; ploop = ploop->next)
 485     {
 486       l = get_loop_level (ploop);
 487       if (l >= mx)
 488         mx = l + 1;
 489     }
 490   return mx;
 491 }
 492
 493 /* Returns estimate on cost of computing SEQ.  */
 494
 495 static unsigned
 496 seq_cost (rtx seq)
 497 {
 498   unsigned cost = 0;
 499   rtx set;
 500
 501   for (; seq; seq = NEXT_INSN (seq))
 502     {
 503       set = single_set (seq);
 504       if (set)
 505         cost += rtx_cost (set, SET);
 506       else
 507         cost++;
 508     }
 509
 510   return cost;
 511 }
 512
 513 /* The properties of the target.  */
 514
 515 unsigned target_avail_regs;     /* Number of available registers.  */
 516 unsigned target_res_regs;       /* Number of reserved registers.  */
 517 unsigned target_small_cost;     /* The cost for register when there is a free one.  */
 518 unsigned target_pres_cost;      /* The cost for register when there are not too many
 519                                    free ones.  */
 520 unsigned target_spill_cost;     /* The cost for register when we need to spill.  */
 521
 522 /* Initialize the constants for computing set costs.  */
 523
 524 void
 525 init_set_costs (void)
 526 {
 527   rtx seq;
 528   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 529   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 530   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 531   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 532   unsigned i;
 533
 534   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 535     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 536         && !fixed_regs[i])
 537       target_avail_regs++;
 538
 539   target_res_regs = 3;
 540
 541   /* These are really just heuristic values.  */
 542
 543   start_sequence ();
 544   emit_move_insn (reg1, reg2);
 545   seq = get_insns ();
 546   end_sequence ();
 547   target_small_cost = seq_cost (seq);
 548   target_pres_cost = 2 * target_small_cost;
 549
 550   start_sequence ();
 551   emit_move_insn (mem, reg1);
 552   emit_move_insn (reg2, mem);
 553   seq = get_insns ();
 554   end_sequence ();
 555   target_spill_cost = seq_cost (seq);
 556 }
 557
 558 /* Calculates cost for having SIZE new loop global variables.  REGS_USED is the
 559    number of global registers used in loop.  N_USES is the number of relevant
 560    variable uses.  */
 561
 562 unsigned
 563 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
 564 {
 565   unsigned regs_needed = regs_used + size;
 566   unsigned cost = 0;
 567
 568   if (regs_needed + target_res_regs <= target_avail_regs)
 569     cost += target_small_cost * size;
 570   else if (regs_needed <= target_avail_regs)
 571     cost += target_pres_cost * size;
 572   else
 573     {
 574       cost += target_pres_cost * size;
 575       cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
 576     }
 577
 578   return cost;
 579 }
 580
 581 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 582
 583 void
 584 mark_loop_exit_edges (void)
 585 {
 586   basic_block bb;
 587   edge e;
 588
 589   if (!current_loops)
 590     return;
 591
 592   FOR_EACH_BB (bb)
 593     {
 594       edge_iterator ei;
 595
 596       FOR_EACH_EDGE (e, ei, bb->succs)
 597         {
 598           if (bb->loop_father->outer
 599               && loop_exit_edge_p (bb->loop_father, e))
 600             e->flags |= EDGE_LOOP_EXIT;
 601           else
 602             e->flags &= ~EDGE_LOOP_EXIT;
 603         }
 604     }
 605 }
 606