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       fprintf (rtl_dump_file, HOST_WIDE_INT_PRINT_UNSIGNED, iter);
 653       fprintf (rtl_dump_file, "th iteration: ");
 654       print_simple_rtl (rtl_dump_file, exp);
 655       fprintf (rtl_dump_file, "\n");
 656     }
 657   return exp;
 658 }
 659
 660
 661 /* Tests whether exit at EXIT_EDGE from LOOP is simple.  Returns simple loop
 662    description joined to it in in DESC.  INVARIANT_REGS and SINGLE_SET_REGS
 663    are results of blocks_{invariant,single_set}_regs over BODY.  */
 664 static bool
 665 simple_loop_exit_p (loops, loop, exit_edge, invariant_regs, single_set_regs, desc)
 666      struct loops *loops;
 667      struct loop *loop;
 668      edge exit_edge;
 669      struct loop_desc *desc;
 670      regset invariant_regs;
 671      rtx *single_set_regs;
 672 {
 673   basic_block mod_bb, exit_bb;
 674   int fallthru_out;
 675   rtx condition;
 676   edge ei, e;
 677
 678   exit_bb = exit_edge->src;
 679
 680   fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
 681
 682   if (!exit_bb)
 683     return false;
 684
 685   /* It must be tested (at least) once during any iteration.  */
 686   if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
 687     return false;
 688
 689   /* It must end in a simple conditional jump.  */
 690   if (!any_condjump_p (exit_bb->end))
 691     return false;
 692
 693   ei = exit_bb->succ;
 694   if (ei == exit_edge)
 695     ei = ei->succ_next;
 696
 697   desc->out_edge = exit_edge;
 698   desc->in_edge = ei;
 699
 700   /* Condition must be a simple comparison in that one of operands
 701      is register and the other one is invariant.  */
 702   if (!(condition = get_condition (exit_bb->end, NULL)))
 703     return false;
 704
 705   if (!simple_condition_p (loop, condition, invariant_regs, desc))
 706     return false;
 707
 708   /*  Var must be simply incremented or decremented in exactly one insn that
 709      is executed just once every iteration.  */
 710   if (!(mod_bb = simple_increment (loops, loop, single_set_regs, desc)))
 711     return false;
 712
 713   /* OK, it is simple loop.  Now just fill in remaining info.  */
 714   desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
 715   desc->neg = !fallthru_out;
 716
 717   /* Find initial value of var and alternative values for lim.  */
 718   e = loop_preheader_edge (loop);
 719   desc->var_alts = variable_initial_values (e, desc->var);
 720   desc->lim_alts = variable_initial_values (e, desc->lim);
 721
 722   /* Number of iterations.  */
 723   if (!count_loop_iterations (desc, NULL, NULL))
 724     return false;
 725   desc->const_iter =
 726     constant_iterations (desc, &desc->niter, &desc->may_be_zero);
 727   return true;
 728 }
 729
 730 /* Tests whether LOOP is simple for loop.  Returns simple loop description
 731    in DESC.  */
 732 bool
 733 simple_loop_p (loops, loop, desc)
 734      struct loops *loops;
 735      struct loop *loop;
 736      struct loop_desc *desc;
 737 {
 738   unsigned i;
 739   basic_block *body;
 740   edge e;
 741   struct loop_desc act;
 742   bool any = false;
 743   regset invariant_regs;
 744   regset_head invariant_regs_head;
 745   rtx *single_set_regs;
 746   int n_branches;
 747
 748   body = get_loop_body (loop);
 749
 750   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
 751   single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
 752
 753   blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
 754   blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
 755
 756   n_branches = 0;
 757   for (i = 0; i < loop->num_nodes; i++)
 758     {
 759       for (e = body[i]->succ; e; e = e->succ_next)
 760         if (!flow_bb_inside_loop_p (loop, e->dest)
 761             && simple_loop_exit_p (loops, loop, e,
 762                    invariant_regs, single_set_regs, &act))
 763           {
 764             /* Prefer constant iterations; the less the better.  */
 765             if (!any)
 766               any = true;
 767             else if (!act.const_iter
 768                      || (desc->const_iter && act.niter >= desc->niter))
 769               continue;
 770             *desc = act;
 771           }
 772
 773       if (body[i]->succ && body[i]->succ->succ_next)
 774         n_branches++;
 775     }
 776   desc->n_branches = n_branches;
 777
 778   if (rtl_dump_file && any)
 779     {
 780       fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
 781       if (desc->postincr)
 782         fprintf (rtl_dump_file,
 783                  ";  does postincrement after loop exit condition\n");
 784
 785       fprintf (rtl_dump_file, ";  Induction variable:");
 786       print_simple_rtl (rtl_dump_file, desc->var);
 787       fputc ('\n', rtl_dump_file);
 788
 789       fprintf (rtl_dump_file, ";  Initial values:");
 790       print_simple_rtl (rtl_dump_file, desc->var_alts);
 791       fputc ('\n', rtl_dump_file);
 792
 793       fprintf (rtl_dump_file, ";  Stride:");
 794       print_simple_rtl (rtl_dump_file, desc->stride);
 795       fputc ('\n', rtl_dump_file);
 796
 797       fprintf (rtl_dump_file, ";  Compared with:");
 798       print_simple_rtl (rtl_dump_file, desc->lim);
 799       fputc ('\n', rtl_dump_file);
 800
 801       fprintf (rtl_dump_file, ";  Alternative values:");
 802       print_simple_rtl (rtl_dump_file, desc->lim_alts);
 803       fputc ('\n', rtl_dump_file);
 804
 805       fprintf (rtl_dump_file, ";  Exit condition:");
 806       if (desc->neg)
 807         fprintf (rtl_dump_file, "(negated)");
 808       fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
 809
 810       fprintf (rtl_dump_file, ";  Number of branches:");
 811       fprintf (rtl_dump_file, "%d\n", desc->n_branches);
 812
 813       fputc ('\n', rtl_dump_file);
 814     }
 815
 816   free (body);
 817   FREE_REG_SET (invariant_regs);
 818   free (single_set_regs);
 819   return any;
 820 }
 821
 822 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
 823    throw away all latch edges and mark blocks inside any remaining cycle.
 824    Everything is a bit complicated due to fact we do not want to do this
 825    for parts of cycles that only "pass" through some loop -- i.e. for
 826    each cycle, we want to mark blocks that belong directly to innermost
 827    loop containing the whole cycle.  */
 828 void
 829 mark_irreducible_loops (loops)
 830      struct loops *loops;
 831 {
 832   int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
 833   unsigned i;
 834   edge **edges, e;
 835   edge *estack;
 836   basic_block act;
 837   int stack_top, tick, depth;
 838   struct loop *cloop;
 839
 840   /* Reset the flags.  */
 841   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 842     {
 843       act->flags &= ~BB_IRREDUCIBLE_LOOP;
 844       for (e = act->succ; e; e = e->succ_next)
 845         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 846     }
 847
 848   /* The first last_basic_block + 1 entries are for real blocks (including
 849      entry); then we have loops->num - 1 fake blocks for loops to that we
 850      assign edges leading from loops (fake loop 0 is not interesting).  */
 851   dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 852   closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 853   mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 854   mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 855   n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
 856   edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
 857   stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
 858   estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
 859
 860   /* Create the edge lists.  */
 861   for (i = 0; i < last_basic_block + loops->num; i++)
 862     n_edges[i] = 0;
 863   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 864     for (e = act->succ; e; e = e->succ_next)
 865       {
 866         /* Ignore edges to exit.  */
 867         if (e->dest == EXIT_BLOCK_PTR)
 868           continue;
 869         /* And latch edges.  */
 870         if (e->dest->loop_father->header == e->dest
 871             && e->dest->loop_father->latch == act)
 872           continue;
 873         /* Edges inside a single loop should be left where they are.  Edges
 874            to subloop headers should lead to representative of the subloop,
 875            but from the same place.  */
 876         if (act->loop_father == e->dest->loop_father
 877             || act->loop_father == e->dest->loop_father->outer)
 878           {
 879             n_edges[act->index + 1]++;
 880             continue;
 881           }
 882         /* Edges exiting loops remain.  They should lead from representative
 883            of the son of nearest common ancestor of the loops in that
 884            act lays.  */
 885         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
 886         if (depth == act->loop_father->depth)
 887           cloop = act->loop_father;
 888         else
 889           cloop = act->loop_father->pred[depth];
 890         n_edges[cloop->num + last_basic_block]++;
 891       }
 892
 893   for (i = 0; i < last_basic_block + loops->num; i++)
 894     {
 895       edges[i] = xmalloc (n_edges[i] * sizeof (edge));
 896       n_edges[i] = 0;
 897     }
 898
 899   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 900     for (e = act->succ; e; e = e->succ_next)
 901       {
 902         if (e->dest == EXIT_BLOCK_PTR)
 903           continue;
 904         if (e->dest->loop_father->header == e->dest
 905             && e->dest->loop_father->latch == act)
 906           continue;
 907         if (act->loop_father == e->dest->loop_father
 908             || act->loop_father == e->dest->loop_father->outer)
 909           {
 910             edges[act->index + 1][n_edges[act->index + 1]++] = e;
 911             continue;
 912           }
 913         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
 914         if (depth == act->loop_father->depth)
 915           cloop = act->loop_father;
 916         else
 917           cloop = act->loop_father->pred[depth];
 918         i = cloop->num + last_basic_block;
 919         edges[i][n_edges[i]++] = e;
 920       }
 921
 922   /* Compute dfs numbering, starting from loop headers, and mark found
 923      loops.*/
 924   tick = 0;
 925   for (i = 0; i < last_basic_block + loops->num; i++)
 926     {
 927       dfs_in[i] = -1;
 928       closed[i] = 0;
 929       mr[i] = last_basic_block + loops->num;
 930       mri[i] = -1;
 931     }
 932
 933   stack_top = 0;
 934   for (i = 0; i < loops->num; i++)
 935     if (loops->parray[i])
 936       {
 937         stack[stack_top] = loops->parray[i]->header->index + 1;
 938         estack[stack_top] = NULL;
 939         stack_top++;
 940       }
 941
 942   while (stack_top)
 943     {
 944       int idx, sidx;
 945
 946       idx = stack[stack_top - 1];
 947       if (dfs_in[idx] < 0)
 948         dfs_in[idx] = tick++;
 949
 950       while (n_edges[idx])
 951         {
 952           e = edges[idx][--n_edges[idx]];
 953           sidx = e->dest->loop_father->header == e->dest
 954                    ? e->dest->loop_father->num + last_basic_block
 955                    : e->dest->index + 1;
 956           if (closed[sidx])
 957             {
 958               if (!closed[mri[sidx]])
 959                 {
 960                   if (mr[sidx] < mr[idx])
 961                     {
 962                       mr[idx] = mr[sidx];
 963                       mri[idx] = mri[sidx];
 964                     }
 965
 966                   if (mr[sidx] <= dfs_in[idx])
 967                     e->flags |= EDGE_IRREDUCIBLE_LOOP;
 968                 }
 969               continue;
 970             }
 971           if (dfs_in[sidx] < 0)
 972             {
 973               stack[stack_top] = sidx;
 974               estack[stack_top] = e;
 975               stack_top++;
 976               goto next;
 977             }
 978           if (dfs_in[sidx] < mr[idx])
 979             {
 980               mr[idx] = dfs_in[sidx];
 981               mri[idx] = sidx;
 982             }
 983           e->flags |= EDGE_IRREDUCIBLE_LOOP;
 984         }
 985
 986       /* Return back.  */
 987       closed[idx] = 1;
 988       e = estack[stack_top - 1];
 989       stack_top--;
 990       if (e)
 991         {
 992           /* Propagate information back.  */
 993           sidx = stack[stack_top - 1];
 994           if (mr[sidx] > mr[idx])
 995             {
 996               mr[sidx] = mr[idx];
 997               mri[sidx] = mri[idx];
 998             }
 999           if (mr[idx] <= dfs_in[sidx])
1000             e->flags |= EDGE_IRREDUCIBLE_LOOP;
1001         }
1002       /* Mark the block if relevant.  */
1003       if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
1004         BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
1005 next:;
1006     }
1007
1008   free (stack);
1009   free (estack);
1010   free (dfs_in);
1011   free (closed);
1012   free (mr);
1013   free (mri);
1014   for (i = 0; i < last_basic_block + loops->num; i++)
1015     free (edges[i]);
1016   free (edges);
1017   free (n_edges);
1018   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
1019 }
1020
1021 /* Counts number of insns inside LOOP.  */
1022 int
1023 num_loop_insns (loop)
1024      struct loop *loop;
1025 {
1026   basic_block *bbs, bb;
1027   unsigned i, ninsns = 0;
1028   rtx insn;
1029
1030   bbs = get_loop_body (loop);
1031   for (i = 0; i < loop->num_nodes; i++)
1032     {
1033       bb = bbs[i];
1034       ninsns++;
1035       for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (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         binsns++;
1061
1062       ratio = loop->header->frequency == 0
1063               ? BB_FREQ_MAX
1064               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
1065       ninsns += binsns * ratio;
1066     }
1067   free(bbs);
1068
1069   ninsns /= BB_FREQ_MAX;
1070   if (!ninsns)
1071     ninsns = 1; /* To avoid division by zero.  */
1072
1073   return ninsns;
1074 }
1075
1076 /* Returns expected number of LOOP iterations.
1077    Compute upper bound on number of iterations in case they do not fit integer
1078    to help loop peeling heuristics.  Use exact counts if at all possible.  */
1079 unsigned
1080 expected_loop_iterations (loop)
1081      const struct loop *loop;
1082 {
1083   edge e;
1084
1085   if (loop->header->count)
1086     {
1087       gcov_type count_in, count_latch, expected;
1088
1089       count_in = 0;
1090       count_latch = 0;
1091
1092       for (e = loop->header->pred; e; e = e->pred_next)
1093         if (e->src == loop->latch)
1094           count_latch = e->count;
1095         else
1096           count_in += e->count;
1097
1098       if (count_in == 0)
1099         return 0;
1100
1101       expected = (count_latch + count_in - 1) / count_in;
1102
1103       /* Avoid overflows.  */
1104       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
1105     }
1106   else
1107     {
1108       int freq_in, freq_latch;
1109
1110       freq_in = 0;
1111       freq_latch = 0;
1112
1113       for (e = loop->header->pred; e; e = e->pred_next)
1114         if (e->src == loop->latch)
1115           freq_latch = EDGE_FREQUENCY (e);
1116         else
1117           freq_in += EDGE_FREQUENCY (e);
1118
1119       if (freq_in == 0)
1120         return 0;
1121
1122       return (freq_latch + freq_in - 1) / freq_in;
1123     }
1124 }