gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004 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 (rtx, rtx, regset);
  34 static void blocks_invariant_registers (basic_block *, int, regset);
  35 static void unmark_altered_insn (rtx, rtx, struct unmark_altered_insn_data *);
  36 static void blocks_single_set_registers (basic_block *, int, rtx *);
  37 static int invariant_rtx_wrto_regs_p_helper (rtx *, regset);
  38 static bool invariant_rtx_wrto_regs_p (rtx, regset);
  39 static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
  40 static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
  41                                  bool *);
  42 static bool simple_loop_exit_p (struct loop *, edge, regset,
  43                                 rtx *, struct loop_desc *);
  44 static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
  45 static rtx variable_initial_values (edge, rtx, enum machine_mode);
  46 static bool simple_condition_p (struct loop *, rtx, regset,
  47                                 struct loop_desc *);
  48 static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
  49 static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
  50                                           int, rtx, enum machine_mode,
  51                                           enum machine_mode);
  52 static unsigned HOST_WIDEST_INT inverse (unsigned HOST_WIDEST_INT, int);
  53 static bool fits_in_mode_p (enum machine_mode mode, rtx expr);
  54
  55 /* Computes inverse to X modulo (1 << MOD).  */
  56 static unsigned HOST_WIDEST_INT
  57 inverse (unsigned HOST_WIDEST_INT x, int mod)
  58 {
  59   unsigned HOST_WIDEST_INT mask =
  60           ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
  61   unsigned HOST_WIDEST_INT rslt = 1;
  62   int i;
  63
  64   for (i = 0; i < mod - 1; i++)
  65     {
  66       rslt = (rslt * x) & mask;
  67       x = (x * x) & mask;
  68     }
  69
  70   return rslt;
  71 }
  72
  73 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  74 bool
  75 just_once_each_iteration_p (struct loop *loop, basic_block bb)
  76 {
  77   /* It must be executed at least once each iteration.  */
  78   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
  79     return false;
  80
  81   /* And just once.  */
  82   if (bb->loop_father != loop)
  83     return false;
  84
  85   /* But this was not enough.  We might have some irreducible loop here.  */
  86   if (bb->flags & BB_IRREDUCIBLE_LOOP)
  87     return false;
  88
  89   return true;
  90 }
  91
  92
  93 /* Unmarks modified registers; helper to blocks_invariant_registers.  */
  94 static void
  95 unmark_altered (rtx what, rtx by ATTRIBUTE_UNUSED, regset regs)
  96 {
  97   if (GET_CODE (what) == SUBREG)
  98     what = SUBREG_REG (what);
  99   if (!REG_P (what))
 100     return;
 101   CLEAR_REGNO_REG_SET (regs, REGNO (what));
 102 }
 103
 104 /* Marks registers that are invariant inside blocks BBS.  */
 105 static void
 106 blocks_invariant_registers (basic_block *bbs, int nbbs, regset regs)
 107 {
 108   rtx insn;
 109   int i;
 110
 111   for (i = 0; i < max_reg_num (); i++)
 112     SET_REGNO_REG_SET (regs, i);
 113   for (i = 0; i < nbbs; i++)
 114     for (insn = BB_HEAD (bbs[i]);
 115          insn != NEXT_INSN (BB_END (bbs[i]));
 116          insn = NEXT_INSN (insn))
 117       if (INSN_P (insn))
 118         note_stores (PATTERN (insn),
 119                      (void (*) (rtx, rtx, void *)) unmark_altered,
 120                      regs);
 121 }
 122
 123 /* Unmarks modified registers; helper to blocks_single_set_registers.  */
 124 struct unmark_altered_insn_data
 125 {
 126   rtx *regs;
 127   rtx insn;
 128 };
 129
 130 static void
 131 unmark_altered_insn (rtx what, rtx by ATTRIBUTE_UNUSED,
 132                      struct unmark_altered_insn_data *data)
 133 {
 134   int rn;
 135
 136   if (GET_CODE (what) == SUBREG)
 137     what = SUBREG_REG (what);
 138   if (!REG_P (what))
 139     return;
 140   rn = REGNO (what);
 141   if (data->regs[rn] == data->insn)
 142     return;
 143   data->regs[rn] = NULL;
 144 }
 145
 146 /* Marks registers that have just single simple set in BBS; the relevant
 147    insn is returned in REGS.  */
 148 static void
 149 blocks_single_set_registers (basic_block *bbs, int nbbs, rtx *regs)
 150 {
 151   rtx insn;
 152   int i;
 153   struct unmark_altered_insn_data data;
 154
 155   for (i = 0; i < max_reg_num (); i++)
 156     regs[i] = NULL;
 157
 158   for (i = 0; i < nbbs; i++)
 159     for (insn = BB_HEAD (bbs[i]);
 160          insn != NEXT_INSN (BB_END (bbs[i]));
 161          insn = NEXT_INSN (insn))
 162       {
 163         rtx set = single_set (insn);
 164         if (!set)
 165           continue;
 166         if (!REG_P (SET_DEST (set)))
 167           continue;
 168         regs[REGNO (SET_DEST (set))] = insn;
 169       }
 170
 171   data.regs = regs;
 172   for (i = 0; i < nbbs; i++)
 173     for (insn = BB_HEAD (bbs[i]);
 174          insn != NEXT_INSN (BB_END (bbs[i]));
 175          insn = NEXT_INSN (insn))
 176       {
 177         if (!INSN_P (insn))
 178           continue;
 179         data.insn = insn;
 180         note_stores (PATTERN (insn),
 181             (void (*) (rtx, rtx, void *)) unmark_altered_insn,
 182             &data);
 183       }
 184 }
 185
 186 /* Helper for invariant_rtx_wrto_regs_p.  */
 187 static int
 188 invariant_rtx_wrto_regs_p_helper (rtx *expr, regset invariant_regs)
 189 {
 190   switch (GET_CODE (*expr))
 191     {
 192     case CC0:
 193     case PC:
 194     case UNSPEC_VOLATILE:
 195       return 1;
 196
 197     case CONST_INT:
 198     case CONST_DOUBLE:
 199     case CONST:
 200     case SYMBOL_REF:
 201     case LABEL_REF:
 202       return 0;
 203
 204     case ASM_OPERANDS:
 205       return MEM_VOLATILE_P (*expr);
 206
 207     case MEM:
 208       /* If the memory is not constant, assume it is modified.  If it is
 209          constant, we still have to check the address.  */
 210       return !RTX_UNCHANGING_P (*expr);
 211
 212     case REG:
 213       return !REGNO_REG_SET_P (invariant_regs, REGNO (*expr));
 214
 215     default:
 216       return 0;
 217     }
 218 }
 219
 220 /* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant.  */
 221 static bool
 222 invariant_rtx_wrto_regs_p (rtx expr, regset invariant_regs)
 223 {
 224   return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper,
 225                         invariant_regs);
 226 }
 227
 228 /* Checks whether CONDITION is a simple comparison in that one of operands
 229    is register and the other one is invariant in the LOOP. Fills var, lim
 230    and cond fields in DESC.  */
 231 static bool
 232 simple_condition_p (struct loop *loop ATTRIBUTE_UNUSED, rtx condition,
 233                     regset invariant_regs, struct loop_desc *desc)
 234 {
 235   rtx op0, op1;
 236
 237   /* Check condition.  */
 238   switch (GET_CODE (condition))
 239     {
 240       case EQ:
 241       case NE:
 242       case LE:
 243       case LT:
 244       case GE:
 245       case GT:
 246       case GEU:
 247       case GTU:
 248       case LEU:
 249       case LTU:
 250         break;
 251       default:
 252         return false;
 253     }
 254
 255   /* Of integers or pointers.  */
 256   if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
 257       && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
 258     return false;
 259
 260   /* One of operands must be a simple register.  */
 261   op0 = XEXP (condition, 0);
 262   op1 = XEXP (condition, 1);
 263
 264   /* One of operands must be invariant.  */
 265   if (invariant_rtx_wrto_regs_p (op0, invariant_regs))
 266     {
 267       /* And the other one must be a register.  */
 268       if (!REG_P (op1))
 269         return false;
 270       desc->var = op1;
 271       desc->lim = op0;
 272
 273       desc->cond = swap_condition (GET_CODE (condition));
 274       if (desc->cond == UNKNOWN)
 275         return false;
 276       return true;
 277     }
 278
 279   /* Check the other operand.  */
 280   if (!invariant_rtx_wrto_regs_p (op1, invariant_regs))
 281     return false;
 282   if (!REG_P (op0))
 283     return false;
 284
 285   desc->var = op0;
 286   desc->lim = op1;
 287
 288   desc->cond = GET_CODE (condition);
 289
 290   return true;
 291 }
 292
 293 /* Checks whether DESC->var is incremented/decremented exactly once each
 294    iteration.  Fills in DESC->stride and returns block in that DESC->var is
 295    modified.  */
 296 static basic_block
 297 simple_increment (struct loop *loop, rtx *simple_increment_regs,
 298                   struct loop_desc *desc)
 299 {
 300   rtx mod_insn, mod_insn1, set, set_src, set_add;
 301   basic_block mod_bb, mod_bb1;
 302
 303   /* Find insn that modifies var.  */
 304   mod_insn = simple_increment_regs[REGNO (desc->var)];
 305   if (!mod_insn)
 306     return NULL;
 307   mod_bb = BLOCK_FOR_INSN (mod_insn);
 308
 309   /* Check that it is executed exactly once each iteration.  */
 310   if (!just_once_each_iteration_p (loop, mod_bb))
 311     return NULL;
 312
 313   /* mod_insn must be a simple increment/decrement.  */
 314   set = single_set (mod_insn);
 315   if (!set)
 316     abort ();
 317   if (!rtx_equal_p (SET_DEST (set), desc->var))
 318     abort ();
 319
 320   set_src = find_reg_equal_equiv_note (mod_insn);
 321   if (!set_src)
 322     set_src = SET_SRC (set);
 323
 324   /* Check for variables that iterate in narrower mode.  */
 325   if (GET_CODE (set_src) == SIGN_EXTEND
 326       || GET_CODE (set_src) == ZERO_EXTEND)
 327     {
 328       /* If we are sign extending variable that is then compared unsigned
 329          or vice versa, there is something weird happening.  */
 330       if (desc->cond != EQ
 331           && desc->cond != NE
 332           && ((desc->cond == LEU
 333                || desc->cond == LTU
 334                || desc->cond == GEU
 335                || desc->cond == GTU)
 336               ^ (GET_CODE (set_src) == ZERO_EXTEND)))
 337         return NULL;
 338
 339       if (GET_CODE (XEXP (set_src, 0)) != SUBREG
 340           || SUBREG_BYTE (XEXP (set_src, 0)) != 0
 341           || GET_MODE (SUBREG_REG (XEXP (set_src, 0))) != GET_MODE (desc->var))
 342         return NULL;
 343
 344       desc->inner_mode = GET_MODE (XEXP (set_src, 0));
 345       desc->extend = GET_CODE (set_src);
 346       set_src = SUBREG_REG (XEXP (set_src, 0));
 347
 348       if (GET_CODE (set_src) != REG)
 349         return NULL;
 350
 351       /* Find where the reg is set.  */
 352       mod_insn1 = simple_increment_regs[REGNO (set_src)];
 353       if (!mod_insn1)
 354         return NULL;
 355
 356       mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
 357       if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
 358         return NULL;
 359       if (mod_bb1 == mod_bb)
 360         {
 361           for (;
 362                mod_insn != PREV_INSN (BB_HEAD (mod_bb));
 363                mod_insn = PREV_INSN (mod_insn))
 364             if (mod_insn == mod_insn1)
 365               break;
 366
 367           if (mod_insn == PREV_INSN (BB_HEAD (mod_bb)))
 368             return NULL;
 369         }
 370
 371       /* Replace the source with the possible place of increment.  */
 372       set = single_set (mod_insn1);
 373       if (!set)
 374         abort ();
 375       if (!rtx_equal_p (SET_DEST (set), set_src))
 376         abort ();
 377
 378       set_src = find_reg_equal_equiv_note (mod_insn1);
 379       if (!set_src)
 380         set_src = SET_SRC (set);
 381     }
 382   else
 383     {
 384       desc->inner_mode = GET_MODE (desc->var);
 385       desc->extend = NIL;
 386     }
 387
 388   if (GET_CODE (set_src) != PLUS)
 389     return NULL;
 390   if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
 391     return NULL;
 392
 393   /* Set desc->stride.  */
 394   set_add = XEXP (set_src, 1);
 395   if (CONSTANT_P (set_add))
 396     desc->stride = set_add;
 397   else
 398     return NULL;
 399
 400   return mod_bb;
 401 }
 402
 403 /* Tries to find initial value of VAR in INSN.  This value must be invariant
 404    wrto INVARIANT_REGS.  If SET_INSN is not NULL, insn in that var is set is
 405    placed here.  INNER_MODE is mode in that induction variable VAR iterates.  */
 406 static rtx
 407 variable_initial_value (rtx insn, regset invariant_regs,
 408                         rtx var, rtx *set_insn, enum machine_mode inner_mode)
 409 {
 410   basic_block bb;
 411   rtx set;
 412   rtx ret = NULL;
 413
 414   /* Go back through cfg.  */
 415   bb = BLOCK_FOR_INSN (insn);
 416   while (1)
 417     {
 418       for (; insn != BB_HEAD (bb); insn = PREV_INSN (insn))
 419         {
 420           if (INSN_P (insn))
 421             note_stores (PATTERN (insn),
 422                 (void (*) (rtx, rtx, void *)) unmark_altered,
 423                 invariant_regs);
 424           if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
 425             break;
 426         }
 427
 428       if (insn != BB_HEAD (bb))
 429         {
 430           /* We found place where var is set.  */
 431           rtx set_dest;
 432           rtx val;
 433           rtx note;
 434
 435           set = single_set (insn);
 436           if (!set)
 437             return NULL;
 438           set_dest = SET_DEST (set);
 439           if (!rtx_equal_p (set_dest, var))
 440             return NULL;
 441
 442           note = find_reg_equal_equiv_note (insn);
 443           if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
 444             val = XEXP (note, 0);
 445           else
 446             val = SET_SRC (set);
 447
 448           /* If we know that the initial value is indeed in range of
 449              the inner mode, record the fact even in case the value itself
 450              is useless.  */
 451           if ((GET_CODE (val) == SIGN_EXTEND
 452                || GET_CODE (val) == ZERO_EXTEND)
 453               && GET_MODE (XEXP (val, 0)) == inner_mode)
 454             ret = gen_rtx_fmt_e (GET_CODE (val),
 455                                  GET_MODE (var),
 456                                  gen_rtx_fmt_ei (SUBREG,
 457                                                  inner_mode,
 458                                                  var, 0));
 459
 460           if (!invariant_rtx_wrto_regs_p (val, invariant_regs))
 461             return ret;
 462
 463           if (set_insn)
 464             *set_insn = insn;
 465           return val;
 466         }
 467
 468
 469       if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
 470         return NULL;
 471
 472       bb = bb->pred->src;
 473       insn = BB_END (bb);
 474     }
 475
 476   return NULL;
 477 }
 478
 479 /* Returns list of definitions of initial value of VAR at edge E.  INNER_MODE
 480    is mode in that induction variable VAR really iterates.  */
 481 static rtx
 482 variable_initial_values (edge e, rtx var, enum machine_mode inner_mode)
 483 {
 484   rtx set_insn, list;
 485   regset invariant_regs;
 486   regset_head invariant_regs_head;
 487   int i;
 488
 489   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
 490   for (i = 0; i < max_reg_num (); i++)
 491     SET_REGNO_REG_SET (invariant_regs, i);
 492
 493   list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
 494
 495   if (e->src == ENTRY_BLOCK_PTR)
 496     return list;
 497
 498   set_insn = BB_END (e->src);
 499   while (REG_P (var)
 500          && (var = variable_initial_value (set_insn, invariant_regs, var,
 501                                            &set_insn, inner_mode)))
 502     list = alloc_EXPR_LIST (0, copy_rtx (var), list);
 503
 504   FREE_REG_SET (invariant_regs);
 505   return list;
 506 }
 507
 508 /* Counts constant number of iterations of the loop described by DESC;
 509    returns false if impossible.  */
 510 static bool
 511 constant_iterations (struct loop_desc *desc, unsigned HOST_WIDE_INT *niter,
 512                      bool *may_be_zero)
 513 {
 514   rtx test, expr;
 515   rtx ainit, alim;
 516
 517   test = test_for_iteration (desc, 0);
 518   if (test == const0_rtx)
 519     {
 520       *niter = 0;
 521       *may_be_zero = false;
 522       return true;
 523     }
 524
 525   *may_be_zero = (test != const_true_rtx);
 526
 527   /* It would make a little sense to check every with every when we
 528      know that all but the first alternative are simply registers.  */
 529   for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
 530     {
 531       alim = XEXP (desc->lim_alts, 0);
 532       if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
 533         continue;
 534       if (GET_CODE (expr) == CONST_INT)
 535         {
 536           *niter = INTVAL (expr);
 537           return true;
 538         }
 539     }
 540   for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
 541     {
 542       ainit = XEXP (desc->var_alts, 0);
 543       if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
 544         continue;
 545       if (GET_CODE (expr) == CONST_INT)
 546         {
 547           *niter = INTVAL (expr);
 548           return true;
 549         }
 550     }
 551
 552   return false;
 553 }
 554
 555 /* Attempts to determine a number of iterations of a "strange" loop.
 556    Its induction variable starts with value INIT, is compared by COND
 557    with LIM.  If POSTINCR, it is incremented after the test.  It is incremented
 558    by STRIDE each iteration, has mode MODE but iterates in INNER_MODE.
 559
 560    By "strange" we mean loops where induction variable increases in the wrong
 561    direction wrto comparison, i.e. for (i = 6; i > 5; i++).  */
 562 static rtx
 563 count_strange_loop_iterations (rtx init, rtx lim, enum rtx_code cond,
 564                                int postincr, rtx stride, enum machine_mode mode,
 565                                enum machine_mode inner_mode)
 566 {
 567   rtx rqmt, n_to_wrap, before_wrap, after_wrap;
 568   rtx mode_min, mode_max;
 569   int size;
 570
 571   /* This could be handled, but it is not important enough to lose time with
 572      it just now.  */
 573   if (mode != inner_mode)
 574     return NULL_RTX;
 575
 576   if (!postincr)
 577     init = simplify_gen_binary (PLUS, mode, init, stride);
 578
 579   /* If we are able to prove that we don't pass the first test, we are
 580      done.  */
 581   rqmt = simplify_relational_operation (cond, mode, init, lim);
 582   if (rqmt == const0_rtx)
 583     return const0_rtx;
 584
 585   /* And if we don't know we pass it, the things are too complicated for us.  */
 586   if (rqmt != const_true_rtx)
 587     return NULL_RTX;
 588
 589   switch (cond)
 590     {
 591     case GE:
 592     case GT:
 593     case LE:
 594     case LT:
 595       size = GET_MODE_BITSIZE (mode);
 596       mode_min = GEN_INT (-((unsigned HOST_WIDEST_INT) 1 << (size - 1)));
 597       mode_max = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1)) - 1);
 598
 599       break;
 600
 601     case GEU:
 602     case GTU:
 603     case LEU:
 604     case LTU:
 605     case EQ:
 606       mode_min = const0_rtx;
 607       mode_max = simplify_gen_binary (MINUS, mode, const0_rtx, const1_rtx);
 608       break;
 609
 610     default:
 611       abort ();
 612     }
 613
 614   switch (cond)
 615     {
 616     case EQ:
 617       /* This iterates once, as init == lim.  */
 618       return const1_rtx;
 619
 620       /* The behavior is undefined in signed cases.  Never mind, we still
 621          try to behave sanely.  */
 622     case GE:
 623     case GT:
 624     case GEU:
 625     case GTU:
 626       if (INTVAL (stride) <= 0)
 627         abort ();
 628       n_to_wrap = simplify_gen_binary (MINUS, mode, mode_max, copy_rtx (init));
 629       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
 630       before_wrap = simplify_gen_binary (MULT, mode,
 631                                          copy_rtx (n_to_wrap), stride);
 632       before_wrap = simplify_gen_binary (PLUS, mode,
 633                                          before_wrap, copy_rtx (init));
 634       after_wrap = simplify_gen_binary (PLUS, mode,
 635                                         before_wrap, stride);
 636       if (GET_CODE (after_wrap) != CONST_INT)
 637         {
 638           after_wrap = simplify_gen_binary (PLUS, mode, mode_min, stride);
 639           after_wrap = simplify_gen_binary (MINUS, mode, after_wrap, const1_rtx);
 640         }
 641       break;
 642
 643     case LE:
 644     case LT:
 645     case LEU:
 646     case LTU:
 647       if (INTVAL (stride) >= 0)
 648         abort ();
 649       stride = simplify_gen_unary (NEG, mode, stride, mode);
 650       n_to_wrap = simplify_gen_binary (MINUS, mode, copy_rtx (init), mode_min);
 651       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
 652       before_wrap = simplify_gen_binary (MULT, mode,
 653                                          copy_rtx (n_to_wrap), stride);
 654       before_wrap = simplify_gen_binary (MINUS, mode,
 655                                          copy_rtx (init), before_wrap);
 656       after_wrap = simplify_gen_binary (MINUS, mode,
 657                                         before_wrap, stride);
 658       if (GET_CODE (after_wrap) != CONST_INT)
 659         {
 660           after_wrap = simplify_gen_binary (MINUS, mode, mode_max, stride);
 661           after_wrap = simplify_gen_binary (PLUS, mode, after_wrap, const1_rtx);
 662         }
 663       break;
 664     default:
 665       abort ();
 666     }
 667
 668   /* If this is const_true_rtx and we did not take a conservative approximation
 669      of after_wrap above, we might iterate the calculation (but of course we
 670      would have to take care about infinite cases).  Ignore this for now.  */
 671   rqmt = simplify_relational_operation (cond, mode, after_wrap, lim);
 672   if (rqmt != const0_rtx)
 673     return NULL_RTX;
 674
 675   return simplify_gen_binary (PLUS, mode, n_to_wrap, const1_rtx);
 676 }
 677
 678 /* Checks whether value of EXPR fits into range of MODE.  */
 679 static bool
 680 fits_in_mode_p (enum machine_mode mode, rtx expr)
 681 {
 682   unsigned HOST_WIDEST_INT val;
 683   int n_bits = 0;
 684
 685   if (GET_CODE (expr) == CONST_INT)
 686     {
 687       for (val = INTVAL (expr); val; val >>= 1)
 688         n_bits++;
 689
 690       return n_bits <= GET_MODE_BITSIZE (mode);
 691     }
 692
 693   if (GET_CODE (expr) == SIGN_EXTEND
 694       || GET_CODE (expr) == ZERO_EXTEND)
 695     return GET_MODE (XEXP (expr, 0)) == mode;
 696
 697   return false;
 698 }
 699
 700 /* Return RTX expression representing number of iterations of loop as bounded
 701    by test described by DESC (in the case loop really has multiple exit
 702    edges, fewer iterations may happen in the practice).
 703
 704    Return NULL if it is unknown.  Additionally the value may be invalid for
 705    paradoxical loop (lets define paradoxical loops as loops whose test is
 706    failing at -1th iteration, for instance "for (i=5;i<1;i++);").
 707
 708    These cases needs to be either cared by copying the loop test in the front
 709    of loop or keeping the test in first iteration of loop.
 710
 711    When INIT/LIM are set, they are used instead of var/lim of DESC.  */
 712 rtx
 713 count_loop_iterations (struct loop_desc *desc, rtx init, rtx lim)
 714 {
 715   enum rtx_code cond = desc->cond;
 716   rtx stride = desc->stride;
 717   rtx mod, exp, ainit, bound;
 718   rtx overflow_check, mx, mxp;
 719   enum machine_mode mode = GET_MODE (desc->var);
 720   unsigned HOST_WIDEST_INT s, size, d;
 721
 722   /* Give up on floating point modes and friends.  It can be possible to do
 723      the job for constant loop bounds, but it is probably not worthwhile.  */
 724   if (!INTEGRAL_MODE_P (mode))
 725     return NULL;
 726
 727   init = copy_rtx (init ? init : desc->var);
 728   lim = copy_rtx (lim ? lim : desc->lim);
 729
 730   /* Ensure that we always handle the condition to stay inside loop.  */
 731   if (desc->neg)
 732     cond = reverse_condition (cond);
 733
 734   if (desc->inner_mode != mode)
 735     {
 736       /* We have a case when the variable in fact iterates in the narrower
 737          mode.  This has following consequences:
 738
 739          For induction variable itself, if !desc->postincr, it does not mean
 740          anything too special, since we know the variable is already in range
 741          of the inner mode when we compare it (so it is just needed to shorten
 742          it into the mode before calculations are done, so that we don't risk
 743          wrong results).  More complicated case is when desc->postincr; then
 744          the first two iterations are special (the first one because the value
 745          may be out of range, the second one because after shortening it to the
 746          range it may have absolutely any value), and we do not handle this in
 747          unrolling.  So if we aren't able to prove that the initial value is in
 748          the range, we fail in this case.
 749
 750          Step is just moduled to fit into inner mode.
 751
 752          If lim is out of range, then either the loop is infinite (and then
 753          we may unroll however we like to), or exits in the first iteration
 754          (this is also ok, since we handle it specially for this case anyway).
 755          So we may safely assume that it fits into the inner mode.  */
 756
 757       for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
 758         if (fits_in_mode_p (desc->inner_mode, XEXP (ainit, 0)))
 759           break;
 760
 761       if (!ainit)
 762         {
 763           if (desc->postincr)
 764             return NULL_RTX;
 765
 766           init = simplify_gen_unary (desc->extend,
 767                                      mode,
 768                                      simplify_gen_subreg (desc->inner_mode,
 769                                                           init,
 770                                                           mode,
 771                                                           0),
 772                                      desc->inner_mode);
 773         }
 774
 775       stride = simplify_gen_subreg (desc->inner_mode, stride, mode, 0);
 776       if (stride == const0_rtx)
 777         return NULL_RTX;
 778     }
 779
 780   /* Prepare condition to verify that we do not risk overflow.  */
 781   if (stride == const1_rtx
 782       || stride == constm1_rtx
 783       || cond == NE
 784       || cond == EQ)
 785     {
 786       /* Overflow at NE conditions does not occur.  EQ condition
 787          is weird and is handled in count_strange_loop_iterations.
 788          If stride is 1, overflow may occur only for <= and >= conditions,
 789          and then they are infinite, so it does not bother us.  */
 790       overflow_check = const0_rtx;
 791     }
 792   else
 793     {
 794       if (cond == LT || cond == LTU)
 795         mx = simplify_gen_binary (MINUS, mode, lim, const1_rtx);
 796       else if (cond == GT || cond == GTU)
 797         mx = simplify_gen_binary (PLUS, mode, lim, const1_rtx);
 798       else
 799         mx = lim;
 800       if (mode != desc->inner_mode)
 801         mxp = simplify_gen_subreg (desc->inner_mode, mx, mode, 0);
 802       else
 803         mxp = mx;
 804       mxp = simplify_gen_binary (PLUS, desc->inner_mode, mxp, stride);
 805       if (mode != desc->inner_mode)
 806         mxp = simplify_gen_unary (desc->extend, mode, mxp, desc->inner_mode);
 807       overflow_check = simplify_gen_relational (cond, SImode, mode, mx, mxp);
 808     }
 809
 810   /* Compute absolute value of the difference of initial and final value.  */
 811   if (INTVAL (stride) > 0)
 812     {
 813       /* Handle strange tests specially.  */
 814       if (cond == EQ || cond == GE || cond == GT || cond == GEU
 815           || cond == GTU)
 816         return count_strange_loop_iterations (init, lim, cond, desc->postincr,
 817                                               stride, mode, desc->inner_mode);
 818       exp = simplify_gen_binary (MINUS, mode, lim, init);
 819     }
 820   else
 821     {
 822       if (cond == EQ || cond == LE || cond == LT || cond == LEU
 823           || cond == LTU)
 824         return count_strange_loop_iterations (init, lim, cond, desc->postincr,
 825                                               stride, mode, desc->inner_mode);
 826       exp = simplify_gen_binary (MINUS, mode, init, lim);
 827       stride = simplify_gen_unary (NEG, mode, stride, mode);
 828     }
 829
 830   /* If there is a risk of overflow (i.e. when we increment value satisfying
 831      a condition, we may again obtain a value satisfying the condition),
 832      fail.  */
 833   if (overflow_check != const0_rtx)
 834     return NULL_RTX;
 835
 836   /* Normalize difference so the value is always first examined
 837      and later incremented.  */
 838   if (!desc->postincr)
 839     exp = simplify_gen_binary (MINUS, mode, exp, stride);
 840
 841   /* Determine delta caused by exit condition.  */
 842   switch (cond)
 843     {
 844     case NE:
 845       /* NE tests are easy to handle, because we just perform simple
 846          arithmetics modulo power of 2.  Let's use the fact to compute the
 847          number of iterations exactly.  We are now in situation when we want to
 848          solve an equation stride * i = c (mod size of inner_mode).
 849          Let nsd (stride, size of mode) = d.  If d does not divide c, the
 850          loop is infinite.  Otherwise, the number of iterations is
 851          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
 852       size = GET_MODE_BITSIZE (desc->inner_mode);
 853       s = INTVAL (stride);
 854       d = 1;
 855       while (s % 2 != 1)
 856         {
 857           s /= 2;
 858           d *= 2;
 859           size--;
 860         }
 861       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
 862       exp = simplify_gen_binary (UDIV, mode, exp, GEN_INT (d));
 863       exp = simplify_gen_binary (MULT, mode,
 864                                  exp, GEN_INT (inverse (s, size)));
 865       exp = simplify_gen_binary (AND, mode, exp, bound);
 866       break;
 867
 868     case LT:
 869     case GT:
 870     case LTU:
 871     case GTU:
 872       break;
 873     case LE:
 874     case GE:
 875     case LEU:
 876     case GEU:
 877       exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
 878       break;
 879     default:
 880       abort ();
 881     }
 882
 883   if (cond != NE && stride != const1_rtx)
 884     {
 885       /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
 886          but we need to take care for overflows.  */
 887
 888       mod = simplify_gen_binary (UMOD, mode, exp, stride);
 889
 890       /* This is dirty trick.  When we can't compute number of iterations
 891          to be constant, we simply ignore the possible overflow, as
 892          runtime unroller always use power of 2 amounts and does not
 893          care about possible lost bits.  */
 894
 895       if (GET_CODE (mod) != CONST_INT)
 896         {
 897           rtx stridem1 = simplify_gen_binary (PLUS, mode, stride, constm1_rtx);
 898           exp = simplify_gen_binary (PLUS, mode, exp, stridem1);
 899           exp = simplify_gen_binary (UDIV, mode, exp, stride);
 900         }
 901       else
 902         {
 903           exp = simplify_gen_binary (UDIV, mode, exp, stride);
 904           if (mod != const0_rtx)
 905             exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
 906         }
 907     }
 908
 909   if (rtl_dump_file)
 910     {
 911       fprintf (rtl_dump_file, ";  Number of iterations: ");
 912       print_simple_rtl (rtl_dump_file, exp);
 913       fprintf (rtl_dump_file, "\n");
 914     }
 915
 916   return exp;
 917 }
 918
 919 /* Return simplified RTX expression representing the value of test
 920    described of DESC at given iteration of loop.  */
 921
 922 static rtx
 923 test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT iter)
 924 {
 925   enum rtx_code cond = desc->cond;
 926   rtx exp = XEXP (desc->var_alts, 0);
 927   rtx addval;
 928
 929   /* Give up on floating point modes and friends.  It can be possible to do
 930      the job for constant loop bounds, but it is probably not worthwhile.  */
 931   if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
 932     return NULL;
 933
 934   /* Ensure that we always handle the condition to stay inside loop.  */
 935   if (desc->neg)
 936     cond = reverse_condition (cond);
 937
 938   /* Compute the value of induction variable.  */
 939   addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
 940                                 desc->stride,
 941                                 gen_int_mode (desc->postincr
 942                                               ? iter : iter + 1,
 943                                               GET_MODE (desc->var)));
 944   exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
 945   /* Test at given condition.  */
 946   exp = simplify_gen_relational (cond, SImode,
 947                                  GET_MODE (desc->var), exp, desc->lim);
 948
 949   if (rtl_dump_file)
 950     {
 951       fprintf (rtl_dump_file, ";  Conditional to continue loop at "
 952                HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
 953       print_simple_rtl (rtl_dump_file, exp);
 954       fprintf (rtl_dump_file, "\n");
 955     }
 956   return exp;
 957 }
 958
 959
 960 /* Tests whether exit at EXIT_EDGE from LOOP is simple.  Returns simple loop
 961    description joined to it in in DESC.  INVARIANT_REGS and SINGLE_SET_REGS
 962    are results of blocks_{invariant,single_set}_regs over BODY.  */
 963 static bool
 964 simple_loop_exit_p (struct loop *loop, edge exit_edge,
 965                     regset invariant_regs, rtx *single_set_regs,
 966                     struct loop_desc *desc)
 967 {
 968   basic_block mod_bb, exit_bb;
 969   int fallthru_out;
 970   rtx condition;
 971   edge ei, e;
 972
 973   exit_bb = exit_edge->src;
 974
 975   fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
 976
 977   if (!exit_bb)
 978     return false;
 979
 980   /* It must be tested (at least) once during any iteration.  */
 981   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
 982     return false;
 983
 984   /* It must end in a simple conditional jump.  */
 985   if (!any_condjump_p (BB_END (exit_bb)))
 986     return false;
 987
 988   ei = exit_bb->succ;
 989   if (ei == exit_edge)
 990     ei = ei->succ_next;
 991
 992   desc->out_edge = exit_edge;
 993   desc->in_edge = ei;
 994
 995   /* Condition must be a simple comparison in that one of operands
 996      is register and the other one is invariant.  */
 997   if (!(condition = get_condition (BB_END (exit_bb), NULL, false)))
 998     return false;
 999
1000   if (!simple_condition_p (loop, condition, invariant_regs, desc))
1001     return false;
1002
1003   /*  Var must be simply incremented or decremented in exactly one insn that
1004      is executed just once every iteration.  */
1005   if (!(mod_bb = simple_increment (loop, single_set_regs, desc)))
1006     return false;
1007
1008   /* OK, it is simple loop.  Now just fill in remaining info.  */
1009   desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
1010   desc->neg = !fallthru_out;
1011
1012   /* Find initial value of var and alternative values for lim.  */
1013   e = loop_preheader_edge (loop);
1014   desc->var_alts = variable_initial_values (e, desc->var, desc->inner_mode);
1015   desc->lim_alts = variable_initial_values (e, desc->lim, desc->inner_mode);
1016
1017   /* Number of iterations.  */
1018   desc->const_iter =
1019     constant_iterations (desc, &desc->niter, &desc->may_be_zero);
1020   if (!desc->const_iter && !count_loop_iterations (desc, NULL, NULL))
1021     return false;
1022   return true;
1023 }
1024
1025 /* Tests whether LOOP is simple for loop.  Returns simple loop description
1026    in DESC.  */
1027 bool
1028 simple_loop_p (struct loop *loop, struct loop_desc *desc)
1029 {
1030   unsigned i;
1031   basic_block *body;
1032   edge e;
1033   struct loop_desc act;
1034   bool any = false;
1035   regset invariant_regs;
1036   regset_head invariant_regs_head;
1037   rtx *single_set_regs;
1038   int n_branches;
1039
1040   body = get_loop_body (loop);
1041
1042   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
1043   single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
1044
1045   blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
1046   blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
1047
1048   n_branches = 0;
1049   for (i = 0; i < loop->num_nodes; i++)
1050     {
1051       for (e = body[i]->succ; e; e = e->succ_next)
1052         if (!flow_bb_inside_loop_p (loop, e->dest)
1053             && simple_loop_exit_p (loop, e,
1054                    invariant_regs, single_set_regs, &act))
1055           {
1056             /* Prefer constant iterations; the less the better.  */
1057             if (!any)
1058               any = true;
1059             else if (!act.const_iter
1060                      || (desc->const_iter && act.niter >= desc->niter))
1061               continue;
1062             *desc = act;
1063           }
1064
1065       if (body[i]->succ && body[i]->succ->succ_next)
1066         n_branches++;
1067     }
1068   desc->n_branches = n_branches;
1069
1070   if (rtl_dump_file && any)
1071     {
1072       fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
1073       if (desc->postincr)
1074         fprintf (rtl_dump_file,
1075                  ";  does postincrement after loop exit condition\n");
1076
1077       fprintf (rtl_dump_file, ";  Induction variable:");
1078       print_simple_rtl (rtl_dump_file, desc->var);
1079       fputc ('\n', rtl_dump_file);
1080
1081       fprintf (rtl_dump_file, ";  Initial values:");
1082       print_simple_rtl (rtl_dump_file, desc->var_alts);
1083       fputc ('\n', rtl_dump_file);
1084
1085       fprintf (rtl_dump_file, ";  Stride:");
1086       print_simple_rtl (rtl_dump_file, desc->stride);
1087       fputc ('\n', rtl_dump_file);
1088
1089       fprintf (rtl_dump_file, ";  Compared with:");
1090       print_simple_rtl (rtl_dump_file, desc->lim);
1091       fputc ('\n', rtl_dump_file);
1092
1093       fprintf (rtl_dump_file, ";  Alternative values:");
1094       print_simple_rtl (rtl_dump_file, desc->lim_alts);
1095       fputc ('\n', rtl_dump_file);
1096
1097       fprintf (rtl_dump_file, ";  Exit condition:");
1098       if (desc->neg)
1099         fprintf (rtl_dump_file, "(negated)");
1100       fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
1101
1102       fprintf (rtl_dump_file, ";  Number of branches:");
1103       fprintf (rtl_dump_file, "%d\n", desc->n_branches);
1104
1105       fputc ('\n', rtl_dump_file);
1106     }
1107
1108   free (body);
1109   FREE_REG_SET (invariant_regs);
1110   free (single_set_regs);
1111   return any;
1112 }
1113
1114 /* Structure representing edge of a graph.  */
1115
1116 struct edge
1117 {
1118   int src, dest;        /* Source and destination.  */
1119   struct edge *pred_next, *succ_next;
1120                         /* Next edge in predecessor and successor lists.  */
1121   void *data;           /* Data attached to the edge.  */
1122 };
1123
1124 /* Structure representing vertex of a graph.  */
1125
1126 struct vertex
1127 {
1128   struct edge *pred, *succ;
1129                         /* Lists of predecessors and successors.  */
1130   int component;        /* Number of dfs restarts before reaching the
1131                            vertex.  */
1132   int post;             /* Postorder number.  */
1133 };
1134
1135 /* Structure representing a graph.  */
1136
1137 struct graph
1138 {
1139   int n_vertices;       /* Number of vertices.  */
1140   struct vertex *vertices;
1141                         /* The vertices.  */
1142 };
1143
1144 /* Dumps graph G into F.  */
1145
1146 extern void dump_graph (FILE *, struct graph *);
1147 void dump_graph (FILE *f, struct graph *g)
1148 {
1149   int i;
1150   struct edge *e;
1151
1152   for (i = 0; i < g->n_vertices; i++)
1153     {
1154       if (!g->vertices[i].pred
1155           && !g->vertices[i].succ)
1156         continue;
1157
1158       fprintf (f, "%d (%d)\t<-", i, g->vertices[i].component);
1159       for (e = g->vertices[i].pred; e; e = e->pred_next)
1160         fprintf (f, " %d", e->src);
1161       fprintf (f, "\n");
1162
1163       fprintf (f, "\t->");
1164       for (e = g->vertices[i].succ; e; e = e->succ_next)
1165         fprintf (f, " %d", e->dest);
1166       fprintf (f, "\n");
1167     }
1168 }
1169
1170 /* Creates a new graph with N_VERTICES vertices.  */
1171
1172 static struct graph *
1173 new_graph (int n_vertices)
1174 {
1175   struct graph *g = xmalloc (sizeof (struct graph));
1176
1177   g->n_vertices = n_vertices;
1178   g->vertices = xcalloc (n_vertices, sizeof (struct vertex));
1179
1180   return g;
1181 }
1182
1183 /* Adds an edge from F to T to graph G, with DATA attached.  */
1184
1185 static void
1186 add_edge (struct graph *g, int f, int t, void *data)
1187 {
1188   struct edge *e = xmalloc (sizeof (struct edge));
1189
1190   e->src = f;
1191   e->dest = t;
1192   e->data = data;
1193
1194   e->pred_next = g->vertices[t].pred;
1195   g->vertices[t].pred = e;
1196
1197   e->succ_next = g->vertices[f].succ;
1198   g->vertices[f].succ = e;
1199 }
1200
1201 /* Runs dfs search over vertices of G, from NQ vertices in queue QS.
1202    The vertices in postorder are stored into QT.  If FORWARD is false,
1203    backward dfs is run.  */
1204
1205 static void
1206 dfs (struct graph *g, int *qs, int nq, int *qt, bool forward)
1207 {
1208   int i, tick = 0, v, comp = 0, top;
1209   struct edge *e;
1210   struct edge **stack = xmalloc (sizeof (struct edge *) * g->n_vertices);
1211
1212   for (i = 0; i < g->n_vertices; i++)
1213     {
1214       g->vertices[i].component = -1;
1215       g->vertices[i].post = -1;
1216     }
1217
1218 #define FST_EDGE(V) (forward ? g->vertices[(V)].succ : g->vertices[(V)].pred)
1219 #define NEXT_EDGE(E) (forward ? (E)->succ_next : (E)->pred_next)
1220 #define EDGE_SRC(E) (forward ? (E)->src : (E)->dest)
1221 #define EDGE_DEST(E) (forward ? (E)->dest : (E)->src)
1222
1223   for (i = 0; i < nq; i++)
1224     {
1225       v = qs[i];
1226       if (g->vertices[v].post != -1)
1227         continue;
1228
1229       g->vertices[v].component = comp++;
1230       e = FST_EDGE (v);
1231       top = 0;
1232
1233       while (1)
1234         {
1235           while (e && g->vertices[EDGE_DEST (e)].component != -1)
1236             e = NEXT_EDGE (e);
1237
1238           if (!e)
1239             {
1240               if (qt)
1241                 qt[tick] = v;
1242               g->vertices[v].post = tick++;
1243
1244               if (!top)
1245                 break;
1246
1247               e = stack[--top];
1248               v = EDGE_SRC (e);
1249               e = NEXT_EDGE (e);
1250               continue;
1251             }
1252
1253           stack[top++] = e;
1254           v = EDGE_DEST (e);
1255           e = FST_EDGE (v);
1256           g->vertices[v].component = comp - 1;
1257         }
1258     }
1259
1260   free (stack);
1261 }
1262
1263 /* Marks the edge E in graph G irreducible if it connects two vertices in the
1264    same scc.  */
1265
1266 static void
1267 check_irred (struct graph *g, struct edge *e)
1268 {
1269   edge real = e->data;
1270
1271   /* All edges should lead from a component with higher number to the
1272      one with lower one.  */
1273   if (g->vertices[e->src].component < g->vertices[e->dest].component)
1274     abort ();
1275
1276   if (g->vertices[e->src].component != g->vertices[e->dest].component)
1277     return;
1278
1279   real->flags |= EDGE_IRREDUCIBLE_LOOP;
1280   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
1281     real->src->flags |= BB_IRREDUCIBLE_LOOP;
1282 }
1283
1284 /* Runs CALLBACK for all edges in G.  */
1285
1286 static void
1287 for_each_edge (struct graph *g,
1288                void (callback) (struct graph *, struct edge *))
1289 {
1290   struct edge *e;
1291   int i;
1292
1293   for (i = 0; i < g->n_vertices; i++)
1294     for (e = g->vertices[i].succ; e; e = e->succ_next)
1295       callback (g, e);
1296 }
1297
1298 /* Releases the memory occupied by G.  */
1299
1300 static void
1301 free_graph (struct graph *g)
1302 {
1303   struct edge *e, *n;
1304   int i;
1305
1306   for (i = 0; i < g->n_vertices; i++)
1307     for (e = g->vertices[i].succ; e; e = n)
1308       {
1309         n = e->succ_next;
1310         free (e);
1311       }
1312   free (g->vertices);
1313   free (g);
1314 }
1315
1316 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
1317    throw away all latch edges and mark blocks inside any remaining cycle.
1318    Everything is a bit complicated due to fact we do not want to do this
1319    for parts of cycles that only "pass" through some loop -- i.e. for
1320    each cycle, we want to mark blocks that belong directly to innermost
1321    loop containing the whole cycle.
1322
1323    LOOPS is the loop tree.  */
1324
1325 #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
1326 #define BB_REPR(BB) ((BB)->index + 1)
1327
1328 void
1329 mark_irreducible_loops (struct loops *loops)
1330 {
1331   basic_block act;
1332   edge e;
1333   int i, src, dest;
1334   struct graph *g;
1335   int *queue1 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1336   int *queue2 = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1337   int nq, depth;
1338   struct loop *cloop;
1339
1340   /* Reset the flags.  */
1341   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1342     {
1343       act->flags &= ~BB_IRREDUCIBLE_LOOP;
1344       for (e = act->succ; e; e = e->succ_next)
1345         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1346     }
1347
1348   /* Create the edge lists.  */
1349   g = new_graph (last_basic_block + loops->num);
1350
1351   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1352     for (e = act->succ; e; e = e->succ_next)
1353       {
1354         /* Ignore edges to exit.  */
1355         if (e->dest == EXIT_BLOCK_PTR)
1356           continue;
1357
1358         /* And latch edges.  */
1359         if (e->dest->loop_father->header == e->dest
1360             && e->dest->loop_father->latch == act)
1361           continue;
1362
1363         /* Edges inside a single loop should be left where they are.  Edges
1364            to subloop headers should lead to representative of the subloop,
1365            but from the same place.
1366
1367            Edges exiting loops should lead from representative
1368            of the son of nearest common ancestor of the loops in that
1369            act lays.  */
1370
1371         src = BB_REPR (act);
1372         dest = BB_REPR (e->dest);
1373
1374         if (e->dest->loop_father->header == e->dest)
1375           dest = LOOP_REPR (e->dest->loop_father);
1376
1377         if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
1378           {
1379             depth = find_common_loop (act->loop_father,
1380                                       e->dest->loop_father)->depth + 1;
1381             if (depth == act->loop_father->depth)
1382               cloop = act->loop_father;
1383             else
1384               cloop = act->loop_father->pred[depth];
1385
1386             src = LOOP_REPR (cloop);
1387           }
1388
1389         add_edge (g, src, dest, e);
1390       }
1391
1392   /* Find the strongly connected components.  Use the algorithm of Tarjan --
1393      first determine the postorder dfs numbering in reversed graph, then
1394      run the dfs on the original graph in the order given by decreasing
1395      numbers assigned by the previous pass.  */
1396   nq = 0;
1397   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1398     {
1399       queue1[nq++] = BB_REPR (act);
1400     }
1401   for (i = 1; i < (int) loops->num; i++)
1402     if (loops->parray[i])
1403       queue1[nq++] = LOOP_REPR (loops->parray[i]);
1404   dfs (g, queue1, nq, queue2, false);
1405   for (i = 0; i < nq; i++)
1406     queue1[i] = queue2[nq - i - 1];
1407   dfs (g, queue1, nq, NULL, true);
1408
1409   /* Mark the irreducible loops.  */
1410   for_each_edge (g, check_irred);
1411
1412   free_graph (g);
1413   free (queue1);
1414   free (queue2);
1415
1416   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
1417 }
1418
1419 /* Counts number of insns inside LOOP.  */
1420 int
1421 num_loop_insns (struct loop *loop)
1422 {
1423   basic_block *bbs, bb;
1424   unsigned i, ninsns = 0;
1425   rtx insn;
1426
1427   bbs = get_loop_body (loop);
1428   for (i = 0; i < loop->num_nodes; i++)
1429     {
1430       bb = bbs[i];
1431       ninsns++;
1432       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
1433         if (INSN_P (insn))
1434           ninsns++;
1435     }
1436   free(bbs);
1437
1438   return ninsns;
1439 }
1440
1441 /* Counts number of insns executed on average per iteration LOOP.  */
1442 int
1443 average_num_loop_insns (struct loop *loop)
1444 {
1445   basic_block *bbs, bb;
1446   unsigned i, binsns, ninsns, ratio;
1447   rtx insn;
1448
1449   ninsns = 0;
1450   bbs = get_loop_body (loop);
1451   for (i = 0; i < loop->num_nodes; i++)
1452     {
1453       bb = bbs[i];
1454
1455       binsns = 1;
1456       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
1457         if (INSN_P (insn))
1458           binsns++;
1459
1460       ratio = loop->header->frequency == 0
1461               ? BB_FREQ_MAX
1462               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
1463       ninsns += binsns * ratio;
1464     }
1465   free(bbs);
1466
1467   ninsns /= BB_FREQ_MAX;
1468   if (!ninsns)
1469     ninsns = 1; /* To avoid division by zero.  */
1470
1471   return ninsns;
1472 }
1473
1474 /* Returns expected number of LOOP iterations.
1475    Compute upper bound on number of iterations in case they do not fit integer
1476    to help loop peeling heuristics.  Use exact counts if at all possible.  */
1477 unsigned
1478 expected_loop_iterations (const struct loop *loop)
1479 {
1480   edge e;
1481
1482   if (loop->header->count)
1483     {
1484       gcov_type count_in, count_latch, expected;
1485
1486       count_in = 0;
1487       count_latch = 0;
1488
1489       for (e = loop->header->pred; e; e = e->pred_next)
1490         if (e->src == loop->latch)
1491           count_latch = e->count;
1492         else
1493           count_in += e->count;
1494
1495       if (count_in == 0)
1496         return 0;
1497
1498       expected = (count_latch + count_in - 1) / count_in;
1499
1500       /* Avoid overflows.  */
1501       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
1502     }
1503   else
1504     {
1505       int freq_in, freq_latch;
1506
1507       freq_in = 0;
1508       freq_latch = 0;
1509
1510       for (e = loop->header->pred; e; e = e->pred_next)
1511         if (e->src == loop->latch)
1512           freq_latch = EDGE_FREQUENCY (e);
1513         else
1514           freq_in += EDGE_FREQUENCY (e);
1515
1516       if (freq_in == 0)
1517         return 0;
1518
1519       return (freq_latch + freq_in - 1) / freq_in;
1520     }
1521 }