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;
 280   unsigned depth;
 281   struct loop *cloop, *loop;
 282   loop_iterator li;
 283
 284   /* Reset the flags.  */
 285   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 286     {
 287       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 288       FOR_EACH_EDGE (e, ei, act->succs)
 289         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 290     }
 291
 292   /* Create the edge lists.  */
 293   g = new_graph (last_basic_block + num);
 294
 295   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 296     FOR_EACH_EDGE (e, ei, act->succs)
 297       {
 298         /* Ignore edges to exit.  */
 299         if (e->dest == EXIT_BLOCK_PTR)
 300           continue;
 301
 302         src = BB_REPR (act);
 303         dest = BB_REPR (e->dest);
 304
 305         if (current_loops)
 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,
 331                                      depth);
 332
 333                 src = LOOP_REPR (cloop);
 334               }
 335           }
 336
 337         add_edge (g, src, dest, e);
 338       }
 339
 340   /* Find the strongly connected components.  Use the algorithm of Tarjan --
 341      first determine the postorder dfs numbering in reversed graph, then
 342      run the dfs on the original graph in the order given by decreasing
 343      numbers assigned by the previous pass.  */
 344   nq = 0;
 345   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 346     {
 347       queue1[nq++] = BB_REPR (act);
 348     }
 349
 350   if (current_loops)
 351     {
 352       FOR_EACH_LOOP (li, loop, 0)
 353         {
 354           queue1[nq++] = LOOP_REPR (loop);
 355         }
 356     }
 357   dfs (g, queue1, nq, queue2, false);
 358   for (i = 0; i < nq; i++)
 359     queue1[i] = queue2[nq - i - 1];
 360   dfs (g, queue1, nq, NULL, true);
 361
 362   /* Mark the irreducible loops.  */
 363   for_each_edge (g, check_irred);
 364
 365   free_graph (g);
 366   free (queue1);
 367   free (queue2);
 368
 369   if (current_loops)
 370     current_loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 371 }
 372
 373 /* Counts number of insns inside LOOP.  */
 374 int
 375 num_loop_insns (struct loop *loop)
 376 {
 377   basic_block *bbs, bb;
 378   unsigned i, ninsns = 0;
 379   rtx insn;
 380
 381   bbs = get_loop_body (loop);
 382   for (i = 0; i < loop->num_nodes; i++)
 383     {
 384       bb = bbs[i];
 385       ninsns++;
 386       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 387         if (INSN_P (insn))
 388           ninsns++;
 389     }
 390   free(bbs);
 391
 392   return ninsns;
 393 }
 394
 395 /* Counts number of insns executed on average per iteration LOOP.  */
 396 int
 397 average_num_loop_insns (struct loop *loop)
 398 {
 399   basic_block *bbs, bb;
 400   unsigned i, binsns, ninsns, ratio;
 401   rtx insn;
 402
 403   ninsns = 0;
 404   bbs = get_loop_body (loop);
 405   for (i = 0; i < loop->num_nodes; i++)
 406     {
 407       bb = bbs[i];
 408
 409       binsns = 1;
 410       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 411         if (INSN_P (insn))
 412           binsns++;
 413
 414       ratio = loop->header->frequency == 0
 415               ? BB_FREQ_MAX
 416               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 417       ninsns += binsns * ratio;
 418     }
 419   free(bbs);
 420
 421   ninsns /= BB_FREQ_MAX;
 422   if (!ninsns)
 423     ninsns = 1; /* To avoid division by zero.  */
 424
 425   return ninsns;
 426 }
 427
 428 /* Returns expected number of iterations of LOOP, according to
 429    measured or guessed profile.  No bounding is done on the
 430    value.  */
 431
 432 gcov_type
 433 expected_loop_iterations_unbounded (const struct loop *loop)
 434 {
 435   edge e;
 436   edge_iterator ei;
 437
 438   if (loop->latch->count || loop->header->count)
 439     {
 440       gcov_type count_in, count_latch, expected;
 441
 442       count_in = 0;
 443       count_latch = 0;
 444
 445       FOR_EACH_EDGE (e, ei, loop->header->preds)
 446         if (e->src == loop->latch)
 447           count_latch = e->count;
 448         else
 449           count_in += e->count;
 450
 451       if (count_in == 0)
 452         expected = count_latch * 2;
 453       else
 454         expected = (count_latch + count_in - 1) / count_in;
 455
 456       return expected;
 457     }
 458   else
 459     {
 460       int freq_in, freq_latch;
 461
 462       freq_in = 0;
 463       freq_latch = 0;
 464
 465       FOR_EACH_EDGE (e, ei, loop->header->preds)
 466         if (e->src == loop->latch)
 467           freq_latch = EDGE_FREQUENCY (e);
 468         else
 469           freq_in += EDGE_FREQUENCY (e);
 470
 471       if (freq_in == 0)
 472         return freq_latch * 2;
 473
 474       return (freq_latch + freq_in - 1) / freq_in;
 475     }
 476 }
 477
 478 /* Returns expected number of LOOP iterations.  The returned value is bounded
 479    by REG_BR_PROB_BASE.  */
 480
 481 unsigned
 482 expected_loop_iterations (const struct loop *loop)
 483 {
 484   gcov_type expected = expected_loop_iterations_unbounded (loop);
 485   return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 486 }
 487
 488 /* Returns the maximum level of nesting of subloops of LOOP.  */
 489
 490 unsigned
 491 get_loop_level (const struct loop *loop)
 492 {
 493   const struct loop *ploop;
 494   unsigned mx = 0, l;
 495
 496   for (ploop = loop->inner; ploop; ploop = ploop->next)
 497     {
 498       l = get_loop_level (ploop);
 499       if (l >= mx)
 500         mx = l + 1;
 501     }
 502   return mx;
 503 }
 504
 505 /* Returns estimate on cost of computing SEQ.  */
 506
 507 static unsigned
 508 seq_cost (rtx seq)
 509 {
 510   unsigned cost = 0;
 511   rtx set;
 512
 513   for (; seq; seq = NEXT_INSN (seq))
 514     {
 515       set = single_set (seq);
 516       if (set)
 517         cost += rtx_cost (set, SET);
 518       else
 519         cost++;
 520     }
 521
 522   return cost;
 523 }
 524
 525 /* The properties of the target.  */
 526
 527 unsigned target_avail_regs;     /* Number of available registers.  */
 528 unsigned target_res_regs;       /* Number of registers reserved for temporary
 529                                    expressions.  */
 530 unsigned target_reg_cost;       /* The cost for register when there still
 531                                    is some reserve, but we are approaching
 532                                    the number of available registers.  */
 533 unsigned target_spill_cost;     /* The cost for register when we need
 534                                    to spill.  */
 535
 536 /* Initialize the constants for computing set costs.  */
 537
 538 void
 539 init_set_costs (void)
 540 {
 541   rtx seq;
 542   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 543   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 544   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 545   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 546   unsigned i;
 547
 548   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 549     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 550         && !fixed_regs[i])
 551       target_avail_regs++;
 552
 553   target_res_regs = 3;
 554
 555   /* Set up the costs for using extra registers:
 556
 557      1) If not many free registers remain, we should prefer having an
 558         additional move to decreasing the number of available registers.
 559         (TARGET_REG_COST).
 560      2) If no registers are available, we need to spill, which may require
 561         storing the old value to memory and loading it back
 562         (TARGET_SPILL_COST).  */
 563
 564   start_sequence ();
 565   emit_move_insn (reg1, reg2);
 566   seq = get_insns ();
 567   end_sequence ();
 568   target_reg_cost = seq_cost (seq);
 569
 570   start_sequence ();
 571   emit_move_insn (mem, reg1);
 572   emit_move_insn (reg2, mem);
 573   seq = get_insns ();
 574   end_sequence ();
 575   target_spill_cost = seq_cost (seq);
 576 }
 577
 578 /* Estimates cost of increased register pressure caused by making N_NEW new
 579    registers live around the loop.  N_OLD is the number of registers live
 580    around the loop.  */
 581
 582 unsigned
 583 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old)
 584 {
 585   unsigned regs_needed = n_new + n_old;
 586
 587   /* If we have enough registers, we should use them and not restrict
 588      the transformations unnecessarily.  */
 589   if (regs_needed + target_res_regs <= target_avail_regs)
 590     return 0;
 591
 592   /* If we are close to running out of registers, try to preserve them.  */
 593   if (regs_needed <= target_avail_regs)
 594     return target_reg_cost * n_new;
 595
 596   /* If we run out of registers, it is very expensive to add another one.  */
 597   return target_spill_cost * n_new;
 598 }
 599
 600 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 601
 602 void
 603 mark_loop_exit_edges (void)
 604 {
 605   basic_block bb;
 606   edge e;
 607
 608   if (!current_loops)
 609     return;
 610
 611   FOR_EACH_BB (bb)
 612     {
 613       edge_iterator ei;
 614
 615       FOR_EACH_EDGE (e, ei, bb->succs)
 616         {
 617           if (loop_outer (bb->loop_father)
 618               && loop_exit_edge_p (bb->loop_father, e))
 619             e->flags |= EDGE_LOOP_EXIT;
 620           else
 621             e->flags &= ~EDGE_LOOP_EXIT;
 622         }
 623     }
 624 }
 625