1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004, 2005, 2006, 2007 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.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
57 #include "basic-block.h"
66 /* Possible return values of iv_get_reaching_def. */
70 /* More than one reaching def, or reaching def that does not
74 /* The use is trivial invariant of the loop, i.e. is not changed
78 /* The use is reached by initial value and a value from the
79 previous iteration. */
82 /* The use has single dominating def. */
86 /* Information about a biv. */
90 unsigned regno
; /* The register of the biv. */
91 struct rtx_iv iv
; /* Value of the biv. */
94 static bool clean_slate
= true;
96 static unsigned int iv_ref_table_size
= 0;
98 /* Table of rtx_ivs indexed by the df_ref uid field. */
99 static struct rtx_iv
** iv_ref_table
;
101 /* Induction variable stored at the reference. */
102 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
103 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
105 /* The current loop. */
107 static struct loop
*current_loop
;
109 /* Bivs of the current loop. */
113 static bool iv_analyze_op (rtx
, rtx
, struct rtx_iv
*);
115 /* Dumps information about IV to FILE. */
117 extern void dump_iv_info (FILE *, struct rtx_iv
*);
119 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
123 fprintf (file
, "not simple");
127 if (iv
->step
== const0_rtx
128 && !iv
->first_special
)
129 fprintf (file
, "invariant ");
131 print_rtl (file
, iv
->base
);
132 if (iv
->step
!= const0_rtx
)
134 fprintf (file
, " + ");
135 print_rtl (file
, iv
->step
);
136 fprintf (file
, " * iteration");
138 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
140 if (iv
->mode
!= iv
->extend_mode
)
141 fprintf (file
, " %s to %s",
142 rtx_name
[iv
->extend
],
143 GET_MODE_NAME (iv
->extend_mode
));
145 if (iv
->mult
!= const1_rtx
)
147 fprintf (file
, " * ");
148 print_rtl (file
, iv
->mult
);
150 if (iv
->delta
!= const0_rtx
)
152 fprintf (file
, " + ");
153 print_rtl (file
, iv
->delta
);
155 if (iv
->first_special
)
156 fprintf (file
, " (first special)");
159 /* Generates a subreg to get the least significant part of EXPR (in mode
160 INNER_MODE) to OUTER_MODE. */
163 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
164 enum machine_mode inner_mode
)
166 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
167 subreg_lowpart_offset (outer_mode
, inner_mode
));
171 check_iv_ref_table_size (void)
173 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE())
175 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
176 iv_ref_table
= xrealloc (iv_ref_table
,
177 sizeof (struct rtx_iv
*) * new_size
);
178 memset (&iv_ref_table
[iv_ref_table_size
], 0,
179 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
180 iv_ref_table_size
= new_size
;
185 /* Checks whether REG is a well-behaved register. */
188 simple_reg_p (rtx reg
)
192 if (GET_CODE (reg
) == SUBREG
)
194 if (!subreg_lowpart_p (reg
))
196 reg
= SUBREG_REG (reg
);
203 if (HARD_REGISTER_NUM_P (r
))
206 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
212 /* Clears the information about ivs stored in df. */
217 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
220 check_iv_ref_table_size ();
221 for (i
= 0; i
< n_defs
; i
++)
223 iv
= iv_ref_table
[i
];
227 iv_ref_table
[i
] = NULL
;
234 /* Returns hash value for biv B. */
237 biv_hash (const void *b
)
239 return ((const struct biv_entry
*) b
)->regno
;
242 /* Compares biv B and register R. */
245 biv_eq (const void *b
, const void *r
)
247 return ((const struct biv_entry
*) b
)->regno
== REGNO ((rtx
) r
);
250 /* Prepare the data for an induction variable analysis of a LOOP. */
253 iv_analysis_loop_init (struct loop
*loop
)
255 basic_block
*body
= get_loop_body_in_dom_order (loop
), bb
;
256 bitmap blocks
= BITMAP_ALLOC (NULL
);
261 /* Clear the information from the analysis of the previous loop. */
264 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
265 bivs
= htab_create (10, biv_hash
, biv_eq
, free
);
271 for (i
= 0; i
< loop
->num_nodes
; i
++)
274 bitmap_set_bit (blocks
, bb
->index
);
276 /* Get rid of the ud chains before processing the rescans. Then add
278 df_remove_problem (df_chain
);
279 df_process_deferred_rescans ();
280 df_chain_add_problem (DF_UD_CHAIN
);
281 df_set_blocks (blocks
);
286 check_iv_ref_table_size ();
287 BITMAP_FREE (blocks
);
291 /* Finds the definition of REG that dominates loop latch and stores
292 it to DEF. Returns false if there is not a single definition
293 dominating the latch. If REG has no definition in loop, DEF
294 is set to NULL and true is returned. */
297 latch_dominating_def (rtx reg
, struct df_ref
**def
)
299 struct df_ref
*single_rd
= NULL
, *adef
;
300 unsigned regno
= REGNO (reg
);
301 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
303 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= adef
->next_reg
)
305 if (!bitmap_bit_p (bb_info
->out
, DF_REF_ID (adef
)))
308 /* More than one reaching definition. */
312 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
322 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
324 static enum iv_grd_result
325 iv_get_reaching_def (rtx insn
, rtx reg
, struct df_ref
**def
)
327 struct df_ref
*use
, *adef
;
328 basic_block def_bb
, use_bb
;
333 if (!simple_reg_p (reg
))
335 if (GET_CODE (reg
) == SUBREG
)
336 reg
= SUBREG_REG (reg
);
337 gcc_assert (REG_P (reg
));
339 use
= df_find_use (insn
, reg
);
340 gcc_assert (use
!= NULL
);
342 if (!DF_REF_CHAIN (use
))
343 return GRD_INVARIANT
;
345 /* More than one reaching def. */
346 if (DF_REF_CHAIN (use
)->next
)
349 adef
= DF_REF_CHAIN (use
)->ref
;
350 def_insn
= DF_REF_INSN (adef
);
351 def_bb
= DF_REF_BB (adef
);
352 use_bb
= BLOCK_FOR_INSN (insn
);
354 if (use_bb
== def_bb
)
355 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
357 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
362 return GRD_SINGLE_DOM
;
365 /* The definition does not dominate the use. This is still OK if
366 this may be a use of a biv, i.e. if the def_bb dominates loop
368 if (just_once_each_iteration_p (current_loop
, def_bb
))
369 return GRD_MAYBE_BIV
;
374 /* Sets IV to invariant CST in MODE. Always returns true (just for
375 consistency with other iv manipulation functions that may fail). */
378 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
380 if (mode
== VOIDmode
)
381 mode
= GET_MODE (cst
);
385 iv
->step
= const0_rtx
;
386 iv
->first_special
= false;
387 iv
->extend
= UNKNOWN
;
388 iv
->extend_mode
= iv
->mode
;
389 iv
->delta
= const0_rtx
;
390 iv
->mult
= const1_rtx
;
395 /* Evaluates application of subreg to MODE on IV. */
398 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
400 /* If iv is invariant, just calculate the new value. */
401 if (iv
->step
== const0_rtx
402 && !iv
->first_special
)
404 rtx val
= get_iv_value (iv
, const0_rtx
);
405 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
408 iv
->extend
= UNKNOWN
;
409 iv
->mode
= iv
->extend_mode
= mode
;
410 iv
->delta
= const0_rtx
;
411 iv
->mult
= const1_rtx
;
415 if (iv
->extend_mode
== mode
)
418 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
421 iv
->extend
= UNKNOWN
;
424 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
425 simplify_gen_binary (MULT
, iv
->extend_mode
,
426 iv
->base
, iv
->mult
));
427 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
428 iv
->mult
= const1_rtx
;
429 iv
->delta
= const0_rtx
;
430 iv
->first_special
= false;
435 /* Evaluates application of EXTEND to MODE on IV. */
438 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
440 /* If iv is invariant, just calculate the new value. */
441 if (iv
->step
== const0_rtx
442 && !iv
->first_special
)
444 rtx val
= get_iv_value (iv
, const0_rtx
);
445 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
448 iv
->extend
= UNKNOWN
;
449 iv
->mode
= iv
->extend_mode
= mode
;
450 iv
->delta
= const0_rtx
;
451 iv
->mult
= const1_rtx
;
455 if (mode
!= iv
->extend_mode
)
458 if (iv
->extend
!= UNKNOWN
459 && iv
->extend
!= extend
)
467 /* Evaluates negation of IV. */
470 iv_neg (struct rtx_iv
*iv
)
472 if (iv
->extend
== UNKNOWN
)
474 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
475 iv
->base
, iv
->extend_mode
);
476 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
477 iv
->step
, iv
->extend_mode
);
481 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
482 iv
->delta
, iv
->extend_mode
);
483 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
484 iv
->mult
, iv
->extend_mode
);
490 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
493 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
495 enum machine_mode mode
;
498 /* Extend the constant to extend_mode of the other operand if necessary. */
499 if (iv0
->extend
== UNKNOWN
500 && iv0
->mode
== iv0
->extend_mode
501 && iv0
->step
== const0_rtx
502 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
504 iv0
->extend_mode
= iv1
->extend_mode
;
505 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
506 iv0
->base
, iv0
->mode
);
508 if (iv1
->extend
== UNKNOWN
509 && iv1
->mode
== iv1
->extend_mode
510 && iv1
->step
== const0_rtx
511 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
513 iv1
->extend_mode
= iv0
->extend_mode
;
514 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
515 iv1
->base
, iv1
->mode
);
518 mode
= iv0
->extend_mode
;
519 if (mode
!= iv1
->extend_mode
)
522 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
524 if (iv0
->mode
!= iv1
->mode
)
527 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
528 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
533 /* Handle addition of constant. */
534 if (iv1
->extend
== UNKNOWN
536 && iv1
->step
== const0_rtx
)
538 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
542 if (iv0
->extend
== UNKNOWN
544 && iv0
->step
== const0_rtx
)
552 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
559 /* Evaluates multiplication of IV by constant CST. */
562 iv_mult (struct rtx_iv
*iv
, rtx mby
)
564 enum machine_mode mode
= iv
->extend_mode
;
566 if (GET_MODE (mby
) != VOIDmode
567 && GET_MODE (mby
) != mode
)
570 if (iv
->extend
== UNKNOWN
)
572 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
573 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
577 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
578 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
584 /* Evaluates shift of IV by constant CST. */
587 iv_shift (struct rtx_iv
*iv
, rtx mby
)
589 enum machine_mode mode
= iv
->extend_mode
;
591 if (GET_MODE (mby
) != VOIDmode
592 && GET_MODE (mby
) != mode
)
595 if (iv
->extend
== UNKNOWN
)
597 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
598 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
602 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
603 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
609 /* The recursive part of get_biv_step. Gets the value of the single value
610 defined by DEF wrto initial value of REG inside loop, in shape described
614 get_biv_step_1 (struct df_ref
*def
, rtx reg
,
615 rtx
*inner_step
, enum machine_mode
*inner_mode
,
616 enum rtx_code
*extend
, enum machine_mode outer_mode
,
619 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
620 rtx next
, nextr
, tmp
;
622 rtx insn
= DF_REF_INSN (def
);
623 struct df_ref
*next_def
;
624 enum iv_grd_result res
;
626 set
= single_set (insn
);
630 rhs
= find_reg_equal_equiv_note (insn
);
636 code
= GET_CODE (rhs
);
649 if (code
== PLUS
&& CONSTANT_P (op0
))
651 tmp
= op0
; op0
= op1
; op1
= tmp
;
654 if (!simple_reg_p (op0
)
655 || !CONSTANT_P (op1
))
658 if (GET_MODE (rhs
) != outer_mode
)
660 /* ppc64 uses expressions like
662 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
664 this is equivalent to
666 (set x':DI (plus:DI y:DI 1))
667 (set x:SI (subreg:SI (x':DI)). */
668 if (GET_CODE (op0
) != SUBREG
)
670 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
679 if (GET_MODE (rhs
) != outer_mode
)
683 if (!simple_reg_p (op0
))
693 if (GET_CODE (next
) == SUBREG
)
695 if (!subreg_lowpart_p (next
))
698 nextr
= SUBREG_REG (next
);
699 if (GET_MODE (nextr
) != outer_mode
)
705 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
707 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
710 if (res
== GRD_MAYBE_BIV
)
712 if (!rtx_equal_p (nextr
, reg
))
715 *inner_step
= const0_rtx
;
717 *inner_mode
= outer_mode
;
718 *outer_step
= const0_rtx
;
720 else if (!get_biv_step_1 (next_def
, reg
,
721 inner_step
, inner_mode
, extend
, outer_mode
,
725 if (GET_CODE (next
) == SUBREG
)
727 enum machine_mode amode
= GET_MODE (next
);
729 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
733 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
734 *inner_step
, *outer_step
);
735 *outer_step
= const0_rtx
;
747 if (*inner_mode
== outer_mode
748 /* See comment in previous switch. */
749 || GET_MODE (rhs
) != outer_mode
)
750 *inner_step
= simplify_gen_binary (code
, outer_mode
,
753 *outer_step
= simplify_gen_binary (code
, outer_mode
,
759 gcc_assert (GET_MODE (op0
) == *inner_mode
760 && *extend
== UNKNOWN
761 && *outer_step
== const0_rtx
);
773 /* Gets the operation on register REG inside loop, in shape
775 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
777 If the operation cannot be described in this shape, return false.
778 LAST_DEF is the definition of REG that dominates loop latch. */
781 get_biv_step (struct df_ref
*last_def
, rtx reg
, rtx
*inner_step
,
782 enum machine_mode
*inner_mode
, enum rtx_code
*extend
,
783 enum machine_mode
*outer_mode
, rtx
*outer_step
)
785 *outer_mode
= GET_MODE (reg
);
787 if (!get_biv_step_1 (last_def
, reg
,
788 inner_step
, inner_mode
, extend
, *outer_mode
,
792 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= UNKNOWN
));
793 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
798 /* Records information that DEF is induction variable IV. */
801 record_iv (struct df_ref
*def
, struct rtx_iv
*iv
)
803 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
806 check_iv_ref_table_size ();
807 DF_REF_IV_SET (def
, recorded_iv
);
810 /* If DEF was already analyzed for bivness, store the description of the biv to
811 IV and return true. Otherwise return false. */
814 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
816 struct biv_entry
*biv
= htab_find_with_hash (bivs
, def
, REGNO (def
));
826 record_biv (rtx def
, struct rtx_iv
*iv
)
828 struct biv_entry
*biv
= XNEW (struct biv_entry
);
829 void **slot
= htab_find_slot_with_hash (bivs
, def
, REGNO (def
), INSERT
);
831 biv
->regno
= REGNO (def
);
837 /* Determines whether DEF is a biv and if so, stores its description
841 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
843 rtx inner_step
, outer_step
;
844 enum machine_mode inner_mode
, outer_mode
;
845 enum rtx_code extend
;
846 struct df_ref
*last_def
;
850 fprintf (dump_file
, "Analyzing ");
851 print_rtl (dump_file
, def
);
852 fprintf (dump_file
, " for bivness.\n");
857 if (!CONSTANT_P (def
))
860 return iv_constant (iv
, def
, VOIDmode
);
863 if (!latch_dominating_def (def
, &last_def
))
866 fprintf (dump_file
, " not simple.\n");
871 return iv_constant (iv
, def
, VOIDmode
);
873 if (analyzed_for_bivness_p (def
, iv
))
876 fprintf (dump_file
, " already analysed.\n");
877 return iv
->base
!= NULL_RTX
;
880 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
881 &outer_mode
, &outer_step
))
887 /* Loop transforms base to es (base + inner_step) + outer_step,
888 where es means extend of subreg between inner_mode and outer_mode.
889 The corresponding induction variable is
891 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
893 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
894 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
895 iv
->mode
= inner_mode
;
896 iv
->extend_mode
= outer_mode
;
898 iv
->mult
= const1_rtx
;
899 iv
->delta
= outer_step
;
900 iv
->first_special
= inner_mode
!= outer_mode
;
905 fprintf (dump_file
, " ");
906 dump_iv_info (dump_file
, iv
);
907 fprintf (dump_file
, "\n");
910 record_biv (def
, iv
);
911 return iv
->base
!= NULL_RTX
;
914 /* Analyzes expression RHS used at INSN and stores the result to *IV.
915 The mode of the induction variable is MODE. */
918 iv_analyze_expr (rtx insn
, rtx rhs
, enum machine_mode mode
, struct rtx_iv
*iv
)
920 rtx mby
= NULL_RTX
, tmp
;
921 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
922 struct rtx_iv iv0
, iv1
;
923 enum rtx_code code
= GET_CODE (rhs
);
924 enum machine_mode omode
= mode
;
930 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
936 if (!iv_analyze_op (insn
, rhs
, iv
))
939 if (iv
->mode
== VOIDmode
)
942 iv
->extend_mode
= mode
;
958 omode
= GET_MODE (op0
);
970 if (!CONSTANT_P (mby
))
976 if (!CONSTANT_P (mby
))
983 if (!CONSTANT_P (mby
))
992 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
996 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1003 if (!iv_extend (&iv0
, code
, mode
))
1014 if (!iv_add (&iv0
, &iv1
, code
))
1019 if (!iv_mult (&iv0
, mby
))
1024 if (!iv_shift (&iv0
, mby
))
1033 return iv
->base
!= NULL_RTX
;
1036 /* Analyzes iv DEF and stores the result to *IV. */
1039 iv_analyze_def (struct df_ref
*def
, struct rtx_iv
*iv
)
1041 rtx insn
= DF_REF_INSN (def
);
1042 rtx reg
= DF_REF_REG (def
);
1047 fprintf (dump_file
, "Analyzing def of ");
1048 print_rtl (dump_file
, reg
);
1049 fprintf (dump_file
, " in insn ");
1050 print_rtl_single (dump_file
, insn
);
1053 check_iv_ref_table_size ();
1054 if (DF_REF_IV (def
))
1057 fprintf (dump_file
, " already analysed.\n");
1058 *iv
= *DF_REF_IV (def
);
1059 return iv
->base
!= NULL_RTX
;
1062 iv
->mode
= VOIDmode
;
1063 iv
->base
= NULL_RTX
;
1064 iv
->step
= NULL_RTX
;
1069 set
= single_set (insn
);
1073 if (!REG_P (SET_DEST (set
)))
1076 gcc_assert (SET_DEST (set
) == reg
);
1077 rhs
= find_reg_equal_equiv_note (insn
);
1079 rhs
= XEXP (rhs
, 0);
1081 rhs
= SET_SRC (set
);
1083 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1084 record_iv (def
, iv
);
1088 print_rtl (dump_file
, reg
);
1089 fprintf (dump_file
, " in insn ");
1090 print_rtl_single (dump_file
, insn
);
1091 fprintf (dump_file
, " is ");
1092 dump_iv_info (dump_file
, iv
);
1093 fprintf (dump_file
, "\n");
1096 return iv
->base
!= NULL_RTX
;
1099 /* Analyzes operand OP of INSN and stores the result to *IV. */
1102 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1104 struct df_ref
*def
= NULL
;
1105 enum iv_grd_result res
;
1109 fprintf (dump_file
, "Analyzing operand ");
1110 print_rtl (dump_file
, op
);
1111 fprintf (dump_file
, " of insn ");
1112 print_rtl_single (dump_file
, insn
);
1115 if (CONSTANT_P (op
))
1116 res
= GRD_INVARIANT
;
1117 else if (GET_CODE (op
) == SUBREG
)
1119 if (!subreg_lowpart_p (op
))
1122 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1125 return iv_subreg (iv
, GET_MODE (op
));
1129 res
= iv_get_reaching_def (insn
, op
, &def
);
1130 if (res
== GRD_INVALID
)
1133 fprintf (dump_file
, " not simple.\n");
1138 if (res
== GRD_INVARIANT
)
1140 iv_constant (iv
, op
, VOIDmode
);
1144 fprintf (dump_file
, " ");
1145 dump_iv_info (dump_file
, iv
);
1146 fprintf (dump_file
, "\n");
1151 if (res
== GRD_MAYBE_BIV
)
1152 return iv_analyze_biv (op
, iv
);
1154 return iv_analyze_def (def
, iv
);
1157 /* Analyzes value VAL at INSN and stores the result to *IV. */
1160 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
1164 /* We must find the insn in that val is used, so that we get to UD chains.
1165 Since the function is sometimes called on result of get_condition,
1166 this does not necessarily have to be directly INSN; scan also the
1168 if (simple_reg_p (val
))
1170 if (GET_CODE (val
) == SUBREG
)
1171 reg
= SUBREG_REG (val
);
1175 while (!df_find_use (insn
, reg
))
1176 insn
= NEXT_INSN (insn
);
1179 return iv_analyze_op (insn
, val
, iv
);
1182 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1185 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1187 struct df_ref
*adef
;
1189 adef
= df_find_def (insn
, def
);
1193 return iv_analyze_def (adef
, iv
);
1196 /* Checks whether definition of register REG in INSN is a basic induction
1197 variable. IV analysis must have been initialized (via a call to
1198 iv_analysis_loop_init) for this function to produce a result. */
1201 biv_p (rtx insn
, rtx reg
)
1204 struct df_ref
*def
, *last_def
;
1206 if (!simple_reg_p (reg
))
1209 def
= df_find_def (insn
, reg
);
1210 gcc_assert (def
!= NULL
);
1211 if (!latch_dominating_def (reg
, &last_def
))
1213 if (last_def
!= def
)
1216 if (!iv_analyze_biv (reg
, &iv
))
1219 return iv
.step
!= const0_rtx
;
1222 /* Calculates value of IV at ITERATION-th iteration. */
1225 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1229 /* We would need to generate some if_then_else patterns, and so far
1230 it is not needed anywhere. */
1231 gcc_assert (!iv
->first_special
);
1233 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1234 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1235 simplify_gen_binary (MULT
, iv
->extend_mode
,
1236 iv
->step
, iteration
));
1240 if (iv
->extend_mode
== iv
->mode
)
1243 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1245 if (iv
->extend
== UNKNOWN
)
1248 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1249 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1250 simplify_gen_binary (MULT
, iv
->extend_mode
,
1256 /* Free the data for an induction variable analysis. */
1259 iv_analysis_done (void)
1267 free (iv_ref_table
);
1268 iv_ref_table
= NULL
;
1269 iv_ref_table_size
= 0;
1274 /* Computes inverse to X modulo (1 << MOD). */
1276 static unsigned HOST_WIDEST_INT
1277 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1279 unsigned HOST_WIDEST_INT mask
=
1280 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1281 unsigned HOST_WIDEST_INT rslt
= 1;
1284 for (i
= 0; i
< mod
- 1; i
++)
1286 rslt
= (rslt
* x
) & mask
;
1293 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1296 altered_reg_used (rtx
*reg
, void *alt
)
1301 return REGNO_REG_SET_P (alt
, REGNO (*reg
));
1304 /* Marks registers altered by EXPR in set ALT. */
1307 mark_altered (rtx expr
, rtx by ATTRIBUTE_UNUSED
, void *alt
)
1309 if (GET_CODE (expr
) == SUBREG
)
1310 expr
= SUBREG_REG (expr
);
1314 SET_REGNO_REG_SET (alt
, REGNO (expr
));
1317 /* Checks whether RHS is simple enough to process. */
1320 simple_rhs_p (rtx rhs
)
1324 if (CONSTANT_P (rhs
)
1325 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1328 switch (GET_CODE (rhs
))
1332 op0
= XEXP (rhs
, 0);
1333 op1
= XEXP (rhs
, 1);
1334 /* Allow reg + const sets only. */
1335 if (REG_P (op0
) && !HARD_REGISTER_P (op0
) && CONSTANT_P (op1
))
1337 if (REG_P (op1
) && !HARD_REGISTER_P (op1
) && CONSTANT_P (op0
))
1347 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1351 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1353 rtx set
= single_set (insn
);
1354 rtx lhs
= NULL_RTX
, rhs
;
1359 lhs
= SET_DEST (set
);
1361 || altered_reg_used (&lhs
, altered
))
1367 note_stores (PATTERN (insn
), mark_altered
, altered
);
1372 /* Kill all call clobbered registers. */
1373 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1374 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1375 SET_REGNO_REG_SET (altered
, i
);
1381 rhs
= find_reg_equal_equiv_note (insn
);
1383 rhs
= XEXP (rhs
, 0);
1385 rhs
= SET_SRC (set
);
1387 if (!simple_rhs_p (rhs
))
1390 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1393 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1396 /* Checks whether A implies B. */
1399 implies_p (rtx a
, rtx b
)
1401 rtx op0
, op1
, opb0
, opb1
, r
;
1402 enum machine_mode mode
;
1404 if (GET_CODE (a
) == EQ
)
1411 r
= simplify_replace_rtx (b
, op0
, op1
);
1412 if (r
== const_true_rtx
)
1418 r
= simplify_replace_rtx (b
, op1
, op0
);
1419 if (r
== const_true_rtx
)
1424 if (b
== const_true_rtx
)
1427 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1428 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1429 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1430 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1438 mode
= GET_MODE (op0
);
1439 if (mode
!= GET_MODE (opb0
))
1441 else if (mode
== VOIDmode
)
1443 mode
= GET_MODE (op1
);
1444 if (mode
!= GET_MODE (opb1
))
1448 /* A < B implies A + 1 <= B. */
1449 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1450 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1453 if (GET_CODE (a
) == GT
)
1460 if (GET_CODE (b
) == GE
)
1467 if (SCALAR_INT_MODE_P (mode
)
1468 && rtx_equal_p (op1
, opb1
)
1469 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1474 /* A < B or A > B imply A != B. TODO: Likewise
1475 A + n < B implies A != B + n if neither wraps. */
1476 if (GET_CODE (b
) == NE
1477 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1478 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1480 if (rtx_equal_p (op0
, opb0
)
1481 && rtx_equal_p (op1
, opb1
))
1485 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1486 if (GET_CODE (a
) == NE
1487 && op1
== const0_rtx
)
1489 if ((GET_CODE (b
) == GTU
1490 && opb1
== const0_rtx
)
1491 || (GET_CODE (b
) == GEU
1492 && opb1
== const1_rtx
))
1493 return rtx_equal_p (op0
, opb0
);
1496 /* A != N is equivalent to A - (N + 1) <u -1. */
1497 if (GET_CODE (a
) == NE
1498 && GET_CODE (op1
) == CONST_INT
1499 && GET_CODE (b
) == LTU
1500 && opb1
== constm1_rtx
1501 && GET_CODE (opb0
) == PLUS
1502 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1503 /* Avoid overflows. */
1504 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1505 != ((unsigned HOST_WIDE_INT
)1
1506 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1507 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1508 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1510 /* Likewise, A != N implies A - N > 0. */
1511 if (GET_CODE (a
) == NE
1512 && GET_CODE (op1
) == CONST_INT
)
1514 if (GET_CODE (b
) == GTU
1515 && GET_CODE (opb0
) == PLUS
1516 && opb1
== const0_rtx
1517 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1518 /* Avoid overflows. */
1519 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1520 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1521 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1522 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1523 if (GET_CODE (b
) == GEU
1524 && GET_CODE (opb0
) == PLUS
1525 && opb1
== const1_rtx
1526 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1527 /* Avoid overflows. */
1528 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1529 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1530 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1531 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1534 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1535 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1536 && GET_CODE (op1
) == CONST_INT
1537 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1538 || INTVAL (op1
) >= 0)
1539 && GET_CODE (b
) == LTU
1540 && GET_CODE (opb1
) == CONST_INT
)
1541 return INTVAL (opb1
) < 0;
1546 /* Canonicalizes COND so that
1548 (1) Ensure that operands are ordered according to
1549 swap_commutative_operands_p.
1550 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1551 for GE, GEU, and LEU. */
1554 canon_condition (rtx cond
)
1559 enum machine_mode mode
;
1561 code
= GET_CODE (cond
);
1562 op0
= XEXP (cond
, 0);
1563 op1
= XEXP (cond
, 1);
1565 if (swap_commutative_operands_p (op0
, op1
))
1567 code
= swap_condition (code
);
1573 mode
= GET_MODE (op0
);
1574 if (mode
== VOIDmode
)
1575 mode
= GET_MODE (op1
);
1576 gcc_assert (mode
!= VOIDmode
);
1578 if (GET_CODE (op1
) == CONST_INT
1579 && GET_MODE_CLASS (mode
) != MODE_CC
1580 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1582 HOST_WIDE_INT const_val
= INTVAL (op1
);
1583 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1584 unsigned HOST_WIDE_INT max_val
1585 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1590 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1591 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1594 /* When cross-compiling, const_val might be sign-extended from
1595 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1597 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1598 != (((HOST_WIDE_INT
) 1
1599 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1600 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1604 if (uconst_val
< max_val
)
1605 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1609 if (uconst_val
!= 0)
1610 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1618 if (op0
!= XEXP (cond
, 0)
1619 || op1
!= XEXP (cond
, 1)
1620 || code
!= GET_CODE (cond
)
1621 || GET_MODE (cond
) != SImode
)
1622 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1627 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1628 set of altered regs. */
1631 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1633 rtx rev
, reve
, exp
= *expr
;
1635 if (!COMPARISON_P (exp
))
1638 /* If some register gets altered later, we do not really speak about its
1639 value at the time of comparison. */
1641 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1644 rev
= reversed_condition (cond
);
1645 reve
= reversed_condition (exp
);
1647 cond
= canon_condition (cond
);
1648 exp
= canon_condition (exp
);
1650 rev
= canon_condition (rev
);
1652 reve
= canon_condition (reve
);
1654 if (rtx_equal_p (exp
, cond
))
1656 *expr
= const_true_rtx
;
1661 if (rev
&& rtx_equal_p (exp
, rev
))
1667 if (implies_p (cond
, exp
))
1669 *expr
= const_true_rtx
;
1673 if (reve
&& implies_p (cond
, reve
))
1679 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1681 if (rev
&& implies_p (exp
, rev
))
1687 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1688 if (rev
&& reve
&& implies_p (reve
, rev
))
1690 *expr
= const_true_rtx
;
1694 /* We would like to have some other tests here. TODO. */
1699 /* Use relationship between A and *B to eventually eliminate *B.
1700 OP is the operation we consider. */
1703 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1708 /* If A implies *B, we may replace *B by true. */
1709 if (implies_p (a
, *b
))
1710 *b
= const_true_rtx
;
1714 /* If *B implies A, we may replace *B by false. */
1715 if (implies_p (*b
, a
))
1724 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1725 operation we consider. */
1728 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1732 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1733 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1734 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1735 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1738 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1739 is a list, its elements are assumed to be combined using OP. */
1742 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1744 rtx head
, tail
, insn
;
1752 if (CONSTANT_P (*expr
))
1755 if (GET_CODE (*expr
) == EXPR_LIST
)
1757 head
= XEXP (*expr
, 0);
1758 tail
= XEXP (*expr
, 1);
1760 eliminate_implied_conditions (op
, &head
, tail
);
1765 neutral
= const_true_rtx
;
1770 neutral
= const0_rtx
;
1771 aggr
= const_true_rtx
;
1778 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1781 XEXP (*expr
, 0) = aggr
;
1782 XEXP (*expr
, 1) = NULL_RTX
;
1785 else if (head
== neutral
)
1788 simplify_using_initial_values (loop
, op
, expr
);
1791 simplify_using_initial_values (loop
, op
, &tail
);
1793 if (tail
&& XEXP (tail
, 0) == aggr
)
1799 XEXP (*expr
, 0) = head
;
1800 XEXP (*expr
, 1) = tail
;
1804 gcc_assert (op
== UNKNOWN
);
1806 e
= loop_preheader_edge (loop
);
1807 if (e
->src
== ENTRY_BLOCK_PTR
)
1810 altered
= ALLOC_REG_SET (®_obstack
);
1814 insn
= BB_END (e
->src
);
1815 if (any_condjump_p (insn
))
1817 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1819 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1820 cond
= reversed_condition (cond
);
1823 simplify_using_condition (cond
, expr
, altered
);
1824 if (CONSTANT_P (*expr
))
1826 FREE_REG_SET (altered
);
1832 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1837 simplify_using_assignment (insn
, expr
, altered
);
1838 if (CONSTANT_P (*expr
))
1840 FREE_REG_SET (altered
);
1843 if (for_each_rtx (expr
, altered_reg_used
, altered
))
1845 FREE_REG_SET (altered
);
1850 if (!single_pred_p (e
->src
)
1851 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
1853 e
= single_pred_edge (e
->src
);
1856 FREE_REG_SET (altered
);
1859 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1860 that IV occurs as left operands of comparison COND and its signedness
1861 is SIGNED_P to DESC. */
1864 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1865 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1867 rtx mmin
, mmax
, cond_over
, cond_under
;
1869 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1870 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1872 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1881 if (cond_under
!= const0_rtx
)
1883 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1884 if (cond_over
!= const0_rtx
)
1885 desc
->noloop_assumptions
=
1886 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1893 if (cond_over
!= const0_rtx
)
1895 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1896 if (cond_under
!= const0_rtx
)
1897 desc
->noloop_assumptions
=
1898 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1902 if (cond_over
!= const0_rtx
)
1904 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1905 if (cond_under
!= const0_rtx
)
1907 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1915 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1918 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1919 subregs of the same mode if possible (sometimes it is necessary to add
1920 some assumptions to DESC). */
1923 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1924 enum rtx_code cond
, struct niter_desc
*desc
)
1926 enum machine_mode comp_mode
;
1929 /* If the ivs behave specially in the first iteration, or are
1930 added/multiplied after extending, we ignore them. */
1931 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1933 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1936 /* If there is some extend, it must match signedness of the comparison. */
1941 if (iv0
->extend
== ZERO_EXTEND
1942 || iv1
->extend
== ZERO_EXTEND
)
1949 if (iv0
->extend
== SIGN_EXTEND
1950 || iv1
->extend
== SIGN_EXTEND
)
1956 if (iv0
->extend
!= UNKNOWN
1957 && iv1
->extend
!= UNKNOWN
1958 && iv0
->extend
!= iv1
->extend
)
1962 if (iv0
->extend
!= UNKNOWN
)
1963 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1964 if (iv1
->extend
!= UNKNOWN
)
1965 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1972 /* Values of both variables should be computed in the same mode. These
1973 might indeed be different, if we have comparison like
1975 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1977 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1978 in different modes. This does not seem impossible to handle, but
1979 it hardly ever occurs in practice.
1981 The only exception is the case when one of operands is invariant.
1982 For example pentium 3 generates comparisons like
1983 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1984 definitely do not want this prevent the optimization. */
1985 comp_mode
= iv0
->extend_mode
;
1986 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1987 comp_mode
= iv1
->extend_mode
;
1989 if (iv0
->extend_mode
!= comp_mode
)
1991 if (iv0
->mode
!= iv0
->extend_mode
1992 || iv0
->step
!= const0_rtx
)
1995 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1996 comp_mode
, iv0
->base
, iv0
->mode
);
1997 iv0
->extend_mode
= comp_mode
;
2000 if (iv1
->extend_mode
!= comp_mode
)
2002 if (iv1
->mode
!= iv1
->extend_mode
2003 || iv1
->step
!= const0_rtx
)
2006 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2007 comp_mode
, iv1
->base
, iv1
->mode
);
2008 iv1
->extend_mode
= comp_mode
;
2011 /* Check that both ivs belong to a range of a single mode. If one of the
2012 operands is an invariant, we may need to shorten it into the common
2014 if (iv0
->mode
== iv0
->extend_mode
2015 && iv0
->step
== const0_rtx
2016 && iv0
->mode
!= iv1
->mode
)
2017 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2019 if (iv1
->mode
== iv1
->extend_mode
2020 && iv1
->step
== const0_rtx
2021 && iv0
->mode
!= iv1
->mode
)
2022 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2024 if (iv0
->mode
!= iv1
->mode
)
2027 desc
->mode
= iv0
->mode
;
2028 desc
->signed_p
= signed_p
;
2033 /* Tries to estimate the maximum number of iterations. */
2035 static unsigned HOST_WIDEST_INT
2036 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
)
2038 rtx niter
= desc
->niter_expr
;
2039 rtx mmin
, mmax
, cmp
;
2040 unsigned HOST_WIDEST_INT nmax
, inc
;
2042 if (GET_CODE (niter
) == AND
2043 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
2045 nmax
= INTVAL (XEXP (niter
, 0));
2046 if (!(nmax
& (nmax
+ 1)))
2048 desc
->niter_max
= nmax
;
2053 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2054 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2056 if (GET_CODE (niter
) == UDIV
)
2058 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
2060 desc
->niter_max
= nmax
;
2063 inc
= INTVAL (XEXP (niter
, 1));
2064 niter
= XEXP (niter
, 0);
2069 /* We could use a binary search here, but for now improving the upper
2070 bound by just one eliminates one important corner case. */
2071 cmp
= gen_rtx_fmt_ee (desc
->signed_p
? LT
: LTU
, VOIDmode
, niter
, mmax
);
2072 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2073 if (cmp
== const_true_rtx
)
2078 fprintf (dump_file
, ";; improved upper bound by one.\n");
2080 desc
->niter_max
= nmax
/ inc
;
2084 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2085 the result into DESC. Very similar to determine_number_of_iterations
2086 (basically its rtl version), complicated by things like subregs. */
2089 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2090 struct niter_desc
*desc
)
2092 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2093 struct rtx_iv iv0
, iv1
, tmp_iv
;
2094 rtx assumption
, may_not_xform
;
2096 enum machine_mode mode
, comp_mode
;
2097 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2098 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2099 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2100 int was_sharp
= false;
2104 /* The meaning of these assumptions is this:
2106 then the rest of information does not have to be valid
2107 if noloop_assumptions then the loop does not roll
2108 if infinite then this exit is never used */
2110 desc
->assumptions
= NULL_RTX
;
2111 desc
->noloop_assumptions
= NULL_RTX
;
2112 desc
->infinite
= NULL_RTX
;
2113 desc
->simple_p
= true;
2115 desc
->const_iter
= false;
2116 desc
->niter_expr
= NULL_RTX
;
2117 desc
->niter_max
= 0;
2119 cond
= GET_CODE (condition
);
2120 gcc_assert (COMPARISON_P (condition
));
2122 mode
= GET_MODE (XEXP (condition
, 0));
2123 if (mode
== VOIDmode
)
2124 mode
= GET_MODE (XEXP (condition
, 1));
2125 /* The constant comparisons should be folded. */
2126 gcc_assert (mode
!= VOIDmode
);
2128 /* We only handle integers or pointers. */
2129 if (GET_MODE_CLASS (mode
) != MODE_INT
2130 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2133 op0
= XEXP (condition
, 0);
2134 if (!iv_analyze (insn
, op0
, &iv0
))
2136 if (iv0
.extend_mode
== VOIDmode
)
2137 iv0
.mode
= iv0
.extend_mode
= mode
;
2139 op1
= XEXP (condition
, 1);
2140 if (!iv_analyze (insn
, op1
, &iv1
))
2142 if (iv1
.extend_mode
== VOIDmode
)
2143 iv1
.mode
= iv1
.extend_mode
= mode
;
2145 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2146 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2149 /* Check condition and normalize it. */
2157 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2158 cond
= swap_condition (cond
);
2170 /* Handle extends. This is relatively nontrivial, so we only try in some
2171 easy cases, when we can canonicalize the ivs (possibly by adding some
2172 assumptions) to shape subreg (base + i * step). This function also fills
2173 in desc->mode and desc->signed_p. */
2175 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2178 comp_mode
= iv0
.extend_mode
;
2180 size
= GET_MODE_BITSIZE (mode
);
2181 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2182 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2183 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2185 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2188 /* We can take care of the case of two induction variables chasing each other
2189 if the test is NE. I have never seen a loop using it, but still it is
2191 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2196 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2197 iv1
.step
= const0_rtx
;
2200 /* This is either infinite loop or the one that ends immediately, depending
2201 on initial values. Unswitching should remove this kind of conditions. */
2202 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2207 if (iv0
.step
== const0_rtx
)
2208 step_val
= -INTVAL (iv1
.step
);
2210 step_val
= INTVAL (iv0
.step
);
2212 /* Ignore loops of while (i-- < 10) type. */
2216 step_is_pow2
= !(step_val
& (step_val
- 1));
2220 /* We do not care about whether the step is power of two in this
2222 step_is_pow2
= false;
2226 /* Some more condition normalization. We must record some assumptions
2227 due to overflows. */
2232 /* We want to take care only of non-sharp relationals; this is easy,
2233 as in cases the overflow would make the transformation unsafe
2234 the loop does not roll. Seemingly it would make more sense to want
2235 to take care of sharp relationals instead, as NE is more similar to
2236 them, but the problem is that here the transformation would be more
2237 difficult due to possibly infinite loops. */
2238 if (iv0
.step
== const0_rtx
)
2240 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2241 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2243 if (assumption
== const_true_rtx
)
2244 goto zero_iter_simplify
;
2245 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2246 iv0
.base
, const1_rtx
);
2250 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2251 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2253 if (assumption
== const_true_rtx
)
2254 goto zero_iter_simplify
;
2255 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2256 iv1
.base
, constm1_rtx
);
2259 if (assumption
!= const0_rtx
)
2260 desc
->noloop_assumptions
=
2261 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2262 cond
= (cond
== LT
) ? LE
: LEU
;
2264 /* It will be useful to be able to tell the difference once more in
2265 LE -> NE reduction. */
2271 /* Take care of trivially infinite loops. */
2274 if (iv0
.step
== const0_rtx
)
2276 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2277 if (rtx_equal_p (tmp
, mode_mmin
))
2280 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2281 /* Fill in the remaining fields somehow. */
2282 goto zero_iter_simplify
;
2287 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2288 if (rtx_equal_p (tmp
, mode_mmax
))
2291 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2292 /* Fill in the remaining fields somehow. */
2293 goto zero_iter_simplify
;
2298 /* If we can we want to take care of NE conditions instead of size
2299 comparisons, as they are much more friendly (most importantly
2300 this takes care of special handling of loops with step 1). We can
2301 do it if we first check that upper bound is greater or equal to
2302 lower bound, their difference is constant c modulo step and that
2303 there is not an overflow. */
2306 if (iv0
.step
== const0_rtx
)
2307 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2310 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2311 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2312 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2313 may_xform
= const0_rtx
;
2314 may_not_xform
= const_true_rtx
;
2316 if (GET_CODE (delta
) == CONST_INT
)
2318 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2320 /* A special case. We have transformed condition of type
2321 for (i = 0; i < 4; i += 4)
2323 for (i = 0; i <= 3; i += 4)
2324 obviously if the test for overflow during that transformation
2325 passed, we cannot overflow here. Most importantly any
2326 loop with sharp end condition and step 1 falls into this
2327 category, so handling this case specially is definitely
2328 worth the troubles. */
2329 may_xform
= const_true_rtx
;
2331 else if (iv0
.step
== const0_rtx
)
2333 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2334 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2335 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2336 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2337 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2339 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2345 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2346 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2347 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2348 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2349 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2351 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2357 if (may_xform
!= const0_rtx
)
2359 /* We perform the transformation always provided that it is not
2360 completely senseless. This is OK, as we would need this assumption
2361 to determine the number of iterations anyway. */
2362 if (may_xform
!= const_true_rtx
)
2364 /* If the step is a power of two and the final value we have
2365 computed overflows, the cycle is infinite. Otherwise it
2366 is nontrivial to compute the number of iterations. */
2368 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2371 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2375 /* We are going to lose some information about upper bound on
2376 number of iterations in this step, so record the information
2378 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2379 if (GET_CODE (iv1
.base
) == CONST_INT
)
2380 up
= INTVAL (iv1
.base
);
2382 up
= INTVAL (mode_mmax
) - inc
;
2383 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2386 desc
->niter_max
= (up
- down
) / inc
+ 1;
2388 if (iv0
.step
== const0_rtx
)
2390 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2391 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2395 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2396 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2399 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2400 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2401 assumption
= simplify_gen_relational (reverse_condition (cond
),
2402 SImode
, mode
, tmp0
, tmp1
);
2403 if (assumption
== const_true_rtx
)
2404 goto zero_iter_simplify
;
2405 else if (assumption
!= const0_rtx
)
2406 desc
->noloop_assumptions
=
2407 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2412 /* Count the number of iterations. */
2415 /* Everything we do here is just arithmetics modulo size of mode. This
2416 makes us able to do more involved computations of number of iterations
2417 than in other cases. First transform the condition into shape
2418 s * i <> c, with s positive. */
2419 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2420 iv0
.base
= const0_rtx
;
2421 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2422 iv1
.step
= const0_rtx
;
2423 if (INTVAL (iv0
.step
) < 0)
2425 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2426 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2428 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2430 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2431 is infinite. Otherwise, the number of iterations is
2432 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2433 s
= INTVAL (iv0
.step
); d
= 1;
2440 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2442 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2443 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2444 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2445 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2447 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2448 inv
= inverse (s
, size
);
2449 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2450 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2454 if (iv1
.step
== const0_rtx
)
2455 /* Condition in shape a + s * i <= b
2456 We must know that b + s does not overflow and a <= b + s and then we
2457 can compute number of iterations as (b + s - a) / s. (It might
2458 seem that we in fact could be more clever about testing the b + s
2459 overflow condition using some information about b - a mod s,
2460 but it was already taken into account during LE -> NE transform). */
2463 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2464 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2466 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2467 lowpart_subreg (mode
, step
,
2473 /* If s is power of 2, we know that the loop is infinite if
2474 a % s <= b % s and b + s overflows. */
2475 assumption
= simplify_gen_relational (reverse_condition (cond
),
2479 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2480 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2481 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2482 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2484 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2488 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2491 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2494 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2495 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2496 assumption
= simplify_gen_relational (reverse_condition (cond
),
2497 SImode
, mode
, tmp0
, tmp
);
2499 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2500 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2504 /* Condition in shape a <= b - s * i
2505 We must know that a - s does not overflow and a - s <= b and then
2506 we can again compute number of iterations as (b - (a - s)) / s. */
2507 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2508 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2509 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2511 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2512 lowpart_subreg (mode
, step
, comp_mode
));
2517 /* If s is power of 2, we know that the loop is infinite if
2518 a % s <= b % s and a - s overflows. */
2519 assumption
= simplify_gen_relational (reverse_condition (cond
),
2523 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2524 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2525 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2526 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2528 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2532 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2535 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2538 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2539 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2540 assumption
= simplify_gen_relational (reverse_condition (cond
),
2543 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2544 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2546 if (assumption
== const_true_rtx
)
2547 goto zero_iter_simplify
;
2548 else if (assumption
!= const0_rtx
)
2549 desc
->noloop_assumptions
=
2550 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2551 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2552 desc
->niter_expr
= delta
;
2555 old_niter
= desc
->niter_expr
;
2557 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2558 if (desc
->assumptions
2559 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2561 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2562 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2563 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2565 /* Rerun the simplification. Consider code (created by copying loop headers)
2577 The first pass determines that i = 0, the second pass uses it to eliminate
2578 noloop assumption. */
2580 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2581 if (desc
->assumptions
2582 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2584 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2585 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2586 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2588 if (desc
->noloop_assumptions
2589 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2592 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2594 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2596 desc
->const_iter
= true;
2597 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2601 if (!desc
->niter_max
)
2602 desc
->niter_max
= determine_max_iter (loop
, desc
);
2604 /* simplify_using_initial_values does a copy propagation on the registers
2605 in the expression for the number of iterations. This prolongs life
2606 ranges of registers and increases register pressure, and usually
2607 brings no gain (and if it happens to do, the cse pass will take care
2608 of it anyway). So prevent this behavior, unless it enabled us to
2609 derive that the number of iterations is a constant. */
2610 desc
->niter_expr
= old_niter
;
2616 /* Simplify the assumptions. */
2617 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2618 if (desc
->assumptions
2619 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2621 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2625 desc
->const_iter
= true;
2627 desc
->niter_max
= 0;
2628 desc
->noloop_assumptions
= NULL_RTX
;
2629 desc
->niter_expr
= const0_rtx
;
2633 desc
->simple_p
= false;
2637 /* Checks whether E is a simple exit from LOOP and stores its description
2641 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2643 basic_block exit_bb
;
2648 desc
->simple_p
= false;
2650 /* It must belong directly to the loop. */
2651 if (exit_bb
->loop_father
!= loop
)
2654 /* It must be tested (at least) once during any iteration. */
2655 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2658 /* It must end in a simple conditional jump. */
2659 if (!any_condjump_p (BB_END (exit_bb
)))
2662 ein
= EDGE_SUCC (exit_bb
, 0);
2664 ein
= EDGE_SUCC (exit_bb
, 1);
2667 desc
->in_edge
= ein
;
2669 /* Test whether the condition is suitable. */
2670 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2673 if (ein
->flags
& EDGE_FALLTHRU
)
2675 condition
= reversed_condition (condition
);
2680 /* Check that we are able to determine number of iterations and fill
2681 in information about it. */
2682 iv_number_of_iterations (loop
, at
, condition
, desc
);
2685 /* Finds a simple exit of LOOP and stores its description into DESC. */
2688 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2693 struct niter_desc act
;
2697 desc
->simple_p
= false;
2698 body
= get_loop_body (loop
);
2700 for (i
= 0; i
< loop
->num_nodes
; i
++)
2702 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2704 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2707 check_simple_exit (loop
, e
, &act
);
2715 /* Prefer constant iterations; the less the better. */
2717 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2720 /* Also if the actual exit may be infinite, while the old one
2721 not, prefer the old one. */
2722 if (act
.infinite
&& !desc
->infinite
)
2734 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2735 fprintf (dump_file
, " simple exit %d -> %d\n",
2736 desc
->out_edge
->src
->index
,
2737 desc
->out_edge
->dest
->index
);
2738 if (desc
->assumptions
)
2740 fprintf (dump_file
, " assumptions: ");
2741 print_rtl (dump_file
, desc
->assumptions
);
2742 fprintf (dump_file
, "\n");
2744 if (desc
->noloop_assumptions
)
2746 fprintf (dump_file
, " does not roll if: ");
2747 print_rtl (dump_file
, desc
->noloop_assumptions
);
2748 fprintf (dump_file
, "\n");
2752 fprintf (dump_file
, " infinite if: ");
2753 print_rtl (dump_file
, desc
->infinite
);
2754 fprintf (dump_file
, "\n");
2757 fprintf (dump_file
, " number of iterations: ");
2758 print_rtl (dump_file
, desc
->niter_expr
);
2759 fprintf (dump_file
, "\n");
2761 fprintf (dump_file
, " upper bound: ");
2762 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2763 fprintf (dump_file
, "\n");
2766 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2772 /* Creates a simple loop description of LOOP if it was not computed
2776 get_simple_loop_desc (struct loop
*loop
)
2778 struct niter_desc
*desc
= simple_loop_desc (loop
);
2783 desc
= XNEW (struct niter_desc
);
2784 iv_analysis_loop_init (loop
);
2785 find_simple_exit (loop
, desc
);
2788 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
2790 const char *wording
;
2792 /* Assume that no overflow happens and that the loop is finite.
2793 We already warned at the tree level if we ran optimizations there. */
2794 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
2799 flag_unsafe_loop_optimizations
2800 ? N_("assuming that the loop is not infinite")
2801 : N_("cannot optimize possibly infinite loops");
2802 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2805 if (desc
->assumptions
)
2808 flag_unsafe_loop_optimizations
2809 ? N_("assuming that the loop counter does not overflow")
2810 : N_("cannot optimize loop, the loop counter may overflow");
2811 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2816 if (flag_unsafe_loop_optimizations
)
2818 desc
->assumptions
= NULL_RTX
;
2819 desc
->infinite
= NULL_RTX
;
2826 /* Releases simple loop description for LOOP. */
2829 free_simple_loop_desc (struct loop
*loop
)
2831 struct niter_desc
*desc
= simple_loop_desc (loop
);