2013-11-21 Edward Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / loop-iv.c
blobc01ee1783051357df04f09d422003a95cdb235f1
1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY 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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
23 on demand.
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
50 #include "config.h"
51 #include "system.h"
52 #include "coretypes.h"
53 #include "tm.h"
54 #include "rtl.h"
55 #include "hard-reg-set.h"
56 #include "obstack.h"
57 #include "basic-block.h"
58 #include "cfgloop.h"
59 #include "expr.h"
60 #include "intl.h"
61 #include "diagnostic-core.h"
62 #include "df.h"
63 #include "hash-table.h"
64 #include "dumpfile.h"
66 /* Possible return values of iv_get_reaching_def. */
68 enum iv_grd_result
70 /* More than one reaching def, or reaching def that does not
71 dominate the use. */
72 GRD_INVALID,
74 /* The use is trivial invariant of the loop, i.e. is not changed
75 inside the loop. */
76 GRD_INVARIANT,
78 /* The use is reached by initial value and a value from the
79 previous iteration. */
80 GRD_MAYBE_BIV,
82 /* The use has single dominating def. */
83 GRD_SINGLE_DOM
86 /* Information about a biv. */
88 struct biv_entry
90 unsigned regno; /* The register of the biv. */
91 struct rtx_iv iv; /* Value of the biv. */
94 static bool clean_slate = true;
96 static unsigned int iv_ref_table_size = 0;
98 /* Table of rtx_ivs indexed by the df_ref uid field. */
99 static struct rtx_iv ** iv_ref_table;
101 /* Induction variable stored at the reference. */
102 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
103 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
105 /* The current loop. */
107 static struct loop *current_loop;
109 /* Hashtable helper. */
111 struct biv_entry_hasher : typed_free_remove <biv_entry>
113 typedef biv_entry value_type;
114 typedef rtx_def compare_type;
115 static inline hashval_t hash (const value_type *);
116 static inline bool equal (const value_type *, const compare_type *);
119 /* Returns hash value for biv B. */
121 inline hashval_t
122 biv_entry_hasher::hash (const value_type *b)
124 return b->regno;
127 /* Compares biv B and register R. */
129 inline bool
130 biv_entry_hasher::equal (const value_type *b, const compare_type *r)
132 return b->regno == REGNO (r);
135 /* Bivs of the current loop. */
137 static hash_table <biv_entry_hasher> bivs;
139 static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
141 /* Return the RTX code corresponding to the IV extend code EXTEND. */
142 static inline enum rtx_code
143 iv_extend_to_rtx_code (enum iv_extend_code extend)
145 switch (extend)
147 case IV_SIGN_EXTEND:
148 return SIGN_EXTEND;
149 case IV_ZERO_EXTEND:
150 return ZERO_EXTEND;
151 case IV_UNKNOWN_EXTEND:
152 return UNKNOWN;
154 gcc_unreachable ();
157 /* Dumps information about IV to FILE. */
159 extern void dump_iv_info (FILE *, struct rtx_iv *);
160 void
161 dump_iv_info (FILE *file, struct rtx_iv *iv)
163 if (!iv->base)
165 fprintf (file, "not simple");
166 return;
169 if (iv->step == const0_rtx
170 && !iv->first_special)
171 fprintf (file, "invariant ");
173 print_rtl (file, iv->base);
174 if (iv->step != const0_rtx)
176 fprintf (file, " + ");
177 print_rtl (file, iv->step);
178 fprintf (file, " * iteration");
180 fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
182 if (iv->mode != iv->extend_mode)
183 fprintf (file, " %s to %s",
184 rtx_name[iv_extend_to_rtx_code (iv->extend)],
185 GET_MODE_NAME (iv->extend_mode));
187 if (iv->mult != const1_rtx)
189 fprintf (file, " * ");
190 print_rtl (file, iv->mult);
192 if (iv->delta != const0_rtx)
194 fprintf (file, " + ");
195 print_rtl (file, iv->delta);
197 if (iv->first_special)
198 fprintf (file, " (first special)");
201 /* Generates a subreg to get the least significant part of EXPR (in mode
202 INNER_MODE) to OUTER_MODE. */
205 lowpart_subreg (enum machine_mode outer_mode, rtx expr,
206 enum machine_mode inner_mode)
208 return simplify_gen_subreg (outer_mode, expr, inner_mode,
209 subreg_lowpart_offset (outer_mode, inner_mode));
212 static void
213 check_iv_ref_table_size (void)
215 if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ())
217 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
218 iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
219 memset (&iv_ref_table[iv_ref_table_size], 0,
220 (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
221 iv_ref_table_size = new_size;
226 /* Checks whether REG is a well-behaved register. */
228 static bool
229 simple_reg_p (rtx reg)
231 unsigned r;
233 if (GET_CODE (reg) == SUBREG)
235 if (!subreg_lowpart_p (reg))
236 return false;
237 reg = SUBREG_REG (reg);
240 if (!REG_P (reg))
241 return false;
243 r = REGNO (reg);
244 if (HARD_REGISTER_NUM_P (r))
245 return false;
247 if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
248 return false;
250 return true;
253 /* Clears the information about ivs stored in df. */
255 static void
256 clear_iv_info (void)
258 unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
259 struct rtx_iv *iv;
261 check_iv_ref_table_size ();
262 for (i = 0; i < n_defs; i++)
264 iv = iv_ref_table[i];
265 if (iv)
267 free (iv);
268 iv_ref_table[i] = NULL;
272 bivs.empty ();
276 /* Prepare the data for an induction variable analysis of a LOOP. */
278 void
279 iv_analysis_loop_init (struct loop *loop)
281 basic_block *body = get_loop_body_in_dom_order (loop), bb;
282 bitmap blocks = BITMAP_ALLOC (NULL);
283 unsigned i;
285 current_loop = loop;
287 /* Clear the information from the analysis of the previous loop. */
288 if (clean_slate)
290 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
291 bivs.create (10);
292 clean_slate = false;
294 else
295 clear_iv_info ();
297 for (i = 0; i < loop->num_nodes; i++)
299 bb = body[i];
300 bitmap_set_bit (blocks, bb->index);
302 /* Get rid of the ud chains before processing the rescans. Then add
303 the problem back. */
304 df_remove_problem (df_chain);
305 df_process_deferred_rescans ();
306 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
307 df_chain_add_problem (DF_UD_CHAIN);
308 df_note_add_problem ();
309 df_set_blocks (blocks);
310 df_analyze ();
311 if (dump_file)
312 df_dump_region (dump_file);
314 check_iv_ref_table_size ();
315 BITMAP_FREE (blocks);
316 free (body);
319 /* Finds the definition of REG that dominates loop latch and stores
320 it to DEF. Returns false if there is not a single definition
321 dominating the latch. If REG has no definition in loop, DEF
322 is set to NULL and true is returned. */
324 static bool
325 latch_dominating_def (rtx reg, df_ref *def)
327 df_ref single_rd = NULL, adef;
328 unsigned regno = REGNO (reg);
329 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
331 for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
333 if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
334 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
335 continue;
337 /* More than one reaching definition. */
338 if (single_rd)
339 return false;
341 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
342 return false;
344 single_rd = adef;
347 *def = single_rd;
348 return true;
351 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
353 static enum iv_grd_result
354 iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
356 df_ref use, adef;
357 basic_block def_bb, use_bb;
358 rtx def_insn;
359 bool dom_p;
361 *def = NULL;
362 if (!simple_reg_p (reg))
363 return GRD_INVALID;
364 if (GET_CODE (reg) == SUBREG)
365 reg = SUBREG_REG (reg);
366 gcc_assert (REG_P (reg));
368 use = df_find_use (insn, reg);
369 gcc_assert (use != NULL);
371 if (!DF_REF_CHAIN (use))
372 return GRD_INVARIANT;
374 /* More than one reaching def. */
375 if (DF_REF_CHAIN (use)->next)
376 return GRD_INVALID;
378 adef = DF_REF_CHAIN (use)->ref;
380 /* We do not handle setting only part of the register. */
381 if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
382 return GRD_INVALID;
384 def_insn = DF_REF_INSN (adef);
385 def_bb = DF_REF_BB (adef);
386 use_bb = BLOCK_FOR_INSN (insn);
388 if (use_bb == def_bb)
389 dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
390 else
391 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
393 if (dom_p)
395 *def = adef;
396 return GRD_SINGLE_DOM;
399 /* The definition does not dominate the use. This is still OK if
400 this may be a use of a biv, i.e. if the def_bb dominates loop
401 latch. */
402 if (just_once_each_iteration_p (current_loop, def_bb))
403 return GRD_MAYBE_BIV;
405 return GRD_INVALID;
408 /* Sets IV to invariant CST in MODE. Always returns true (just for
409 consistency with other iv manipulation functions that may fail). */
411 static bool
412 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
414 if (mode == VOIDmode)
415 mode = GET_MODE (cst);
417 iv->mode = mode;
418 iv->base = cst;
419 iv->step = const0_rtx;
420 iv->first_special = false;
421 iv->extend = IV_UNKNOWN_EXTEND;
422 iv->extend_mode = iv->mode;
423 iv->delta = const0_rtx;
424 iv->mult = const1_rtx;
426 return true;
429 /* Evaluates application of subreg to MODE on IV. */
431 static bool
432 iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
434 /* If iv is invariant, just calculate the new value. */
435 if (iv->step == const0_rtx
436 && !iv->first_special)
438 rtx val = get_iv_value (iv, const0_rtx);
439 val = lowpart_subreg (mode, val,
440 iv->extend == IV_UNKNOWN_EXTEND
441 ? iv->mode : iv->extend_mode);
443 iv->base = val;
444 iv->extend = IV_UNKNOWN_EXTEND;
445 iv->mode = iv->extend_mode = mode;
446 iv->delta = const0_rtx;
447 iv->mult = const1_rtx;
448 return true;
451 if (iv->extend_mode == mode)
452 return true;
454 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
455 return false;
457 iv->extend = IV_UNKNOWN_EXTEND;
458 iv->mode = mode;
460 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
461 simplify_gen_binary (MULT, iv->extend_mode,
462 iv->base, iv->mult));
463 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
464 iv->mult = const1_rtx;
465 iv->delta = const0_rtx;
466 iv->first_special = false;
468 return true;
471 /* Evaluates application of EXTEND to MODE on IV. */
473 static bool
474 iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode)
476 /* If iv is invariant, just calculate the new value. */
477 if (iv->step == const0_rtx
478 && !iv->first_special)
480 rtx val = get_iv_value (iv, const0_rtx);
481 if (iv->extend_mode != iv->mode
482 && iv->extend != IV_UNKNOWN_EXTEND
483 && iv->extend != extend)
484 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
485 val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
486 val,
487 iv->extend == extend
488 ? iv->extend_mode : iv->mode);
489 iv->base = val;
490 iv->extend = IV_UNKNOWN_EXTEND;
491 iv->mode = iv->extend_mode = mode;
492 iv->delta = const0_rtx;
493 iv->mult = const1_rtx;
494 return true;
497 if (mode != iv->extend_mode)
498 return false;
500 if (iv->extend != IV_UNKNOWN_EXTEND
501 && iv->extend != extend)
502 return false;
504 iv->extend = extend;
506 return true;
509 /* Evaluates negation of IV. */
511 static bool
512 iv_neg (struct rtx_iv *iv)
514 if (iv->extend == IV_UNKNOWN_EXTEND)
516 iv->base = simplify_gen_unary (NEG, iv->extend_mode,
517 iv->base, iv->extend_mode);
518 iv->step = simplify_gen_unary (NEG, iv->extend_mode,
519 iv->step, iv->extend_mode);
521 else
523 iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
524 iv->delta, iv->extend_mode);
525 iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
526 iv->mult, iv->extend_mode);
529 return true;
532 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
534 static bool
535 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
537 enum machine_mode mode;
538 rtx arg;
540 /* Extend the constant to extend_mode of the other operand if necessary. */
541 if (iv0->extend == IV_UNKNOWN_EXTEND
542 && iv0->mode == iv0->extend_mode
543 && iv0->step == const0_rtx
544 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
546 iv0->extend_mode = iv1->extend_mode;
547 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
548 iv0->base, iv0->mode);
550 if (iv1->extend == IV_UNKNOWN_EXTEND
551 && iv1->mode == iv1->extend_mode
552 && iv1->step == const0_rtx
553 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
555 iv1->extend_mode = iv0->extend_mode;
556 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
557 iv1->base, iv1->mode);
560 mode = iv0->extend_mode;
561 if (mode != iv1->extend_mode)
562 return false;
564 if (iv0->extend == IV_UNKNOWN_EXTEND
565 && iv1->extend == IV_UNKNOWN_EXTEND)
567 if (iv0->mode != iv1->mode)
568 return false;
570 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
571 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
573 return true;
576 /* Handle addition of constant. */
577 if (iv1->extend == IV_UNKNOWN_EXTEND
578 && iv1->mode == mode
579 && iv1->step == const0_rtx)
581 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
582 return true;
585 if (iv0->extend == IV_UNKNOWN_EXTEND
586 && iv0->mode == mode
587 && iv0->step == const0_rtx)
589 arg = iv0->base;
590 *iv0 = *iv1;
591 if (op == MINUS
592 && !iv_neg (iv0))
593 return false;
595 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
596 return true;
599 return false;
602 /* Evaluates multiplication of IV by constant CST. */
604 static bool
605 iv_mult (struct rtx_iv *iv, rtx mby)
607 enum machine_mode mode = iv->extend_mode;
609 if (GET_MODE (mby) != VOIDmode
610 && GET_MODE (mby) != mode)
611 return false;
613 if (iv->extend == IV_UNKNOWN_EXTEND)
615 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
616 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
618 else
620 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
621 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
624 return true;
627 /* Evaluates shift of IV by constant CST. */
629 static bool
630 iv_shift (struct rtx_iv *iv, rtx mby)
632 enum machine_mode mode = iv->extend_mode;
634 if (GET_MODE (mby) != VOIDmode
635 && GET_MODE (mby) != mode)
636 return false;
638 if (iv->extend == IV_UNKNOWN_EXTEND)
640 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
641 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
643 else
645 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
646 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
649 return true;
652 /* The recursive part of get_biv_step. Gets the value of the single value
653 defined by DEF wrto initial value of REG inside loop, in shape described
654 at get_biv_step. */
656 static bool
657 get_biv_step_1 (df_ref def, rtx reg,
658 rtx *inner_step, enum machine_mode *inner_mode,
659 enum iv_extend_code *extend, enum machine_mode outer_mode,
660 rtx *outer_step)
662 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
663 rtx next, nextr, tmp;
664 enum rtx_code code;
665 rtx insn = DF_REF_INSN (def);
666 df_ref next_def;
667 enum iv_grd_result res;
669 set = single_set (insn);
670 if (!set)
671 return false;
673 rhs = find_reg_equal_equiv_note (insn);
674 if (rhs)
675 rhs = XEXP (rhs, 0);
676 else
677 rhs = SET_SRC (set);
679 code = GET_CODE (rhs);
680 switch (code)
682 case SUBREG:
683 case REG:
684 next = rhs;
685 break;
687 case PLUS:
688 case MINUS:
689 op0 = XEXP (rhs, 0);
690 op1 = XEXP (rhs, 1);
692 if (code == PLUS && CONSTANT_P (op0))
694 tmp = op0; op0 = op1; op1 = tmp;
697 if (!simple_reg_p (op0)
698 || !CONSTANT_P (op1))
699 return false;
701 if (GET_MODE (rhs) != outer_mode)
703 /* ppc64 uses expressions like
705 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
707 this is equivalent to
709 (set x':DI (plus:DI y:DI 1))
710 (set x:SI (subreg:SI (x':DI)). */
711 if (GET_CODE (op0) != SUBREG)
712 return false;
713 if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
714 return false;
717 next = op0;
718 break;
720 case SIGN_EXTEND:
721 case ZERO_EXTEND:
722 if (GET_MODE (rhs) != outer_mode)
723 return false;
725 op0 = XEXP (rhs, 0);
726 if (!simple_reg_p (op0))
727 return false;
729 next = op0;
730 break;
732 default:
733 return false;
736 if (GET_CODE (next) == SUBREG)
738 if (!subreg_lowpart_p (next))
739 return false;
741 nextr = SUBREG_REG (next);
742 if (GET_MODE (nextr) != outer_mode)
743 return false;
745 else
746 nextr = next;
748 res = iv_get_reaching_def (insn, nextr, &next_def);
750 if (res == GRD_INVALID || res == GRD_INVARIANT)
751 return false;
753 if (res == GRD_MAYBE_BIV)
755 if (!rtx_equal_p (nextr, reg))
756 return false;
758 *inner_step = const0_rtx;
759 *extend = IV_UNKNOWN_EXTEND;
760 *inner_mode = outer_mode;
761 *outer_step = const0_rtx;
763 else if (!get_biv_step_1 (next_def, reg,
764 inner_step, inner_mode, extend, outer_mode,
765 outer_step))
766 return false;
768 if (GET_CODE (next) == SUBREG)
770 enum machine_mode amode = GET_MODE (next);
772 if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
773 return false;
775 *inner_mode = amode;
776 *inner_step = simplify_gen_binary (PLUS, outer_mode,
777 *inner_step, *outer_step);
778 *outer_step = const0_rtx;
779 *extend = IV_UNKNOWN_EXTEND;
782 switch (code)
784 case REG:
785 case SUBREG:
786 break;
788 case PLUS:
789 case MINUS:
790 if (*inner_mode == outer_mode
791 /* See comment in previous switch. */
792 || GET_MODE (rhs) != outer_mode)
793 *inner_step = simplify_gen_binary (code, outer_mode,
794 *inner_step, op1);
795 else
796 *outer_step = simplify_gen_binary (code, outer_mode,
797 *outer_step, op1);
798 break;
800 case SIGN_EXTEND:
801 case ZERO_EXTEND:
802 gcc_assert (GET_MODE (op0) == *inner_mode
803 && *extend == IV_UNKNOWN_EXTEND
804 && *outer_step == const0_rtx);
806 *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
807 break;
809 default:
810 return false;
813 return true;
816 /* Gets the operation on register REG inside loop, in shape
818 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
820 If the operation cannot be described in this shape, return false.
821 LAST_DEF is the definition of REG that dominates loop latch. */
823 static bool
824 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
825 enum machine_mode *inner_mode, enum iv_extend_code *extend,
826 enum machine_mode *outer_mode, rtx *outer_step)
828 *outer_mode = GET_MODE (reg);
830 if (!get_biv_step_1 (last_def, reg,
831 inner_step, inner_mode, extend, *outer_mode,
832 outer_step))
833 return false;
835 gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
836 gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
838 return true;
841 /* Records information that DEF is induction variable IV. */
843 static void
844 record_iv (df_ref def, struct rtx_iv *iv)
846 struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
848 *recorded_iv = *iv;
849 check_iv_ref_table_size ();
850 DF_REF_IV_SET (def, recorded_iv);
853 /* If DEF was already analyzed for bivness, store the description of the biv to
854 IV and return true. Otherwise return false. */
856 static bool
857 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
859 struct biv_entry *biv = bivs.find_with_hash (def, REGNO (def));
861 if (!biv)
862 return false;
864 *iv = biv->iv;
865 return true;
868 static void
869 record_biv (rtx def, struct rtx_iv *iv)
871 struct biv_entry *biv = XNEW (struct biv_entry);
872 biv_entry **slot = bivs.find_slot_with_hash (def, REGNO (def), INSERT);
874 biv->regno = REGNO (def);
875 biv->iv = *iv;
876 gcc_assert (!*slot);
877 *slot = biv;
880 /* Determines whether DEF is a biv and if so, stores its description
881 to *IV. */
883 static bool
884 iv_analyze_biv (rtx def, struct rtx_iv *iv)
886 rtx inner_step, outer_step;
887 enum machine_mode inner_mode, outer_mode;
888 enum iv_extend_code extend;
889 df_ref last_def;
891 if (dump_file)
893 fprintf (dump_file, "Analyzing ");
894 print_rtl (dump_file, def);
895 fprintf (dump_file, " for bivness.\n");
898 if (!REG_P (def))
900 if (!CONSTANT_P (def))
901 return false;
903 return iv_constant (iv, def, VOIDmode);
906 if (!latch_dominating_def (def, &last_def))
908 if (dump_file)
909 fprintf (dump_file, " not simple.\n");
910 return false;
913 if (!last_def)
914 return iv_constant (iv, def, VOIDmode);
916 if (analyzed_for_bivness_p (def, iv))
918 if (dump_file)
919 fprintf (dump_file, " already analysed.\n");
920 return iv->base != NULL_RTX;
923 if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
924 &outer_mode, &outer_step))
926 iv->base = NULL_RTX;
927 goto end;
930 /* Loop transforms base to es (base + inner_step) + outer_step,
931 where es means extend of subreg between inner_mode and outer_mode.
932 The corresponding induction variable is
934 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
936 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
937 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
938 iv->mode = inner_mode;
939 iv->extend_mode = outer_mode;
940 iv->extend = extend;
941 iv->mult = const1_rtx;
942 iv->delta = outer_step;
943 iv->first_special = inner_mode != outer_mode;
945 end:
946 if (dump_file)
948 fprintf (dump_file, " ");
949 dump_iv_info (dump_file, iv);
950 fprintf (dump_file, "\n");
953 record_biv (def, iv);
954 return iv->base != NULL_RTX;
957 /* Analyzes expression RHS used at INSN and stores the result to *IV.
958 The mode of the induction variable is MODE. */
960 bool
961 iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
963 rtx mby = NULL_RTX, tmp;
964 rtx op0 = NULL_RTX, op1 = NULL_RTX;
965 struct rtx_iv iv0, iv1;
966 enum rtx_code code = GET_CODE (rhs);
967 enum machine_mode omode = mode;
969 iv->mode = VOIDmode;
970 iv->base = NULL_RTX;
971 iv->step = NULL_RTX;
973 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
975 if (CONSTANT_P (rhs)
976 || REG_P (rhs)
977 || code == SUBREG)
979 if (!iv_analyze_op (insn, rhs, iv))
980 return false;
982 if (iv->mode == VOIDmode)
984 iv->mode = mode;
985 iv->extend_mode = mode;
988 return true;
991 switch (code)
993 case REG:
994 op0 = rhs;
995 break;
997 case SIGN_EXTEND:
998 case ZERO_EXTEND:
999 case NEG:
1000 op0 = XEXP (rhs, 0);
1001 omode = GET_MODE (op0);
1002 break;
1004 case PLUS:
1005 case MINUS:
1006 op0 = XEXP (rhs, 0);
1007 op1 = XEXP (rhs, 1);
1008 break;
1010 case MULT:
1011 op0 = XEXP (rhs, 0);
1012 mby = XEXP (rhs, 1);
1013 if (!CONSTANT_P (mby))
1015 tmp = op0;
1016 op0 = mby;
1017 mby = tmp;
1019 if (!CONSTANT_P (mby))
1020 return false;
1021 break;
1023 case ASHIFT:
1024 op0 = XEXP (rhs, 0);
1025 mby = XEXP (rhs, 1);
1026 if (!CONSTANT_P (mby))
1027 return false;
1028 break;
1030 default:
1031 return false;
1034 if (op0
1035 && !iv_analyze_expr (insn, op0, omode, &iv0))
1036 return false;
1038 if (op1
1039 && !iv_analyze_expr (insn, op1, omode, &iv1))
1040 return false;
1042 switch (code)
1044 case SIGN_EXTEND:
1045 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1046 return false;
1047 break;
1049 case ZERO_EXTEND:
1050 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1051 return false;
1052 break;
1054 case NEG:
1055 if (!iv_neg (&iv0))
1056 return false;
1057 break;
1059 case PLUS:
1060 case MINUS:
1061 if (!iv_add (&iv0, &iv1, code))
1062 return false;
1063 break;
1065 case MULT:
1066 if (!iv_mult (&iv0, mby))
1067 return false;
1068 break;
1070 case ASHIFT:
1071 if (!iv_shift (&iv0, mby))
1072 return false;
1073 break;
1075 default:
1076 break;
1079 *iv = iv0;
1080 return iv->base != NULL_RTX;
1083 /* Analyzes iv DEF and stores the result to *IV. */
1085 static bool
1086 iv_analyze_def (df_ref def, struct rtx_iv *iv)
1088 rtx insn = DF_REF_INSN (def);
1089 rtx reg = DF_REF_REG (def);
1090 rtx set, rhs;
1092 if (dump_file)
1094 fprintf (dump_file, "Analyzing def of ");
1095 print_rtl (dump_file, reg);
1096 fprintf (dump_file, " in insn ");
1097 print_rtl_single (dump_file, insn);
1100 check_iv_ref_table_size ();
1101 if (DF_REF_IV (def))
1103 if (dump_file)
1104 fprintf (dump_file, " already analysed.\n");
1105 *iv = *DF_REF_IV (def);
1106 return iv->base != NULL_RTX;
1109 iv->mode = VOIDmode;
1110 iv->base = NULL_RTX;
1111 iv->step = NULL_RTX;
1113 if (!REG_P (reg))
1114 return false;
1116 set = single_set (insn);
1117 if (!set)
1118 return false;
1120 if (!REG_P (SET_DEST (set)))
1121 return false;
1123 gcc_assert (SET_DEST (set) == reg);
1124 rhs = find_reg_equal_equiv_note (insn);
1125 if (rhs)
1126 rhs = XEXP (rhs, 0);
1127 else
1128 rhs = SET_SRC (set);
1130 iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1131 record_iv (def, iv);
1133 if (dump_file)
1135 print_rtl (dump_file, reg);
1136 fprintf (dump_file, " in insn ");
1137 print_rtl_single (dump_file, insn);
1138 fprintf (dump_file, " is ");
1139 dump_iv_info (dump_file, iv);
1140 fprintf (dump_file, "\n");
1143 return iv->base != NULL_RTX;
1146 /* Analyzes operand OP of INSN and stores the result to *IV. */
1148 static bool
1149 iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
1151 df_ref def = NULL;
1152 enum iv_grd_result res;
1154 if (dump_file)
1156 fprintf (dump_file, "Analyzing operand ");
1157 print_rtl (dump_file, op);
1158 fprintf (dump_file, " of insn ");
1159 print_rtl_single (dump_file, insn);
1162 if (function_invariant_p (op))
1163 res = GRD_INVARIANT;
1164 else if (GET_CODE (op) == SUBREG)
1166 if (!subreg_lowpart_p (op))
1167 return false;
1169 if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1170 return false;
1172 return iv_subreg (iv, GET_MODE (op));
1174 else
1176 res = iv_get_reaching_def (insn, op, &def);
1177 if (res == GRD_INVALID)
1179 if (dump_file)
1180 fprintf (dump_file, " not simple.\n");
1181 return false;
1185 if (res == GRD_INVARIANT)
1187 iv_constant (iv, op, VOIDmode);
1189 if (dump_file)
1191 fprintf (dump_file, " ");
1192 dump_iv_info (dump_file, iv);
1193 fprintf (dump_file, "\n");
1195 return true;
1198 if (res == GRD_MAYBE_BIV)
1199 return iv_analyze_biv (op, iv);
1201 return iv_analyze_def (def, iv);
1204 /* Analyzes value VAL at INSN and stores the result to *IV. */
1206 bool
1207 iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
1209 rtx reg;
1211 /* We must find the insn in that val is used, so that we get to UD chains.
1212 Since the function is sometimes called on result of get_condition,
1213 this does not necessarily have to be directly INSN; scan also the
1214 following insns. */
1215 if (simple_reg_p (val))
1217 if (GET_CODE (val) == SUBREG)
1218 reg = SUBREG_REG (val);
1219 else
1220 reg = val;
1222 while (!df_find_use (insn, reg))
1223 insn = NEXT_INSN (insn);
1226 return iv_analyze_op (insn, val, iv);
1229 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1231 bool
1232 iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
1234 df_ref adef;
1236 adef = df_find_def (insn, def);
1237 if (!adef)
1238 return false;
1240 return iv_analyze_def (adef, iv);
1243 /* Checks whether definition of register REG in INSN is a basic induction
1244 variable. IV analysis must have been initialized (via a call to
1245 iv_analysis_loop_init) for this function to produce a result. */
1247 bool
1248 biv_p (rtx insn, rtx reg)
1250 struct rtx_iv iv;
1251 df_ref def, last_def;
1253 if (!simple_reg_p (reg))
1254 return false;
1256 def = df_find_def (insn, reg);
1257 gcc_assert (def != NULL);
1258 if (!latch_dominating_def (reg, &last_def))
1259 return false;
1260 if (last_def != def)
1261 return false;
1263 if (!iv_analyze_biv (reg, &iv))
1264 return false;
1266 return iv.step != const0_rtx;
1269 /* Calculates value of IV at ITERATION-th iteration. */
1272 get_iv_value (struct rtx_iv *iv, rtx iteration)
1274 rtx val;
1276 /* We would need to generate some if_then_else patterns, and so far
1277 it is not needed anywhere. */
1278 gcc_assert (!iv->first_special);
1280 if (iv->step != const0_rtx && iteration != const0_rtx)
1281 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1282 simplify_gen_binary (MULT, iv->extend_mode,
1283 iv->step, iteration));
1284 else
1285 val = iv->base;
1287 if (iv->extend_mode == iv->mode)
1288 return val;
1290 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1292 if (iv->extend == IV_UNKNOWN_EXTEND)
1293 return val;
1295 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1296 iv->extend_mode, val, iv->mode);
1297 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1298 simplify_gen_binary (MULT, iv->extend_mode,
1299 iv->mult, val));
1301 return val;
1304 /* Free the data for an induction variable analysis. */
1306 void
1307 iv_analysis_done (void)
1309 if (!clean_slate)
1311 clear_iv_info ();
1312 clean_slate = true;
1313 df_finish_pass (true);
1314 bivs.dispose ();
1315 free (iv_ref_table);
1316 iv_ref_table = NULL;
1317 iv_ref_table_size = 0;
1321 /* Computes inverse to X modulo (1 << MOD). */
1323 static unsigned HOST_WIDEST_INT
1324 inverse (unsigned HOST_WIDEST_INT x, int mod)
1326 unsigned HOST_WIDEST_INT mask =
1327 ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
1328 unsigned HOST_WIDEST_INT rslt = 1;
1329 int i;
1331 for (i = 0; i < mod - 1; i++)
1333 rslt = (rslt * x) & mask;
1334 x = (x * x) & mask;
1337 return rslt;
1340 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1342 static int
1343 altered_reg_used (rtx *reg, void *alt)
1345 if (!REG_P (*reg))
1346 return 0;
1348 return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
1351 /* Marks registers altered by EXPR in set ALT. */
1353 static void
1354 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1356 if (GET_CODE (expr) == SUBREG)
1357 expr = SUBREG_REG (expr);
1358 if (!REG_P (expr))
1359 return;
1361 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1364 /* Checks whether RHS is simple enough to process. */
1366 static bool
1367 simple_rhs_p (rtx rhs)
1369 rtx op0, op1;
1371 if (function_invariant_p (rhs)
1372 || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1373 return true;
1375 switch (GET_CODE (rhs))
1377 case PLUS:
1378 case MINUS:
1379 case AND:
1380 op0 = XEXP (rhs, 0);
1381 op1 = XEXP (rhs, 1);
1382 /* Allow reg OP const and reg OP reg. */
1383 if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1384 && !function_invariant_p (op0))
1385 return false;
1386 if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1387 && !function_invariant_p (op1))
1388 return false;
1390 return true;
1392 case ASHIFT:
1393 case ASHIFTRT:
1394 case LSHIFTRT:
1395 case MULT:
1396 op0 = XEXP (rhs, 0);
1397 op1 = XEXP (rhs, 1);
1398 /* Allow reg OP const. */
1399 if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1400 return false;
1401 if (!function_invariant_p (op1))
1402 return false;
1404 return true;
1406 default:
1407 return false;
1411 /* If REG has a single definition, replace it with its known value in EXPR.
1412 Callback for for_each_rtx. */
1414 static int
1415 replace_single_def_regs (rtx *reg, void *expr1)
1417 unsigned regno;
1418 df_ref adef;
1419 rtx set, src;
1420 rtx *expr = (rtx *)expr1;
1422 if (!REG_P (*reg))
1423 return 0;
1425 regno = REGNO (*reg);
1426 for (;;)
1428 rtx note;
1429 adef = DF_REG_DEF_CHAIN (regno);
1430 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1431 || DF_REF_IS_ARTIFICIAL (adef))
1432 return -1;
1434 set = single_set (DF_REF_INSN (adef));
1435 if (set == NULL || !REG_P (SET_DEST (set))
1436 || REGNO (SET_DEST (set)) != regno)
1437 return -1;
1439 note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1441 if (note && function_invariant_p (XEXP (note, 0)))
1443 src = XEXP (note, 0);
1444 break;
1446 src = SET_SRC (set);
1448 if (REG_P (src))
1450 regno = REGNO (src);
1451 continue;
1453 break;
1455 if (!function_invariant_p (src))
1456 return -1;
1458 *expr = simplify_replace_rtx (*expr, *reg, src);
1459 return 1;
1462 /* A subroutine of simplify_using_initial_values, this function examines INSN
1463 to see if it contains a suitable set that we can use to make a replacement.
1464 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1465 the set; return false otherwise. */
1467 static bool
1468 suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
1470 rtx set = single_set (insn);
1471 rtx lhs = NULL_RTX, rhs;
1473 if (!set)
1474 return false;
1476 lhs = SET_DEST (set);
1477 if (!REG_P (lhs))
1478 return false;
1480 rhs = find_reg_equal_equiv_note (insn);
1481 if (rhs)
1482 rhs = XEXP (rhs, 0);
1483 else
1484 rhs = SET_SRC (set);
1486 if (!simple_rhs_p (rhs))
1487 return false;
1489 *dest = lhs;
1490 *src = rhs;
1491 return true;
1494 /* Using the data returned by suitable_set_for_replacement, replace DEST
1495 with SRC in *EXPR and return the new expression. Also call
1496 replace_single_def_regs if the replacement changed something. */
1497 static void
1498 replace_in_expr (rtx *expr, rtx dest, rtx src)
1500 rtx old = *expr;
1501 *expr = simplify_replace_rtx (*expr, dest, src);
1502 if (old == *expr)
1503 return;
1504 while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
1505 continue;
1508 /* Checks whether A implies B. */
1510 static bool
1511 implies_p (rtx a, rtx b)
1513 rtx op0, op1, opb0, opb1, r;
1514 enum machine_mode mode;
1516 if (rtx_equal_p (a, b))
1517 return true;
1519 if (GET_CODE (a) == EQ)
1521 op0 = XEXP (a, 0);
1522 op1 = XEXP (a, 1);
1524 if (REG_P (op0)
1525 || (GET_CODE (op0) == SUBREG
1526 && REG_P (SUBREG_REG (op0))))
1528 r = simplify_replace_rtx (b, op0, op1);
1529 if (r == const_true_rtx)
1530 return true;
1533 if (REG_P (op1)
1534 || (GET_CODE (op1) == SUBREG
1535 && REG_P (SUBREG_REG (op1))))
1537 r = simplify_replace_rtx (b, op1, op0);
1538 if (r == const_true_rtx)
1539 return true;
1543 if (b == const_true_rtx)
1544 return true;
1546 if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1547 && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1548 || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1549 && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1550 return false;
1552 op0 = XEXP (a, 0);
1553 op1 = XEXP (a, 1);
1554 opb0 = XEXP (b, 0);
1555 opb1 = XEXP (b, 1);
1557 mode = GET_MODE (op0);
1558 if (mode != GET_MODE (opb0))
1559 mode = VOIDmode;
1560 else if (mode == VOIDmode)
1562 mode = GET_MODE (op1);
1563 if (mode != GET_MODE (opb1))
1564 mode = VOIDmode;
1567 /* A < B implies A + 1 <= B. */
1568 if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1569 && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1572 if (GET_CODE (a) == GT)
1574 r = op0;
1575 op0 = op1;
1576 op1 = r;
1579 if (GET_CODE (b) == GE)
1581 r = opb0;
1582 opb0 = opb1;
1583 opb1 = r;
1586 if (SCALAR_INT_MODE_P (mode)
1587 && rtx_equal_p (op1, opb1)
1588 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1589 return true;
1590 return false;
1593 /* A < B or A > B imply A != B. TODO: Likewise
1594 A + n < B implies A != B + n if neither wraps. */
1595 if (GET_CODE (b) == NE
1596 && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1597 || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1599 if (rtx_equal_p (op0, opb0)
1600 && rtx_equal_p (op1, opb1))
1601 return true;
1604 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1605 if (GET_CODE (a) == NE
1606 && op1 == const0_rtx)
1608 if ((GET_CODE (b) == GTU
1609 && opb1 == const0_rtx)
1610 || (GET_CODE (b) == GEU
1611 && opb1 == const1_rtx))
1612 return rtx_equal_p (op0, opb0);
1615 /* A != N is equivalent to A - (N + 1) <u -1. */
1616 if (GET_CODE (a) == NE
1617 && CONST_INT_P (op1)
1618 && GET_CODE (b) == LTU
1619 && opb1 == constm1_rtx
1620 && GET_CODE (opb0) == PLUS
1621 && CONST_INT_P (XEXP (opb0, 1))
1622 /* Avoid overflows. */
1623 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1624 != ((unsigned HOST_WIDE_INT)1
1625 << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1626 && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1627 return rtx_equal_p (op0, XEXP (opb0, 0));
1629 /* Likewise, A != N implies A - N > 0. */
1630 if (GET_CODE (a) == NE
1631 && CONST_INT_P (op1))
1633 if (GET_CODE (b) == GTU
1634 && GET_CODE (opb0) == PLUS
1635 && opb1 == const0_rtx
1636 && CONST_INT_P (XEXP (opb0, 1))
1637 /* Avoid overflows. */
1638 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1639 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1640 && rtx_equal_p (XEXP (opb0, 0), op0))
1641 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1642 if (GET_CODE (b) == GEU
1643 && GET_CODE (opb0) == PLUS
1644 && opb1 == const1_rtx
1645 && CONST_INT_P (XEXP (opb0, 1))
1646 /* Avoid overflows. */
1647 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1648 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1649 && rtx_equal_p (XEXP (opb0, 0), op0))
1650 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1653 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1654 if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1655 && CONST_INT_P (op1)
1656 && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1657 || INTVAL (op1) >= 0)
1658 && GET_CODE (b) == LTU
1659 && CONST_INT_P (opb1)
1660 && rtx_equal_p (op0, opb0))
1661 return INTVAL (opb1) < 0;
1663 return false;
1666 /* Canonicalizes COND so that
1668 (1) Ensure that operands are ordered according to
1669 swap_commutative_operands_p.
1670 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1671 for GE, GEU, and LEU. */
1674 canon_condition (rtx cond)
1676 rtx tem;
1677 rtx op0, op1;
1678 enum rtx_code code;
1679 enum machine_mode mode;
1681 code = GET_CODE (cond);
1682 op0 = XEXP (cond, 0);
1683 op1 = XEXP (cond, 1);
1685 if (swap_commutative_operands_p (op0, op1))
1687 code = swap_condition (code);
1688 tem = op0;
1689 op0 = op1;
1690 op1 = tem;
1693 mode = GET_MODE (op0);
1694 if (mode == VOIDmode)
1695 mode = GET_MODE (op1);
1696 gcc_assert (mode != VOIDmode);
1698 if (CONST_INT_P (op1)
1699 && GET_MODE_CLASS (mode) != MODE_CC
1700 && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1702 HOST_WIDE_INT const_val = INTVAL (op1);
1703 unsigned HOST_WIDE_INT uconst_val = const_val;
1704 unsigned HOST_WIDE_INT max_val
1705 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1707 switch (code)
1709 case LE:
1710 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1711 code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1712 break;
1714 /* When cross-compiling, const_val might be sign-extended from
1715 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1716 case GE:
1717 if ((HOST_WIDE_INT) (const_val & max_val)
1718 != (((HOST_WIDE_INT) 1
1719 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1720 code = GT, op1 = gen_int_mode (const_val - 1, mode);
1721 break;
1723 case LEU:
1724 if (uconst_val < max_val)
1725 code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1726 break;
1728 case GEU:
1729 if (uconst_val != 0)
1730 code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1731 break;
1733 default:
1734 break;
1738 if (op0 != XEXP (cond, 0)
1739 || op1 != XEXP (cond, 1)
1740 || code != GET_CODE (cond)
1741 || GET_MODE (cond) != SImode)
1742 cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1744 return cond;
1747 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1748 set of altered regs. */
1750 void
1751 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1753 rtx rev, reve, exp = *expr;
1755 /* If some register gets altered later, we do not really speak about its
1756 value at the time of comparison. */
1757 if (altered
1758 && for_each_rtx (&cond, altered_reg_used, altered))
1759 return;
1761 if (GET_CODE (cond) == EQ
1762 && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1764 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1765 return;
1768 if (!COMPARISON_P (exp))
1769 return;
1771 rev = reversed_condition (cond);
1772 reve = reversed_condition (exp);
1774 cond = canon_condition (cond);
1775 exp = canon_condition (exp);
1776 if (rev)
1777 rev = canon_condition (rev);
1778 if (reve)
1779 reve = canon_condition (reve);
1781 if (rtx_equal_p (exp, cond))
1783 *expr = const_true_rtx;
1784 return;
1787 if (rev && rtx_equal_p (exp, rev))
1789 *expr = const0_rtx;
1790 return;
1793 if (implies_p (cond, exp))
1795 *expr = const_true_rtx;
1796 return;
1799 if (reve && implies_p (cond, reve))
1801 *expr = const0_rtx;
1802 return;
1805 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1806 be false. */
1807 if (rev && implies_p (exp, rev))
1809 *expr = const0_rtx;
1810 return;
1813 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1814 if (rev && reve && implies_p (reve, rev))
1816 *expr = const_true_rtx;
1817 return;
1820 /* We would like to have some other tests here. TODO. */
1822 return;
1825 /* Use relationship between A and *B to eventually eliminate *B.
1826 OP is the operation we consider. */
1828 static void
1829 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1831 switch (op)
1833 case AND:
1834 /* If A implies *B, we may replace *B by true. */
1835 if (implies_p (a, *b))
1836 *b = const_true_rtx;
1837 break;
1839 case IOR:
1840 /* If *B implies A, we may replace *B by false. */
1841 if (implies_p (*b, a))
1842 *b = const0_rtx;
1843 break;
1845 default:
1846 gcc_unreachable ();
1850 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1851 operation we consider. */
1853 static void
1854 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1856 rtx elt;
1858 for (elt = tail; elt; elt = XEXP (elt, 1))
1859 eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1860 for (elt = tail; elt; elt = XEXP (elt, 1))
1861 eliminate_implied_condition (op, XEXP (elt, 0), head);
1864 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1865 is a list, its elements are assumed to be combined using OP. */
1867 static void
1868 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1870 bool expression_valid;
1871 rtx head, tail, insn, cond_list, last_valid_expr;
1872 rtx neutral, aggr;
1873 regset altered, this_altered;
1874 edge e;
1876 if (!*expr)
1877 return;
1879 if (CONSTANT_P (*expr))
1880 return;
1882 if (GET_CODE (*expr) == EXPR_LIST)
1884 head = XEXP (*expr, 0);
1885 tail = XEXP (*expr, 1);
1887 eliminate_implied_conditions (op, &head, tail);
1889 switch (op)
1891 case AND:
1892 neutral = const_true_rtx;
1893 aggr = const0_rtx;
1894 break;
1896 case IOR:
1897 neutral = const0_rtx;
1898 aggr = const_true_rtx;
1899 break;
1901 default:
1902 gcc_unreachable ();
1905 simplify_using_initial_values (loop, UNKNOWN, &head);
1906 if (head == aggr)
1908 XEXP (*expr, 0) = aggr;
1909 XEXP (*expr, 1) = NULL_RTX;
1910 return;
1912 else if (head == neutral)
1914 *expr = tail;
1915 simplify_using_initial_values (loop, op, expr);
1916 return;
1918 simplify_using_initial_values (loop, op, &tail);
1920 if (tail && XEXP (tail, 0) == aggr)
1922 *expr = tail;
1923 return;
1926 XEXP (*expr, 0) = head;
1927 XEXP (*expr, 1) = tail;
1928 return;
1931 gcc_assert (op == UNKNOWN);
1933 for (;;)
1934 if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
1935 break;
1936 if (CONSTANT_P (*expr))
1937 return;
1939 e = loop_preheader_edge (loop);
1940 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1941 return;
1943 altered = ALLOC_REG_SET (&reg_obstack);
1944 this_altered = ALLOC_REG_SET (&reg_obstack);
1946 expression_valid = true;
1947 last_valid_expr = *expr;
1948 cond_list = NULL_RTX;
1949 while (1)
1951 insn = BB_END (e->src);
1952 if (any_condjump_p (insn))
1954 rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1956 if (cond && (e->flags & EDGE_FALLTHRU))
1957 cond = reversed_condition (cond);
1958 if (cond)
1960 rtx old = *expr;
1961 simplify_using_condition (cond, expr, altered);
1962 if (old != *expr)
1964 rtx note;
1965 if (CONSTANT_P (*expr))
1966 goto out;
1967 for (note = cond_list; note; note = XEXP (note, 1))
1969 simplify_using_condition (XEXP (note, 0), expr, altered);
1970 if (CONSTANT_P (*expr))
1971 goto out;
1974 cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1978 FOR_BB_INSNS_REVERSE (e->src, insn)
1980 rtx src, dest;
1981 rtx old = *expr;
1983 if (!INSN_P (insn))
1984 continue;
1986 CLEAR_REG_SET (this_altered);
1987 note_stores (PATTERN (insn), mark_altered, this_altered);
1988 if (CALL_P (insn))
1990 /* Kill all call clobbered registers. */
1991 unsigned int i;
1992 hard_reg_set_iterator hrsi;
1993 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
1994 0, i, hrsi)
1995 SET_REGNO_REG_SET (this_altered, i);
1998 if (suitable_set_for_replacement (insn, &dest, &src))
2000 rtx *pnote, *pnote_next;
2002 replace_in_expr (expr, dest, src);
2003 if (CONSTANT_P (*expr))
2004 goto out;
2006 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2008 rtx note = *pnote;
2009 rtx old_cond = XEXP (note, 0);
2011 pnote_next = &XEXP (note, 1);
2012 replace_in_expr (&XEXP (note, 0), dest, src);
2014 /* We can no longer use a condition that has been simplified
2015 to a constant, and simplify_using_condition will abort if
2016 we try. */
2017 if (CONSTANT_P (XEXP (note, 0)))
2019 *pnote = *pnote_next;
2020 pnote_next = pnote;
2021 free_EXPR_LIST_node (note);
2023 /* Retry simplifications with this condition if either the
2024 expression or the condition changed. */
2025 else if (old_cond != XEXP (note, 0) || old != *expr)
2026 simplify_using_condition (XEXP (note, 0), expr, altered);
2029 else
2031 rtx *pnote, *pnote_next;
2033 /* If we did not use this insn to make a replacement, any overlap
2034 between stores in this insn and our expression will cause the
2035 expression to become invalid. */
2036 if (for_each_rtx (expr, altered_reg_used, this_altered))
2037 goto out;
2039 /* Likewise for the conditions. */
2040 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2042 rtx note = *pnote;
2043 rtx old_cond = XEXP (note, 0);
2045 pnote_next = &XEXP (note, 1);
2046 if (for_each_rtx (&old_cond, altered_reg_used, this_altered))
2048 *pnote = *pnote_next;
2049 pnote_next = pnote;
2050 free_EXPR_LIST_node (note);
2055 if (CONSTANT_P (*expr))
2056 goto out;
2058 IOR_REG_SET (altered, this_altered);
2060 /* If the expression now contains regs that have been altered, we
2061 can't return it to the caller. However, it is still valid for
2062 further simplification, so keep searching to see if we can
2063 eventually turn it into a constant. */
2064 if (for_each_rtx (expr, altered_reg_used, altered))
2065 expression_valid = false;
2066 if (expression_valid)
2067 last_valid_expr = *expr;
2070 if (!single_pred_p (e->src)
2071 || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2072 break;
2073 e = single_pred_edge (e->src);
2076 out:
2077 free_EXPR_LIST_list (&cond_list);
2078 if (!CONSTANT_P (*expr))
2079 *expr = last_valid_expr;
2080 FREE_REG_SET (altered);
2081 FREE_REG_SET (this_altered);
2084 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2085 that IV occurs as left operands of comparison COND and its signedness
2086 is SIGNED_P to DESC. */
2088 static void
2089 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
2090 enum rtx_code cond, bool signed_p, struct niter_desc *desc)
2092 rtx mmin, mmax, cond_over, cond_under;
2094 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2095 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2096 iv->base, mmin);
2097 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2098 iv->base, mmax);
2100 switch (cond)
2102 case LE:
2103 case LT:
2104 case LEU:
2105 case LTU:
2106 if (cond_under != const0_rtx)
2107 desc->infinite =
2108 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2109 if (cond_over != const0_rtx)
2110 desc->noloop_assumptions =
2111 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2112 break;
2114 case GE:
2115 case GT:
2116 case GEU:
2117 case GTU:
2118 if (cond_over != const0_rtx)
2119 desc->infinite =
2120 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2121 if (cond_under != const0_rtx)
2122 desc->noloop_assumptions =
2123 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2124 break;
2126 case NE:
2127 if (cond_over != const0_rtx)
2128 desc->infinite =
2129 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2130 if (cond_under != const0_rtx)
2131 desc->infinite =
2132 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2133 break;
2135 default:
2136 gcc_unreachable ();
2139 iv->mode = mode;
2140 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2143 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2144 subregs of the same mode if possible (sometimes it is necessary to add
2145 some assumptions to DESC). */
2147 static bool
2148 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
2149 enum rtx_code cond, struct niter_desc *desc)
2151 enum machine_mode comp_mode;
2152 bool signed_p;
2154 /* If the ivs behave specially in the first iteration, or are
2155 added/multiplied after extending, we ignore them. */
2156 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2157 return false;
2158 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2159 return false;
2161 /* If there is some extend, it must match signedness of the comparison. */
2162 switch (cond)
2164 case LE:
2165 case LT:
2166 if (iv0->extend == IV_ZERO_EXTEND
2167 || iv1->extend == IV_ZERO_EXTEND)
2168 return false;
2169 signed_p = true;
2170 break;
2172 case LEU:
2173 case LTU:
2174 if (iv0->extend == IV_SIGN_EXTEND
2175 || iv1->extend == IV_SIGN_EXTEND)
2176 return false;
2177 signed_p = false;
2178 break;
2180 case NE:
2181 if (iv0->extend != IV_UNKNOWN_EXTEND
2182 && iv1->extend != IV_UNKNOWN_EXTEND
2183 && iv0->extend != iv1->extend)
2184 return false;
2186 signed_p = false;
2187 if (iv0->extend != IV_UNKNOWN_EXTEND)
2188 signed_p = iv0->extend == IV_SIGN_EXTEND;
2189 if (iv1->extend != IV_UNKNOWN_EXTEND)
2190 signed_p = iv1->extend == IV_SIGN_EXTEND;
2191 break;
2193 default:
2194 gcc_unreachable ();
2197 /* Values of both variables should be computed in the same mode. These
2198 might indeed be different, if we have comparison like
2200 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2202 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2203 in different modes. This does not seem impossible to handle, but
2204 it hardly ever occurs in practice.
2206 The only exception is the case when one of operands is invariant.
2207 For example pentium 3 generates comparisons like
2208 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2209 definitely do not want this prevent the optimization. */
2210 comp_mode = iv0->extend_mode;
2211 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2212 comp_mode = iv1->extend_mode;
2214 if (iv0->extend_mode != comp_mode)
2216 if (iv0->mode != iv0->extend_mode
2217 || iv0->step != const0_rtx)
2218 return false;
2220 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2221 comp_mode, iv0->base, iv0->mode);
2222 iv0->extend_mode = comp_mode;
2225 if (iv1->extend_mode != comp_mode)
2227 if (iv1->mode != iv1->extend_mode
2228 || iv1->step != const0_rtx)
2229 return false;
2231 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2232 comp_mode, iv1->base, iv1->mode);
2233 iv1->extend_mode = comp_mode;
2236 /* Check that both ivs belong to a range of a single mode. If one of the
2237 operands is an invariant, we may need to shorten it into the common
2238 mode. */
2239 if (iv0->mode == iv0->extend_mode
2240 && iv0->step == const0_rtx
2241 && iv0->mode != iv1->mode)
2242 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2244 if (iv1->mode == iv1->extend_mode
2245 && iv1->step == const0_rtx
2246 && iv0->mode != iv1->mode)
2247 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2249 if (iv0->mode != iv1->mode)
2250 return false;
2252 desc->mode = iv0->mode;
2253 desc->signed_p = signed_p;
2255 return true;
2258 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2259 result. This function is called from iv_number_of_iterations with
2260 a number of fields in DESC already filled in. OLD_NITER is the original
2261 expression for the number of iterations, before we tried to simplify it. */
2263 static unsigned HOST_WIDEST_INT
2264 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
2266 rtx niter = desc->niter_expr;
2267 rtx mmin, mmax, cmp;
2268 unsigned HOST_WIDEST_INT nmax, inc;
2269 unsigned HOST_WIDEST_INT andmax = 0;
2271 /* We used to look for constant operand 0 of AND,
2272 but canonicalization should always make this impossible. */
2273 gcc_checking_assert (GET_CODE (niter) != AND
2274 || !CONST_INT_P (XEXP (niter, 0)));
2276 if (GET_CODE (niter) == AND
2277 && CONST_INT_P (XEXP (niter, 1)))
2279 andmax = UINTVAL (XEXP (niter, 1));
2280 niter = XEXP (niter, 0);
2283 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2284 nmax = INTVAL (mmax) - INTVAL (mmin);
2286 if (GET_CODE (niter) == UDIV)
2288 if (!CONST_INT_P (XEXP (niter, 1)))
2289 return nmax;
2290 inc = INTVAL (XEXP (niter, 1));
2291 niter = XEXP (niter, 0);
2293 else
2294 inc = 1;
2296 /* We could use a binary search here, but for now improving the upper
2297 bound by just one eliminates one important corner case. */
2298 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2299 desc->mode, old_niter, mmax);
2300 simplify_using_initial_values (loop, UNKNOWN, &cmp);
2301 if (cmp == const_true_rtx)
2303 nmax--;
2305 if (dump_file)
2306 fprintf (dump_file, ";; improved upper bound by one.\n");
2308 nmax /= inc;
2309 if (andmax)
2310 nmax = MIN (nmax, andmax);
2311 if (dump_file)
2312 fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n",
2313 nmax);
2314 return nmax;
2317 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2318 the result into DESC. Very similar to determine_number_of_iterations
2319 (basically its rtl version), complicated by things like subregs. */
2321 static void
2322 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2323 struct niter_desc *desc)
2325 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2326 struct rtx_iv iv0, iv1, tmp_iv;
2327 rtx assumption, may_not_xform;
2328 enum rtx_code cond;
2329 enum machine_mode mode, comp_mode;
2330 rtx mmin, mmax, mode_mmin, mode_mmax;
2331 unsigned HOST_WIDEST_INT s, size, d, inv, max;
2332 HOST_WIDEST_INT up, down, inc, step_val;
2333 int was_sharp = false;
2334 rtx old_niter;
2335 bool step_is_pow2;
2337 /* The meaning of these assumptions is this:
2338 if !assumptions
2339 then the rest of information does not have to be valid
2340 if noloop_assumptions then the loop does not roll
2341 if infinite then this exit is never used */
2343 desc->assumptions = NULL_RTX;
2344 desc->noloop_assumptions = NULL_RTX;
2345 desc->infinite = NULL_RTX;
2346 desc->simple_p = true;
2348 desc->const_iter = false;
2349 desc->niter_expr = NULL_RTX;
2351 cond = GET_CODE (condition);
2352 gcc_assert (COMPARISON_P (condition));
2354 mode = GET_MODE (XEXP (condition, 0));
2355 if (mode == VOIDmode)
2356 mode = GET_MODE (XEXP (condition, 1));
2357 /* The constant comparisons should be folded. */
2358 gcc_assert (mode != VOIDmode);
2360 /* We only handle integers or pointers. */
2361 if (GET_MODE_CLASS (mode) != MODE_INT
2362 && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2363 goto fail;
2365 op0 = XEXP (condition, 0);
2366 if (!iv_analyze (insn, op0, &iv0))
2367 goto fail;
2368 if (iv0.extend_mode == VOIDmode)
2369 iv0.mode = iv0.extend_mode = mode;
2371 op1 = XEXP (condition, 1);
2372 if (!iv_analyze (insn, op1, &iv1))
2373 goto fail;
2374 if (iv1.extend_mode == VOIDmode)
2375 iv1.mode = iv1.extend_mode = mode;
2377 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2378 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2379 goto fail;
2381 /* Check condition and normalize it. */
2383 switch (cond)
2385 case GE:
2386 case GT:
2387 case GEU:
2388 case GTU:
2389 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2390 cond = swap_condition (cond);
2391 break;
2392 case NE:
2393 case LE:
2394 case LEU:
2395 case LT:
2396 case LTU:
2397 break;
2398 default:
2399 goto fail;
2402 /* Handle extends. This is relatively nontrivial, so we only try in some
2403 easy cases, when we can canonicalize the ivs (possibly by adding some
2404 assumptions) to shape subreg (base + i * step). This function also fills
2405 in desc->mode and desc->signed_p. */
2407 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2408 goto fail;
2410 comp_mode = iv0.extend_mode;
2411 mode = iv0.mode;
2412 size = GET_MODE_BITSIZE (mode);
2413 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2414 mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2415 mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2417 if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2418 goto fail;
2420 /* We can take care of the case of two induction variables chasing each other
2421 if the test is NE. I have never seen a loop using it, but still it is
2422 cool. */
2423 if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2425 if (cond != NE)
2426 goto fail;
2428 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2429 iv1.step = const0_rtx;
2432 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2433 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2435 /* This is either infinite loop or the one that ends immediately, depending
2436 on initial values. Unswitching should remove this kind of conditions. */
2437 if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2438 goto fail;
2440 if (cond != NE)
2442 if (iv0.step == const0_rtx)
2443 step_val = -INTVAL (iv1.step);
2444 else
2445 step_val = INTVAL (iv0.step);
2447 /* Ignore loops of while (i-- < 10) type. */
2448 if (step_val < 0)
2449 goto fail;
2451 step_is_pow2 = !(step_val & (step_val - 1));
2453 else
2455 /* We do not care about whether the step is power of two in this
2456 case. */
2457 step_is_pow2 = false;
2458 step_val = 0;
2461 /* Some more condition normalization. We must record some assumptions
2462 due to overflows. */
2463 switch (cond)
2465 case LT:
2466 case LTU:
2467 /* We want to take care only of non-sharp relationals; this is easy,
2468 as in cases the overflow would make the transformation unsafe
2469 the loop does not roll. Seemingly it would make more sense to want
2470 to take care of sharp relationals instead, as NE is more similar to
2471 them, but the problem is that here the transformation would be more
2472 difficult due to possibly infinite loops. */
2473 if (iv0.step == const0_rtx)
2475 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2476 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2477 mode_mmax);
2478 if (assumption == const_true_rtx)
2479 goto zero_iter_simplify;
2480 iv0.base = simplify_gen_binary (PLUS, comp_mode,
2481 iv0.base, const1_rtx);
2483 else
2485 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2486 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2487 mode_mmin);
2488 if (assumption == const_true_rtx)
2489 goto zero_iter_simplify;
2490 iv1.base = simplify_gen_binary (PLUS, comp_mode,
2491 iv1.base, constm1_rtx);
2494 if (assumption != const0_rtx)
2495 desc->noloop_assumptions =
2496 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2497 cond = (cond == LT) ? LE : LEU;
2499 /* It will be useful to be able to tell the difference once more in
2500 LE -> NE reduction. */
2501 was_sharp = true;
2502 break;
2503 default: ;
2506 /* Take care of trivially infinite loops. */
2507 if (cond != NE)
2509 if (iv0.step == const0_rtx)
2511 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2512 if (rtx_equal_p (tmp, mode_mmin))
2514 desc->infinite =
2515 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2516 /* Fill in the remaining fields somehow. */
2517 goto zero_iter_simplify;
2520 else
2522 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2523 if (rtx_equal_p (tmp, mode_mmax))
2525 desc->infinite =
2526 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2527 /* Fill in the remaining fields somehow. */
2528 goto zero_iter_simplify;
2533 /* If we can we want to take care of NE conditions instead of size
2534 comparisons, as they are much more friendly (most importantly
2535 this takes care of special handling of loops with step 1). We can
2536 do it if we first check that upper bound is greater or equal to
2537 lower bound, their difference is constant c modulo step and that
2538 there is not an overflow. */
2539 if (cond != NE)
2541 if (iv0.step == const0_rtx)
2542 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2543 else
2544 step = iv0.step;
2545 step = lowpart_subreg (mode, step, comp_mode);
2546 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2547 delta = lowpart_subreg (mode, delta, comp_mode);
2548 delta = simplify_gen_binary (UMOD, mode, delta, step);
2549 may_xform = const0_rtx;
2550 may_not_xform = const_true_rtx;
2552 if (CONST_INT_P (delta))
2554 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2556 /* A special case. We have transformed condition of type
2557 for (i = 0; i < 4; i += 4)
2558 into
2559 for (i = 0; i <= 3; i += 4)
2560 obviously if the test for overflow during that transformation
2561 passed, we cannot overflow here. Most importantly any
2562 loop with sharp end condition and step 1 falls into this
2563 category, so handling this case specially is definitely
2564 worth the troubles. */
2565 may_xform = const_true_rtx;
2567 else if (iv0.step == const0_rtx)
2569 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2570 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2571 bound = lowpart_subreg (mode, bound, comp_mode);
2572 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2573 may_xform = simplify_gen_relational (cond, SImode, mode,
2574 bound, tmp);
2575 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2576 SImode, mode,
2577 bound, tmp);
2579 else
2581 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2582 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2583 bound = lowpart_subreg (mode, bound, comp_mode);
2584 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2585 may_xform = simplify_gen_relational (cond, SImode, mode,
2586 tmp, bound);
2587 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2588 SImode, mode,
2589 tmp, bound);
2593 if (may_xform != const0_rtx)
2595 /* We perform the transformation always provided that it is not
2596 completely senseless. This is OK, as we would need this assumption
2597 to determine the number of iterations anyway. */
2598 if (may_xform != const_true_rtx)
2600 /* If the step is a power of two and the final value we have
2601 computed overflows, the cycle is infinite. Otherwise it
2602 is nontrivial to compute the number of iterations. */
2603 if (step_is_pow2)
2604 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2605 desc->infinite);
2606 else
2607 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2608 desc->assumptions);
2611 /* We are going to lose some information about upper bound on
2612 number of iterations in this step, so record the information
2613 here. */
2614 inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2615 if (CONST_INT_P (iv1.base))
2616 up = INTVAL (iv1.base);
2617 else
2618 up = INTVAL (mode_mmax) - inc;
2619 down = INTVAL (CONST_INT_P (iv0.base)
2620 ? iv0.base
2621 : mode_mmin);
2622 max = (up - down) / inc + 1;
2623 if (!desc->infinite
2624 && !desc->assumptions)
2625 record_niter_bound (loop, double_int::from_uhwi (max),
2626 false, true);
2628 if (iv0.step == const0_rtx)
2630 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2631 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2633 else
2635 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2636 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2639 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2640 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2641 assumption = simplify_gen_relational (reverse_condition (cond),
2642 SImode, mode, tmp0, tmp1);
2643 if (assumption == const_true_rtx)
2644 goto zero_iter_simplify;
2645 else if (assumption != const0_rtx)
2646 desc->noloop_assumptions =
2647 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2648 cond = NE;
2652 /* Count the number of iterations. */
2653 if (cond == NE)
2655 /* Everything we do here is just arithmetics modulo size of mode. This
2656 makes us able to do more involved computations of number of iterations
2657 than in other cases. First transform the condition into shape
2658 s * i <> c, with s positive. */
2659 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2660 iv0.base = const0_rtx;
2661 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2662 iv1.step = const0_rtx;
2663 if (INTVAL (iv0.step) < 0)
2665 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2666 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2668 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2670 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2671 is infinite. Otherwise, the number of iterations is
2672 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2673 s = INTVAL (iv0.step); d = 1;
2674 while (s % 2 != 1)
2676 s /= 2;
2677 d *= 2;
2678 size--;
2680 bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2682 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2683 tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2684 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2685 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2687 tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2688 inv = inverse (s, size);
2689 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2690 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2692 else
2694 if (iv1.step == const0_rtx)
2695 /* Condition in shape a + s * i <= b
2696 We must know that b + s does not overflow and a <= b + s and then we
2697 can compute number of iterations as (b + s - a) / s. (It might
2698 seem that we in fact could be more clever about testing the b + s
2699 overflow condition using some information about b - a mod s,
2700 but it was already taken into account during LE -> NE transform). */
2702 step = iv0.step;
2703 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2704 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2706 bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2707 lowpart_subreg (mode, step,
2708 comp_mode));
2709 if (step_is_pow2)
2711 rtx t0, t1;
2713 /* If s is power of 2, we know that the loop is infinite if
2714 a % s <= b % s and b + s overflows. */
2715 assumption = simplify_gen_relational (reverse_condition (cond),
2716 SImode, mode,
2717 tmp1, bound);
2719 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2720 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2721 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2722 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2723 desc->infinite =
2724 alloc_EXPR_LIST (0, assumption, desc->infinite);
2726 else
2728 assumption = simplify_gen_relational (cond, SImode, mode,
2729 tmp1, bound);
2730 desc->assumptions =
2731 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2734 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2735 tmp = lowpart_subreg (mode, tmp, comp_mode);
2736 assumption = simplify_gen_relational (reverse_condition (cond),
2737 SImode, mode, tmp0, tmp);
2739 delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2740 delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2742 else
2744 /* Condition in shape a <= b - s * i
2745 We must know that a - s does not overflow and a - s <= b and then
2746 we can again compute number of iterations as (b - (a - s)) / s. */
2747 step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2748 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2749 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2751 bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2752 lowpart_subreg (mode, step, comp_mode));
2753 if (step_is_pow2)
2755 rtx t0, t1;
2757 /* If s is power of 2, we know that the loop is infinite if
2758 a % s <= b % s and a - s overflows. */
2759 assumption = simplify_gen_relational (reverse_condition (cond),
2760 SImode, mode,
2761 bound, tmp0);
2763 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2764 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2765 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2766 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2767 desc->infinite =
2768 alloc_EXPR_LIST (0, assumption, desc->infinite);
2770 else
2772 assumption = simplify_gen_relational (cond, SImode, mode,
2773 bound, tmp0);
2774 desc->assumptions =
2775 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2778 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2779 tmp = lowpart_subreg (mode, tmp, comp_mode);
2780 assumption = simplify_gen_relational (reverse_condition (cond),
2781 SImode, mode,
2782 tmp, tmp1);
2783 delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2784 delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2786 if (assumption == const_true_rtx)
2787 goto zero_iter_simplify;
2788 else if (assumption != const0_rtx)
2789 desc->noloop_assumptions =
2790 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2791 delta = simplify_gen_binary (UDIV, mode, delta, step);
2792 desc->niter_expr = delta;
2795 old_niter = desc->niter_expr;
2797 simplify_using_initial_values (loop, AND, &desc->assumptions);
2798 if (desc->assumptions
2799 && XEXP (desc->assumptions, 0) == const0_rtx)
2800 goto fail;
2801 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2802 simplify_using_initial_values (loop, IOR, &desc->infinite);
2803 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2805 /* Rerun the simplification. Consider code (created by copying loop headers)
2807 i = 0;
2809 if (0 < n)
2813 i++;
2814 } while (i < n);
2817 The first pass determines that i = 0, the second pass uses it to eliminate
2818 noloop assumption. */
2820 simplify_using_initial_values (loop, AND, &desc->assumptions);
2821 if (desc->assumptions
2822 && XEXP (desc->assumptions, 0) == const0_rtx)
2823 goto fail;
2824 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2825 simplify_using_initial_values (loop, IOR, &desc->infinite);
2826 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2828 if (desc->noloop_assumptions
2829 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2830 goto zero_iter;
2832 if (CONST_INT_P (desc->niter_expr))
2834 unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2836 desc->const_iter = true;
2837 desc->niter = val & GET_MODE_MASK (desc->mode);
2838 if (!desc->infinite
2839 && !desc->assumptions)
2840 record_niter_bound (loop, double_int::from_uhwi (desc->niter),
2841 false, true);
2843 else
2845 max = determine_max_iter (loop, desc, old_niter);
2846 if (!max)
2847 goto zero_iter_simplify;
2848 if (!desc->infinite
2849 && !desc->assumptions)
2850 record_niter_bound (loop, double_int::from_uhwi (max),
2851 false, true);
2853 /* simplify_using_initial_values does a copy propagation on the registers
2854 in the expression for the number of iterations. This prolongs life
2855 ranges of registers and increases register pressure, and usually
2856 brings no gain (and if it happens to do, the cse pass will take care
2857 of it anyway). So prevent this behavior, unless it enabled us to
2858 derive that the number of iterations is a constant. */
2859 desc->niter_expr = old_niter;
2862 return;
2864 zero_iter_simplify:
2865 /* Simplify the assumptions. */
2866 simplify_using_initial_values (loop, AND, &desc->assumptions);
2867 if (desc->assumptions
2868 && XEXP (desc->assumptions, 0) == const0_rtx)
2869 goto fail;
2870 simplify_using_initial_values (loop, IOR, &desc->infinite);
2872 /* Fallthru. */
2873 zero_iter:
2874 desc->const_iter = true;
2875 desc->niter = 0;
2876 record_niter_bound (loop, double_int_zero,
2877 true, true);
2878 desc->noloop_assumptions = NULL_RTX;
2879 desc->niter_expr = const0_rtx;
2880 return;
2882 fail:
2883 desc->simple_p = false;
2884 return;
2887 /* Checks whether E is a simple exit from LOOP and stores its description
2888 into DESC. */
2890 static void
2891 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2893 basic_block exit_bb;
2894 rtx condition, at;
2895 edge ein;
2897 exit_bb = e->src;
2898 desc->simple_p = false;
2900 /* It must belong directly to the loop. */
2901 if (exit_bb->loop_father != loop)
2902 return;
2904 /* It must be tested (at least) once during any iteration. */
2905 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2906 return;
2908 /* It must end in a simple conditional jump. */
2909 if (!any_condjump_p (BB_END (exit_bb)))
2910 return;
2912 ein = EDGE_SUCC (exit_bb, 0);
2913 if (ein == e)
2914 ein = EDGE_SUCC (exit_bb, 1);
2916 desc->out_edge = e;
2917 desc->in_edge = ein;
2919 /* Test whether the condition is suitable. */
2920 if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2921 return;
2923 if (ein->flags & EDGE_FALLTHRU)
2925 condition = reversed_condition (condition);
2926 if (!condition)
2927 return;
2930 /* Check that we are able to determine number of iterations and fill
2931 in information about it. */
2932 iv_number_of_iterations (loop, at, condition, desc);
2935 /* Finds a simple exit of LOOP and stores its description into DESC. */
2937 void
2938 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2940 unsigned i;
2941 basic_block *body;
2942 edge e;
2943 struct niter_desc act;
2944 bool any = false;
2945 edge_iterator ei;
2947 desc->simple_p = false;
2948 body = get_loop_body (loop);
2950 for (i = 0; i < loop->num_nodes; i++)
2952 FOR_EACH_EDGE (e, ei, body[i]->succs)
2954 if (flow_bb_inside_loop_p (loop, e->dest))
2955 continue;
2957 check_simple_exit (loop, e, &act);
2958 if (!act.simple_p)
2959 continue;
2961 if (!any)
2962 any = true;
2963 else
2965 /* Prefer constant iterations; the less the better. */
2966 if (!act.const_iter
2967 || (desc->const_iter && act.niter >= desc->niter))
2968 continue;
2970 /* Also if the actual exit may be infinite, while the old one
2971 not, prefer the old one. */
2972 if (act.infinite && !desc->infinite)
2973 continue;
2976 *desc = act;
2980 if (dump_file)
2982 if (desc->simple_p)
2984 fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2985 fprintf (dump_file, " simple exit %d -> %d\n",
2986 desc->out_edge->src->index,
2987 desc->out_edge->dest->index);
2988 if (desc->assumptions)
2990 fprintf (dump_file, " assumptions: ");
2991 print_rtl (dump_file, desc->assumptions);
2992 fprintf (dump_file, "\n");
2994 if (desc->noloop_assumptions)
2996 fprintf (dump_file, " does not roll if: ");
2997 print_rtl (dump_file, desc->noloop_assumptions);
2998 fprintf (dump_file, "\n");
3000 if (desc->infinite)
3002 fprintf (dump_file, " infinite if: ");
3003 print_rtl (dump_file, desc->infinite);
3004 fprintf (dump_file, "\n");
3007 fprintf (dump_file, " number of iterations: ");
3008 print_rtl (dump_file, desc->niter_expr);
3009 fprintf (dump_file, "\n");
3011 fprintf (dump_file, " upper bound: %li\n",
3012 (long)get_max_loop_iterations_int (loop));
3013 fprintf (dump_file, " realistic bound: %li\n",
3014 (long)get_estimated_loop_iterations_int (loop));
3016 else
3017 fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
3020 free (body);
3023 /* Creates a simple loop description of LOOP if it was not computed
3024 already. */
3026 struct niter_desc *
3027 get_simple_loop_desc (struct loop *loop)
3029 struct niter_desc *desc = simple_loop_desc (loop);
3031 if (desc)
3032 return desc;
3034 /* At least desc->infinite is not always initialized by
3035 find_simple_loop_exit. */
3036 desc = ggc_alloc_cleared_niter_desc ();
3037 iv_analysis_loop_init (loop);
3038 find_simple_exit (loop, desc);
3039 loop->simple_loop_desc = desc;
3041 if (desc->simple_p && (desc->assumptions || desc->infinite))
3043 const char *wording;
3045 /* Assume that no overflow happens and that the loop is finite.
3046 We already warned at the tree level if we ran optimizations there. */
3047 if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
3049 if (desc->infinite)
3051 wording =
3052 flag_unsafe_loop_optimizations
3053 ? N_("assuming that the loop is not infinite")
3054 : N_("cannot optimize possibly infinite loops");
3055 warning (OPT_Wunsafe_loop_optimizations, "%s",
3056 gettext (wording));
3058 if (desc->assumptions)
3060 wording =
3061 flag_unsafe_loop_optimizations
3062 ? N_("assuming that the loop counter does not overflow")
3063 : N_("cannot optimize loop, the loop counter may overflow");
3064 warning (OPT_Wunsafe_loop_optimizations, "%s",
3065 gettext (wording));
3069 if (flag_unsafe_loop_optimizations)
3071 desc->assumptions = NULL_RTX;
3072 desc->infinite = NULL_RTX;
3076 return desc;
3079 /* Releases simple loop description for LOOP. */
3081 void
3082 free_simple_loop_desc (struct loop *loop)
3084 struct niter_desc *desc = simple_loop_desc (loop);
3086 if (!desc)
3087 return;
3089 ggc_free (desc);
3090 loop->simple_loop_desc = NULL;