gcc/cfgloopanal.c

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