gcc/cfgloopanal.c

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