1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2019 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, mode, reg, iv): Stores the description of the induction
39 variable corresponding to the use of register REG in INSN to IV, given
40 that REG has mode MODE. Returns true if REG is an induction variable
41 in INSN. false otherwise. If a use of REG is not found in INSN,
42 the following insns are scanned (so that we may call this function
43 on insns returned by get_condition).
44 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
45 corresponding to DEF, which is a register defined in INSN.
46 iv_analyze_expr (insn, mode, expr, iv): Stores to IV the description of iv
47 corresponding to expression EXPR evaluated at INSN. All registers used bu
48 EXPR must also be used in INSN. MODE is the mode of EXPR.
53 #include "coretypes.h"
59 #include "diagnostic-core.h"
64 #include "tree-ssa-loop-niter.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. */
91 unsigned regno
; /* The register of the biv. */
92 class rtx_iv iv
; /* Value of the biv. */
95 static bool clean_slate
= true;
97 static unsigned int iv_ref_table_size
= 0;
99 /* Table of rtx_ivs indexed by the df_ref uid field. */
100 static class rtx_iv
** iv_ref_table
;
102 /* Induction variable stored at the reference. */
103 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
104 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
106 /* The current loop. */
108 static class loop
*current_loop
;
110 /* Hashtable helper. */
112 struct biv_entry_hasher
: free_ptr_hash
<biv_entry
>
114 typedef rtx_def
*compare_type
;
115 static inline hashval_t
hash (const biv_entry
*);
116 static inline bool equal (const biv_entry
*, const rtx_def
*);
119 /* Returns hash value for biv B. */
122 biv_entry_hasher::hash (const biv_entry
*b
)
127 /* Compares biv B and register R. */
130 biv_entry_hasher::equal (const biv_entry
*b
, const rtx_def
*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
*, scalar_int_mode
, rtx
, class 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 *, class rtx_iv
*);
161 dump_iv_info (FILE *file
, class 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)");
202 check_iv_ref_table_size (void)
204 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
206 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
207 iv_ref_table
= XRESIZEVEC (class rtx_iv
*, iv_ref_table
, new_size
);
208 memset (&iv_ref_table
[iv_ref_table_size
], 0,
209 (new_size
- iv_ref_table_size
) * sizeof (class rtx_iv
*));
210 iv_ref_table_size
= new_size
;
215 /* Checks whether REG is a well-behaved register. */
218 simple_reg_p (rtx reg
)
222 if (GET_CODE (reg
) == SUBREG
)
224 if (!subreg_lowpart_p (reg
))
226 reg
= SUBREG_REG (reg
);
233 if (HARD_REGISTER_NUM_P (r
))
236 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
242 /* Clears the information about ivs stored in df. */
247 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
250 check_iv_ref_table_size ();
251 for (i
= 0; i
< n_defs
; i
++)
253 iv
= iv_ref_table
[i
];
257 iv_ref_table
[i
] = NULL
;
265 /* Prepare the data for an induction variable analysis of a LOOP. */
268 iv_analysis_loop_init (class loop
*loop
)
272 /* Clear the information from the analysis of the previous loop. */
275 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
276 bivs
= new hash_table
<biv_entry_hasher
> (10);
282 /* Get rid of the ud chains before processing the rescans. Then add
284 df_remove_problem (df_chain
);
285 df_process_deferred_rescans ();
286 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
287 df_chain_add_problem (DF_UD_CHAIN
);
288 df_note_add_problem ();
289 df_analyze_loop (loop
);
291 df_dump_region (dump_file
);
293 check_iv_ref_table_size ();
296 /* Finds the definition of REG that dominates loop latch and stores
297 it to DEF. Returns false if there is not a single definition
298 dominating the latch. If REG has no definition in loop, DEF
299 is set to NULL and true is returned. */
302 latch_dominating_def (rtx reg
, df_ref
*def
)
304 df_ref single_rd
= NULL
, adef
;
305 unsigned regno
= REGNO (reg
);
306 class df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
308 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
310 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
311 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
314 /* More than one reaching definition. */
318 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
328 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
330 static enum iv_grd_result
331 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
334 basic_block def_bb
, use_bb
;
339 if (!simple_reg_p (reg
))
341 if (GET_CODE (reg
) == SUBREG
)
342 reg
= SUBREG_REG (reg
);
343 gcc_assert (REG_P (reg
));
345 use
= df_find_use (insn
, reg
);
346 gcc_assert (use
!= NULL
);
348 if (!DF_REF_CHAIN (use
))
349 return GRD_INVARIANT
;
351 /* More than one reaching def. */
352 if (DF_REF_CHAIN (use
)->next
)
355 adef
= DF_REF_CHAIN (use
)->ref
;
357 /* We do not handle setting only part of the register. */
358 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
361 def_insn
= DF_REF_INSN (adef
);
362 def_bb
= DF_REF_BB (adef
);
363 use_bb
= BLOCK_FOR_INSN (insn
);
365 if (use_bb
== def_bb
)
366 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
368 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
373 return GRD_SINGLE_DOM
;
376 /* The definition does not dominate the use. This is still OK if
377 this may be a use of a biv, i.e. if the def_bb dominates loop
379 if (just_once_each_iteration_p (current_loop
, def_bb
))
380 return GRD_MAYBE_BIV
;
385 /* Sets IV to invariant CST in MODE. Always returns true (just for
386 consistency with other iv manipulation functions that may fail). */
389 iv_constant (class rtx_iv
*iv
, scalar_int_mode mode
, rtx cst
)
393 iv
->step
= const0_rtx
;
394 iv
->first_special
= false;
395 iv
->extend
= IV_UNKNOWN_EXTEND
;
396 iv
->extend_mode
= iv
->mode
;
397 iv
->delta
= const0_rtx
;
398 iv
->mult
= const1_rtx
;
403 /* Evaluates application of subreg to MODE on IV. */
406 iv_subreg (class rtx_iv
*iv
, scalar_int_mode mode
)
408 /* If iv is invariant, just calculate the new value. */
409 if (iv
->step
== const0_rtx
410 && !iv
->first_special
)
412 rtx val
= get_iv_value (iv
, const0_rtx
);
413 val
= lowpart_subreg (mode
, val
,
414 iv
->extend
== IV_UNKNOWN_EXTEND
415 ? iv
->mode
: iv
->extend_mode
);
418 iv
->extend
= IV_UNKNOWN_EXTEND
;
419 iv
->mode
= iv
->extend_mode
= mode
;
420 iv
->delta
= const0_rtx
;
421 iv
->mult
= const1_rtx
;
425 if (iv
->extend_mode
== mode
)
428 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
431 iv
->extend
= IV_UNKNOWN_EXTEND
;
434 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
435 simplify_gen_binary (MULT
, iv
->extend_mode
,
436 iv
->base
, iv
->mult
));
437 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
438 iv
->mult
= const1_rtx
;
439 iv
->delta
= const0_rtx
;
440 iv
->first_special
= false;
445 /* Evaluates application of EXTEND to MODE on IV. */
448 iv_extend (class rtx_iv
*iv
, enum iv_extend_code extend
, scalar_int_mode mode
)
450 /* If iv is invariant, just calculate the new value. */
451 if (iv
->step
== const0_rtx
452 && !iv
->first_special
)
454 rtx val
= get_iv_value (iv
, const0_rtx
);
455 if (iv
->extend_mode
!= iv
->mode
456 && iv
->extend
!= IV_UNKNOWN_EXTEND
457 && iv
->extend
!= extend
)
458 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
459 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
462 ? iv
->extend_mode
: iv
->mode
);
464 iv
->extend
= IV_UNKNOWN_EXTEND
;
465 iv
->mode
= iv
->extend_mode
= mode
;
466 iv
->delta
= const0_rtx
;
467 iv
->mult
= const1_rtx
;
471 if (mode
!= iv
->extend_mode
)
474 if (iv
->extend
!= IV_UNKNOWN_EXTEND
475 && iv
->extend
!= extend
)
483 /* Evaluates negation of IV. */
486 iv_neg (class rtx_iv
*iv
)
488 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
490 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
491 iv
->base
, iv
->extend_mode
);
492 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
493 iv
->step
, iv
->extend_mode
);
497 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
498 iv
->delta
, iv
->extend_mode
);
499 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
500 iv
->mult
, iv
->extend_mode
);
506 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
509 iv_add (class rtx_iv
*iv0
, class rtx_iv
*iv1
, enum rtx_code op
)
511 scalar_int_mode mode
;
514 /* Extend the constant to extend_mode of the other operand if necessary. */
515 if (iv0
->extend
== IV_UNKNOWN_EXTEND
516 && iv0
->mode
== iv0
->extend_mode
517 && iv0
->step
== const0_rtx
518 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
520 iv0
->extend_mode
= iv1
->extend_mode
;
521 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
522 iv0
->base
, iv0
->mode
);
524 if (iv1
->extend
== IV_UNKNOWN_EXTEND
525 && iv1
->mode
== iv1
->extend_mode
526 && iv1
->step
== const0_rtx
527 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
529 iv1
->extend_mode
= iv0
->extend_mode
;
530 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
531 iv1
->base
, iv1
->mode
);
534 mode
= iv0
->extend_mode
;
535 if (mode
!= iv1
->extend_mode
)
538 if (iv0
->extend
== IV_UNKNOWN_EXTEND
539 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
541 if (iv0
->mode
!= iv1
->mode
)
544 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
545 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
550 /* Handle addition of constant. */
551 if (iv1
->extend
== IV_UNKNOWN_EXTEND
553 && iv1
->step
== const0_rtx
)
555 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
559 if (iv0
->extend
== IV_UNKNOWN_EXTEND
561 && iv0
->step
== const0_rtx
)
569 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
576 /* Evaluates multiplication of IV by constant CST. */
579 iv_mult (class rtx_iv
*iv
, rtx mby
)
581 scalar_int_mode mode
= iv
->extend_mode
;
583 if (GET_MODE (mby
) != VOIDmode
584 && GET_MODE (mby
) != mode
)
587 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
589 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
590 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
594 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
595 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
601 /* Evaluates shift of IV by constant CST. */
604 iv_shift (class rtx_iv
*iv
, rtx mby
)
606 scalar_int_mode mode
= iv
->extend_mode
;
608 if (GET_MODE (mby
) != VOIDmode
609 && GET_MODE (mby
) != mode
)
612 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
614 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
615 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
619 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
620 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
626 /* The recursive part of get_biv_step. Gets the value of the single value
627 defined by DEF wrto initial value of REG inside loop, in shape described
631 get_biv_step_1 (df_ref def
, scalar_int_mode outer_mode
, rtx reg
,
632 rtx
*inner_step
, scalar_int_mode
*inner_mode
,
633 enum iv_extend_code
*extend
,
636 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
639 rtx_insn
*insn
= DF_REF_INSN (def
);
641 enum iv_grd_result res
;
643 set
= single_set (insn
);
647 rhs
= find_reg_equal_equiv_note (insn
);
653 code
= GET_CODE (rhs
);
666 if (code
== PLUS
&& CONSTANT_P (op0
))
667 std::swap (op0
, op1
);
669 if (!simple_reg_p (op0
)
670 || !CONSTANT_P (op1
))
673 if (GET_MODE (rhs
) != outer_mode
)
675 /* ppc64 uses expressions like
677 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
679 this is equivalent to
681 (set x':DI (plus:DI y:DI 1))
682 (set x:SI (subreg:SI (x':DI)). */
683 if (GET_CODE (op0
) != SUBREG
)
685 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
694 if (GET_MODE (rhs
) != outer_mode
)
698 if (!simple_reg_p (op0
))
708 if (GET_CODE (next
) == SUBREG
)
710 if (!subreg_lowpart_p (next
))
713 nextr
= SUBREG_REG (next
);
714 if (GET_MODE (nextr
) != outer_mode
)
720 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
722 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
725 if (res
== GRD_MAYBE_BIV
)
727 if (!rtx_equal_p (nextr
, reg
))
730 *inner_step
= const0_rtx
;
731 *extend
= IV_UNKNOWN_EXTEND
;
732 *inner_mode
= outer_mode
;
733 *outer_step
= const0_rtx
;
735 else if (!get_biv_step_1 (next_def
, outer_mode
, reg
,
736 inner_step
, inner_mode
, extend
,
740 if (GET_CODE (next
) == SUBREG
)
742 scalar_int_mode amode
;
743 if (!is_a
<scalar_int_mode
> (GET_MODE (next
), &amode
)
744 || GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
748 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
749 *inner_step
, *outer_step
);
750 *outer_step
= const0_rtx
;
751 *extend
= IV_UNKNOWN_EXTEND
;
762 if (*inner_mode
== outer_mode
763 /* See comment in previous switch. */
764 || GET_MODE (rhs
) != outer_mode
)
765 *inner_step
= simplify_gen_binary (code
, outer_mode
,
768 *outer_step
= simplify_gen_binary (code
, outer_mode
,
774 gcc_assert (GET_MODE (op0
) == *inner_mode
775 && *extend
== IV_UNKNOWN_EXTEND
776 && *outer_step
== const0_rtx
);
778 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
788 /* Gets the operation on register REG inside loop, in shape
790 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
792 If the operation cannot be described in this shape, return false.
793 LAST_DEF is the definition of REG that dominates loop latch. */
796 get_biv_step (df_ref last_def
, scalar_int_mode outer_mode
, rtx reg
,
797 rtx
*inner_step
, scalar_int_mode
*inner_mode
,
798 enum iv_extend_code
*extend
, rtx
*outer_step
)
800 if (!get_biv_step_1 (last_def
, outer_mode
, reg
,
801 inner_step
, inner_mode
, extend
,
805 gcc_assert ((*inner_mode
== outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
806 gcc_assert (*inner_mode
!= outer_mode
|| *outer_step
== const0_rtx
);
811 /* Records information that DEF is induction variable IV. */
814 record_iv (df_ref def
, class rtx_iv
*iv
)
816 class rtx_iv
*recorded_iv
= XNEW (class rtx_iv
);
819 check_iv_ref_table_size ();
820 DF_REF_IV_SET (def
, recorded_iv
);
823 /* If DEF was already analyzed for bivness, store the description of the biv to
824 IV and return true. Otherwise return false. */
827 analyzed_for_bivness_p (rtx def
, class rtx_iv
*iv
)
829 class biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
839 record_biv (rtx def
, class rtx_iv
*iv
)
841 class biv_entry
*biv
= XNEW (class biv_entry
);
842 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
844 biv
->regno
= REGNO (def
);
850 /* Determines whether DEF is a biv and if so, stores its description
851 to *IV. OUTER_MODE is the mode of DEF. */
854 iv_analyze_biv (scalar_int_mode outer_mode
, rtx def
, class rtx_iv
*iv
)
856 rtx inner_step
, outer_step
;
857 scalar_int_mode inner_mode
;
858 enum iv_extend_code extend
;
863 fprintf (dump_file
, "Analyzing ");
864 print_rtl (dump_file
, def
);
865 fprintf (dump_file
, " for bivness.\n");
870 if (!CONSTANT_P (def
))
873 return iv_constant (iv
, outer_mode
, def
);
876 if (!latch_dominating_def (def
, &last_def
))
879 fprintf (dump_file
, " not simple.\n");
884 return iv_constant (iv
, outer_mode
, def
);
886 if (analyzed_for_bivness_p (def
, iv
))
889 fprintf (dump_file
, " already analysed.\n");
890 return iv
->base
!= NULL_RTX
;
893 if (!get_biv_step (last_def
, outer_mode
, def
, &inner_step
, &inner_mode
,
894 &extend
, &outer_step
))
900 /* Loop transforms base to es (base + inner_step) + outer_step,
901 where es means extend of subreg between inner_mode and outer_mode.
902 The corresponding induction variable is
904 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
906 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
907 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
908 iv
->mode
= inner_mode
;
909 iv
->extend_mode
= outer_mode
;
911 iv
->mult
= const1_rtx
;
912 iv
->delta
= outer_step
;
913 iv
->first_special
= inner_mode
!= outer_mode
;
918 fprintf (dump_file
, " ");
919 dump_iv_info (dump_file
, iv
);
920 fprintf (dump_file
, "\n");
923 record_biv (def
, iv
);
924 return iv
->base
!= NULL_RTX
;
927 /* Analyzes expression RHS used at INSN and stores the result to *IV.
928 The mode of the induction variable is MODE. */
931 iv_analyze_expr (rtx_insn
*insn
, scalar_int_mode mode
, rtx rhs
,
935 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
936 class rtx_iv iv0
, iv1
;
937 enum rtx_code code
= GET_CODE (rhs
);
938 scalar_int_mode omode
= mode
;
943 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
948 return iv_analyze_op (insn
, mode
, rhs
, iv
);
960 /* We don't know how many bits there are in a sign-extended constant. */
961 if (!is_a
<scalar_int_mode
> (GET_MODE (op0
), &omode
))
974 if (!CONSTANT_P (mby
))
975 std::swap (op0
, mby
);
976 if (!CONSTANT_P (mby
))
983 if (!CONSTANT_P (mby
))
992 && !iv_analyze_expr (insn
, omode
, op0
, &iv0
))
996 && !iv_analyze_expr (insn
, omode
, op1
, &iv1
))
1002 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1007 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1018 if (!iv_add (&iv0
, &iv1
, code
))
1023 if (!iv_mult (&iv0
, mby
))
1028 if (!iv_shift (&iv0
, mby
))
1037 return iv
->base
!= NULL_RTX
;
1040 /* Analyzes iv DEF and stores the result to *IV. */
1043 iv_analyze_def (df_ref def
, class rtx_iv
*iv
)
1045 rtx_insn
*insn
= DF_REF_INSN (def
);
1046 rtx reg
= DF_REF_REG (def
);
1051 fprintf (dump_file
, "Analyzing def of ");
1052 print_rtl (dump_file
, reg
);
1053 fprintf (dump_file
, " in insn ");
1054 print_rtl_single (dump_file
, insn
);
1057 check_iv_ref_table_size ();
1058 if (DF_REF_IV (def
))
1061 fprintf (dump_file
, " already analysed.\n");
1062 *iv
= *DF_REF_IV (def
);
1063 return iv
->base
!= NULL_RTX
;
1066 iv
->base
= NULL_RTX
;
1067 iv
->step
= NULL_RTX
;
1069 scalar_int_mode mode
;
1070 if (!REG_P (reg
) || !is_a
<scalar_int_mode
> (GET_MODE (reg
), &mode
))
1073 set
= single_set (insn
);
1077 if (!REG_P (SET_DEST (set
)))
1080 gcc_assert (SET_DEST (set
) == reg
);
1081 rhs
= find_reg_equal_equiv_note (insn
);
1083 rhs
= XEXP (rhs
, 0);
1085 rhs
= SET_SRC (set
);
1087 iv_analyze_expr (insn
, mode
, rhs
, iv
);
1088 record_iv (def
, iv
);
1092 print_rtl (dump_file
, reg
);
1093 fprintf (dump_file
, " in insn ");
1094 print_rtl_single (dump_file
, insn
);
1095 fprintf (dump_file
, " is ");
1096 dump_iv_info (dump_file
, iv
);
1097 fprintf (dump_file
, "\n");
1100 return iv
->base
!= NULL_RTX
;
1103 /* Analyzes operand OP of INSN and stores the result to *IV. MODE is the
1107 iv_analyze_op (rtx_insn
*insn
, scalar_int_mode mode
, rtx op
, class rtx_iv
*iv
)
1110 enum iv_grd_result res
;
1114 fprintf (dump_file
, "Analyzing operand ");
1115 print_rtl (dump_file
, op
);
1116 fprintf (dump_file
, " of insn ");
1117 print_rtl_single (dump_file
, insn
);
1120 if (function_invariant_p (op
))
1121 res
= GRD_INVARIANT
;
1122 else if (GET_CODE (op
) == SUBREG
)
1124 scalar_int_mode inner_mode
;
1125 if (!subreg_lowpart_p (op
)
1126 || !is_a
<scalar_int_mode
> (GET_MODE (SUBREG_REG (op
)), &inner_mode
))
1129 if (!iv_analyze_op (insn
, inner_mode
, SUBREG_REG (op
), iv
))
1132 return iv_subreg (iv
, mode
);
1136 res
= iv_get_reaching_def (insn
, op
, &def
);
1137 if (res
== GRD_INVALID
)
1140 fprintf (dump_file
, " not simple.\n");
1145 if (res
== GRD_INVARIANT
)
1147 iv_constant (iv
, mode
, op
);
1151 fprintf (dump_file
, " ");
1152 dump_iv_info (dump_file
, iv
);
1153 fprintf (dump_file
, "\n");
1158 if (res
== GRD_MAYBE_BIV
)
1159 return iv_analyze_biv (mode
, op
, iv
);
1161 return iv_analyze_def (def
, iv
);
1164 /* Analyzes value VAL at INSN and stores the result to *IV. MODE is the
1168 iv_analyze (rtx_insn
*insn
, scalar_int_mode mode
, rtx val
, class rtx_iv
*iv
)
1172 /* We must find the insn in that val is used, so that we get to UD chains.
1173 Since the function is sometimes called on result of get_condition,
1174 this does not necessarily have to be directly INSN; scan also the
1176 if (simple_reg_p (val
))
1178 if (GET_CODE (val
) == SUBREG
)
1179 reg
= SUBREG_REG (val
);
1183 while (!df_find_use (insn
, reg
))
1184 insn
= NEXT_INSN (insn
);
1187 return iv_analyze_op (insn
, mode
, val
, iv
);
1190 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1193 iv_analyze_result (rtx_insn
*insn
, rtx def
, class rtx_iv
*iv
)
1197 adef
= df_find_def (insn
, def
);
1201 return iv_analyze_def (adef
, iv
);
1204 /* Checks whether definition of register REG in INSN is a basic induction
1205 variable. MODE is the mode of REG.
1207 IV analysis must have been initialized (via a call to
1208 iv_analysis_loop_init) for this function to produce a result. */
1211 biv_p (rtx_insn
*insn
, scalar_int_mode mode
, rtx reg
)
1214 df_ref def
, last_def
;
1216 if (!simple_reg_p (reg
))
1219 def
= df_find_def (insn
, reg
);
1220 gcc_assert (def
!= NULL
);
1221 if (!latch_dominating_def (reg
, &last_def
))
1223 if (last_def
!= def
)
1226 if (!iv_analyze_biv (mode
, reg
, &iv
))
1229 return iv
.step
!= const0_rtx
;
1232 /* Calculates value of IV at ITERATION-th iteration. */
1235 get_iv_value (class rtx_iv
*iv
, rtx iteration
)
1239 /* We would need to generate some if_then_else patterns, and so far
1240 it is not needed anywhere. */
1241 gcc_assert (!iv
->first_special
);
1243 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1244 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1245 simplify_gen_binary (MULT
, iv
->extend_mode
,
1246 iv
->step
, iteration
));
1250 if (iv
->extend_mode
== iv
->mode
)
1253 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1255 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1258 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1259 iv
->extend_mode
, val
, iv
->mode
);
1260 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1261 simplify_gen_binary (MULT
, iv
->extend_mode
,
1267 /* Free the data for an induction variable analysis. */
1270 iv_analysis_done (void)
1276 df_finish_pass (true);
1279 free (iv_ref_table
);
1280 iv_ref_table
= NULL
;
1281 iv_ref_table_size
= 0;
1285 /* Computes inverse to X modulo (1 << MOD). */
1288 inverse (uint64_t x
, int mod
)
1291 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1295 for (i
= 0; i
< mod
- 1; i
++)
1297 rslt
= (rslt
* x
) & mask
;
1304 /* Checks whether any register in X is in set ALT. */
1307 altered_reg_used (const_rtx x
, bitmap alt
)
1309 subrtx_iterator::array_type array
;
1310 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
1312 const_rtx x
= *iter
;
1313 if (REG_P (x
) && REGNO_REG_SET_P (alt
, REGNO (x
)))
1319 /* Marks registers altered by EXPR in set ALT. */
1322 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1324 if (GET_CODE (expr
) == SUBREG
)
1325 expr
= SUBREG_REG (expr
);
1329 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1332 /* Checks whether RHS is simple enough to process. */
1335 simple_rhs_p (rtx rhs
)
1339 if (function_invariant_p (rhs
)
1340 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1343 switch (GET_CODE (rhs
))
1348 op0
= XEXP (rhs
, 0);
1349 op1
= XEXP (rhs
, 1);
1350 /* Allow reg OP const and reg OP reg. */
1351 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1352 && !function_invariant_p (op0
))
1354 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1355 && !function_invariant_p (op1
))
1364 op0
= XEXP (rhs
, 0);
1365 op1
= XEXP (rhs
, 1);
1366 /* Allow reg OP const. */
1367 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1369 if (!function_invariant_p (op1
))
1379 /* If REGNO has a single definition, return its known value, otherwise return
1383 find_single_def_src (unsigned int regno
)
1391 adef
= DF_REG_DEF_CHAIN (regno
);
1392 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1393 || DF_REF_IS_ARTIFICIAL (adef
))
1396 set
= single_set (DF_REF_INSN (adef
));
1397 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1398 || REGNO (SET_DEST (set
)) != regno
)
1401 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1403 if (note
&& function_invariant_p (XEXP (note
, 0)))
1405 src
= XEXP (note
, 0);
1408 src
= SET_SRC (set
);
1412 regno
= REGNO (src
);
1417 if (!function_invariant_p (src
))
1423 /* If any registers in *EXPR that have a single definition, try to replace
1424 them with the known-equivalent values. */
1427 replace_single_def_regs (rtx
*expr
)
1429 subrtx_var_iterator::array_type array
;
1431 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1435 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1437 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1443 /* A subroutine of simplify_using_initial_values, this function examines INSN
1444 to see if it contains a suitable set that we can use to make a replacement.
1445 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1446 the set; return false otherwise. */
1449 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1451 rtx set
= single_set (insn
);
1452 rtx lhs
= NULL_RTX
, rhs
;
1457 lhs
= SET_DEST (set
);
1461 rhs
= find_reg_equal_equiv_note (insn
);
1463 rhs
= XEXP (rhs
, 0);
1465 rhs
= SET_SRC (set
);
1467 if (!simple_rhs_p (rhs
))
1475 /* Using the data returned by suitable_set_for_replacement, replace DEST
1476 with SRC in *EXPR and return the new expression. Also call
1477 replace_single_def_regs if the replacement changed something. */
1479 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1482 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1485 replace_single_def_regs (expr
);
1488 /* Checks whether A implies B. */
1491 implies_p (rtx a
, rtx b
)
1493 rtx op0
, op1
, opb0
, opb1
;
1496 if (rtx_equal_p (a
, b
))
1499 if (GET_CODE (a
) == EQ
)
1505 || (GET_CODE (op0
) == SUBREG
1506 && REG_P (SUBREG_REG (op0
))))
1508 rtx r
= simplify_replace_rtx (b
, op0
, op1
);
1509 if (r
== const_true_rtx
)
1514 || (GET_CODE (op1
) == SUBREG
1515 && REG_P (SUBREG_REG (op1
))))
1517 rtx r
= simplify_replace_rtx (b
, op1
, op0
);
1518 if (r
== const_true_rtx
)
1523 if (b
== const_true_rtx
)
1526 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1527 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1528 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1529 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1537 mode
= GET_MODE (op0
);
1538 if (mode
!= GET_MODE (opb0
))
1540 else if (mode
== VOIDmode
)
1542 mode
= GET_MODE (op1
);
1543 if (mode
!= GET_MODE (opb1
))
1547 /* A < B implies A + 1 <= B. */
1548 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1549 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1552 if (GET_CODE (a
) == GT
)
1553 std::swap (op0
, op1
);
1555 if (GET_CODE (b
) == GE
)
1556 std::swap (opb0
, opb1
);
1558 if (SCALAR_INT_MODE_P (mode
)
1559 && rtx_equal_p (op1
, opb1
)
1560 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1565 /* A < B or A > B imply A != B. TODO: Likewise
1566 A + n < B implies A != B + n if neither wraps. */
1567 if (GET_CODE (b
) == NE
1568 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1569 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1571 if (rtx_equal_p (op0
, opb0
)
1572 && rtx_equal_p (op1
, opb1
))
1576 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1577 if (GET_CODE (a
) == NE
1578 && op1
== const0_rtx
)
1580 if ((GET_CODE (b
) == GTU
1581 && opb1
== const0_rtx
)
1582 || (GET_CODE (b
) == GEU
1583 && opb1
== const1_rtx
))
1584 return rtx_equal_p (op0
, opb0
);
1587 /* A != N is equivalent to A - (N + 1) <u -1. */
1588 if (GET_CODE (a
) == NE
1589 && CONST_INT_P (op1
)
1590 && GET_CODE (b
) == LTU
1591 && opb1
== constm1_rtx
1592 && GET_CODE (opb0
) == PLUS
1593 && CONST_INT_P (XEXP (opb0
, 1))
1594 /* Avoid overflows. */
1595 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1596 != ((unsigned HOST_WIDE_INT
)1
1597 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1598 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1599 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1601 /* Likewise, A != N implies A - N > 0. */
1602 if (GET_CODE (a
) == NE
1603 && CONST_INT_P (op1
))
1605 if (GET_CODE (b
) == GTU
1606 && GET_CODE (opb0
) == PLUS
1607 && opb1
== const0_rtx
1608 && CONST_INT_P (XEXP (opb0
, 1))
1609 /* Avoid overflows. */
1610 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1611 != (HOST_WIDE_INT_1U
<< (HOST_BITS_PER_WIDE_INT
- 1)))
1612 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1613 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1614 if (GET_CODE (b
) == GEU
1615 && GET_CODE (opb0
) == PLUS
1616 && opb1
== const1_rtx
1617 && CONST_INT_P (XEXP (opb0
, 1))
1618 /* Avoid overflows. */
1619 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1620 != (HOST_WIDE_INT_1U
<< (HOST_BITS_PER_WIDE_INT
- 1)))
1621 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1622 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1625 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1626 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1627 && CONST_INT_P (op1
)
1628 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1629 || INTVAL (op1
) >= 0)
1630 && GET_CODE (b
) == LTU
1631 && CONST_INT_P (opb1
)
1632 && rtx_equal_p (op0
, opb0
))
1633 return INTVAL (opb1
) < 0;
1638 /* Canonicalizes COND so that
1640 (1) Ensure that operands are ordered according to
1641 swap_commutative_operands_p.
1642 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1643 for GE, GEU, and LEU. */
1646 canon_condition (rtx cond
)
1652 code
= GET_CODE (cond
);
1653 op0
= XEXP (cond
, 0);
1654 op1
= XEXP (cond
, 1);
1656 if (swap_commutative_operands_p (op0
, op1
))
1658 code
= swap_condition (code
);
1659 std::swap (op0
, op1
);
1662 mode
= GET_MODE (op0
);
1663 if (mode
== VOIDmode
)
1664 mode
= GET_MODE (op1
);
1665 gcc_assert (mode
!= VOIDmode
);
1667 if (CONST_SCALAR_INT_P (op1
) && GET_MODE_CLASS (mode
) != MODE_CC
)
1669 rtx_mode_t
const_val (op1
, mode
);
1674 if (wi::ne_p (const_val
, wi::max_value (mode
, SIGNED
)))
1677 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1682 if (wi::ne_p (const_val
, wi::min_value (mode
, SIGNED
)))
1685 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1690 if (wi::ne_p (const_val
, -1))
1693 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1698 if (wi::ne_p (const_val
, 0))
1701 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1710 if (op0
!= XEXP (cond
, 0)
1711 || op1
!= XEXP (cond
, 1)
1712 || code
!= GET_CODE (cond
)
1713 || GET_MODE (cond
) != SImode
)
1714 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1719 /* Reverses CONDition; returns NULL if we cannot. */
1722 reversed_condition (rtx cond
)
1724 enum rtx_code reversed
;
1725 reversed
= reversed_comparison_code (cond
, NULL
);
1726 if (reversed
== UNKNOWN
)
1729 return gen_rtx_fmt_ee (reversed
,
1730 GET_MODE (cond
), XEXP (cond
, 0),
1734 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1735 set of altered regs. */
1738 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1740 rtx rev
, reve
, exp
= *expr
;
1742 /* If some register gets altered later, we do not really speak about its
1743 value at the time of comparison. */
1744 if (altered
&& altered_reg_used (cond
, altered
))
1747 if (GET_CODE (cond
) == EQ
1748 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1750 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1754 if (!COMPARISON_P (exp
))
1757 rev
= reversed_condition (cond
);
1758 reve
= reversed_condition (exp
);
1760 cond
= canon_condition (cond
);
1761 exp
= canon_condition (exp
);
1763 rev
= canon_condition (rev
);
1765 reve
= canon_condition (reve
);
1767 if (rtx_equal_p (exp
, cond
))
1769 *expr
= const_true_rtx
;
1773 if (rev
&& rtx_equal_p (exp
, rev
))
1779 if (implies_p (cond
, exp
))
1781 *expr
= const_true_rtx
;
1785 if (reve
&& implies_p (cond
, reve
))
1791 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1793 if (rev
&& implies_p (exp
, rev
))
1799 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1800 if (rev
&& reve
&& implies_p (reve
, rev
))
1802 *expr
= const_true_rtx
;
1806 /* We would like to have some other tests here. TODO. */
1811 /* Use relationship between A and *B to eventually eliminate *B.
1812 OP is the operation we consider. */
1815 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1820 /* If A implies *B, we may replace *B by true. */
1821 if (implies_p (a
, *b
))
1822 *b
= const_true_rtx
;
1826 /* If *B implies A, we may replace *B by false. */
1827 if (implies_p (*b
, a
))
1836 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1837 operation we consider. */
1840 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1844 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1845 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1846 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1847 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1850 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1851 is a list, its elements are assumed to be combined using OP. */
1854 simplify_using_initial_values (class loop
*loop
, enum rtx_code op
, rtx
*expr
)
1856 bool expression_valid
;
1857 rtx head
, tail
, last_valid_expr
;
1858 rtx_expr_list
*cond_list
;
1861 regset altered
, this_altered
;
1867 if (CONSTANT_P (*expr
))
1870 if (GET_CODE (*expr
) == EXPR_LIST
)
1872 head
= XEXP (*expr
, 0);
1873 tail
= XEXP (*expr
, 1);
1875 eliminate_implied_conditions (op
, &head
, tail
);
1880 neutral
= const_true_rtx
;
1885 neutral
= const0_rtx
;
1886 aggr
= const_true_rtx
;
1893 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1896 XEXP (*expr
, 0) = aggr
;
1897 XEXP (*expr
, 1) = NULL_RTX
;
1900 else if (head
== neutral
)
1903 simplify_using_initial_values (loop
, op
, expr
);
1906 simplify_using_initial_values (loop
, op
, &tail
);
1908 if (tail
&& XEXP (tail
, 0) == aggr
)
1914 XEXP (*expr
, 0) = head
;
1915 XEXP (*expr
, 1) = tail
;
1919 gcc_assert (op
== UNKNOWN
);
1921 replace_single_def_regs (expr
);
1922 if (CONSTANT_P (*expr
))
1925 e
= loop_preheader_edge (loop
);
1926 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1929 altered
= ALLOC_REG_SET (®_obstack
);
1930 this_altered
= ALLOC_REG_SET (®_obstack
);
1932 expression_valid
= true;
1933 last_valid_expr
= *expr
;
1937 insn
= BB_END (e
->src
);
1938 if (any_condjump_p (insn
))
1940 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1942 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1943 cond
= reversed_condition (cond
);
1947 simplify_using_condition (cond
, expr
, altered
);
1951 if (CONSTANT_P (*expr
))
1953 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1955 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1956 if (CONSTANT_P (*expr
))
1960 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1964 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1972 CLEAR_REG_SET (this_altered
);
1973 note_stores (insn
, mark_altered
, this_altered
);
1975 /* Kill all call clobbered registers. */
1976 IOR_REG_SET_HRS (this_altered
, regs_invalidated_by_call
);
1978 if (suitable_set_for_replacement (insn
, &dest
, &src
))
1980 rtx_expr_list
**pnote
, **pnote_next
;
1982 replace_in_expr (expr
, dest
, src
);
1983 if (CONSTANT_P (*expr
))
1986 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
1988 rtx_expr_list
*note
= *pnote
;
1989 rtx old_cond
= XEXP (note
, 0);
1991 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
1992 replace_in_expr (&XEXP (note
, 0), dest
, src
);
1994 /* We can no longer use a condition that has been simplified
1995 to a constant, and simplify_using_condition will abort if
1997 if (CONSTANT_P (XEXP (note
, 0)))
1999 *pnote
= *pnote_next
;
2001 free_EXPR_LIST_node (note
);
2003 /* Retry simplifications with this condition if either the
2004 expression or the condition changed. */
2005 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2006 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2011 rtx_expr_list
**pnote
, **pnote_next
;
2013 /* If we did not use this insn to make a replacement, any overlap
2014 between stores in this insn and our expression will cause the
2015 expression to become invalid. */
2016 if (altered_reg_used (*expr
, this_altered
))
2019 /* Likewise for the conditions. */
2020 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2022 rtx_expr_list
*note
= *pnote
;
2023 rtx old_cond
= XEXP (note
, 0);
2025 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2026 if (altered_reg_used (old_cond
, this_altered
))
2028 *pnote
= *pnote_next
;
2030 free_EXPR_LIST_node (note
);
2035 if (CONSTANT_P (*expr
))
2038 IOR_REG_SET (altered
, this_altered
);
2040 /* If the expression now contains regs that have been altered, we
2041 can't return it to the caller. However, it is still valid for
2042 further simplification, so keep searching to see if we can
2043 eventually turn it into a constant. */
2044 if (altered_reg_used (*expr
, altered
))
2045 expression_valid
= false;
2046 if (expression_valid
)
2047 last_valid_expr
= *expr
;
2050 if (!single_pred_p (e
->src
)
2051 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2053 e
= single_pred_edge (e
->src
);
2057 free_EXPR_LIST_list (&cond_list
);
2058 if (!CONSTANT_P (*expr
))
2059 *expr
= last_valid_expr
;
2060 FREE_REG_SET (altered
);
2061 FREE_REG_SET (this_altered
);
2064 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2065 that IV occurs as left operands of comparison COND and its signedness
2066 is SIGNED_P to DESC. */
2069 shorten_into_mode (class rtx_iv
*iv
, scalar_int_mode mode
,
2070 enum rtx_code cond
, bool signed_p
, class niter_desc
*desc
)
2072 rtx mmin
, mmax
, cond_over
, cond_under
;
2074 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2075 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2077 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2086 if (cond_under
!= const0_rtx
)
2088 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2089 if (cond_over
!= const0_rtx
)
2090 desc
->noloop_assumptions
=
2091 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2098 if (cond_over
!= const0_rtx
)
2100 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2101 if (cond_under
!= const0_rtx
)
2102 desc
->noloop_assumptions
=
2103 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2107 if (cond_over
!= const0_rtx
)
2109 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2110 if (cond_under
!= const0_rtx
)
2112 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2120 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2123 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2124 subregs of the same mode if possible (sometimes it is necessary to add
2125 some assumptions to DESC). */
2128 canonicalize_iv_subregs (class rtx_iv
*iv0
, class rtx_iv
*iv1
,
2129 enum rtx_code cond
, class niter_desc
*desc
)
2131 scalar_int_mode comp_mode
;
2134 /* If the ivs behave specially in the first iteration, or are
2135 added/multiplied after extending, we ignore them. */
2136 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2138 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2141 /* If there is some extend, it must match signedness of the comparison. */
2146 if (iv0
->extend
== IV_ZERO_EXTEND
2147 || iv1
->extend
== IV_ZERO_EXTEND
)
2154 if (iv0
->extend
== IV_SIGN_EXTEND
2155 || iv1
->extend
== IV_SIGN_EXTEND
)
2161 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2162 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2163 && iv0
->extend
!= iv1
->extend
)
2167 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2168 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2169 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2170 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2177 /* Values of both variables should be computed in the same mode. These
2178 might indeed be different, if we have comparison like
2180 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2182 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2183 in different modes. This does not seem impossible to handle, but
2184 it hardly ever occurs in practice.
2186 The only exception is the case when one of operands is invariant.
2187 For example pentium 3 generates comparisons like
2188 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2189 definitely do not want this prevent the optimization. */
2190 comp_mode
= iv0
->extend_mode
;
2191 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2192 comp_mode
= iv1
->extend_mode
;
2194 if (iv0
->extend_mode
!= comp_mode
)
2196 if (iv0
->mode
!= iv0
->extend_mode
2197 || iv0
->step
!= const0_rtx
)
2200 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2201 comp_mode
, iv0
->base
, iv0
->mode
);
2202 iv0
->extend_mode
= comp_mode
;
2205 if (iv1
->extend_mode
!= comp_mode
)
2207 if (iv1
->mode
!= iv1
->extend_mode
2208 || iv1
->step
!= const0_rtx
)
2211 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2212 comp_mode
, iv1
->base
, iv1
->mode
);
2213 iv1
->extend_mode
= comp_mode
;
2216 /* Check that both ivs belong to a range of a single mode. If one of the
2217 operands is an invariant, we may need to shorten it into the common
2219 if (iv0
->mode
== iv0
->extend_mode
2220 && iv0
->step
== const0_rtx
2221 && iv0
->mode
!= iv1
->mode
)
2222 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2224 if (iv1
->mode
== iv1
->extend_mode
2225 && iv1
->step
== const0_rtx
2226 && iv0
->mode
!= iv1
->mode
)
2227 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2229 if (iv0
->mode
!= iv1
->mode
)
2232 desc
->mode
= iv0
->mode
;
2233 desc
->signed_p
= signed_p
;
2238 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2239 result. This function is called from iv_number_of_iterations with
2240 a number of fields in DESC already filled in. OLD_NITER is the original
2241 expression for the number of iterations, before we tried to simplify it. */
2244 determine_max_iter (class loop
*loop
, class niter_desc
*desc
, rtx old_niter
)
2246 rtx niter
= desc
->niter_expr
;
2247 rtx mmin
, mmax
, cmp
;
2249 uint64_t andmax
= 0;
2251 /* We used to look for constant operand 0 of AND,
2252 but canonicalization should always make this impossible. */
2253 gcc_checking_assert (GET_CODE (niter
) != AND
2254 || !CONST_INT_P (XEXP (niter
, 0)));
2256 if (GET_CODE (niter
) == AND
2257 && CONST_INT_P (XEXP (niter
, 1)))
2259 andmax
= UINTVAL (XEXP (niter
, 1));
2260 niter
= XEXP (niter
, 0);
2263 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2264 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2266 if (GET_CODE (niter
) == UDIV
)
2268 if (!CONST_INT_P (XEXP (niter
, 1)))
2270 inc
= INTVAL (XEXP (niter
, 1));
2271 niter
= XEXP (niter
, 0);
2276 /* We could use a binary search here, but for now improving the upper
2277 bound by just one eliminates one important corner case. */
2278 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2279 desc
->mode
, old_niter
, mmax
);
2280 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2281 if (cmp
== const_true_rtx
)
2286 fprintf (dump_file
, ";; improved upper bound by one.\n");
2290 nmax
= MIN (nmax
, andmax
);
2292 fprintf (dump_file
, ";; Determined upper bound %" PRId64
".\n",
2297 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2298 the result into DESC. Very similar to determine_number_of_iterations
2299 (basically its rtl version), complicated by things like subregs. */
2302 iv_number_of_iterations (class loop
*loop
, rtx_insn
*insn
, rtx condition
,
2303 class niter_desc
*desc
)
2305 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2306 class rtx_iv iv0
, iv1
;
2307 rtx assumption
, may_not_xform
;
2309 machine_mode nonvoid_mode
;
2310 scalar_int_mode comp_mode
;
2311 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2312 uint64_t s
, size
, d
, inv
, max
, up
, down
;
2313 int64_t inc
, step_val
;
2314 int was_sharp
= false;
2318 /* The meaning of these assumptions is this:
2320 then the rest of information does not have to be valid
2321 if noloop_assumptions then the loop does not roll
2322 if infinite then this exit is never used */
2324 desc
->assumptions
= NULL_RTX
;
2325 desc
->noloop_assumptions
= NULL_RTX
;
2326 desc
->infinite
= NULL_RTX
;
2327 desc
->simple_p
= true;
2329 desc
->const_iter
= false;
2330 desc
->niter_expr
= NULL_RTX
;
2332 cond
= GET_CODE (condition
);
2333 gcc_assert (COMPARISON_P (condition
));
2335 nonvoid_mode
= GET_MODE (XEXP (condition
, 0));
2336 if (nonvoid_mode
== VOIDmode
)
2337 nonvoid_mode
= GET_MODE (XEXP (condition
, 1));
2338 /* The constant comparisons should be folded. */
2339 gcc_assert (nonvoid_mode
!= VOIDmode
);
2341 /* We only handle integers or pointers. */
2342 scalar_int_mode mode
;
2343 if (!is_a
<scalar_int_mode
> (nonvoid_mode
, &mode
))
2346 op0
= XEXP (condition
, 0);
2347 if (!iv_analyze (insn
, mode
, op0
, &iv0
))
2350 op1
= XEXP (condition
, 1);
2351 if (!iv_analyze (insn
, mode
, op1
, &iv1
))
2354 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2355 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2358 /* Check condition and normalize it. */
2366 std::swap (iv0
, iv1
);
2367 cond
= swap_condition (cond
);
2379 /* Handle extends. This is relatively nontrivial, so we only try in some
2380 easy cases, when we can canonicalize the ivs (possibly by adding some
2381 assumptions) to shape subreg (base + i * step). This function also fills
2382 in desc->mode and desc->signed_p. */
2384 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2387 comp_mode
= iv0
.extend_mode
;
2389 size
= GET_MODE_PRECISION (mode
);
2390 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2391 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2392 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2394 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2397 /* We can take care of the case of two induction variables chasing each other
2398 if the test is NE. I have never seen a loop using it, but still it is
2400 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2405 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2406 iv1
.step
= const0_rtx
;
2409 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2410 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2412 /* This is either infinite loop or the one that ends immediately, depending
2413 on initial values. Unswitching should remove this kind of conditions. */
2414 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2419 if (iv0
.step
== const0_rtx
)
2420 step_val
= -INTVAL (iv1
.step
);
2422 step_val
= INTVAL (iv0
.step
);
2424 /* Ignore loops of while (i-- < 10) type. */
2428 step_is_pow2
= !(step_val
& (step_val
- 1));
2432 /* We do not care about whether the step is power of two in this
2434 step_is_pow2
= false;
2438 /* Some more condition normalization. We must record some assumptions
2439 due to overflows. */
2444 /* We want to take care only of non-sharp relationals; this is easy,
2445 as in cases the overflow would make the transformation unsafe
2446 the loop does not roll. Seemingly it would make more sense to want
2447 to take care of sharp relationals instead, as NE is more similar to
2448 them, but the problem is that here the transformation would be more
2449 difficult due to possibly infinite loops. */
2450 if (iv0
.step
== const0_rtx
)
2452 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2453 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2455 if (assumption
== const_true_rtx
)
2456 goto zero_iter_simplify
;
2457 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2458 iv0
.base
, const1_rtx
);
2462 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2463 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2465 if (assumption
== const_true_rtx
)
2466 goto zero_iter_simplify
;
2467 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2468 iv1
.base
, constm1_rtx
);
2471 if (assumption
!= const0_rtx
)
2472 desc
->noloop_assumptions
=
2473 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2474 cond
= (cond
== LT
) ? LE
: LEU
;
2476 /* It will be useful to be able to tell the difference once more in
2477 LE -> NE reduction. */
2483 /* Take care of trivially infinite loops. */
2486 if (iv0
.step
== const0_rtx
)
2488 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2489 if (rtx_equal_p (tmp
, mode_mmin
))
2492 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2493 /* Fill in the remaining fields somehow. */
2494 goto zero_iter_simplify
;
2499 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2500 if (rtx_equal_p (tmp
, mode_mmax
))
2503 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2504 /* Fill in the remaining fields somehow. */
2505 goto zero_iter_simplify
;
2510 /* If we can we want to take care of NE conditions instead of size
2511 comparisons, as they are much more friendly (most importantly
2512 this takes care of special handling of loops with step 1). We can
2513 do it if we first check that upper bound is greater or equal to
2514 lower bound, their difference is constant c modulo step and that
2515 there is not an overflow. */
2518 if (iv0
.step
== const0_rtx
)
2519 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2522 step
= lowpart_subreg (mode
, step
, comp_mode
);
2523 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2524 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2525 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2526 may_xform
= const0_rtx
;
2527 may_not_xform
= const_true_rtx
;
2529 if (CONST_INT_P (delta
))
2531 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2533 /* A special case. We have transformed condition of type
2534 for (i = 0; i < 4; i += 4)
2536 for (i = 0; i <= 3; i += 4)
2537 obviously if the test for overflow during that transformation
2538 passed, we cannot overflow here. Most importantly any
2539 loop with sharp end condition and step 1 falls into this
2540 category, so handling this case specially is definitely
2541 worth the troubles. */
2542 may_xform
= const_true_rtx
;
2544 else if (iv0
.step
== const0_rtx
)
2546 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2547 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2548 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2549 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2550 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2552 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2558 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2559 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2560 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2561 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2562 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2564 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2570 if (may_xform
!= const0_rtx
)
2572 /* We perform the transformation always provided that it is not
2573 completely senseless. This is OK, as we would need this assumption
2574 to determine the number of iterations anyway. */
2575 if (may_xform
!= const_true_rtx
)
2577 /* If the step is a power of two and the final value we have
2578 computed overflows, the cycle is infinite. Otherwise it
2579 is nontrivial to compute the number of iterations. */
2581 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2584 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2588 /* We are going to lose some information about upper bound on
2589 number of iterations in this step, so record the information
2591 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2592 if (CONST_INT_P (iv1
.base
))
2593 up
= INTVAL (iv1
.base
);
2595 up
= INTVAL (mode_mmax
) - inc
;
2596 down
= INTVAL (CONST_INT_P (iv0
.base
)
2599 max
= (up
- down
) / inc
+ 1;
2601 && !desc
->assumptions
)
2602 record_niter_bound (loop
, max
, false, true);
2604 if (iv0
.step
== const0_rtx
)
2606 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2607 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2611 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2612 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2615 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2616 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2617 assumption
= simplify_gen_relational (reverse_condition (cond
),
2618 SImode
, mode
, tmp0
, tmp1
);
2619 if (assumption
== const_true_rtx
)
2620 goto zero_iter_simplify
;
2621 else if (assumption
!= const0_rtx
)
2622 desc
->noloop_assumptions
=
2623 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2628 /* Count the number of iterations. */
2631 /* Everything we do here is just arithmetics modulo size of mode. This
2632 makes us able to do more involved computations of number of iterations
2633 than in other cases. First transform the condition into shape
2634 s * i <> c, with s positive. */
2635 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2636 iv0
.base
= const0_rtx
;
2637 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2638 iv1
.step
= const0_rtx
;
2639 if (INTVAL (iv0
.step
) < 0)
2641 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2642 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2644 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2646 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2647 is infinite. Otherwise, the number of iterations is
2648 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2649 s
= INTVAL (iv0
.step
); d
= 1;
2656 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2658 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2659 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2660 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2661 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2663 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2664 inv
= inverse (s
, size
);
2665 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2666 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2670 if (iv1
.step
== const0_rtx
)
2671 /* Condition in shape a + s * i <= b
2672 We must know that b + s does not overflow and a <= b + s and then we
2673 can compute number of iterations as (b + s - a) / s. (It might
2674 seem that we in fact could be more clever about testing the b + s
2675 overflow condition using some information about b - a mod s,
2676 but it was already taken into account during LE -> NE transform). */
2679 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2680 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2682 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2683 lowpart_subreg (mode
, step
,
2689 /* If s is power of 2, we know that the loop is infinite if
2690 a % s <= b % s and b + s overflows. */
2691 assumption
= simplify_gen_relational (reverse_condition (cond
),
2695 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2696 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2697 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2698 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2700 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2704 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2707 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2710 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2711 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2712 assumption
= simplify_gen_relational (reverse_condition (cond
),
2713 SImode
, mode
, tmp0
, tmp
);
2715 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2716 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2720 /* Condition in shape a <= b - s * i
2721 We must know that a - s does not overflow and a - s <= b and then
2722 we can again compute number of iterations as (b - (a - s)) / s. */
2723 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2724 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2725 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2727 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2728 lowpart_subreg (mode
, step
, comp_mode
));
2733 /* If s is power of 2, we know that the loop is infinite if
2734 a % s <= b % s and a - s overflows. */
2735 assumption
= simplify_gen_relational (reverse_condition (cond
),
2739 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2740 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2741 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2742 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2744 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2748 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2751 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2754 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2755 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2756 assumption
= simplify_gen_relational (reverse_condition (cond
),
2759 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2760 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2762 if (assumption
== const_true_rtx
)
2763 goto zero_iter_simplify
;
2764 else if (assumption
!= const0_rtx
)
2765 desc
->noloop_assumptions
=
2766 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2767 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2768 desc
->niter_expr
= delta
;
2771 old_niter
= desc
->niter_expr
;
2773 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2774 if (desc
->assumptions
2775 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2777 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2778 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2779 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2781 /* Rerun the simplification. Consider code (created by copying loop headers)
2793 The first pass determines that i = 0, the second pass uses it to eliminate
2794 noloop assumption. */
2796 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2797 if (desc
->assumptions
2798 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2800 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2801 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2802 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2804 if (desc
->noloop_assumptions
2805 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2808 if (CONST_INT_P (desc
->niter_expr
))
2810 uint64_t val
= INTVAL (desc
->niter_expr
);
2812 desc
->const_iter
= true;
2813 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2815 && !desc
->assumptions
)
2816 record_niter_bound (loop
, desc
->niter
, false, true);
2820 max
= determine_max_iter (loop
, desc
, old_niter
);
2822 goto zero_iter_simplify
;
2824 && !desc
->assumptions
)
2825 record_niter_bound (loop
, max
, false, true);
2827 /* simplify_using_initial_values does a copy propagation on the registers
2828 in the expression for the number of iterations. This prolongs life
2829 ranges of registers and increases register pressure, and usually
2830 brings no gain (and if it happens to do, the cse pass will take care
2831 of it anyway). So prevent this behavior, unless it enabled us to
2832 derive that the number of iterations is a constant. */
2833 desc
->niter_expr
= old_niter
;
2839 /* Simplify the assumptions. */
2840 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2841 if (desc
->assumptions
2842 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2844 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2848 desc
->const_iter
= true;
2850 record_niter_bound (loop
, 0, true, true);
2851 desc
->noloop_assumptions
= NULL_RTX
;
2852 desc
->niter_expr
= const0_rtx
;
2856 desc
->simple_p
= false;
2860 /* Checks whether E is a simple exit from LOOP and stores its description
2864 check_simple_exit (class loop
*loop
, edge e
, class niter_desc
*desc
)
2866 basic_block exit_bb
;
2872 desc
->simple_p
= false;
2874 /* It must belong directly to the loop. */
2875 if (exit_bb
->loop_father
!= loop
)
2878 /* It must be tested (at least) once during any iteration. */
2879 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2882 /* It must end in a simple conditional jump. */
2883 if (!any_condjump_p (BB_END (exit_bb
)))
2886 ein
= EDGE_SUCC (exit_bb
, 0);
2888 ein
= EDGE_SUCC (exit_bb
, 1);
2891 desc
->in_edge
= ein
;
2893 /* Test whether the condition is suitable. */
2894 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2897 if (ein
->flags
& EDGE_FALLTHRU
)
2899 condition
= reversed_condition (condition
);
2904 /* Check that we are able to determine number of iterations and fill
2905 in information about it. */
2906 iv_number_of_iterations (loop
, at
, condition
, desc
);
2909 /* Finds a simple exit of LOOP and stores its description into DESC. */
2912 find_simple_exit (class loop
*loop
, class niter_desc
*desc
)
2917 class niter_desc act
;
2921 desc
->simple_p
= false;
2922 body
= get_loop_body (loop
);
2924 for (i
= 0; i
< loop
->num_nodes
; i
++)
2926 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2928 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2931 check_simple_exit (loop
, e
, &act
);
2939 /* Prefer constant iterations; the less the better. */
2941 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2944 /* Also if the actual exit may be infinite, while the old one
2945 not, prefer the old one. */
2946 if (act
.infinite
&& !desc
->infinite
)
2958 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2959 fprintf (dump_file
, " simple exit %d -> %d\n",
2960 desc
->out_edge
->src
->index
,
2961 desc
->out_edge
->dest
->index
);
2962 if (desc
->assumptions
)
2964 fprintf (dump_file
, " assumptions: ");
2965 print_rtl (dump_file
, desc
->assumptions
);
2966 fprintf (dump_file
, "\n");
2968 if (desc
->noloop_assumptions
)
2970 fprintf (dump_file
, " does not roll if: ");
2971 print_rtl (dump_file
, desc
->noloop_assumptions
);
2972 fprintf (dump_file
, "\n");
2976 fprintf (dump_file
, " infinite if: ");
2977 print_rtl (dump_file
, desc
->infinite
);
2978 fprintf (dump_file
, "\n");
2981 fprintf (dump_file
, " number of iterations: ");
2982 print_rtl (dump_file
, desc
->niter_expr
);
2983 fprintf (dump_file
, "\n");
2985 fprintf (dump_file
, " upper bound: %li\n",
2986 (long)get_max_loop_iterations_int (loop
));
2987 fprintf (dump_file
, " likely upper bound: %li\n",
2988 (long)get_likely_max_loop_iterations_int (loop
));
2989 fprintf (dump_file
, " realistic bound: %li\n",
2990 (long)get_estimated_loop_iterations_int (loop
));
2993 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2996 /* Fix up the finiteness if possible. We can only do it for single exit,
2997 since the loop is finite, but it's possible that we predicate one loop
2998 exit to be finite which can not be determined as finite in middle-end as
2999 well. It results in incorrect predicate information on the exit condition
3000 expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite,
3001 it means _1 can exactly divide -8. */
3002 if (desc
->infinite
&& single_exit (loop
) && finite_loop_p (loop
))
3004 desc
->infinite
= NULL_RTX
;
3006 fprintf (dump_file
, " infinite updated to finite.\n");
3012 /* Creates a simple loop description of LOOP if it was not computed
3016 get_simple_loop_desc (class loop
*loop
)
3018 class niter_desc
*desc
= simple_loop_desc (loop
);
3023 /* At least desc->infinite is not always initialized by
3024 find_simple_loop_exit. */
3025 desc
= ggc_cleared_alloc
<niter_desc
> ();
3026 iv_analysis_loop_init (loop
);
3027 find_simple_exit (loop
, desc
);
3028 loop
->simple_loop_desc
= desc
;
3032 /* Releases simple loop description for LOOP. */
3035 free_simple_loop_desc (class loop
*loop
)
3037 class niter_desc
*desc
= simple_loop_desc (loop
);
3043 loop
->simple_loop_desc
= NULL
;