gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002-2015 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "rtl.h"
  25 #include "hard-reg-set.h"
  26 #include "obstack.h"
  27 #include "predict.h"
  28 #include "input.h"
  29 #include "function.h"
  30 #include "dominance.h"
  31 #include "cfg.h"
  32 #include "basic-block.h"
  33 #include "cfgloop.h"
  34 #include "symtab.h"
  35 #include "flags.h"
  36 #include "alias.h"
  37 #include "tree.h"
  38 #include "insn-config.h"
  39 #include "expmed.h"
  40 #include "dojump.h"
  41 #include "explow.h"
  42 #include "calls.h"
  43 #include "emit-rtl.h"
  44 #include "varasm.h"
  45 #include "stmt.h"
  46 #include "expr.h"
  47 #include "graphds.h"
  48 #include "params.h"
  49
  50 struct target_cfgloop default_target_cfgloop;
  51 #if SWITCHABLE_TARGET
  52 struct target_cfgloop *this_target_cfgloop = &default_target_cfgloop;
  53 #endif
  54
  55 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  56
  57 bool
  58 just_once_each_iteration_p (const struct loop *loop, const_basic_block bb)
  59 {
  60   /* It must be executed at least once each iteration.  */
  61   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
  62     return false;
  63
  64   /* And just once.  */
  65   if (bb->loop_father != loop)
  66     return false;
  67
  68   /* But this was not enough.  We might have some irreducible loop here.  */
  69   if (bb->flags & BB_IRREDUCIBLE_LOOP)
  70     return false;
  71
  72   return true;
  73 }
  74
  75 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
  76    throw away all latch edges and mark blocks inside any remaining cycle.
  77    Everything is a bit complicated due to fact we do not want to do this
  78    for parts of cycles that only "pass" through some loop -- i.e. for
  79    each cycle, we want to mark blocks that belong directly to innermost
  80    loop containing the whole cycle.
  81
  82    LOOPS is the loop tree.  */
  83
  84 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block_for_fn (cfun))
  85 #define BB_REPR(BB) ((BB)->index + 1)
  86
  87 bool
  88 mark_irreducible_loops (void)
  89 {
  90   basic_block act;
  91   struct graph_edge *ge;
  92   edge e;
  93   edge_iterator ei;
  94   int src, dest;
  95   unsigned depth;
  96   struct graph *g;
  97   int num = number_of_loops (cfun);
  98   struct loop *cloop;
  99   bool irred_loop_found = false;
 100   int i;
 101
 102   gcc_assert (current_loops != NULL);
 103
 104   /* Reset the flags.  */
 105   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
 106                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
 107     {
 108       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 109       FOR_EACH_EDGE (e, ei, act->succs)
 110         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 111     }
 112
 113   /* Create the edge lists.  */
 114   g = new_graph (last_basic_block_for_fn (cfun) + num);
 115
 116   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR_FOR_FN (cfun),
 117                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
 118     FOR_EACH_EDGE (e, ei, act->succs)
 119       {
 120         /* Ignore edges to exit.  */
 121         if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
 122           continue;
 123
 124         src = BB_REPR (act);
 125         dest = BB_REPR (e->dest);
 126
 127         /* Ignore latch edges.  */
 128         if (e->dest->loop_father->header == e->dest
 129             && e->dest->loop_father->latch == act)
 130           continue;
 131
 132         /* Edges inside a single loop should be left where they are.  Edges
 133            to subloop headers should lead to representative of the subloop,
 134            but from the same place.
 135
 136            Edges exiting loops should lead from representative
 137            of the son of nearest common ancestor of the loops in that
 138            act lays.  */
 139
 140         if (e->dest->loop_father->header == e->dest)
 141           dest = LOOP_REPR (e->dest->loop_father);
 142
 143         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
 144           {
 145             depth = 1 + loop_depth (find_common_loop (act->loop_father,
 146                                                       e->dest->loop_father));
 147             if (depth == loop_depth (act->loop_father))
 148               cloop = act->loop_father;
 149             else
 150               cloop = (*act->loop_father->superloops)[depth];
 151
 152             src = LOOP_REPR (cloop);
 153           }
 154
 155         add_edge (g, src, dest)->data = e;
 156       }
 157
 158   /* Find the strongly connected components.  */
 159   graphds_scc (g, NULL);
 160
 161   /* Mark the irreducible loops.  */
 162   for (i = 0; i < g->n_vertices; i++)
 163     for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
 164       {
 165         edge real = (edge) ge->data;
 166         /* edge E in graph G is irreducible if it connects two vertices in the
 167            same scc.  */
 168
 169         /* All edges should lead from a component with higher number to the
 170            one with lower one.  */
 171         gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
 172
 173         if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
 174           continue;
 175
 176         real->flags |= EDGE_IRREDUCIBLE_LOOP;
 177         irred_loop_found = true;
 178         if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
 179           real->src->flags |= BB_IRREDUCIBLE_LOOP;
 180       }
 181
 182   free_graph (g);
 183
 184   loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
 185   return irred_loop_found;
 186 }
 187
 188 /* Counts number of insns inside LOOP.  */
 189 int
 190 num_loop_insns (const struct loop *loop)
 191 {
 192   basic_block *bbs, bb;
 193   unsigned i, ninsns = 0;
 194   rtx_insn *insn;
 195
 196   bbs = get_loop_body (loop);
 197   for (i = 0; i < loop->num_nodes; i++)
 198     {
 199       bb = bbs[i];
 200       FOR_BB_INSNS (bb, insn)
 201         if (NONDEBUG_INSN_P (insn))
 202           ninsns++;
 203     }
 204   free (bbs);
 205
 206   if (!ninsns)
 207     ninsns = 1; /* To avoid division by zero.  */
 208
 209   return ninsns;
 210 }
 211
 212 /* Counts number of insns executed on average per iteration LOOP.  */
 213 int
 214 average_num_loop_insns (const struct loop *loop)
 215 {
 216   basic_block *bbs, bb;
 217   unsigned i, binsns, ninsns, ratio;
 218   rtx_insn *insn;
 219
 220   ninsns = 0;
 221   bbs = get_loop_body (loop);
 222   for (i = 0; i < loop->num_nodes; i++)
 223     {
 224       bb = bbs[i];
 225
 226       binsns = 0;
 227       FOR_BB_INSNS (bb, insn)
 228         if (NONDEBUG_INSN_P (insn))
 229           binsns++;
 230
 231       ratio = loop->header->frequency == 0
 232               ? BB_FREQ_MAX
 233               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
 234       ninsns += binsns * ratio;
 235     }
 236   free (bbs);
 237
 238   ninsns /= BB_FREQ_MAX;
 239   if (!ninsns)
 240     ninsns = 1; /* To avoid division by zero.  */
 241
 242   return ninsns;
 243 }
 244
 245 /* Returns expected number of iterations of LOOP, according to
 246    measured or guessed profile.  No bounding is done on the
 247    value.  */
 248
 249 gcov_type
 250 expected_loop_iterations_unbounded (const struct loop *loop)
 251 {
 252   edge e;
 253   edge_iterator ei;
 254
 255   if (loop->latch->count || loop->header->count)
 256     {
 257       gcov_type count_in, count_latch, expected;
 258
 259       count_in = 0;
 260       count_latch = 0;
 261
 262       FOR_EACH_EDGE (e, ei, loop->header->preds)
 263         if (e->src == loop->latch)
 264           count_latch = e->count;
 265         else
 266           count_in += e->count;
 267
 268       if (count_in == 0)
 269         expected = count_latch * 2;
 270       else
 271         expected = (count_latch + count_in - 1) / count_in;
 272
 273       return expected;
 274     }
 275   else
 276     {
 277       int freq_in, freq_latch;
 278
 279       freq_in = 0;
 280       freq_latch = 0;
 281
 282       FOR_EACH_EDGE (e, ei, loop->header->preds)
 283         if (e->src == loop->latch)
 284           freq_latch = EDGE_FREQUENCY (e);
 285         else
 286           freq_in += EDGE_FREQUENCY (e);
 287
 288       if (freq_in == 0)
 289         return freq_latch * 2;
 290
 291       return (freq_latch + freq_in - 1) / freq_in;
 292     }
 293 }
 294
 295 /* Returns expected number of LOOP iterations.  The returned value is bounded
 296    by REG_BR_PROB_BASE.  */
 297
 298 unsigned
 299 expected_loop_iterations (const struct loop *loop)
 300 {
 301   gcov_type expected = expected_loop_iterations_unbounded (loop);
 302   return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
 303 }
 304
 305 /* Returns the maximum level of nesting of subloops of LOOP.  */
 306
 307 unsigned
 308 get_loop_level (const struct loop *loop)
 309 {
 310   const struct loop *ploop;
 311   unsigned mx = 0, l;
 312
 313   for (ploop = loop->inner; ploop; ploop = ploop->next)
 314     {
 315       l = get_loop_level (ploop);
 316       if (l >= mx)
 317         mx = l + 1;
 318     }
 319   return mx;
 320 }
 321
 322 /* Initialize the constants for computing set costs.  */
 323
 324 void
 325 init_set_costs (void)
 326 {
 327   int speed;
 328   rtx_insn *seq;
 329   rtx reg1 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 1);
 330   rtx reg2 = gen_raw_REG (SImode, LAST_VIRTUAL_REGISTER + 2);
 331   rtx addr = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 3);
 332   rtx mem = validize_mem (gen_rtx_MEM (SImode, addr));
 333   unsigned i;
 334
 335   target_avail_regs = 0;
 336   target_clobbered_regs = 0;
 337   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 338     if (TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], i)
 339         && !fixed_regs[i])
 340       {
 341         target_avail_regs++;
 342         if (call_used_regs[i])
 343           target_clobbered_regs++;
 344       }
 345
 346   target_res_regs = 3;
 347
 348   for (speed = 0; speed < 2; speed++)
 349      {
 350       crtl->maybe_hot_insn_p = speed;
 351       /* Set up the costs for using extra registers:
 352
 353          1) If not many free registers remain, we should prefer having an
 354             additional move to decreasing the number of available registers.
 355             (TARGET_REG_COST).
 356          2) If no registers are available, we need to spill, which may require
 357             storing the old value to memory and loading it back
 358             (TARGET_SPILL_COST).  */
 359
 360       start_sequence ();
 361       emit_move_insn (reg1, reg2);
 362       seq = get_insns ();
 363       end_sequence ();
 364       target_reg_cost [speed] = seq_cost (seq, speed);
 365
 366       start_sequence ();
 367       emit_move_insn (mem, reg1);
 368       emit_move_insn (reg2, mem);
 369       seq = get_insns ();
 370       end_sequence ();
 371       target_spill_cost [speed] = seq_cost (seq, speed);
 372     }
 373   default_rtl_profile ();
 374 }
 375
 376 /* Estimates cost of increased register pressure caused by making N_NEW new
 377    registers live around the loop.  N_OLD is the number of registers live
 378    around the loop.  If CALL_P is true, also take into account that
 379    call-used registers may be clobbered in the loop body, reducing the
 380    number of available registers before we spill.  */
 381
 382 unsigned
 383 estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed,
 384                             bool call_p)
 385 {
 386   unsigned cost;
 387   unsigned regs_needed = n_new + n_old;
 388   unsigned available_regs = target_avail_regs;
 389
 390   /* If there is a call in the loop body, the call-clobbered registers
 391      are not available for loop invariants.  */
 392   if (call_p)
 393     available_regs = available_regs - target_clobbered_regs;
 394
 395   /* If we have enough registers, we should use them and not restrict
 396      the transformations unnecessarily.  */
 397   if (regs_needed + target_res_regs <= available_regs)
 398     return 0;
 399
 400   if (regs_needed <= available_regs)
 401     /* If we are close to running out of registers, try to preserve
 402        them.  */
 403     cost = target_reg_cost [speed] * n_new;
 404   else
 405     /* If we run out of registers, it is very expensive to add another
 406        one.  */
 407     cost = target_spill_cost [speed] * n_new;
 408
 409   if (optimize && (flag_ira_region == IRA_REGION_ALL
 410                    || flag_ira_region == IRA_REGION_MIXED)
 411       && number_of_loops (cfun) <= (unsigned) IRA_MAX_LOOPS_NUM)
 412     /* IRA regional allocation deals with high register pressure
 413        better.  So decrease the cost (to do more accurate the cost
 414        calculation for IRA, we need to know how many registers lives
 415        through the loop transparently).  */
 416     cost /= 2;
 417
 418   return cost;
 419 }
 420
 421 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 422
 423 void
 424 mark_loop_exit_edges (void)
 425 {
 426   basic_block bb;
 427   edge e;
 428
 429   if (number_of_loops (cfun) <= 1)
 430     return;
 431
 432   FOR_EACH_BB_FN (bb, cfun)
 433     {
 434       edge_iterator ei;
 435
 436       FOR_EACH_EDGE (e, ei, bb->succs)
 437         {
 438           if (loop_outer (bb->loop_father)
 439               && loop_exit_edge_p (bb->loop_father, e))
 440             e->flags |= EDGE_LOOP_EXIT;
 441           else
 442             e->flags &= ~EDGE_LOOP_EXIT;
 443         }
 444     }
 445 }
 446
 447 /* Return exit edge if loop has only one exit that is likely
 448    to be executed on runtime (i.e. it is not EH or leading
 449    to noreturn call.  */
 450
 451 edge
 452 single_likely_exit (struct loop *loop)
 453 {
 454   edge found = single_exit (loop);
 455   vec<edge> exits;
 456   unsigned i;
 457   edge ex;
 458
 459   if (found)
 460     return found;
 461   exits = get_loop_exit_edges (loop);
 462   FOR_EACH_VEC_ELT (exits, i, ex)
 463     {
 464       if (ex->flags & (EDGE_EH | EDGE_ABNORMAL_CALL))
 465         continue;
 466       /* The constant of 5 is set in a way so noreturn calls are
 467          ruled out by this test.  The static branch prediction algorithm
 468          will not assign such a low probability to conditionals for usual
 469          reasons.  */
 470       if (profile_status_for_fn (cfun) != PROFILE_ABSENT
 471           && ex->probability < 5 && !ex->count)
 472         continue;
 473       if (!found)
 474         found = ex;
 475       else
 476         {
 477           exits.release ();
 478           return NULL;
 479         }
 480     }
 481   exits.release ();
 482   return found;
 483 }
 484
 485
 486 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 487    order against direction of edges from latch.  Specially, if
 488    header != latch, latch is the 1-st block.  */
 489
 490 vec<basic_block>
 491 get_loop_hot_path (const struct loop *loop)
 492 {
 493   basic_block bb = loop->header;
 494   vec<basic_block> path = vNULL;
 495   bitmap visited = BITMAP_ALLOC (NULL);
 496
 497   while (true)
 498     {
 499       edge_iterator ei;
 500       edge e;
 501       edge best = NULL;
 502
 503       path.safe_push (bb);
 504       bitmap_set_bit (visited, bb->index);
 505       FOR_EACH_EDGE (e, ei, bb->succs)
 506         if ((!best || e->probability > best->probability)
 507             && !loop_exit_edge_p (loop, e)
 508             && !bitmap_bit_p (visited, e->dest->index))
 509           best = e;
 510       if (!best || best->dest == loop->header)
 511         break;
 512       bb = best->dest;
 513     }
 514   BITMAP_FREE (visited);
 515   return path;
 516 }