1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
64 #include "dominance.h"
66 #include "basic-block.h"
70 #include "statistics.h"
71 #include "double-int.h"
73 #include "fixed-value.h"
78 #include "insn-config.h"
88 #include "diagnostic-core.h"
90 #include "hash-table.h"
94 /* Possible return values of iv_get_reaching_def. */
98 /* More than one reaching def, or reaching def that does not
102 /* The use is trivial invariant of the loop, i.e. is not changed
106 /* The use is reached by initial value and a value from the
107 previous iteration. */
110 /* The use has single dominating def. */
114 /* Information about a biv. */
118 unsigned regno
; /* The register of the biv. */
119 struct rtx_iv iv
; /* Value of the biv. */
122 static bool clean_slate
= true;
124 static unsigned int iv_ref_table_size
= 0;
126 /* Table of rtx_ivs indexed by the df_ref uid field. */
127 static struct rtx_iv
** iv_ref_table
;
129 /* Induction variable stored at the reference. */
130 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
131 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
133 /* The current loop. */
135 static struct loop
*current_loop
;
137 /* Hashtable helper. */
139 struct biv_entry_hasher
: typed_free_remove
<biv_entry
>
141 typedef biv_entry value_type
;
142 typedef rtx_def compare_type
;
143 static inline hashval_t
hash (const value_type
*);
144 static inline bool equal (const value_type
*, const compare_type
*);
147 /* Returns hash value for biv B. */
150 biv_entry_hasher::hash (const value_type
*b
)
155 /* Compares biv B and register R. */
158 biv_entry_hasher::equal (const value_type
*b
, const compare_type
*r
)
160 return b
->regno
== REGNO (r
);
163 /* Bivs of the current loop. */
165 static hash_table
<biv_entry_hasher
> *bivs
;
167 static bool iv_analyze_op (rtx_insn
*, rtx
, struct rtx_iv
*);
169 /* Return the RTX code corresponding to the IV extend code EXTEND. */
170 static inline enum rtx_code
171 iv_extend_to_rtx_code (enum iv_extend_code extend
)
179 case IV_UNKNOWN_EXTEND
:
185 /* Dumps information about IV to FILE. */
187 extern void dump_iv_info (FILE *, struct rtx_iv
*);
189 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
193 fprintf (file
, "not simple");
197 if (iv
->step
== const0_rtx
198 && !iv
->first_special
)
199 fprintf (file
, "invariant ");
201 print_rtl (file
, iv
->base
);
202 if (iv
->step
!= const0_rtx
)
204 fprintf (file
, " + ");
205 print_rtl (file
, iv
->step
);
206 fprintf (file
, " * iteration");
208 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
210 if (iv
->mode
!= iv
->extend_mode
)
211 fprintf (file
, " %s to %s",
212 rtx_name
[iv_extend_to_rtx_code (iv
->extend
)],
213 GET_MODE_NAME (iv
->extend_mode
));
215 if (iv
->mult
!= const1_rtx
)
217 fprintf (file
, " * ");
218 print_rtl (file
, iv
->mult
);
220 if (iv
->delta
!= const0_rtx
)
222 fprintf (file
, " + ");
223 print_rtl (file
, iv
->delta
);
225 if (iv
->first_special
)
226 fprintf (file
, " (first special)");
229 /* Generates a subreg to get the least significant part of EXPR (in mode
230 INNER_MODE) to OUTER_MODE. */
233 lowpart_subreg (machine_mode outer_mode
, rtx expr
,
234 machine_mode inner_mode
)
236 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
237 subreg_lowpart_offset (outer_mode
, inner_mode
));
241 check_iv_ref_table_size (void)
243 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
245 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
246 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
247 memset (&iv_ref_table
[iv_ref_table_size
], 0,
248 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
249 iv_ref_table_size
= new_size
;
254 /* Checks whether REG is a well-behaved register. */
257 simple_reg_p (rtx reg
)
261 if (GET_CODE (reg
) == SUBREG
)
263 if (!subreg_lowpart_p (reg
))
265 reg
= SUBREG_REG (reg
);
272 if (HARD_REGISTER_NUM_P (r
))
275 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
281 /* Clears the information about ivs stored in df. */
286 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
289 check_iv_ref_table_size ();
290 for (i
= 0; i
< n_defs
; i
++)
292 iv
= iv_ref_table
[i
];
296 iv_ref_table
[i
] = NULL
;
304 /* Prepare the data for an induction variable analysis of a LOOP. */
307 iv_analysis_loop_init (struct loop
*loop
)
311 /* Clear the information from the analysis of the previous loop. */
314 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
315 bivs
= new hash_table
<biv_entry_hasher
> (10);
321 /* Get rid of the ud chains before processing the rescans. Then add
323 df_remove_problem (df_chain
);
324 df_process_deferred_rescans ();
325 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
326 df_chain_add_problem (DF_UD_CHAIN
);
327 df_note_add_problem ();
328 df_analyze_loop (loop
);
330 df_dump_region (dump_file
);
332 check_iv_ref_table_size ();
335 /* Finds the definition of REG that dominates loop latch and stores
336 it to DEF. Returns false if there is not a single definition
337 dominating the latch. If REG has no definition in loop, DEF
338 is set to NULL and true is returned. */
341 latch_dominating_def (rtx reg
, df_ref
*def
)
343 df_ref single_rd
= NULL
, adef
;
344 unsigned regno
= REGNO (reg
);
345 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
347 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
349 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
350 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
353 /* More than one reaching definition. */
357 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
367 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
369 static enum iv_grd_result
370 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
373 basic_block def_bb
, use_bb
;
378 if (!simple_reg_p (reg
))
380 if (GET_CODE (reg
) == SUBREG
)
381 reg
= SUBREG_REG (reg
);
382 gcc_assert (REG_P (reg
));
384 use
= df_find_use (insn
, reg
);
385 gcc_assert (use
!= NULL
);
387 if (!DF_REF_CHAIN (use
))
388 return GRD_INVARIANT
;
390 /* More than one reaching def. */
391 if (DF_REF_CHAIN (use
)->next
)
394 adef
= DF_REF_CHAIN (use
)->ref
;
396 /* We do not handle setting only part of the register. */
397 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
400 def_insn
= DF_REF_INSN (adef
);
401 def_bb
= DF_REF_BB (adef
);
402 use_bb
= BLOCK_FOR_INSN (insn
);
404 if (use_bb
== def_bb
)
405 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
407 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
412 return GRD_SINGLE_DOM
;
415 /* The definition does not dominate the use. This is still OK if
416 this may be a use of a biv, i.e. if the def_bb dominates loop
418 if (just_once_each_iteration_p (current_loop
, def_bb
))
419 return GRD_MAYBE_BIV
;
424 /* Sets IV to invariant CST in MODE. Always returns true (just for
425 consistency with other iv manipulation functions that may fail). */
428 iv_constant (struct rtx_iv
*iv
, rtx cst
, machine_mode mode
)
430 if (mode
== VOIDmode
)
431 mode
= GET_MODE (cst
);
435 iv
->step
= const0_rtx
;
436 iv
->first_special
= false;
437 iv
->extend
= IV_UNKNOWN_EXTEND
;
438 iv
->extend_mode
= iv
->mode
;
439 iv
->delta
= const0_rtx
;
440 iv
->mult
= const1_rtx
;
445 /* Evaluates application of subreg to MODE on IV. */
448 iv_subreg (struct rtx_iv
*iv
, machine_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 val
= lowpart_subreg (mode
, val
,
456 iv
->extend
== IV_UNKNOWN_EXTEND
457 ? iv
->mode
: iv
->extend_mode
);
460 iv
->extend
= IV_UNKNOWN_EXTEND
;
461 iv
->mode
= iv
->extend_mode
= mode
;
462 iv
->delta
= const0_rtx
;
463 iv
->mult
= const1_rtx
;
467 if (iv
->extend_mode
== mode
)
470 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
473 iv
->extend
= IV_UNKNOWN_EXTEND
;
476 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
477 simplify_gen_binary (MULT
, iv
->extend_mode
,
478 iv
->base
, iv
->mult
));
479 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
480 iv
->mult
= const1_rtx
;
481 iv
->delta
= const0_rtx
;
482 iv
->first_special
= false;
487 /* Evaluates application of EXTEND to MODE on IV. */
490 iv_extend (struct rtx_iv
*iv
, enum iv_extend_code extend
, machine_mode mode
)
492 /* If iv is invariant, just calculate the new value. */
493 if (iv
->step
== const0_rtx
494 && !iv
->first_special
)
496 rtx val
= get_iv_value (iv
, const0_rtx
);
497 if (iv
->extend_mode
!= iv
->mode
498 && iv
->extend
!= IV_UNKNOWN_EXTEND
499 && iv
->extend
!= extend
)
500 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
501 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
504 ? iv
->extend_mode
: iv
->mode
);
506 iv
->extend
= IV_UNKNOWN_EXTEND
;
507 iv
->mode
= iv
->extend_mode
= mode
;
508 iv
->delta
= const0_rtx
;
509 iv
->mult
= const1_rtx
;
513 if (mode
!= iv
->extend_mode
)
516 if (iv
->extend
!= IV_UNKNOWN_EXTEND
517 && iv
->extend
!= extend
)
525 /* Evaluates negation of IV. */
528 iv_neg (struct rtx_iv
*iv
)
530 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
532 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
533 iv
->base
, iv
->extend_mode
);
534 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
535 iv
->step
, iv
->extend_mode
);
539 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
540 iv
->delta
, iv
->extend_mode
);
541 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
542 iv
->mult
, iv
->extend_mode
);
548 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
551 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
556 /* Extend the constant to extend_mode of the other operand if necessary. */
557 if (iv0
->extend
== IV_UNKNOWN_EXTEND
558 && iv0
->mode
== iv0
->extend_mode
559 && iv0
->step
== const0_rtx
560 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
562 iv0
->extend_mode
= iv1
->extend_mode
;
563 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
564 iv0
->base
, iv0
->mode
);
566 if (iv1
->extend
== IV_UNKNOWN_EXTEND
567 && iv1
->mode
== iv1
->extend_mode
568 && iv1
->step
== const0_rtx
569 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
571 iv1
->extend_mode
= iv0
->extend_mode
;
572 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
573 iv1
->base
, iv1
->mode
);
576 mode
= iv0
->extend_mode
;
577 if (mode
!= iv1
->extend_mode
)
580 if (iv0
->extend
== IV_UNKNOWN_EXTEND
581 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
583 if (iv0
->mode
!= iv1
->mode
)
586 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
587 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
592 /* Handle addition of constant. */
593 if (iv1
->extend
== IV_UNKNOWN_EXTEND
595 && iv1
->step
== const0_rtx
)
597 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
601 if (iv0
->extend
== IV_UNKNOWN_EXTEND
603 && iv0
->step
== const0_rtx
)
611 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
618 /* Evaluates multiplication of IV by constant CST. */
621 iv_mult (struct rtx_iv
*iv
, rtx mby
)
623 machine_mode mode
= iv
->extend_mode
;
625 if (GET_MODE (mby
) != VOIDmode
626 && GET_MODE (mby
) != mode
)
629 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
631 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
632 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
636 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
637 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
643 /* Evaluates shift of IV by constant CST. */
646 iv_shift (struct rtx_iv
*iv
, rtx mby
)
648 machine_mode mode
= iv
->extend_mode
;
650 if (GET_MODE (mby
) != VOIDmode
651 && GET_MODE (mby
) != mode
)
654 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
656 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
657 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
661 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
662 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
668 /* The recursive part of get_biv_step. Gets the value of the single value
669 defined by DEF wrto initial value of REG inside loop, in shape described
673 get_biv_step_1 (df_ref def
, rtx reg
,
674 rtx
*inner_step
, machine_mode
*inner_mode
,
675 enum iv_extend_code
*extend
, machine_mode outer_mode
,
678 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
679 rtx next
, nextr
, tmp
;
681 rtx_insn
*insn
= DF_REF_INSN (def
);
683 enum iv_grd_result res
;
685 set
= single_set (insn
);
689 rhs
= find_reg_equal_equiv_note (insn
);
695 code
= GET_CODE (rhs
);
708 if (code
== PLUS
&& CONSTANT_P (op0
))
710 tmp
= op0
; op0
= op1
; op1
= tmp
;
713 if (!simple_reg_p (op0
)
714 || !CONSTANT_P (op1
))
717 if (GET_MODE (rhs
) != outer_mode
)
719 /* ppc64 uses expressions like
721 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
723 this is equivalent to
725 (set x':DI (plus:DI y:DI 1))
726 (set x:SI (subreg:SI (x':DI)). */
727 if (GET_CODE (op0
) != SUBREG
)
729 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
738 if (GET_MODE (rhs
) != outer_mode
)
742 if (!simple_reg_p (op0
))
752 if (GET_CODE (next
) == SUBREG
)
754 if (!subreg_lowpart_p (next
))
757 nextr
= SUBREG_REG (next
);
758 if (GET_MODE (nextr
) != outer_mode
)
764 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
766 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
769 if (res
== GRD_MAYBE_BIV
)
771 if (!rtx_equal_p (nextr
, reg
))
774 *inner_step
= const0_rtx
;
775 *extend
= IV_UNKNOWN_EXTEND
;
776 *inner_mode
= outer_mode
;
777 *outer_step
= const0_rtx
;
779 else if (!get_biv_step_1 (next_def
, reg
,
780 inner_step
, inner_mode
, extend
, outer_mode
,
784 if (GET_CODE (next
) == SUBREG
)
786 machine_mode amode
= GET_MODE (next
);
788 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
792 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
793 *inner_step
, *outer_step
);
794 *outer_step
= const0_rtx
;
795 *extend
= IV_UNKNOWN_EXTEND
;
806 if (*inner_mode
== outer_mode
807 /* See comment in previous switch. */
808 || GET_MODE (rhs
) != outer_mode
)
809 *inner_step
= simplify_gen_binary (code
, outer_mode
,
812 *outer_step
= simplify_gen_binary (code
, outer_mode
,
818 gcc_assert (GET_MODE (op0
) == *inner_mode
819 && *extend
== IV_UNKNOWN_EXTEND
820 && *outer_step
== const0_rtx
);
822 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
832 /* Gets the operation on register REG inside loop, in shape
834 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
836 If the operation cannot be described in this shape, return false.
837 LAST_DEF is the definition of REG that dominates loop latch. */
840 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
841 machine_mode
*inner_mode
, enum iv_extend_code
*extend
,
842 machine_mode
*outer_mode
, rtx
*outer_step
)
844 *outer_mode
= GET_MODE (reg
);
846 if (!get_biv_step_1 (last_def
, reg
,
847 inner_step
, inner_mode
, extend
, *outer_mode
,
851 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
852 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
857 /* Records information that DEF is induction variable IV. */
860 record_iv (df_ref def
, struct rtx_iv
*iv
)
862 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
865 check_iv_ref_table_size ();
866 DF_REF_IV_SET (def
, recorded_iv
);
869 /* If DEF was already analyzed for bivness, store the description of the biv to
870 IV and return true. Otherwise return false. */
873 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
875 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
885 record_biv (rtx def
, struct rtx_iv
*iv
)
887 struct biv_entry
*biv
= XNEW (struct biv_entry
);
888 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
890 biv
->regno
= REGNO (def
);
896 /* Determines whether DEF is a biv and if so, stores its description
900 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
902 rtx inner_step
, outer_step
;
903 machine_mode inner_mode
, outer_mode
;
904 enum iv_extend_code extend
;
909 fprintf (dump_file
, "Analyzing ");
910 print_rtl (dump_file
, def
);
911 fprintf (dump_file
, " for bivness.\n");
916 if (!CONSTANT_P (def
))
919 return iv_constant (iv
, def
, VOIDmode
);
922 if (!latch_dominating_def (def
, &last_def
))
925 fprintf (dump_file
, " not simple.\n");
930 return iv_constant (iv
, def
, VOIDmode
);
932 if (analyzed_for_bivness_p (def
, iv
))
935 fprintf (dump_file
, " already analysed.\n");
936 return iv
->base
!= NULL_RTX
;
939 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
940 &outer_mode
, &outer_step
))
946 /* Loop transforms base to es (base + inner_step) + outer_step,
947 where es means extend of subreg between inner_mode and outer_mode.
948 The corresponding induction variable is
950 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
952 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
953 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
954 iv
->mode
= inner_mode
;
955 iv
->extend_mode
= outer_mode
;
957 iv
->mult
= const1_rtx
;
958 iv
->delta
= outer_step
;
959 iv
->first_special
= inner_mode
!= outer_mode
;
964 fprintf (dump_file
, " ");
965 dump_iv_info (dump_file
, iv
);
966 fprintf (dump_file
, "\n");
969 record_biv (def
, iv
);
970 return iv
->base
!= NULL_RTX
;
973 /* Analyzes expression RHS used at INSN and stores the result to *IV.
974 The mode of the induction variable is MODE. */
977 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, machine_mode mode
,
980 rtx mby
= NULL_RTX
, tmp
;
981 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
982 struct rtx_iv iv0
, iv1
;
983 enum rtx_code code
= GET_CODE (rhs
);
984 machine_mode omode
= mode
;
990 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
996 if (!iv_analyze_op (insn
, rhs
, iv
))
999 if (iv
->mode
== VOIDmode
)
1002 iv
->extend_mode
= mode
;
1017 op0
= XEXP (rhs
, 0);
1018 omode
= GET_MODE (op0
);
1023 op0
= XEXP (rhs
, 0);
1024 op1
= XEXP (rhs
, 1);
1028 op0
= XEXP (rhs
, 0);
1029 mby
= XEXP (rhs
, 1);
1030 if (!CONSTANT_P (mby
))
1036 if (!CONSTANT_P (mby
))
1041 op0
= XEXP (rhs
, 0);
1042 mby
= XEXP (rhs
, 1);
1043 if (!CONSTANT_P (mby
))
1052 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1056 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1062 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1067 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1078 if (!iv_add (&iv0
, &iv1
, code
))
1083 if (!iv_mult (&iv0
, mby
))
1088 if (!iv_shift (&iv0
, mby
))
1097 return iv
->base
!= NULL_RTX
;
1100 /* Analyzes iv DEF and stores the result to *IV. */
1103 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1105 rtx_insn
*insn
= DF_REF_INSN (def
);
1106 rtx reg
= DF_REF_REG (def
);
1111 fprintf (dump_file
, "Analyzing def of ");
1112 print_rtl (dump_file
, reg
);
1113 fprintf (dump_file
, " in insn ");
1114 print_rtl_single (dump_file
, insn
);
1117 check_iv_ref_table_size ();
1118 if (DF_REF_IV (def
))
1121 fprintf (dump_file
, " already analysed.\n");
1122 *iv
= *DF_REF_IV (def
);
1123 return iv
->base
!= NULL_RTX
;
1126 iv
->mode
= VOIDmode
;
1127 iv
->base
= NULL_RTX
;
1128 iv
->step
= NULL_RTX
;
1133 set
= single_set (insn
);
1137 if (!REG_P (SET_DEST (set
)))
1140 gcc_assert (SET_DEST (set
) == reg
);
1141 rhs
= find_reg_equal_equiv_note (insn
);
1143 rhs
= XEXP (rhs
, 0);
1145 rhs
= SET_SRC (set
);
1147 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1148 record_iv (def
, iv
);
1152 print_rtl (dump_file
, reg
);
1153 fprintf (dump_file
, " in insn ");
1154 print_rtl_single (dump_file
, insn
);
1155 fprintf (dump_file
, " is ");
1156 dump_iv_info (dump_file
, iv
);
1157 fprintf (dump_file
, "\n");
1160 return iv
->base
!= NULL_RTX
;
1163 /* Analyzes operand OP of INSN and stores the result to *IV. */
1166 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1169 enum iv_grd_result res
;
1173 fprintf (dump_file
, "Analyzing operand ");
1174 print_rtl (dump_file
, op
);
1175 fprintf (dump_file
, " of insn ");
1176 print_rtl_single (dump_file
, insn
);
1179 if (function_invariant_p (op
))
1180 res
= GRD_INVARIANT
;
1181 else if (GET_CODE (op
) == SUBREG
)
1183 if (!subreg_lowpart_p (op
))
1186 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1189 return iv_subreg (iv
, GET_MODE (op
));
1193 res
= iv_get_reaching_def (insn
, op
, &def
);
1194 if (res
== GRD_INVALID
)
1197 fprintf (dump_file
, " not simple.\n");
1202 if (res
== GRD_INVARIANT
)
1204 iv_constant (iv
, op
, VOIDmode
);
1208 fprintf (dump_file
, " ");
1209 dump_iv_info (dump_file
, iv
);
1210 fprintf (dump_file
, "\n");
1215 if (res
== GRD_MAYBE_BIV
)
1216 return iv_analyze_biv (op
, iv
);
1218 return iv_analyze_def (def
, iv
);
1221 /* Analyzes value VAL at INSN and stores the result to *IV. */
1224 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1228 /* We must find the insn in that val is used, so that we get to UD chains.
1229 Since the function is sometimes called on result of get_condition,
1230 this does not necessarily have to be directly INSN; scan also the
1232 if (simple_reg_p (val
))
1234 if (GET_CODE (val
) == SUBREG
)
1235 reg
= SUBREG_REG (val
);
1239 while (!df_find_use (insn
, reg
))
1240 insn
= NEXT_INSN (insn
);
1243 return iv_analyze_op (insn
, val
, iv
);
1246 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1249 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1253 adef
= df_find_def (insn
, def
);
1257 return iv_analyze_def (adef
, iv
);
1260 /* Checks whether definition of register REG in INSN is a basic induction
1261 variable. IV analysis must have been initialized (via a call to
1262 iv_analysis_loop_init) for this function to produce a result. */
1265 biv_p (rtx_insn
*insn
, rtx reg
)
1268 df_ref def
, last_def
;
1270 if (!simple_reg_p (reg
))
1273 def
= df_find_def (insn
, reg
);
1274 gcc_assert (def
!= NULL
);
1275 if (!latch_dominating_def (reg
, &last_def
))
1277 if (last_def
!= def
)
1280 if (!iv_analyze_biv (reg
, &iv
))
1283 return iv
.step
!= const0_rtx
;
1286 /* Calculates value of IV at ITERATION-th iteration. */
1289 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1293 /* We would need to generate some if_then_else patterns, and so far
1294 it is not needed anywhere. */
1295 gcc_assert (!iv
->first_special
);
1297 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1298 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1299 simplify_gen_binary (MULT
, iv
->extend_mode
,
1300 iv
->step
, iteration
));
1304 if (iv
->extend_mode
== iv
->mode
)
1307 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1309 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1312 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1313 iv
->extend_mode
, val
, iv
->mode
);
1314 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1315 simplify_gen_binary (MULT
, iv
->extend_mode
,
1321 /* Free the data for an induction variable analysis. */
1324 iv_analysis_done (void)
1330 df_finish_pass (true);
1333 free (iv_ref_table
);
1334 iv_ref_table
= NULL
;
1335 iv_ref_table_size
= 0;
1339 /* Computes inverse to X modulo (1 << MOD). */
1342 inverse (uint64_t x
, int mod
)
1345 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1349 for (i
= 0; i
< mod
- 1; i
++)
1351 rslt
= (rslt
* x
) & mask
;
1358 /* Checks whether any register in X is in set ALT. */
1361 altered_reg_used (const_rtx x
, bitmap alt
)
1363 subrtx_iterator::array_type array
;
1364 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
1366 const_rtx x
= *iter
;
1367 if (REG_P (x
) && REGNO_REG_SET_P (alt
, REGNO (x
)))
1373 /* Marks registers altered by EXPR in set ALT. */
1376 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1378 if (GET_CODE (expr
) == SUBREG
)
1379 expr
= SUBREG_REG (expr
);
1383 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1386 /* Checks whether RHS is simple enough to process. */
1389 simple_rhs_p (rtx rhs
)
1393 if (function_invariant_p (rhs
)
1394 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1397 switch (GET_CODE (rhs
))
1402 op0
= XEXP (rhs
, 0);
1403 op1
= XEXP (rhs
, 1);
1404 /* Allow reg OP const and reg OP reg. */
1405 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1406 && !function_invariant_p (op0
))
1408 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1409 && !function_invariant_p (op1
))
1418 op0
= XEXP (rhs
, 0);
1419 op1
= XEXP (rhs
, 1);
1420 /* Allow reg OP const. */
1421 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1423 if (!function_invariant_p (op1
))
1433 /* If REGNO has a single definition, return its known value, otherwise return
1437 find_single_def_src (unsigned int regno
)
1445 adef
= DF_REG_DEF_CHAIN (regno
);
1446 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1447 || DF_REF_IS_ARTIFICIAL (adef
))
1450 set
= single_set (DF_REF_INSN (adef
));
1451 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1452 || REGNO (SET_DEST (set
)) != regno
)
1455 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1457 if (note
&& function_invariant_p (XEXP (note
, 0)))
1459 src
= XEXP (note
, 0);
1462 src
= SET_SRC (set
);
1466 regno
= REGNO (src
);
1471 if (!function_invariant_p (src
))
1477 /* If any registers in *EXPR that have a single definition, try to replace
1478 them with the known-equivalent values. */
1481 replace_single_def_regs (rtx
*expr
)
1483 subrtx_var_iterator::array_type array
;
1485 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1489 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1491 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1497 /* A subroutine of simplify_using_initial_values, this function examines INSN
1498 to see if it contains a suitable set that we can use to make a replacement.
1499 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1500 the set; return false otherwise. */
1503 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1505 rtx set
= single_set (insn
);
1506 rtx lhs
= NULL_RTX
, rhs
;
1511 lhs
= SET_DEST (set
);
1515 rhs
= find_reg_equal_equiv_note (insn
);
1517 rhs
= XEXP (rhs
, 0);
1519 rhs
= SET_SRC (set
);
1521 if (!simple_rhs_p (rhs
))
1529 /* Using the data returned by suitable_set_for_replacement, replace DEST
1530 with SRC in *EXPR and return the new expression. Also call
1531 replace_single_def_regs if the replacement changed something. */
1533 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1536 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1539 replace_single_def_regs (expr
);
1542 /* Checks whether A implies B. */
1545 implies_p (rtx a
, rtx b
)
1547 rtx op0
, op1
, opb0
, opb1
, r
;
1550 if (rtx_equal_p (a
, b
))
1553 if (GET_CODE (a
) == EQ
)
1559 || (GET_CODE (op0
) == SUBREG
1560 && REG_P (SUBREG_REG (op0
))))
1562 r
= simplify_replace_rtx (b
, op0
, op1
);
1563 if (r
== const_true_rtx
)
1568 || (GET_CODE (op1
) == SUBREG
1569 && REG_P (SUBREG_REG (op1
))))
1571 r
= simplify_replace_rtx (b
, op1
, op0
);
1572 if (r
== const_true_rtx
)
1577 if (b
== const_true_rtx
)
1580 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1581 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1582 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1583 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1591 mode
= GET_MODE (op0
);
1592 if (mode
!= GET_MODE (opb0
))
1594 else if (mode
== VOIDmode
)
1596 mode
= GET_MODE (op1
);
1597 if (mode
!= GET_MODE (opb1
))
1601 /* A < B implies A + 1 <= B. */
1602 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1603 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1606 if (GET_CODE (a
) == GT
)
1613 if (GET_CODE (b
) == GE
)
1620 if (SCALAR_INT_MODE_P (mode
)
1621 && rtx_equal_p (op1
, opb1
)
1622 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1627 /* A < B or A > B imply A != B. TODO: Likewise
1628 A + n < B implies A != B + n if neither wraps. */
1629 if (GET_CODE (b
) == NE
1630 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1631 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1633 if (rtx_equal_p (op0
, opb0
)
1634 && rtx_equal_p (op1
, opb1
))
1638 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1639 if (GET_CODE (a
) == NE
1640 && op1
== const0_rtx
)
1642 if ((GET_CODE (b
) == GTU
1643 && opb1
== const0_rtx
)
1644 || (GET_CODE (b
) == GEU
1645 && opb1
== const1_rtx
))
1646 return rtx_equal_p (op0
, opb0
);
1649 /* A != N is equivalent to A - (N + 1) <u -1. */
1650 if (GET_CODE (a
) == NE
1651 && CONST_INT_P (op1
)
1652 && GET_CODE (b
) == LTU
1653 && opb1
== constm1_rtx
1654 && GET_CODE (opb0
) == PLUS
1655 && CONST_INT_P (XEXP (opb0
, 1))
1656 /* Avoid overflows. */
1657 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1658 != ((unsigned HOST_WIDE_INT
)1
1659 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1660 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1661 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1663 /* Likewise, A != N implies A - N > 0. */
1664 if (GET_CODE (a
) == NE
1665 && CONST_INT_P (op1
))
1667 if (GET_CODE (b
) == GTU
1668 && GET_CODE (opb0
) == PLUS
1669 && opb1
== const0_rtx
1670 && CONST_INT_P (XEXP (opb0
, 1))
1671 /* Avoid overflows. */
1672 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1673 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1674 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1675 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1676 if (GET_CODE (b
) == GEU
1677 && GET_CODE (opb0
) == PLUS
1678 && opb1
== const1_rtx
1679 && CONST_INT_P (XEXP (opb0
, 1))
1680 /* Avoid overflows. */
1681 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1682 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1683 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1684 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1687 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1688 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1689 && CONST_INT_P (op1
)
1690 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1691 || INTVAL (op1
) >= 0)
1692 && GET_CODE (b
) == LTU
1693 && CONST_INT_P (opb1
)
1694 && rtx_equal_p (op0
, opb0
))
1695 return INTVAL (opb1
) < 0;
1700 /* Canonicalizes COND so that
1702 (1) Ensure that operands are ordered according to
1703 swap_commutative_operands_p.
1704 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1705 for GE, GEU, and LEU. */
1708 canon_condition (rtx cond
)
1715 code
= GET_CODE (cond
);
1716 op0
= XEXP (cond
, 0);
1717 op1
= XEXP (cond
, 1);
1719 if (swap_commutative_operands_p (op0
, op1
))
1721 code
= swap_condition (code
);
1727 mode
= GET_MODE (op0
);
1728 if (mode
== VOIDmode
)
1729 mode
= GET_MODE (op1
);
1730 gcc_assert (mode
!= VOIDmode
);
1732 if (CONST_INT_P (op1
)
1733 && GET_MODE_CLASS (mode
) != MODE_CC
1734 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1736 HOST_WIDE_INT const_val
= INTVAL (op1
);
1737 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1738 unsigned HOST_WIDE_INT max_val
1739 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1744 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1745 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1748 /* When cross-compiling, const_val might be sign-extended from
1749 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1751 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1752 != (((HOST_WIDE_INT
) 1
1753 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1754 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1758 if (uconst_val
< max_val
)
1759 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1763 if (uconst_val
!= 0)
1764 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1772 if (op0
!= XEXP (cond
, 0)
1773 || op1
!= XEXP (cond
, 1)
1774 || code
!= GET_CODE (cond
)
1775 || GET_MODE (cond
) != SImode
)
1776 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1781 /* Reverses CONDition; returns NULL if we cannot. */
1784 reversed_condition (rtx cond
)
1786 enum rtx_code reversed
;
1787 reversed
= reversed_comparison_code (cond
, NULL
);
1788 if (reversed
== UNKNOWN
)
1791 return gen_rtx_fmt_ee (reversed
,
1792 GET_MODE (cond
), XEXP (cond
, 0),
1796 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1797 set of altered regs. */
1800 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1802 rtx rev
, reve
, exp
= *expr
;
1804 /* If some register gets altered later, we do not really speak about its
1805 value at the time of comparison. */
1806 if (altered
&& altered_reg_used (cond
, altered
))
1809 if (GET_CODE (cond
) == EQ
1810 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1812 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1816 if (!COMPARISON_P (exp
))
1819 rev
= reversed_condition (cond
);
1820 reve
= reversed_condition (exp
);
1822 cond
= canon_condition (cond
);
1823 exp
= canon_condition (exp
);
1825 rev
= canon_condition (rev
);
1827 reve
= canon_condition (reve
);
1829 if (rtx_equal_p (exp
, cond
))
1831 *expr
= const_true_rtx
;
1835 if (rev
&& rtx_equal_p (exp
, rev
))
1841 if (implies_p (cond
, exp
))
1843 *expr
= const_true_rtx
;
1847 if (reve
&& implies_p (cond
, reve
))
1853 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1855 if (rev
&& implies_p (exp
, rev
))
1861 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1862 if (rev
&& reve
&& implies_p (reve
, rev
))
1864 *expr
= const_true_rtx
;
1868 /* We would like to have some other tests here. TODO. */
1873 /* Use relationship between A and *B to eventually eliminate *B.
1874 OP is the operation we consider. */
1877 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1882 /* If A implies *B, we may replace *B by true. */
1883 if (implies_p (a
, *b
))
1884 *b
= const_true_rtx
;
1888 /* If *B implies A, we may replace *B by false. */
1889 if (implies_p (*b
, a
))
1898 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1899 operation we consider. */
1902 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1906 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1907 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1908 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1909 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1912 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1913 is a list, its elements are assumed to be combined using OP. */
1916 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1918 bool expression_valid
;
1919 rtx head
, tail
, last_valid_expr
;
1920 rtx_expr_list
*cond_list
;
1923 regset altered
, this_altered
;
1929 if (CONSTANT_P (*expr
))
1932 if (GET_CODE (*expr
) == EXPR_LIST
)
1934 head
= XEXP (*expr
, 0);
1935 tail
= XEXP (*expr
, 1);
1937 eliminate_implied_conditions (op
, &head
, tail
);
1942 neutral
= const_true_rtx
;
1947 neutral
= const0_rtx
;
1948 aggr
= const_true_rtx
;
1955 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1958 XEXP (*expr
, 0) = aggr
;
1959 XEXP (*expr
, 1) = NULL_RTX
;
1962 else if (head
== neutral
)
1965 simplify_using_initial_values (loop
, op
, expr
);
1968 simplify_using_initial_values (loop
, op
, &tail
);
1970 if (tail
&& XEXP (tail
, 0) == aggr
)
1976 XEXP (*expr
, 0) = head
;
1977 XEXP (*expr
, 1) = tail
;
1981 gcc_assert (op
== UNKNOWN
);
1983 replace_single_def_regs (expr
);
1984 if (CONSTANT_P (*expr
))
1987 e
= loop_preheader_edge (loop
);
1988 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1991 altered
= ALLOC_REG_SET (®_obstack
);
1992 this_altered
= ALLOC_REG_SET (®_obstack
);
1994 expression_valid
= true;
1995 last_valid_expr
= *expr
;
1999 insn
= BB_END (e
->src
);
2000 if (any_condjump_p (insn
))
2002 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
2004 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
2005 cond
= reversed_condition (cond
);
2009 simplify_using_condition (cond
, expr
, altered
);
2013 if (CONSTANT_P (*expr
))
2015 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
2017 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2018 if (CONSTANT_P (*expr
))
2022 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
2026 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
2034 CLEAR_REG_SET (this_altered
);
2035 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
2038 /* Kill all call clobbered registers. */
2040 hard_reg_set_iterator hrsi
;
2041 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2043 SET_REGNO_REG_SET (this_altered
, i
);
2046 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2048 rtx_expr_list
**pnote
, **pnote_next
;
2050 replace_in_expr (expr
, dest
, src
);
2051 if (CONSTANT_P (*expr
))
2054 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2057 rtx old_cond
= XEXP (note
, 0);
2059 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2060 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2062 /* We can no longer use a condition that has been simplified
2063 to a constant, and simplify_using_condition will abort if
2065 if (CONSTANT_P (XEXP (note
, 0)))
2067 *pnote
= *pnote_next
;
2069 free_EXPR_LIST_node (note
);
2071 /* Retry simplifications with this condition if either the
2072 expression or the condition changed. */
2073 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2074 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2079 rtx_expr_list
**pnote
, **pnote_next
;
2081 /* If we did not use this insn to make a replacement, any overlap
2082 between stores in this insn and our expression will cause the
2083 expression to become invalid. */
2084 if (altered_reg_used (*expr
, this_altered
))
2087 /* Likewise for the conditions. */
2088 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2091 rtx old_cond
= XEXP (note
, 0);
2093 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2094 if (altered_reg_used (old_cond
, this_altered
))
2096 *pnote
= *pnote_next
;
2098 free_EXPR_LIST_node (note
);
2103 if (CONSTANT_P (*expr
))
2106 IOR_REG_SET (altered
, this_altered
);
2108 /* If the expression now contains regs that have been altered, we
2109 can't return it to the caller. However, it is still valid for
2110 further simplification, so keep searching to see if we can
2111 eventually turn it into a constant. */
2112 if (altered_reg_used (*expr
, altered
))
2113 expression_valid
= false;
2114 if (expression_valid
)
2115 last_valid_expr
= *expr
;
2118 if (!single_pred_p (e
->src
)
2119 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2121 e
= single_pred_edge (e
->src
);
2125 free_EXPR_LIST_list (&cond_list
);
2126 if (!CONSTANT_P (*expr
))
2127 *expr
= last_valid_expr
;
2128 FREE_REG_SET (altered
);
2129 FREE_REG_SET (this_altered
);
2132 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2133 that IV occurs as left operands of comparison COND and its signedness
2134 is SIGNED_P to DESC. */
2137 shorten_into_mode (struct rtx_iv
*iv
, machine_mode mode
,
2138 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2140 rtx mmin
, mmax
, cond_over
, cond_under
;
2142 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2143 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2145 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2154 if (cond_under
!= const0_rtx
)
2156 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2157 if (cond_over
!= const0_rtx
)
2158 desc
->noloop_assumptions
=
2159 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2166 if (cond_over
!= const0_rtx
)
2168 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2169 if (cond_under
!= const0_rtx
)
2170 desc
->noloop_assumptions
=
2171 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2175 if (cond_over
!= const0_rtx
)
2177 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2178 if (cond_under
!= const0_rtx
)
2180 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2188 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2191 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2192 subregs of the same mode if possible (sometimes it is necessary to add
2193 some assumptions to DESC). */
2196 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2197 enum rtx_code cond
, struct niter_desc
*desc
)
2199 machine_mode comp_mode
;
2202 /* If the ivs behave specially in the first iteration, or are
2203 added/multiplied after extending, we ignore them. */
2204 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2206 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2209 /* If there is some extend, it must match signedness of the comparison. */
2214 if (iv0
->extend
== IV_ZERO_EXTEND
2215 || iv1
->extend
== IV_ZERO_EXTEND
)
2222 if (iv0
->extend
== IV_SIGN_EXTEND
2223 || iv1
->extend
== IV_SIGN_EXTEND
)
2229 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2230 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2231 && iv0
->extend
!= iv1
->extend
)
2235 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2236 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2237 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2238 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2245 /* Values of both variables should be computed in the same mode. These
2246 might indeed be different, if we have comparison like
2248 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2250 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2251 in different modes. This does not seem impossible to handle, but
2252 it hardly ever occurs in practice.
2254 The only exception is the case when one of operands is invariant.
2255 For example pentium 3 generates comparisons like
2256 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2257 definitely do not want this prevent the optimization. */
2258 comp_mode
= iv0
->extend_mode
;
2259 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2260 comp_mode
= iv1
->extend_mode
;
2262 if (iv0
->extend_mode
!= comp_mode
)
2264 if (iv0
->mode
!= iv0
->extend_mode
2265 || iv0
->step
!= const0_rtx
)
2268 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2269 comp_mode
, iv0
->base
, iv0
->mode
);
2270 iv0
->extend_mode
= comp_mode
;
2273 if (iv1
->extend_mode
!= comp_mode
)
2275 if (iv1
->mode
!= iv1
->extend_mode
2276 || iv1
->step
!= const0_rtx
)
2279 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2280 comp_mode
, iv1
->base
, iv1
->mode
);
2281 iv1
->extend_mode
= comp_mode
;
2284 /* Check that both ivs belong to a range of a single mode. If one of the
2285 operands is an invariant, we may need to shorten it into the common
2287 if (iv0
->mode
== iv0
->extend_mode
2288 && iv0
->step
== const0_rtx
2289 && iv0
->mode
!= iv1
->mode
)
2290 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2292 if (iv1
->mode
== iv1
->extend_mode
2293 && iv1
->step
== const0_rtx
2294 && iv0
->mode
!= iv1
->mode
)
2295 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2297 if (iv0
->mode
!= iv1
->mode
)
2300 desc
->mode
= iv0
->mode
;
2301 desc
->signed_p
= signed_p
;
2306 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2307 result. This function is called from iv_number_of_iterations with
2308 a number of fields in DESC already filled in. OLD_NITER is the original
2309 expression for the number of iterations, before we tried to simplify it. */
2312 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2314 rtx niter
= desc
->niter_expr
;
2315 rtx mmin
, mmax
, cmp
;
2317 uint64_t andmax
= 0;
2319 /* We used to look for constant operand 0 of AND,
2320 but canonicalization should always make this impossible. */
2321 gcc_checking_assert (GET_CODE (niter
) != AND
2322 || !CONST_INT_P (XEXP (niter
, 0)));
2324 if (GET_CODE (niter
) == AND
2325 && CONST_INT_P (XEXP (niter
, 1)))
2327 andmax
= UINTVAL (XEXP (niter
, 1));
2328 niter
= XEXP (niter
, 0);
2331 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2332 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2334 if (GET_CODE (niter
) == UDIV
)
2336 if (!CONST_INT_P (XEXP (niter
, 1)))
2338 inc
= INTVAL (XEXP (niter
, 1));
2339 niter
= XEXP (niter
, 0);
2344 /* We could use a binary search here, but for now improving the upper
2345 bound by just one eliminates one important corner case. */
2346 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2347 desc
->mode
, old_niter
, mmax
);
2348 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2349 if (cmp
== const_true_rtx
)
2354 fprintf (dump_file
, ";; improved upper bound by one.\n");
2358 nmax
= MIN (nmax
, andmax
);
2360 fprintf (dump_file
, ";; Determined upper bound %"PRId64
".\n",
2365 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2366 the result into DESC. Very similar to determine_number_of_iterations
2367 (basically its rtl version), complicated by things like subregs. */
2370 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2371 struct niter_desc
*desc
)
2373 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2374 struct rtx_iv iv0
, iv1
, tmp_iv
;
2375 rtx assumption
, may_not_xform
;
2377 machine_mode mode
, comp_mode
;
2378 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2379 uint64_t s
, size
, d
, inv
, max
;
2380 int64_t up
, down
, inc
, step_val
;
2381 int was_sharp
= false;
2385 /* The meaning of these assumptions is this:
2387 then the rest of information does not have to be valid
2388 if noloop_assumptions then the loop does not roll
2389 if infinite then this exit is never used */
2391 desc
->assumptions
= NULL_RTX
;
2392 desc
->noloop_assumptions
= NULL_RTX
;
2393 desc
->infinite
= NULL_RTX
;
2394 desc
->simple_p
= true;
2396 desc
->const_iter
= false;
2397 desc
->niter_expr
= NULL_RTX
;
2399 cond
= GET_CODE (condition
);
2400 gcc_assert (COMPARISON_P (condition
));
2402 mode
= GET_MODE (XEXP (condition
, 0));
2403 if (mode
== VOIDmode
)
2404 mode
= GET_MODE (XEXP (condition
, 1));
2405 /* The constant comparisons should be folded. */
2406 gcc_assert (mode
!= VOIDmode
);
2408 /* We only handle integers or pointers. */
2409 if (GET_MODE_CLASS (mode
) != MODE_INT
2410 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2413 op0
= XEXP (condition
, 0);
2414 if (!iv_analyze (insn
, op0
, &iv0
))
2416 if (iv0
.extend_mode
== VOIDmode
)
2417 iv0
.mode
= iv0
.extend_mode
= mode
;
2419 op1
= XEXP (condition
, 1);
2420 if (!iv_analyze (insn
, op1
, &iv1
))
2422 if (iv1
.extend_mode
== VOIDmode
)
2423 iv1
.mode
= iv1
.extend_mode
= mode
;
2425 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2426 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2429 /* Check condition and normalize it. */
2437 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2438 cond
= swap_condition (cond
);
2450 /* Handle extends. This is relatively nontrivial, so we only try in some
2451 easy cases, when we can canonicalize the ivs (possibly by adding some
2452 assumptions) to shape subreg (base + i * step). This function also fills
2453 in desc->mode and desc->signed_p. */
2455 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2458 comp_mode
= iv0
.extend_mode
;
2460 size
= GET_MODE_PRECISION (mode
);
2461 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2462 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2463 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2465 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2468 /* We can take care of the case of two induction variables chasing each other
2469 if the test is NE. I have never seen a loop using it, but still it is
2471 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2476 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2477 iv1
.step
= const0_rtx
;
2480 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2481 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2483 /* This is either infinite loop or the one that ends immediately, depending
2484 on initial values. Unswitching should remove this kind of conditions. */
2485 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2490 if (iv0
.step
== const0_rtx
)
2491 step_val
= -INTVAL (iv1
.step
);
2493 step_val
= INTVAL (iv0
.step
);
2495 /* Ignore loops of while (i-- < 10) type. */
2499 step_is_pow2
= !(step_val
& (step_val
- 1));
2503 /* We do not care about whether the step is power of two in this
2505 step_is_pow2
= false;
2509 /* Some more condition normalization. We must record some assumptions
2510 due to overflows. */
2515 /* We want to take care only of non-sharp relationals; this is easy,
2516 as in cases the overflow would make the transformation unsafe
2517 the loop does not roll. Seemingly it would make more sense to want
2518 to take care of sharp relationals instead, as NE is more similar to
2519 them, but the problem is that here the transformation would be more
2520 difficult due to possibly infinite loops. */
2521 if (iv0
.step
== const0_rtx
)
2523 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2524 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2526 if (assumption
== const_true_rtx
)
2527 goto zero_iter_simplify
;
2528 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2529 iv0
.base
, const1_rtx
);
2533 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2534 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2536 if (assumption
== const_true_rtx
)
2537 goto zero_iter_simplify
;
2538 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2539 iv1
.base
, constm1_rtx
);
2542 if (assumption
!= const0_rtx
)
2543 desc
->noloop_assumptions
=
2544 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2545 cond
= (cond
== LT
) ? LE
: LEU
;
2547 /* It will be useful to be able to tell the difference once more in
2548 LE -> NE reduction. */
2554 /* Take care of trivially infinite loops. */
2557 if (iv0
.step
== const0_rtx
)
2559 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2560 if (rtx_equal_p (tmp
, mode_mmin
))
2563 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2564 /* Fill in the remaining fields somehow. */
2565 goto zero_iter_simplify
;
2570 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2571 if (rtx_equal_p (tmp
, mode_mmax
))
2574 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2575 /* Fill in the remaining fields somehow. */
2576 goto zero_iter_simplify
;
2581 /* If we can we want to take care of NE conditions instead of size
2582 comparisons, as they are much more friendly (most importantly
2583 this takes care of special handling of loops with step 1). We can
2584 do it if we first check that upper bound is greater or equal to
2585 lower bound, their difference is constant c modulo step and that
2586 there is not an overflow. */
2589 if (iv0
.step
== const0_rtx
)
2590 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2593 step
= lowpart_subreg (mode
, step
, comp_mode
);
2594 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2595 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2596 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2597 may_xform
= const0_rtx
;
2598 may_not_xform
= const_true_rtx
;
2600 if (CONST_INT_P (delta
))
2602 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2604 /* A special case. We have transformed condition of type
2605 for (i = 0; i < 4; i += 4)
2607 for (i = 0; i <= 3; i += 4)
2608 obviously if the test for overflow during that transformation
2609 passed, we cannot overflow here. Most importantly any
2610 loop with sharp end condition and step 1 falls into this
2611 category, so handling this case specially is definitely
2612 worth the troubles. */
2613 may_xform
= const_true_rtx
;
2615 else if (iv0
.step
== const0_rtx
)
2617 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2618 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2619 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2620 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2621 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2623 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2629 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2630 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2631 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2632 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2633 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2635 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2641 if (may_xform
!= const0_rtx
)
2643 /* We perform the transformation always provided that it is not
2644 completely senseless. This is OK, as we would need this assumption
2645 to determine the number of iterations anyway. */
2646 if (may_xform
!= const_true_rtx
)
2648 /* If the step is a power of two and the final value we have
2649 computed overflows, the cycle is infinite. Otherwise it
2650 is nontrivial to compute the number of iterations. */
2652 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2655 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2659 /* We are going to lose some information about upper bound on
2660 number of iterations in this step, so record the information
2662 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2663 if (CONST_INT_P (iv1
.base
))
2664 up
= INTVAL (iv1
.base
);
2666 up
= INTVAL (mode_mmax
) - inc
;
2667 down
= INTVAL (CONST_INT_P (iv0
.base
)
2670 max
= (uint64_t) (up
- down
) / inc
+ 1;
2672 && !desc
->assumptions
)
2673 record_niter_bound (loop
, max
, false, true);
2675 if (iv0
.step
== const0_rtx
)
2677 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2678 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2682 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2683 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2686 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2687 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2688 assumption
= simplify_gen_relational (reverse_condition (cond
),
2689 SImode
, mode
, tmp0
, tmp1
);
2690 if (assumption
== const_true_rtx
)
2691 goto zero_iter_simplify
;
2692 else if (assumption
!= const0_rtx
)
2693 desc
->noloop_assumptions
=
2694 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2699 /* Count the number of iterations. */
2702 /* Everything we do here is just arithmetics modulo size of mode. This
2703 makes us able to do more involved computations of number of iterations
2704 than in other cases. First transform the condition into shape
2705 s * i <> c, with s positive. */
2706 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2707 iv0
.base
= const0_rtx
;
2708 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2709 iv1
.step
= const0_rtx
;
2710 if (INTVAL (iv0
.step
) < 0)
2712 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2713 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2715 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2717 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2718 is infinite. Otherwise, the number of iterations is
2719 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2720 s
= INTVAL (iv0
.step
); d
= 1;
2727 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2729 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2730 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2731 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2732 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2734 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2735 inv
= inverse (s
, size
);
2736 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2737 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2741 if (iv1
.step
== const0_rtx
)
2742 /* Condition in shape a + s * i <= b
2743 We must know that b + s does not overflow and a <= b + s and then we
2744 can compute number of iterations as (b + s - a) / s. (It might
2745 seem that we in fact could be more clever about testing the b + s
2746 overflow condition using some information about b - a mod s,
2747 but it was already taken into account during LE -> NE transform). */
2750 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2751 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2753 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2754 lowpart_subreg (mode
, step
,
2760 /* If s is power of 2, we know that the loop is infinite if
2761 a % s <= b % s and b + s overflows. */
2762 assumption
= simplify_gen_relational (reverse_condition (cond
),
2766 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2767 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2768 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2769 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2771 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2775 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2778 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2781 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2782 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2783 assumption
= simplify_gen_relational (reverse_condition (cond
),
2784 SImode
, mode
, tmp0
, tmp
);
2786 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2787 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2791 /* Condition in shape a <= b - s * i
2792 We must know that a - s does not overflow and a - s <= b and then
2793 we can again compute number of iterations as (b - (a - s)) / s. */
2794 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2795 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2796 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2798 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2799 lowpart_subreg (mode
, step
, comp_mode
));
2804 /* If s is power of 2, we know that the loop is infinite if
2805 a % s <= b % s and a - s overflows. */
2806 assumption
= simplify_gen_relational (reverse_condition (cond
),
2810 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2811 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2812 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2813 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2815 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2819 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2822 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2825 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2826 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2827 assumption
= simplify_gen_relational (reverse_condition (cond
),
2830 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2831 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2833 if (assumption
== const_true_rtx
)
2834 goto zero_iter_simplify
;
2835 else if (assumption
!= const0_rtx
)
2836 desc
->noloop_assumptions
=
2837 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2838 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2839 desc
->niter_expr
= delta
;
2842 old_niter
= desc
->niter_expr
;
2844 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2845 if (desc
->assumptions
2846 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2848 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2849 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2850 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2852 /* Rerun the simplification. Consider code (created by copying loop headers)
2864 The first pass determines that i = 0, the second pass uses it to eliminate
2865 noloop assumption. */
2867 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2868 if (desc
->assumptions
2869 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2871 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2872 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2873 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2875 if (desc
->noloop_assumptions
2876 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2879 if (CONST_INT_P (desc
->niter_expr
))
2881 uint64_t val
= INTVAL (desc
->niter_expr
);
2883 desc
->const_iter
= true;
2884 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2886 && !desc
->assumptions
)
2887 record_niter_bound (loop
, desc
->niter
, false, true);
2891 max
= determine_max_iter (loop
, desc
, old_niter
);
2893 goto zero_iter_simplify
;
2895 && !desc
->assumptions
)
2896 record_niter_bound (loop
, max
, false, true);
2898 /* simplify_using_initial_values does a copy propagation on the registers
2899 in the expression for the number of iterations. This prolongs life
2900 ranges of registers and increases register pressure, and usually
2901 brings no gain (and if it happens to do, the cse pass will take care
2902 of it anyway). So prevent this behavior, unless it enabled us to
2903 derive that the number of iterations is a constant. */
2904 desc
->niter_expr
= old_niter
;
2910 /* Simplify the assumptions. */
2911 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2912 if (desc
->assumptions
2913 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2915 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2919 desc
->const_iter
= true;
2921 record_niter_bound (loop
, 0, true, true);
2922 desc
->noloop_assumptions
= NULL_RTX
;
2923 desc
->niter_expr
= const0_rtx
;
2927 desc
->simple_p
= false;
2931 /* Checks whether E is a simple exit from LOOP and stores its description
2935 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2937 basic_block exit_bb
;
2943 desc
->simple_p
= false;
2945 /* It must belong directly to the loop. */
2946 if (exit_bb
->loop_father
!= loop
)
2949 /* It must be tested (at least) once during any iteration. */
2950 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2953 /* It must end in a simple conditional jump. */
2954 if (!any_condjump_p (BB_END (exit_bb
)))
2957 ein
= EDGE_SUCC (exit_bb
, 0);
2959 ein
= EDGE_SUCC (exit_bb
, 1);
2962 desc
->in_edge
= ein
;
2964 /* Test whether the condition is suitable. */
2965 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2968 if (ein
->flags
& EDGE_FALLTHRU
)
2970 condition
= reversed_condition (condition
);
2975 /* Check that we are able to determine number of iterations and fill
2976 in information about it. */
2977 iv_number_of_iterations (loop
, at
, condition
, desc
);
2980 /* Finds a simple exit of LOOP and stores its description into DESC. */
2983 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2988 struct niter_desc act
;
2992 desc
->simple_p
= false;
2993 body
= get_loop_body (loop
);
2995 for (i
= 0; i
< loop
->num_nodes
; i
++)
2997 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2999 if (flow_bb_inside_loop_p (loop
, e
->dest
))
3002 check_simple_exit (loop
, e
, &act
);
3010 /* Prefer constant iterations; the less the better. */
3012 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
3015 /* Also if the actual exit may be infinite, while the old one
3016 not, prefer the old one. */
3017 if (act
.infinite
&& !desc
->infinite
)
3029 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
3030 fprintf (dump_file
, " simple exit %d -> %d\n",
3031 desc
->out_edge
->src
->index
,
3032 desc
->out_edge
->dest
->index
);
3033 if (desc
->assumptions
)
3035 fprintf (dump_file
, " assumptions: ");
3036 print_rtl (dump_file
, desc
->assumptions
);
3037 fprintf (dump_file
, "\n");
3039 if (desc
->noloop_assumptions
)
3041 fprintf (dump_file
, " does not roll if: ");
3042 print_rtl (dump_file
, desc
->noloop_assumptions
);
3043 fprintf (dump_file
, "\n");
3047 fprintf (dump_file
, " infinite if: ");
3048 print_rtl (dump_file
, desc
->infinite
);
3049 fprintf (dump_file
, "\n");
3052 fprintf (dump_file
, " number of iterations: ");
3053 print_rtl (dump_file
, desc
->niter_expr
);
3054 fprintf (dump_file
, "\n");
3056 fprintf (dump_file
, " upper bound: %li\n",
3057 (long)get_max_loop_iterations_int (loop
));
3058 fprintf (dump_file
, " realistic bound: %li\n",
3059 (long)get_estimated_loop_iterations_int (loop
));
3062 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3068 /* Creates a simple loop description of LOOP if it was not computed
3072 get_simple_loop_desc (struct loop
*loop
)
3074 struct niter_desc
*desc
= simple_loop_desc (loop
);
3079 /* At least desc->infinite is not always initialized by
3080 find_simple_loop_exit. */
3081 desc
= ggc_cleared_alloc
<niter_desc
> ();
3082 iv_analysis_loop_init (loop
);
3083 find_simple_exit (loop
, desc
);
3084 loop
->simple_loop_desc
= desc
;
3086 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3088 const char *wording
;
3090 /* Assume that no overflow happens and that the loop is finite.
3091 We already warned at the tree level if we ran optimizations there. */
3092 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3097 flag_unsafe_loop_optimizations
3098 ? N_("assuming that the loop is not infinite")
3099 : N_("cannot optimize possibly infinite loops");
3100 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3103 if (desc
->assumptions
)
3106 flag_unsafe_loop_optimizations
3107 ? N_("assuming that the loop counter does not overflow")
3108 : N_("cannot optimize loop, the loop counter may overflow");
3109 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3114 if (flag_unsafe_loop_optimizations
)
3116 desc
->assumptions
= NULL_RTX
;
3117 desc
->infinite
= NULL_RTX
;
3124 /* Releases simple loop description for LOOP. */
3127 free_simple_loop_desc (struct loop
*loop
)
3129 struct niter_desc
*desc
= simple_loop_desc (loop
);
3135 loop
->simple_loop_desc
= NULL
;