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