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