gcc/cfgloopanal.c

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