gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004, 2005 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 "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 void dump_graph (FILE *f, struct graph *g)
  87 {
  88   int i;
  89   struct edge *e;
  90
  91   for (i = 0; i < g->n_vertices; i++)
  92     {
  93       if (!g->vertices[i].pred
  94           && !g->vertices[i].succ)
  95         continue;
  96
  97       fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
  98       for (e = g->vertices[i].pred; e; e = e->pred_next)
  99         fprintf (f, " %d", e->src);
 100       fprintf (f, "\n");
 101
 102       fprintf (f, "\t->");
 103       for (e = g->vertices[i].succ; e; e = e->succ_next)
 104         fprintf (f, " %d", e->dest);
 105       fprintf (f, "\n");
 106     }
 107 }
 108
 109 /* Creates a new graph with N_VERTICES vertices.  */
 110
 111 static struct graph *
 112 new_graph (int n_vertices)
 113 {
 114   struct graph *g = xmalloc (sizeof (struct graph));
 115
 116   g->n_vertices = n_vertices;
 117   g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
 118
 119   return g;
 120 }
 121
 122 /* Adds an edge from F to T to graph G, with DATA attached.  */
 123
 124 static void
 125 add_edge (struct graph *g, int f, int t, void *data)
 126 {
 127   struct edge *e = xmalloc (sizeof (struct edge));
 128
 129   e->src = f;
 130   e->dest = t;
 131   e->data = data;
 132
 133   e->pred_next = g->vertices[t].pred;
 134   g->vertices[t].pred = e;
 135
 136   e->succ_next = g->vertices[f].succ;
 137   g->vertices[f].succ = e;
 138 }
 139
 140 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
 141    The vertices in postorder are stored into QT.  If FORWARD is false,
 142    backward dfs is run.  */
 143
 144 static void
 145 dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
 146 {
 147   int i, tick = 0, v, comp = 0, top;
 148   struct edge *e;
 149   struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
 150
 151   for (i = 0; i < g->n_vertices; i++)
 152     {
 153       g->vertices[i].component = -1;
 154       g->vertices[i].post = -1;
 155     }
 156
 157 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
 158 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
 159 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
 160 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
 161
 162   for (i = 0; i < nq; i++)
 163     {
 164       v = qs[i];
 165       if (g->vertices[v].post != -1)
 166         continue;
 167
 168       g->vertices[v].component = comp++;
 169       e = FST_EDGE (v);
 170       top = 0;
 171
 172       while (1)
 173         {
 174           while (e && g->vertices[EDGE_DEST (e)].component != -1)
 175             e = NEXT_EDGE (e);
 176
 177           if (!e)
 178             {
 179               if (qt)
 180                 qt[tick] = v;
 181               g->vertices[v].post = tick++;
 182
 183               if (!top)
 184                 break;
 185
 186               e = stack[--top];
 187               v = EDGE_SRC (e);
 188               e = NEXT_EDGE (e);
 189               continue;
 190             }
 191
 192           stack[top++] = e;
 193           v = EDGE_DEST (e);
 194           e = FST_EDGE (v);
 195           g->vertices[v].component = comp - 1;
 196         }
 197     }
 198
 199   free (stack);
 200 }
 201
 202 /* Marks the edge E in graph G irreducible if it connects two vertices in the
 203    same scc.  */
 204
 205 static void
 206 check_irred (struct graph *g, struct edge *e)
 207 {
 208   edge real = e->data;
 209
 210   /* All edges should lead from a component with higher number to the
 211      one with lower one.  */
 212   gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
 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   edge_iterator ei;
 272   int i, src, dest;
 273   struct graph *g;
 274   int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 275   int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 276   int nq, depth;
 277   struct loop *cloop;
 278
 279   /* Reset the flags.  */
 280   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 281     {
 282       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 283       FOR_EACH_EDGE (e, ei, act->succs)
 284         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 285     }
 286
 287   /* Create the edge lists.  */
 288   g = new_graph (last_basic_block + loops->num);
 289
 290   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 291     FOR_EACH_EDGE (e, ei, act->succs)
 292       {
 293         /* Ignore edges to exit.  */
 294         if (e->dest == EXIT_BLOCK_PTR)
 295           continue;
 296
 297         /* And latch edges.  */
 298         if (e->dest->loop_father->header == e->dest
 299             && e->dest->loop_father->latch == act)
 300           continue;
 301
 302         /* Edges inside a single loop should be left where they are.  Edges
 303            to subloop headers should lead to representative of the subloop,
 304            but from the same place.
 305
 306            Edges exiting loops should lead from representative
 307            of the son of nearest common ancestor of the loops in that
 308            act lays.  */
 309
 310         src = BB_REPR (act);
 311         dest = BB_REPR (e->dest);
 312
 313         if (e->dest->loop_father->header == e->dest)
 314           dest = LOOP_REPR (e->dest->loop_father);
 315
 316         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 317           {
 318             depth = find_common_loop (act->loop_father,
 319                                       e->dest->loop_father)->depth + 1;
 320             if (depth == act->loop_father->depth)
 321               cloop = act->loop_father;
 322             else
 323               cloop = act->loop_father->pred[depth];
 324
 325             src = LOOP_REPR (cloop);
 326           }
 327
 328         add_edge (g, src, dest, e);
 329       }
 330
 331   /* Find the strongly connected components.  Use the algorithm of Tarjan --
 332      first determine the postorder dfs numbering in reversed graph, then
 333      run the dfs on the original graph in the order given by decreasing
 334      numbers assigned by the previous pass.  */
 335   nq = 0;
 336   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 337     {
 338       queue1[nq++] = BB_REPR (act);
 339     }
 340   for (i = 1; i < (int) loops->num; i++)
 341     if (loops->parray[i])
 342       queue1[nq++] = LOOP_REPR (loops->parray[i]);
 343   dfs (g, queue1, nq, queue2, false);
 344   for (i = 0; i < nq; i++)
 345     queue1[i] = queue2[nq - i - 1];
 346   dfs (g, queue1, nq, NULL, true);
 347
 348   /* Mark the irreducible loops.  */
 349   for_each_edge (g, check_irred);
 350
 351   free_graph (g);
 352   free (queue1);
 353   free (queue2);
 354
 355   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
 356 }
 357
 358 /* Counts number of insns inside LOOP.  */
 359 int
 360 num_loop_insns (struct loop *loop)
 361 {
 362   basic_block *bbs, bb;
 363   unsigned i, ninsns = 0;
 364   rtx insn;
 365
 366   bbs = get_loop_body (loop);
 367   for (i = 0; i < loop->num_nodes; i++)
 368     {
 369       bb = bbs[i];
 370       ninsns++;
 371       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 372         if (INSN_P (insn))
 373           ninsns++;
 374     }
 375   free(bbs);
 376
 377   return ninsns;
 378 }
 379
 380 /* Counts number of insns executed on average per iteration LOOP.  */
 381 int
 382 average_num_loop_insns (struct loop *loop)
 383 {
 384   basic_block *bbs, bb;
 385   unsigned i, binsns, ninsns, ratio;
 386   rtx insn;
 387
 388   ninsns = 0;
 389   bbs = get_loop_body (loop);
 390   for (i = 0; i < loop->num_nodes; i++)
 391     {
 392       bb = bbs[i];
 393
 394       binsns = 1;
 395       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 396         if (INSN_P (insn))
 397           binsns++;
 398
 399       ratio = loop->header->frequency == 0
 400               ? BB_FREQ_MAX
 401               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 402       ninsns += binsns * ratio;
 403     }
 404   free(bbs);
 405
 406   ninsns /= BB_FREQ_MAX;
 407   if (!ninsns)
 408     ninsns = 1; /* To avoid division by zero.  */
 409
 410   return ninsns;
 411 }
 412
 413 /* Returns expected number of LOOP iterations.
 414    Compute upper bound on number of iterations in case they do not fit integer
 415    to help loop peeling heuristics.  Use exact counts if at all possible.  */
 416 unsigned
 417 expected_loop_iterations (const struct loop *loop)
 418 {
 419   edge e;
 420   edge_iterator ei;
 421
 422   if (loop->latch->count || loop->header->count)
 423     {
 424       gcov_type count_in, count_latch, expected;
 425
 426       count_in = 0;
 427       count_latch = 0;
 428
 429       FOR_EACH_EDGE (e, ei, loop->header->preds)
 430         if (e->src == loop->latch)
 431           count_latch = e->count;
 432         else
 433           count_in += e->count;
 434
 435       if (count_in == 0)
 436         expected = count_latch * 2;
 437       else
 438         expected = (count_latch + count_in - 1) / count_in;
 439
 440       /* Avoid overflows.  */
 441       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 442     }
 443   else
 444     {
 445       int freq_in, freq_latch;
 446
 447       freq_in = 0;
 448       freq_latch = 0;
 449
 450       FOR_EACH_EDGE (e, ei, loop->header->preds)
 451         if (e->src == loop->latch)
 452           freq_latch = EDGE_FREQUENCY (e);
 453         else
 454           freq_in += EDGE_FREQUENCY (e);
 455
 456       if (freq_in == 0)
 457         return freq_latch * 2;
 458
 459       return (freq_latch + freq_in - 1) / freq_in;
 460     }
 461 }
 462
 463 /* Returns the maximum level of nesting of subloops of LOOP.  */
 464
 465 unsigned
 466 get_loop_level (const struct loop *loop)
 467 {
 468   const struct loop *ploop;
 469   unsigned mx = 0, l;
 470
 471   for (ploop = loop->inner; ploop; ploop = ploop->next)
 472     {
 473       l = get_loop_level (ploop);
 474       if (l >= mx)
 475         mx = l + 1;
 476     }
 477   return mx;
 478 }
 479
 480 /* Returns estimate on cost of computing SEQ.  */
 481
 482 static unsigned
 483 seq_cost (rtx seq)
 484 {
 485   unsigned cost = 0;
 486   rtx set;
 487
 488   for (; seq; seq = NEXT_INSN (seq))
 489     {
 490       set = single_set (seq);
 491       if (set)
 492         cost += rtx_cost (set, SET);
 493       else
 494         cost++;
 495     }
 496
 497   return cost;
 498 }
 499
 500 /* The properties of the target.  */
 501
 502 unsigned target_avail_regs;     /* Number of available registers.  */
 503 unsigned target_res_regs;       /* Number of reserved registers.  */
 504 unsigned target_small_cost;     /* The cost for register when there is a free one.  */
 505 unsigned target_pres_cost;      /* The cost for register when there are not too many
 506                                    free ones.  */
 507 unsigned target_spill_cost;     /* The cost for register when we need to spill.  */
 508
 509 /* Initialize the constants for computing set costs.  */
 510
 511 void
 512 init_set_costs (void)
 513 {
 514   rtx seq;
 515   rtx reg1 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER);
 516   rtx reg2 = gen_raw_REG (SImode, FIRST_PSEUDO_REGISTER + 1);
 517   rtx addr = gen_raw_REG (Pmode, FIRST_PSEUDO_REGISTER + 2);
 518   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 519   unsigned i;
 520
 521   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 522     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 523         && !fixed_regs[i])
 524       target_avail_regs++;
 525
 526   target_res_regs = 3;
 527
 528   /* These are really just heuristic values.  */
 529
 530   start_sequence ();
 531   emit_move_insn (reg1, reg2);
 532   seq = get_insns ();
 533   end_sequence ();
 534   target_small_cost = seq_cost (seq);
 535   target_pres_cost = 2 * target_small_cost;
 536
 537   start_sequence ();
 538   emit_move_insn (mem, reg1);
 539   emit_move_insn (reg2, mem);
 540   seq = get_insns ();
 541   end_sequence ();
 542   target_spill_cost = seq_cost (seq);
 543 }
 544
 545 /* Calculates cost for having SIZE new loop global variables.  REGS_USED is the
 546    number of global registers used in loop.  N_USES is the number of relevant
 547    variable uses.  */
 548
 549 unsigned
 550 global_cost_for_size (unsigned size, unsigned regs_used, unsigned n_uses)
 551 {
 552   unsigned regs_needed = regs_used + size;
 553   unsigned cost = 0;
 554
 555   if (regs_needed + target_res_regs <= target_avail_regs)
 556     cost += target_small_cost * size;
 557   else if (regs_needed <= target_avail_regs)
 558     cost += target_pres_cost * size;
 559   else
 560     {
 561       cost += target_pres_cost * size;
 562       cost += target_spill_cost * n_uses * (regs_needed - target_avail_regs) / regs_needed;
 563     }
 564
 565   return cost;
 566 }
 567
 568 /* Sets EDGE_LOOP_EXIT flag for all exits of LOOPS.  */
 569
 570 void
 571 mark_loop_exit_edges (struct loops *loops)
 572 {
 573   basic_block bb;
 574   edge e;
 575
 576   if (loops->num <= 1)
 577     return;
 578
 579   FOR_EACH_BB (bb)
 580     {
 581       edge_iterator ei;
 582
 583       FOR_EACH_EDGE (e, ei, bb->succs)
 584         {
 585           if (bb->loop_father->outer
 586               && loop_exit_edge_p (bb->loop_father, e))
 587             e->flags |= EDGE_LOOP_EXIT;
 588           else
 589             e->flags &= ~EDGE_LOOP_EXIT;
 590         }
 591     }
 592 }
 593