1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This is a simple analysis of induction variables of the loop. The major use
22 is for determining the number of iterations of a loop for loop unrolling,
23 doloop optimization and branch prediction. The iv information is computed
26 Induction variable is analyzed by walking the use-def chains. When a biv
27 is found, it is cached in the bivs hash table. When register is proved
28 to be a giv, its description 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.
48 iv_current_loop_df (): Returns the dataflow object for the current loop used
53 #include "coretypes.h"
56 #include "hard-reg-set.h"
58 #include "basic-block.h"
67 /* Possible return values of iv_get_reaching_def. */
71 /* More than one reaching def, or reaching def that does not
75 /* The use is trivial invariant of the loop, i.e. is not changed
79 /* The use is reached by initial value and a value from the
80 previous iteration. */
83 /* The use has single dominating def. */
87 /* Information about a biv. */
91 unsigned regno
; /* The register of the biv. */
92 struct rtx_iv iv
; /* Value of the biv. */
95 /* Induction variable stored at the reference. */
96 #define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF))
97 #define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV)
99 /* The current loop. */
101 static struct loop
*current_loop
;
103 /* Dataflow information for the current loop. */
105 static struct df
*df
= NULL
;
107 /* Bivs of the current loop. */
111 /* Return the dataflow object for the current loop. */
113 iv_current_loop_df (void)
118 static bool iv_analyze_op (rtx
, rtx
, struct rtx_iv
*);
120 /* Dumps information about IV to FILE. */
122 extern void dump_iv_info (FILE *, struct rtx_iv
*);
124 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
128 fprintf (file
, "not simple");
132 if (iv
->step
== const0_rtx
133 && !iv
->first_special
)
134 fprintf (file
, "invariant ");
136 print_rtl (file
, iv
->base
);
137 if (iv
->step
!= const0_rtx
)
139 fprintf (file
, " + ");
140 print_rtl (file
, iv
->step
);
141 fprintf (file
, " * iteration");
143 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
145 if (iv
->mode
!= iv
->extend_mode
)
146 fprintf (file
, " %s to %s",
147 rtx_name
[iv
->extend
],
148 GET_MODE_NAME (iv
->extend_mode
));
150 if (iv
->mult
!= const1_rtx
)
152 fprintf (file
, " * ");
153 print_rtl (file
, iv
->mult
);
155 if (iv
->delta
!= const0_rtx
)
157 fprintf (file
, " + ");
158 print_rtl (file
, iv
->delta
);
160 if (iv
->first_special
)
161 fprintf (file
, " (first special)");
164 /* Generates a subreg to get the least significant part of EXPR (in mode
165 INNER_MODE) to OUTER_MODE. */
168 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
169 enum machine_mode inner_mode
)
171 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
172 subreg_lowpart_offset (outer_mode
, inner_mode
));
175 /* Checks whether REG is a well-behaved register. */
178 simple_reg_p (rtx reg
)
182 if (GET_CODE (reg
) == SUBREG
)
184 if (!subreg_lowpart_p (reg
))
186 reg
= SUBREG_REG (reg
);
193 if (HARD_REGISTER_NUM_P (r
))
196 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
202 /* Clears the information about ivs stored in df. */
207 unsigned i
, n_defs
= DF_DEFS_SIZE (df
);
211 for (i
= 0; i
< n_defs
; i
++)
213 def
= DF_DEFS_GET (df
, i
);
214 iv
= DF_REF_IV (def
);
218 DF_REF_IV_SET (def
, NULL
);
224 /* Returns hash value for biv B. */
227 biv_hash (const void *b
)
229 return ((const struct biv_entry
*) b
)->regno
;
232 /* Compares biv B and register R. */
235 biv_eq (const void *b
, const void *r
)
237 return ((const struct biv_entry
*) b
)->regno
== REGNO ((rtx
) r
);
240 /* Prepare the data for an induction variable analysis of a LOOP. */
243 iv_analysis_loop_init (struct loop
*loop
)
245 basic_block
*body
= get_loop_body_in_dom_order (loop
), bb
;
246 bitmap blocks
= BITMAP_ALLOC (NULL
);
248 bool first_time
= (df
== NULL
);
252 /* Clear the information from the analysis of the previous loop. */
255 df
= df_init (DF_HARD_REGS
| DF_EQUIV_NOTES
);
256 df_chain_add_problem (df
, DF_UD_CHAIN
);
257 bivs
= htab_create (10, biv_hash
, biv_eq
, free
);
262 for (i
= 0; i
< loop
->num_nodes
; i
++)
265 bitmap_set_bit (blocks
, bb
->index
);
267 df_set_blocks (df
, blocks
);
269 BITMAP_FREE (blocks
);
273 /* Finds the definition of REG that dominates loop latch and stores
274 it to DEF. Returns false if there is not a single definition
275 dominating the latch. If REG has no definition in loop, DEF
276 is set to NULL and true is returned. */
279 latch_dominating_def (rtx reg
, struct df_ref
**def
)
281 struct df_ref
*single_rd
= NULL
, *adef
;
282 unsigned regno
= REGNO (reg
);
283 struct df_reg_info
*reg_info
= DF_REG_DEF_GET (df
, regno
);
284 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (df
, current_loop
->latch
);
286 for (adef
= reg_info
->reg_chain
; adef
; adef
= adef
->next_reg
)
288 if (!bitmap_bit_p (bb_info
->out
, DF_REF_ID (adef
)))
291 /* More than one reaching definition. */
295 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
305 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
307 static enum iv_grd_result
308 iv_get_reaching_def (rtx insn
, rtx reg
, struct df_ref
**def
)
310 struct df_ref
*use
, *adef
;
311 basic_block def_bb
, use_bb
;
316 if (!simple_reg_p (reg
))
318 if (GET_CODE (reg
) == SUBREG
)
319 reg
= SUBREG_REG (reg
);
320 gcc_assert (REG_P (reg
));
322 use
= df_find_use (df
, insn
, reg
);
323 gcc_assert (use
!= NULL
);
325 if (!DF_REF_CHAIN (use
))
326 return GRD_INVARIANT
;
328 /* More than one reaching def. */
329 if (DF_REF_CHAIN (use
)->next
)
332 adef
= DF_REF_CHAIN (use
)->ref
;
333 def_insn
= DF_REF_INSN (adef
);
334 def_bb
= DF_REF_BB (adef
);
335 use_bb
= BLOCK_FOR_INSN (insn
);
337 if (use_bb
== def_bb
)
338 dom_p
= (DF_INSN_LUID (df
, def_insn
) < DF_INSN_LUID (df
, insn
));
340 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
345 return GRD_SINGLE_DOM
;
348 /* The definition does not dominate the use. This is still OK if
349 this may be a use of a biv, i.e. if the def_bb dominates loop
351 if (just_once_each_iteration_p (current_loop
, def_bb
))
352 return GRD_MAYBE_BIV
;
357 /* Sets IV to invariant CST in MODE. Always returns true (just for
358 consistency with other iv manipulation functions that may fail). */
361 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
363 if (mode
== VOIDmode
)
364 mode
= GET_MODE (cst
);
368 iv
->step
= const0_rtx
;
369 iv
->first_special
= false;
370 iv
->extend
= UNKNOWN
;
371 iv
->extend_mode
= iv
->mode
;
372 iv
->delta
= const0_rtx
;
373 iv
->mult
= const1_rtx
;
378 /* Evaluates application of subreg to MODE on IV. */
381 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
383 /* If iv is invariant, just calculate the new value. */
384 if (iv
->step
== const0_rtx
385 && !iv
->first_special
)
387 rtx val
= get_iv_value (iv
, const0_rtx
);
388 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
391 iv
->extend
= UNKNOWN
;
392 iv
->mode
= iv
->extend_mode
= mode
;
393 iv
->delta
= const0_rtx
;
394 iv
->mult
= const1_rtx
;
398 if (iv
->extend_mode
== mode
)
401 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
404 iv
->extend
= UNKNOWN
;
407 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
408 simplify_gen_binary (MULT
, iv
->extend_mode
,
409 iv
->base
, iv
->mult
));
410 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
411 iv
->mult
= const1_rtx
;
412 iv
->delta
= const0_rtx
;
413 iv
->first_special
= false;
418 /* Evaluates application of EXTEND to MODE on IV. */
421 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
423 /* If iv is invariant, just calculate the new value. */
424 if (iv
->step
== const0_rtx
425 && !iv
->first_special
)
427 rtx val
= get_iv_value (iv
, const0_rtx
);
428 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
431 iv
->extend
= UNKNOWN
;
432 iv
->mode
= iv
->extend_mode
= mode
;
433 iv
->delta
= const0_rtx
;
434 iv
->mult
= const1_rtx
;
438 if (mode
!= iv
->extend_mode
)
441 if (iv
->extend
!= UNKNOWN
442 && iv
->extend
!= extend
)
450 /* Evaluates negation of IV. */
453 iv_neg (struct rtx_iv
*iv
)
455 if (iv
->extend
== UNKNOWN
)
457 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
458 iv
->base
, iv
->extend_mode
);
459 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
460 iv
->step
, iv
->extend_mode
);
464 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
465 iv
->delta
, iv
->extend_mode
);
466 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
467 iv
->mult
, iv
->extend_mode
);
473 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
476 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
478 enum machine_mode mode
;
481 /* Extend the constant to extend_mode of the other operand if necessary. */
482 if (iv0
->extend
== UNKNOWN
483 && iv0
->mode
== iv0
->extend_mode
484 && iv0
->step
== const0_rtx
485 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
487 iv0
->extend_mode
= iv1
->extend_mode
;
488 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
489 iv0
->base
, iv0
->mode
);
491 if (iv1
->extend
== UNKNOWN
492 && iv1
->mode
== iv1
->extend_mode
493 && iv1
->step
== const0_rtx
494 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
496 iv1
->extend_mode
= iv0
->extend_mode
;
497 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
498 iv1
->base
, iv1
->mode
);
501 mode
= iv0
->extend_mode
;
502 if (mode
!= iv1
->extend_mode
)
505 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
507 if (iv0
->mode
!= iv1
->mode
)
510 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
511 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
516 /* Handle addition of constant. */
517 if (iv1
->extend
== UNKNOWN
519 && iv1
->step
== const0_rtx
)
521 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
525 if (iv0
->extend
== UNKNOWN
527 && iv0
->step
== const0_rtx
)
535 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
542 /* Evaluates multiplication of IV by constant CST. */
545 iv_mult (struct rtx_iv
*iv
, rtx mby
)
547 enum machine_mode mode
= iv
->extend_mode
;
549 if (GET_MODE (mby
) != VOIDmode
550 && GET_MODE (mby
) != mode
)
553 if (iv
->extend
== UNKNOWN
)
555 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
556 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
560 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
561 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
567 /* Evaluates shift of IV by constant CST. */
570 iv_shift (struct rtx_iv
*iv
, rtx mby
)
572 enum machine_mode mode
= iv
->extend_mode
;
574 if (GET_MODE (mby
) != VOIDmode
575 && GET_MODE (mby
) != mode
)
578 if (iv
->extend
== UNKNOWN
)
580 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
581 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
585 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
586 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
592 /* The recursive part of get_biv_step. Gets the value of the single value
593 defined by DEF wrto initial value of REG inside loop, in shape described
597 get_biv_step_1 (struct df_ref
*def
, rtx reg
,
598 rtx
*inner_step
, enum machine_mode
*inner_mode
,
599 enum rtx_code
*extend
, enum machine_mode outer_mode
,
602 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
603 rtx next
, nextr
, tmp
;
605 rtx insn
= DF_REF_INSN (def
);
606 struct df_ref
*next_def
;
607 enum iv_grd_result res
;
609 set
= single_set (insn
);
613 rhs
= find_reg_equal_equiv_note (insn
);
619 code
= GET_CODE (rhs
);
632 if (code
== PLUS
&& CONSTANT_P (op0
))
634 tmp
= op0
; op0
= op1
; op1
= tmp
;
637 if (!simple_reg_p (op0
)
638 || !CONSTANT_P (op1
))
641 if (GET_MODE (rhs
) != outer_mode
)
643 /* ppc64 uses expressions like
645 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
647 this is equivalent to
649 (set x':DI (plus:DI y:DI 1))
650 (set x:SI (subreg:SI (x':DI)). */
651 if (GET_CODE (op0
) != SUBREG
)
653 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
662 if (GET_MODE (rhs
) != outer_mode
)
666 if (!simple_reg_p (op0
))
676 if (GET_CODE (next
) == SUBREG
)
678 if (!subreg_lowpart_p (next
))
681 nextr
= SUBREG_REG (next
);
682 if (GET_MODE (nextr
) != outer_mode
)
688 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
690 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
693 if (res
== GRD_MAYBE_BIV
)
695 if (!rtx_equal_p (nextr
, reg
))
698 *inner_step
= const0_rtx
;
700 *inner_mode
= outer_mode
;
701 *outer_step
= const0_rtx
;
703 else if (!get_biv_step_1 (next_def
, reg
,
704 inner_step
, inner_mode
, extend
, outer_mode
,
708 if (GET_CODE (next
) == SUBREG
)
710 enum machine_mode amode
= GET_MODE (next
);
712 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
716 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
717 *inner_step
, *outer_step
);
718 *outer_step
= const0_rtx
;
730 if (*inner_mode
== outer_mode
731 /* See comment in previous switch. */
732 || GET_MODE (rhs
) != outer_mode
)
733 *inner_step
= simplify_gen_binary (code
, outer_mode
,
736 *outer_step
= simplify_gen_binary (code
, outer_mode
,
742 gcc_assert (GET_MODE (op0
) == *inner_mode
743 && *extend
== UNKNOWN
744 && *outer_step
== const0_rtx
);
756 /* Gets the operation on register REG inside loop, in shape
758 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
760 If the operation cannot be described in this shape, return false.
761 LAST_DEF is the definition of REG that dominates loop latch. */
764 get_biv_step (struct df_ref
*last_def
, rtx reg
, rtx
*inner_step
,
765 enum machine_mode
*inner_mode
, enum rtx_code
*extend
,
766 enum machine_mode
*outer_mode
, rtx
*outer_step
)
768 *outer_mode
= GET_MODE (reg
);
770 if (!get_biv_step_1 (last_def
, reg
,
771 inner_step
, inner_mode
, extend
, *outer_mode
,
775 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= UNKNOWN
));
776 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
781 /* Records information that DEF is induction variable IV. */
784 record_iv (struct df_ref
*def
, struct rtx_iv
*iv
)
786 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
789 DF_REF_IV_SET (def
, recorded_iv
);
792 /* If DEF was already analyzed for bivness, store the description of the biv to
793 IV and return true. Otherwise return false. */
796 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
798 struct biv_entry
*biv
= htab_find_with_hash (bivs
, def
, REGNO (def
));
808 record_biv (rtx def
, struct rtx_iv
*iv
)
810 struct biv_entry
*biv
= XNEW (struct biv_entry
);
811 void **slot
= htab_find_slot_with_hash (bivs
, def
, REGNO (def
), INSERT
);
813 biv
->regno
= REGNO (def
);
819 /* Determines whether DEF is a biv and if so, stores its description
823 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
825 rtx inner_step
, outer_step
;
826 enum machine_mode inner_mode
, outer_mode
;
827 enum rtx_code extend
;
828 struct df_ref
*last_def
;
832 fprintf (dump_file
, "Analyzing ");
833 print_rtl (dump_file
, def
);
834 fprintf (dump_file
, " for bivness.\n");
839 if (!CONSTANT_P (def
))
842 return iv_constant (iv
, def
, VOIDmode
);
845 if (!latch_dominating_def (def
, &last_def
))
848 fprintf (dump_file
, " not simple.\n");
853 return iv_constant (iv
, def
, VOIDmode
);
855 if (analyzed_for_bivness_p (def
, iv
))
858 fprintf (dump_file
, " already analysed.\n");
859 return iv
->base
!= NULL_RTX
;
862 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
863 &outer_mode
, &outer_step
))
869 /* Loop transforms base to es (base + inner_step) + outer_step,
870 where es means extend of subreg between inner_mode and outer_mode.
871 The corresponding induction variable is
873 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
875 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
876 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
877 iv
->mode
= inner_mode
;
878 iv
->extend_mode
= outer_mode
;
880 iv
->mult
= const1_rtx
;
881 iv
->delta
= outer_step
;
882 iv
->first_special
= inner_mode
!= outer_mode
;
887 fprintf (dump_file
, " ");
888 dump_iv_info (dump_file
, iv
);
889 fprintf (dump_file
, "\n");
892 record_biv (def
, iv
);
893 return iv
->base
!= NULL_RTX
;
896 /* Analyzes expression RHS used at INSN and stores the result to *IV.
897 The mode of the induction variable is MODE. */
900 iv_analyze_expr (rtx insn
, rtx rhs
, enum machine_mode mode
, struct rtx_iv
*iv
)
902 rtx mby
= NULL_RTX
, tmp
;
903 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
904 struct rtx_iv iv0
, iv1
;
905 enum rtx_code code
= GET_CODE (rhs
);
906 enum machine_mode omode
= mode
;
912 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
918 if (!iv_analyze_op (insn
, rhs
, iv
))
921 if (iv
->mode
== VOIDmode
)
924 iv
->extend_mode
= mode
;
940 omode
= GET_MODE (op0
);
952 if (!CONSTANT_P (mby
))
958 if (!CONSTANT_P (mby
))
965 if (!CONSTANT_P (mby
))
974 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
978 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
985 if (!iv_extend (&iv0
, code
, mode
))
996 if (!iv_add (&iv0
, &iv1
, code
))
1001 if (!iv_mult (&iv0
, mby
))
1006 if (!iv_shift (&iv0
, mby
))
1015 return iv
->base
!= NULL_RTX
;
1018 /* Analyzes iv DEF and stores the result to *IV. */
1021 iv_analyze_def (struct df_ref
*def
, struct rtx_iv
*iv
)
1023 rtx insn
= DF_REF_INSN (def
);
1024 rtx reg
= DF_REF_REG (def
);
1029 fprintf (dump_file
, "Analysing def of ");
1030 print_rtl (dump_file
, reg
);
1031 fprintf (dump_file
, " in insn ");
1032 print_rtl_single (dump_file
, insn
);
1035 if (DF_REF_IV (def
))
1038 fprintf (dump_file
, " already analysed.\n");
1039 *iv
= *DF_REF_IV (def
);
1040 return iv
->base
!= NULL_RTX
;
1043 iv
->mode
= VOIDmode
;
1044 iv
->base
= NULL_RTX
;
1045 iv
->step
= NULL_RTX
;
1047 set
= single_set (insn
);
1048 if (!set
|| SET_DEST (set
) != reg
)
1051 rhs
= find_reg_equal_equiv_note (insn
);
1053 rhs
= XEXP (rhs
, 0);
1055 rhs
= SET_SRC (set
);
1057 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1058 record_iv (def
, iv
);
1062 print_rtl (dump_file
, reg
);
1063 fprintf (dump_file
, " in insn ");
1064 print_rtl_single (dump_file
, insn
);
1065 fprintf (dump_file
, " is ");
1066 dump_iv_info (dump_file
, iv
);
1067 fprintf (dump_file
, "\n");
1070 return iv
->base
!= NULL_RTX
;
1073 /* Analyzes operand OP of INSN and stores the result to *IV. */
1076 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1078 struct df_ref
*def
= NULL
;
1079 enum iv_grd_result res
;
1083 fprintf (dump_file
, "Analysing operand ");
1084 print_rtl (dump_file
, op
);
1085 fprintf (dump_file
, " of insn ");
1086 print_rtl_single (dump_file
, insn
);
1089 if (CONSTANT_P (op
))
1090 res
= GRD_INVARIANT
;
1091 else if (GET_CODE (op
) == SUBREG
)
1093 if (!subreg_lowpart_p (op
))
1096 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1099 return iv_subreg (iv
, GET_MODE (op
));
1103 res
= iv_get_reaching_def (insn
, op
, &def
);
1104 if (res
== GRD_INVALID
)
1107 fprintf (dump_file
, " not simple.\n");
1112 if (res
== GRD_INVARIANT
)
1114 iv_constant (iv
, op
, VOIDmode
);
1118 fprintf (dump_file
, " ");
1119 dump_iv_info (dump_file
, iv
);
1120 fprintf (dump_file
, "\n");
1125 if (res
== GRD_MAYBE_BIV
)
1126 return iv_analyze_biv (op
, iv
);
1128 return iv_analyze_def (def
, iv
);
1131 /* Analyzes value VAL at INSN and stores the result to *IV. */
1134 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
1138 /* We must find the insn in that val is used, so that we get to UD chains.
1139 Since the function is sometimes called on result of get_condition,
1140 this does not necessarily have to be directly INSN; scan also the
1142 if (simple_reg_p (val
))
1144 if (GET_CODE (val
) == SUBREG
)
1145 reg
= SUBREG_REG (val
);
1149 while (!df_find_use (df
, insn
, reg
))
1150 insn
= NEXT_INSN (insn
);
1153 return iv_analyze_op (insn
, val
, iv
);
1156 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1159 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1161 struct df_ref
*adef
;
1163 adef
= df_find_def (df
, insn
, def
);
1167 return iv_analyze_def (adef
, iv
);
1170 /* Checks whether definition of register REG in INSN is a basic induction
1171 variable. IV analysis must have been initialized (via a call to
1172 iv_analysis_loop_init) for this function to produce a result. */
1175 biv_p (rtx insn
, rtx reg
)
1178 struct df_ref
*def
, *last_def
;
1180 if (!simple_reg_p (reg
))
1183 def
= df_find_def (df
, insn
, reg
);
1184 gcc_assert (def
!= NULL
);
1185 if (!latch_dominating_def (reg
, &last_def
))
1187 if (last_def
!= def
)
1190 if (!iv_analyze_biv (reg
, &iv
))
1193 return iv
.step
!= const0_rtx
;
1196 /* Calculates value of IV at ITERATION-th iteration. */
1199 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1203 /* We would need to generate some if_then_else patterns, and so far
1204 it is not needed anywhere. */
1205 gcc_assert (!iv
->first_special
);
1207 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1208 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1209 simplify_gen_binary (MULT
, iv
->extend_mode
,
1210 iv
->step
, iteration
));
1214 if (iv
->extend_mode
== iv
->mode
)
1217 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1219 if (iv
->extend
== UNKNOWN
)
1222 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1223 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1224 simplify_gen_binary (MULT
, iv
->extend_mode
,
1230 /* Free the data for an induction variable analysis. */
1233 iv_analysis_done (void)
1245 /* Computes inverse to X modulo (1 << MOD). */
1247 static unsigned HOST_WIDEST_INT
1248 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1250 unsigned HOST_WIDEST_INT mask
=
1251 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1252 unsigned HOST_WIDEST_INT rslt
= 1;
1255 for (i
= 0; i
< mod
- 1; i
++)
1257 rslt
= (rslt
* x
) & mask
;
1264 /* Tries to estimate the maximum number of iterations. */
1266 static unsigned HOST_WIDEST_INT
1267 determine_max_iter (struct niter_desc
*desc
)
1269 rtx niter
= desc
->niter_expr
;
1270 rtx mmin
, mmax
, left
, right
;
1271 unsigned HOST_WIDEST_INT nmax
, inc
;
1273 if (GET_CODE (niter
) == AND
1274 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
1276 nmax
= INTVAL (XEXP (niter
, 0));
1277 if (!(nmax
& (nmax
+ 1)))
1279 desc
->niter_max
= nmax
;
1284 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
1285 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1287 if (GET_CODE (niter
) == UDIV
)
1289 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
1291 desc
->niter_max
= nmax
;
1294 inc
= INTVAL (XEXP (niter
, 1));
1295 niter
= XEXP (niter
, 0);
1300 if (GET_CODE (niter
) == PLUS
)
1302 left
= XEXP (niter
, 0);
1303 right
= XEXP (niter
, 0);
1305 if (GET_CODE (right
) == CONST_INT
)
1306 right
= GEN_INT (-INTVAL (right
));
1308 else if (GET_CODE (niter
) == MINUS
)
1310 left
= XEXP (niter
, 0);
1311 right
= XEXP (niter
, 0);
1319 if (GET_CODE (left
) == CONST_INT
)
1321 if (GET_CODE (right
) == CONST_INT
)
1323 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1325 desc
->niter_max
= nmax
/ inc
;
1329 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1332 altered_reg_used (rtx
*reg
, void *alt
)
1337 return REGNO_REG_SET_P (alt
, REGNO (*reg
));
1340 /* Marks registers altered by EXPR in set ALT. */
1343 mark_altered (rtx expr
, rtx by ATTRIBUTE_UNUSED
, void *alt
)
1345 if (GET_CODE (expr
) == SUBREG
)
1346 expr
= SUBREG_REG (expr
);
1350 SET_REGNO_REG_SET (alt
, REGNO (expr
));
1353 /* Checks whether RHS is simple enough to process. */
1356 simple_rhs_p (rtx rhs
)
1360 if (CONSTANT_P (rhs
)
1364 switch (GET_CODE (rhs
))
1368 op0
= XEXP (rhs
, 0);
1369 op1
= XEXP (rhs
, 1);
1370 /* Allow reg + const sets only. */
1371 if (REG_P (op0
) && CONSTANT_P (op1
))
1373 if (REG_P (op1
) && CONSTANT_P (op0
))
1383 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1387 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1389 rtx set
= single_set (insn
);
1390 rtx lhs
= NULL_RTX
, rhs
;
1395 lhs
= SET_DEST (set
);
1397 || altered_reg_used (&lhs
, altered
))
1403 note_stores (PATTERN (insn
), mark_altered
, altered
);
1407 HARD_REG_SET clobbered_regs
;
1409 /* Kill all call clobbered registers. */
1410 get_call_invalidated_used_regs (insn
, &clobbered_regs
, true);
1411 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1412 if (TEST_HARD_REG_BIT (clobbered_regs
, i
))
1413 SET_REGNO_REG_SET (altered
, i
);
1419 rhs
= find_reg_equal_equiv_note (insn
);
1421 rhs
= XEXP (rhs
, 0);
1423 rhs
= SET_SRC (set
);
1425 if (!simple_rhs_p (rhs
))
1428 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1431 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1434 /* Checks whether A implies B. */
1437 implies_p (rtx a
, rtx b
)
1439 rtx op0
, op1
, opb0
, opb1
, r
;
1440 enum machine_mode mode
;
1442 if (GET_CODE (a
) == EQ
)
1449 r
= simplify_replace_rtx (b
, op0
, op1
);
1450 if (r
== const_true_rtx
)
1456 r
= simplify_replace_rtx (b
, op1
, op0
);
1457 if (r
== const_true_rtx
)
1462 /* A < B implies A + 1 <= B. */
1463 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1464 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1471 if (GET_CODE (a
) == GT
)
1478 if (GET_CODE (b
) == GE
)
1485 mode
= GET_MODE (op0
);
1486 if (mode
!= GET_MODE (opb0
))
1488 else if (mode
== VOIDmode
)
1490 mode
= GET_MODE (op1
);
1491 if (mode
!= GET_MODE (opb1
))
1495 if (SCALAR_INT_MODE_P (mode
)
1496 && rtx_equal_p (op1
, opb1
)
1497 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1504 /* Canonicalizes COND so that
1506 (1) Ensure that operands are ordered according to
1507 swap_commutative_operands_p.
1508 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1509 for GE, GEU, and LEU. */
1512 canon_condition (rtx cond
)
1517 enum machine_mode mode
;
1519 code
= GET_CODE (cond
);
1520 op0
= XEXP (cond
, 0);
1521 op1
= XEXP (cond
, 1);
1523 if (swap_commutative_operands_p (op0
, op1
))
1525 code
= swap_condition (code
);
1531 mode
= GET_MODE (op0
);
1532 if (mode
== VOIDmode
)
1533 mode
= GET_MODE (op1
);
1534 gcc_assert (mode
!= VOIDmode
);
1536 if (GET_CODE (op1
) == CONST_INT
1537 && GET_MODE_CLASS (mode
) != MODE_CC
1538 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1540 HOST_WIDE_INT const_val
= INTVAL (op1
);
1541 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1542 unsigned HOST_WIDE_INT max_val
1543 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1548 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1549 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1552 /* When cross-compiling, const_val might be sign-extended from
1553 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1555 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1556 != (((HOST_WIDE_INT
) 1
1557 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1558 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1562 if (uconst_val
< max_val
)
1563 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1567 if (uconst_val
!= 0)
1568 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1576 if (op0
!= XEXP (cond
, 0)
1577 || op1
!= XEXP (cond
, 1)
1578 || code
!= GET_CODE (cond
)
1579 || GET_MODE (cond
) != SImode
)
1580 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1585 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1586 set of altered regs. */
1589 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1591 rtx rev
, reve
, exp
= *expr
;
1593 if (!COMPARISON_P (exp
))
1596 /* If some register gets altered later, we do not really speak about its
1597 value at the time of comparison. */
1599 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1602 rev
= reversed_condition (cond
);
1603 reve
= reversed_condition (exp
);
1605 cond
= canon_condition (cond
);
1606 exp
= canon_condition (exp
);
1608 rev
= canon_condition (rev
);
1610 reve
= canon_condition (reve
);
1612 if (rtx_equal_p (exp
, cond
))
1614 *expr
= const_true_rtx
;
1619 if (rev
&& rtx_equal_p (exp
, rev
))
1625 if (implies_p (cond
, exp
))
1627 *expr
= const_true_rtx
;
1631 if (reve
&& implies_p (cond
, reve
))
1637 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1639 if (rev
&& implies_p (exp
, rev
))
1645 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1646 if (rev
&& reve
&& implies_p (reve
, rev
))
1648 *expr
= const_true_rtx
;
1652 /* We would like to have some other tests here. TODO. */
1657 /* Use relationship between A and *B to eventually eliminate *B.
1658 OP is the operation we consider. */
1661 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1666 /* If A implies *B, we may replace *B by true. */
1667 if (implies_p (a
, *b
))
1668 *b
= const_true_rtx
;
1672 /* If *B implies A, we may replace *B by false. */
1673 if (implies_p (*b
, a
))
1682 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1683 operation we consider. */
1686 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1690 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1691 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1692 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1693 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1696 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1697 is a list, its elements are assumed to be combined using OP. */
1700 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1702 rtx head
, tail
, insn
;
1710 if (CONSTANT_P (*expr
))
1713 if (GET_CODE (*expr
) == EXPR_LIST
)
1715 head
= XEXP (*expr
, 0);
1716 tail
= XEXP (*expr
, 1);
1718 eliminate_implied_conditions (op
, &head
, tail
);
1723 neutral
= const_true_rtx
;
1728 neutral
= const0_rtx
;
1729 aggr
= const_true_rtx
;
1736 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1739 XEXP (*expr
, 0) = aggr
;
1740 XEXP (*expr
, 1) = NULL_RTX
;
1743 else if (head
== neutral
)
1746 simplify_using_initial_values (loop
, op
, expr
);
1749 simplify_using_initial_values (loop
, op
, &tail
);
1751 if (tail
&& XEXP (tail
, 0) == aggr
)
1757 XEXP (*expr
, 0) = head
;
1758 XEXP (*expr
, 1) = tail
;
1762 gcc_assert (op
== UNKNOWN
);
1764 e
= loop_preheader_edge (loop
);
1765 if (e
->src
== ENTRY_BLOCK_PTR
)
1768 altered
= ALLOC_REG_SET (®_obstack
);
1772 insn
= BB_END (e
->src
);
1773 if (any_condjump_p (insn
))
1775 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1777 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1778 cond
= reversed_condition (cond
);
1781 simplify_using_condition (cond
, expr
, altered
);
1782 if (CONSTANT_P (*expr
))
1784 FREE_REG_SET (altered
);
1790 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1795 simplify_using_assignment (insn
, expr
, altered
);
1796 if (CONSTANT_P (*expr
))
1798 FREE_REG_SET (altered
);
1803 if (!single_pred_p (e
->src
)
1804 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
1806 e
= single_pred_edge (e
->src
);
1809 FREE_REG_SET (altered
);
1812 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1813 that IV occurs as left operands of comparison COND and its signedness
1814 is SIGNED_P to DESC. */
1817 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1818 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1820 rtx mmin
, mmax
, cond_over
, cond_under
;
1822 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1823 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1825 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1834 if (cond_under
!= const0_rtx
)
1836 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1837 if (cond_over
!= const0_rtx
)
1838 desc
->noloop_assumptions
=
1839 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1846 if (cond_over
!= const0_rtx
)
1848 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1849 if (cond_under
!= const0_rtx
)
1850 desc
->noloop_assumptions
=
1851 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1855 if (cond_over
!= const0_rtx
)
1857 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1858 if (cond_under
!= const0_rtx
)
1860 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1868 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1871 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1872 subregs of the same mode if possible (sometimes it is necessary to add
1873 some assumptions to DESC). */
1876 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1877 enum rtx_code cond
, struct niter_desc
*desc
)
1879 enum machine_mode comp_mode
;
1882 /* If the ivs behave specially in the first iteration, or are
1883 added/multiplied after extending, we ignore them. */
1884 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1886 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1889 /* If there is some extend, it must match signedness of the comparison. */
1894 if (iv0
->extend
== ZERO_EXTEND
1895 || iv1
->extend
== ZERO_EXTEND
)
1902 if (iv0
->extend
== SIGN_EXTEND
1903 || iv1
->extend
== SIGN_EXTEND
)
1909 if (iv0
->extend
!= UNKNOWN
1910 && iv1
->extend
!= UNKNOWN
1911 && iv0
->extend
!= iv1
->extend
)
1915 if (iv0
->extend
!= UNKNOWN
)
1916 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1917 if (iv1
->extend
!= UNKNOWN
)
1918 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1925 /* Values of both variables should be computed in the same mode. These
1926 might indeed be different, if we have comparison like
1928 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1930 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1931 in different modes. This does not seem impossible to handle, but
1932 it hardly ever occurs in practice.
1934 The only exception is the case when one of operands is invariant.
1935 For example pentium 3 generates comparisons like
1936 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1937 definitely do not want this prevent the optimization. */
1938 comp_mode
= iv0
->extend_mode
;
1939 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1940 comp_mode
= iv1
->extend_mode
;
1942 if (iv0
->extend_mode
!= comp_mode
)
1944 if (iv0
->mode
!= iv0
->extend_mode
1945 || iv0
->step
!= const0_rtx
)
1948 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1949 comp_mode
, iv0
->base
, iv0
->mode
);
1950 iv0
->extend_mode
= comp_mode
;
1953 if (iv1
->extend_mode
!= comp_mode
)
1955 if (iv1
->mode
!= iv1
->extend_mode
1956 || iv1
->step
!= const0_rtx
)
1959 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1960 comp_mode
, iv1
->base
, iv1
->mode
);
1961 iv1
->extend_mode
= comp_mode
;
1964 /* Check that both ivs belong to a range of a single mode. If one of the
1965 operands is an invariant, we may need to shorten it into the common
1967 if (iv0
->mode
== iv0
->extend_mode
1968 && iv0
->step
== const0_rtx
1969 && iv0
->mode
!= iv1
->mode
)
1970 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
1972 if (iv1
->mode
== iv1
->extend_mode
1973 && iv1
->step
== const0_rtx
1974 && iv0
->mode
!= iv1
->mode
)
1975 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
1977 if (iv0
->mode
!= iv1
->mode
)
1980 desc
->mode
= iv0
->mode
;
1981 desc
->signed_p
= signed_p
;
1986 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1987 the result into DESC. Very similar to determine_number_of_iterations
1988 (basically its rtl version), complicated by things like subregs. */
1991 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
1992 struct niter_desc
*desc
)
1994 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
1995 struct rtx_iv iv0
, iv1
, tmp_iv
;
1996 rtx assumption
, may_not_xform
;
1998 enum machine_mode mode
, comp_mode
;
1999 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2000 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2001 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2002 int was_sharp
= false;
2006 /* The meaning of these assumptions is this:
2008 then the rest of information does not have to be valid
2009 if noloop_assumptions then the loop does not roll
2010 if infinite then this exit is never used */
2012 desc
->assumptions
= NULL_RTX
;
2013 desc
->noloop_assumptions
= NULL_RTX
;
2014 desc
->infinite
= NULL_RTX
;
2015 desc
->simple_p
= true;
2017 desc
->const_iter
= false;
2018 desc
->niter_expr
= NULL_RTX
;
2019 desc
->niter_max
= 0;
2021 cond
= GET_CODE (condition
);
2022 gcc_assert (COMPARISON_P (condition
));
2024 mode
= GET_MODE (XEXP (condition
, 0));
2025 if (mode
== VOIDmode
)
2026 mode
= GET_MODE (XEXP (condition
, 1));
2027 /* The constant comparisons should be folded. */
2028 gcc_assert (mode
!= VOIDmode
);
2030 /* We only handle integers or pointers. */
2031 if (GET_MODE_CLASS (mode
) != MODE_INT
2032 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2035 op0
= XEXP (condition
, 0);
2036 if (!iv_analyze (insn
, op0
, &iv0
))
2038 if (iv0
.extend_mode
== VOIDmode
)
2039 iv0
.mode
= iv0
.extend_mode
= mode
;
2041 op1
= XEXP (condition
, 1);
2042 if (!iv_analyze (insn
, op1
, &iv1
))
2044 if (iv1
.extend_mode
== VOIDmode
)
2045 iv1
.mode
= iv1
.extend_mode
= mode
;
2047 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2048 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2051 /* Check condition and normalize it. */
2059 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2060 cond
= swap_condition (cond
);
2072 /* Handle extends. This is relatively nontrivial, so we only try in some
2073 easy cases, when we can canonicalize the ivs (possibly by adding some
2074 assumptions) to shape subreg (base + i * step). This function also fills
2075 in desc->mode and desc->signed_p. */
2077 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2080 comp_mode
= iv0
.extend_mode
;
2082 size
= GET_MODE_BITSIZE (mode
);
2083 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2084 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2085 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2087 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2090 /* We can take care of the case of two induction variables chasing each other
2091 if the test is NE. I have never seen a loop using it, but still it is
2093 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2098 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2099 iv1
.step
= const0_rtx
;
2102 /* This is either infinite loop or the one that ends immediately, depending
2103 on initial values. Unswitching should remove this kind of conditions. */
2104 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2109 if (iv0
.step
== const0_rtx
)
2110 step_val
= -INTVAL (iv1
.step
);
2112 step_val
= INTVAL (iv0
.step
);
2114 /* Ignore loops of while (i-- < 10) type. */
2118 step_is_pow2
= !(step_val
& (step_val
- 1));
2122 /* We do not care about whether the step is power of two in this
2124 step_is_pow2
= false;
2128 /* Some more condition normalization. We must record some assumptions
2129 due to overflows. */
2134 /* We want to take care only of non-sharp relationals; this is easy,
2135 as in cases the overflow would make the transformation unsafe
2136 the loop does not roll. Seemingly it would make more sense to want
2137 to take care of sharp relationals instead, as NE is more similar to
2138 them, but the problem is that here the transformation would be more
2139 difficult due to possibly infinite loops. */
2140 if (iv0
.step
== const0_rtx
)
2142 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2143 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2145 if (assumption
== const_true_rtx
)
2146 goto zero_iter_simplify
;
2147 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2148 iv0
.base
, const1_rtx
);
2152 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2153 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2155 if (assumption
== const_true_rtx
)
2156 goto zero_iter_simplify
;
2157 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2158 iv1
.base
, constm1_rtx
);
2161 if (assumption
!= const0_rtx
)
2162 desc
->noloop_assumptions
=
2163 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2164 cond
= (cond
== LT
) ? LE
: LEU
;
2166 /* It will be useful to be able to tell the difference once more in
2167 LE -> NE reduction. */
2173 /* Take care of trivially infinite loops. */
2176 if (iv0
.step
== const0_rtx
)
2178 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2179 if (rtx_equal_p (tmp
, mode_mmin
))
2182 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2183 /* Fill in the remaining fields somehow. */
2184 goto zero_iter_simplify
;
2189 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2190 if (rtx_equal_p (tmp
, mode_mmax
))
2193 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2194 /* Fill in the remaining fields somehow. */
2195 goto zero_iter_simplify
;
2200 /* If we can we want to take care of NE conditions instead of size
2201 comparisons, as they are much more friendly (most importantly
2202 this takes care of special handling of loops with step 1). We can
2203 do it if we first check that upper bound is greater or equal to
2204 lower bound, their difference is constant c modulo step and that
2205 there is not an overflow. */
2208 if (iv0
.step
== const0_rtx
)
2209 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2212 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2213 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2214 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2215 may_xform
= const0_rtx
;
2216 may_not_xform
= const_true_rtx
;
2218 if (GET_CODE (delta
) == CONST_INT
)
2220 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2222 /* A special case. We have transformed condition of type
2223 for (i = 0; i < 4; i += 4)
2225 for (i = 0; i <= 3; i += 4)
2226 obviously if the test for overflow during that transformation
2227 passed, we cannot overflow here. Most importantly any
2228 loop with sharp end condition and step 1 falls into this
2229 category, so handling this case specially is definitely
2230 worth the troubles. */
2231 may_xform
= const_true_rtx
;
2233 else if (iv0
.step
== const0_rtx
)
2235 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2236 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2237 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2238 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2239 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2241 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2247 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2248 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2249 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2250 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2251 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2253 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2259 if (may_xform
!= const0_rtx
)
2261 /* We perform the transformation always provided that it is not
2262 completely senseless. This is OK, as we would need this assumption
2263 to determine the number of iterations anyway. */
2264 if (may_xform
!= const_true_rtx
)
2266 /* If the step is a power of two and the final value we have
2267 computed overflows, the cycle is infinite. Otherwise it
2268 is nontrivial to compute the number of iterations. */
2270 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2273 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2277 /* We are going to lose some information about upper bound on
2278 number of iterations in this step, so record the information
2280 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2281 if (GET_CODE (iv1
.base
) == CONST_INT
)
2282 up
= INTVAL (iv1
.base
);
2284 up
= INTVAL (mode_mmax
) - inc
;
2285 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2288 desc
->niter_max
= (up
- down
) / inc
+ 1;
2290 if (iv0
.step
== const0_rtx
)
2292 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2293 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2297 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2298 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2301 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2302 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2303 assumption
= simplify_gen_relational (reverse_condition (cond
),
2304 SImode
, mode
, tmp0
, tmp1
);
2305 if (assumption
== const_true_rtx
)
2306 goto zero_iter_simplify
;
2307 else if (assumption
!= const0_rtx
)
2308 desc
->noloop_assumptions
=
2309 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2314 /* Count the number of iterations. */
2317 /* Everything we do here is just arithmetics modulo size of mode. This
2318 makes us able to do more involved computations of number of iterations
2319 than in other cases. First transform the condition into shape
2320 s * i <> c, with s positive. */
2321 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2322 iv0
.base
= const0_rtx
;
2323 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2324 iv1
.step
= const0_rtx
;
2325 if (INTVAL (iv0
.step
) < 0)
2327 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2328 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2330 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2332 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2333 is infinite. Otherwise, the number of iterations is
2334 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2335 s
= INTVAL (iv0
.step
); d
= 1;
2342 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2344 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2345 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2346 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2347 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2349 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2350 inv
= inverse (s
, size
);
2351 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2352 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2356 if (iv1
.step
== const0_rtx
)
2357 /* Condition in shape a + s * i <= b
2358 We must know that b + s does not overflow and a <= b + s and then we
2359 can compute number of iterations as (b + s - a) / s. (It might
2360 seem that we in fact could be more clever about testing the b + s
2361 overflow condition using some information about b - a mod s,
2362 but it was already taken into account during LE -> NE transform). */
2365 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2366 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2368 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2369 lowpart_subreg (mode
, step
,
2375 /* If s is power of 2, we know that the loop is infinite if
2376 a % s <= b % s and b + s overflows. */
2377 assumption
= simplify_gen_relational (reverse_condition (cond
),
2381 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2382 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2383 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2384 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2386 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2390 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2393 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2396 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2397 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2398 assumption
= simplify_gen_relational (reverse_condition (cond
),
2399 SImode
, mode
, tmp0
, tmp
);
2401 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2402 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2406 /* Condition in shape a <= b - s * i
2407 We must know that a - s does not overflow and a - s <= b and then
2408 we can again compute number of iterations as (b - (a - s)) / s. */
2409 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2410 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2411 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2413 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2414 lowpart_subreg (mode
, step
, comp_mode
));
2419 /* If s is power of 2, we know that the loop is infinite if
2420 a % s <= b % s and a - s overflows. */
2421 assumption
= simplify_gen_relational (reverse_condition (cond
),
2425 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2426 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2427 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2428 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2430 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2434 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2437 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2440 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2441 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2442 assumption
= simplify_gen_relational (reverse_condition (cond
),
2445 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2446 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2448 if (assumption
== const_true_rtx
)
2449 goto zero_iter_simplify
;
2450 else if (assumption
!= const0_rtx
)
2451 desc
->noloop_assumptions
=
2452 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2453 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2454 desc
->niter_expr
= delta
;
2457 old_niter
= desc
->niter_expr
;
2459 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2460 if (desc
->assumptions
2461 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2463 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2464 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2465 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2467 /* Rerun the simplification. Consider code (created by copying loop headers)
2479 The first pass determines that i = 0, the second pass uses it to eliminate
2480 noloop assumption. */
2482 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2483 if (desc
->assumptions
2484 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2486 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2487 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2488 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2490 if (desc
->noloop_assumptions
2491 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2494 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2496 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2498 desc
->const_iter
= true;
2499 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2503 if (!desc
->niter_max
)
2504 desc
->niter_max
= determine_max_iter (desc
);
2506 /* simplify_using_initial_values does a copy propagation on the registers
2507 in the expression for the number of iterations. This prolongs life
2508 ranges of registers and increases register pressure, and usually
2509 brings no gain (and if it happens to do, the cse pass will take care
2510 of it anyway). So prevent this behavior, unless it enabled us to
2511 derive that the number of iterations is a constant. */
2512 desc
->niter_expr
= old_niter
;
2518 /* Simplify the assumptions. */
2519 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2520 if (desc
->assumptions
2521 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2523 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2527 desc
->const_iter
= true;
2529 desc
->niter_max
= 0;
2530 desc
->noloop_assumptions
= NULL_RTX
;
2531 desc
->niter_expr
= const0_rtx
;
2535 desc
->simple_p
= false;
2539 /* Checks whether E is a simple exit from LOOP and stores its description
2543 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2545 basic_block exit_bb
;
2550 desc
->simple_p
= false;
2552 /* It must belong directly to the loop. */
2553 if (exit_bb
->loop_father
!= loop
)
2556 /* It must be tested (at least) once during any iteration. */
2557 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2560 /* It must end in a simple conditional jump. */
2561 if (!any_condjump_p (BB_END (exit_bb
)))
2564 ein
= EDGE_SUCC (exit_bb
, 0);
2566 ein
= EDGE_SUCC (exit_bb
, 1);
2569 desc
->in_edge
= ein
;
2571 /* Test whether the condition is suitable. */
2572 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2575 if (ein
->flags
& EDGE_FALLTHRU
)
2577 condition
= reversed_condition (condition
);
2582 /* Check that we are able to determine number of iterations and fill
2583 in information about it. */
2584 iv_number_of_iterations (loop
, at
, condition
, desc
);
2587 /* Finds a simple exit of LOOP and stores its description into DESC. */
2590 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2595 struct niter_desc act
;
2599 desc
->simple_p
= false;
2600 body
= get_loop_body (loop
);
2602 for (i
= 0; i
< loop
->num_nodes
; i
++)
2604 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2606 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2609 check_simple_exit (loop
, e
, &act
);
2617 /* Prefer constant iterations; the less the better. */
2619 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2622 /* Also if the actual exit may be infinite, while the old one
2623 not, prefer the old one. */
2624 if (act
.infinite
&& !desc
->infinite
)
2636 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2637 fprintf (dump_file
, " simple exit %d -> %d\n",
2638 desc
->out_edge
->src
->index
,
2639 desc
->out_edge
->dest
->index
);
2640 if (desc
->assumptions
)
2642 fprintf (dump_file
, " assumptions: ");
2643 print_rtl (dump_file
, desc
->assumptions
);
2644 fprintf (dump_file
, "\n");
2646 if (desc
->noloop_assumptions
)
2648 fprintf (dump_file
, " does not roll if: ");
2649 print_rtl (dump_file
, desc
->noloop_assumptions
);
2650 fprintf (dump_file
, "\n");
2654 fprintf (dump_file
, " infinite if: ");
2655 print_rtl (dump_file
, desc
->infinite
);
2656 fprintf (dump_file
, "\n");
2659 fprintf (dump_file
, " number of iterations: ");
2660 print_rtl (dump_file
, desc
->niter_expr
);
2661 fprintf (dump_file
, "\n");
2663 fprintf (dump_file
, " upper bound: ");
2664 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2665 fprintf (dump_file
, "\n");
2668 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2674 /* Creates a simple loop description of LOOP if it was not computed
2678 get_simple_loop_desc (struct loop
*loop
)
2680 struct niter_desc
*desc
= simple_loop_desc (loop
);
2685 desc
= XNEW (struct niter_desc
);
2686 iv_analysis_loop_init (loop
);
2687 find_simple_exit (loop
, desc
);
2690 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
2692 const char *wording
;
2694 /* Assume that no overflow happens and that the loop is finite.
2695 We already warned at the tree level if we ran optimizations there. */
2696 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
2701 flag_unsafe_loop_optimizations
2702 ? N_("assuming that the loop is not infinite")
2703 : N_("cannot optimize possibly infinite loops");
2704 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2707 if (desc
->assumptions
)
2710 flag_unsafe_loop_optimizations
2711 ? N_("assuming that the loop counter does not overflow")
2712 : N_("cannot optimize loop, the loop counter may overflow");
2713 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2718 if (flag_unsafe_loop_optimizations
)
2720 desc
->assumptions
= NULL_RTX
;
2721 desc
->infinite
= NULL_RTX
;
2728 /* Releases simple loop description for LOOP. */
2731 free_simple_loop_desc (struct loop
*loop
)
2733 struct niter_desc
*desc
= simple_loop_desc (loop
);