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
, 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
);
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
, 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
= 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
, 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
;
961 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
967 if (!iv_analyze_op (insn
, rhs
, iv
))
970 if (iv
->mode
== VOIDmode
)
973 iv
->extend_mode
= mode
;
989 omode
= GET_MODE (op0
);
1000 mby
= XEXP (rhs
, 1);
1001 if (!CONSTANT_P (mby
))
1007 if (!CONSTANT_P (mby
))
1012 op0
= XEXP (rhs
, 0);
1013 mby
= XEXP (rhs
, 1);
1014 if (!CONSTANT_P (mby
))
1023 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1027 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1033 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1038 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1049 if (!iv_add (&iv0
, &iv1
, code
))
1054 if (!iv_mult (&iv0
, mby
))
1059 if (!iv_shift (&iv0
, mby
))
1068 return iv
->base
!= NULL_RTX
;
1071 /* Analyzes iv DEF and stores the result to *IV. */
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
);
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
))
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
;
1104 set
= single_set (insn
);
1108 if (!REG_P (SET_DEST (set
)))
1111 gcc_assert (SET_DEST (set
) == reg
);
1112 rhs
= find_reg_equal_equiv_note (insn
);
1114 rhs
= XEXP (rhs
, 0);
1116 rhs
= SET_SRC (set
);
1118 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1119 record_iv (def
, iv
);
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. */
1137 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1140 enum iv_grd_result res
;
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
))
1157 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1160 return iv_subreg (iv
, GET_MODE (op
));
1164 res
= iv_get_reaching_def (insn
, op
, &def
);
1165 if (res
== GRD_INVALID
)
1168 fprintf (dump_file
, " not simple.\n");
1173 if (res
== GRD_INVARIANT
)
1175 iv_constant (iv
, op
, VOIDmode
);
1179 fprintf (dump_file
, " ");
1180 dump_iv_info (dump_file
, iv
);
1181 fprintf (dump_file
, "\n");
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. */
1195 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
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
1203 if (simple_reg_p (val
))
1205 if (GET_CODE (val
) == SUBREG
)
1206 reg
= SUBREG_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. */
1220 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1224 adef
= df_find_def (insn
, def
);
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. */
1236 biv_p (rtx insn
, rtx reg
)
1239 df_ref def
, last_def
;
1241 if (!simple_reg_p (reg
))
1244 def
= df_find_def (insn
, reg
);
1245 gcc_assert (def
!= NULL
);
1246 if (!latch_dominating_def (reg
, &last_def
))
1248 if (last_def
!= def
)
1251 if (!iv_analyze_biv (reg
, &iv
))
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
)
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
));
1275 if (iv
->extend_mode
== iv
->mode
)
1278 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1280 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
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
,
1292 /* Free the data for an induction variable analysis. */
1295 iv_analysis_done (void)
1301 df_finish_pass (true);
1303 free (iv_ref_table
);
1304 iv_ref_table
= NULL
;
1305 iv_ref_table_size
= 0;
1309 /* Computes inverse to X modulo (1 << MOD). */
1312 inverse (uint64_t x
, int mod
)
1315 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1319 for (i
= 0; i
< mod
- 1; i
++)
1321 rslt
= (rslt
* x
) & mask
;
1328 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1331 altered_reg_used (rtx
*reg
, void *alt
)
1336 return REGNO_REG_SET_P ((bitmap
) alt
, REGNO (*reg
));
1339 /* Marks registers altered by EXPR in set ALT. */
1342 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1344 if (GET_CODE (expr
) == SUBREG
)
1345 expr
= SUBREG_REG (expr
);
1349 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1352 /* Checks whether RHS is simple enough to process. */
1355 simple_rhs_p (rtx rhs
)
1359 if (function_invariant_p (rhs
)
1360 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1363 switch (GET_CODE (rhs
))
1368 op0
= XEXP (rhs
, 0);
1369 op1
= XEXP (rhs
, 1);
1370 /* Allow reg OP const and reg OP reg. */
1371 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1372 && !function_invariant_p (op0
))
1374 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1375 && !function_invariant_p (op1
))
1384 op0
= XEXP (rhs
, 0);
1385 op1
= XEXP (rhs
, 1);
1386 /* Allow reg OP const. */
1387 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1389 if (!function_invariant_p (op1
))
1399 /* If REG has a single definition, replace it with its known value in EXPR.
1400 Callback for for_each_rtx. */
1403 replace_single_def_regs (rtx
*reg
, void *expr1
)
1408 rtx
*expr
= (rtx
*)expr1
;
1413 regno
= REGNO (*reg
);
1417 adef
= DF_REG_DEF_CHAIN (regno
);
1418 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1419 || DF_REF_IS_ARTIFICIAL (adef
))
1422 set
= single_set (DF_REF_INSN (adef
));
1423 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1424 || REGNO (SET_DEST (set
)) != regno
)
1427 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1429 if (note
&& function_invariant_p (XEXP (note
, 0)))
1431 src
= XEXP (note
, 0);
1434 src
= SET_SRC (set
);
1438 regno
= REGNO (src
);
1443 if (!function_invariant_p (src
))
1446 *expr
= simplify_replace_rtx (*expr
, *reg
, src
);
1450 /* A subroutine of simplify_using_initial_values, this function examines INSN
1451 to see if it contains a suitable set that we can use to make a replacement.
1452 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1453 the set; return false otherwise. */
1456 suitable_set_for_replacement (rtx insn
, rtx
*dest
, rtx
*src
)
1458 rtx set
= single_set (insn
);
1459 rtx lhs
= NULL_RTX
, rhs
;
1464 lhs
= SET_DEST (set
);
1468 rhs
= find_reg_equal_equiv_note (insn
);
1470 rhs
= XEXP (rhs
, 0);
1472 rhs
= SET_SRC (set
);
1474 if (!simple_rhs_p (rhs
))
1482 /* Using the data returned by suitable_set_for_replacement, replace DEST
1483 with SRC in *EXPR and return the new expression. Also call
1484 replace_single_def_regs if the replacement changed something. */
1486 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1489 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1492 while (for_each_rtx (expr
, replace_single_def_regs
, expr
) != 0)
1496 /* Checks whether A implies B. */
1499 implies_p (rtx a
, rtx b
)
1501 rtx op0
, op1
, opb0
, opb1
, r
;
1502 enum machine_mode mode
;
1504 if (rtx_equal_p (a
, b
))
1507 if (GET_CODE (a
) == EQ
)
1513 || (GET_CODE (op0
) == SUBREG
1514 && REG_P (SUBREG_REG (op0
))))
1516 r
= simplify_replace_rtx (b
, op0
, op1
);
1517 if (r
== const_true_rtx
)
1522 || (GET_CODE (op1
) == SUBREG
1523 && REG_P (SUBREG_REG (op1
))))
1525 r
= simplify_replace_rtx (b
, op1
, op0
);
1526 if (r
== const_true_rtx
)
1531 if (b
== const_true_rtx
)
1534 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1535 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1536 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1537 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1545 mode
= GET_MODE (op0
);
1546 if (mode
!= GET_MODE (opb0
))
1548 else if (mode
== VOIDmode
)
1550 mode
= GET_MODE (op1
);
1551 if (mode
!= GET_MODE (opb1
))
1555 /* A < B implies A + 1 <= B. */
1556 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1557 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1560 if (GET_CODE (a
) == GT
)
1567 if (GET_CODE (b
) == GE
)
1574 if (SCALAR_INT_MODE_P (mode
)
1575 && rtx_equal_p (op1
, opb1
)
1576 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1581 /* A < B or A > B imply A != B. TODO: Likewise
1582 A + n < B implies A != B + n if neither wraps. */
1583 if (GET_CODE (b
) == NE
1584 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1585 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1587 if (rtx_equal_p (op0
, opb0
)
1588 && rtx_equal_p (op1
, opb1
))
1592 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1593 if (GET_CODE (a
) == NE
1594 && op1
== const0_rtx
)
1596 if ((GET_CODE (b
) == GTU
1597 && opb1
== const0_rtx
)
1598 || (GET_CODE (b
) == GEU
1599 && opb1
== const1_rtx
))
1600 return rtx_equal_p (op0
, opb0
);
1603 /* A != N is equivalent to A - (N + 1) <u -1. */
1604 if (GET_CODE (a
) == NE
1605 && CONST_INT_P (op1
)
1606 && GET_CODE (b
) == LTU
1607 && opb1
== constm1_rtx
1608 && GET_CODE (opb0
) == PLUS
1609 && CONST_INT_P (XEXP (opb0
, 1))
1610 /* Avoid overflows. */
1611 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1612 != ((unsigned HOST_WIDE_INT
)1
1613 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1614 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1615 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1617 /* Likewise, A != N implies A - N > 0. */
1618 if (GET_CODE (a
) == NE
1619 && CONST_INT_P (op1
))
1621 if (GET_CODE (b
) == GTU
1622 && GET_CODE (opb0
) == PLUS
1623 && opb1
== const0_rtx
1624 && CONST_INT_P (XEXP (opb0
, 1))
1625 /* Avoid overflows. */
1626 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1627 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1628 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1629 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1630 if (GET_CODE (b
) == GEU
1631 && GET_CODE (opb0
) == PLUS
1632 && opb1
== const1_rtx
1633 && CONST_INT_P (XEXP (opb0
, 1))
1634 /* Avoid overflows. */
1635 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1636 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1637 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1638 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1641 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1642 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1643 && CONST_INT_P (op1
)
1644 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1645 || INTVAL (op1
) >= 0)
1646 && GET_CODE (b
) == LTU
1647 && CONST_INT_P (opb1
)
1648 && rtx_equal_p (op0
, opb0
))
1649 return INTVAL (opb1
) < 0;
1654 /* Canonicalizes COND so that
1656 (1) Ensure that operands are ordered according to
1657 swap_commutative_operands_p.
1658 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1659 for GE, GEU, and LEU. */
1662 canon_condition (rtx cond
)
1667 enum machine_mode mode
;
1669 code
= GET_CODE (cond
);
1670 op0
= XEXP (cond
, 0);
1671 op1
= XEXP (cond
, 1);
1673 if (swap_commutative_operands_p (op0
, op1
))
1675 code
= swap_condition (code
);
1681 mode
= GET_MODE (op0
);
1682 if (mode
== VOIDmode
)
1683 mode
= GET_MODE (op1
);
1684 gcc_assert (mode
!= VOIDmode
);
1686 if (CONST_INT_P (op1
)
1687 && GET_MODE_CLASS (mode
) != MODE_CC
1688 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1690 HOST_WIDE_INT const_val
= INTVAL (op1
);
1691 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1692 unsigned HOST_WIDE_INT max_val
1693 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1698 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1699 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1702 /* When cross-compiling, const_val might be sign-extended from
1703 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1705 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1706 != (((HOST_WIDE_INT
) 1
1707 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1708 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1712 if (uconst_val
< max_val
)
1713 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1717 if (uconst_val
!= 0)
1718 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1726 if (op0
!= XEXP (cond
, 0)
1727 || op1
!= XEXP (cond
, 1)
1728 || code
!= GET_CODE (cond
)
1729 || GET_MODE (cond
) != SImode
)
1730 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1735 /* Reverses CONDition; returns NULL if we cannot. */
1738 reversed_condition (rtx cond
)
1740 enum rtx_code reversed
;
1741 reversed
= reversed_comparison_code (cond
, NULL
);
1742 if (reversed
== UNKNOWN
)
1745 return gen_rtx_fmt_ee (reversed
,
1746 GET_MODE (cond
), XEXP (cond
, 0),
1750 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1751 set of altered regs. */
1754 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1756 rtx rev
, reve
, exp
= *expr
;
1758 /* If some register gets altered later, we do not really speak about its
1759 value at the time of comparison. */
1761 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1764 if (GET_CODE (cond
) == EQ
1765 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1767 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1771 if (!COMPARISON_P (exp
))
1774 rev
= reversed_condition (cond
);
1775 reve
= reversed_condition (exp
);
1777 cond
= canon_condition (cond
);
1778 exp
= canon_condition (exp
);
1780 rev
= canon_condition (rev
);
1782 reve
= canon_condition (reve
);
1784 if (rtx_equal_p (exp
, cond
))
1786 *expr
= const_true_rtx
;
1790 if (rev
&& rtx_equal_p (exp
, rev
))
1796 if (implies_p (cond
, exp
))
1798 *expr
= const_true_rtx
;
1802 if (reve
&& implies_p (cond
, reve
))
1808 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1810 if (rev
&& implies_p (exp
, rev
))
1816 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1817 if (rev
&& reve
&& implies_p (reve
, rev
))
1819 *expr
= const_true_rtx
;
1823 /* We would like to have some other tests here. TODO. */
1828 /* Use relationship between A and *B to eventually eliminate *B.
1829 OP is the operation we consider. */
1832 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1837 /* If A implies *B, we may replace *B by true. */
1838 if (implies_p (a
, *b
))
1839 *b
= const_true_rtx
;
1843 /* If *B implies A, we may replace *B by false. */
1844 if (implies_p (*b
, a
))
1853 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1854 operation we consider. */
1857 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1861 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1862 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1863 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1864 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1867 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1868 is a list, its elements are assumed to be combined using OP. */
1871 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1873 bool expression_valid
;
1874 rtx head
, tail
, insn
, cond_list
, last_valid_expr
;
1876 regset altered
, this_altered
;
1882 if (CONSTANT_P (*expr
))
1885 if (GET_CODE (*expr
) == EXPR_LIST
)
1887 head
= XEXP (*expr
, 0);
1888 tail
= XEXP (*expr
, 1);
1890 eliminate_implied_conditions (op
, &head
, tail
);
1895 neutral
= const_true_rtx
;
1900 neutral
= const0_rtx
;
1901 aggr
= const_true_rtx
;
1908 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1911 XEXP (*expr
, 0) = aggr
;
1912 XEXP (*expr
, 1) = NULL_RTX
;
1915 else if (head
== neutral
)
1918 simplify_using_initial_values (loop
, op
, expr
);
1921 simplify_using_initial_values (loop
, op
, &tail
);
1923 if (tail
&& XEXP (tail
, 0) == aggr
)
1929 XEXP (*expr
, 0) = head
;
1930 XEXP (*expr
, 1) = tail
;
1934 gcc_assert (op
== UNKNOWN
);
1937 if (for_each_rtx (expr
, replace_single_def_regs
, expr
) == 0)
1939 if (CONSTANT_P (*expr
))
1942 e
= loop_preheader_edge (loop
);
1943 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1946 altered
= ALLOC_REG_SET (®_obstack
);
1947 this_altered
= ALLOC_REG_SET (®_obstack
);
1949 expression_valid
= true;
1950 last_valid_expr
= *expr
;
1951 cond_list
= NULL_RTX
;
1954 insn
= BB_END (e
->src
);
1955 if (any_condjump_p (insn
))
1957 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1959 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1960 cond
= reversed_condition (cond
);
1964 simplify_using_condition (cond
, expr
, altered
);
1968 if (CONSTANT_P (*expr
))
1970 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1972 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1973 if (CONSTANT_P (*expr
))
1977 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1981 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1989 CLEAR_REG_SET (this_altered
);
1990 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
1993 /* Kill all call clobbered registers. */
1995 hard_reg_set_iterator hrsi
;
1996 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
1998 SET_REGNO_REG_SET (this_altered
, i
);
2001 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2003 rtx
*pnote
, *pnote_next
;
2005 replace_in_expr (expr
, dest
, src
);
2006 if (CONSTANT_P (*expr
))
2009 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2012 rtx old_cond
= XEXP (note
, 0);
2014 pnote_next
= &XEXP (note
, 1);
2015 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2017 /* We can no longer use a condition that has been simplified
2018 to a constant, and simplify_using_condition will abort if
2020 if (CONSTANT_P (XEXP (note
, 0)))
2022 *pnote
= *pnote_next
;
2024 free_EXPR_LIST_node (note
);
2026 /* Retry simplifications with this condition if either the
2027 expression or the condition changed. */
2028 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2029 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2034 rtx
*pnote
, *pnote_next
;
2036 /* If we did not use this insn to make a replacement, any overlap
2037 between stores in this insn and our expression will cause the
2038 expression to become invalid. */
2039 if (for_each_rtx (expr
, altered_reg_used
, this_altered
))
2042 /* Likewise for the conditions. */
2043 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2046 rtx old_cond
= XEXP (note
, 0);
2048 pnote_next
= &XEXP (note
, 1);
2049 if (for_each_rtx (&old_cond
, altered_reg_used
, this_altered
))
2051 *pnote
= *pnote_next
;
2053 free_EXPR_LIST_node (note
);
2058 if (CONSTANT_P (*expr
))
2061 IOR_REG_SET (altered
, this_altered
);
2063 /* If the expression now contains regs that have been altered, we
2064 can't return it to the caller. However, it is still valid for
2065 further simplification, so keep searching to see if we can
2066 eventually turn it into a constant. */
2067 if (for_each_rtx (expr
, altered_reg_used
, altered
))
2068 expression_valid
= false;
2069 if (expression_valid
)
2070 last_valid_expr
= *expr
;
2073 if (!single_pred_p (e
->src
)
2074 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2076 e
= single_pred_edge (e
->src
);
2080 free_EXPR_LIST_list (&cond_list
);
2081 if (!CONSTANT_P (*expr
))
2082 *expr
= last_valid_expr
;
2083 FREE_REG_SET (altered
);
2084 FREE_REG_SET (this_altered
);
2087 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2088 that IV occurs as left operands of comparison COND and its signedness
2089 is SIGNED_P to DESC. */
2092 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
2093 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2095 rtx mmin
, mmax
, cond_over
, cond_under
;
2097 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2098 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2100 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2109 if (cond_under
!= const0_rtx
)
2111 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2112 if (cond_over
!= const0_rtx
)
2113 desc
->noloop_assumptions
=
2114 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2121 if (cond_over
!= const0_rtx
)
2123 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2124 if (cond_under
!= const0_rtx
)
2125 desc
->noloop_assumptions
=
2126 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2130 if (cond_over
!= const0_rtx
)
2132 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2133 if (cond_under
!= const0_rtx
)
2135 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2143 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2146 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2147 subregs of the same mode if possible (sometimes it is necessary to add
2148 some assumptions to DESC). */
2151 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2152 enum rtx_code cond
, struct niter_desc
*desc
)
2154 enum machine_mode comp_mode
;
2157 /* If the ivs behave specially in the first iteration, or are
2158 added/multiplied after extending, we ignore them. */
2159 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2161 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2164 /* If there is some extend, it must match signedness of the comparison. */
2169 if (iv0
->extend
== IV_ZERO_EXTEND
2170 || iv1
->extend
== IV_ZERO_EXTEND
)
2177 if (iv0
->extend
== IV_SIGN_EXTEND
2178 || iv1
->extend
== IV_SIGN_EXTEND
)
2184 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2185 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2186 && iv0
->extend
!= iv1
->extend
)
2190 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2191 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2192 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2193 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2200 /* Values of both variables should be computed in the same mode. These
2201 might indeed be different, if we have comparison like
2203 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2205 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2206 in different modes. This does not seem impossible to handle, but
2207 it hardly ever occurs in practice.
2209 The only exception is the case when one of operands is invariant.
2210 For example pentium 3 generates comparisons like
2211 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2212 definitely do not want this prevent the optimization. */
2213 comp_mode
= iv0
->extend_mode
;
2214 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2215 comp_mode
= iv1
->extend_mode
;
2217 if (iv0
->extend_mode
!= comp_mode
)
2219 if (iv0
->mode
!= iv0
->extend_mode
2220 || iv0
->step
!= const0_rtx
)
2223 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2224 comp_mode
, iv0
->base
, iv0
->mode
);
2225 iv0
->extend_mode
= comp_mode
;
2228 if (iv1
->extend_mode
!= comp_mode
)
2230 if (iv1
->mode
!= iv1
->extend_mode
2231 || iv1
->step
!= const0_rtx
)
2234 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2235 comp_mode
, iv1
->base
, iv1
->mode
);
2236 iv1
->extend_mode
= comp_mode
;
2239 /* Check that both ivs belong to a range of a single mode. If one of the
2240 operands is an invariant, we may need to shorten it into the common
2242 if (iv0
->mode
== iv0
->extend_mode
2243 && iv0
->step
== const0_rtx
2244 && iv0
->mode
!= iv1
->mode
)
2245 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2247 if (iv1
->mode
== iv1
->extend_mode
2248 && iv1
->step
== const0_rtx
2249 && iv0
->mode
!= iv1
->mode
)
2250 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2252 if (iv0
->mode
!= iv1
->mode
)
2255 desc
->mode
= iv0
->mode
;
2256 desc
->signed_p
= signed_p
;
2261 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2262 result. This function is called from iv_number_of_iterations with
2263 a number of fields in DESC already filled in. OLD_NITER is the original
2264 expression for the number of iterations, before we tried to simplify it. */
2267 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2269 rtx niter
= desc
->niter_expr
;
2270 rtx mmin
, mmax
, cmp
;
2272 uint64_t andmax
= 0;
2274 /* We used to look for constant operand 0 of AND,
2275 but canonicalization should always make this impossible. */
2276 gcc_checking_assert (GET_CODE (niter
) != AND
2277 || !CONST_INT_P (XEXP (niter
, 0)));
2279 if (GET_CODE (niter
) == AND
2280 && CONST_INT_P (XEXP (niter
, 1)))
2282 andmax
= UINTVAL (XEXP (niter
, 1));
2283 niter
= XEXP (niter
, 0);
2286 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2287 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2289 if (GET_CODE (niter
) == UDIV
)
2291 if (!CONST_INT_P (XEXP (niter
, 1)))
2293 inc
= INTVAL (XEXP (niter
, 1));
2294 niter
= XEXP (niter
, 0);
2299 /* We could use a binary search here, but for now improving the upper
2300 bound by just one eliminates one important corner case. */
2301 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2302 desc
->mode
, old_niter
, mmax
);
2303 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2304 if (cmp
== const_true_rtx
)
2309 fprintf (dump_file
, ";; improved upper bound by one.\n");
2313 nmax
= MIN (nmax
, andmax
);
2315 fprintf (dump_file
, ";; Determined upper bound %"PRId64
".\n",
2320 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2321 the result into DESC. Very similar to determine_number_of_iterations
2322 (basically its rtl version), complicated by things like subregs. */
2325 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2326 struct niter_desc
*desc
)
2328 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2329 struct rtx_iv iv0
, iv1
, tmp_iv
;
2330 rtx assumption
, may_not_xform
;
2332 enum machine_mode mode
, comp_mode
;
2333 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2334 uint64_t s
, size
, d
, inv
, max
;
2335 int64_t up
, down
, inc
, step_val
;
2336 int was_sharp
= false;
2340 /* The meaning of these assumptions is this:
2342 then the rest of information does not have to be valid
2343 if noloop_assumptions then the loop does not roll
2344 if infinite then this exit is never used */
2346 desc
->assumptions
= NULL_RTX
;
2347 desc
->noloop_assumptions
= NULL_RTX
;
2348 desc
->infinite
= NULL_RTX
;
2349 desc
->simple_p
= true;
2351 desc
->const_iter
= false;
2352 desc
->niter_expr
= NULL_RTX
;
2354 cond
= GET_CODE (condition
);
2355 gcc_assert (COMPARISON_P (condition
));
2357 mode
= GET_MODE (XEXP (condition
, 0));
2358 if (mode
== VOIDmode
)
2359 mode
= GET_MODE (XEXP (condition
, 1));
2360 /* The constant comparisons should be folded. */
2361 gcc_assert (mode
!= VOIDmode
);
2363 /* We only handle integers or pointers. */
2364 if (GET_MODE_CLASS (mode
) != MODE_INT
2365 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2368 op0
= XEXP (condition
, 0);
2369 if (!iv_analyze (insn
, op0
, &iv0
))
2371 if (iv0
.extend_mode
== VOIDmode
)
2372 iv0
.mode
= iv0
.extend_mode
= mode
;
2374 op1
= XEXP (condition
, 1);
2375 if (!iv_analyze (insn
, op1
, &iv1
))
2377 if (iv1
.extend_mode
== VOIDmode
)
2378 iv1
.mode
= iv1
.extend_mode
= mode
;
2380 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2381 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2384 /* Check condition and normalize it. */
2392 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2393 cond
= swap_condition (cond
);
2405 /* Handle extends. This is relatively nontrivial, so we only try in some
2406 easy cases, when we can canonicalize the ivs (possibly by adding some
2407 assumptions) to shape subreg (base + i * step). This function also fills
2408 in desc->mode and desc->signed_p. */
2410 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2413 comp_mode
= iv0
.extend_mode
;
2415 size
= GET_MODE_BITSIZE (mode
);
2416 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2417 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2418 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2420 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2423 /* We can take care of the case of two induction variables chasing each other
2424 if the test is NE. I have never seen a loop using it, but still it is
2426 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2431 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2432 iv1
.step
= const0_rtx
;
2435 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2436 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2438 /* This is either infinite loop or the one that ends immediately, depending
2439 on initial values. Unswitching should remove this kind of conditions. */
2440 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2445 if (iv0
.step
== const0_rtx
)
2446 step_val
= -INTVAL (iv1
.step
);
2448 step_val
= INTVAL (iv0
.step
);
2450 /* Ignore loops of while (i-- < 10) type. */
2454 step_is_pow2
= !(step_val
& (step_val
- 1));
2458 /* We do not care about whether the step is power of two in this
2460 step_is_pow2
= false;
2464 /* Some more condition normalization. We must record some assumptions
2465 due to overflows. */
2470 /* We want to take care only of non-sharp relationals; this is easy,
2471 as in cases the overflow would make the transformation unsafe
2472 the loop does not roll. Seemingly it would make more sense to want
2473 to take care of sharp relationals instead, as NE is more similar to
2474 them, but the problem is that here the transformation would be more
2475 difficult due to possibly infinite loops. */
2476 if (iv0
.step
== const0_rtx
)
2478 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2479 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2481 if (assumption
== const_true_rtx
)
2482 goto zero_iter_simplify
;
2483 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2484 iv0
.base
, const1_rtx
);
2488 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2489 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2491 if (assumption
== const_true_rtx
)
2492 goto zero_iter_simplify
;
2493 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2494 iv1
.base
, constm1_rtx
);
2497 if (assumption
!= const0_rtx
)
2498 desc
->noloop_assumptions
=
2499 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2500 cond
= (cond
== LT
) ? LE
: LEU
;
2502 /* It will be useful to be able to tell the difference once more in
2503 LE -> NE reduction. */
2509 /* Take care of trivially infinite loops. */
2512 if (iv0
.step
== const0_rtx
)
2514 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2515 if (rtx_equal_p (tmp
, mode_mmin
))
2518 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2519 /* Fill in the remaining fields somehow. */
2520 goto zero_iter_simplify
;
2525 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2526 if (rtx_equal_p (tmp
, mode_mmax
))
2529 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2530 /* Fill in the remaining fields somehow. */
2531 goto zero_iter_simplify
;
2536 /* If we can we want to take care of NE conditions instead of size
2537 comparisons, as they are much more friendly (most importantly
2538 this takes care of special handling of loops with step 1). We can
2539 do it if we first check that upper bound is greater or equal to
2540 lower bound, their difference is constant c modulo step and that
2541 there is not an overflow. */
2544 if (iv0
.step
== const0_rtx
)
2545 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2548 step
= lowpart_subreg (mode
, step
, comp_mode
);
2549 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2550 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2551 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2552 may_xform
= const0_rtx
;
2553 may_not_xform
= const_true_rtx
;
2555 if (CONST_INT_P (delta
))
2557 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2559 /* A special case. We have transformed condition of type
2560 for (i = 0; i < 4; i += 4)
2562 for (i = 0; i <= 3; i += 4)
2563 obviously if the test for overflow during that transformation
2564 passed, we cannot overflow here. Most importantly any
2565 loop with sharp end condition and step 1 falls into this
2566 category, so handling this case specially is definitely
2567 worth the troubles. */
2568 may_xform
= const_true_rtx
;
2570 else if (iv0
.step
== const0_rtx
)
2572 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2573 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2574 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2575 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2576 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2578 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2584 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2585 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2586 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2587 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2588 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2590 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2596 if (may_xform
!= const0_rtx
)
2598 /* We perform the transformation always provided that it is not
2599 completely senseless. This is OK, as we would need this assumption
2600 to determine the number of iterations anyway. */
2601 if (may_xform
!= const_true_rtx
)
2603 /* If the step is a power of two and the final value we have
2604 computed overflows, the cycle is infinite. Otherwise it
2605 is nontrivial to compute the number of iterations. */
2607 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2610 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2614 /* We are going to lose some information about upper bound on
2615 number of iterations in this step, so record the information
2617 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2618 if (CONST_INT_P (iv1
.base
))
2619 up
= INTVAL (iv1
.base
);
2621 up
= INTVAL (mode_mmax
) - inc
;
2622 down
= INTVAL (CONST_INT_P (iv0
.base
)
2625 max
= (up
- down
) / inc
+ 1;
2627 && !desc
->assumptions
)
2628 record_niter_bound (loop
, max
, false, true);
2630 if (iv0
.step
== const0_rtx
)
2632 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2633 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2637 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2638 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2641 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2642 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2643 assumption
= simplify_gen_relational (reverse_condition (cond
),
2644 SImode
, mode
, tmp0
, tmp1
);
2645 if (assumption
== const_true_rtx
)
2646 goto zero_iter_simplify
;
2647 else if (assumption
!= const0_rtx
)
2648 desc
->noloop_assumptions
=
2649 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2654 /* Count the number of iterations. */
2657 /* Everything we do here is just arithmetics modulo size of mode. This
2658 makes us able to do more involved computations of number of iterations
2659 than in other cases. First transform the condition into shape
2660 s * i <> c, with s positive. */
2661 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2662 iv0
.base
= const0_rtx
;
2663 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2664 iv1
.step
= const0_rtx
;
2665 if (INTVAL (iv0
.step
) < 0)
2667 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2668 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2670 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2672 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2673 is infinite. Otherwise, the number of iterations is
2674 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2675 s
= INTVAL (iv0
.step
); d
= 1;
2682 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2684 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2685 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2686 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2687 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2689 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2690 inv
= inverse (s
, size
);
2691 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2692 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2696 if (iv1
.step
== const0_rtx
)
2697 /* Condition in shape a + s * i <= b
2698 We must know that b + s does not overflow and a <= b + s and then we
2699 can compute number of iterations as (b + s - a) / s. (It might
2700 seem that we in fact could be more clever about testing the b + s
2701 overflow condition using some information about b - a mod s,
2702 but it was already taken into account during LE -> NE transform). */
2705 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2706 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2708 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2709 lowpart_subreg (mode
, step
,
2715 /* If s is power of 2, we know that the loop is infinite if
2716 a % s <= b % s and b + s overflows. */
2717 assumption
= simplify_gen_relational (reverse_condition (cond
),
2721 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2722 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2723 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2724 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2726 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2730 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2733 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2736 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2737 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2738 assumption
= simplify_gen_relational (reverse_condition (cond
),
2739 SImode
, mode
, tmp0
, tmp
);
2741 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2742 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2746 /* Condition in shape a <= b - s * i
2747 We must know that a - s does not overflow and a - s <= b and then
2748 we can again compute number of iterations as (b - (a - s)) / s. */
2749 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2750 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2751 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2753 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2754 lowpart_subreg (mode
, step
, comp_mode
));
2759 /* If s is power of 2, we know that the loop is infinite if
2760 a % s <= b % s and a - s overflows. */
2761 assumption
= simplify_gen_relational (reverse_condition (cond
),
2765 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2766 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2767 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2768 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2770 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2774 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2777 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2780 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2781 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2782 assumption
= simplify_gen_relational (reverse_condition (cond
),
2785 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2786 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2788 if (assumption
== const_true_rtx
)
2789 goto zero_iter_simplify
;
2790 else if (assumption
!= const0_rtx
)
2791 desc
->noloop_assumptions
=
2792 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2793 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2794 desc
->niter_expr
= delta
;
2797 old_niter
= desc
->niter_expr
;
2799 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2800 if (desc
->assumptions
2801 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2803 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2804 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2805 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2807 /* Rerun the simplification. Consider code (created by copying loop headers)
2819 The first pass determines that i = 0, the second pass uses it to eliminate
2820 noloop assumption. */
2822 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2823 if (desc
->assumptions
2824 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2826 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2827 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2828 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2830 if (desc
->noloop_assumptions
2831 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2834 if (CONST_INT_P (desc
->niter_expr
))
2836 uint64_t val
= INTVAL (desc
->niter_expr
);
2838 desc
->const_iter
= true;
2839 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2841 && !desc
->assumptions
)
2842 record_niter_bound (loop
, desc
->niter
, false, true);
2846 max
= determine_max_iter (loop
, desc
, old_niter
);
2848 goto zero_iter_simplify
;
2850 && !desc
->assumptions
)
2851 record_niter_bound (loop
, max
, false, true);
2853 /* simplify_using_initial_values does a copy propagation on the registers
2854 in the expression for the number of iterations. This prolongs life
2855 ranges of registers and increases register pressure, and usually
2856 brings no gain (and if it happens to do, the cse pass will take care
2857 of it anyway). So prevent this behavior, unless it enabled us to
2858 derive that the number of iterations is a constant. */
2859 desc
->niter_expr
= old_niter
;
2865 /* Simplify the assumptions. */
2866 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2867 if (desc
->assumptions
2868 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2870 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2874 desc
->const_iter
= true;
2876 record_niter_bound (loop
, 0, true, true);
2877 desc
->noloop_assumptions
= NULL_RTX
;
2878 desc
->niter_expr
= const0_rtx
;
2882 desc
->simple_p
= false;
2886 /* Checks whether E is a simple exit from LOOP and stores its description
2890 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2892 basic_block exit_bb
;
2897 desc
->simple_p
= false;
2899 /* It must belong directly to the loop. */
2900 if (exit_bb
->loop_father
!= loop
)
2903 /* It must be tested (at least) once during any iteration. */
2904 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2907 /* It must end in a simple conditional jump. */
2908 if (!any_condjump_p (BB_END (exit_bb
)))
2911 ein
= EDGE_SUCC (exit_bb
, 0);
2913 ein
= EDGE_SUCC (exit_bb
, 1);
2916 desc
->in_edge
= ein
;
2918 /* Test whether the condition is suitable. */
2919 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2922 if (ein
->flags
& EDGE_FALLTHRU
)
2924 condition
= reversed_condition (condition
);
2929 /* Check that we are able to determine number of iterations and fill
2930 in information about it. */
2931 iv_number_of_iterations (loop
, at
, condition
, desc
);
2934 /* Finds a simple exit of LOOP and stores its description into DESC. */
2937 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2942 struct niter_desc act
;
2946 desc
->simple_p
= false;
2947 body
= get_loop_body (loop
);
2949 for (i
= 0; i
< loop
->num_nodes
; i
++)
2951 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2953 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2956 check_simple_exit (loop
, e
, &act
);
2964 /* Prefer constant iterations; the less the better. */
2966 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2969 /* Also if the actual exit may be infinite, while the old one
2970 not, prefer the old one. */
2971 if (act
.infinite
&& !desc
->infinite
)
2983 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2984 fprintf (dump_file
, " simple exit %d -> %d\n",
2985 desc
->out_edge
->src
->index
,
2986 desc
->out_edge
->dest
->index
);
2987 if (desc
->assumptions
)
2989 fprintf (dump_file
, " assumptions: ");
2990 print_rtl (dump_file
, desc
->assumptions
);
2991 fprintf (dump_file
, "\n");
2993 if (desc
->noloop_assumptions
)
2995 fprintf (dump_file
, " does not roll if: ");
2996 print_rtl (dump_file
, desc
->noloop_assumptions
);
2997 fprintf (dump_file
, "\n");
3001 fprintf (dump_file
, " infinite if: ");
3002 print_rtl (dump_file
, desc
->infinite
);
3003 fprintf (dump_file
, "\n");
3006 fprintf (dump_file
, " number of iterations: ");
3007 print_rtl (dump_file
, desc
->niter_expr
);
3008 fprintf (dump_file
, "\n");
3010 fprintf (dump_file
, " upper bound: %li\n",
3011 (long)get_max_loop_iterations_int (loop
));
3012 fprintf (dump_file
, " realistic bound: %li\n",
3013 (long)get_estimated_loop_iterations_int (loop
));
3016 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3022 /* Creates a simple loop description of LOOP if it was not computed
3026 get_simple_loop_desc (struct loop
*loop
)
3028 struct niter_desc
*desc
= simple_loop_desc (loop
);
3033 /* At least desc->infinite is not always initialized by
3034 find_simple_loop_exit. */
3035 desc
= ggc_cleared_alloc
<niter_desc
> ();
3036 iv_analysis_loop_init (loop
);
3037 find_simple_exit (loop
, desc
);
3038 loop
->simple_loop_desc
= desc
;
3040 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3042 const char *wording
;
3044 /* Assume that no overflow happens and that the loop is finite.
3045 We already warned at the tree level if we ran optimizations there. */
3046 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3051 flag_unsafe_loop_optimizations
3052 ? N_("assuming that the loop is not infinite")
3053 : N_("cannot optimize possibly infinite loops");
3054 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3057 if (desc
->assumptions
)
3060 flag_unsafe_loop_optimizations
3061 ? N_("assuming that the loop counter does not overflow")
3062 : N_("cannot optimize loop, the loop counter may overflow");
3063 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3068 if (flag_unsafe_loop_optimizations
)
3070 desc
->assumptions
= NULL_RTX
;
3071 desc
->infinite
= NULL_RTX
;
3078 /* Releases simple loop description for LOOP. */
3081 free_simple_loop_desc (struct loop
*loop
)
3083 struct niter_desc
*desc
= simple_loop_desc (loop
);
3089 loop
->simple_loop_desc
= NULL
;