gcc/cfgloopanal.c

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