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