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"
61 #include "insn-config.h"
71 #include "diagnostic-core.h"
75 /* Possible return values of iv_get_reaching_def. */
79 /* More than one reaching def, or reaching def that does not
83 /* The use is trivial invariant of the loop, i.e. is not changed
87 /* The use is reached by initial value and a value from the
88 previous iteration. */
91 /* The use has single dominating def. */
95 /* Information about a biv. */
99 unsigned regno
; /* The register of the biv. */
100 struct rtx_iv iv
; /* Value of the biv. */
103 static bool clean_slate
= true;
105 static unsigned int iv_ref_table_size
= 0;
107 /* Table of rtx_ivs indexed by the df_ref uid field. */
108 static struct rtx_iv
** iv_ref_table
;
110 /* Induction variable stored at the reference. */
111 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
112 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
114 /* The current loop. */
116 static struct loop
*current_loop
;
118 /* Hashtable helper. */
120 struct biv_entry_hasher
: free_ptr_hash
<biv_entry
>
122 typedef rtx_def
*compare_type
;
123 static inline hashval_t
hash (const biv_entry
*);
124 static inline bool equal (const biv_entry
*, const rtx_def
*);
127 /* Returns hash value for biv B. */
130 biv_entry_hasher::hash (const biv_entry
*b
)
135 /* Compares biv B and register R. */
138 biv_entry_hasher::equal (const biv_entry
*b
, const rtx_def
*r
)
140 return b
->regno
== REGNO (r
);
143 /* Bivs of the current loop. */
145 static hash_table
<biv_entry_hasher
> *bivs
;
147 static bool iv_analyze_op (rtx_insn
*, rtx
, struct rtx_iv
*);
149 /* Return the RTX code corresponding to the IV extend code EXTEND. */
150 static inline enum rtx_code
151 iv_extend_to_rtx_code (enum iv_extend_code extend
)
159 case IV_UNKNOWN_EXTEND
:
165 /* Dumps information about IV to FILE. */
167 extern void dump_iv_info (FILE *, struct rtx_iv
*);
169 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
173 fprintf (file
, "not simple");
177 if (iv
->step
== const0_rtx
178 && !iv
->first_special
)
179 fprintf (file
, "invariant ");
181 print_rtl (file
, iv
->base
);
182 if (iv
->step
!= const0_rtx
)
184 fprintf (file
, " + ");
185 print_rtl (file
, iv
->step
);
186 fprintf (file
, " * iteration");
188 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
190 if (iv
->mode
!= iv
->extend_mode
)
191 fprintf (file
, " %s to %s",
192 rtx_name
[iv_extend_to_rtx_code (iv
->extend
)],
193 GET_MODE_NAME (iv
->extend_mode
));
195 if (iv
->mult
!= const1_rtx
)
197 fprintf (file
, " * ");
198 print_rtl (file
, iv
->mult
);
200 if (iv
->delta
!= const0_rtx
)
202 fprintf (file
, " + ");
203 print_rtl (file
, iv
->delta
);
205 if (iv
->first_special
)
206 fprintf (file
, " (first special)");
209 /* Generates a subreg to get the least significant part of EXPR (in mode
210 INNER_MODE) to OUTER_MODE. */
213 lowpart_subreg (machine_mode outer_mode
, rtx expr
,
214 machine_mode inner_mode
)
216 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
217 subreg_lowpart_offset (outer_mode
, inner_mode
));
221 check_iv_ref_table_size (void)
223 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
225 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
226 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
227 memset (&iv_ref_table
[iv_ref_table_size
], 0,
228 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
229 iv_ref_table_size
= new_size
;
234 /* Checks whether REG is a well-behaved register. */
237 simple_reg_p (rtx reg
)
241 if (GET_CODE (reg
) == SUBREG
)
243 if (!subreg_lowpart_p (reg
))
245 reg
= SUBREG_REG (reg
);
252 if (HARD_REGISTER_NUM_P (r
))
255 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
261 /* Clears the information about ivs stored in df. */
266 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
269 check_iv_ref_table_size ();
270 for (i
= 0; i
< n_defs
; i
++)
272 iv
= iv_ref_table
[i
];
276 iv_ref_table
[i
] = NULL
;
284 /* Prepare the data for an induction variable analysis of a LOOP. */
287 iv_analysis_loop_init (struct loop
*loop
)
291 /* Clear the information from the analysis of the previous loop. */
294 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
295 bivs
= new hash_table
<biv_entry_hasher
> (10);
301 /* Get rid of the ud chains before processing the rescans. Then add
303 df_remove_problem (df_chain
);
304 df_process_deferred_rescans ();
305 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
306 df_chain_add_problem (DF_UD_CHAIN
);
307 df_note_add_problem ();
308 df_analyze_loop (loop
);
310 df_dump_region (dump_file
);
312 check_iv_ref_table_size ();
315 /* Finds the definition of REG that dominates loop latch and stores
316 it to DEF. Returns false if there is not a single definition
317 dominating the latch. If REG has no definition in loop, DEF
318 is set to NULL and true is returned. */
321 latch_dominating_def (rtx reg
, df_ref
*def
)
323 df_ref single_rd
= NULL
, adef
;
324 unsigned regno
= REGNO (reg
);
325 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
327 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
329 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
330 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
333 /* More than one reaching definition. */
337 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
347 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
349 static enum iv_grd_result
350 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
353 basic_block def_bb
, use_bb
;
358 if (!simple_reg_p (reg
))
360 if (GET_CODE (reg
) == SUBREG
)
361 reg
= SUBREG_REG (reg
);
362 gcc_assert (REG_P (reg
));
364 use
= df_find_use (insn
, reg
);
365 gcc_assert (use
!= NULL
);
367 if (!DF_REF_CHAIN (use
))
368 return GRD_INVARIANT
;
370 /* More than one reaching def. */
371 if (DF_REF_CHAIN (use
)->next
)
374 adef
= DF_REF_CHAIN (use
)->ref
;
376 /* We do not handle setting only part of the register. */
377 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
380 def_insn
= DF_REF_INSN (adef
);
381 def_bb
= DF_REF_BB (adef
);
382 use_bb
= BLOCK_FOR_INSN (insn
);
384 if (use_bb
== def_bb
)
385 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
387 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
392 return GRD_SINGLE_DOM
;
395 /* The definition does not dominate the use. This is still OK if
396 this may be a use of a biv, i.e. if the def_bb dominates loop
398 if (just_once_each_iteration_p (current_loop
, def_bb
))
399 return GRD_MAYBE_BIV
;
404 /* Sets IV to invariant CST in MODE. Always returns true (just for
405 consistency with other iv manipulation functions that may fail). */
408 iv_constant (struct rtx_iv
*iv
, rtx cst
, machine_mode mode
)
410 if (mode
== VOIDmode
)
411 mode
= GET_MODE (cst
);
415 iv
->step
= const0_rtx
;
416 iv
->first_special
= false;
417 iv
->extend
= IV_UNKNOWN_EXTEND
;
418 iv
->extend_mode
= iv
->mode
;
419 iv
->delta
= const0_rtx
;
420 iv
->mult
= const1_rtx
;
425 /* Evaluates application of subreg to MODE on IV. */
428 iv_subreg (struct rtx_iv
*iv
, machine_mode mode
)
430 /* If iv is invariant, just calculate the new value. */
431 if (iv
->step
== const0_rtx
432 && !iv
->first_special
)
434 rtx val
= get_iv_value (iv
, const0_rtx
);
435 val
= lowpart_subreg (mode
, val
,
436 iv
->extend
== IV_UNKNOWN_EXTEND
437 ? iv
->mode
: iv
->extend_mode
);
440 iv
->extend
= IV_UNKNOWN_EXTEND
;
441 iv
->mode
= iv
->extend_mode
= mode
;
442 iv
->delta
= const0_rtx
;
443 iv
->mult
= const1_rtx
;
447 if (iv
->extend_mode
== mode
)
450 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
453 iv
->extend
= IV_UNKNOWN_EXTEND
;
456 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
457 simplify_gen_binary (MULT
, iv
->extend_mode
,
458 iv
->base
, iv
->mult
));
459 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
460 iv
->mult
= const1_rtx
;
461 iv
->delta
= const0_rtx
;
462 iv
->first_special
= false;
467 /* Evaluates application of EXTEND to MODE on IV. */
470 iv_extend (struct rtx_iv
*iv
, enum iv_extend_code extend
, machine_mode mode
)
472 /* If iv is invariant, just calculate the new value. */
473 if (iv
->step
== const0_rtx
474 && !iv
->first_special
)
476 rtx val
= get_iv_value (iv
, const0_rtx
);
477 if (iv
->extend_mode
!= iv
->mode
478 && iv
->extend
!= IV_UNKNOWN_EXTEND
479 && iv
->extend
!= extend
)
480 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
481 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
484 ? iv
->extend_mode
: iv
->mode
);
486 iv
->extend
= IV_UNKNOWN_EXTEND
;
487 iv
->mode
= iv
->extend_mode
= mode
;
488 iv
->delta
= const0_rtx
;
489 iv
->mult
= const1_rtx
;
493 if (mode
!= iv
->extend_mode
)
496 if (iv
->extend
!= IV_UNKNOWN_EXTEND
497 && iv
->extend
!= extend
)
505 /* Evaluates negation of IV. */
508 iv_neg (struct rtx_iv
*iv
)
510 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
512 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
513 iv
->base
, iv
->extend_mode
);
514 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
515 iv
->step
, iv
->extend_mode
);
519 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
520 iv
->delta
, iv
->extend_mode
);
521 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
522 iv
->mult
, iv
->extend_mode
);
528 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
531 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
536 /* Extend the constant to extend_mode of the other operand if necessary. */
537 if (iv0
->extend
== IV_UNKNOWN_EXTEND
538 && iv0
->mode
== iv0
->extend_mode
539 && iv0
->step
== const0_rtx
540 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
542 iv0
->extend_mode
= iv1
->extend_mode
;
543 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
544 iv0
->base
, iv0
->mode
);
546 if (iv1
->extend
== IV_UNKNOWN_EXTEND
547 && iv1
->mode
== iv1
->extend_mode
548 && iv1
->step
== const0_rtx
549 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
551 iv1
->extend_mode
= iv0
->extend_mode
;
552 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
553 iv1
->base
, iv1
->mode
);
556 mode
= iv0
->extend_mode
;
557 if (mode
!= iv1
->extend_mode
)
560 if (iv0
->extend
== IV_UNKNOWN_EXTEND
561 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
563 if (iv0
->mode
!= iv1
->mode
)
566 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
567 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
572 /* Handle addition of constant. */
573 if (iv1
->extend
== IV_UNKNOWN_EXTEND
575 && iv1
->step
== const0_rtx
)
577 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
581 if (iv0
->extend
== IV_UNKNOWN_EXTEND
583 && iv0
->step
== const0_rtx
)
591 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
598 /* Evaluates multiplication of IV by constant CST. */
601 iv_mult (struct rtx_iv
*iv
, rtx mby
)
603 machine_mode mode
= iv
->extend_mode
;
605 if (GET_MODE (mby
) != VOIDmode
606 && GET_MODE (mby
) != mode
)
609 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
611 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
612 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
616 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
617 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
623 /* Evaluates shift of IV by constant CST. */
626 iv_shift (struct rtx_iv
*iv
, rtx mby
)
628 machine_mode mode
= iv
->extend_mode
;
630 if (GET_MODE (mby
) != VOIDmode
631 && GET_MODE (mby
) != mode
)
634 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
636 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
637 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
641 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
642 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
648 /* The recursive part of get_biv_step. Gets the value of the single value
649 defined by DEF wrto initial value of REG inside loop, in shape described
653 get_biv_step_1 (df_ref def
, rtx reg
,
654 rtx
*inner_step
, machine_mode
*inner_mode
,
655 enum iv_extend_code
*extend
, machine_mode outer_mode
,
658 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
661 rtx_insn
*insn
= DF_REF_INSN (def
);
663 enum iv_grd_result res
;
665 set
= single_set (insn
);
669 rhs
= find_reg_equal_equiv_note (insn
);
675 code
= GET_CODE (rhs
);
688 if (code
== PLUS
&& CONSTANT_P (op0
))
689 std::swap (op0
, op1
);
691 if (!simple_reg_p (op0
)
692 || !CONSTANT_P (op1
))
695 if (GET_MODE (rhs
) != outer_mode
)
697 /* ppc64 uses expressions like
699 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
701 this is equivalent to
703 (set x':DI (plus:DI y:DI 1))
704 (set x:SI (subreg:SI (x':DI)). */
705 if (GET_CODE (op0
) != SUBREG
)
707 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
716 if (GET_MODE (rhs
) != outer_mode
)
720 if (!simple_reg_p (op0
))
730 if (GET_CODE (next
) == SUBREG
)
732 if (!subreg_lowpart_p (next
))
735 nextr
= SUBREG_REG (next
);
736 if (GET_MODE (nextr
) != outer_mode
)
742 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
744 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
747 if (res
== GRD_MAYBE_BIV
)
749 if (!rtx_equal_p (nextr
, reg
))
752 *inner_step
= const0_rtx
;
753 *extend
= IV_UNKNOWN_EXTEND
;
754 *inner_mode
= outer_mode
;
755 *outer_step
= const0_rtx
;
757 else if (!get_biv_step_1 (next_def
, reg
,
758 inner_step
, inner_mode
, extend
, outer_mode
,
762 if (GET_CODE (next
) == SUBREG
)
764 machine_mode amode
= GET_MODE (next
);
766 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
770 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
771 *inner_step
, *outer_step
);
772 *outer_step
= const0_rtx
;
773 *extend
= IV_UNKNOWN_EXTEND
;
784 if (*inner_mode
== outer_mode
785 /* See comment in previous switch. */
786 || GET_MODE (rhs
) != outer_mode
)
787 *inner_step
= simplify_gen_binary (code
, outer_mode
,
790 *outer_step
= simplify_gen_binary (code
, outer_mode
,
796 gcc_assert (GET_MODE (op0
) == *inner_mode
797 && *extend
== IV_UNKNOWN_EXTEND
798 && *outer_step
== const0_rtx
);
800 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
810 /* Gets the operation on register REG inside loop, in shape
812 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
814 If the operation cannot be described in this shape, return false.
815 LAST_DEF is the definition of REG that dominates loop latch. */
818 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
819 machine_mode
*inner_mode
, enum iv_extend_code
*extend
,
820 machine_mode
*outer_mode
, rtx
*outer_step
)
822 *outer_mode
= GET_MODE (reg
);
824 if (!get_biv_step_1 (last_def
, reg
,
825 inner_step
, inner_mode
, extend
, *outer_mode
,
829 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
830 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
835 /* Records information that DEF is induction variable IV. */
838 record_iv (df_ref def
, struct rtx_iv
*iv
)
840 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
843 check_iv_ref_table_size ();
844 DF_REF_IV_SET (def
, recorded_iv
);
847 /* If DEF was already analyzed for bivness, store the description of the biv to
848 IV and return true. Otherwise return false. */
851 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
853 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
863 record_biv (rtx def
, struct rtx_iv
*iv
)
865 struct biv_entry
*biv
= XNEW (struct biv_entry
);
866 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
868 biv
->regno
= REGNO (def
);
874 /* Determines whether DEF is a biv and if so, stores its description
878 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
880 rtx inner_step
, outer_step
;
881 machine_mode inner_mode
, outer_mode
;
882 enum iv_extend_code extend
;
887 fprintf (dump_file
, "Analyzing ");
888 print_rtl (dump_file
, def
);
889 fprintf (dump_file
, " for bivness.\n");
894 if (!CONSTANT_P (def
))
897 return iv_constant (iv
, def
, VOIDmode
);
900 if (!latch_dominating_def (def
, &last_def
))
903 fprintf (dump_file
, " not simple.\n");
908 return iv_constant (iv
, def
, VOIDmode
);
910 if (analyzed_for_bivness_p (def
, iv
))
913 fprintf (dump_file
, " already analysed.\n");
914 return iv
->base
!= NULL_RTX
;
917 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
918 &outer_mode
, &outer_step
))
924 /* Loop transforms base to es (base + inner_step) + outer_step,
925 where es means extend of subreg between inner_mode and outer_mode.
926 The corresponding induction variable is
928 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
930 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
931 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
932 iv
->mode
= inner_mode
;
933 iv
->extend_mode
= outer_mode
;
935 iv
->mult
= const1_rtx
;
936 iv
->delta
= outer_step
;
937 iv
->first_special
= inner_mode
!= outer_mode
;
942 fprintf (dump_file
, " ");
943 dump_iv_info (dump_file
, iv
);
944 fprintf (dump_file
, "\n");
947 record_biv (def
, iv
);
948 return iv
->base
!= NULL_RTX
;
951 /* Analyzes expression RHS used at INSN and stores the result to *IV.
952 The mode of the induction variable is MODE. */
955 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, machine_mode mode
,
959 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
960 struct rtx_iv iv0
, iv1
;
961 enum rtx_code code
= GET_CODE (rhs
);
962 machine_mode omode
= mode
;
968 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
974 if (!iv_analyze_op (insn
, rhs
, iv
))
977 if (iv
->mode
== VOIDmode
)
980 iv
->extend_mode
= mode
;
996 omode
= GET_MODE (op0
);
1001 op0
= XEXP (rhs
, 0);
1002 op1
= XEXP (rhs
, 1);
1006 op0
= XEXP (rhs
, 0);
1007 mby
= XEXP (rhs
, 1);
1008 if (!CONSTANT_P (mby
))
1009 std::swap (op0
, mby
);
1010 if (!CONSTANT_P (mby
))
1015 op0
= XEXP (rhs
, 0);
1016 mby
= XEXP (rhs
, 1);
1017 if (!CONSTANT_P (mby
))
1026 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1030 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1036 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1041 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1052 if (!iv_add (&iv0
, &iv1
, code
))
1057 if (!iv_mult (&iv0
, mby
))
1062 if (!iv_shift (&iv0
, mby
))
1071 return iv
->base
!= NULL_RTX
;
1074 /* Analyzes iv DEF and stores the result to *IV. */
1077 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1079 rtx_insn
*insn
= DF_REF_INSN (def
);
1080 rtx reg
= DF_REF_REG (def
);
1085 fprintf (dump_file
, "Analyzing def of ");
1086 print_rtl (dump_file
, reg
);
1087 fprintf (dump_file
, " in insn ");
1088 print_rtl_single (dump_file
, insn
);
1091 check_iv_ref_table_size ();
1092 if (DF_REF_IV (def
))
1095 fprintf (dump_file
, " already analysed.\n");
1096 *iv
= *DF_REF_IV (def
);
1097 return iv
->base
!= NULL_RTX
;
1100 iv
->mode
= VOIDmode
;
1101 iv
->base
= NULL_RTX
;
1102 iv
->step
= NULL_RTX
;
1107 set
= single_set (insn
);
1111 if (!REG_P (SET_DEST (set
)))
1114 gcc_assert (SET_DEST (set
) == reg
);
1115 rhs
= find_reg_equal_equiv_note (insn
);
1117 rhs
= XEXP (rhs
, 0);
1119 rhs
= SET_SRC (set
);
1121 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1122 record_iv (def
, iv
);
1126 print_rtl (dump_file
, reg
);
1127 fprintf (dump_file
, " in insn ");
1128 print_rtl_single (dump_file
, insn
);
1129 fprintf (dump_file
, " is ");
1130 dump_iv_info (dump_file
, iv
);
1131 fprintf (dump_file
, "\n");
1134 return iv
->base
!= NULL_RTX
;
1137 /* Analyzes operand OP of INSN and stores the result to *IV. */
1140 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1143 enum iv_grd_result res
;
1147 fprintf (dump_file
, "Analyzing operand ");
1148 print_rtl (dump_file
, op
);
1149 fprintf (dump_file
, " of insn ");
1150 print_rtl_single (dump_file
, insn
);
1153 if (function_invariant_p (op
))
1154 res
= GRD_INVARIANT
;
1155 else if (GET_CODE (op
) == SUBREG
)
1157 if (!subreg_lowpart_p (op
))
1160 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1163 return iv_subreg (iv
, GET_MODE (op
));
1167 res
= iv_get_reaching_def (insn
, op
, &def
);
1168 if (res
== GRD_INVALID
)
1171 fprintf (dump_file
, " not simple.\n");
1176 if (res
== GRD_INVARIANT
)
1178 iv_constant (iv
, op
, VOIDmode
);
1182 fprintf (dump_file
, " ");
1183 dump_iv_info (dump_file
, iv
);
1184 fprintf (dump_file
, "\n");
1189 if (res
== GRD_MAYBE_BIV
)
1190 return iv_analyze_biv (op
, iv
);
1192 return iv_analyze_def (def
, iv
);
1195 /* Analyzes value VAL at INSN and stores the result to *IV. */
1198 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1202 /* We must find the insn in that val is used, so that we get to UD chains.
1203 Since the function is sometimes called on result of get_condition,
1204 this does not necessarily have to be directly INSN; scan also the
1206 if (simple_reg_p (val
))
1208 if (GET_CODE (val
) == SUBREG
)
1209 reg
= SUBREG_REG (val
);
1213 while (!df_find_use (insn
, reg
))
1214 insn
= NEXT_INSN (insn
);
1217 return iv_analyze_op (insn
, val
, iv
);
1220 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1223 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1227 adef
= df_find_def (insn
, def
);
1231 return iv_analyze_def (adef
, iv
);
1234 /* Checks whether definition of register REG in INSN is a basic induction
1235 variable. IV analysis must have been initialized (via a call to
1236 iv_analysis_loop_init) for this function to produce a result. */
1239 biv_p (rtx_insn
*insn
, rtx reg
)
1242 df_ref def
, last_def
;
1244 if (!simple_reg_p (reg
))
1247 def
= df_find_def (insn
, reg
);
1248 gcc_assert (def
!= NULL
);
1249 if (!latch_dominating_def (reg
, &last_def
))
1251 if (last_def
!= def
)
1254 if (!iv_analyze_biv (reg
, &iv
))
1257 return iv
.step
!= const0_rtx
;
1260 /* Calculates value of IV at ITERATION-th iteration. */
1263 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1267 /* We would need to generate some if_then_else patterns, and so far
1268 it is not needed anywhere. */
1269 gcc_assert (!iv
->first_special
);
1271 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1272 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1273 simplify_gen_binary (MULT
, iv
->extend_mode
,
1274 iv
->step
, iteration
));
1278 if (iv
->extend_mode
== iv
->mode
)
1281 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1283 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1286 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1287 iv
->extend_mode
, val
, iv
->mode
);
1288 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1289 simplify_gen_binary (MULT
, iv
->extend_mode
,
1295 /* Free the data for an induction variable analysis. */
1298 iv_analysis_done (void)
1304 df_finish_pass (true);
1307 free (iv_ref_table
);
1308 iv_ref_table
= NULL
;
1309 iv_ref_table_size
= 0;
1313 /* Computes inverse to X modulo (1 << MOD). */
1316 inverse (uint64_t x
, int mod
)
1319 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1323 for (i
= 0; i
< mod
- 1; i
++)
1325 rslt
= (rslt
* x
) & mask
;
1332 /* Checks whether any register in X is in set ALT. */
1335 altered_reg_used (const_rtx x
, bitmap alt
)
1337 subrtx_iterator::array_type array
;
1338 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
1340 const_rtx x
= *iter
;
1341 if (REG_P (x
) && REGNO_REG_SET_P (alt
, REGNO (x
)))
1347 /* Marks registers altered by EXPR in set ALT. */
1350 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1352 if (GET_CODE (expr
) == SUBREG
)
1353 expr
= SUBREG_REG (expr
);
1357 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1360 /* Checks whether RHS is simple enough to process. */
1363 simple_rhs_p (rtx rhs
)
1367 if (function_invariant_p (rhs
)
1368 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1371 switch (GET_CODE (rhs
))
1376 op0
= XEXP (rhs
, 0);
1377 op1
= XEXP (rhs
, 1);
1378 /* Allow reg OP const and reg OP reg. */
1379 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1380 && !function_invariant_p (op0
))
1382 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1383 && !function_invariant_p (op1
))
1392 op0
= XEXP (rhs
, 0);
1393 op1
= XEXP (rhs
, 1);
1394 /* Allow reg OP const. */
1395 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1397 if (!function_invariant_p (op1
))
1407 /* If REGNO has a single definition, return its known value, otherwise return
1411 find_single_def_src (unsigned int regno
)
1419 adef
= DF_REG_DEF_CHAIN (regno
);
1420 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1421 || DF_REF_IS_ARTIFICIAL (adef
))
1424 set
= single_set (DF_REF_INSN (adef
));
1425 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1426 || REGNO (SET_DEST (set
)) != regno
)
1429 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1431 if (note
&& function_invariant_p (XEXP (note
, 0)))
1433 src
= XEXP (note
, 0);
1436 src
= SET_SRC (set
);
1440 regno
= REGNO (src
);
1445 if (!function_invariant_p (src
))
1451 /* If any registers in *EXPR that have a single definition, try to replace
1452 them with the known-equivalent values. */
1455 replace_single_def_regs (rtx
*expr
)
1457 subrtx_var_iterator::array_type array
;
1459 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1463 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1465 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1471 /* A subroutine of simplify_using_initial_values, this function examines INSN
1472 to see if it contains a suitable set that we can use to make a replacement.
1473 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1474 the set; return false otherwise. */
1477 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1479 rtx set
= single_set (insn
);
1480 rtx lhs
= NULL_RTX
, rhs
;
1485 lhs
= SET_DEST (set
);
1489 rhs
= find_reg_equal_equiv_note (insn
);
1491 rhs
= XEXP (rhs
, 0);
1493 rhs
= SET_SRC (set
);
1495 if (!simple_rhs_p (rhs
))
1503 /* Using the data returned by suitable_set_for_replacement, replace DEST
1504 with SRC in *EXPR and return the new expression. Also call
1505 replace_single_def_regs if the replacement changed something. */
1507 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1510 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1513 replace_single_def_regs (expr
);
1516 /* Checks whether A implies B. */
1519 implies_p (rtx a
, rtx b
)
1521 rtx op0
, op1
, opb0
, opb1
;
1524 if (rtx_equal_p (a
, b
))
1527 if (GET_CODE (a
) == EQ
)
1533 || (GET_CODE (op0
) == SUBREG
1534 && REG_P (SUBREG_REG (op0
))))
1536 rtx r
= simplify_replace_rtx (b
, op0
, op1
);
1537 if (r
== const_true_rtx
)
1542 || (GET_CODE (op1
) == SUBREG
1543 && REG_P (SUBREG_REG (op1
))))
1545 rtx r
= simplify_replace_rtx (b
, op1
, op0
);
1546 if (r
== const_true_rtx
)
1551 if (b
== const_true_rtx
)
1554 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1555 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1556 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1557 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1565 mode
= GET_MODE (op0
);
1566 if (mode
!= GET_MODE (opb0
))
1568 else if (mode
== VOIDmode
)
1570 mode
= GET_MODE (op1
);
1571 if (mode
!= GET_MODE (opb1
))
1575 /* A < B implies A + 1 <= B. */
1576 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1577 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1580 if (GET_CODE (a
) == GT
)
1581 std::swap (op0
, op1
);
1583 if (GET_CODE (b
) == GE
)
1584 std::swap (opb0
, opb1
);
1586 if (SCALAR_INT_MODE_P (mode
)
1587 && rtx_equal_p (op1
, opb1
)
1588 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1593 /* A < B or A > B imply A != B. TODO: Likewise
1594 A + n < B implies A != B + n if neither wraps. */
1595 if (GET_CODE (b
) == NE
1596 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1597 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1599 if (rtx_equal_p (op0
, opb0
)
1600 && rtx_equal_p (op1
, opb1
))
1604 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1605 if (GET_CODE (a
) == NE
1606 && op1
== const0_rtx
)
1608 if ((GET_CODE (b
) == GTU
1609 && opb1
== const0_rtx
)
1610 || (GET_CODE (b
) == GEU
1611 && opb1
== const1_rtx
))
1612 return rtx_equal_p (op0
, opb0
);
1615 /* A != N is equivalent to A - (N + 1) <u -1. */
1616 if (GET_CODE (a
) == NE
1617 && CONST_INT_P (op1
)
1618 && GET_CODE (b
) == LTU
1619 && opb1
== constm1_rtx
1620 && GET_CODE (opb0
) == PLUS
1621 && CONST_INT_P (XEXP (opb0
, 1))
1622 /* Avoid overflows. */
1623 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1624 != ((unsigned HOST_WIDE_INT
)1
1625 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1626 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1627 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1629 /* Likewise, A != N implies A - N > 0. */
1630 if (GET_CODE (a
) == NE
1631 && CONST_INT_P (op1
))
1633 if (GET_CODE (b
) == GTU
1634 && GET_CODE (opb0
) == PLUS
1635 && opb1
== const0_rtx
1636 && CONST_INT_P (XEXP (opb0
, 1))
1637 /* Avoid overflows. */
1638 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1639 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1640 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1641 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1642 if (GET_CODE (b
) == GEU
1643 && GET_CODE (opb0
) == PLUS
1644 && opb1
== const1_rtx
1645 && CONST_INT_P (XEXP (opb0
, 1))
1646 /* Avoid overflows. */
1647 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1648 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1649 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1650 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1653 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1654 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1655 && CONST_INT_P (op1
)
1656 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1657 || INTVAL (op1
) >= 0)
1658 && GET_CODE (b
) == LTU
1659 && CONST_INT_P (opb1
)
1660 && rtx_equal_p (op0
, opb0
))
1661 return INTVAL (opb1
) < 0;
1666 /* Canonicalizes COND so that
1668 (1) Ensure that operands are ordered according to
1669 swap_commutative_operands_p.
1670 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1671 for GE, GEU, and LEU. */
1674 canon_condition (rtx cond
)
1680 code
= GET_CODE (cond
);
1681 op0
= XEXP (cond
, 0);
1682 op1
= XEXP (cond
, 1);
1684 if (swap_commutative_operands_p (op0
, op1
))
1686 code
= swap_condition (code
);
1687 std::swap (op0
, op1
);
1690 mode
= GET_MODE (op0
);
1691 if (mode
== VOIDmode
)
1692 mode
= GET_MODE (op1
);
1693 gcc_assert (mode
!= VOIDmode
);
1695 if (CONST_SCALAR_INT_P (op1
) && GET_MODE_CLASS (mode
) != MODE_CC
)
1697 rtx_mode_t
const_val (op1
, mode
);
1702 if (wi::ne_p (const_val
, wi::max_value (mode
, SIGNED
)))
1705 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1710 if (wi::ne_p (const_val
, wi::min_value (mode
, SIGNED
)))
1713 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1718 if (wi::ne_p (const_val
, -1))
1721 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1726 if (wi::ne_p (const_val
, 0))
1729 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1738 if (op0
!= XEXP (cond
, 0)
1739 || op1
!= XEXP (cond
, 1)
1740 || code
!= GET_CODE (cond
)
1741 || GET_MODE (cond
) != SImode
)
1742 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1747 /* Reverses CONDition; returns NULL if we cannot. */
1750 reversed_condition (rtx cond
)
1752 enum rtx_code reversed
;
1753 reversed
= reversed_comparison_code (cond
, NULL
);
1754 if (reversed
== UNKNOWN
)
1757 return gen_rtx_fmt_ee (reversed
,
1758 GET_MODE (cond
), XEXP (cond
, 0),
1762 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1763 set of altered regs. */
1766 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1768 rtx rev
, reve
, exp
= *expr
;
1770 /* If some register gets altered later, we do not really speak about its
1771 value at the time of comparison. */
1772 if (altered
&& altered_reg_used (cond
, altered
))
1775 if (GET_CODE (cond
) == EQ
1776 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1778 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1782 if (!COMPARISON_P (exp
))
1785 rev
= reversed_condition (cond
);
1786 reve
= reversed_condition (exp
);
1788 cond
= canon_condition (cond
);
1789 exp
= canon_condition (exp
);
1791 rev
= canon_condition (rev
);
1793 reve
= canon_condition (reve
);
1795 if (rtx_equal_p (exp
, cond
))
1797 *expr
= const_true_rtx
;
1801 if (rev
&& rtx_equal_p (exp
, rev
))
1807 if (implies_p (cond
, exp
))
1809 *expr
= const_true_rtx
;
1813 if (reve
&& implies_p (cond
, reve
))
1819 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1821 if (rev
&& implies_p (exp
, rev
))
1827 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1828 if (rev
&& reve
&& implies_p (reve
, rev
))
1830 *expr
= const_true_rtx
;
1834 /* We would like to have some other tests here. TODO. */
1839 /* Use relationship between A and *B to eventually eliminate *B.
1840 OP is the operation we consider. */
1843 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1848 /* If A implies *B, we may replace *B by true. */
1849 if (implies_p (a
, *b
))
1850 *b
= const_true_rtx
;
1854 /* If *B implies A, we may replace *B by false. */
1855 if (implies_p (*b
, a
))
1864 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1865 operation we consider. */
1868 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1872 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1873 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1874 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1875 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1878 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1879 is a list, its elements are assumed to be combined using OP. */
1882 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1884 bool expression_valid
;
1885 rtx head
, tail
, last_valid_expr
;
1886 rtx_expr_list
*cond_list
;
1889 regset altered
, this_altered
;
1895 if (CONSTANT_P (*expr
))
1898 if (GET_CODE (*expr
) == EXPR_LIST
)
1900 head
= XEXP (*expr
, 0);
1901 tail
= XEXP (*expr
, 1);
1903 eliminate_implied_conditions (op
, &head
, tail
);
1908 neutral
= const_true_rtx
;
1913 neutral
= const0_rtx
;
1914 aggr
= const_true_rtx
;
1921 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1924 XEXP (*expr
, 0) = aggr
;
1925 XEXP (*expr
, 1) = NULL_RTX
;
1928 else if (head
== neutral
)
1931 simplify_using_initial_values (loop
, op
, expr
);
1934 simplify_using_initial_values (loop
, op
, &tail
);
1936 if (tail
&& XEXP (tail
, 0) == aggr
)
1942 XEXP (*expr
, 0) = head
;
1943 XEXP (*expr
, 1) = tail
;
1947 gcc_assert (op
== UNKNOWN
);
1949 replace_single_def_regs (expr
);
1950 if (CONSTANT_P (*expr
))
1953 e
= loop_preheader_edge (loop
);
1954 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1957 altered
= ALLOC_REG_SET (®_obstack
);
1958 this_altered
= ALLOC_REG_SET (®_obstack
);
1960 expression_valid
= true;
1961 last_valid_expr
= *expr
;
1965 insn
= BB_END (e
->src
);
1966 if (any_condjump_p (insn
))
1968 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1970 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1971 cond
= reversed_condition (cond
);
1975 simplify_using_condition (cond
, expr
, altered
);
1979 if (CONSTANT_P (*expr
))
1981 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1983 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1984 if (CONSTANT_P (*expr
))
1988 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1992 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
2000 CLEAR_REG_SET (this_altered
);
2001 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
2004 /* Kill all call clobbered registers. */
2006 hard_reg_set_iterator hrsi
;
2007 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2009 SET_REGNO_REG_SET (this_altered
, i
);
2012 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2014 rtx_expr_list
**pnote
, **pnote_next
;
2016 replace_in_expr (expr
, dest
, src
);
2017 if (CONSTANT_P (*expr
))
2020 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2022 rtx_expr_list
*note
= *pnote
;
2023 rtx old_cond
= XEXP (note
, 0);
2025 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2026 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2028 /* We can no longer use a condition that has been simplified
2029 to a constant, and simplify_using_condition will abort if
2031 if (CONSTANT_P (XEXP (note
, 0)))
2033 *pnote
= *pnote_next
;
2035 free_EXPR_LIST_node (note
);
2037 /* Retry simplifications with this condition if either the
2038 expression or the condition changed. */
2039 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2040 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2045 rtx_expr_list
**pnote
, **pnote_next
;
2047 /* If we did not use this insn to make a replacement, any overlap
2048 between stores in this insn and our expression will cause the
2049 expression to become invalid. */
2050 if (altered_reg_used (*expr
, this_altered
))
2053 /* Likewise for the conditions. */
2054 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2056 rtx_expr_list
*note
= *pnote
;
2057 rtx old_cond
= XEXP (note
, 0);
2059 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2060 if (altered_reg_used (old_cond
, this_altered
))
2062 *pnote
= *pnote_next
;
2064 free_EXPR_LIST_node (note
);
2069 if (CONSTANT_P (*expr
))
2072 IOR_REG_SET (altered
, this_altered
);
2074 /* If the expression now contains regs that have been altered, we
2075 can't return it to the caller. However, it is still valid for
2076 further simplification, so keep searching to see if we can
2077 eventually turn it into a constant. */
2078 if (altered_reg_used (*expr
, altered
))
2079 expression_valid
= false;
2080 if (expression_valid
)
2081 last_valid_expr
= *expr
;
2084 if (!single_pred_p (e
->src
)
2085 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2087 e
= single_pred_edge (e
->src
);
2091 free_EXPR_LIST_list (&cond_list
);
2092 if (!CONSTANT_P (*expr
))
2093 *expr
= last_valid_expr
;
2094 FREE_REG_SET (altered
);
2095 FREE_REG_SET (this_altered
);
2098 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2099 that IV occurs as left operands of comparison COND and its signedness
2100 is SIGNED_P to DESC. */
2103 shorten_into_mode (struct rtx_iv
*iv
, machine_mode mode
,
2104 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2106 rtx mmin
, mmax
, cond_over
, cond_under
;
2108 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2109 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2111 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2120 if (cond_under
!= const0_rtx
)
2122 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2123 if (cond_over
!= const0_rtx
)
2124 desc
->noloop_assumptions
=
2125 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2132 if (cond_over
!= const0_rtx
)
2134 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2135 if (cond_under
!= const0_rtx
)
2136 desc
->noloop_assumptions
=
2137 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2141 if (cond_over
!= const0_rtx
)
2143 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2144 if (cond_under
!= const0_rtx
)
2146 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2154 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2157 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2158 subregs of the same mode if possible (sometimes it is necessary to add
2159 some assumptions to DESC). */
2162 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2163 enum rtx_code cond
, struct niter_desc
*desc
)
2165 machine_mode comp_mode
;
2168 /* If the ivs behave specially in the first iteration, or are
2169 added/multiplied after extending, we ignore them. */
2170 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2172 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2175 /* If there is some extend, it must match signedness of the comparison. */
2180 if (iv0
->extend
== IV_ZERO_EXTEND
2181 || iv1
->extend
== IV_ZERO_EXTEND
)
2188 if (iv0
->extend
== IV_SIGN_EXTEND
2189 || iv1
->extend
== IV_SIGN_EXTEND
)
2195 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2196 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2197 && iv0
->extend
!= iv1
->extend
)
2201 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2202 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2203 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2204 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2211 /* Values of both variables should be computed in the same mode. These
2212 might indeed be different, if we have comparison like
2214 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2216 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2217 in different modes. This does not seem impossible to handle, but
2218 it hardly ever occurs in practice.
2220 The only exception is the case when one of operands is invariant.
2221 For example pentium 3 generates comparisons like
2222 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2223 definitely do not want this prevent the optimization. */
2224 comp_mode
= iv0
->extend_mode
;
2225 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2226 comp_mode
= iv1
->extend_mode
;
2228 if (iv0
->extend_mode
!= comp_mode
)
2230 if (iv0
->mode
!= iv0
->extend_mode
2231 || iv0
->step
!= const0_rtx
)
2234 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2235 comp_mode
, iv0
->base
, iv0
->mode
);
2236 iv0
->extend_mode
= comp_mode
;
2239 if (iv1
->extend_mode
!= comp_mode
)
2241 if (iv1
->mode
!= iv1
->extend_mode
2242 || iv1
->step
!= const0_rtx
)
2245 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2246 comp_mode
, iv1
->base
, iv1
->mode
);
2247 iv1
->extend_mode
= comp_mode
;
2250 /* Check that both ivs belong to a range of a single mode. If one of the
2251 operands is an invariant, we may need to shorten it into the common
2253 if (iv0
->mode
== iv0
->extend_mode
2254 && iv0
->step
== const0_rtx
2255 && iv0
->mode
!= iv1
->mode
)
2256 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2258 if (iv1
->mode
== iv1
->extend_mode
2259 && iv1
->step
== const0_rtx
2260 && iv0
->mode
!= iv1
->mode
)
2261 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2263 if (iv0
->mode
!= iv1
->mode
)
2266 desc
->mode
= iv0
->mode
;
2267 desc
->signed_p
= signed_p
;
2272 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2273 result. This function is called from iv_number_of_iterations with
2274 a number of fields in DESC already filled in. OLD_NITER is the original
2275 expression for the number of iterations, before we tried to simplify it. */
2278 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2280 rtx niter
= desc
->niter_expr
;
2281 rtx mmin
, mmax
, cmp
;
2283 uint64_t andmax
= 0;
2285 /* We used to look for constant operand 0 of AND,
2286 but canonicalization should always make this impossible. */
2287 gcc_checking_assert (GET_CODE (niter
) != AND
2288 || !CONST_INT_P (XEXP (niter
, 0)));
2290 if (GET_CODE (niter
) == AND
2291 && CONST_INT_P (XEXP (niter
, 1)))
2293 andmax
= UINTVAL (XEXP (niter
, 1));
2294 niter
= XEXP (niter
, 0);
2297 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2298 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2300 if (GET_CODE (niter
) == UDIV
)
2302 if (!CONST_INT_P (XEXP (niter
, 1)))
2304 inc
= INTVAL (XEXP (niter
, 1));
2305 niter
= XEXP (niter
, 0);
2310 /* We could use a binary search here, but for now improving the upper
2311 bound by just one eliminates one important corner case. */
2312 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2313 desc
->mode
, old_niter
, mmax
);
2314 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2315 if (cmp
== const_true_rtx
)
2320 fprintf (dump_file
, ";; improved upper bound by one.\n");
2324 nmax
= MIN (nmax
, andmax
);
2326 fprintf (dump_file
, ";; Determined upper bound %" PRId64
".\n",
2331 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2332 the result into DESC. Very similar to determine_number_of_iterations
2333 (basically its rtl version), complicated by things like subregs. */
2336 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2337 struct niter_desc
*desc
)
2339 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2340 struct rtx_iv iv0
, iv1
;
2341 rtx assumption
, may_not_xform
;
2343 machine_mode mode
, comp_mode
;
2344 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2345 uint64_t s
, size
, d
, inv
, max
;
2346 int64_t up
, down
, inc
, step_val
;
2347 int was_sharp
= false;
2351 /* The meaning of these assumptions is this:
2353 then the rest of information does not have to be valid
2354 if noloop_assumptions then the loop does not roll
2355 if infinite then this exit is never used */
2357 desc
->assumptions
= NULL_RTX
;
2358 desc
->noloop_assumptions
= NULL_RTX
;
2359 desc
->infinite
= NULL_RTX
;
2360 desc
->simple_p
= true;
2362 desc
->const_iter
= false;
2363 desc
->niter_expr
= NULL_RTX
;
2365 cond
= GET_CODE (condition
);
2366 gcc_assert (COMPARISON_P (condition
));
2368 mode
= GET_MODE (XEXP (condition
, 0));
2369 if (mode
== VOIDmode
)
2370 mode
= GET_MODE (XEXP (condition
, 1));
2371 /* The constant comparisons should be folded. */
2372 gcc_assert (mode
!= VOIDmode
);
2374 /* We only handle integers or pointers. */
2375 if (GET_MODE_CLASS (mode
) != MODE_INT
2376 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2379 op0
= XEXP (condition
, 0);
2380 if (!iv_analyze (insn
, op0
, &iv0
))
2382 if (iv0
.extend_mode
== VOIDmode
)
2383 iv0
.mode
= iv0
.extend_mode
= mode
;
2385 op1
= XEXP (condition
, 1);
2386 if (!iv_analyze (insn
, op1
, &iv1
))
2388 if (iv1
.extend_mode
== VOIDmode
)
2389 iv1
.mode
= iv1
.extend_mode
= mode
;
2391 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2392 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2395 /* Check condition and normalize it. */
2403 std::swap (iv0
, iv1
);
2404 cond
= swap_condition (cond
);
2416 /* Handle extends. This is relatively nontrivial, so we only try in some
2417 easy cases, when we can canonicalize the ivs (possibly by adding some
2418 assumptions) to shape subreg (base + i * step). This function also fills
2419 in desc->mode and desc->signed_p. */
2421 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2424 comp_mode
= iv0
.extend_mode
;
2426 size
= GET_MODE_PRECISION (mode
);
2427 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2428 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2429 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2431 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2434 /* We can take care of the case of two induction variables chasing each other
2435 if the test is NE. I have never seen a loop using it, but still it is
2437 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2442 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2443 iv1
.step
= const0_rtx
;
2446 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2447 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2449 /* This is either infinite loop or the one that ends immediately, depending
2450 on initial values. Unswitching should remove this kind of conditions. */
2451 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2456 if (iv0
.step
== const0_rtx
)
2457 step_val
= -INTVAL (iv1
.step
);
2459 step_val
= INTVAL (iv0
.step
);
2461 /* Ignore loops of while (i-- < 10) type. */
2465 step_is_pow2
= !(step_val
& (step_val
- 1));
2469 /* We do not care about whether the step is power of two in this
2471 step_is_pow2
= false;
2475 /* Some more condition normalization. We must record some assumptions
2476 due to overflows. */
2481 /* We want to take care only of non-sharp relationals; this is easy,
2482 as in cases the overflow would make the transformation unsafe
2483 the loop does not roll. Seemingly it would make more sense to want
2484 to take care of sharp relationals instead, as NE is more similar to
2485 them, but the problem is that here the transformation would be more
2486 difficult due to possibly infinite loops. */
2487 if (iv0
.step
== const0_rtx
)
2489 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2490 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2492 if (assumption
== const_true_rtx
)
2493 goto zero_iter_simplify
;
2494 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2495 iv0
.base
, const1_rtx
);
2499 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2500 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2502 if (assumption
== const_true_rtx
)
2503 goto zero_iter_simplify
;
2504 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2505 iv1
.base
, constm1_rtx
);
2508 if (assumption
!= const0_rtx
)
2509 desc
->noloop_assumptions
=
2510 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2511 cond
= (cond
== LT
) ? LE
: LEU
;
2513 /* It will be useful to be able to tell the difference once more in
2514 LE -> NE reduction. */
2520 /* Take care of trivially infinite loops. */
2523 if (iv0
.step
== const0_rtx
)
2525 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2526 if (rtx_equal_p (tmp
, mode_mmin
))
2529 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2530 /* Fill in the remaining fields somehow. */
2531 goto zero_iter_simplify
;
2536 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2537 if (rtx_equal_p (tmp
, mode_mmax
))
2540 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2541 /* Fill in the remaining fields somehow. */
2542 goto zero_iter_simplify
;
2547 /* If we can we want to take care of NE conditions instead of size
2548 comparisons, as they are much more friendly (most importantly
2549 this takes care of special handling of loops with step 1). We can
2550 do it if we first check that upper bound is greater or equal to
2551 lower bound, their difference is constant c modulo step and that
2552 there is not an overflow. */
2555 if (iv0
.step
== const0_rtx
)
2556 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2559 step
= lowpart_subreg (mode
, step
, comp_mode
);
2560 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2561 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2562 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2563 may_xform
= const0_rtx
;
2564 may_not_xform
= const_true_rtx
;
2566 if (CONST_INT_P (delta
))
2568 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2570 /* A special case. We have transformed condition of type
2571 for (i = 0; i < 4; i += 4)
2573 for (i = 0; i <= 3; i += 4)
2574 obviously if the test for overflow during that transformation
2575 passed, we cannot overflow here. Most importantly any
2576 loop with sharp end condition and step 1 falls into this
2577 category, so handling this case specially is definitely
2578 worth the troubles. */
2579 may_xform
= const_true_rtx
;
2581 else if (iv0
.step
== const0_rtx
)
2583 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2584 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2585 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2586 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2587 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2589 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2595 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2596 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2597 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2598 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2599 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2601 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2607 if (may_xform
!= const0_rtx
)
2609 /* We perform the transformation always provided that it is not
2610 completely senseless. This is OK, as we would need this assumption
2611 to determine the number of iterations anyway. */
2612 if (may_xform
!= const_true_rtx
)
2614 /* If the step is a power of two and the final value we have
2615 computed overflows, the cycle is infinite. Otherwise it
2616 is nontrivial to compute the number of iterations. */
2618 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2621 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2625 /* We are going to lose some information about upper bound on
2626 number of iterations in this step, so record the information
2628 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2629 if (CONST_INT_P (iv1
.base
))
2630 up
= INTVAL (iv1
.base
);
2632 up
= INTVAL (mode_mmax
) - inc
;
2633 down
= INTVAL (CONST_INT_P (iv0
.base
)
2636 max
= (uint64_t) (up
- down
) / inc
+ 1;
2638 && !desc
->assumptions
)
2639 record_niter_bound (loop
, max
, false, true);
2641 if (iv0
.step
== const0_rtx
)
2643 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2644 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2648 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2649 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2652 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2653 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2654 assumption
= simplify_gen_relational (reverse_condition (cond
),
2655 SImode
, mode
, tmp0
, tmp1
);
2656 if (assumption
== const_true_rtx
)
2657 goto zero_iter_simplify
;
2658 else if (assumption
!= const0_rtx
)
2659 desc
->noloop_assumptions
=
2660 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2665 /* Count the number of iterations. */
2668 /* Everything we do here is just arithmetics modulo size of mode. This
2669 makes us able to do more involved computations of number of iterations
2670 than in other cases. First transform the condition into shape
2671 s * i <> c, with s positive. */
2672 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2673 iv0
.base
= const0_rtx
;
2674 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2675 iv1
.step
= const0_rtx
;
2676 if (INTVAL (iv0
.step
) < 0)
2678 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2679 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2681 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2683 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2684 is infinite. Otherwise, the number of iterations is
2685 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2686 s
= INTVAL (iv0
.step
); d
= 1;
2693 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2695 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2696 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2697 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2698 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2700 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2701 inv
= inverse (s
, size
);
2702 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2703 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2707 if (iv1
.step
== const0_rtx
)
2708 /* Condition in shape a + s * i <= b
2709 We must know that b + s does not overflow and a <= b + s and then we
2710 can compute number of iterations as (b + s - a) / s. (It might
2711 seem that we in fact could be more clever about testing the b + s
2712 overflow condition using some information about b - a mod s,
2713 but it was already taken into account during LE -> NE transform). */
2716 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2717 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2719 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2720 lowpart_subreg (mode
, step
,
2726 /* If s is power of 2, we know that the loop is infinite if
2727 a % s <= b % s and b + s overflows. */
2728 assumption
= simplify_gen_relational (reverse_condition (cond
),
2732 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2733 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2734 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2735 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2737 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2741 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2744 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2747 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2748 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2749 assumption
= simplify_gen_relational (reverse_condition (cond
),
2750 SImode
, mode
, tmp0
, tmp
);
2752 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2753 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2757 /* Condition in shape a <= b - s * i
2758 We must know that a - s does not overflow and a - s <= b and then
2759 we can again compute number of iterations as (b - (a - s)) / s. */
2760 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2761 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2762 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2764 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2765 lowpart_subreg (mode
, step
, comp_mode
));
2770 /* If s is power of 2, we know that the loop is infinite if
2771 a % s <= b % s and a - s overflows. */
2772 assumption
= simplify_gen_relational (reverse_condition (cond
),
2776 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2777 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2778 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2779 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2781 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2785 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2788 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2791 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2792 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2793 assumption
= simplify_gen_relational (reverse_condition (cond
),
2796 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2797 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2799 if (assumption
== const_true_rtx
)
2800 goto zero_iter_simplify
;
2801 else if (assumption
!= const0_rtx
)
2802 desc
->noloop_assumptions
=
2803 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2804 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2805 desc
->niter_expr
= delta
;
2808 old_niter
= desc
->niter_expr
;
2810 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2811 if (desc
->assumptions
2812 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2814 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2815 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2816 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2818 /* Rerun the simplification. Consider code (created by copying loop headers)
2830 The first pass determines that i = 0, the second pass uses it to eliminate
2831 noloop assumption. */
2833 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2834 if (desc
->assumptions
2835 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2837 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2838 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2839 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2841 if (desc
->noloop_assumptions
2842 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2845 if (CONST_INT_P (desc
->niter_expr
))
2847 uint64_t val
= INTVAL (desc
->niter_expr
);
2849 desc
->const_iter
= true;
2850 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2852 && !desc
->assumptions
)
2853 record_niter_bound (loop
, desc
->niter
, false, true);
2857 max
= determine_max_iter (loop
, desc
, old_niter
);
2859 goto zero_iter_simplify
;
2861 && !desc
->assumptions
)
2862 record_niter_bound (loop
, max
, false, true);
2864 /* simplify_using_initial_values does a copy propagation on the registers
2865 in the expression for the number of iterations. This prolongs life
2866 ranges of registers and increases register pressure, and usually
2867 brings no gain (and if it happens to do, the cse pass will take care
2868 of it anyway). So prevent this behavior, unless it enabled us to
2869 derive that the number of iterations is a constant. */
2870 desc
->niter_expr
= old_niter
;
2876 /* Simplify the assumptions. */
2877 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2878 if (desc
->assumptions
2879 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2881 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2885 desc
->const_iter
= true;
2887 record_niter_bound (loop
, 0, true, true);
2888 desc
->noloop_assumptions
= NULL_RTX
;
2889 desc
->niter_expr
= const0_rtx
;
2893 desc
->simple_p
= false;
2897 /* Checks whether E is a simple exit from LOOP and stores its description
2901 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2903 basic_block exit_bb
;
2909 desc
->simple_p
= false;
2911 /* It must belong directly to the loop. */
2912 if (exit_bb
->loop_father
!= loop
)
2915 /* It must be tested (at least) once during any iteration. */
2916 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2919 /* It must end in a simple conditional jump. */
2920 if (!any_condjump_p (BB_END (exit_bb
)))
2923 ein
= EDGE_SUCC (exit_bb
, 0);
2925 ein
= EDGE_SUCC (exit_bb
, 1);
2928 desc
->in_edge
= ein
;
2930 /* Test whether the condition is suitable. */
2931 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2934 if (ein
->flags
& EDGE_FALLTHRU
)
2936 condition
= reversed_condition (condition
);
2941 /* Check that we are able to determine number of iterations and fill
2942 in information about it. */
2943 iv_number_of_iterations (loop
, at
, condition
, desc
);
2946 /* Finds a simple exit of LOOP and stores its description into DESC. */
2949 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2954 struct niter_desc act
;
2958 desc
->simple_p
= false;
2959 body
= get_loop_body (loop
);
2961 for (i
= 0; i
< loop
->num_nodes
; i
++)
2963 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2965 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2968 check_simple_exit (loop
, e
, &act
);
2976 /* Prefer constant iterations; the less the better. */
2978 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2981 /* Also if the actual exit may be infinite, while the old one
2982 not, prefer the old one. */
2983 if (act
.infinite
&& !desc
->infinite
)
2995 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2996 fprintf (dump_file
, " simple exit %d -> %d\n",
2997 desc
->out_edge
->src
->index
,
2998 desc
->out_edge
->dest
->index
);
2999 if (desc
->assumptions
)
3001 fprintf (dump_file
, " assumptions: ");
3002 print_rtl (dump_file
, desc
->assumptions
);
3003 fprintf (dump_file
, "\n");
3005 if (desc
->noloop_assumptions
)
3007 fprintf (dump_file
, " does not roll if: ");
3008 print_rtl (dump_file
, desc
->noloop_assumptions
);
3009 fprintf (dump_file
, "\n");
3013 fprintf (dump_file
, " infinite if: ");
3014 print_rtl (dump_file
, desc
->infinite
);
3015 fprintf (dump_file
, "\n");
3018 fprintf (dump_file
, " number of iterations: ");
3019 print_rtl (dump_file
, desc
->niter_expr
);
3020 fprintf (dump_file
, "\n");
3022 fprintf (dump_file
, " upper bound: %li\n",
3023 (long)get_max_loop_iterations_int (loop
));
3024 fprintf (dump_file
, " realistic bound: %li\n",
3025 (long)get_estimated_loop_iterations_int (loop
));
3028 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3034 /* Creates a simple loop description of LOOP if it was not computed
3038 get_simple_loop_desc (struct loop
*loop
)
3040 struct niter_desc
*desc
= simple_loop_desc (loop
);
3045 /* At least desc->infinite is not always initialized by
3046 find_simple_loop_exit. */
3047 desc
= ggc_cleared_alloc
<niter_desc
> ();
3048 iv_analysis_loop_init (loop
);
3049 find_simple_exit (loop
, desc
);
3050 loop
->simple_loop_desc
= desc
;
3052 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3054 const char *wording
;
3056 /* Assume that no overflow happens and that the loop is finite.
3057 We already warned at the tree level if we ran optimizations there. */
3058 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3063 flag_unsafe_loop_optimizations
3064 ? N_("assuming that the loop is not infinite")
3065 : N_("cannot optimize possibly infinite loops");
3066 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3069 if (desc
->assumptions
)
3072 flag_unsafe_loop_optimizations
3073 ? N_("assuming that the loop counter does not overflow")
3074 : N_("cannot optimize loop, the loop counter may overflow");
3075 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3080 if (flag_unsafe_loop_optimizations
)
3082 desc
->assumptions
= NULL_RTX
;
3083 desc
->infinite
= NULL_RTX
;
3090 /* Releases simple loop description for LOOP. */
3093 free_simple_loop_desc (struct loop
*loop
)
3095 struct niter_desc
*desc
= simple_loop_desc (loop
);
3101 loop
->simple_loop_desc
= NULL
;