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