2014-07-29 Ed Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / loop-iv.c
blob1c204e9c1dafde3197f63bf259c5176f630115c5
1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2014 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 current_loop = loop;
283 /* Clear the information from the analysis of the previous loop. */
284 if (clean_slate)
286 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
287 bivs = new hash_table<biv_entry_hasher> (10);
288 clean_slate = false;
290 else
291 clear_iv_info ();
293 /* Get rid of the ud chains before processing the rescans. Then add
294 the problem back. */
295 df_remove_problem (df_chain);
296 df_process_deferred_rescans ();
297 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
298 df_chain_add_problem (DF_UD_CHAIN);
299 df_note_add_problem ();
300 df_analyze_loop (loop);
301 if (dump_file)
302 df_dump_region (dump_file);
304 check_iv_ref_table_size ();
307 /* Finds the definition of REG that dominates loop latch and stores
308 it to DEF. Returns false if there is not a single definition
309 dominating the latch. If REG has no definition in loop, DEF
310 is set to NULL and true is returned. */
312 static bool
313 latch_dominating_def (rtx reg, df_ref *def)
315 df_ref single_rd = NULL, adef;
316 unsigned regno = REGNO (reg);
317 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
319 for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
321 if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
322 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
323 continue;
325 /* More than one reaching definition. */
326 if (single_rd)
327 return false;
329 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
330 return false;
332 single_rd = adef;
335 *def = single_rd;
336 return true;
339 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
341 static enum iv_grd_result
342 iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
344 df_ref use, adef;
345 basic_block def_bb, use_bb;
346 rtx def_insn;
347 bool dom_p;
349 *def = NULL;
350 if (!simple_reg_p (reg))
351 return GRD_INVALID;
352 if (GET_CODE (reg) == SUBREG)
353 reg = SUBREG_REG (reg);
354 gcc_assert (REG_P (reg));
356 use = df_find_use (insn, reg);
357 gcc_assert (use != NULL);
359 if (!DF_REF_CHAIN (use))
360 return GRD_INVARIANT;
362 /* More than one reaching def. */
363 if (DF_REF_CHAIN (use)->next)
364 return GRD_INVALID;
366 adef = DF_REF_CHAIN (use)->ref;
368 /* We do not handle setting only part of the register. */
369 if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
370 return GRD_INVALID;
372 def_insn = DF_REF_INSN (adef);
373 def_bb = DF_REF_BB (adef);
374 use_bb = BLOCK_FOR_INSN (insn);
376 if (use_bb == def_bb)
377 dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
378 else
379 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
381 if (dom_p)
383 *def = adef;
384 return GRD_SINGLE_DOM;
387 /* The definition does not dominate the use. This is still OK if
388 this may be a use of a biv, i.e. if the def_bb dominates loop
389 latch. */
390 if (just_once_each_iteration_p (current_loop, def_bb))
391 return GRD_MAYBE_BIV;
393 return GRD_INVALID;
396 /* Sets IV to invariant CST in MODE. Always returns true (just for
397 consistency with other iv manipulation functions that may fail). */
399 static bool
400 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
402 if (mode == VOIDmode)
403 mode = GET_MODE (cst);
405 iv->mode = mode;
406 iv->base = cst;
407 iv->step = const0_rtx;
408 iv->first_special = false;
409 iv->extend = IV_UNKNOWN_EXTEND;
410 iv->extend_mode = iv->mode;
411 iv->delta = const0_rtx;
412 iv->mult = const1_rtx;
414 return true;
417 /* Evaluates application of subreg to MODE on IV. */
419 static bool
420 iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
422 /* If iv is invariant, just calculate the new value. */
423 if (iv->step == const0_rtx
424 && !iv->first_special)
426 rtx val = get_iv_value (iv, const0_rtx);
427 val = lowpart_subreg (mode, val,
428 iv->extend == IV_UNKNOWN_EXTEND
429 ? iv->mode : iv->extend_mode);
431 iv->base = val;
432 iv->extend = IV_UNKNOWN_EXTEND;
433 iv->mode = iv->extend_mode = mode;
434 iv->delta = const0_rtx;
435 iv->mult = const1_rtx;
436 return true;
439 if (iv->extend_mode == mode)
440 return true;
442 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
443 return false;
445 iv->extend = IV_UNKNOWN_EXTEND;
446 iv->mode = mode;
448 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
449 simplify_gen_binary (MULT, iv->extend_mode,
450 iv->base, iv->mult));
451 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
452 iv->mult = const1_rtx;
453 iv->delta = const0_rtx;
454 iv->first_special = false;
456 return true;
459 /* Evaluates application of EXTEND to MODE on IV. */
461 static bool
462 iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode)
464 /* If iv is invariant, just calculate the new value. */
465 if (iv->step == const0_rtx
466 && !iv->first_special)
468 rtx val = get_iv_value (iv, const0_rtx);
469 if (iv->extend_mode != iv->mode
470 && iv->extend != IV_UNKNOWN_EXTEND
471 && iv->extend != extend)
472 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
473 val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
474 val,
475 iv->extend == extend
476 ? iv->extend_mode : iv->mode);
477 iv->base = val;
478 iv->extend = IV_UNKNOWN_EXTEND;
479 iv->mode = iv->extend_mode = mode;
480 iv->delta = const0_rtx;
481 iv->mult = const1_rtx;
482 return true;
485 if (mode != iv->extend_mode)
486 return false;
488 if (iv->extend != IV_UNKNOWN_EXTEND
489 && iv->extend != extend)
490 return false;
492 iv->extend = extend;
494 return true;
497 /* Evaluates negation of IV. */
499 static bool
500 iv_neg (struct rtx_iv *iv)
502 if (iv->extend == IV_UNKNOWN_EXTEND)
504 iv->base = simplify_gen_unary (NEG, iv->extend_mode,
505 iv->base, iv->extend_mode);
506 iv->step = simplify_gen_unary (NEG, iv->extend_mode,
507 iv->step, iv->extend_mode);
509 else
511 iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
512 iv->delta, iv->extend_mode);
513 iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
514 iv->mult, iv->extend_mode);
517 return true;
520 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
522 static bool
523 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
525 enum machine_mode mode;
526 rtx arg;
528 /* Extend the constant to extend_mode of the other operand if necessary. */
529 if (iv0->extend == IV_UNKNOWN_EXTEND
530 && iv0->mode == iv0->extend_mode
531 && iv0->step == const0_rtx
532 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
534 iv0->extend_mode = iv1->extend_mode;
535 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
536 iv0->base, iv0->mode);
538 if (iv1->extend == IV_UNKNOWN_EXTEND
539 && iv1->mode == iv1->extend_mode
540 && iv1->step == const0_rtx
541 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
543 iv1->extend_mode = iv0->extend_mode;
544 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
545 iv1->base, iv1->mode);
548 mode = iv0->extend_mode;
549 if (mode != iv1->extend_mode)
550 return false;
552 if (iv0->extend == IV_UNKNOWN_EXTEND
553 && iv1->extend == IV_UNKNOWN_EXTEND)
555 if (iv0->mode != iv1->mode)
556 return false;
558 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
559 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
561 return true;
564 /* Handle addition of constant. */
565 if (iv1->extend == IV_UNKNOWN_EXTEND
566 && iv1->mode == mode
567 && iv1->step == const0_rtx)
569 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
570 return true;
573 if (iv0->extend == IV_UNKNOWN_EXTEND
574 && iv0->mode == mode
575 && iv0->step == const0_rtx)
577 arg = iv0->base;
578 *iv0 = *iv1;
579 if (op == MINUS
580 && !iv_neg (iv0))
581 return false;
583 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
584 return true;
587 return false;
590 /* Evaluates multiplication of IV by constant CST. */
592 static bool
593 iv_mult (struct rtx_iv *iv, rtx mby)
595 enum machine_mode mode = iv->extend_mode;
597 if (GET_MODE (mby) != VOIDmode
598 && GET_MODE (mby) != mode)
599 return false;
601 if (iv->extend == IV_UNKNOWN_EXTEND)
603 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
604 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
606 else
608 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
609 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
612 return true;
615 /* Evaluates shift of IV by constant CST. */
617 static bool
618 iv_shift (struct rtx_iv *iv, rtx mby)
620 enum machine_mode mode = iv->extend_mode;
622 if (GET_MODE (mby) != VOIDmode
623 && GET_MODE (mby) != mode)
624 return false;
626 if (iv->extend == IV_UNKNOWN_EXTEND)
628 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
629 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
631 else
633 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
634 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
637 return true;
640 /* The recursive part of get_biv_step. Gets the value of the single value
641 defined by DEF wrto initial value of REG inside loop, in shape described
642 at get_biv_step. */
644 static bool
645 get_biv_step_1 (df_ref def, rtx reg,
646 rtx *inner_step, enum machine_mode *inner_mode,
647 enum iv_extend_code *extend, enum machine_mode outer_mode,
648 rtx *outer_step)
650 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
651 rtx next, nextr, tmp;
652 enum rtx_code code;
653 rtx insn = DF_REF_INSN (def);
654 df_ref next_def;
655 enum iv_grd_result res;
657 set = single_set (insn);
658 if (!set)
659 return false;
661 rhs = find_reg_equal_equiv_note (insn);
662 if (rhs)
663 rhs = XEXP (rhs, 0);
664 else
665 rhs = SET_SRC (set);
667 code = GET_CODE (rhs);
668 switch (code)
670 case SUBREG:
671 case REG:
672 next = rhs;
673 break;
675 case PLUS:
676 case MINUS:
677 op0 = XEXP (rhs, 0);
678 op1 = XEXP (rhs, 1);
680 if (code == PLUS && CONSTANT_P (op0))
682 tmp = op0; op0 = op1; op1 = tmp;
685 if (!simple_reg_p (op0)
686 || !CONSTANT_P (op1))
687 return false;
689 if (GET_MODE (rhs) != outer_mode)
691 /* ppc64 uses expressions like
693 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
695 this is equivalent to
697 (set x':DI (plus:DI y:DI 1))
698 (set x:SI (subreg:SI (x':DI)). */
699 if (GET_CODE (op0) != SUBREG)
700 return false;
701 if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
702 return false;
705 next = op0;
706 break;
708 case SIGN_EXTEND:
709 case ZERO_EXTEND:
710 if (GET_MODE (rhs) != outer_mode)
711 return false;
713 op0 = XEXP (rhs, 0);
714 if (!simple_reg_p (op0))
715 return false;
717 next = op0;
718 break;
720 default:
721 return false;
724 if (GET_CODE (next) == SUBREG)
726 if (!subreg_lowpart_p (next))
727 return false;
729 nextr = SUBREG_REG (next);
730 if (GET_MODE (nextr) != outer_mode)
731 return false;
733 else
734 nextr = next;
736 res = iv_get_reaching_def (insn, nextr, &next_def);
738 if (res == GRD_INVALID || res == GRD_INVARIANT)
739 return false;
741 if (res == GRD_MAYBE_BIV)
743 if (!rtx_equal_p (nextr, reg))
744 return false;
746 *inner_step = const0_rtx;
747 *extend = IV_UNKNOWN_EXTEND;
748 *inner_mode = outer_mode;
749 *outer_step = const0_rtx;
751 else if (!get_biv_step_1 (next_def, reg,
752 inner_step, inner_mode, extend, outer_mode,
753 outer_step))
754 return false;
756 if (GET_CODE (next) == SUBREG)
758 enum machine_mode amode = GET_MODE (next);
760 if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
761 return false;
763 *inner_mode = amode;
764 *inner_step = simplify_gen_binary (PLUS, outer_mode,
765 *inner_step, *outer_step);
766 *outer_step = const0_rtx;
767 *extend = IV_UNKNOWN_EXTEND;
770 switch (code)
772 case REG:
773 case SUBREG:
774 break;
776 case PLUS:
777 case MINUS:
778 if (*inner_mode == outer_mode
779 /* See comment in previous switch. */
780 || GET_MODE (rhs) != outer_mode)
781 *inner_step = simplify_gen_binary (code, outer_mode,
782 *inner_step, op1);
783 else
784 *outer_step = simplify_gen_binary (code, outer_mode,
785 *outer_step, op1);
786 break;
788 case SIGN_EXTEND:
789 case ZERO_EXTEND:
790 gcc_assert (GET_MODE (op0) == *inner_mode
791 && *extend == IV_UNKNOWN_EXTEND
792 && *outer_step == const0_rtx);
794 *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
795 break;
797 default:
798 return false;
801 return true;
804 /* Gets the operation on register REG inside loop, in shape
806 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
808 If the operation cannot be described in this shape, return false.
809 LAST_DEF is the definition of REG that dominates loop latch. */
811 static bool
812 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
813 enum machine_mode *inner_mode, enum iv_extend_code *extend,
814 enum machine_mode *outer_mode, rtx *outer_step)
816 *outer_mode = GET_MODE (reg);
818 if (!get_biv_step_1 (last_def, reg,
819 inner_step, inner_mode, extend, *outer_mode,
820 outer_step))
821 return false;
823 gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
824 gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
826 return true;
829 /* Records information that DEF is induction variable IV. */
831 static void
832 record_iv (df_ref def, struct rtx_iv *iv)
834 struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
836 *recorded_iv = *iv;
837 check_iv_ref_table_size ();
838 DF_REF_IV_SET (def, recorded_iv);
841 /* If DEF was already analyzed for bivness, store the description of the biv to
842 IV and return true. Otherwise return false. */
844 static bool
845 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
847 struct biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
849 if (!biv)
850 return false;
852 *iv = biv->iv;
853 return true;
856 static void
857 record_biv (rtx def, struct rtx_iv *iv)
859 struct biv_entry *biv = XNEW (struct biv_entry);
860 biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
862 biv->regno = REGNO (def);
863 biv->iv = *iv;
864 gcc_assert (!*slot);
865 *slot = biv;
868 /* Determines whether DEF is a biv and if so, stores its description
869 to *IV. */
871 static bool
872 iv_analyze_biv (rtx def, struct rtx_iv *iv)
874 rtx inner_step, outer_step;
875 enum machine_mode inner_mode, outer_mode;
876 enum iv_extend_code extend;
877 df_ref last_def;
879 if (dump_file)
881 fprintf (dump_file, "Analyzing ");
882 print_rtl (dump_file, def);
883 fprintf (dump_file, " for bivness.\n");
886 if (!REG_P (def))
888 if (!CONSTANT_P (def))
889 return false;
891 return iv_constant (iv, def, VOIDmode);
894 if (!latch_dominating_def (def, &last_def))
896 if (dump_file)
897 fprintf (dump_file, " not simple.\n");
898 return false;
901 if (!last_def)
902 return iv_constant (iv, def, VOIDmode);
904 if (analyzed_for_bivness_p (def, iv))
906 if (dump_file)
907 fprintf (dump_file, " already analysed.\n");
908 return iv->base != NULL_RTX;
911 if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
912 &outer_mode, &outer_step))
914 iv->base = NULL_RTX;
915 goto end;
918 /* Loop transforms base to es (base + inner_step) + outer_step,
919 where es means extend of subreg between inner_mode and outer_mode.
920 The corresponding induction variable is
922 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
924 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
925 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
926 iv->mode = inner_mode;
927 iv->extend_mode = outer_mode;
928 iv->extend = extend;
929 iv->mult = const1_rtx;
930 iv->delta = outer_step;
931 iv->first_special = inner_mode != outer_mode;
933 end:
934 if (dump_file)
936 fprintf (dump_file, " ");
937 dump_iv_info (dump_file, iv);
938 fprintf (dump_file, "\n");
941 record_biv (def, iv);
942 return iv->base != NULL_RTX;
945 /* Analyzes expression RHS used at INSN and stores the result to *IV.
946 The mode of the induction variable is MODE. */
948 bool
949 iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
951 rtx mby = NULL_RTX, tmp;
952 rtx op0 = NULL_RTX, op1 = NULL_RTX;
953 struct rtx_iv iv0, iv1;
954 enum rtx_code code = GET_CODE (rhs);
955 enum machine_mode omode = mode;
957 iv->mode = VOIDmode;
958 iv->base = NULL_RTX;
959 iv->step = NULL_RTX;
961 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
963 if (CONSTANT_P (rhs)
964 || REG_P (rhs)
965 || code == SUBREG)
967 if (!iv_analyze_op (insn, rhs, iv))
968 return false;
970 if (iv->mode == VOIDmode)
972 iv->mode = mode;
973 iv->extend_mode = mode;
976 return true;
979 switch (code)
981 case REG:
982 op0 = rhs;
983 break;
985 case SIGN_EXTEND:
986 case ZERO_EXTEND:
987 case NEG:
988 op0 = XEXP (rhs, 0);
989 omode = GET_MODE (op0);
990 break;
992 case PLUS:
993 case MINUS:
994 op0 = XEXP (rhs, 0);
995 op1 = XEXP (rhs, 1);
996 break;
998 case MULT:
999 op0 = XEXP (rhs, 0);
1000 mby = XEXP (rhs, 1);
1001 if (!CONSTANT_P (mby))
1003 tmp = op0;
1004 op0 = mby;
1005 mby = tmp;
1007 if (!CONSTANT_P (mby))
1008 return false;
1009 break;
1011 case ASHIFT:
1012 op0 = XEXP (rhs, 0);
1013 mby = XEXP (rhs, 1);
1014 if (!CONSTANT_P (mby))
1015 return false;
1016 break;
1018 default:
1019 return false;
1022 if (op0
1023 && !iv_analyze_expr (insn, op0, omode, &iv0))
1024 return false;
1026 if (op1
1027 && !iv_analyze_expr (insn, op1, omode, &iv1))
1028 return false;
1030 switch (code)
1032 case SIGN_EXTEND:
1033 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1034 return false;
1035 break;
1037 case ZERO_EXTEND:
1038 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1039 return false;
1040 break;
1042 case NEG:
1043 if (!iv_neg (&iv0))
1044 return false;
1045 break;
1047 case PLUS:
1048 case MINUS:
1049 if (!iv_add (&iv0, &iv1, code))
1050 return false;
1051 break;
1053 case MULT:
1054 if (!iv_mult (&iv0, mby))
1055 return false;
1056 break;
1058 case ASHIFT:
1059 if (!iv_shift (&iv0, mby))
1060 return false;
1061 break;
1063 default:
1064 break;
1067 *iv = iv0;
1068 return iv->base != NULL_RTX;
1071 /* Analyzes iv DEF and stores the result to *IV. */
1073 static bool
1074 iv_analyze_def (df_ref def, struct rtx_iv *iv)
1076 rtx insn = DF_REF_INSN (def);
1077 rtx reg = DF_REF_REG (def);
1078 rtx set, rhs;
1080 if (dump_file)
1082 fprintf (dump_file, "Analyzing def of ");
1083 print_rtl (dump_file, reg);
1084 fprintf (dump_file, " in insn ");
1085 print_rtl_single (dump_file, insn);
1088 check_iv_ref_table_size ();
1089 if (DF_REF_IV (def))
1091 if (dump_file)
1092 fprintf (dump_file, " already analysed.\n");
1093 *iv = *DF_REF_IV (def);
1094 return iv->base != NULL_RTX;
1097 iv->mode = VOIDmode;
1098 iv->base = NULL_RTX;
1099 iv->step = NULL_RTX;
1101 if (!REG_P (reg))
1102 return false;
1104 set = single_set (insn);
1105 if (!set)
1106 return false;
1108 if (!REG_P (SET_DEST (set)))
1109 return false;
1111 gcc_assert (SET_DEST (set) == reg);
1112 rhs = find_reg_equal_equiv_note (insn);
1113 if (rhs)
1114 rhs = XEXP (rhs, 0);
1115 else
1116 rhs = SET_SRC (set);
1118 iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1119 record_iv (def, iv);
1121 if (dump_file)
1123 print_rtl (dump_file, reg);
1124 fprintf (dump_file, " in insn ");
1125 print_rtl_single (dump_file, insn);
1126 fprintf (dump_file, " is ");
1127 dump_iv_info (dump_file, iv);
1128 fprintf (dump_file, "\n");
1131 return iv->base != NULL_RTX;
1134 /* Analyzes operand OP of INSN and stores the result to *IV. */
1136 static bool
1137 iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
1139 df_ref def = NULL;
1140 enum iv_grd_result res;
1142 if (dump_file)
1144 fprintf (dump_file, "Analyzing operand ");
1145 print_rtl (dump_file, op);
1146 fprintf (dump_file, " of insn ");
1147 print_rtl_single (dump_file, insn);
1150 if (function_invariant_p (op))
1151 res = GRD_INVARIANT;
1152 else if (GET_CODE (op) == SUBREG)
1154 if (!subreg_lowpart_p (op))
1155 return false;
1157 if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1158 return false;
1160 return iv_subreg (iv, GET_MODE (op));
1162 else
1164 res = iv_get_reaching_def (insn, op, &def);
1165 if (res == GRD_INVALID)
1167 if (dump_file)
1168 fprintf (dump_file, " not simple.\n");
1169 return false;
1173 if (res == GRD_INVARIANT)
1175 iv_constant (iv, op, VOIDmode);
1177 if (dump_file)
1179 fprintf (dump_file, " ");
1180 dump_iv_info (dump_file, iv);
1181 fprintf (dump_file, "\n");
1183 return true;
1186 if (res == GRD_MAYBE_BIV)
1187 return iv_analyze_biv (op, iv);
1189 return iv_analyze_def (def, iv);
1192 /* Analyzes value VAL at INSN and stores the result to *IV. */
1194 bool
1195 iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
1197 rtx reg;
1199 /* We must find the insn in that val is used, so that we get to UD chains.
1200 Since the function is sometimes called on result of get_condition,
1201 this does not necessarily have to be directly INSN; scan also the
1202 following insns. */
1203 if (simple_reg_p (val))
1205 if (GET_CODE (val) == SUBREG)
1206 reg = SUBREG_REG (val);
1207 else
1208 reg = val;
1210 while (!df_find_use (insn, reg))
1211 insn = NEXT_INSN (insn);
1214 return iv_analyze_op (insn, val, iv);
1217 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1219 bool
1220 iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
1222 df_ref adef;
1224 adef = df_find_def (insn, def);
1225 if (!adef)
1226 return false;
1228 return iv_analyze_def (adef, iv);
1231 /* Checks whether definition of register REG in INSN is a basic induction
1232 variable. IV analysis must have been initialized (via a call to
1233 iv_analysis_loop_init) for this function to produce a result. */
1235 bool
1236 biv_p (rtx insn, rtx reg)
1238 struct rtx_iv iv;
1239 df_ref def, last_def;
1241 if (!simple_reg_p (reg))
1242 return false;
1244 def = df_find_def (insn, reg);
1245 gcc_assert (def != NULL);
1246 if (!latch_dominating_def (reg, &last_def))
1247 return false;
1248 if (last_def != def)
1249 return false;
1251 if (!iv_analyze_biv (reg, &iv))
1252 return false;
1254 return iv.step != const0_rtx;
1257 /* Calculates value of IV at ITERATION-th iteration. */
1260 get_iv_value (struct rtx_iv *iv, rtx iteration)
1262 rtx val;
1264 /* We would need to generate some if_then_else patterns, and so far
1265 it is not needed anywhere. */
1266 gcc_assert (!iv->first_special);
1268 if (iv->step != const0_rtx && iteration != const0_rtx)
1269 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1270 simplify_gen_binary (MULT, iv->extend_mode,
1271 iv->step, iteration));
1272 else
1273 val = iv->base;
1275 if (iv->extend_mode == iv->mode)
1276 return val;
1278 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1280 if (iv->extend == IV_UNKNOWN_EXTEND)
1281 return val;
1283 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1284 iv->extend_mode, val, iv->mode);
1285 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1286 simplify_gen_binary (MULT, iv->extend_mode,
1287 iv->mult, val));
1289 return val;
1292 /* Free the data for an induction variable analysis. */
1294 void
1295 iv_analysis_done (void)
1297 if (!clean_slate)
1299 clear_iv_info ();
1300 clean_slate = true;
1301 df_finish_pass (true);
1302 delete bivs;
1303 bivs = NULL;
1304 free (iv_ref_table);
1305 iv_ref_table = NULL;
1306 iv_ref_table_size = 0;
1310 /* Computes inverse to X modulo (1 << MOD). */
1312 static uint64_t
1313 inverse (uint64_t x, int mod)
1315 uint64_t mask =
1316 ((uint64_t) 1 << (mod - 1) << 1) - 1;
1317 uint64_t rslt = 1;
1318 int i;
1320 for (i = 0; i < mod - 1; i++)
1322 rslt = (rslt * x) & mask;
1323 x = (x * x) & mask;
1326 return rslt;
1329 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1331 static int
1332 altered_reg_used (rtx *reg, void *alt)
1334 if (!REG_P (*reg))
1335 return 0;
1337 return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
1340 /* Marks registers altered by EXPR in set ALT. */
1342 static void
1343 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1345 if (GET_CODE (expr) == SUBREG)
1346 expr = SUBREG_REG (expr);
1347 if (!REG_P (expr))
1348 return;
1350 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1353 /* Checks whether RHS is simple enough to process. */
1355 static bool
1356 simple_rhs_p (rtx rhs)
1358 rtx op0, op1;
1360 if (function_invariant_p (rhs)
1361 || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1362 return true;
1364 switch (GET_CODE (rhs))
1366 case PLUS:
1367 case MINUS:
1368 case AND:
1369 op0 = XEXP (rhs, 0);
1370 op1 = XEXP (rhs, 1);
1371 /* Allow reg OP const and reg OP reg. */
1372 if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1373 && !function_invariant_p (op0))
1374 return false;
1375 if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1376 && !function_invariant_p (op1))
1377 return false;
1379 return true;
1381 case ASHIFT:
1382 case ASHIFTRT:
1383 case LSHIFTRT:
1384 case MULT:
1385 op0 = XEXP (rhs, 0);
1386 op1 = XEXP (rhs, 1);
1387 /* Allow reg OP const. */
1388 if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1389 return false;
1390 if (!function_invariant_p (op1))
1391 return false;
1393 return true;
1395 default:
1396 return false;
1400 /* If REG has a single definition, replace it with its known value in EXPR.
1401 Callback for for_each_rtx. */
1403 static int
1404 replace_single_def_regs (rtx *reg, void *expr1)
1406 unsigned regno;
1407 df_ref adef;
1408 rtx set, src;
1409 rtx *expr = (rtx *)expr1;
1411 if (!REG_P (*reg))
1412 return 0;
1414 regno = REGNO (*reg);
1415 for (;;)
1417 rtx note;
1418 adef = DF_REG_DEF_CHAIN (regno);
1419 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1420 || DF_REF_IS_ARTIFICIAL (adef))
1421 return -1;
1423 set = single_set (DF_REF_INSN (adef));
1424 if (set == NULL || !REG_P (SET_DEST (set))
1425 || REGNO (SET_DEST (set)) != regno)
1426 return -1;
1428 note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1430 if (note && function_invariant_p (XEXP (note, 0)))
1432 src = XEXP (note, 0);
1433 break;
1435 src = SET_SRC (set);
1437 if (REG_P (src))
1439 regno = REGNO (src);
1440 continue;
1442 break;
1444 if (!function_invariant_p (src))
1445 return -1;
1447 *expr = simplify_replace_rtx (*expr, *reg, src);
1448 return 1;
1451 /* A subroutine of simplify_using_initial_values, this function examines INSN
1452 to see if it contains a suitable set that we can use to make a replacement.
1453 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1454 the set; return false otherwise. */
1456 static bool
1457 suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
1459 rtx set = single_set (insn);
1460 rtx lhs = NULL_RTX, rhs;
1462 if (!set)
1463 return false;
1465 lhs = SET_DEST (set);
1466 if (!REG_P (lhs))
1467 return false;
1469 rhs = find_reg_equal_equiv_note (insn);
1470 if (rhs)
1471 rhs = XEXP (rhs, 0);
1472 else
1473 rhs = SET_SRC (set);
1475 if (!simple_rhs_p (rhs))
1476 return false;
1478 *dest = lhs;
1479 *src = rhs;
1480 return true;
1483 /* Using the data returned by suitable_set_for_replacement, replace DEST
1484 with SRC in *EXPR and return the new expression. Also call
1485 replace_single_def_regs if the replacement changed something. */
1486 static void
1487 replace_in_expr (rtx *expr, rtx dest, rtx src)
1489 rtx old = *expr;
1490 *expr = simplify_replace_rtx (*expr, dest, src);
1491 if (old == *expr)
1492 return;
1493 while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
1494 continue;
1497 /* Checks whether A implies B. */
1499 static bool
1500 implies_p (rtx a, rtx b)
1502 rtx op0, op1, opb0, opb1, r;
1503 enum machine_mode mode;
1505 if (rtx_equal_p (a, b))
1506 return true;
1508 if (GET_CODE (a) == EQ)
1510 op0 = XEXP (a, 0);
1511 op1 = XEXP (a, 1);
1513 if (REG_P (op0)
1514 || (GET_CODE (op0) == SUBREG
1515 && REG_P (SUBREG_REG (op0))))
1517 r = simplify_replace_rtx (b, op0, op1);
1518 if (r == const_true_rtx)
1519 return true;
1522 if (REG_P (op1)
1523 || (GET_CODE (op1) == SUBREG
1524 && REG_P (SUBREG_REG (op1))))
1526 r = simplify_replace_rtx (b, op1, op0);
1527 if (r == const_true_rtx)
1528 return true;
1532 if (b == const_true_rtx)
1533 return true;
1535 if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1536 && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1537 || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1538 && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1539 return false;
1541 op0 = XEXP (a, 0);
1542 op1 = XEXP (a, 1);
1543 opb0 = XEXP (b, 0);
1544 opb1 = XEXP (b, 1);
1546 mode = GET_MODE (op0);
1547 if (mode != GET_MODE (opb0))
1548 mode = VOIDmode;
1549 else if (mode == VOIDmode)
1551 mode = GET_MODE (op1);
1552 if (mode != GET_MODE (opb1))
1553 mode = VOIDmode;
1556 /* A < B implies A + 1 <= B. */
1557 if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1558 && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1561 if (GET_CODE (a) == GT)
1563 r = op0;
1564 op0 = op1;
1565 op1 = r;
1568 if (GET_CODE (b) == GE)
1570 r = opb0;
1571 opb0 = opb1;
1572 opb1 = r;
1575 if (SCALAR_INT_MODE_P (mode)
1576 && rtx_equal_p (op1, opb1)
1577 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1578 return true;
1579 return false;
1582 /* A < B or A > B imply A != B. TODO: Likewise
1583 A + n < B implies A != B + n if neither wraps. */
1584 if (GET_CODE (b) == NE
1585 && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1586 || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1588 if (rtx_equal_p (op0, opb0)
1589 && rtx_equal_p (op1, opb1))
1590 return true;
1593 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1594 if (GET_CODE (a) == NE
1595 && op1 == const0_rtx)
1597 if ((GET_CODE (b) == GTU
1598 && opb1 == const0_rtx)
1599 || (GET_CODE (b) == GEU
1600 && opb1 == const1_rtx))
1601 return rtx_equal_p (op0, opb0);
1604 /* A != N is equivalent to A - (N + 1) <u -1. */
1605 if (GET_CODE (a) == NE
1606 && CONST_INT_P (op1)
1607 && GET_CODE (b) == LTU
1608 && opb1 == constm1_rtx
1609 && GET_CODE (opb0) == PLUS
1610 && CONST_INT_P (XEXP (opb0, 1))
1611 /* Avoid overflows. */
1612 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1613 != ((unsigned HOST_WIDE_INT)1
1614 << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1615 && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1616 return rtx_equal_p (op0, XEXP (opb0, 0));
1618 /* Likewise, A != N implies A - N > 0. */
1619 if (GET_CODE (a) == NE
1620 && CONST_INT_P (op1))
1622 if (GET_CODE (b) == GTU
1623 && GET_CODE (opb0) == PLUS
1624 && opb1 == const0_rtx
1625 && CONST_INT_P (XEXP (opb0, 1))
1626 /* Avoid overflows. */
1627 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1628 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1629 && rtx_equal_p (XEXP (opb0, 0), op0))
1630 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1631 if (GET_CODE (b) == GEU
1632 && GET_CODE (opb0) == PLUS
1633 && opb1 == const1_rtx
1634 && CONST_INT_P (XEXP (opb0, 1))
1635 /* Avoid overflows. */
1636 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1637 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1638 && rtx_equal_p (XEXP (opb0, 0), op0))
1639 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1642 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1643 if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1644 && CONST_INT_P (op1)
1645 && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1646 || INTVAL (op1) >= 0)
1647 && GET_CODE (b) == LTU
1648 && CONST_INT_P (opb1)
1649 && rtx_equal_p (op0, opb0))
1650 return INTVAL (opb1) < 0;
1652 return false;
1655 /* Canonicalizes COND so that
1657 (1) Ensure that operands are ordered according to
1658 swap_commutative_operands_p.
1659 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1660 for GE, GEU, and LEU. */
1663 canon_condition (rtx cond)
1665 rtx tem;
1666 rtx op0, op1;
1667 enum rtx_code code;
1668 enum machine_mode mode;
1670 code = GET_CODE (cond);
1671 op0 = XEXP (cond, 0);
1672 op1 = XEXP (cond, 1);
1674 if (swap_commutative_operands_p (op0, op1))
1676 code = swap_condition (code);
1677 tem = op0;
1678 op0 = op1;
1679 op1 = tem;
1682 mode = GET_MODE (op0);
1683 if (mode == VOIDmode)
1684 mode = GET_MODE (op1);
1685 gcc_assert (mode != VOIDmode);
1687 if (CONST_INT_P (op1)
1688 && GET_MODE_CLASS (mode) != MODE_CC
1689 && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1691 HOST_WIDE_INT const_val = INTVAL (op1);
1692 unsigned HOST_WIDE_INT uconst_val = const_val;
1693 unsigned HOST_WIDE_INT max_val
1694 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1696 switch (code)
1698 case LE:
1699 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1700 code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1701 break;
1703 /* When cross-compiling, const_val might be sign-extended from
1704 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1705 case GE:
1706 if ((HOST_WIDE_INT) (const_val & max_val)
1707 != (((HOST_WIDE_INT) 1
1708 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1709 code = GT, op1 = gen_int_mode (const_val - 1, mode);
1710 break;
1712 case LEU:
1713 if (uconst_val < max_val)
1714 code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1715 break;
1717 case GEU:
1718 if (uconst_val != 0)
1719 code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1720 break;
1722 default:
1723 break;
1727 if (op0 != XEXP (cond, 0)
1728 || op1 != XEXP (cond, 1)
1729 || code != GET_CODE (cond)
1730 || GET_MODE (cond) != SImode)
1731 cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1733 return cond;
1736 /* Reverses CONDition; returns NULL if we cannot. */
1738 static rtx
1739 reversed_condition (rtx cond)
1741 enum rtx_code reversed;
1742 reversed = reversed_comparison_code (cond, NULL);
1743 if (reversed == UNKNOWN)
1744 return NULL_RTX;
1745 else
1746 return gen_rtx_fmt_ee (reversed,
1747 GET_MODE (cond), XEXP (cond, 0),
1748 XEXP (cond, 1));
1751 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1752 set of altered regs. */
1754 void
1755 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1757 rtx rev, reve, exp = *expr;
1759 /* If some register gets altered later, we do not really speak about its
1760 value at the time of comparison. */
1761 if (altered
1762 && for_each_rtx (&cond, altered_reg_used, altered))
1763 return;
1765 if (GET_CODE (cond) == EQ
1766 && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1768 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1769 return;
1772 if (!COMPARISON_P (exp))
1773 return;
1775 rev = reversed_condition (cond);
1776 reve = reversed_condition (exp);
1778 cond = canon_condition (cond);
1779 exp = canon_condition (exp);
1780 if (rev)
1781 rev = canon_condition (rev);
1782 if (reve)
1783 reve = canon_condition (reve);
1785 if (rtx_equal_p (exp, cond))
1787 *expr = const_true_rtx;
1788 return;
1791 if (rev && rtx_equal_p (exp, rev))
1793 *expr = const0_rtx;
1794 return;
1797 if (implies_p (cond, exp))
1799 *expr = const_true_rtx;
1800 return;
1803 if (reve && implies_p (cond, reve))
1805 *expr = const0_rtx;
1806 return;
1809 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1810 be false. */
1811 if (rev && implies_p (exp, rev))
1813 *expr = const0_rtx;
1814 return;
1817 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1818 if (rev && reve && implies_p (reve, rev))
1820 *expr = const_true_rtx;
1821 return;
1824 /* We would like to have some other tests here. TODO. */
1826 return;
1829 /* Use relationship between A and *B to eventually eliminate *B.
1830 OP is the operation we consider. */
1832 static void
1833 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1835 switch (op)
1837 case AND:
1838 /* If A implies *B, we may replace *B by true. */
1839 if (implies_p (a, *b))
1840 *b = const_true_rtx;
1841 break;
1843 case IOR:
1844 /* If *B implies A, we may replace *B by false. */
1845 if (implies_p (*b, a))
1846 *b = const0_rtx;
1847 break;
1849 default:
1850 gcc_unreachable ();
1854 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1855 operation we consider. */
1857 static void
1858 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1860 rtx elt;
1862 for (elt = tail; elt; elt = XEXP (elt, 1))
1863 eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1864 for (elt = tail; elt; elt = XEXP (elt, 1))
1865 eliminate_implied_condition (op, XEXP (elt, 0), head);
1868 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1869 is a list, its elements are assumed to be combined using OP. */
1871 static void
1872 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1874 bool expression_valid;
1875 rtx head, tail, insn, cond_list, last_valid_expr;
1876 rtx neutral, aggr;
1877 regset altered, this_altered;
1878 edge e;
1880 if (!*expr)
1881 return;
1883 if (CONSTANT_P (*expr))
1884 return;
1886 if (GET_CODE (*expr) == EXPR_LIST)
1888 head = XEXP (*expr, 0);
1889 tail = XEXP (*expr, 1);
1891 eliminate_implied_conditions (op, &head, tail);
1893 switch (op)
1895 case AND:
1896 neutral = const_true_rtx;
1897 aggr = const0_rtx;
1898 break;
1900 case IOR:
1901 neutral = const0_rtx;
1902 aggr = const_true_rtx;
1903 break;
1905 default:
1906 gcc_unreachable ();
1909 simplify_using_initial_values (loop, UNKNOWN, &head);
1910 if (head == aggr)
1912 XEXP (*expr, 0) = aggr;
1913 XEXP (*expr, 1) = NULL_RTX;
1914 return;
1916 else if (head == neutral)
1918 *expr = tail;
1919 simplify_using_initial_values (loop, op, expr);
1920 return;
1922 simplify_using_initial_values (loop, op, &tail);
1924 if (tail && XEXP (tail, 0) == aggr)
1926 *expr = tail;
1927 return;
1930 XEXP (*expr, 0) = head;
1931 XEXP (*expr, 1) = tail;
1932 return;
1935 gcc_assert (op == UNKNOWN);
1937 for (;;)
1938 if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
1939 break;
1940 if (CONSTANT_P (*expr))
1941 return;
1943 e = loop_preheader_edge (loop);
1944 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1945 return;
1947 altered = ALLOC_REG_SET (&reg_obstack);
1948 this_altered = ALLOC_REG_SET (&reg_obstack);
1950 expression_valid = true;
1951 last_valid_expr = *expr;
1952 cond_list = NULL_RTX;
1953 while (1)
1955 insn = BB_END (e->src);
1956 if (any_condjump_p (insn))
1958 rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1960 if (cond && (e->flags & EDGE_FALLTHRU))
1961 cond = reversed_condition (cond);
1962 if (cond)
1964 rtx old = *expr;
1965 simplify_using_condition (cond, expr, altered);
1966 if (old != *expr)
1968 rtx note;
1969 if (CONSTANT_P (*expr))
1970 goto out;
1971 for (note = cond_list; note; note = XEXP (note, 1))
1973 simplify_using_condition (XEXP (note, 0), expr, altered);
1974 if (CONSTANT_P (*expr))
1975 goto out;
1978 cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1982 FOR_BB_INSNS_REVERSE (e->src, insn)
1984 rtx src, dest;
1985 rtx old = *expr;
1987 if (!INSN_P (insn))
1988 continue;
1990 CLEAR_REG_SET (this_altered);
1991 note_stores (PATTERN (insn), mark_altered, this_altered);
1992 if (CALL_P (insn))
1994 /* Kill all call clobbered registers. */
1995 unsigned int i;
1996 hard_reg_set_iterator hrsi;
1997 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
1998 0, i, hrsi)
1999 SET_REGNO_REG_SET (this_altered, i);
2002 if (suitable_set_for_replacement (insn, &dest, &src))
2004 rtx *pnote, *pnote_next;
2006 replace_in_expr (expr, dest, src);
2007 if (CONSTANT_P (*expr))
2008 goto out;
2010 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2012 rtx note = *pnote;
2013 rtx old_cond = XEXP (note, 0);
2015 pnote_next = &XEXP (note, 1);
2016 replace_in_expr (&XEXP (note, 0), dest, src);
2018 /* We can no longer use a condition that has been simplified
2019 to a constant, and simplify_using_condition will abort if
2020 we try. */
2021 if (CONSTANT_P (XEXP (note, 0)))
2023 *pnote = *pnote_next;
2024 pnote_next = pnote;
2025 free_EXPR_LIST_node (note);
2027 /* Retry simplifications with this condition if either the
2028 expression or the condition changed. */
2029 else if (old_cond != XEXP (note, 0) || old != *expr)
2030 simplify_using_condition (XEXP (note, 0), expr, altered);
2033 else
2035 rtx *pnote, *pnote_next;
2037 /* If we did not use this insn to make a replacement, any overlap
2038 between stores in this insn and our expression will cause the
2039 expression to become invalid. */
2040 if (for_each_rtx (expr, altered_reg_used, this_altered))
2041 goto out;
2043 /* Likewise for the conditions. */
2044 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2046 rtx note = *pnote;
2047 rtx old_cond = XEXP (note, 0);
2049 pnote_next = &XEXP (note, 1);
2050 if (for_each_rtx (&old_cond, altered_reg_used, this_altered))
2052 *pnote = *pnote_next;
2053 pnote_next = pnote;
2054 free_EXPR_LIST_node (note);
2059 if (CONSTANT_P (*expr))
2060 goto out;
2062 IOR_REG_SET (altered, this_altered);
2064 /* If the expression now contains regs that have been altered, we
2065 can't return it to the caller. However, it is still valid for
2066 further simplification, so keep searching to see if we can
2067 eventually turn it into a constant. */
2068 if (for_each_rtx (expr, altered_reg_used, altered))
2069 expression_valid = false;
2070 if (expression_valid)
2071 last_valid_expr = *expr;
2074 if (!single_pred_p (e->src)
2075 || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2076 break;
2077 e = single_pred_edge (e->src);
2080 out:
2081 free_EXPR_LIST_list (&cond_list);
2082 if (!CONSTANT_P (*expr))
2083 *expr = last_valid_expr;
2084 FREE_REG_SET (altered);
2085 FREE_REG_SET (this_altered);
2088 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2089 that IV occurs as left operands of comparison COND and its signedness
2090 is SIGNED_P to DESC. */
2092 static void
2093 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
2094 enum rtx_code cond, bool signed_p, struct niter_desc *desc)
2096 rtx mmin, mmax, cond_over, cond_under;
2098 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2099 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2100 iv->base, mmin);
2101 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2102 iv->base, mmax);
2104 switch (cond)
2106 case LE:
2107 case LT:
2108 case LEU:
2109 case LTU:
2110 if (cond_under != const0_rtx)
2111 desc->infinite =
2112 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2113 if (cond_over != const0_rtx)
2114 desc->noloop_assumptions =
2115 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2116 break;
2118 case GE:
2119 case GT:
2120 case GEU:
2121 case GTU:
2122 if (cond_over != const0_rtx)
2123 desc->infinite =
2124 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2125 if (cond_under != const0_rtx)
2126 desc->noloop_assumptions =
2127 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2128 break;
2130 case NE:
2131 if (cond_over != const0_rtx)
2132 desc->infinite =
2133 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2134 if (cond_under != const0_rtx)
2135 desc->infinite =
2136 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2137 break;
2139 default:
2140 gcc_unreachable ();
2143 iv->mode = mode;
2144 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2147 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2148 subregs of the same mode if possible (sometimes it is necessary to add
2149 some assumptions to DESC). */
2151 static bool
2152 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
2153 enum rtx_code cond, struct niter_desc *desc)
2155 enum machine_mode comp_mode;
2156 bool signed_p;
2158 /* If the ivs behave specially in the first iteration, or are
2159 added/multiplied after extending, we ignore them. */
2160 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2161 return false;
2162 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2163 return false;
2165 /* If there is some extend, it must match signedness of the comparison. */
2166 switch (cond)
2168 case LE:
2169 case LT:
2170 if (iv0->extend == IV_ZERO_EXTEND
2171 || iv1->extend == IV_ZERO_EXTEND)
2172 return false;
2173 signed_p = true;
2174 break;
2176 case LEU:
2177 case LTU:
2178 if (iv0->extend == IV_SIGN_EXTEND
2179 || iv1->extend == IV_SIGN_EXTEND)
2180 return false;
2181 signed_p = false;
2182 break;
2184 case NE:
2185 if (iv0->extend != IV_UNKNOWN_EXTEND
2186 && iv1->extend != IV_UNKNOWN_EXTEND
2187 && iv0->extend != iv1->extend)
2188 return false;
2190 signed_p = false;
2191 if (iv0->extend != IV_UNKNOWN_EXTEND)
2192 signed_p = iv0->extend == IV_SIGN_EXTEND;
2193 if (iv1->extend != IV_UNKNOWN_EXTEND)
2194 signed_p = iv1->extend == IV_SIGN_EXTEND;
2195 break;
2197 default:
2198 gcc_unreachable ();
2201 /* Values of both variables should be computed in the same mode. These
2202 might indeed be different, if we have comparison like
2204 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2206 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2207 in different modes. This does not seem impossible to handle, but
2208 it hardly ever occurs in practice.
2210 The only exception is the case when one of operands is invariant.
2211 For example pentium 3 generates comparisons like
2212 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2213 definitely do not want this prevent the optimization. */
2214 comp_mode = iv0->extend_mode;
2215 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2216 comp_mode = iv1->extend_mode;
2218 if (iv0->extend_mode != comp_mode)
2220 if (iv0->mode != iv0->extend_mode
2221 || iv0->step != const0_rtx)
2222 return false;
2224 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2225 comp_mode, iv0->base, iv0->mode);
2226 iv0->extend_mode = comp_mode;
2229 if (iv1->extend_mode != comp_mode)
2231 if (iv1->mode != iv1->extend_mode
2232 || iv1->step != const0_rtx)
2233 return false;
2235 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2236 comp_mode, iv1->base, iv1->mode);
2237 iv1->extend_mode = comp_mode;
2240 /* Check that both ivs belong to a range of a single mode. If one of the
2241 operands is an invariant, we may need to shorten it into the common
2242 mode. */
2243 if (iv0->mode == iv0->extend_mode
2244 && iv0->step == const0_rtx
2245 && iv0->mode != iv1->mode)
2246 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2248 if (iv1->mode == iv1->extend_mode
2249 && iv1->step == const0_rtx
2250 && iv0->mode != iv1->mode)
2251 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2253 if (iv0->mode != iv1->mode)
2254 return false;
2256 desc->mode = iv0->mode;
2257 desc->signed_p = signed_p;
2259 return true;
2262 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2263 result. This function is called from iv_number_of_iterations with
2264 a number of fields in DESC already filled in. OLD_NITER is the original
2265 expression for the number of iterations, before we tried to simplify it. */
2267 static uint64_t
2268 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
2270 rtx niter = desc->niter_expr;
2271 rtx mmin, mmax, cmp;
2272 uint64_t nmax, inc;
2273 uint64_t andmax = 0;
2275 /* We used to look for constant operand 0 of AND,
2276 but canonicalization should always make this impossible. */
2277 gcc_checking_assert (GET_CODE (niter) != AND
2278 || !CONST_INT_P (XEXP (niter, 0)));
2280 if (GET_CODE (niter) == AND
2281 && CONST_INT_P (XEXP (niter, 1)))
2283 andmax = UINTVAL (XEXP (niter, 1));
2284 niter = XEXP (niter, 0);
2287 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2288 nmax = INTVAL (mmax) - INTVAL (mmin);
2290 if (GET_CODE (niter) == UDIV)
2292 if (!CONST_INT_P (XEXP (niter, 1)))
2293 return nmax;
2294 inc = INTVAL (XEXP (niter, 1));
2295 niter = XEXP (niter, 0);
2297 else
2298 inc = 1;
2300 /* We could use a binary search here, but for now improving the upper
2301 bound by just one eliminates one important corner case. */
2302 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2303 desc->mode, old_niter, mmax);
2304 simplify_using_initial_values (loop, UNKNOWN, &cmp);
2305 if (cmp == const_true_rtx)
2307 nmax--;
2309 if (dump_file)
2310 fprintf (dump_file, ";; improved upper bound by one.\n");
2312 nmax /= inc;
2313 if (andmax)
2314 nmax = MIN (nmax, andmax);
2315 if (dump_file)
2316 fprintf (dump_file, ";; Determined upper bound %"PRId64".\n",
2317 nmax);
2318 return nmax;
2321 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2322 the result into DESC. Very similar to determine_number_of_iterations
2323 (basically its rtl version), complicated by things like subregs. */
2325 static void
2326 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2327 struct niter_desc *desc)
2329 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2330 struct rtx_iv iv0, iv1, tmp_iv;
2331 rtx assumption, may_not_xform;
2332 enum rtx_code cond;
2333 enum machine_mode mode, comp_mode;
2334 rtx mmin, mmax, mode_mmin, mode_mmax;
2335 uint64_t s, size, d, inv, max;
2336 int64_t up, down, inc, step_val;
2337 int was_sharp = false;
2338 rtx old_niter;
2339 bool step_is_pow2;
2341 /* The meaning of these assumptions is this:
2342 if !assumptions
2343 then the rest of information does not have to be valid
2344 if noloop_assumptions then the loop does not roll
2345 if infinite then this exit is never used */
2347 desc->assumptions = NULL_RTX;
2348 desc->noloop_assumptions = NULL_RTX;
2349 desc->infinite = NULL_RTX;
2350 desc->simple_p = true;
2352 desc->const_iter = false;
2353 desc->niter_expr = NULL_RTX;
2355 cond = GET_CODE (condition);
2356 gcc_assert (COMPARISON_P (condition));
2358 mode = GET_MODE (XEXP (condition, 0));
2359 if (mode == VOIDmode)
2360 mode = GET_MODE (XEXP (condition, 1));
2361 /* The constant comparisons should be folded. */
2362 gcc_assert (mode != VOIDmode);
2364 /* We only handle integers or pointers. */
2365 if (GET_MODE_CLASS (mode) != MODE_INT
2366 && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2367 goto fail;
2369 op0 = XEXP (condition, 0);
2370 if (!iv_analyze (insn, op0, &iv0))
2371 goto fail;
2372 if (iv0.extend_mode == VOIDmode)
2373 iv0.mode = iv0.extend_mode = mode;
2375 op1 = XEXP (condition, 1);
2376 if (!iv_analyze (insn, op1, &iv1))
2377 goto fail;
2378 if (iv1.extend_mode == VOIDmode)
2379 iv1.mode = iv1.extend_mode = mode;
2381 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2382 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2383 goto fail;
2385 /* Check condition and normalize it. */
2387 switch (cond)
2389 case GE:
2390 case GT:
2391 case GEU:
2392 case GTU:
2393 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2394 cond = swap_condition (cond);
2395 break;
2396 case NE:
2397 case LE:
2398 case LEU:
2399 case LT:
2400 case LTU:
2401 break;
2402 default:
2403 goto fail;
2406 /* Handle extends. This is relatively nontrivial, so we only try in some
2407 easy cases, when we can canonicalize the ivs (possibly by adding some
2408 assumptions) to shape subreg (base + i * step). This function also fills
2409 in desc->mode and desc->signed_p. */
2411 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2412 goto fail;
2414 comp_mode = iv0.extend_mode;
2415 mode = iv0.mode;
2416 size = GET_MODE_BITSIZE (mode);
2417 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2418 mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2419 mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2421 if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2422 goto fail;
2424 /* We can take care of the case of two induction variables chasing each other
2425 if the test is NE. I have never seen a loop using it, but still it is
2426 cool. */
2427 if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2429 if (cond != NE)
2430 goto fail;
2432 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2433 iv1.step = const0_rtx;
2436 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2437 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2439 /* This is either infinite loop or the one that ends immediately, depending
2440 on initial values. Unswitching should remove this kind of conditions. */
2441 if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2442 goto fail;
2444 if (cond != NE)
2446 if (iv0.step == const0_rtx)
2447 step_val = -INTVAL (iv1.step);
2448 else
2449 step_val = INTVAL (iv0.step);
2451 /* Ignore loops of while (i-- < 10) type. */
2452 if (step_val < 0)
2453 goto fail;
2455 step_is_pow2 = !(step_val & (step_val - 1));
2457 else
2459 /* We do not care about whether the step is power of two in this
2460 case. */
2461 step_is_pow2 = false;
2462 step_val = 0;
2465 /* Some more condition normalization. We must record some assumptions
2466 due to overflows. */
2467 switch (cond)
2469 case LT:
2470 case LTU:
2471 /* We want to take care only of non-sharp relationals; this is easy,
2472 as in cases the overflow would make the transformation unsafe
2473 the loop does not roll. Seemingly it would make more sense to want
2474 to take care of sharp relationals instead, as NE is more similar to
2475 them, but the problem is that here the transformation would be more
2476 difficult due to possibly infinite loops. */
2477 if (iv0.step == const0_rtx)
2479 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2480 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2481 mode_mmax);
2482 if (assumption == const_true_rtx)
2483 goto zero_iter_simplify;
2484 iv0.base = simplify_gen_binary (PLUS, comp_mode,
2485 iv0.base, const1_rtx);
2487 else
2489 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2490 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2491 mode_mmin);
2492 if (assumption == const_true_rtx)
2493 goto zero_iter_simplify;
2494 iv1.base = simplify_gen_binary (PLUS, comp_mode,
2495 iv1.base, constm1_rtx);
2498 if (assumption != const0_rtx)
2499 desc->noloop_assumptions =
2500 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2501 cond = (cond == LT) ? LE : LEU;
2503 /* It will be useful to be able to tell the difference once more in
2504 LE -> NE reduction. */
2505 was_sharp = true;
2506 break;
2507 default: ;
2510 /* Take care of trivially infinite loops. */
2511 if (cond != NE)
2513 if (iv0.step == const0_rtx)
2515 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2516 if (rtx_equal_p (tmp, mode_mmin))
2518 desc->infinite =
2519 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2520 /* Fill in the remaining fields somehow. */
2521 goto zero_iter_simplify;
2524 else
2526 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2527 if (rtx_equal_p (tmp, mode_mmax))
2529 desc->infinite =
2530 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2531 /* Fill in the remaining fields somehow. */
2532 goto zero_iter_simplify;
2537 /* If we can we want to take care of NE conditions instead of size
2538 comparisons, as they are much more friendly (most importantly
2539 this takes care of special handling of loops with step 1). We can
2540 do it if we first check that upper bound is greater or equal to
2541 lower bound, their difference is constant c modulo step and that
2542 there is not an overflow. */
2543 if (cond != NE)
2545 if (iv0.step == const0_rtx)
2546 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2547 else
2548 step = iv0.step;
2549 step = lowpart_subreg (mode, step, comp_mode);
2550 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2551 delta = lowpart_subreg (mode, delta, comp_mode);
2552 delta = simplify_gen_binary (UMOD, mode, delta, step);
2553 may_xform = const0_rtx;
2554 may_not_xform = const_true_rtx;
2556 if (CONST_INT_P (delta))
2558 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2560 /* A special case. We have transformed condition of type
2561 for (i = 0; i < 4; i += 4)
2562 into
2563 for (i = 0; i <= 3; i += 4)
2564 obviously if the test for overflow during that transformation
2565 passed, we cannot overflow here. Most importantly any
2566 loop with sharp end condition and step 1 falls into this
2567 category, so handling this case specially is definitely
2568 worth the troubles. */
2569 may_xform = const_true_rtx;
2571 else if (iv0.step == const0_rtx)
2573 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2574 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2575 bound = lowpart_subreg (mode, bound, comp_mode);
2576 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2577 may_xform = simplify_gen_relational (cond, SImode, mode,
2578 bound, tmp);
2579 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2580 SImode, mode,
2581 bound, tmp);
2583 else
2585 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2586 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2587 bound = lowpart_subreg (mode, bound, comp_mode);
2588 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2589 may_xform = simplify_gen_relational (cond, SImode, mode,
2590 tmp, bound);
2591 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2592 SImode, mode,
2593 tmp, bound);
2597 if (may_xform != const0_rtx)
2599 /* We perform the transformation always provided that it is not
2600 completely senseless. This is OK, as we would need this assumption
2601 to determine the number of iterations anyway. */
2602 if (may_xform != const_true_rtx)
2604 /* If the step is a power of two and the final value we have
2605 computed overflows, the cycle is infinite. Otherwise it
2606 is nontrivial to compute the number of iterations. */
2607 if (step_is_pow2)
2608 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2609 desc->infinite);
2610 else
2611 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2612 desc->assumptions);
2615 /* We are going to lose some information about upper bound on
2616 number of iterations in this step, so record the information
2617 here. */
2618 inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2619 if (CONST_INT_P (iv1.base))
2620 up = INTVAL (iv1.base);
2621 else
2622 up = INTVAL (mode_mmax) - inc;
2623 down = INTVAL (CONST_INT_P (iv0.base)
2624 ? iv0.base
2625 : mode_mmin);
2626 max = (up - down) / inc + 1;
2627 if (!desc->infinite
2628 && !desc->assumptions)
2629 record_niter_bound (loop, max, false, true);
2631 if (iv0.step == const0_rtx)
2633 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2634 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2636 else
2638 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2639 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2642 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2643 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2644 assumption = simplify_gen_relational (reverse_condition (cond),
2645 SImode, mode, tmp0, tmp1);
2646 if (assumption == const_true_rtx)
2647 goto zero_iter_simplify;
2648 else if (assumption != const0_rtx)
2649 desc->noloop_assumptions =
2650 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2651 cond = NE;
2655 /* Count the number of iterations. */
2656 if (cond == NE)
2658 /* Everything we do here is just arithmetics modulo size of mode. This
2659 makes us able to do more involved computations of number of iterations
2660 than in other cases. First transform the condition into shape
2661 s * i <> c, with s positive. */
2662 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2663 iv0.base = const0_rtx;
2664 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2665 iv1.step = const0_rtx;
2666 if (INTVAL (iv0.step) < 0)
2668 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
2669 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
2671 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2673 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2674 is infinite. Otherwise, the number of iterations is
2675 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2676 s = INTVAL (iv0.step); d = 1;
2677 while (s % 2 != 1)
2679 s /= 2;
2680 d *= 2;
2681 size--;
2683 bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1);
2685 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2686 tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2687 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2688 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2690 tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2691 inv = inverse (s, size);
2692 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2693 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2695 else
2697 if (iv1.step == const0_rtx)
2698 /* Condition in shape a + s * i <= b
2699 We must know that b + s does not overflow and a <= b + s and then we
2700 can compute number of iterations as (b + s - a) / s. (It might
2701 seem that we in fact could be more clever about testing the b + s
2702 overflow condition using some information about b - a mod s,
2703 but it was already taken into account during LE -> NE transform). */
2705 step = iv0.step;
2706 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2707 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2709 bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2710 lowpart_subreg (mode, step,
2711 comp_mode));
2712 if (step_is_pow2)
2714 rtx t0, t1;
2716 /* If s is power of 2, we know that the loop is infinite if
2717 a % s <= b % s and b + s overflows. */
2718 assumption = simplify_gen_relational (reverse_condition (cond),
2719 SImode, mode,
2720 tmp1, bound);
2722 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2723 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2724 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2725 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2726 desc->infinite =
2727 alloc_EXPR_LIST (0, assumption, desc->infinite);
2729 else
2731 assumption = simplify_gen_relational (cond, SImode, mode,
2732 tmp1, bound);
2733 desc->assumptions =
2734 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2737 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2738 tmp = lowpart_subreg (mode, tmp, comp_mode);
2739 assumption = simplify_gen_relational (reverse_condition (cond),
2740 SImode, mode, tmp0, tmp);
2742 delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2743 delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2745 else
2747 /* Condition in shape a <= b - s * i
2748 We must know that a - s does not overflow and a - s <= b and then
2749 we can again compute number of iterations as (b - (a - s)) / s. */
2750 step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2751 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2752 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2754 bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2755 lowpart_subreg (mode, step, comp_mode));
2756 if (step_is_pow2)
2758 rtx t0, t1;
2760 /* If s is power of 2, we know that the loop is infinite if
2761 a % s <= b % s and a - s overflows. */
2762 assumption = simplify_gen_relational (reverse_condition (cond),
2763 SImode, mode,
2764 bound, tmp0);
2766 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2767 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2768 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2769 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2770 desc->infinite =
2771 alloc_EXPR_LIST (0, assumption, desc->infinite);
2773 else
2775 assumption = simplify_gen_relational (cond, SImode, mode,
2776 bound, tmp0);
2777 desc->assumptions =
2778 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2781 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2782 tmp = lowpart_subreg (mode, tmp, comp_mode);
2783 assumption = simplify_gen_relational (reverse_condition (cond),
2784 SImode, mode,
2785 tmp, tmp1);
2786 delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2787 delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2789 if (assumption == const_true_rtx)
2790 goto zero_iter_simplify;
2791 else if (assumption != const0_rtx)
2792 desc->noloop_assumptions =
2793 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2794 delta = simplify_gen_binary (UDIV, mode, delta, step);
2795 desc->niter_expr = delta;
2798 old_niter = desc->niter_expr;
2800 simplify_using_initial_values (loop, AND, &desc->assumptions);
2801 if (desc->assumptions
2802 && XEXP (desc->assumptions, 0) == const0_rtx)
2803 goto fail;
2804 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2805 simplify_using_initial_values (loop, IOR, &desc->infinite);
2806 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2808 /* Rerun the simplification. Consider code (created by copying loop headers)
2810 i = 0;
2812 if (0 < n)
2816 i++;
2817 } while (i < n);
2820 The first pass determines that i = 0, the second pass uses it to eliminate
2821 noloop assumption. */
2823 simplify_using_initial_values (loop, AND, &desc->assumptions);
2824 if (desc->assumptions
2825 && XEXP (desc->assumptions, 0) == const0_rtx)
2826 goto fail;
2827 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2828 simplify_using_initial_values (loop, IOR, &desc->infinite);
2829 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2831 if (desc->noloop_assumptions
2832 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2833 goto zero_iter;
2835 if (CONST_INT_P (desc->niter_expr))
2837 uint64_t val = INTVAL (desc->niter_expr);
2839 desc->const_iter = true;
2840 desc->niter = val & GET_MODE_MASK (desc->mode);
2841 if (!desc->infinite
2842 && !desc->assumptions)
2843 record_niter_bound (loop, desc->niter, false, true);
2845 else
2847 max = determine_max_iter (loop, desc, old_niter);
2848 if (!max)
2849 goto zero_iter_simplify;
2850 if (!desc->infinite
2851 && !desc->assumptions)
2852 record_niter_bound (loop, max, false, true);
2854 /* simplify_using_initial_values does a copy propagation on the registers
2855 in the expression for the number of iterations. This prolongs life
2856 ranges of registers and increases register pressure, and usually
2857 brings no gain (and if it happens to do, the cse pass will take care
2858 of it anyway). So prevent this behavior, unless it enabled us to
2859 derive that the number of iterations is a constant. */
2860 desc->niter_expr = old_niter;
2863 return;
2865 zero_iter_simplify:
2866 /* Simplify the assumptions. */
2867 simplify_using_initial_values (loop, AND, &desc->assumptions);
2868 if (desc->assumptions
2869 && XEXP (desc->assumptions, 0) == const0_rtx)
2870 goto fail;
2871 simplify_using_initial_values (loop, IOR, &desc->infinite);
2873 /* Fallthru. */
2874 zero_iter:
2875 desc->const_iter = true;
2876 desc->niter = 0;
2877 record_niter_bound (loop, 0, 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_cleared_alloc<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;