gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002 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 "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "expr.h"
  30 #include "output.h"
  31
  32 struct unmark_altered_insn_data;
  33 static void unmark_altered       PARAMS ((rtx, rtx, regset));
  34 static void blocks_invariant_registers PARAMS ((basic_block *, int, regset));
  35 static void unmark_altered_insn  PARAMS ((rtx, rtx, struct unmark_altered_insn_data *));
  36 static void blocks_single_set_registers PARAMS ((basic_block *, int, rtx *));
  37 static int invariant_rtx_wrto_regs_p_helper PARAMS ((rtx *, regset));
  38 static bool invariant_rtx_wrto_regs_p PARAMS ((rtx, regset));
  39 static rtx test_for_iteration PARAMS ((struct loop_desc *desc,
  40                                        unsigned HOST_WIDE_INT));
  41 static bool constant_iterations PARAMS ((struct loop_desc *,
  42                                          unsigned HOST_WIDE_INT *,
  43                                          bool *));
  44 static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
  45                                         edge, regset, rtx *,
  46                                         struct loop_desc *));
  47 static rtx variable_initial_value PARAMS ((rtx, regset, rtx, rtx *));
  48 static rtx variable_initial_values PARAMS ((edge, rtx));
  49 static bool simple_condition_p PARAMS ((struct loop *, rtx,
  50                                         regset, struct loop_desc *));
  51 static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
  52                                              rtx *, struct loop_desc *));
  53
  54 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  55 bool
  56 just_once_each_iteration_p (loops, loop, bb)
  57      struct loops *loops;
  58      struct loop *loop;
  59      basic_block bb;
  60 {
  61   /* It must be executed at least once each iteration.  */
  62   if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
  63     return false;
  64
  65   /* And just once.  */
  66   if (bb->loop_father != loop)
  67     return false;
  68
  69   /* But this was not enough.  We might have some irreducible loop here.  */
  70   if (bb->flags & BB_IRREDUCIBLE_LOOP)
  71     return false;
  72
  73   return true;
  74 }
  75
  76
  77 /* Unmarks modified registers; helper to blocks_invariant_registers.  */
  78 static void
  79 unmark_altered (what, by, regs)
  80      rtx what;
  81      rtx by ATTRIBUTE_UNUSED;
  82      regset regs;
  83 {
  84   if (GET_CODE (what) == SUBREG)
  85     what = SUBREG_REG (what);
  86   if (!REG_P (what))
  87     return;
  88   CLEAR_REGNO_REG_SET (regs, REGNO (what));
  89 }
  90
  91 /* Marks registers that are invariant inside blocks BBS.  */
  92 static void
  93 blocks_invariant_registers (bbs, nbbs, regs)
  94      basic_block *bbs;
  95      int nbbs;
  96      regset regs;
  97 {
  98   rtx insn;
  99   int i;
 100
 101   for (i = 0; i < max_reg_num (); i++)
 102     SET_REGNO_REG_SET (regs, i);
 103   for (i = 0; i < nbbs; i++)
 104     for (insn = bbs[i]->head;
 105          insn != NEXT_INSN (bbs[i]->end);
 106          insn = NEXT_INSN (insn))
 107       if (INSN_P (insn))
 108         note_stores (PATTERN (insn),
 109                      (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered,
 110                      regs);
 111 }
 112
 113 /* Unmarks modified registers; helper to blocks_single_set_registers.  */
 114 struct unmark_altered_insn_data
 115 {
 116   rtx *regs;
 117   rtx insn;
 118 };
 119
 120 static void
 121 unmark_altered_insn (what, by, data)
 122      rtx what;
 123      rtx by ATTRIBUTE_UNUSED;
 124      struct unmark_altered_insn_data *data;
 125 {
 126   int rn;
 127
 128   if (GET_CODE (what) == SUBREG)
 129     what = SUBREG_REG (what);
 130   if (!REG_P (what))
 131     return;
 132   rn = REGNO (what);
 133   if (data->regs[rn] == data->insn)
 134     return;
 135   data->regs[rn] = NULL;
 136 }
 137
 138 /* Marks registers that have just single simple set in BBS; the relevant
 139    insn is returned in REGS.  */
 140 static void
 141 blocks_single_set_registers (bbs, nbbs, regs)
 142      basic_block *bbs;
 143      int nbbs;
 144      rtx *regs;
 145 {
 146   rtx insn;
 147   int i;
 148   struct unmark_altered_insn_data data;
 149
 150   for (i = 0; i < max_reg_num (); i++)
 151     regs[i] = NULL;
 152
 153   for (i = 0; i < nbbs; i++)
 154     for (insn = bbs[i]->head;
 155          insn != NEXT_INSN (bbs[i]->end);
 156          insn = NEXT_INSN (insn))
 157       {
 158         rtx set = single_set (insn);
 159         if (!set)
 160           continue;
 161         if (!REG_P (SET_DEST (set)))
 162           continue;
 163         regs[REGNO (SET_DEST (set))] = insn;
 164       }
 165
 166   data.regs = regs;
 167   for (i = 0; i < nbbs; i++)
 168     for (insn = bbs[i]->head;
 169          insn != NEXT_INSN (bbs[i]->end);
 170          insn = NEXT_INSN (insn))
 171       {
 172         if (!INSN_P (insn))
 173           continue;
 174         data.insn = insn;
 175         note_stores (PATTERN (insn),
 176             (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered_insn,
 177             &data);
 178       }
 179 }
 180
 181 /* Helper for invariant_rtx_wrto_regs_p.  */
 182 static int
 183 invariant_rtx_wrto_regs_p_helper (expr, invariant_regs)
 184      rtx *expr;
 185      regset invariant_regs;
 186 {
 187   switch (GET_CODE (*expr))
 188     {
 189     case CC0:
 190     case PC:
 191     case UNSPEC_VOLATILE:
 192       return 1;
 193
 194     case CONST_INT:
 195     case CONST_DOUBLE:
 196     case CONST:
 197     case SYMBOL_REF:
 198     case LABEL_REF:
 199       return 0;
 200
 201     case ASM_OPERANDS:
 202       return MEM_VOLATILE_P (*expr);
 203
 204     case MEM:
 205       /* If the memory is not constant, assume it is modified.  If it is
 206          constant, we still have to check the address.  */
 207       return !RTX_UNCHANGING_P (*expr);
 208
 209     case REG:
 210       return !REGNO_REG_SET_P (invariant_regs, REGNO (*expr));
 211
 212     default:
 213       return 0;
 214     }
 215 }
 216
 217 /* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant.  */
 218 static bool
 219 invariant_rtx_wrto_regs_p (expr, invariant_regs)
 220      rtx expr;
 221      regset invariant_regs;
 222 {
 223   return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper,
 224                         invariant_regs);
 225 }
 226
 227 /* Checks whether CONDITION is a simple comparison in that one of operands
 228    is register and the other one is invariant in the LOOP. Fills var, lim
 229    and cond fields in DESC.  */
 230 static bool
 231 simple_condition_p (loop, condition, invariant_regs, desc)
 232      struct loop *loop ATTRIBUTE_UNUSED;
 233      rtx condition;
 234      regset invariant_regs;
 235      struct loop_desc *desc;
 236 {
 237   rtx op0, op1;
 238
 239   /* Check condition.  */
 240   switch (GET_CODE (condition))
 241     {
 242       case EQ:
 243       case NE:
 244       case LE:
 245       case LT:
 246       case GE:
 247       case GT:
 248       case GEU:
 249       case GTU:
 250       case LEU:
 251       case LTU:
 252         break;
 253       default:
 254         return false;
 255     }
 256
 257   /* Of integers or pointers.  */
 258   if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
 259       && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
 260     return false;
 261
 262   /* One of operands must be a simple register.  */
 263   op0 = XEXP (condition, 0);
 264   op1 = XEXP (condition, 1);
 265
 266   /* One of operands must be invariant.  */
 267   if (invariant_rtx_wrto_regs_p (op0, invariant_regs))
 268     {
 269       /* And the other one must be a register.  */
 270       if (!REG_P (op1))
 271         return false;
 272       desc->var = op1;
 273       desc->lim = op0;
 274
 275       desc->cond = swap_condition (GET_CODE (condition));
 276       if (desc->cond == UNKNOWN)
 277         return false;
 278       return true;
 279     }
 280
 281   /* Check the other operand.  */
 282   if (!invariant_rtx_wrto_regs_p (op1, invariant_regs))
 283     return false;
 284   if (!REG_P (op0))
 285     return false;
 286
 287   desc->var = op0;
 288   desc->lim = op1;
 289
 290   desc->cond = GET_CODE (condition);
 291
 292   return true;
 293 }
 294
 295 /* Checks whether DESC->var is incremented/decremented exactly once each
 296    iteration.  Fills in DESC->stride and returns block in that DESC->var is
 297    modified.  */
 298 static basic_block
 299 simple_increment (loops, loop, simple_increment_regs, desc)
 300      struct loops *loops;
 301      struct loop *loop;
 302      rtx *simple_increment_regs;
 303      struct loop_desc *desc;
 304 {
 305   rtx mod_insn, set, set_src, set_add;
 306   basic_block mod_bb;
 307
 308   /* Find insn that modifies var.  */
 309   mod_insn = simple_increment_regs[REGNO (desc->var)];
 310   if (!mod_insn)
 311     return NULL;
 312   mod_bb = BLOCK_FOR_INSN (mod_insn);
 313
 314   /* Check that it is executed exactly once each iteration.  */
 315   if (!just_once_each_iteration_p (loops, loop, mod_bb))
 316     return NULL;
 317
 318   /* mod_insn must be a simple increment/decrement.  */
 319   set = single_set (mod_insn);
 320   if (!set)
 321     abort ();
 322   if (!rtx_equal_p (SET_DEST (set), desc->var))
 323     abort ();
 324
 325   set_src = find_reg_equal_equiv_note (mod_insn);
 326   if (!set_src)
 327     set_src = SET_SRC (set);
 328   if (GET_CODE (set_src) != PLUS)
 329     return NULL;
 330   if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
 331     return NULL;
 332
 333   /* Set desc->stride.  */
 334   set_add = XEXP (set_src, 1);
 335   if (CONSTANT_P (set_add))
 336     desc->stride = set_add;
 337   else
 338     return NULL;
 339
 340   return mod_bb;
 341 }
 342
 343 /* Tries to find initial value of VAR in INSN.  This value must be invariant
 344    wrto INVARIANT_REGS.  If SET_INSN is not NULL, insn in that var is set is
 345    placed here.  */
 346 static rtx
 347 variable_initial_value (insn, invariant_regs, var, set_insn)
 348      rtx insn;
 349      regset invariant_regs;
 350      rtx var;
 351      rtx *set_insn;
 352 {
 353   basic_block bb;
 354   rtx set;
 355
 356   /* Go back through cfg.  */
 357   bb = BLOCK_FOR_INSN (insn);
 358   while (1)
 359     {
 360       for (; insn != bb->head; insn = PREV_INSN (insn))
 361         {
 362           if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
 363             break;
 364           if (INSN_P (insn))
 365             note_stores (PATTERN (insn),
 366                 (void (*) PARAMS ((rtx, rtx, void *))) unmark_altered,
 367                 invariant_regs);
 368         }
 369
 370       if (insn != bb->head)
 371         {
 372           /* We found place where var is set.  */
 373           rtx set_dest;
 374           rtx val;
 375           rtx note;
 376
 377           set = single_set (insn);
 378           if (!set)
 379             return NULL;
 380           set_dest = SET_DEST (set);
 381           if (!rtx_equal_p (set_dest, var))
 382             return NULL;
 383
 384           note = find_reg_equal_equiv_note (insn);
 385           if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
 386             val = XEXP (note, 0);
 387           else
 388             val = SET_SRC (set);
 389           if (!invariant_rtx_wrto_regs_p (val, invariant_regs))
 390             return NULL;
 391
 392           if (set_insn)
 393             *set_insn = insn;
 394           return val;
 395         }
 396
 397
 398       if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
 399         return NULL;
 400
 401       bb = bb->pred->src;
 402       insn = bb->end;
 403     }
 404
 405   return NULL;
 406 }
 407
 408 /* Returns list of definitions of initial value of VAR at Edge.  */
 409 static rtx
 410 variable_initial_values (e, var)
 411      edge e;
 412      rtx var;
 413 {
 414   rtx set_insn, list;
 415   regset invariant_regs;
 416   regset_head invariant_regs_head;
 417   int i;
 418
 419   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
 420   for (i = 0; i < max_reg_num (); i++)
 421     SET_REGNO_REG_SET (invariant_regs, i);
 422
 423   list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
 424
 425   if (e->src == ENTRY_BLOCK_PTR)
 426     return list;
 427
 428   set_insn = e->src->end;
 429   while (REG_P (var)
 430          && (var = variable_initial_value (set_insn, invariant_regs, var, &set_insn)))
 431     list = alloc_EXPR_LIST (0, copy_rtx (var), list);
 432
 433   FREE_REG_SET (invariant_regs);
 434   return list;
 435 }
 436
 437 /* Counts constant number of iterations of the loop described by DESC;
 438    returns false if impossible.  */
 439 static bool
 440 constant_iterations (desc, niter, may_be_zero)
 441      struct loop_desc *desc;
 442      unsigned HOST_WIDE_INT *niter;
 443      bool *may_be_zero;
 444 {
 445   rtx test, expr;
 446   rtx ainit, alim;
 447
 448   test = test_for_iteration (desc, 0);
 449   if (test == const0_rtx)
 450     {
 451       *niter = 0;
 452       *may_be_zero = false;
 453       return true;
 454     }
 455
 456   *may_be_zero = (test != const_true_rtx);
 457
 458   /* It would make a little sense to check every with every when we
 459      know that all but the first alternative are simply registers.  */
 460   for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
 461     {
 462       alim = XEXP (desc->lim_alts, 0);
 463       if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
 464         abort ();
 465       if (GET_CODE (expr) == CONST_INT)
 466         {
 467           *niter = INTVAL (expr);
 468           return true;
 469         }
 470     }
 471   for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
 472     {
 473       ainit = XEXP (desc->var_alts, 0);
 474       if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
 475         abort ();
 476       if (GET_CODE (expr) == CONST_INT)
 477         {
 478           *niter = INTVAL (expr);
 479           return true;
 480         }
 481     }
 482
 483   return false;
 484 }
 485
 486 /* Return RTX expression representing number of iterations of loop as bounded
 487    by test described by DESC (in the case loop really has multiple exit
 488    edges, fewer iterations may happen in the practice).
 489
 490    Return NULL if it is unknown.  Additionally the value may be invalid for
 491    paradoxical loop (lets define paradoxical loops as loops whose test is
 492    failing at -1th iteration, for instance "for (i=5;i<1;i++);").
 493
 494    These cases needs to be either cared by copying the loop test in the front
 495    of loop or keeping the test in first iteration of loop.
 496
 497    When INIT/LIM are set, they are used instead of var/lim of DESC.  */
 498 rtx
 499 count_loop_iterations (desc, init, lim)
 500      struct loop_desc *desc;
 501      rtx init;
 502      rtx lim;
 503 {
 504   enum rtx_code cond = desc->cond;
 505   rtx stride = desc->stride;
 506   rtx mod, exp;
 507
 508   /* Give up on floating point modes and friends.  It can be possible to do
 509      the job for constant loop bounds, but it is probably not worthwhile.  */
 510   if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
 511     return NULL;
 512
 513   init = copy_rtx (init ? init : desc->var);
 514   lim = copy_rtx (lim ? lim : desc->lim);
 515
 516   /* Ensure that we always handle the condition to stay inside loop.  */
 517   if (desc->neg)
 518     cond = reverse_condition (cond);
 519
 520   /* Compute absolute value of the difference of initial and final value.  */
 521   if (INTVAL (stride) > 0)
 522     {
 523       /* Bypass nonsensical tests.  */
 524       if (cond == EQ || cond == GE || cond == GT || cond == GEU
 525           || cond == GTU)
 526         return NULL;
 527       exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
 528                                  lim, init);
 529     }
 530   else
 531     {
 532       /* Bypass nonsensical tests.  */
 533       if (cond == EQ || cond == LE || cond == LT || cond == LEU
 534           || cond == LTU)
 535         return NULL;
 536       exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
 537                                  init, lim);
 538       stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
 539                                    stride, GET_MODE (desc->var));
 540     }
 541
 542   /* Normalize difference so the value is always first examined
 543      and later incremented.  */
 544
 545   if (!desc->postincr)
 546     exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
 547                                exp, stride);
 548
 549   /* Determine delta caused by exit condition.  */
 550   switch (cond)
 551     {
 552     case NE:
 553       /* For NE tests, make sure that the iteration variable won't miss
 554          the final value.  If EXP mod STRIDE is not zero, then the
 555          iteration variable will overflow before the loop exits, and we
 556          can not calculate the number of iterations easily.  */
 557       if (stride != const1_rtx
 558           && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
 559               != const0_rtx))
 560         return NULL;
 561       break;
 562     case LT:
 563     case GT:
 564     case LTU:
 565     case GTU:
 566       break;
 567     case LE:
 568     case GE:
 569     case LEU:
 570     case GEU:
 571       exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
 572                                  exp, const1_rtx);
 573       break;
 574     default:
 575       abort ();
 576     }
 577
 578   if (stride != const1_rtx)
 579     {
 580       /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
 581          but we need to take care for overflows.  */
 582
 583       mod = simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride);
 584
 585       /* This is dirty trick.  When we can't compute number of iterations
 586          to be constant, we simply ignore the possible overflow, as
 587          runtime unroller always use power of 2 amounts and does not
 588          care about possible lost bits.  */
 589
 590       if (GET_CODE (mod) != CONST_INT)
 591         {
 592           rtx stridem1 = simplify_gen_binary (PLUS, GET_MODE (desc->var),
 593                                               stride, constm1_rtx);
 594           exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
 595                                      exp, stridem1);
 596           exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
 597         }
 598       else
 599         {
 600           exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
 601           if (mod != const0_rtx)
 602             exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
 603                                        exp, const1_rtx);
 604         }
 605     }
 606
 607   if (rtl_dump_file)
 608     {
 609       fprintf (rtl_dump_file, ";  Number of iterations: ");
 610       print_simple_rtl (rtl_dump_file, exp);
 611       fprintf (rtl_dump_file, "\n");
 612     }
 613
 614   return exp;
 615 }
 616
 617 /* Return simplified RTX expression representing the value of test
 618    described of DESC at given iteration of loop.  */
 619
 620 static rtx
 621 test_for_iteration (desc, iter)
 622      struct loop_desc *desc;
 623      unsigned HOST_WIDE_INT iter;
 624 {
 625   enum rtx_code cond = desc->cond;
 626   rtx exp = XEXP (desc->var_alts, 0);
 627   rtx addval;
 628
 629   /* Give up on floating point modes and friends.  It can be possible to do
 630      the job for constant loop bounds, but it is probably not worthwhile.  */
 631   if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
 632     return NULL;
 633
 634   /* Ensure that we always handle the condition to stay inside loop.  */
 635   if (desc->neg)
 636     cond = reverse_condition (cond);
 637
 638   /* Compute the value of induction variable.  */
 639   addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
 640                                 desc->stride,
 641                                 gen_int_mode (desc->postincr
 642                                               ? iter : iter + 1,
 643                                               GET_MODE (desc->var)));
 644   exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
 645   /* Test at given condition.  */
 646   exp = simplify_gen_relational (cond, SImode,
 647                                  GET_MODE (desc->var), exp, desc->lim);
 648
 649   if (rtl_dump_file)
 650     {
 651       fprintf (rtl_dump_file, ";  Conditional to continue loop at "
 652                HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
 653       print_simple_rtl (rtl_dump_file, exp);
 654       fprintf (rtl_dump_file, "\n");
 655     }
 656   return exp;
 657 }
 658
 659
 660 /* Tests whether exit at EXIT_EDGE from LOOP is simple.  Returns simple loop
 661    description joined to it in in DESC.  INVARIANT_REGS and SINGLE_SET_REGS
 662    are results of blocks_{invariant,single_set}_regs over BODY.  */
 663 static bool
 664 simple_loop_exit_p (loops, loop, exit_edge, invariant_regs, single_set_regs, desc)
 665      struct loops *loops;
 666      struct loop *loop;
 667      edge exit_edge;
 668      struct loop_desc *desc;
 669      regset invariant_regs;
 670      rtx *single_set_regs;
 671 {
 672   basic_block mod_bb, exit_bb;
 673   int fallthru_out;
 674   rtx condition;
 675   edge ei, e;
 676
 677   exit_bb = exit_edge->src;
 678
 679   fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
 680
 681   if (!exit_bb)
 682     return false;
 683
 684   /* It must be tested (at least) once during any iteration.  */
 685   if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
 686     return false;
 687
 688   /* It must end in a simple conditional jump.  */
 689   if (!any_condjump_p (exit_bb->end))
 690     return false;
 691
 692   ei = exit_bb->succ;
 693   if (ei == exit_edge)
 694     ei = ei->succ_next;
 695
 696   desc->out_edge = exit_edge;
 697   desc->in_edge = ei;
 698
 699   /* Condition must be a simple comparison in that one of operands
 700      is register and the other one is invariant.  */
 701   if (!(condition = get_condition (exit_bb->end, NULL)))
 702     return false;
 703
 704   if (!simple_condition_p (loop, condition, invariant_regs, desc))
 705     return false;
 706
 707   /*  Var must be simply incremented or decremented in exactly one insn that
 708      is executed just once every iteration.  */
 709   if (!(mod_bb = simple_increment (loops, loop, single_set_regs, desc)))
 710     return false;
 711
 712   /* OK, it is simple loop.  Now just fill in remaining info.  */
 713   desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
 714   desc->neg = !fallthru_out;
 715
 716   /* Find initial value of var and alternative values for lim.  */
 717   e = loop_preheader_edge (loop);
 718   desc->var_alts = variable_initial_values (e, desc->var);
 719   desc->lim_alts = variable_initial_values (e, desc->lim);
 720
 721   /* Number of iterations.  */
 722   if (!count_loop_iterations (desc, NULL, NULL))
 723     return false;
 724   desc->const_iter =
 725     constant_iterations (desc, &desc->niter, &desc->may_be_zero);
 726   return true;
 727 }
 728
 729 /* Tests whether LOOP is simple for loop.  Returns simple loop description
 730    in DESC.  */
 731 bool
 732 simple_loop_p (loops, loop, desc)
 733      struct loops *loops;
 734      struct loop *loop;
 735      struct loop_desc *desc;
 736 {
 737   unsigned i;
 738   basic_block *body;
 739   edge e;
 740   struct loop_desc act;
 741   bool any = false;
 742   regset invariant_regs;
 743   regset_head invariant_regs_head;
 744   rtx *single_set_regs;
 745   int n_branches;
 746
 747   body = get_loop_body (loop);
 748
 749   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
 750   single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
 751
 752   blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
 753   blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
 754
 755   n_branches = 0;
 756   for (i = 0; i < loop->num_nodes; i++)
 757     {
 758       for (e = body[i]->succ; e; e = e->succ_next)
 759         if (!flow_bb_inside_loop_p (loop, e->dest)
 760             && simple_loop_exit_p (loops, loop, e,
 761                    invariant_regs, single_set_regs, &act))
 762           {
 763             /* Prefer constant iterations; the less the better.  */
 764             if (!any)
 765               any = true;
 766             else if (!act.const_iter
 767                      || (desc->const_iter && act.niter >= desc->niter))
 768               continue;
 769             *desc = act;
 770           }
 771
 772       if (body[i]->succ && body[i]->succ->succ_next)
 773         n_branches++;
 774     }
 775   desc->n_branches = n_branches;
 776
 777   if (rtl_dump_file && any)
 778     {
 779       fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
 780       if (desc->postincr)
 781         fprintf (rtl_dump_file,
 782                  ";  does postincrement after loop exit condition\n");
 783
 784       fprintf (rtl_dump_file, ";  Induction variable:");
 785       print_simple_rtl (rtl_dump_file, desc->var);
 786       fputc ('\n', rtl_dump_file);
 787
 788       fprintf (rtl_dump_file, ";  Initial values:");
 789       print_simple_rtl (rtl_dump_file, desc->var_alts);
 790       fputc ('\n', rtl_dump_file);
 791
 792       fprintf (rtl_dump_file, ";  Stride:");
 793       print_simple_rtl (rtl_dump_file, desc->stride);
 794       fputc ('\n', rtl_dump_file);
 795
 796       fprintf (rtl_dump_file, ";  Compared with:");
 797       print_simple_rtl (rtl_dump_file, desc->lim);
 798       fputc ('\n', rtl_dump_file);
 799
 800       fprintf (rtl_dump_file, ";  Alternative values:");
 801       print_simple_rtl (rtl_dump_file, desc->lim_alts);
 802       fputc ('\n', rtl_dump_file);
 803
 804       fprintf (rtl_dump_file, ";  Exit condition:");
 805       if (desc->neg)
 806         fprintf (rtl_dump_file, "(negated)");
 807       fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
 808
 809       fprintf (rtl_dump_file, ";  Number of branches:");
 810       fprintf (rtl_dump_file, "%d\n", desc->n_branches);
 811
 812       fputc ('\n', rtl_dump_file);
 813     }
 814
 815   free (body);
 816   FREE_REG_SET (invariant_regs);
 817   free (single_set_regs);
 818   return any;
 819 }
 820
 821 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
 822    throw away all latch edges and mark blocks inside any remaining cycle.
 823    Everything is a bit complicated due to fact we do not want to do this
 824    for parts of cycles that only "pass" through some loop -- i.e. for
 825    each cycle, we want to mark blocks that belong directly to innermost
 826    loop containing the whole cycle.  */
 827 void
 828 mark_irreducible_loops (loops)
 829      struct loops *loops;
 830 {
 831   int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
 832   unsigned i;
 833   edge **edges, e;
 834   edge *estack;
 835   basic_block act;
 836   int stack_top, tick, depth;
 837   struct loop *cloop;
 838
 839   /* Reset the flags.  */
 840   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 841     {
 842       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 843       for (e = act->succ; e; e = e->succ_next)
 844         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 845     }
 846
 847   /* The first last_basic_block + 1 entries are for real blocks (including
 848      entry); then we have loops->num - 1 fake blocks for loops to that we
 849      assign edges leading from loops (fake loop 0 is not interesting).  */
 850   dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 851   closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 852   mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 853   mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 854   n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 855   edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
 856   stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
 857   estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
 858
 859   /* Create the edge lists.  */
 860   for (i = 0; i < last_basic_block + loops->num; i++)
 861     n_edges[i] = 0;
 862   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 863     for (e = act->succ; e; e = e->succ_next)
 864       {
 865         /* Ignore edges to exit.  */
 866         if (e->dest == EXIT_BLOCK_PTR)
 867           continue;
 868         /* And latch edges.  */
 869         if (e->dest->loop_father->header == e->dest
 870             && e->dest->loop_father->latch == act)
 871           continue;
 872         /* Edges inside a single loop should be left where they are.  Edges
 873            to subloop headers should lead to representative of the subloop,
 874            but from the same place.  */
 875         if (act->loop_father == e->dest->loop_father
 876             || act->loop_father == e->dest->loop_father->outer)
 877           {
 878             n_edges[act->index + 1]++;
 879             continue;
 880           }
 881         /* Edges exiting loops remain.  They should lead from representative
 882            of the son of nearest common ancestor of the loops in that
 883            act lays.  */
 884         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
 885         if (depth == act->loop_father->depth)
 886           cloop = act->loop_father;
 887         else
 888           cloop = act->loop_father->pred[depth];
 889         n_edges[cloop->num + last_basic_block]++;
 890       }
 891
 892   for (i = 0; i < last_basic_block + loops->num; i++)
 893     {
 894       edges[i] = xmalloc (n_edges[i] * sizeof (edge));
 895       n_edges[i] = 0;
 896     }
 897
 898   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 899     for (e = act->succ; e; e = e->succ_next)
 900       {
 901         if (e->dest == EXIT_BLOCK_PTR)
 902           continue;
 903         if (e->dest->loop_father->header == e->dest
 904             && e->dest->loop_father->latch == act)
 905           continue;
 906         if (act->loop_father == e->dest->loop_father
 907             || act->loop_father == e->dest->loop_father->outer)
 908           {
 909             edges[act->index + 1][n_edges[act->index + 1]++] = e;
 910             continue;
 911           }
 912         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
 913         if (depth == act->loop_father->depth)
 914           cloop = act->loop_father;
 915         else
 916           cloop = act->loop_father->pred[depth];
 917         i = cloop->num + last_basic_block;
 918         edges[i][n_edges[i]++] = e;
 919       }
 920
 921   /* Compute dfs numbering, starting from loop headers, and mark found
 922      loops.*/
 923   tick = 0;
 924   for (i = 0; i < last_basic_block + loops->num; i++)
 925     {
 926       dfs_in[i] = -1;
 927       closed[i] = 0;
 928       mr[i] = last_basic_block + loops->num;
 929       mri[i] = -1;
 930     }
 931
 932   stack_top = 0;
 933   for (i = 0; i < loops->num; i++)
 934     if (loops->parray[i])
 935       {
 936         stack[stack_top] = loops->parray[i]->header->index + 1;
 937         estack[stack_top] = NULL;
 938         stack_top++;
 939       }
 940
 941   while (stack_top)
 942     {
 943       int idx, sidx;
 944
 945       idx = stack[stack_top - 1];
 946       if (dfs_in[idx] < 0)
 947         dfs_in[idx] = tick++;
 948
 949       while (n_edges[idx])
 950         {
 951           e = edges[idx][--n_edges[idx]];
 952           sidx = e->dest->loop_father->header == e->dest
 953                    ? e->dest->loop_father->num + last_basic_block
 954                    : e->dest->index + 1;
 955           if (closed[sidx])
 956             {
 957               if (!closed[mri[sidx]])
 958                 {
 959                   if (mr[sidx] < mr[idx])
 960                     {
 961                       mr[idx] = mr[sidx];
 962                       mri[idx] = mri[sidx];
 963                     }
 964
 965                   if (mr[sidx] <= dfs_in[idx])
 966                     e->flags |= EDGE_IRREDUCIBLE_LOOP;
 967                 }
 968               continue;
 969             }
 970           if (dfs_in[sidx] < 0)
 971             {
 972               stack[stack_top] = sidx;
 973               estack[stack_top] = e;
 974               stack_top++;
 975               goto next;
 976             }
 977           if (dfs_in[sidx] < mr[idx])
 978             {
 979               mr[idx] = dfs_in[sidx];
 980               mri[idx] = sidx;
 981             }
 982           e->flags |= EDGE_IRREDUCIBLE_LOOP;
 983         }
 984
 985       /* Return back.  */
 986       closed[idx] = 1;
 987       e = estack[stack_top - 1];
 988       stack_top--;
 989       if (e)
 990         {
 991           /* Propagate information back.  */
 992           sidx = stack[stack_top - 1];
 993           if (mr[sidx] > mr[idx])
 994             {
 995               mr[sidx] = mr[idx];
 996               mri[sidx] = mri[idx];
 997             }
 998           if (mr[idx] <= dfs_in[sidx])
 999             e->flags |= EDGE_IRREDUCIBLE_LOOP;
1000         }
1001       /* Mark the block if relevant.  */
1002       if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
1003         BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
1004 next:;
1005     }
1006
1007   free (stack);
1008   free (estack);
1009   free (dfs_in);
1010   free (closed);
1011   free (mr);
1012   free (mri);
1013   for (i = 0; i < last_basic_block + loops->num; i++)
1014     free (edges[i]);
1015   free (edges);
1016   free (n_edges);
1017   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
1018 }
1019
1020 /* Counts number of insns inside LOOP.  */
1021 int
1022 num_loop_insns (loop)
1023      struct loop *loop;
1024 {
1025   basic_block *bbs, bb;
1026   unsigned i, ninsns = 0;
1027   rtx insn;
1028
1029   bbs = get_loop_body (loop);
1030   for (i = 0; i < loop->num_nodes; i++)
1031     {
1032       bb = bbs[i];
1033       ninsns++;
1034       for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
1035         if (INSN_P (insn))
1036           ninsns++;
1037     }
1038   free(bbs);
1039
1040   return ninsns;
1041 }
1042
1043 /* Counts number of insns executed on average per iteration LOOP.  */
1044 int
1045 average_num_loop_insns (loop)
1046      struct loop *loop;
1047 {
1048   basic_block *bbs, bb;
1049   unsigned i, binsns, ninsns, ratio;
1050   rtx insn;
1051
1052   ninsns = 0;
1053   bbs = get_loop_body (loop);
1054   for (i = 0; i < loop->num_nodes; i++)
1055     {
1056       bb = bbs[i];
1057
1058       binsns = 1;
1059       for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
1060         if (INSN_P (insn))
1061           binsns++;
1062
1063       ratio = loop->header->frequency == 0
1064               ? BB_FREQ_MAX
1065               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
1066       ninsns += binsns * ratio;
1067     }
1068   free(bbs);
1069
1070   ninsns /= BB_FREQ_MAX;
1071   if (!ninsns)
1072     ninsns = 1; /* To avoid division by zero.  */
1073
1074   return ninsns;
1075 }
1076
1077 /* Returns expected number of LOOP iterations.
1078    Compute upper bound on number of iterations in case they do not fit integer
1079    to help loop peeling heuristics.  Use exact counts if at all possible.  */
1080 unsigned
1081 expected_loop_iterations (loop)
1082      const struct loop *loop;
1083 {
1084   edge e;
1085
1086   if (loop->header->count)
1087     {
1088       gcov_type count_in, count_latch, expected;
1089
1090       count_in = 0;
1091       count_latch = 0;
1092
1093       for (e = loop->header->pred; e; e = e->pred_next)
1094         if (e->src == loop->latch)
1095           count_latch = e->count;
1096         else
1097           count_in += e->count;
1098
1099       if (count_in == 0)
1100         return 0;
1101
1102       expected = (count_latch + count_in - 1) / count_in;
1103
1104       /* Avoid overflows.  */
1105       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
1106     }
1107   else
1108     {
1109       int freq_in, freq_latch;
1110
1111       freq_in = 0;
1112       freq_latch = 0;
1113
1114       for (e = loop->header->pred; e; e = e->pred_next)
1115         if (e->src == loop->latch)
1116           freq_latch = EDGE_FREQUENCY (e);
1117         else
1118           freq_in += EDGE_FREQUENCY (e);
1119
1120       if (freq_in == 0)
1121         return 0;
1122
1123       return (freq_latch + freq_in - 1) / freq_in;
1124     }
1125 }