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