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   gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
 212
 213   if (g->vertices[e->src].component != g->vertices[e->dest].component)
 214     return;
 215
 216   real->flags |= EDGE_IRREDUCIBLE_LOOP;
 217   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
 218     real->src->flags |= BB_IRREDUCIBLE_LOOP;
 219 }
 220
 221 /* Runs CALLBACK for all edges in G.  */
 222
 223 static void
 224 for_each_edge (struct graph *g,
 225                void (callback) (struct graph *, struct edge *))
 226 {
 227   struct edge *e;
 228   int i;
 229
 230   for (i = 0; i < g->n_vertices; i++)
 231     for (e = g->vertices[i].succ; e; e = e->succ_next)
 232       callback (g, e);
 233 }
 234
 235 /* Releases the memory occupied by G.  */
 236
 237 static void
 238 free_graph (struct graph *g)
 239 {
 240   struct edge *e, *n;
 241   int i;
 242
 243   for (i = 0; i < g->n_vertices; i++)
 244     for (e = g->vertices[i].succ; e; e = n)
 245       {
 246         n = e->succ_next;
 247         free (e);
 248       }
 249   free (g->vertices);
 250   free (g);
 251 }
 252
 253 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
 254    throw away all latch edges and mark blocks inside any remaining cycle.
 255    Everything is a bit complicated due to fact we do not want to do this
 256    for parts of cycles that only "pass" through some loop -- i.e. for
 257    each cycle, we want to mark blocks that belong directly to innermost
 258    loop containing the whole cycle.
 259
 260    LOOPS is the loop tree.  */
 261
 262 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
 263 #define BB_REPR(BB) ((BB)->index + 1)
 264
 265 void
 266 mark_irreducible_loops (struct loops *loops)
 267 {
 268   basic_block act;
 269   edge e;
 270   edge_iterator ei;
 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_EACH_EDGE (e, ei, act->succs)
 283         {
 284           e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 285         }
 286     }
 287
 288   /* Create the edge lists.  */
 289   g = new_graph (last_basic_block + loops->num);
 290
 291   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 292     FOR_EACH_EDGE (e, ei, act->succs)
 293       {
 294         /* Ignore edges to exit.  */
 295         if (e->dest == EXIT_BLOCK_PTR)
 296           continue;
 297
 298         /* And latch edges.  */
 299         if (e->dest->loop_father->header == e->dest
 300             && e->dest->loop_father->latch == act)
 301           continue;
 302
 303         /* Edges inside a single loop should be left where they are.  Edges
 304            to subloop headers should lead to representative of the subloop,
 305            but from the same place.
 306
 307            Edges exiting loops should lead from representative
 308            of the son of nearest common ancestor of the loops in that
 309            act lays.  */
 310
 311         src = BB_REPR (act);
 312         dest = BB_REPR (e->dest);
 313
 314         if (e->dest->loop_father->header == e->dest)
 315           dest = LOOP_REPR (e->dest->loop_father);
 316
 317         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 318           {
 319             depth = find_common_loop (act->loop_father,
 320                                       e->dest->loop_father)->depth + 1;
 321             if (depth == act->loop_father->depth)
 322               cloop = act->loop_father;
 323             else
 324               cloop = act->loop_father->pred[depth];
 325
 326             src = LOOP_REPR (cloop);
 327           }
 328
 329         add_edge (g, src, dest, e);
 330       }
 331
 332   /* Find the strongly connected components.  Use the algorithm of Tarjan --
 333      first determine the postorder dfs numbering in reversed graph, then
 334      run the dfs on the original graph in the order given by decreasing
 335      numbers assigned by the previous pass.  */
 336   nq = 0;
 337   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 338     {
 339       queue1[nq++] = BB_REPR (act);
 340     }
 341   for (i = 1; i < (int) loops->num; i++)
 342     if (loops->parray[i])
 343       queue1[nq++] = LOOP_REPR (loops->parray[i]);
 344   dfs (g, queue1, nq, queue2, false);
 345   for (i = 0; i < nq; i++)
 346     queue1[i] = queue2[nq - i - 1];
 347   dfs (g, queue1, nq, NULL, true);
 348
 349   /* Mark the irreducible loops.  */
 350   for_each_edge (g, check_irred);
 351
 352   free_graph (g);
 353   free (queue1);
 354   free (queue2);
 355
 356   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 357 }
 358
 359 /* Counts number of insns inside LOOP.  */
 360 int
 361 num_loop_insns (struct loop *loop)
 362 {
 363   basic_block *bbs, bb;
 364   unsigned i, ninsns = 0;
 365   rtx insn;
 366
 367   bbs = get_loop_body (loop);
 368   for (i = 0; i < loop->num_nodes; i++)
 369     {
 370       bb = bbs[i];
 371       ninsns++;
 372       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 373         if (INSN_P (insn))
 374           ninsns++;
 375     }
 376   free(bbs);
 377
 378   return ninsns;
 379 }
 380
 381 /* Counts number of insns executed on average per iteration LOOP.  */
 382 int
 383 average_num_loop_insns (struct loop *loop)
 384 {
 385   basic_block *bbs, bb;
 386   unsigned i, binsns, ninsns, ratio;
 387   rtx insn;
 388
 389   ninsns = 0;
 390   bbs = get_loop_body (loop);
 391   for (i = 0; i < loop->num_nodes; i++)
 392     {
 393       bb = bbs[i];
 394
 395       binsns = 1;
 396       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 397         if (INSN_P (insn))
 398           binsns++;
 399
 400       ratio = loop->header->frequency == 0
 401               ? BB_FREQ_MAX
 402               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 403       ninsns += binsns * ratio;
 404     }
 405   free(bbs);
 406
 407   ninsns /= BB_FREQ_MAX;
 408   if (!ninsns)
 409     ninsns = 1; /* To avoid division by zero.  */
 410
 411   return ninsns;
 412 }
 413
 414 /* Returns expected number of LOOP iterations.
 415    Compute upper bound on number of iterations in case they do not fit integer
 416    to help loop peeling heuristics.  Use exact counts if at all possible.  */
 417 unsigned
 418 expected_loop_iterations (const struct loop *loop)
 419 {
 420   edge e;
 421   edge_iterator ei;
 422
 423   if (loop->header->count)
 424     {
 425       gcov_type count_in, count_latch, expected;
 426
 427       count_in = 0;
 428       count_latch = 0;
 429
 430       FOR_EACH_EDGE (e, ei, loop->header->preds)
 431         {
 432           if (e->src == loop->latch)
 433             count_latch = e->count;
 434           else
 435             count_in += e->count;
 436         }
 437
 438       if (count_in == 0)
 439         expected = count_latch * 2;
 440       else
 441         expected = (count_latch + count_in - 1) / count_in;
 442
 443       /* Avoid overflows.  */
 444       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 445     }
 446   else
 447     {
 448       int freq_in, freq_latch;
 449
 450       freq_in = 0;
 451       freq_latch = 0;
 452
 453       FOR_EACH_EDGE (e, ei, loop->header->preds)
 454         {
 455           if (e->src == loop->latch)
 456             freq_latch = EDGE_FREQUENCY (e);
 457           else
 458             freq_in += EDGE_FREQUENCY (e);
 459         }
 460
 461       if (freq_in == 0)
 462         return freq_latch * 2;
 463
 464       return (freq_latch + freq_in - 1) / freq_in;
 465     }
 466 }
 467
 468 /* Returns the maximum level of nesting of subloops of LOOP.  */
 469
 470 unsigned
 471 get_loop_level (const struct loop *loop)
 472 {
 473   const struct loop *ploop;
 474   unsigned mx = 0, l;
 475
 476   for (ploop = loop->inner; ploop; ploop = ploop->next)
 477     {
 478       l = get_loop_level (ploop);
 479       if (l >= mx)
 480         mx = l + 1;
 481     }
 482   return mx;
 483 }
 484
 485 /* Returns estimate on cost of computing SEQ.  */
 486
 487 static unsigned
 488 seq_cost (rtx seq)
 489 {
 490   unsigned cost = 0;
 491   rtx set;
 492
 493   for (; seq; seq = NEXT_INSN (seq))
 494     {
 495       set = single_set (seq);
 496       if (set)
 497         cost += rtx_cost (set, SET);
 498       else
 499         cost++;
 500     }
 501
 502   return cost;
 503 }
 504
 505 /* The properties of the target.  */
 506
 507 unsigned target_avail_regs;     /* Number of available registers.  */
 508 unsigned target_res_regs;       /* Number of reserved registers.  */
 509 unsigned target_small_cost;     /* The cost for register when there is a free one.  */
 510 unsigned target_pres_cost;      /* The cost for register when there are not too many
 511                                    free ones.  */
 512 unsigned target_spill_cost;     /* The cost for register when we need to spill.  */
 513
 514 /* Initialize the constants for computing set costs.  */
 515
 516 void
 517 init_set_costs (void)
 518 {
 519   rtx seq;
 520   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 521   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 522   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 523   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 524   unsigned i;
 525
 526   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 527     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 528         && !fixed_regs[i])
 529       target_avail_regs++;
 530
 531   target_res_regs = 3;
 532
 533   /* These are really just heuristic values.  */
 534
 535   start_sequence ();
 536   emit_move_insn (reg1, reg2);
 537   seq = get_insns ();
 538   end_sequence ();
 539   target_small_cost = seq_cost (seq);
 540   target_pres_cost = 2 * target_small_cost;
 541
 542   start_sequence ();
 543   emit_move_insn (mem, reg1);
 544   emit_move_insn (reg2, mem);
 545   seq = get_insns ();
 546   end_sequence ();
 547   target_spill_cost = seq_cost (seq);
 548 }
 549
 550 /* Calculates cost for having SIZE new loop global variables.  REGS_USED is the
 551    number of global registers used in loop.  N_USES is the number of relevant
 552    variable uses.  */
 553
 554 unsigned
 555 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
 556 {
 557   unsigned regs_needed = regs_used + size;
 558   unsigned cost = 0;
 559
 560   if (regs_needed + target_res_regs <= target_avail_regs)
 561     cost += target_small_cost * size;
 562   else if (regs_needed <= target_avail_regs)
 563     cost += target_pres_cost * size;
 564   else
 565     {
 566       cost += target_pres_cost * size;
 567       cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
 568     }
 569
 570   return cost;
 571 }
 572