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 (PATTERN (insn
), mark_altered
, this_altered
);
1976 /* Kill all call clobbered registers. */
1978 hard_reg_set_iterator hrsi
;
1979 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
1981 SET_REGNO_REG_SET (this_altered
, i
);
1984 if (suitable_set_for_replacement (insn
, &dest
, &src
))
1986 rtx_expr_list
**pnote
, **pnote_next
;
1988 replace_in_expr (expr
, dest
, src
);
1989 if (CONSTANT_P (*expr
))
1992 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
1994 rtx_expr_list
*note
= *pnote
;
1995 rtx old_cond
= XEXP (note
, 0);
1997 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
1998 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2000 /* We can no longer use a condition that has been simplified
2001 to a constant, and simplify_using_condition will abort if
2003 if (CONSTANT_P (XEXP (note
, 0)))
2005 *pnote
= *pnote_next
;
2007 free_EXPR_LIST_node (note
);
2009 /* Retry simplifications with this condition if either the
2010 expression or the condition changed. */
2011 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2012 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2017 rtx_expr_list
**pnote
, **pnote_next
;
2019 /* If we did not use this insn to make a replacement, any overlap
2020 between stores in this insn and our expression will cause the
2021 expression to become invalid. */
2022 if (altered_reg_used (*expr
, this_altered
))
2025 /* Likewise for the conditions. */
2026 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2028 rtx_expr_list
*note
= *pnote
;
2029 rtx old_cond
= XEXP (note
, 0);
2031 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2032 if (altered_reg_used (old_cond
, this_altered
))
2034 *pnote
= *pnote_next
;
2036 free_EXPR_LIST_node (note
);
2041 if (CONSTANT_P (*expr
))
2044 IOR_REG_SET (altered
, this_altered
);
2046 /* If the expression now contains regs that have been altered, we
2047 can't return it to the caller. However, it is still valid for
2048 further simplification, so keep searching to see if we can
2049 eventually turn it into a constant. */
2050 if (altered_reg_used (*expr
, altered
))
2051 expression_valid
= false;
2052 if (expression_valid
)
2053 last_valid_expr
= *expr
;
2056 if (!single_pred_p (e
->src
)
2057 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2059 e
= single_pred_edge (e
->src
);
2063 free_EXPR_LIST_list (&cond_list
);
2064 if (!CONSTANT_P (*expr
))
2065 *expr
= last_valid_expr
;
2066 FREE_REG_SET (altered
);
2067 FREE_REG_SET (this_altered
);
2070 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2071 that IV occurs as left operands of comparison COND and its signedness
2072 is SIGNED_P to DESC. */
2075 shorten_into_mode (class rtx_iv
*iv
, scalar_int_mode mode
,
2076 enum rtx_code cond
, bool signed_p
, class niter_desc
*desc
)
2078 rtx mmin
, mmax
, cond_over
, cond_under
;
2080 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2081 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2083 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2092 if (cond_under
!= const0_rtx
)
2094 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2095 if (cond_over
!= const0_rtx
)
2096 desc
->noloop_assumptions
=
2097 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2104 if (cond_over
!= const0_rtx
)
2106 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2107 if (cond_under
!= const0_rtx
)
2108 desc
->noloop_assumptions
=
2109 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2113 if (cond_over
!= const0_rtx
)
2115 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2116 if (cond_under
!= const0_rtx
)
2118 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2126 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2129 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2130 subregs of the same mode if possible (sometimes it is necessary to add
2131 some assumptions to DESC). */
2134 canonicalize_iv_subregs (class rtx_iv
*iv0
, class rtx_iv
*iv1
,
2135 enum rtx_code cond
, class niter_desc
*desc
)
2137 scalar_int_mode comp_mode
;
2140 /* If the ivs behave specially in the first iteration, or are
2141 added/multiplied after extending, we ignore them. */
2142 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2144 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2147 /* If there is some extend, it must match signedness of the comparison. */
2152 if (iv0
->extend
== IV_ZERO_EXTEND
2153 || iv1
->extend
== IV_ZERO_EXTEND
)
2160 if (iv0
->extend
== IV_SIGN_EXTEND
2161 || iv1
->extend
== IV_SIGN_EXTEND
)
2167 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2168 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2169 && iv0
->extend
!= iv1
->extend
)
2173 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2174 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2175 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2176 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2183 /* Values of both variables should be computed in the same mode. These
2184 might indeed be different, if we have comparison like
2186 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2188 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2189 in different modes. This does not seem impossible to handle, but
2190 it hardly ever occurs in practice.
2192 The only exception is the case when one of operands is invariant.
2193 For example pentium 3 generates comparisons like
2194 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2195 definitely do not want this prevent the optimization. */
2196 comp_mode
= iv0
->extend_mode
;
2197 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2198 comp_mode
= iv1
->extend_mode
;
2200 if (iv0
->extend_mode
!= comp_mode
)
2202 if (iv0
->mode
!= iv0
->extend_mode
2203 || iv0
->step
!= const0_rtx
)
2206 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2207 comp_mode
, iv0
->base
, iv0
->mode
);
2208 iv0
->extend_mode
= comp_mode
;
2211 if (iv1
->extend_mode
!= comp_mode
)
2213 if (iv1
->mode
!= iv1
->extend_mode
2214 || iv1
->step
!= const0_rtx
)
2217 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2218 comp_mode
, iv1
->base
, iv1
->mode
);
2219 iv1
->extend_mode
= comp_mode
;
2222 /* Check that both ivs belong to a range of a single mode. If one of the
2223 operands is an invariant, we may need to shorten it into the common
2225 if (iv0
->mode
== iv0
->extend_mode
2226 && iv0
->step
== const0_rtx
2227 && iv0
->mode
!= iv1
->mode
)
2228 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2230 if (iv1
->mode
== iv1
->extend_mode
2231 && iv1
->step
== const0_rtx
2232 && iv0
->mode
!= iv1
->mode
)
2233 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2235 if (iv0
->mode
!= iv1
->mode
)
2238 desc
->mode
= iv0
->mode
;
2239 desc
->signed_p
= signed_p
;
2244 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2245 result. This function is called from iv_number_of_iterations with
2246 a number of fields in DESC already filled in. OLD_NITER is the original
2247 expression for the number of iterations, before we tried to simplify it. */
2250 determine_max_iter (class loop
*loop
, class niter_desc
*desc
, rtx old_niter
)
2252 rtx niter
= desc
->niter_expr
;
2253 rtx mmin
, mmax
, cmp
;
2255 uint64_t andmax
= 0;
2257 /* We used to look for constant operand 0 of AND,
2258 but canonicalization should always make this impossible. */
2259 gcc_checking_assert (GET_CODE (niter
) != AND
2260 || !CONST_INT_P (XEXP (niter
, 0)));
2262 if (GET_CODE (niter
) == AND
2263 && CONST_INT_P (XEXP (niter
, 1)))
2265 andmax
= UINTVAL (XEXP (niter
, 1));
2266 niter
= XEXP (niter
, 0);
2269 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2270 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2272 if (GET_CODE (niter
) == UDIV
)
2274 if (!CONST_INT_P (XEXP (niter
, 1)))
2276 inc
= INTVAL (XEXP (niter
, 1));
2277 niter
= XEXP (niter
, 0);
2282 /* We could use a binary search here, but for now improving the upper
2283 bound by just one eliminates one important corner case. */
2284 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2285 desc
->mode
, old_niter
, mmax
);
2286 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2287 if (cmp
== const_true_rtx
)
2292 fprintf (dump_file
, ";; improved upper bound by one.\n");
2296 nmax
= MIN (nmax
, andmax
);
2298 fprintf (dump_file
, ";; Determined upper bound %" PRId64
".\n",
2303 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2304 the result into DESC. Very similar to determine_number_of_iterations
2305 (basically its rtl version), complicated by things like subregs. */
2308 iv_number_of_iterations (class loop
*loop
, rtx_insn
*insn
, rtx condition
,
2309 class niter_desc
*desc
)
2311 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2312 class rtx_iv iv0
, iv1
;
2313 rtx assumption
, may_not_xform
;
2315 machine_mode nonvoid_mode
;
2316 scalar_int_mode comp_mode
;
2317 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2318 uint64_t s
, size
, d
, inv
, max
, up
, down
;
2319 int64_t inc
, step_val
;
2320 int was_sharp
= false;
2324 /* The meaning of these assumptions is this:
2326 then the rest of information does not have to be valid
2327 if noloop_assumptions then the loop does not roll
2328 if infinite then this exit is never used */
2330 desc
->assumptions
= NULL_RTX
;
2331 desc
->noloop_assumptions
= NULL_RTX
;
2332 desc
->infinite
= NULL_RTX
;
2333 desc
->simple_p
= true;
2335 desc
->const_iter
= false;
2336 desc
->niter_expr
= NULL_RTX
;
2338 cond
= GET_CODE (condition
);
2339 gcc_assert (COMPARISON_P (condition
));
2341 nonvoid_mode
= GET_MODE (XEXP (condition
, 0));
2342 if (nonvoid_mode
== VOIDmode
)
2343 nonvoid_mode
= GET_MODE (XEXP (condition
, 1));
2344 /* The constant comparisons should be folded. */
2345 gcc_assert (nonvoid_mode
!= VOIDmode
);
2347 /* We only handle integers or pointers. */
2348 scalar_int_mode mode
;
2349 if (!is_a
<scalar_int_mode
> (nonvoid_mode
, &mode
))
2352 op0
= XEXP (condition
, 0);
2353 if (!iv_analyze (insn
, mode
, op0
, &iv0
))
2356 op1
= XEXP (condition
, 1);
2357 if (!iv_analyze (insn
, mode
, op1
, &iv1
))
2360 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2361 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2364 /* Check condition and normalize it. */
2372 std::swap (iv0
, iv1
);
2373 cond
= swap_condition (cond
);
2385 /* Handle extends. This is relatively nontrivial, so we only try in some
2386 easy cases, when we can canonicalize the ivs (possibly by adding some
2387 assumptions) to shape subreg (base + i * step). This function also fills
2388 in desc->mode and desc->signed_p. */
2390 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2393 comp_mode
= iv0
.extend_mode
;
2395 size
= GET_MODE_PRECISION (mode
);
2396 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2397 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2398 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2400 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2403 /* We can take care of the case of two induction variables chasing each other
2404 if the test is NE. I have never seen a loop using it, but still it is
2406 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2411 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2412 iv1
.step
= const0_rtx
;
2415 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2416 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2418 /* This is either infinite loop or the one that ends immediately, depending
2419 on initial values. Unswitching should remove this kind of conditions. */
2420 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2425 if (iv0
.step
== const0_rtx
)
2426 step_val
= -INTVAL (iv1
.step
);
2428 step_val
= INTVAL (iv0
.step
);
2430 /* Ignore loops of while (i-- < 10) type. */
2434 step_is_pow2
= !(step_val
& (step_val
- 1));
2438 /* We do not care about whether the step is power of two in this
2440 step_is_pow2
= false;
2444 /* Some more condition normalization. We must record some assumptions
2445 due to overflows. */
2450 /* We want to take care only of non-sharp relationals; this is easy,
2451 as in cases the overflow would make the transformation unsafe
2452 the loop does not roll. Seemingly it would make more sense to want
2453 to take care of sharp relationals instead, as NE is more similar to
2454 them, but the problem is that here the transformation would be more
2455 difficult due to possibly infinite loops. */
2456 if (iv0
.step
== const0_rtx
)
2458 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2459 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2461 if (assumption
== const_true_rtx
)
2462 goto zero_iter_simplify
;
2463 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2464 iv0
.base
, const1_rtx
);
2468 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2469 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2471 if (assumption
== const_true_rtx
)
2472 goto zero_iter_simplify
;
2473 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2474 iv1
.base
, constm1_rtx
);
2477 if (assumption
!= const0_rtx
)
2478 desc
->noloop_assumptions
=
2479 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2480 cond
= (cond
== LT
) ? LE
: LEU
;
2482 /* It will be useful to be able to tell the difference once more in
2483 LE -> NE reduction. */
2489 /* Take care of trivially infinite loops. */
2492 if (iv0
.step
== const0_rtx
)
2494 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2495 if (rtx_equal_p (tmp
, mode_mmin
))
2498 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2499 /* Fill in the remaining fields somehow. */
2500 goto zero_iter_simplify
;
2505 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2506 if (rtx_equal_p (tmp
, mode_mmax
))
2509 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2510 /* Fill in the remaining fields somehow. */
2511 goto zero_iter_simplify
;
2516 /* If we can we want to take care of NE conditions instead of size
2517 comparisons, as they are much more friendly (most importantly
2518 this takes care of special handling of loops with step 1). We can
2519 do it if we first check that upper bound is greater or equal to
2520 lower bound, their difference is constant c modulo step and that
2521 there is not an overflow. */
2524 if (iv0
.step
== const0_rtx
)
2525 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2528 step
= lowpart_subreg (mode
, step
, comp_mode
);
2529 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2530 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2531 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2532 may_xform
= const0_rtx
;
2533 may_not_xform
= const_true_rtx
;
2535 if (CONST_INT_P (delta
))
2537 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2539 /* A special case. We have transformed condition of type
2540 for (i = 0; i < 4; i += 4)
2542 for (i = 0; i <= 3; i += 4)
2543 obviously if the test for overflow during that transformation
2544 passed, we cannot overflow here. Most importantly any
2545 loop with sharp end condition and step 1 falls into this
2546 category, so handling this case specially is definitely
2547 worth the troubles. */
2548 may_xform
= const_true_rtx
;
2550 else if (iv0
.step
== const0_rtx
)
2552 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2553 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2554 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2555 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2556 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2558 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2564 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2565 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2566 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2567 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2568 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2570 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2576 if (may_xform
!= const0_rtx
)
2578 /* We perform the transformation always provided that it is not
2579 completely senseless. This is OK, as we would need this assumption
2580 to determine the number of iterations anyway. */
2581 if (may_xform
!= const_true_rtx
)
2583 /* If the step is a power of two and the final value we have
2584 computed overflows, the cycle is infinite. Otherwise it
2585 is nontrivial to compute the number of iterations. */
2587 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2590 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2594 /* We are going to lose some information about upper bound on
2595 number of iterations in this step, so record the information
2597 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2598 if (CONST_INT_P (iv1
.base
))
2599 up
= INTVAL (iv1
.base
);
2601 up
= INTVAL (mode_mmax
) - inc
;
2602 down
= INTVAL (CONST_INT_P (iv0
.base
)
2605 max
= (up
- down
) / inc
+ 1;
2607 && !desc
->assumptions
)
2608 record_niter_bound (loop
, max
, false, true);
2610 if (iv0
.step
== const0_rtx
)
2612 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2613 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2617 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2618 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2621 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2622 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2623 assumption
= simplify_gen_relational (reverse_condition (cond
),
2624 SImode
, mode
, tmp0
, tmp1
);
2625 if (assumption
== const_true_rtx
)
2626 goto zero_iter_simplify
;
2627 else if (assumption
!= const0_rtx
)
2628 desc
->noloop_assumptions
=
2629 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2634 /* Count the number of iterations. */
2637 /* Everything we do here is just arithmetics modulo size of mode. This
2638 makes us able to do more involved computations of number of iterations
2639 than in other cases. First transform the condition into shape
2640 s * i <> c, with s positive. */
2641 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2642 iv0
.base
= const0_rtx
;
2643 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2644 iv1
.step
= const0_rtx
;
2645 if (INTVAL (iv0
.step
) < 0)
2647 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2648 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2650 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2652 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2653 is infinite. Otherwise, the number of iterations is
2654 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2655 s
= INTVAL (iv0
.step
); d
= 1;
2662 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2664 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2665 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2666 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2667 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2669 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2670 inv
= inverse (s
, size
);
2671 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2672 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2676 if (iv1
.step
== const0_rtx
)
2677 /* Condition in shape a + s * i <= b
2678 We must know that b + s does not overflow and a <= b + s and then we
2679 can compute number of iterations as (b + s - a) / s. (It might
2680 seem that we in fact could be more clever about testing the b + s
2681 overflow condition using some information about b - a mod s,
2682 but it was already taken into account during LE -> NE transform). */
2685 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2686 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2688 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2689 lowpart_subreg (mode
, step
,
2695 /* If s is power of 2, we know that the loop is infinite if
2696 a % s <= b % s and b + s overflows. */
2697 assumption
= simplify_gen_relational (reverse_condition (cond
),
2701 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2702 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2703 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2704 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2706 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2710 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2713 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2716 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2717 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2718 assumption
= simplify_gen_relational (reverse_condition (cond
),
2719 SImode
, mode
, tmp0
, tmp
);
2721 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2722 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2726 /* Condition in shape a <= b - s * i
2727 We must know that a - s does not overflow and a - s <= b and then
2728 we can again compute number of iterations as (b - (a - s)) / s. */
2729 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2730 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2731 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2733 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2734 lowpart_subreg (mode
, step
, comp_mode
));
2739 /* If s is power of 2, we know that the loop is infinite if
2740 a % s <= b % s and a - s overflows. */
2741 assumption
= simplify_gen_relational (reverse_condition (cond
),
2745 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2746 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2747 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2748 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2750 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2754 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2757 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2760 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2761 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2762 assumption
= simplify_gen_relational (reverse_condition (cond
),
2765 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2766 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2768 if (assumption
== const_true_rtx
)
2769 goto zero_iter_simplify
;
2770 else if (assumption
!= const0_rtx
)
2771 desc
->noloop_assumptions
=
2772 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2773 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2774 desc
->niter_expr
= delta
;
2777 old_niter
= desc
->niter_expr
;
2779 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2780 if (desc
->assumptions
2781 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2783 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2784 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2785 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2787 /* Rerun the simplification. Consider code (created by copying loop headers)
2799 The first pass determines that i = 0, the second pass uses it to eliminate
2800 noloop assumption. */
2802 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2803 if (desc
->assumptions
2804 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2806 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2807 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2808 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2810 if (desc
->noloop_assumptions
2811 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2814 if (CONST_INT_P (desc
->niter_expr
))
2816 uint64_t val
= INTVAL (desc
->niter_expr
);
2818 desc
->const_iter
= true;
2819 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2821 && !desc
->assumptions
)
2822 record_niter_bound (loop
, desc
->niter
, false, true);
2826 max
= determine_max_iter (loop
, desc
, old_niter
);
2828 goto zero_iter_simplify
;
2830 && !desc
->assumptions
)
2831 record_niter_bound (loop
, max
, false, true);
2833 /* simplify_using_initial_values does a copy propagation on the registers
2834 in the expression for the number of iterations. This prolongs life
2835 ranges of registers and increases register pressure, and usually
2836 brings no gain (and if it happens to do, the cse pass will take care
2837 of it anyway). So prevent this behavior, unless it enabled us to
2838 derive that the number of iterations is a constant. */
2839 desc
->niter_expr
= old_niter
;
2845 /* Simplify the assumptions. */
2846 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2847 if (desc
->assumptions
2848 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2850 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2854 desc
->const_iter
= true;
2856 record_niter_bound (loop
, 0, true, true);
2857 desc
->noloop_assumptions
= NULL_RTX
;
2858 desc
->niter_expr
= const0_rtx
;
2862 desc
->simple_p
= false;
2866 /* Checks whether E is a simple exit from LOOP and stores its description
2870 check_simple_exit (class loop
*loop
, edge e
, class niter_desc
*desc
)
2872 basic_block exit_bb
;
2878 desc
->simple_p
= false;
2880 /* It must belong directly to the loop. */
2881 if (exit_bb
->loop_father
!= loop
)
2884 /* It must be tested (at least) once during any iteration. */
2885 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2888 /* It must end in a simple conditional jump. */
2889 if (!any_condjump_p (BB_END (exit_bb
)))
2892 ein
= EDGE_SUCC (exit_bb
, 0);
2894 ein
= EDGE_SUCC (exit_bb
, 1);
2897 desc
->in_edge
= ein
;
2899 /* Test whether the condition is suitable. */
2900 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2903 if (ein
->flags
& EDGE_FALLTHRU
)
2905 condition
= reversed_condition (condition
);
2910 /* Check that we are able to determine number of iterations and fill
2911 in information about it. */
2912 iv_number_of_iterations (loop
, at
, condition
, desc
);
2915 /* Finds a simple exit of LOOP and stores its description into DESC. */
2918 find_simple_exit (class loop
*loop
, class niter_desc
*desc
)
2923 class niter_desc act
;
2927 desc
->simple_p
= false;
2928 body
= get_loop_body (loop
);
2930 for (i
= 0; i
< loop
->num_nodes
; i
++)
2932 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2934 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2937 check_simple_exit (loop
, e
, &act
);
2945 /* Prefer constant iterations; the less the better. */
2947 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2950 /* Also if the actual exit may be infinite, while the old one
2951 not, prefer the old one. */
2952 if (act
.infinite
&& !desc
->infinite
)
2964 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2965 fprintf (dump_file
, " simple exit %d -> %d\n",
2966 desc
->out_edge
->src
->index
,
2967 desc
->out_edge
->dest
->index
);
2968 if (desc
->assumptions
)
2970 fprintf (dump_file
, " assumptions: ");
2971 print_rtl (dump_file
, desc
->assumptions
);
2972 fprintf (dump_file
, "\n");
2974 if (desc
->noloop_assumptions
)
2976 fprintf (dump_file
, " does not roll if: ");
2977 print_rtl (dump_file
, desc
->noloop_assumptions
);
2978 fprintf (dump_file
, "\n");
2982 fprintf (dump_file
, " infinite if: ");
2983 print_rtl (dump_file
, desc
->infinite
);
2984 fprintf (dump_file
, "\n");
2987 fprintf (dump_file
, " number of iterations: ");
2988 print_rtl (dump_file
, desc
->niter_expr
);
2989 fprintf (dump_file
, "\n");
2991 fprintf (dump_file
, " upper bound: %li\n",
2992 (long)get_max_loop_iterations_int (loop
));
2993 fprintf (dump_file
, " likely upper bound: %li\n",
2994 (long)get_likely_max_loop_iterations_int (loop
));
2995 fprintf (dump_file
, " realistic bound: %li\n",
2996 (long)get_estimated_loop_iterations_int (loop
));
2999 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3002 /* Fix up the finiteness if possible. We can only do it for single exit,
3003 since the loop is finite, but it's possible that we predicate one loop
3004 exit to be finite which can not be determined as finite in middle-end as
3005 well. It results in incorrect predicate information on the exit condition
3006 expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite,
3007 it means _1 can exactly divide -8. */
3008 if (desc
->infinite
&& single_exit (loop
) && finite_loop_p (loop
))
3010 desc
->infinite
= NULL_RTX
;
3012 fprintf (dump_file
, " infinite updated to finite.\n");
3018 /* Creates a simple loop description of LOOP if it was not computed
3022 get_simple_loop_desc (class loop
*loop
)
3024 class niter_desc
*desc
= simple_loop_desc (loop
);
3029 /* At least desc->infinite is not always initialized by
3030 find_simple_loop_exit. */
3031 desc
= ggc_cleared_alloc
<niter_desc
> ();
3032 iv_analysis_loop_init (loop
);
3033 find_simple_exit (loop
, desc
);
3034 loop
->simple_loop_desc
= desc
;
3038 /* Releases simple loop description for LOOP. */
3041 free_simple_loop_desc (class loop
*loop
)
3043 class niter_desc
*desc
= simple_loop_desc (loop
);
3049 loop
->simple_loop_desc
= NULL
;