gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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 "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "expr.h"
  30 #include "output.h"
  31
  32 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  33
  34 bool
  35 just_once_each_iteration_p (struct loop *loop, basic_block bb)
  36 {
  37   /* It must be executed at least once each iteration.  */
  38   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
  39     return false;
  40
  41   /* And just once.  */
  42   if (bb->loop_father != loop)
  43     return false;
  44
  45   /* But this was not enough.  We might have some irreducible loop here.  */
  46   if (bb->flags & BB_IRREDUCIBLE_LOOP)
  47     return false;
  48
  49   return true;
  50 }
  51
  52 /* Structure representing edge of a graph.  */
  53
  54 struct edge
  55 {
  56   int src, dest;        /* Source and destination.  */
  57   struct edge *pred_next, *succ_next;
  58                         /* Next edge in predecessor and successor lists.  */
  59   void *data;           /* Data attached to the edge.  */
  60 };
  61
  62 /* Structure representing vertex of a graph.  */
  63
  64 struct vertex
  65 {
  66   struct edge *pred, *succ;
  67                         /* Lists of predecessors and successors.  */
  68   int component;        /* Number of dfs restarts before reaching the
  69                            vertex.  */
  70   int post;             /* Postorder number.  */
  71 };
  72
  73 /* Structure representing a graph.  */
  74
  75 struct graph
  76 {
  77   int n_vertices;       /* Number of vertices.  */
  78   struct vertex *vertices;
  79                         /* The vertices.  */
  80 };
  81
  82 /* Dumps graph G into F.  */
  83
  84 extern void dump_graph (FILE *, struct graph *);
  85 void dump_graph (FILE *f, struct graph *g)
  86 {
  87   int i;
  88   struct edge *e;
  89
  90   for (i = 0; i < g->n_vertices; i++)
  91     {
  92       if (!g->vertices[i].pred
  93           && !g->vertices[i].succ)
  94         continue;
  95
  96       fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
  97       for (e = g->vertices[i].pred; e; e = e->pred_next)
  98         fprintf (f, " %d", e->src);
  99       fprintf (f, "\n");
 100
 101       fprintf (f, "\t->");
 102       for (e = g->vertices[i].succ; e; e = e->succ_next)
 103         fprintf (f, " %d", e->dest);
 104       fprintf (f, "\n");
 105     }
 106 }
 107
 108 /* Creates a new graph with N_VERTICES vertices.  */
 109
 110 static struct graph *
 111 new_graph (int n_vertices)
 112 {
 113   struct graph *g = xmalloc (sizeof (struct graph));
 114
 115   g->n_vertices = n_vertices;
 116   g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
 117
 118   return g;
 119 }
 120
 121 /* Adds an edge from F to T to graph G, with DATA attached.  */
 122
 123 static void
 124 add_edge (struct graph *g, int f, int t, void *data)
 125 {
 126   struct edge *e = xmalloc (sizeof (struct edge));
 127
 128   e->src = f;
 129   e->dest = t;
 130   e->data = data;
 131
 132   e->pred_next = g->vertices[t].pred;
 133   g->vertices[t].pred = e;
 134
 135   e->succ_next = g->vertices[f].succ;
 136   g->vertices[f].succ = e;
 137 }
 138
 139 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
 140    The vertices in postorder are stored into QT.  If FORWARD is false,
 141    backward dfs is run.  */
 142
 143 static void
 144 dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
 145 {
 146   int i, tick = 0, v, comp = 0, top;
 147   struct edge *e;
 148   struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
 149
 150   for (i = 0; i < g->n_vertices; i++)
 151     {
 152       g->vertices[i].component = -1;
 153       g->vertices[i].post = -1;
 154     }
 155
 156 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
 157 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
 158 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
 159 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
 160
 161   for (i = 0; i < nq; i++)
 162     {
 163       v = qs[i];
 164       if (g->vertices[v].post != -1)
 165         continue;
 166
 167       g->vertices[v].component = comp++;
 168       e = FST_EDGE (v);
 169       top = 0;
 170
 171       while (1)
 172         {
 173           while (e && g->vertices[EDGE_DEST (e)].component != -1)
 174             e = NEXT_EDGE (e);
 175
 176           if (!e)
 177             {
 178               if (qt)
 179                 qt[tick] = v;
 180               g->vertices[v].post = tick++;
 181
 182               if (!top)
 183                 break;
 184
 185               e = stack[--top];
 186               v = EDGE_SRC (e);
 187               e = NEXT_EDGE (e);
 188               continue;
 189             }
 190
 191           stack[top++] = e;
 192           v = EDGE_DEST (e);
 193           e = FST_EDGE (v);
 194           g->vertices[v].component = comp - 1;
 195         }
 196     }
 197
 198   free (stack);
 199 }
 200
 201 /* Marks the edge E in graph G irreducible if it connects two vertices in the
 202    same scc.  */
 203
 204 static void
 205 check_irred (struct graph *g, struct edge *e)
 206 {
 207   edge real = e->data;
 208
 209   /* All edges should lead from a component with higher number to the
 210      one with lower one.  */
 211   if (g->vertices[e->src].component < g->vertices[e->dest].component)
 212     abort ();
 213
 214   if (g->vertices[e->src].component != g->vertices[e->dest].component)
 215     return;
 216
 217   real->flags |= EDGE_IRREDUCIBLE_LOOP;
 218   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
 219     real->src->flags |= BB_IRREDUCIBLE_LOOP;
 220 }
 221
 222 /* Runs CALLBACK for all edges in G.  */
 223
 224 static void
 225 for_each_edge (struct graph *g,
 226                void (callback) (struct graph *, struct edge *))
 227 {
 228   struct edge *e;
 229   int i;
 230
 231   for (i = 0; i < g->n_vertices; i++)
 232     for (e = g->vertices[i].succ; e; e = e->succ_next)
 233       callback (g, e);
 234 }
 235
 236 /* Releases the memory occupied by G.  */
 237
 238 static void
 239 free_graph (struct graph *g)
 240 {
 241   struct edge *e, *n;
 242   int i;
 243
 244   for (i = 0; i < g->n_vertices; i++)
 245     for (e = g->vertices[i].succ; e; e = n)
 246       {
 247         n = e->succ_next;
 248         free (e);
 249       }
 250   free (g->vertices);
 251   free (g);
 252 }
 253
 254 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
 255    throw away all latch edges and mark blocks inside any remaining cycle.
 256    Everything is a bit complicated due to fact we do not want to do this
 257    for parts of cycles that only "pass" through some loop -- i.e. for
 258    each cycle, we want to mark blocks that belong directly to innermost
 259    loop containing the whole cycle.
 260
 261    LOOPS is the loop tree.  */
 262
 263 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
 264 #define BB_REPR(BB) ((BB)->index + 1)
 265
 266 void
 267 mark_irreducible_loops (struct loops *loops)
 268 {
 269   basic_block act;
 270   edge e;
 271   int i, src, dest;
 272   struct graph *g;
 273   int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 274   int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 275   int nq, depth;
 276   struct loop *cloop;
 277
 278   /* Reset the flags.  */
 279   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 280     {
 281       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 282       for (e = act->succ; e; e = e->succ_next)
 283         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 284     }
 285
 286   /* Create the edge lists.  */
 287   g = new_graph (last_basic_block + loops->num);
 288
 289   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 290     for (e = act->succ; e; e = e->succ_next)
 291       {
 292         /* Ignore edges to exit.  */
 293         if (e->dest == EXIT_BLOCK_PTR)
 294           continue;
 295
 296         /* And latch edges.  */
 297         if (e->dest->loop_father->header == e->dest
 298             && e->dest->loop_father->latch == act)
 299           continue;
 300
 301         /* Edges inside a single loop should be left where they are.  Edges
 302            to subloop headers should lead to representative of the subloop,
 303            but from the same place.
 304
 305            Edges exiting loops should lead from representative
 306            of the son of nearest common ancestor of the loops in that
 307            act lays.  */
 308
 309         src = BB_REPR (act);
 310         dest = BB_REPR (e->dest);
 311
 312         if (e->dest->loop_father->header == e->dest)
 313           dest = LOOP_REPR (e->dest->loop_father);
 314
 315         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 316           {
 317             depth = find_common_loop (act->loop_father,
 318                                       e->dest->loop_father)->depth + 1;
 319             if (depth == act->loop_father->depth)
 320               cloop = act->loop_father;
 321             else
 322               cloop = act->loop_father->pred[depth];
 323
 324             src = LOOP_REPR (cloop);
 325           }
 326
 327         add_edge (g, src, dest, e);
 328       }
 329
 330   /* Find the strongly connected components.  Use the algorithm of Tarjan --
 331      first determine the postorder dfs numbering in reversed graph, then
 332      run the dfs on the original graph in the order given by decreasing
 333      numbers assigned by the previous pass.  */
 334   nq = 0;
 335   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 336     {
 337       queue1[nq++] = BB_REPR (act);
 338     }
 339   for (i = 1; i < (int) loops->num; i++)
 340     if (loops->parray[i])
 341       queue1[nq++] = LOOP_REPR (loops->parray[i]);
 342   dfs (g, queue1, nq, queue2, false);
 343   for (i = 0; i < nq; i++)
 344     queue1[i] = queue2[nq - i - 1];
 345   dfs (g, queue1, nq, NULL, true);
 346
 347   /* Mark the irreducible loops.  */
 348   for_each_edge (g, check_irred);
 349
 350   free_graph (g);
 351   free (queue1);
 352   free (queue2);
 353
 354   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 355 }
 356
 357 /* Counts number of insns inside LOOP.  */
 358 int
 359 num_loop_insns (struct loop *loop)
 360 {
 361   basic_block *bbs, bb;
 362   unsigned i, ninsns = 0;
 363   rtx insn;
 364
 365   bbs = get_loop_body (loop);
 366   for (i = 0; i < loop->num_nodes; i++)
 367     {
 368       bb = bbs[i];
 369       ninsns++;
 370       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 371         if (INSN_P (insn))
 372           ninsns++;
 373     }
 374   free(bbs);
 375
 376   return ninsns;
 377 }
 378
 379 /* Counts number of insns executed on average per iteration LOOP.  */
 380 int
 381 average_num_loop_insns (struct loop *loop)
 382 {
 383   basic_block *bbs, bb;
 384   unsigned i, binsns, ninsns, ratio;
 385   rtx insn;
 386
 387   ninsns = 0;
 388   bbs = get_loop_body (loop);
 389   for (i = 0; i < loop->num_nodes; i++)
 390     {
 391       bb = bbs[i];
 392
 393       binsns = 1;
 394       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 395         if (INSN_P (insn))
 396           binsns++;
 397
 398       ratio = loop->header->frequency == 0
 399               ? BB_FREQ_MAX
 400               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 401       ninsns += binsns * ratio;
 402     }
 403   free(bbs);
 404
 405   ninsns /= BB_FREQ_MAX;
 406   if (!ninsns)
 407     ninsns = 1; /* To avoid division by zero.  */
 408
 409   return ninsns;
 410 }
 411
 412 /* Returns expected number of LOOP iterations.
 413    Compute upper bound on number of iterations in case they do not fit integer
 414    to help loop peeling heuristics.  Use exact counts if at all possible.  */
 415 unsigned
 416 expected_loop_iterations (const struct loop *loop)
 417 {
 418   edge e;
 419
 420   if (loop->header->count)
 421     {
 422       gcov_type count_in, count_latch, expected;
 423
 424       count_in = 0;
 425       count_latch = 0;
 426
 427       for (e = loop->header->pred; e; e = e->pred_next)
 428         if (e->src == loop->latch)
 429           count_latch = e->count;
 430         else
 431           count_in += e->count;
 432
 433       if (count_in == 0)
 434         expected = count_latch * 2;
 435       else
 436         expected = (count_latch + count_in - 1) / count_in;
 437
 438       /* Avoid overflows.  */
 439       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 440     }
 441   else
 442     {
 443       int freq_in, freq_latch;
 444
 445       freq_in = 0;
 446       freq_latch = 0;
 447
 448       for (e = loop->header->pred; e; e = e->pred_next)
 449         if (e->src == loop->latch)
 450           freq_latch = EDGE_FREQUENCY (e);
 451         else
 452           freq_in += EDGE_FREQUENCY (e);
 453
 454       if (freq_in == 0)
 455         return freq_latch * 2;
 456
 457       return (freq_latch + freq_in - 1) / freq_in;
 458     }
 459 }
 460
 461 /* Returns the maximum level of nesting of subloops of LOOP.  */
 462
 463 unsigned
 464 get_loop_level (const struct loop *loop)
 465 {
 466   const struct loop *ploop;
 467   unsigned mx = 0, l;
 468
 469   for (ploop = loop->inner; ploop; ploop = ploop->next)
 470     {
 471       l = get_loop_level (ploop);
 472       if (l >= mx)
 473         mx = l + 1;
 474     }
 475   return mx;
 476 }
 477
 478 /* Returns estimate on cost of computing SEQ.  */
 479
 480 static unsigned
 481 seq_cost (rtx seq)
 482 {
 483   unsigned cost = 0;
 484   rtx set;
 485
 486   for (; seq; seq = NEXT_INSN (seq))
 487     {
 488       set = single_set (seq);
 489       if (set)
 490         cost += rtx_cost (set, SET);
 491       else
 492         cost++;
 493     }
 494
 495   return cost;
 496 }
 497
 498 /* The properties of the target.  */
 499
 500 static unsigned avail_regs;     /* Number of available registers.  */
 501 static unsigned res_regs;       /* Number of reserved registers.  */
 502 static unsigned small_cost;     /* The cost for register when there is a free one.  */
 503 static unsigned pres_cost;      /* The cost for register when there are not too many
 504                                    free ones.  */
 505 static unsigned spill_cost;     /* The cost for register when we need to spill.  */
 506
 507 /* Initialize the constants for computing set costs.  */
 508
 509 void
 510 init_set_costs (void)
 511 {
 512   rtx seq;
 513   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 514   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 515   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 516   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 517   unsigned i;
 518
 519   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 520     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 521         && !fixed_regs[i])
 522       avail_regs++;
 523
 524   res_regs = 3;
 525
 526   /* These are really just heuristic values.  */
 527
 528   start_sequence ();
 529   emit_move_insn (reg1, reg2);
 530   seq = get_insns ();
 531   end_sequence ();
 532   small_cost = seq_cost (seq);
 533   pres_cost = 2 * small_cost;
 534
 535   start_sequence ();
 536   emit_move_insn (mem, reg1);
 537   emit_move_insn (reg2, mem);
 538   seq = get_insns ();
 539   end_sequence ();
 540   spill_cost = seq_cost (seq);
 541 }
 542
 543 /* Calculates cost for having SIZE new loop global variables.  REGS_USED is the
 544    number of global registers used in loop.  N_USES is the number of relevant
 545    variable uses.  */
 546
 547 unsigned
 548 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
 549 {
 550   unsigned regs_needed = regs_used + size;
 551   unsigned cost = 0;
 552
 553   if (regs_needed + res_regs <= avail_regs)
 554     cost += small_cost * size;
 555   else if (regs_needed <= avail_regs)
 556     cost += pres_cost * size;
 557   else
 558     {
 559       cost += pres_cost * size;
 560       cost += spill_cost * n_uses * (regs_needed - avail_regs) / regs_needed;
 561     }
 562
 563   return cost;
 564 }
 565