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
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
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
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.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
57 #include "basic-block.h"
61 #include "diagnostic-core.h"
63 #include "hash-table.h"
66 /* Possible return values of iv_get_reaching_def. */
70 /* More than one reaching def, or reaching def that does not
74 /* The use is trivial invariant of the loop, i.e. is not changed
78 /* The use is reached by initial value and a value from the
79 previous iteration. */
82 /* The use has single dominating def. */
86 /* Information about a biv. */
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. */
122 biv_entry_hasher::hash (const value_type
*b
)
127 /* Compares biv B and register R. */
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_insn
*, 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
)
151 case IV_UNKNOWN_EXTEND
:
157 /* Dumps information about IV to FILE. */
159 extern void dump_iv_info (FILE *, struct rtx_iv
*);
161 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
165 fprintf (file
, "not simple");
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
));
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. */
229 simple_reg_p (rtx reg
)
233 if (GET_CODE (reg
) == SUBREG
)
235 if (!subreg_lowpart_p (reg
))
237 reg
= SUBREG_REG (reg
);
244 if (HARD_REGISTER_NUM_P (r
))
247 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
253 /* Clears the information about ivs stored in df. */
258 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
261 check_iv_ref_table_size ();
262 for (i
= 0; i
< n_defs
; i
++)
264 iv
= iv_ref_table
[i
];
268 iv_ref_table
[i
] = NULL
;
276 /* Prepare the data for an induction variable analysis of a LOOP. */
279 iv_analysis_loop_init (struct loop
*loop
)
283 /* Clear the information from the analysis of the previous loop. */
286 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
287 bivs
= new hash_table
<biv_entry_hasher
> (10);
293 /* Get rid of the ud chains before processing the rescans. Then add
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
);
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. */
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
)))
325 /* More than one reaching definition. */
329 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
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
*insn
, rtx reg
, df_ref
*def
)
345 basic_block def_bb
, use_bb
;
350 if (!simple_reg_p (reg
))
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
)
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
)
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
));
379 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
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
390 if (just_once_each_iteration_p (current_loop
, def_bb
))
391 return GRD_MAYBE_BIV
;
396 /* Sets IV to invariant CST in MODE. Always returns true (just for
397 consistency with other iv manipulation functions that may fail). */
400 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
402 if (mode
== VOIDmode
)
403 mode
= GET_MODE (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
;
417 /* Evaluates application of subreg to MODE on IV. */
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
);
432 iv
->extend
= IV_UNKNOWN_EXTEND
;
433 iv
->mode
= iv
->extend_mode
= mode
;
434 iv
->delta
= const0_rtx
;
435 iv
->mult
= const1_rtx
;
439 if (iv
->extend_mode
== mode
)
442 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
445 iv
->extend
= IV_UNKNOWN_EXTEND
;
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;
459 /* Evaluates application of EXTEND to MODE on IV. */
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
,
476 ? iv
->extend_mode
: iv
->mode
);
478 iv
->extend
= IV_UNKNOWN_EXTEND
;
479 iv
->mode
= iv
->extend_mode
= mode
;
480 iv
->delta
= const0_rtx
;
481 iv
->mult
= const1_rtx
;
485 if (mode
!= iv
->extend_mode
)
488 if (iv
->extend
!= IV_UNKNOWN_EXTEND
489 && iv
->extend
!= extend
)
497 /* Evaluates negation of IV. */
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
);
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
);
520 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
523 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
525 enum machine_mode mode
;
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
)
552 if (iv0
->extend
== IV_UNKNOWN_EXTEND
553 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
555 if (iv0
->mode
!= iv1
->mode
)
558 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
559 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
564 /* Handle addition of constant. */
565 if (iv1
->extend
== IV_UNKNOWN_EXTEND
567 && iv1
->step
== const0_rtx
)
569 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
573 if (iv0
->extend
== IV_UNKNOWN_EXTEND
575 && iv0
->step
== const0_rtx
)
583 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
590 /* Evaluates multiplication of IV by constant CST. */
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
)
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
);
608 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
609 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
615 /* Evaluates shift of IV by constant CST. */
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
)
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
);
633 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
634 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
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
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
,
650 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
651 rtx next
, nextr
, tmp
;
653 rtx_insn
*insn
= DF_REF_INSN (def
);
655 enum iv_grd_result res
;
657 set
= single_set (insn
);
661 rhs
= find_reg_equal_equiv_note (insn
);
667 code
= GET_CODE (rhs
);
680 if (code
== PLUS
&& CONSTANT_P (op0
))
682 tmp
= op0
; op0
= op1
; op1
= tmp
;
685 if (!simple_reg_p (op0
)
686 || !CONSTANT_P (op1
))
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
)
701 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
710 if (GET_MODE (rhs
) != outer_mode
)
714 if (!simple_reg_p (op0
))
724 if (GET_CODE (next
) == SUBREG
)
726 if (!subreg_lowpart_p (next
))
729 nextr
= SUBREG_REG (next
);
730 if (GET_MODE (nextr
) != outer_mode
)
736 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
738 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
741 if (res
== GRD_MAYBE_BIV
)
743 if (!rtx_equal_p (nextr
, reg
))
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
,
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
))
764 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
765 *inner_step
, *outer_step
);
766 *outer_step
= const0_rtx
;
767 *extend
= IV_UNKNOWN_EXTEND
;
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
,
784 *outer_step
= simplify_gen_binary (code
, outer_mode
,
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
;
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. */
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
,
823 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
824 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
829 /* Records information that DEF is induction variable IV. */
832 record_iv (df_ref def
, struct rtx_iv
*iv
)
834 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_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. */
845 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
847 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
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
);
868 /* Determines whether DEF is a biv and if so, stores its description
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
;
881 fprintf (dump_file
, "Analyzing ");
882 print_rtl (dump_file
, def
);
883 fprintf (dump_file
, " for bivness.\n");
888 if (!CONSTANT_P (def
))
891 return iv_constant (iv
, def
, VOIDmode
);
894 if (!latch_dominating_def (def
, &last_def
))
897 fprintf (dump_file
, " not simple.\n");
902 return iv_constant (iv
, def
, VOIDmode
);
904 if (analyzed_for_bivness_p (def
, iv
))
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
))
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
;
929 iv
->mult
= const1_rtx
;
930 iv
->delta
= outer_step
;
931 iv
->first_special
= inner_mode
!= outer_mode
;
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. */
949 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, enum machine_mode mode
,
952 rtx mby
= NULL_RTX
, tmp
;
953 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
954 struct rtx_iv iv0
, iv1
;
955 enum rtx_code code
= GET_CODE (rhs
);
956 enum machine_mode omode
= mode
;
962 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
968 if (!iv_analyze_op (insn
, rhs
, iv
))
971 if (iv
->mode
== VOIDmode
)
974 iv
->extend_mode
= mode
;
990 omode
= GET_MODE (op0
);
1000 op0
= XEXP (rhs
, 0);
1001 mby
= XEXP (rhs
, 1);
1002 if (!CONSTANT_P (mby
))
1008 if (!CONSTANT_P (mby
))
1013 op0
= XEXP (rhs
, 0);
1014 mby
= XEXP (rhs
, 1);
1015 if (!CONSTANT_P (mby
))
1024 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1028 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1034 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1039 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1050 if (!iv_add (&iv0
, &iv1
, code
))
1055 if (!iv_mult (&iv0
, mby
))
1060 if (!iv_shift (&iv0
, mby
))
1069 return iv
->base
!= NULL_RTX
;
1072 /* Analyzes iv DEF and stores the result to *IV. */
1075 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1077 rtx_insn
*insn
= DF_REF_INSN (def
);
1078 rtx reg
= DF_REF_REG (def
);
1083 fprintf (dump_file
, "Analyzing def of ");
1084 print_rtl (dump_file
, reg
);
1085 fprintf (dump_file
, " in insn ");
1086 print_rtl_single (dump_file
, insn
);
1089 check_iv_ref_table_size ();
1090 if (DF_REF_IV (def
))
1093 fprintf (dump_file
, " already analysed.\n");
1094 *iv
= *DF_REF_IV (def
);
1095 return iv
->base
!= NULL_RTX
;
1098 iv
->mode
= VOIDmode
;
1099 iv
->base
= NULL_RTX
;
1100 iv
->step
= NULL_RTX
;
1105 set
= single_set (insn
);
1109 if (!REG_P (SET_DEST (set
)))
1112 gcc_assert (SET_DEST (set
) == reg
);
1113 rhs
= find_reg_equal_equiv_note (insn
);
1115 rhs
= XEXP (rhs
, 0);
1117 rhs
= SET_SRC (set
);
1119 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1120 record_iv (def
, iv
);
1124 print_rtl (dump_file
, reg
);
1125 fprintf (dump_file
, " in insn ");
1126 print_rtl_single (dump_file
, insn
);
1127 fprintf (dump_file
, " is ");
1128 dump_iv_info (dump_file
, iv
);
1129 fprintf (dump_file
, "\n");
1132 return iv
->base
!= NULL_RTX
;
1135 /* Analyzes operand OP of INSN and stores the result to *IV. */
1138 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1141 enum iv_grd_result res
;
1145 fprintf (dump_file
, "Analyzing operand ");
1146 print_rtl (dump_file
, op
);
1147 fprintf (dump_file
, " of insn ");
1148 print_rtl_single (dump_file
, insn
);
1151 if (function_invariant_p (op
))
1152 res
= GRD_INVARIANT
;
1153 else if (GET_CODE (op
) == SUBREG
)
1155 if (!subreg_lowpart_p (op
))
1158 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1161 return iv_subreg (iv
, GET_MODE (op
));
1165 res
= iv_get_reaching_def (insn
, op
, &def
);
1166 if (res
== GRD_INVALID
)
1169 fprintf (dump_file
, " not simple.\n");
1174 if (res
== GRD_INVARIANT
)
1176 iv_constant (iv
, op
, VOIDmode
);
1180 fprintf (dump_file
, " ");
1181 dump_iv_info (dump_file
, iv
);
1182 fprintf (dump_file
, "\n");
1187 if (res
== GRD_MAYBE_BIV
)
1188 return iv_analyze_biv (op
, iv
);
1190 return iv_analyze_def (def
, iv
);
1193 /* Analyzes value VAL at INSN and stores the result to *IV. */
1196 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1200 /* We must find the insn in that val is used, so that we get to UD chains.
1201 Since the function is sometimes called on result of get_condition,
1202 this does not necessarily have to be directly INSN; scan also the
1204 if (simple_reg_p (val
))
1206 if (GET_CODE (val
) == SUBREG
)
1207 reg
= SUBREG_REG (val
);
1211 while (!df_find_use (insn
, reg
))
1212 insn
= NEXT_INSN (insn
);
1215 return iv_analyze_op (insn
, val
, iv
);
1218 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1221 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1225 adef
= df_find_def (insn
, def
);
1229 return iv_analyze_def (adef
, iv
);
1232 /* Checks whether definition of register REG in INSN is a basic induction
1233 variable. IV analysis must have been initialized (via a call to
1234 iv_analysis_loop_init) for this function to produce a result. */
1237 biv_p (rtx_insn
*insn
, rtx reg
)
1240 df_ref def
, last_def
;
1242 if (!simple_reg_p (reg
))
1245 def
= df_find_def (insn
, reg
);
1246 gcc_assert (def
!= NULL
);
1247 if (!latch_dominating_def (reg
, &last_def
))
1249 if (last_def
!= def
)
1252 if (!iv_analyze_biv (reg
, &iv
))
1255 return iv
.step
!= const0_rtx
;
1258 /* Calculates value of IV at ITERATION-th iteration. */
1261 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1265 /* We would need to generate some if_then_else patterns, and so far
1266 it is not needed anywhere. */
1267 gcc_assert (!iv
->first_special
);
1269 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1270 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1271 simplify_gen_binary (MULT
, iv
->extend_mode
,
1272 iv
->step
, iteration
));
1276 if (iv
->extend_mode
== iv
->mode
)
1279 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1281 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1284 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1285 iv
->extend_mode
, val
, iv
->mode
);
1286 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1287 simplify_gen_binary (MULT
, iv
->extend_mode
,
1293 /* Free the data for an induction variable analysis. */
1296 iv_analysis_done (void)
1302 df_finish_pass (true);
1305 free (iv_ref_table
);
1306 iv_ref_table
= NULL
;
1307 iv_ref_table_size
= 0;
1311 /* Computes inverse to X modulo (1 << MOD). */
1314 inverse (uint64_t x
, int mod
)
1317 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1321 for (i
= 0; i
< mod
- 1; i
++)
1323 rslt
= (rslt
* x
) & mask
;
1330 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1333 altered_reg_used (rtx
*reg
, void *alt
)
1338 return REGNO_REG_SET_P ((bitmap
) alt
, REGNO (*reg
));
1341 /* Marks registers altered by EXPR in set ALT. */
1344 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1346 if (GET_CODE (expr
) == SUBREG
)
1347 expr
= SUBREG_REG (expr
);
1351 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1354 /* Checks whether RHS is simple enough to process. */
1357 simple_rhs_p (rtx rhs
)
1361 if (function_invariant_p (rhs
)
1362 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1365 switch (GET_CODE (rhs
))
1370 op0
= XEXP (rhs
, 0);
1371 op1
= XEXP (rhs
, 1);
1372 /* Allow reg OP const and reg OP reg. */
1373 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1374 && !function_invariant_p (op0
))
1376 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1377 && !function_invariant_p (op1
))
1386 op0
= XEXP (rhs
, 0);
1387 op1
= XEXP (rhs
, 1);
1388 /* Allow reg OP const. */
1389 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1391 if (!function_invariant_p (op1
))
1401 /* If REG has a single definition, replace it with its known value in EXPR.
1402 Callback for for_each_rtx. */
1405 replace_single_def_regs (rtx
*reg
, void *expr1
)
1410 rtx
*expr
= (rtx
*)expr1
;
1415 regno
= REGNO (*reg
);
1419 adef
= DF_REG_DEF_CHAIN (regno
);
1420 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1421 || DF_REF_IS_ARTIFICIAL (adef
))
1424 set
= single_set (DF_REF_INSN (adef
));
1425 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1426 || REGNO (SET_DEST (set
)) != regno
)
1429 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1431 if (note
&& function_invariant_p (XEXP (note
, 0)))
1433 src
= XEXP (note
, 0);
1436 src
= SET_SRC (set
);
1440 regno
= REGNO (src
);
1445 if (!function_invariant_p (src
))
1448 *expr
= simplify_replace_rtx (*expr
, *reg
, src
);
1452 /* A subroutine of simplify_using_initial_values, this function examines INSN
1453 to see if it contains a suitable set that we can use to make a replacement.
1454 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1455 the set; return false otherwise. */
1458 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1460 rtx set
= single_set (insn
);
1461 rtx lhs
= NULL_RTX
, rhs
;
1466 lhs
= SET_DEST (set
);
1470 rhs
= find_reg_equal_equiv_note (insn
);
1472 rhs
= XEXP (rhs
, 0);
1474 rhs
= SET_SRC (set
);
1476 if (!simple_rhs_p (rhs
))
1484 /* Using the data returned by suitable_set_for_replacement, replace DEST
1485 with SRC in *EXPR and return the new expression. Also call
1486 replace_single_def_regs if the replacement changed something. */
1488 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1491 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1494 while (for_each_rtx (expr
, replace_single_def_regs
, expr
) != 0)
1498 /* Checks whether A implies B. */
1501 implies_p (rtx a
, rtx b
)
1503 rtx op0
, op1
, opb0
, opb1
, r
;
1504 enum machine_mode mode
;
1506 if (rtx_equal_p (a
, b
))
1509 if (GET_CODE (a
) == EQ
)
1515 || (GET_CODE (op0
) == SUBREG
1516 && REG_P (SUBREG_REG (op0
))))
1518 r
= simplify_replace_rtx (b
, op0
, op1
);
1519 if (r
== const_true_rtx
)
1524 || (GET_CODE (op1
) == SUBREG
1525 && REG_P (SUBREG_REG (op1
))))
1527 r
= simplify_replace_rtx (b
, op1
, op0
);
1528 if (r
== const_true_rtx
)
1533 if (b
== const_true_rtx
)
1536 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1537 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1538 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1539 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1547 mode
= GET_MODE (op0
);
1548 if (mode
!= GET_MODE (opb0
))
1550 else if (mode
== VOIDmode
)
1552 mode
= GET_MODE (op1
);
1553 if (mode
!= GET_MODE (opb1
))
1557 /* A < B implies A + 1 <= B. */
1558 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1559 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1562 if (GET_CODE (a
) == GT
)
1569 if (GET_CODE (b
) == GE
)
1576 if (SCALAR_INT_MODE_P (mode
)
1577 && rtx_equal_p (op1
, opb1
)
1578 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1583 /* A < B or A > B imply A != B. TODO: Likewise
1584 A + n < B implies A != B + n if neither wraps. */
1585 if (GET_CODE (b
) == NE
1586 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1587 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1589 if (rtx_equal_p (op0
, opb0
)
1590 && rtx_equal_p (op1
, opb1
))
1594 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1595 if (GET_CODE (a
) == NE
1596 && op1
== const0_rtx
)
1598 if ((GET_CODE (b
) == GTU
1599 && opb1
== const0_rtx
)
1600 || (GET_CODE (b
) == GEU
1601 && opb1
== const1_rtx
))
1602 return rtx_equal_p (op0
, opb0
);
1605 /* A != N is equivalent to A - (N + 1) <u -1. */
1606 if (GET_CODE (a
) == NE
1607 && CONST_INT_P (op1
)
1608 && GET_CODE (b
) == LTU
1609 && opb1
== constm1_rtx
1610 && GET_CODE (opb0
) == PLUS
1611 && CONST_INT_P (XEXP (opb0
, 1))
1612 /* Avoid overflows. */
1613 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1614 != ((unsigned HOST_WIDE_INT
)1
1615 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1616 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1617 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1619 /* Likewise, A != N implies A - N > 0. */
1620 if (GET_CODE (a
) == NE
1621 && CONST_INT_P (op1
))
1623 if (GET_CODE (b
) == GTU
1624 && GET_CODE (opb0
) == PLUS
1625 && opb1
== const0_rtx
1626 && CONST_INT_P (XEXP (opb0
, 1))
1627 /* Avoid overflows. */
1628 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1629 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1630 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1631 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1632 if (GET_CODE (b
) == GEU
1633 && GET_CODE (opb0
) == PLUS
1634 && opb1
== const1_rtx
1635 && CONST_INT_P (XEXP (opb0
, 1))
1636 /* Avoid overflows. */
1637 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1638 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1639 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1640 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1643 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1644 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1645 && CONST_INT_P (op1
)
1646 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1647 || INTVAL (op1
) >= 0)
1648 && GET_CODE (b
) == LTU
1649 && CONST_INT_P (opb1
)
1650 && rtx_equal_p (op0
, opb0
))
1651 return INTVAL (opb1
) < 0;
1656 /* Canonicalizes COND so that
1658 (1) Ensure that operands are ordered according to
1659 swap_commutative_operands_p.
1660 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1661 for GE, GEU, and LEU. */
1664 canon_condition (rtx cond
)
1669 enum machine_mode mode
;
1671 code
= GET_CODE (cond
);
1672 op0
= XEXP (cond
, 0);
1673 op1
= XEXP (cond
, 1);
1675 if (swap_commutative_operands_p (op0
, op1
))
1677 code
= swap_condition (code
);
1683 mode
= GET_MODE (op0
);
1684 if (mode
== VOIDmode
)
1685 mode
= GET_MODE (op1
);
1686 gcc_assert (mode
!= VOIDmode
);
1688 if (CONST_INT_P (op1
)
1689 && GET_MODE_CLASS (mode
) != MODE_CC
1690 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1692 HOST_WIDE_INT const_val
= INTVAL (op1
);
1693 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1694 unsigned HOST_WIDE_INT max_val
1695 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1700 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1701 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1704 /* When cross-compiling, const_val might be sign-extended from
1705 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1707 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1708 != (((HOST_WIDE_INT
) 1
1709 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1710 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1714 if (uconst_val
< max_val
)
1715 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1719 if (uconst_val
!= 0)
1720 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1728 if (op0
!= XEXP (cond
, 0)
1729 || op1
!= XEXP (cond
, 1)
1730 || code
!= GET_CODE (cond
)
1731 || GET_MODE (cond
) != SImode
)
1732 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1737 /* Reverses CONDition; returns NULL if we cannot. */
1740 reversed_condition (rtx cond
)
1742 enum rtx_code reversed
;
1743 reversed
= reversed_comparison_code (cond
, NULL
);
1744 if (reversed
== UNKNOWN
)
1747 return gen_rtx_fmt_ee (reversed
,
1748 GET_MODE (cond
), XEXP (cond
, 0),
1752 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1753 set of altered regs. */
1756 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1758 rtx rev
, reve
, exp
= *expr
;
1760 /* If some register gets altered later, we do not really speak about its
1761 value at the time of comparison. */
1763 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1766 if (GET_CODE (cond
) == EQ
1767 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1769 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1773 if (!COMPARISON_P (exp
))
1776 rev
= reversed_condition (cond
);
1777 reve
= reversed_condition (exp
);
1779 cond
= canon_condition (cond
);
1780 exp
= canon_condition (exp
);
1782 rev
= canon_condition (rev
);
1784 reve
= canon_condition (reve
);
1786 if (rtx_equal_p (exp
, cond
))
1788 *expr
= const_true_rtx
;
1792 if (rev
&& rtx_equal_p (exp
, rev
))
1798 if (implies_p (cond
, exp
))
1800 *expr
= const_true_rtx
;
1804 if (reve
&& implies_p (cond
, reve
))
1810 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1812 if (rev
&& implies_p (exp
, rev
))
1818 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1819 if (rev
&& reve
&& implies_p (reve
, rev
))
1821 *expr
= const_true_rtx
;
1825 /* We would like to have some other tests here. TODO. */
1830 /* Use relationship between A and *B to eventually eliminate *B.
1831 OP is the operation we consider. */
1834 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1839 /* If A implies *B, we may replace *B by true. */
1840 if (implies_p (a
, *b
))
1841 *b
= const_true_rtx
;
1845 /* If *B implies A, we may replace *B by false. */
1846 if (implies_p (*b
, a
))
1855 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1856 operation we consider. */
1859 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1863 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1864 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1865 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1866 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1869 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1870 is a list, its elements are assumed to be combined using OP. */
1873 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1875 bool expression_valid
;
1876 rtx head
, tail
, last_valid_expr
;
1877 rtx_expr_list
*cond_list
;
1880 regset altered
, this_altered
;
1886 if (CONSTANT_P (*expr
))
1889 if (GET_CODE (*expr
) == EXPR_LIST
)
1891 head
= XEXP (*expr
, 0);
1892 tail
= XEXP (*expr
, 1);
1894 eliminate_implied_conditions (op
, &head
, tail
);
1899 neutral
= const_true_rtx
;
1904 neutral
= const0_rtx
;
1905 aggr
= const_true_rtx
;
1912 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1915 XEXP (*expr
, 0) = aggr
;
1916 XEXP (*expr
, 1) = NULL_RTX
;
1919 else if (head
== neutral
)
1922 simplify_using_initial_values (loop
, op
, expr
);
1925 simplify_using_initial_values (loop
, op
, &tail
);
1927 if (tail
&& XEXP (tail
, 0) == aggr
)
1933 XEXP (*expr
, 0) = head
;
1934 XEXP (*expr
, 1) = tail
;
1938 gcc_assert (op
== UNKNOWN
);
1941 if (for_each_rtx (expr
, replace_single_def_regs
, expr
) == 0)
1943 if (CONSTANT_P (*expr
))
1946 e
= loop_preheader_edge (loop
);
1947 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1950 altered
= ALLOC_REG_SET (®_obstack
);
1951 this_altered
= ALLOC_REG_SET (®_obstack
);
1953 expression_valid
= true;
1954 last_valid_expr
= *expr
;
1958 insn
= BB_END (e
->src
);
1959 if (any_condjump_p (insn
))
1961 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1963 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1964 cond
= reversed_condition (cond
);
1968 simplify_using_condition (cond
, expr
, altered
);
1972 if (CONSTANT_P (*expr
))
1974 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1976 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1977 if (CONSTANT_P (*expr
))
1981 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1985 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1993 CLEAR_REG_SET (this_altered
);
1994 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
1997 /* Kill all call clobbered registers. */
1999 hard_reg_set_iterator hrsi
;
2000 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2002 SET_REGNO_REG_SET (this_altered
, i
);
2005 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2007 rtx_expr_list
**pnote
, **pnote_next
;
2009 replace_in_expr (expr
, dest
, src
);
2010 if (CONSTANT_P (*expr
))
2013 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2016 rtx old_cond
= XEXP (note
, 0);
2018 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2019 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2021 /* We can no longer use a condition that has been simplified
2022 to a constant, and simplify_using_condition will abort if
2024 if (CONSTANT_P (XEXP (note
, 0)))
2026 *pnote
= *pnote_next
;
2028 free_EXPR_LIST_node (note
);
2030 /* Retry simplifications with this condition if either the
2031 expression or the condition changed. */
2032 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2033 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2038 rtx_expr_list
**pnote
, **pnote_next
;
2040 /* If we did not use this insn to make a replacement, any overlap
2041 between stores in this insn and our expression will cause the
2042 expression to become invalid. */
2043 if (for_each_rtx (expr
, altered_reg_used
, this_altered
))
2046 /* Likewise for the conditions. */
2047 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2050 rtx old_cond
= XEXP (note
, 0);
2052 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2053 if (for_each_rtx (&old_cond
, altered_reg_used
, this_altered
))
2055 *pnote
= *pnote_next
;
2057 free_EXPR_LIST_node (note
);
2062 if (CONSTANT_P (*expr
))
2065 IOR_REG_SET (altered
, this_altered
);
2067 /* If the expression now contains regs that have been altered, we
2068 can't return it to the caller. However, it is still valid for
2069 further simplification, so keep searching to see if we can
2070 eventually turn it into a constant. */
2071 if (for_each_rtx (expr
, altered_reg_used
, altered
))
2072 expression_valid
= false;
2073 if (expression_valid
)
2074 last_valid_expr
= *expr
;
2077 if (!single_pred_p (e
->src
)
2078 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2080 e
= single_pred_edge (e
->src
);
2084 free_EXPR_LIST_list (&cond_list
);
2085 if (!CONSTANT_P (*expr
))
2086 *expr
= last_valid_expr
;
2087 FREE_REG_SET (altered
);
2088 FREE_REG_SET (this_altered
);
2091 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2092 that IV occurs as left operands of comparison COND and its signedness
2093 is SIGNED_P to DESC. */
2096 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
2097 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2099 rtx mmin
, mmax
, cond_over
, cond_under
;
2101 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2102 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2104 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2113 if (cond_under
!= const0_rtx
)
2115 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2116 if (cond_over
!= const0_rtx
)
2117 desc
->noloop_assumptions
=
2118 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2125 if (cond_over
!= const0_rtx
)
2127 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2128 if (cond_under
!= const0_rtx
)
2129 desc
->noloop_assumptions
=
2130 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2134 if (cond_over
!= const0_rtx
)
2136 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2137 if (cond_under
!= const0_rtx
)
2139 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2147 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2150 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2151 subregs of the same mode if possible (sometimes it is necessary to add
2152 some assumptions to DESC). */
2155 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2156 enum rtx_code cond
, struct niter_desc
*desc
)
2158 enum machine_mode comp_mode
;
2161 /* If the ivs behave specially in the first iteration, or are
2162 added/multiplied after extending, we ignore them. */
2163 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2165 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2168 /* If there is some extend, it must match signedness of the comparison. */
2173 if (iv0
->extend
== IV_ZERO_EXTEND
2174 || iv1
->extend
== IV_ZERO_EXTEND
)
2181 if (iv0
->extend
== IV_SIGN_EXTEND
2182 || iv1
->extend
== IV_SIGN_EXTEND
)
2188 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2189 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2190 && iv0
->extend
!= iv1
->extend
)
2194 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2195 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2196 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2197 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2204 /* Values of both variables should be computed in the same mode. These
2205 might indeed be different, if we have comparison like
2207 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2209 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2210 in different modes. This does not seem impossible to handle, but
2211 it hardly ever occurs in practice.
2213 The only exception is the case when one of operands is invariant.
2214 For example pentium 3 generates comparisons like
2215 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2216 definitely do not want this prevent the optimization. */
2217 comp_mode
= iv0
->extend_mode
;
2218 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2219 comp_mode
= iv1
->extend_mode
;
2221 if (iv0
->extend_mode
!= comp_mode
)
2223 if (iv0
->mode
!= iv0
->extend_mode
2224 || iv0
->step
!= const0_rtx
)
2227 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2228 comp_mode
, iv0
->base
, iv0
->mode
);
2229 iv0
->extend_mode
= comp_mode
;
2232 if (iv1
->extend_mode
!= comp_mode
)
2234 if (iv1
->mode
!= iv1
->extend_mode
2235 || iv1
->step
!= const0_rtx
)
2238 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2239 comp_mode
, iv1
->base
, iv1
->mode
);
2240 iv1
->extend_mode
= comp_mode
;
2243 /* Check that both ivs belong to a range of a single mode. If one of the
2244 operands is an invariant, we may need to shorten it into the common
2246 if (iv0
->mode
== iv0
->extend_mode
2247 && iv0
->step
== const0_rtx
2248 && iv0
->mode
!= iv1
->mode
)
2249 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2251 if (iv1
->mode
== iv1
->extend_mode
2252 && iv1
->step
== const0_rtx
2253 && iv0
->mode
!= iv1
->mode
)
2254 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2256 if (iv0
->mode
!= iv1
->mode
)
2259 desc
->mode
= iv0
->mode
;
2260 desc
->signed_p
= signed_p
;
2265 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2266 result. This function is called from iv_number_of_iterations with
2267 a number of fields in DESC already filled in. OLD_NITER is the original
2268 expression for the number of iterations, before we tried to simplify it. */
2271 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2273 rtx niter
= desc
->niter_expr
;
2274 rtx mmin
, mmax
, cmp
;
2276 uint64_t andmax
= 0;
2278 /* We used to look for constant operand 0 of AND,
2279 but canonicalization should always make this impossible. */
2280 gcc_checking_assert (GET_CODE (niter
) != AND
2281 || !CONST_INT_P (XEXP (niter
, 0)));
2283 if (GET_CODE (niter
) == AND
2284 && CONST_INT_P (XEXP (niter
, 1)))
2286 andmax
= UINTVAL (XEXP (niter
, 1));
2287 niter
= XEXP (niter
, 0);
2290 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2291 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2293 if (GET_CODE (niter
) == UDIV
)
2295 if (!CONST_INT_P (XEXP (niter
, 1)))
2297 inc
= INTVAL (XEXP (niter
, 1));
2298 niter
= XEXP (niter
, 0);
2303 /* We could use a binary search here, but for now improving the upper
2304 bound by just one eliminates one important corner case. */
2305 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2306 desc
->mode
, old_niter
, mmax
);
2307 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2308 if (cmp
== const_true_rtx
)
2313 fprintf (dump_file
, ";; improved upper bound by one.\n");
2317 nmax
= MIN (nmax
, andmax
);
2319 fprintf (dump_file
, ";; Determined upper bound %"PRId64
".\n",
2324 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2325 the result into DESC. Very similar to determine_number_of_iterations
2326 (basically its rtl version), complicated by things like subregs. */
2329 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2330 struct niter_desc
*desc
)
2332 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2333 struct rtx_iv iv0
, iv1
, tmp_iv
;
2334 rtx assumption
, may_not_xform
;
2336 enum machine_mode mode
, comp_mode
;
2337 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2338 uint64_t s
, size
, d
, inv
, max
;
2339 int64_t up
, down
, inc
, step_val
;
2340 int was_sharp
= false;
2344 /* The meaning of these assumptions is this:
2346 then the rest of information does not have to be valid
2347 if noloop_assumptions then the loop does not roll
2348 if infinite then this exit is never used */
2350 desc
->assumptions
= NULL_RTX
;
2351 desc
->noloop_assumptions
= NULL_RTX
;
2352 desc
->infinite
= NULL_RTX
;
2353 desc
->simple_p
= true;
2355 desc
->const_iter
= false;
2356 desc
->niter_expr
= NULL_RTX
;
2358 cond
= GET_CODE (condition
);
2359 gcc_assert (COMPARISON_P (condition
));
2361 mode
= GET_MODE (XEXP (condition
, 0));
2362 if (mode
== VOIDmode
)
2363 mode
= GET_MODE (XEXP (condition
, 1));
2364 /* The constant comparisons should be folded. */
2365 gcc_assert (mode
!= VOIDmode
);
2367 /* We only handle integers or pointers. */
2368 if (GET_MODE_CLASS (mode
) != MODE_INT
2369 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2372 op0
= XEXP (condition
, 0);
2373 if (!iv_analyze (insn
, op0
, &iv0
))
2375 if (iv0
.extend_mode
== VOIDmode
)
2376 iv0
.mode
= iv0
.extend_mode
= mode
;
2378 op1
= XEXP (condition
, 1);
2379 if (!iv_analyze (insn
, op1
, &iv1
))
2381 if (iv1
.extend_mode
== VOIDmode
)
2382 iv1
.mode
= iv1
.extend_mode
= mode
;
2384 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2385 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2388 /* Check condition and normalize it. */
2396 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2397 cond
= swap_condition (cond
);
2409 /* Handle extends. This is relatively nontrivial, so we only try in some
2410 easy cases, when we can canonicalize the ivs (possibly by adding some
2411 assumptions) to shape subreg (base + i * step). This function also fills
2412 in desc->mode and desc->signed_p. */
2414 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2417 comp_mode
= iv0
.extend_mode
;
2419 size
= GET_MODE_BITSIZE (mode
);
2420 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2421 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2422 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2424 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2427 /* We can take care of the case of two induction variables chasing each other
2428 if the test is NE. I have never seen a loop using it, but still it is
2430 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2435 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2436 iv1
.step
= const0_rtx
;
2439 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2440 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2442 /* This is either infinite loop or the one that ends immediately, depending
2443 on initial values. Unswitching should remove this kind of conditions. */
2444 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2449 if (iv0
.step
== const0_rtx
)
2450 step_val
= -INTVAL (iv1
.step
);
2452 step_val
= INTVAL (iv0
.step
);
2454 /* Ignore loops of while (i-- < 10) type. */
2458 step_is_pow2
= !(step_val
& (step_val
- 1));
2462 /* We do not care about whether the step is power of two in this
2464 step_is_pow2
= false;
2468 /* Some more condition normalization. We must record some assumptions
2469 due to overflows. */
2474 /* We want to take care only of non-sharp relationals; this is easy,
2475 as in cases the overflow would make the transformation unsafe
2476 the loop does not roll. Seemingly it would make more sense to want
2477 to take care of sharp relationals instead, as NE is more similar to
2478 them, but the problem is that here the transformation would be more
2479 difficult due to possibly infinite loops. */
2480 if (iv0
.step
== const0_rtx
)
2482 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2483 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2485 if (assumption
== const_true_rtx
)
2486 goto zero_iter_simplify
;
2487 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2488 iv0
.base
, const1_rtx
);
2492 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2493 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2495 if (assumption
== const_true_rtx
)
2496 goto zero_iter_simplify
;
2497 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2498 iv1
.base
, constm1_rtx
);
2501 if (assumption
!= const0_rtx
)
2502 desc
->noloop_assumptions
=
2503 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2504 cond
= (cond
== LT
) ? LE
: LEU
;
2506 /* It will be useful to be able to tell the difference once more in
2507 LE -> NE reduction. */
2513 /* Take care of trivially infinite loops. */
2516 if (iv0
.step
== const0_rtx
)
2518 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2519 if (rtx_equal_p (tmp
, mode_mmin
))
2522 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2523 /* Fill in the remaining fields somehow. */
2524 goto zero_iter_simplify
;
2529 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2530 if (rtx_equal_p (tmp
, mode_mmax
))
2533 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2534 /* Fill in the remaining fields somehow. */
2535 goto zero_iter_simplify
;
2540 /* If we can we want to take care of NE conditions instead of size
2541 comparisons, as they are much more friendly (most importantly
2542 this takes care of special handling of loops with step 1). We can
2543 do it if we first check that upper bound is greater or equal to
2544 lower bound, their difference is constant c modulo step and that
2545 there is not an overflow. */
2548 if (iv0
.step
== const0_rtx
)
2549 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2552 step
= lowpart_subreg (mode
, step
, comp_mode
);
2553 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2554 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2555 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2556 may_xform
= const0_rtx
;
2557 may_not_xform
= const_true_rtx
;
2559 if (CONST_INT_P (delta
))
2561 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2563 /* A special case. We have transformed condition of type
2564 for (i = 0; i < 4; i += 4)
2566 for (i = 0; i <= 3; i += 4)
2567 obviously if the test for overflow during that transformation
2568 passed, we cannot overflow here. Most importantly any
2569 loop with sharp end condition and step 1 falls into this
2570 category, so handling this case specially is definitely
2571 worth the troubles. */
2572 may_xform
= const_true_rtx
;
2574 else if (iv0
.step
== const0_rtx
)
2576 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2577 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2578 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2579 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2580 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2582 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2588 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2589 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2590 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2591 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2592 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2594 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2600 if (may_xform
!= const0_rtx
)
2602 /* We perform the transformation always provided that it is not
2603 completely senseless. This is OK, as we would need this assumption
2604 to determine the number of iterations anyway. */
2605 if (may_xform
!= const_true_rtx
)
2607 /* If the step is a power of two and the final value we have
2608 computed overflows, the cycle is infinite. Otherwise it
2609 is nontrivial to compute the number of iterations. */
2611 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2614 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2618 /* We are going to lose some information about upper bound on
2619 number of iterations in this step, so record the information
2621 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2622 if (CONST_INT_P (iv1
.base
))
2623 up
= INTVAL (iv1
.base
);
2625 up
= INTVAL (mode_mmax
) - inc
;
2626 down
= INTVAL (CONST_INT_P (iv0
.base
)
2629 max
= (up
- down
) / inc
+ 1;
2631 && !desc
->assumptions
)
2632 record_niter_bound (loop
, max
, false, true);
2634 if (iv0
.step
== const0_rtx
)
2636 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2637 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2641 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2642 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2645 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2646 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2647 assumption
= simplify_gen_relational (reverse_condition (cond
),
2648 SImode
, mode
, tmp0
, tmp1
);
2649 if (assumption
== const_true_rtx
)
2650 goto zero_iter_simplify
;
2651 else if (assumption
!= const0_rtx
)
2652 desc
->noloop_assumptions
=
2653 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2658 /* Count the number of iterations. */
2661 /* Everything we do here is just arithmetics modulo size of mode. This
2662 makes us able to do more involved computations of number of iterations
2663 than in other cases. First transform the condition into shape
2664 s * i <> c, with s positive. */
2665 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2666 iv0
.base
= const0_rtx
;
2667 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2668 iv1
.step
= const0_rtx
;
2669 if (INTVAL (iv0
.step
) < 0)
2671 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2672 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2674 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2676 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2677 is infinite. Otherwise, the number of iterations is
2678 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2679 s
= INTVAL (iv0
.step
); d
= 1;
2686 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2688 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2689 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2690 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2691 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2693 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2694 inv
= inverse (s
, size
);
2695 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2696 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2700 if (iv1
.step
== const0_rtx
)
2701 /* Condition in shape a + s * i <= b
2702 We must know that b + s does not overflow and a <= b + s and then we
2703 can compute number of iterations as (b + s - a) / s. (It might
2704 seem that we in fact could be more clever about testing the b + s
2705 overflow condition using some information about b - a mod s,
2706 but it was already taken into account during LE -> NE transform). */
2709 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2710 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2712 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2713 lowpart_subreg (mode
, step
,
2719 /* If s is power of 2, we know that the loop is infinite if
2720 a % s <= b % s and b + s overflows. */
2721 assumption
= simplify_gen_relational (reverse_condition (cond
),
2725 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2726 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2727 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2728 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2730 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2734 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2737 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2740 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2741 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2742 assumption
= simplify_gen_relational (reverse_condition (cond
),
2743 SImode
, mode
, tmp0
, tmp
);
2745 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2746 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2750 /* Condition in shape a <= b - s * i
2751 We must know that a - s does not overflow and a - s <= b and then
2752 we can again compute number of iterations as (b - (a - s)) / s. */
2753 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2754 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2755 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2757 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2758 lowpart_subreg (mode
, step
, comp_mode
));
2763 /* If s is power of 2, we know that the loop is infinite if
2764 a % s <= b % s and a - s overflows. */
2765 assumption
= simplify_gen_relational (reverse_condition (cond
),
2769 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2770 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2771 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2772 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2774 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2778 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2781 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2784 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2785 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2786 assumption
= simplify_gen_relational (reverse_condition (cond
),
2789 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2790 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2792 if (assumption
== const_true_rtx
)
2793 goto zero_iter_simplify
;
2794 else if (assumption
!= const0_rtx
)
2795 desc
->noloop_assumptions
=
2796 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2797 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2798 desc
->niter_expr
= delta
;
2801 old_niter
= desc
->niter_expr
;
2803 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2804 if (desc
->assumptions
2805 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2807 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2808 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2809 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2811 /* Rerun the simplification. Consider code (created by copying loop headers)
2823 The first pass determines that i = 0, the second pass uses it to eliminate
2824 noloop assumption. */
2826 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2827 if (desc
->assumptions
2828 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2830 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2831 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2832 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2834 if (desc
->noloop_assumptions
2835 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2838 if (CONST_INT_P (desc
->niter_expr
))
2840 uint64_t val
= INTVAL (desc
->niter_expr
);
2842 desc
->const_iter
= true;
2843 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2845 && !desc
->assumptions
)
2846 record_niter_bound (loop
, desc
->niter
, false, true);
2850 max
= determine_max_iter (loop
, desc
, old_niter
);
2852 goto zero_iter_simplify
;
2854 && !desc
->assumptions
)
2855 record_niter_bound (loop
, max
, false, true);
2857 /* simplify_using_initial_values does a copy propagation on the registers
2858 in the expression for the number of iterations. This prolongs life
2859 ranges of registers and increases register pressure, and usually
2860 brings no gain (and if it happens to do, the cse pass will take care
2861 of it anyway). So prevent this behavior, unless it enabled us to
2862 derive that the number of iterations is a constant. */
2863 desc
->niter_expr
= old_niter
;
2869 /* Simplify the assumptions. */
2870 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2871 if (desc
->assumptions
2872 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2874 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2878 desc
->const_iter
= true;
2880 record_niter_bound (loop
, 0, true, true);
2881 desc
->noloop_assumptions
= NULL_RTX
;
2882 desc
->niter_expr
= const0_rtx
;
2886 desc
->simple_p
= false;
2890 /* Checks whether E is a simple exit from LOOP and stores its description
2894 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2896 basic_block exit_bb
;
2902 desc
->simple_p
= false;
2904 /* It must belong directly to the loop. */
2905 if (exit_bb
->loop_father
!= loop
)
2908 /* It must be tested (at least) once during any iteration. */
2909 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2912 /* It must end in a simple conditional jump. */
2913 if (!any_condjump_p (BB_END (exit_bb
)))
2916 ein
= EDGE_SUCC (exit_bb
, 0);
2918 ein
= EDGE_SUCC (exit_bb
, 1);
2921 desc
->in_edge
= ein
;
2923 /* Test whether the condition is suitable. */
2924 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2927 if (ein
->flags
& EDGE_FALLTHRU
)
2929 condition
= reversed_condition (condition
);
2934 /* Check that we are able to determine number of iterations and fill
2935 in information about it. */
2936 iv_number_of_iterations (loop
, at
, condition
, desc
);
2939 /* Finds a simple exit of LOOP and stores its description into DESC. */
2942 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2947 struct niter_desc act
;
2951 desc
->simple_p
= false;
2952 body
= get_loop_body (loop
);
2954 for (i
= 0; i
< loop
->num_nodes
; i
++)
2956 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2958 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2961 check_simple_exit (loop
, e
, &act
);
2969 /* Prefer constant iterations; the less the better. */
2971 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2974 /* Also if the actual exit may be infinite, while the old one
2975 not, prefer the old one. */
2976 if (act
.infinite
&& !desc
->infinite
)
2988 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2989 fprintf (dump_file
, " simple exit %d -> %d\n",
2990 desc
->out_edge
->src
->index
,
2991 desc
->out_edge
->dest
->index
);
2992 if (desc
->assumptions
)
2994 fprintf (dump_file
, " assumptions: ");
2995 print_rtl (dump_file
, desc
->assumptions
);
2996 fprintf (dump_file
, "\n");
2998 if (desc
->noloop_assumptions
)
3000 fprintf (dump_file
, " does not roll if: ");
3001 print_rtl (dump_file
, desc
->noloop_assumptions
);
3002 fprintf (dump_file
, "\n");
3006 fprintf (dump_file
, " infinite if: ");
3007 print_rtl (dump_file
, desc
->infinite
);
3008 fprintf (dump_file
, "\n");
3011 fprintf (dump_file
, " number of iterations: ");
3012 print_rtl (dump_file
, desc
->niter_expr
);
3013 fprintf (dump_file
, "\n");
3015 fprintf (dump_file
, " upper bound: %li\n",
3016 (long)get_max_loop_iterations_int (loop
));
3017 fprintf (dump_file
, " realistic bound: %li\n",
3018 (long)get_estimated_loop_iterations_int (loop
));
3021 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3027 /* Creates a simple loop description of LOOP if it was not computed
3031 get_simple_loop_desc (struct loop
*loop
)
3033 struct niter_desc
*desc
= simple_loop_desc (loop
);
3038 /* At least desc->infinite is not always initialized by
3039 find_simple_loop_exit. */
3040 desc
= ggc_cleared_alloc
<niter_desc
> ();
3041 iv_analysis_loop_init (loop
);
3042 find_simple_exit (loop
, desc
);
3043 loop
->simple_loop_desc
= desc
;
3045 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3047 const char *wording
;
3049 /* Assume that no overflow happens and that the loop is finite.
3050 We already warned at the tree level if we ran optimizations there. */
3051 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3056 flag_unsafe_loop_optimizations
3057 ? N_("assuming that the loop is not infinite")
3058 : N_("cannot optimize possibly infinite loops");
3059 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3062 if (desc
->assumptions
)
3065 flag_unsafe_loop_optimizations
3066 ? N_("assuming that the loop counter does not overflow")
3067 : N_("cannot optimize loop, the loop counter may overflow");
3068 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3073 if (flag_unsafe_loop_optimizations
)
3075 desc
->assumptions
= NULL_RTX
;
3076 desc
->infinite
= NULL_RTX
;
3083 /* Releases simple loop description for LOOP. */
3086 free_simple_loop_desc (struct loop
*loop
)
3088 struct niter_desc
*desc
= simple_loop_desc (loop
);
3094 loop
->simple_loop_desc
= NULL
;