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         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_EACH_EDGE (e, ei, act->succs)
 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   edge_iterator ei;
 420
 421   if (loop->header->count)
 422     {
 423       gcov_type count_in, count_latch, expected;
 424
 425       count_in = 0;
 426       count_latch = 0;
 427
 428       FOR_EACH_EDGE (e, ei, loop->header->preds)
 429         if (e->src == loop->latch)
 430           count_latch = e->count;
 431         else
 432           count_in += e->count;
 433
 434       if (count_in == 0)
 435         expected = count_latch * 2;
 436       else
 437         expected = (count_latch + count_in - 1) / count_in;
 438
 439       /* Avoid overflows.  */
 440       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 441     }
 442   else
 443     {
 444       int freq_in, freq_latch;
 445
 446       freq_in = 0;
 447       freq_latch = 0;
 448
 449       FOR_EACH_EDGE (e, ei, loop->header->preds)
 450         if (e->src == loop->latch)
 451           freq_latch = EDGE_FREQUENCY (e);
 452         else
 453           freq_in += EDGE_FREQUENCY (e);
 454
 455       if (freq_in == 0)
 456         return freq_latch * 2;
 457
 458       return (freq_latch + freq_in - 1) / freq_in;
 459     }
 460 }
 461
 462 /* Returns the maximum level of nesting of subloops of LOOP.  */
 463
 464 unsigned
 465 get_loop_level (const struct loop *loop)
 466 {
 467   const struct loop *ploop;
 468   unsigned mx = 0, l;
 469
 470   for (ploop = loop->inner; ploop; ploop = ploop->next)
 471     {
 472       l = get_loop_level (ploop);
 473       if (l >= mx)
 474         mx = l + 1;
 475     }
 476   return mx;
 477 }
 478
 479 /* Returns estimate on cost of computing SEQ.  */
 480
 481 static unsigned
 482 seq_cost (rtx seq)
 483 {
 484   unsigned cost = 0;
 485   rtx set;
 486
 487   for (; seq; seq = NEXT_INSN (seq))
 488     {
 489       set = single_set (seq);
 490       if (set)
 491         cost += rtx_cost (set, SET);
 492       else
 493         cost++;
 494     }
 495
 496   return cost;
 497 }
 498
 499 /* The properties of the target.  */
 500
 501 unsigned target_avail_regs;     /* Number of available registers.  */
 502 unsigned target_res_regs;       /* Number of reserved registers.  */
 503 unsigned target_small_cost;     /* The cost for register when there is a free one.  */
 504 unsigned target_pres_cost;      /* The cost for register when there are not too many
 505                                    free ones.  */
 506 unsigned target_spill_cost;     /* The cost for register when we need to spill.  */
 507
 508 /* Initialize the constants for computing set costs.  */
 509
 510 void
 511 init_set_costs (void)
 512 {
 513   rtx seq;
 514   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 515   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 516   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 517   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 518   unsigned i;
 519
 520   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 521     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 522         && !fixed_regs[i])
 523       target_avail_regs++;
 524
 525   target_res_regs = 3;
 526
 527   /* These are really just heuristic values.  */
 528
 529   start_sequence ();
 530   emit_move_insn (reg1, reg2);
 531   seq = get_insns ();
 532   end_sequence ();
 533   target_small_cost = seq_cost (seq);
 534   target_pres_cost = 2 * target_small_cost;
 535
 536   start_sequence ();
 537   emit_move_insn (mem, reg1);
 538   emit_move_insn (reg2, mem);
 539   seq = get_insns ();
 540   end_sequence ();
 541   target_spill_cost = seq_cost (seq);
 542 }
 543
 544 /* Calculates cost for having SIZE new loop global variables.  REGS_USED is the
 545    number of global registers used in loop.  N_USES is the number of relevant
 546    variable uses.  */
 547
 548 unsigned
 549 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
 550 {
 551   unsigned regs_needed = regs_used + size;
 552   unsigned cost = 0;
 553
 554   if (regs_needed + target_res_regs <= target_avail_regs)
 555     cost += target_small_cost * size;
 556   else if (regs_needed <= target_avail_regs)
 557     cost += target_pres_cost * size;
 558   else
 559     {
 560       cost += target_pres_cost * size;
 561       cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
 562     }
 563
 564   return cost;
 565 }
 566