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 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
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
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
177 memset (&iv_ref_table
[iv_ref_table_size
], 0,
178 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
179 iv_ref_table_size
= new_size
;
184 /* Checks whether REG is a well-behaved register. */
187 simple_reg_p (rtx reg
)
191 if (GET_CODE (reg
) == SUBREG
)
193 if (!subreg_lowpart_p (reg
))
195 reg
= SUBREG_REG (reg
);
202 if (HARD_REGISTER_NUM_P (r
))
205 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
211 /* Clears the information about ivs stored in df. */
216 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
219 check_iv_ref_table_size ();
220 for (i
= 0; i
< n_defs
; i
++)
222 iv
= iv_ref_table
[i
];
226 iv_ref_table
[i
] = NULL
;
233 /* Returns hash value for biv B. */
236 biv_hash (const void *b
)
238 return ((const struct biv_entry
*) b
)->regno
;
241 /* Compares biv B and register R. */
244 biv_eq (const void *b
, const void *r
)
246 return ((const struct biv_entry
*) b
)->regno
== REGNO ((const_rtx
) r
);
249 /* Prepare the data for an induction variable analysis of a LOOP. */
252 iv_analysis_loop_init (struct loop
*loop
)
254 basic_block
*body
= get_loop_body_in_dom_order (loop
), bb
;
255 bitmap blocks
= BITMAP_ALLOC (NULL
);
260 /* Clear the information from the analysis of the previous loop. */
263 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
264 bivs
= htab_create (10, biv_hash
, biv_eq
, free
);
270 for (i
= 0; i
< loop
->num_nodes
; i
++)
273 bitmap_set_bit (blocks
, bb
->index
);
275 /* Get rid of the ud chains before processing the rescans. Then add
277 df_remove_problem (df_chain
);
278 df_process_deferred_rescans ();
279 df_chain_add_problem (DF_UD_CHAIN
);
280 df_set_blocks (blocks
);
283 df_dump_region (dump_file
);
285 check_iv_ref_table_size ();
286 BITMAP_FREE (blocks
);
290 /* Finds the definition of REG that dominates loop latch and stores
291 it to DEF. Returns false if there is not a single definition
292 dominating the latch. If REG has no definition in loop, DEF
293 is set to NULL and true is returned. */
296 latch_dominating_def (rtx reg
, df_ref
*def
)
298 df_ref single_rd
= NULL
, adef
;
299 unsigned regno
= REGNO (reg
);
300 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
302 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
304 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
305 || !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
, df_ref
*def
)
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
;
351 /* We do not handle setting only part of the register. */
352 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
355 def_insn
= DF_REF_INSN (adef
);
356 def_bb
= DF_REF_BB (adef
);
357 use_bb
= BLOCK_FOR_INSN (insn
);
359 if (use_bb
== def_bb
)
360 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
362 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
367 return GRD_SINGLE_DOM
;
370 /* The definition does not dominate the use. This is still OK if
371 this may be a use of a biv, i.e. if the def_bb dominates loop
373 if (just_once_each_iteration_p (current_loop
, def_bb
))
374 return GRD_MAYBE_BIV
;
379 /* Sets IV to invariant CST in MODE. Always returns true (just for
380 consistency with other iv manipulation functions that may fail). */
383 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
385 if (mode
== VOIDmode
)
386 mode
= GET_MODE (cst
);
390 iv
->step
= const0_rtx
;
391 iv
->first_special
= false;
392 iv
->extend
= UNKNOWN
;
393 iv
->extend_mode
= iv
->mode
;
394 iv
->delta
= const0_rtx
;
395 iv
->mult
= const1_rtx
;
400 /* Evaluates application of subreg to MODE on IV. */
403 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
405 /* If iv is invariant, just calculate the new value. */
406 if (iv
->step
== const0_rtx
407 && !iv
->first_special
)
409 rtx val
= get_iv_value (iv
, const0_rtx
);
410 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
413 iv
->extend
= UNKNOWN
;
414 iv
->mode
= iv
->extend_mode
= mode
;
415 iv
->delta
= const0_rtx
;
416 iv
->mult
= const1_rtx
;
420 if (iv
->extend_mode
== mode
)
423 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
426 iv
->extend
= UNKNOWN
;
429 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
430 simplify_gen_binary (MULT
, iv
->extend_mode
,
431 iv
->base
, iv
->mult
));
432 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
433 iv
->mult
= const1_rtx
;
434 iv
->delta
= const0_rtx
;
435 iv
->first_special
= false;
440 /* Evaluates application of EXTEND to MODE on IV. */
443 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
445 /* If iv is invariant, just calculate the new value. */
446 if (iv
->step
== const0_rtx
447 && !iv
->first_special
)
449 rtx val
= get_iv_value (iv
, const0_rtx
);
450 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
453 iv
->extend
= UNKNOWN
;
454 iv
->mode
= iv
->extend_mode
= mode
;
455 iv
->delta
= const0_rtx
;
456 iv
->mult
= const1_rtx
;
460 if (mode
!= iv
->extend_mode
)
463 if (iv
->extend
!= UNKNOWN
464 && iv
->extend
!= extend
)
472 /* Evaluates negation of IV. */
475 iv_neg (struct rtx_iv
*iv
)
477 if (iv
->extend
== UNKNOWN
)
479 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
480 iv
->base
, iv
->extend_mode
);
481 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
482 iv
->step
, iv
->extend_mode
);
486 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
487 iv
->delta
, iv
->extend_mode
);
488 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
489 iv
->mult
, iv
->extend_mode
);
495 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
498 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
500 enum machine_mode mode
;
503 /* Extend the constant to extend_mode of the other operand if necessary. */
504 if (iv0
->extend
== UNKNOWN
505 && iv0
->mode
== iv0
->extend_mode
506 && iv0
->step
== const0_rtx
507 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
509 iv0
->extend_mode
= iv1
->extend_mode
;
510 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
511 iv0
->base
, iv0
->mode
);
513 if (iv1
->extend
== UNKNOWN
514 && iv1
->mode
== iv1
->extend_mode
515 && iv1
->step
== const0_rtx
516 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
518 iv1
->extend_mode
= iv0
->extend_mode
;
519 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
520 iv1
->base
, iv1
->mode
);
523 mode
= iv0
->extend_mode
;
524 if (mode
!= iv1
->extend_mode
)
527 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
529 if (iv0
->mode
!= iv1
->mode
)
532 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
533 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
538 /* Handle addition of constant. */
539 if (iv1
->extend
== UNKNOWN
541 && iv1
->step
== const0_rtx
)
543 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
547 if (iv0
->extend
== UNKNOWN
549 && iv0
->step
== const0_rtx
)
557 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
564 /* Evaluates multiplication of IV by constant CST. */
567 iv_mult (struct rtx_iv
*iv
, rtx mby
)
569 enum machine_mode mode
= iv
->extend_mode
;
571 if (GET_MODE (mby
) != VOIDmode
572 && GET_MODE (mby
) != mode
)
575 if (iv
->extend
== UNKNOWN
)
577 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
578 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
582 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
583 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
589 /* Evaluates shift of IV by constant CST. */
592 iv_shift (struct rtx_iv
*iv
, rtx mby
)
594 enum machine_mode mode
= iv
->extend_mode
;
596 if (GET_MODE (mby
) != VOIDmode
597 && GET_MODE (mby
) != mode
)
600 if (iv
->extend
== UNKNOWN
)
602 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
603 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
607 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
608 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
614 /* The recursive part of get_biv_step. Gets the value of the single value
615 defined by DEF wrto initial value of REG inside loop, in shape described
619 get_biv_step_1 (df_ref def
, rtx reg
,
620 rtx
*inner_step
, enum machine_mode
*inner_mode
,
621 enum rtx_code
*extend
, enum machine_mode outer_mode
,
624 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
625 rtx next
, nextr
, tmp
;
627 rtx insn
= DF_REF_INSN (def
);
629 enum iv_grd_result res
;
631 set
= single_set (insn
);
635 rhs
= find_reg_equal_equiv_note (insn
);
641 code
= GET_CODE (rhs
);
654 if (code
== PLUS
&& CONSTANT_P (op0
))
656 tmp
= op0
; op0
= op1
; op1
= tmp
;
659 if (!simple_reg_p (op0
)
660 || !CONSTANT_P (op1
))
663 if (GET_MODE (rhs
) != outer_mode
)
665 /* ppc64 uses expressions like
667 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
669 this is equivalent to
671 (set x':DI (plus:DI y:DI 1))
672 (set x:SI (subreg:SI (x':DI)). */
673 if (GET_CODE (op0
) != SUBREG
)
675 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
684 if (GET_MODE (rhs
) != outer_mode
)
688 if (!simple_reg_p (op0
))
698 if (GET_CODE (next
) == SUBREG
)
700 if (!subreg_lowpart_p (next
))
703 nextr
= SUBREG_REG (next
);
704 if (GET_MODE (nextr
) != outer_mode
)
710 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
712 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
715 if (res
== GRD_MAYBE_BIV
)
717 if (!rtx_equal_p (nextr
, reg
))
720 *inner_step
= const0_rtx
;
722 *inner_mode
= outer_mode
;
723 *outer_step
= const0_rtx
;
725 else if (!get_biv_step_1 (next_def
, reg
,
726 inner_step
, inner_mode
, extend
, outer_mode
,
730 if (GET_CODE (next
) == SUBREG
)
732 enum machine_mode amode
= GET_MODE (next
);
734 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
738 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
739 *inner_step
, *outer_step
);
740 *outer_step
= const0_rtx
;
752 if (*inner_mode
== outer_mode
753 /* See comment in previous switch. */
754 || GET_MODE (rhs
) != outer_mode
)
755 *inner_step
= simplify_gen_binary (code
, outer_mode
,
758 *outer_step
= simplify_gen_binary (code
, outer_mode
,
764 gcc_assert (GET_MODE (op0
) == *inner_mode
765 && *extend
== UNKNOWN
766 && *outer_step
== const0_rtx
);
778 /* Gets the operation on register REG inside loop, in shape
780 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
782 If the operation cannot be described in this shape, return false.
783 LAST_DEF is the definition of REG that dominates loop latch. */
786 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
787 enum machine_mode
*inner_mode
, enum rtx_code
*extend
,
788 enum machine_mode
*outer_mode
, rtx
*outer_step
)
790 *outer_mode
= GET_MODE (reg
);
792 if (!get_biv_step_1 (last_def
, reg
,
793 inner_step
, inner_mode
, extend
, *outer_mode
,
797 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= UNKNOWN
));
798 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
803 /* Records information that DEF is induction variable IV. */
806 record_iv (df_ref def
, struct rtx_iv
*iv
)
808 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
811 check_iv_ref_table_size ();
812 DF_REF_IV_SET (def
, recorded_iv
);
815 /* If DEF was already analyzed for bivness, store the description of the biv to
816 IV and return true. Otherwise return false. */
819 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
821 struct biv_entry
*biv
=
822 (struct biv_entry
*) htab_find_with_hash (bivs
, def
, REGNO (def
));
832 record_biv (rtx def
, struct rtx_iv
*iv
)
834 struct biv_entry
*biv
= XNEW (struct biv_entry
);
835 void **slot
= htab_find_slot_with_hash (bivs
, def
, REGNO (def
), INSERT
);
837 biv
->regno
= REGNO (def
);
843 /* Determines whether DEF is a biv and if so, stores its description
847 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
849 rtx inner_step
, outer_step
;
850 enum machine_mode inner_mode
, outer_mode
;
851 enum rtx_code extend
;
856 fprintf (dump_file
, "Analyzing ");
857 print_rtl (dump_file
, def
);
858 fprintf (dump_file
, " for bivness.\n");
863 if (!CONSTANT_P (def
))
866 return iv_constant (iv
, def
, VOIDmode
);
869 if (!latch_dominating_def (def
, &last_def
))
872 fprintf (dump_file
, " not simple.\n");
877 return iv_constant (iv
, def
, VOIDmode
);
879 if (analyzed_for_bivness_p (def
, iv
))
882 fprintf (dump_file
, " already analysed.\n");
883 return iv
->base
!= NULL_RTX
;
886 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
887 &outer_mode
, &outer_step
))
893 /* Loop transforms base to es (base + inner_step) + outer_step,
894 where es means extend of subreg between inner_mode and outer_mode.
895 The corresponding induction variable is
897 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
899 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
900 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
901 iv
->mode
= inner_mode
;
902 iv
->extend_mode
= outer_mode
;
904 iv
->mult
= const1_rtx
;
905 iv
->delta
= outer_step
;
906 iv
->first_special
= inner_mode
!= outer_mode
;
911 fprintf (dump_file
, " ");
912 dump_iv_info (dump_file
, iv
);
913 fprintf (dump_file
, "\n");
916 record_biv (def
, iv
);
917 return iv
->base
!= NULL_RTX
;
920 /* Analyzes expression RHS used at INSN and stores the result to *IV.
921 The mode of the induction variable is MODE. */
924 iv_analyze_expr (rtx insn
, rtx rhs
, enum machine_mode mode
, struct rtx_iv
*iv
)
926 rtx mby
= NULL_RTX
, tmp
;
927 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
928 struct rtx_iv iv0
, iv1
;
929 enum rtx_code code
= GET_CODE (rhs
);
930 enum machine_mode omode
= mode
;
936 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
942 if (!iv_analyze_op (insn
, rhs
, iv
))
945 if (iv
->mode
== VOIDmode
)
948 iv
->extend_mode
= mode
;
964 omode
= GET_MODE (op0
);
976 if (!CONSTANT_P (mby
))
982 if (!CONSTANT_P (mby
))
989 if (!CONSTANT_P (mby
))
998 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1002 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1009 if (!iv_extend (&iv0
, code
, mode
))
1020 if (!iv_add (&iv0
, &iv1
, code
))
1025 if (!iv_mult (&iv0
, mby
))
1030 if (!iv_shift (&iv0
, mby
))
1039 return iv
->base
!= NULL_RTX
;
1042 /* Analyzes iv DEF and stores the result to *IV. */
1045 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1047 rtx insn
= DF_REF_INSN (def
);
1048 rtx reg
= DF_REF_REG (def
);
1053 fprintf (dump_file
, "Analyzing def of ");
1054 print_rtl (dump_file
, reg
);
1055 fprintf (dump_file
, " in insn ");
1056 print_rtl_single (dump_file
, insn
);
1059 check_iv_ref_table_size ();
1060 if (DF_REF_IV (def
))
1063 fprintf (dump_file
, " already analysed.\n");
1064 *iv
= *DF_REF_IV (def
);
1065 return iv
->base
!= NULL_RTX
;
1068 iv
->mode
= VOIDmode
;
1069 iv
->base
= NULL_RTX
;
1070 iv
->step
= NULL_RTX
;
1075 set
= single_set (insn
);
1079 if (!REG_P (SET_DEST (set
)))
1082 gcc_assert (SET_DEST (set
) == reg
);
1083 rhs
= find_reg_equal_equiv_note (insn
);
1085 rhs
= XEXP (rhs
, 0);
1087 rhs
= SET_SRC (set
);
1089 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1090 record_iv (def
, iv
);
1094 print_rtl (dump_file
, reg
);
1095 fprintf (dump_file
, " in insn ");
1096 print_rtl_single (dump_file
, insn
);
1097 fprintf (dump_file
, " is ");
1098 dump_iv_info (dump_file
, iv
);
1099 fprintf (dump_file
, "\n");
1102 return iv
->base
!= NULL_RTX
;
1105 /* Analyzes operand OP of INSN and stores the result to *IV. */
1108 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1111 enum iv_grd_result res
;
1115 fprintf (dump_file
, "Analyzing operand ");
1116 print_rtl (dump_file
, op
);
1117 fprintf (dump_file
, " of insn ");
1118 print_rtl_single (dump_file
, insn
);
1121 if (CONSTANT_P (op
))
1122 res
= GRD_INVARIANT
;
1123 else if (GET_CODE (op
) == SUBREG
)
1125 if (!subreg_lowpart_p (op
))
1128 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1131 return iv_subreg (iv
, GET_MODE (op
));
1135 res
= iv_get_reaching_def (insn
, op
, &def
);
1136 if (res
== GRD_INVALID
)
1139 fprintf (dump_file
, " not simple.\n");
1144 if (res
== GRD_INVARIANT
)
1146 iv_constant (iv
, op
, VOIDmode
);
1150 fprintf (dump_file
, " ");
1151 dump_iv_info (dump_file
, iv
);
1152 fprintf (dump_file
, "\n");
1157 if (res
== GRD_MAYBE_BIV
)
1158 return iv_analyze_biv (op
, iv
);
1160 return iv_analyze_def (def
, iv
);
1163 /* Analyzes value VAL at INSN and stores the result to *IV. */
1166 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
1170 /* We must find the insn in that val is used, so that we get to UD chains.
1171 Since the function is sometimes called on result of get_condition,
1172 this does not necessarily have to be directly INSN; scan also the
1174 if (simple_reg_p (val
))
1176 if (GET_CODE (val
) == SUBREG
)
1177 reg
= SUBREG_REG (val
);
1181 while (!df_find_use (insn
, reg
))
1182 insn
= NEXT_INSN (insn
);
1185 return iv_analyze_op (insn
, val
, iv
);
1188 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1191 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1195 adef
= df_find_def (insn
, def
);
1199 return iv_analyze_def (adef
, iv
);
1202 /* Checks whether definition of register REG in INSN is a basic induction
1203 variable. IV analysis must have been initialized (via a call to
1204 iv_analysis_loop_init) for this function to produce a result. */
1207 biv_p (rtx insn
, rtx reg
)
1210 df_ref def
, last_def
;
1212 if (!simple_reg_p (reg
))
1215 def
= df_find_def (insn
, reg
);
1216 gcc_assert (def
!= NULL
);
1217 if (!latch_dominating_def (reg
, &last_def
))
1219 if (last_def
!= def
)
1222 if (!iv_analyze_biv (reg
, &iv
))
1225 return iv
.step
!= const0_rtx
;
1228 /* Calculates value of IV at ITERATION-th iteration. */
1231 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1235 /* We would need to generate some if_then_else patterns, and so far
1236 it is not needed anywhere. */
1237 gcc_assert (!iv
->first_special
);
1239 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1240 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1241 simplify_gen_binary (MULT
, iv
->extend_mode
,
1242 iv
->step
, iteration
));
1246 if (iv
->extend_mode
== iv
->mode
)
1249 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1251 if (iv
->extend
== UNKNOWN
)
1254 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1255 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1256 simplify_gen_binary (MULT
, iv
->extend_mode
,
1262 /* Free the data for an induction variable analysis. */
1265 iv_analysis_done (void)
1271 df_finish_pass (true);
1273 free (iv_ref_table
);
1274 iv_ref_table
= NULL
;
1275 iv_ref_table_size
= 0;
1280 /* Computes inverse to X modulo (1 << MOD). */
1282 static unsigned HOST_WIDEST_INT
1283 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1285 unsigned HOST_WIDEST_INT mask
=
1286 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1287 unsigned HOST_WIDEST_INT rslt
= 1;
1290 for (i
= 0; i
< mod
- 1; i
++)
1292 rslt
= (rslt
* x
) & mask
;
1299 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1302 altered_reg_used (rtx
*reg
, void *alt
)
1307 return REGNO_REG_SET_P ((bitmap
) alt
, REGNO (*reg
));
1310 /* Marks registers altered by EXPR in set ALT. */
1313 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1315 if (GET_CODE (expr
) == SUBREG
)
1316 expr
= SUBREG_REG (expr
);
1320 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1323 /* Checks whether RHS is simple enough to process. */
1326 simple_rhs_p (rtx rhs
)
1330 if (CONSTANT_P (rhs
)
1331 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1334 switch (GET_CODE (rhs
))
1338 op0
= XEXP (rhs
, 0);
1339 op1
= XEXP (rhs
, 1);
1340 /* Allow reg + const and reg + reg. */
1341 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1342 && !CONSTANT_P (op0
))
1344 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1345 && !CONSTANT_P (op1
))
1351 op0
= XEXP (rhs
, 0);
1352 op1
= XEXP (rhs
, 1);
1353 /* Allow reg << const. */
1354 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1356 if (!CONSTANT_P (op1
))
1366 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1370 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1372 rtx set
= single_set (insn
);
1373 rtx lhs
= NULL_RTX
, rhs
;
1378 lhs
= SET_DEST (set
);
1380 || altered_reg_used (&lhs
, altered
))
1386 note_stores (PATTERN (insn
), mark_altered
, altered
);
1391 /* Kill all call clobbered registers. */
1392 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1393 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1394 SET_REGNO_REG_SET (altered
, i
);
1400 rhs
= find_reg_equal_equiv_note (insn
);
1402 rhs
= XEXP (rhs
, 0);
1404 rhs
= SET_SRC (set
);
1406 if (!simple_rhs_p (rhs
))
1409 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1412 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1415 /* Checks whether A implies B. */
1418 implies_p (rtx a
, rtx b
)
1420 rtx op0
, op1
, opb0
, opb1
, r
;
1421 enum machine_mode mode
;
1423 if (GET_CODE (a
) == EQ
)
1430 r
= simplify_replace_rtx (b
, op0
, op1
);
1431 if (r
== const_true_rtx
)
1437 r
= simplify_replace_rtx (b
, op1
, op0
);
1438 if (r
== const_true_rtx
)
1443 if (b
== const_true_rtx
)
1446 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1447 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1448 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1449 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1457 mode
= GET_MODE (op0
);
1458 if (mode
!= GET_MODE (opb0
))
1460 else if (mode
== VOIDmode
)
1462 mode
= GET_MODE (op1
);
1463 if (mode
!= GET_MODE (opb1
))
1467 /* A < B implies A + 1 <= B. */
1468 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1469 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1472 if (GET_CODE (a
) == GT
)
1479 if (GET_CODE (b
) == GE
)
1486 if (SCALAR_INT_MODE_P (mode
)
1487 && rtx_equal_p (op1
, opb1
)
1488 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1493 /* A < B or A > B imply A != B. TODO: Likewise
1494 A + n < B implies A != B + n if neither wraps. */
1495 if (GET_CODE (b
) == NE
1496 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1497 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1499 if (rtx_equal_p (op0
, opb0
)
1500 && rtx_equal_p (op1
, opb1
))
1504 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1505 if (GET_CODE (a
) == NE
1506 && op1
== const0_rtx
)
1508 if ((GET_CODE (b
) == GTU
1509 && opb1
== const0_rtx
)
1510 || (GET_CODE (b
) == GEU
1511 && opb1
== const1_rtx
))
1512 return rtx_equal_p (op0
, opb0
);
1515 /* A != N is equivalent to A - (N + 1) <u -1. */
1516 if (GET_CODE (a
) == NE
1517 && GET_CODE (op1
) == CONST_INT
1518 && GET_CODE (b
) == LTU
1519 && opb1
== constm1_rtx
1520 && GET_CODE (opb0
) == PLUS
1521 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1522 /* Avoid overflows. */
1523 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1524 != ((unsigned HOST_WIDE_INT
)1
1525 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1526 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1527 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1529 /* Likewise, A != N implies A - N > 0. */
1530 if (GET_CODE (a
) == NE
1531 && GET_CODE (op1
) == CONST_INT
)
1533 if (GET_CODE (b
) == GTU
1534 && GET_CODE (opb0
) == PLUS
1535 && opb1
== const0_rtx
1536 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1537 /* Avoid overflows. */
1538 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1539 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1540 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1541 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1542 if (GET_CODE (b
) == GEU
1543 && GET_CODE (opb0
) == PLUS
1544 && opb1
== const1_rtx
1545 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1546 /* Avoid overflows. */
1547 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1548 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1549 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1550 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1553 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1554 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1555 && GET_CODE (op1
) == CONST_INT
1556 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1557 || INTVAL (op1
) >= 0)
1558 && GET_CODE (b
) == LTU
1559 && GET_CODE (opb1
) == CONST_INT
1560 && rtx_equal_p (op0
, opb0
))
1561 return INTVAL (opb1
) < 0;
1566 /* Canonicalizes COND so that
1568 (1) Ensure that operands are ordered according to
1569 swap_commutative_operands_p.
1570 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1571 for GE, GEU, and LEU. */
1574 canon_condition (rtx cond
)
1579 enum machine_mode mode
;
1581 code
= GET_CODE (cond
);
1582 op0
= XEXP (cond
, 0);
1583 op1
= XEXP (cond
, 1);
1585 if (swap_commutative_operands_p (op0
, op1
))
1587 code
= swap_condition (code
);
1593 mode
= GET_MODE (op0
);
1594 if (mode
== VOIDmode
)
1595 mode
= GET_MODE (op1
);
1596 gcc_assert (mode
!= VOIDmode
);
1598 if (GET_CODE (op1
) == CONST_INT
1599 && GET_MODE_CLASS (mode
) != MODE_CC
1600 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1602 HOST_WIDE_INT const_val
= INTVAL (op1
);
1603 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1604 unsigned HOST_WIDE_INT max_val
1605 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1610 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1611 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1614 /* When cross-compiling, const_val might be sign-extended from
1615 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1617 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1618 != (((HOST_WIDE_INT
) 1
1619 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1620 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1624 if (uconst_val
< max_val
)
1625 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1629 if (uconst_val
!= 0)
1630 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1638 if (op0
!= XEXP (cond
, 0)
1639 || op1
!= XEXP (cond
, 1)
1640 || code
!= GET_CODE (cond
)
1641 || GET_MODE (cond
) != SImode
)
1642 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1647 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1648 set of altered regs. */
1651 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1653 rtx rev
, reve
, exp
= *expr
;
1655 if (!COMPARISON_P (exp
))
1658 /* If some register gets altered later, we do not really speak about its
1659 value at the time of comparison. */
1661 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1664 rev
= reversed_condition (cond
);
1665 reve
= reversed_condition (exp
);
1667 cond
= canon_condition (cond
);
1668 exp
= canon_condition (exp
);
1670 rev
= canon_condition (rev
);
1672 reve
= canon_condition (reve
);
1674 if (rtx_equal_p (exp
, cond
))
1676 *expr
= const_true_rtx
;
1681 if (rev
&& rtx_equal_p (exp
, rev
))
1687 if (implies_p (cond
, exp
))
1689 *expr
= const_true_rtx
;
1693 if (reve
&& implies_p (cond
, reve
))
1699 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1701 if (rev
&& implies_p (exp
, rev
))
1707 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1708 if (rev
&& reve
&& implies_p (reve
, rev
))
1710 *expr
= const_true_rtx
;
1714 /* We would like to have some other tests here. TODO. */
1719 /* Use relationship between A and *B to eventually eliminate *B.
1720 OP is the operation we consider. */
1723 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1728 /* If A implies *B, we may replace *B by true. */
1729 if (implies_p (a
, *b
))
1730 *b
= const_true_rtx
;
1734 /* If *B implies A, we may replace *B by false. */
1735 if (implies_p (*b
, a
))
1744 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1745 operation we consider. */
1748 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1752 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1753 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1754 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1755 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1758 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1759 is a list, its elements are assumed to be combined using OP. */
1762 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1764 rtx head
, tail
, insn
;
1772 if (CONSTANT_P (*expr
))
1775 if (GET_CODE (*expr
) == EXPR_LIST
)
1777 head
= XEXP (*expr
, 0);
1778 tail
= XEXP (*expr
, 1);
1780 eliminate_implied_conditions (op
, &head
, tail
);
1785 neutral
= const_true_rtx
;
1790 neutral
= const0_rtx
;
1791 aggr
= const_true_rtx
;
1798 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1801 XEXP (*expr
, 0) = aggr
;
1802 XEXP (*expr
, 1) = NULL_RTX
;
1805 else if (head
== neutral
)
1808 simplify_using_initial_values (loop
, op
, expr
);
1811 simplify_using_initial_values (loop
, op
, &tail
);
1813 if (tail
&& XEXP (tail
, 0) == aggr
)
1819 XEXP (*expr
, 0) = head
;
1820 XEXP (*expr
, 1) = tail
;
1824 gcc_assert (op
== UNKNOWN
);
1826 e
= loop_preheader_edge (loop
);
1827 if (e
->src
== ENTRY_BLOCK_PTR
)
1830 altered
= ALLOC_REG_SET (®_obstack
);
1834 insn
= BB_END (e
->src
);
1835 if (any_condjump_p (insn
))
1837 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1839 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1840 cond
= reversed_condition (cond
);
1843 simplify_using_condition (cond
, expr
, altered
);
1844 if (CONSTANT_P (*expr
))
1846 FREE_REG_SET (altered
);
1852 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1857 simplify_using_assignment (insn
, expr
, altered
);
1858 if (CONSTANT_P (*expr
))
1860 FREE_REG_SET (altered
);
1863 if (for_each_rtx (expr
, altered_reg_used
, altered
))
1865 FREE_REG_SET (altered
);
1870 if (!single_pred_p (e
->src
)
1871 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
1873 e
= single_pred_edge (e
->src
);
1876 FREE_REG_SET (altered
);
1879 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1880 that IV occurs as left operands of comparison COND and its signedness
1881 is SIGNED_P to DESC. */
1884 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1885 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1887 rtx mmin
, mmax
, cond_over
, cond_under
;
1889 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1890 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1892 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1901 if (cond_under
!= const0_rtx
)
1903 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1904 if (cond_over
!= const0_rtx
)
1905 desc
->noloop_assumptions
=
1906 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1913 if (cond_over
!= const0_rtx
)
1915 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1916 if (cond_under
!= const0_rtx
)
1917 desc
->noloop_assumptions
=
1918 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1922 if (cond_over
!= const0_rtx
)
1924 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1925 if (cond_under
!= const0_rtx
)
1927 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1935 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1938 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1939 subregs of the same mode if possible (sometimes it is necessary to add
1940 some assumptions to DESC). */
1943 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1944 enum rtx_code cond
, struct niter_desc
*desc
)
1946 enum machine_mode comp_mode
;
1949 /* If the ivs behave specially in the first iteration, or are
1950 added/multiplied after extending, we ignore them. */
1951 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1953 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1956 /* If there is some extend, it must match signedness of the comparison. */
1961 if (iv0
->extend
== ZERO_EXTEND
1962 || iv1
->extend
== ZERO_EXTEND
)
1969 if (iv0
->extend
== SIGN_EXTEND
1970 || iv1
->extend
== SIGN_EXTEND
)
1976 if (iv0
->extend
!= UNKNOWN
1977 && iv1
->extend
!= UNKNOWN
1978 && iv0
->extend
!= iv1
->extend
)
1982 if (iv0
->extend
!= UNKNOWN
)
1983 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1984 if (iv1
->extend
!= UNKNOWN
)
1985 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1992 /* Values of both variables should be computed in the same mode. These
1993 might indeed be different, if we have comparison like
1995 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1997 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1998 in different modes. This does not seem impossible to handle, but
1999 it hardly ever occurs in practice.
2001 The only exception is the case when one of operands is invariant.
2002 For example pentium 3 generates comparisons like
2003 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2004 definitely do not want this prevent the optimization. */
2005 comp_mode
= iv0
->extend_mode
;
2006 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2007 comp_mode
= iv1
->extend_mode
;
2009 if (iv0
->extend_mode
!= comp_mode
)
2011 if (iv0
->mode
!= iv0
->extend_mode
2012 || iv0
->step
!= const0_rtx
)
2015 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2016 comp_mode
, iv0
->base
, iv0
->mode
);
2017 iv0
->extend_mode
= comp_mode
;
2020 if (iv1
->extend_mode
!= comp_mode
)
2022 if (iv1
->mode
!= iv1
->extend_mode
2023 || iv1
->step
!= const0_rtx
)
2026 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2027 comp_mode
, iv1
->base
, iv1
->mode
);
2028 iv1
->extend_mode
= comp_mode
;
2031 /* Check that both ivs belong to a range of a single mode. If one of the
2032 operands is an invariant, we may need to shorten it into the common
2034 if (iv0
->mode
== iv0
->extend_mode
2035 && iv0
->step
== const0_rtx
2036 && iv0
->mode
!= iv1
->mode
)
2037 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2039 if (iv1
->mode
== iv1
->extend_mode
2040 && iv1
->step
== const0_rtx
2041 && iv0
->mode
!= iv1
->mode
)
2042 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2044 if (iv0
->mode
!= iv1
->mode
)
2047 desc
->mode
= iv0
->mode
;
2048 desc
->signed_p
= signed_p
;
2053 /* Tries to estimate the maximum number of iterations. */
2055 static unsigned HOST_WIDEST_INT
2056 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
)
2058 rtx niter
= desc
->niter_expr
;
2059 rtx mmin
, mmax
, cmp
;
2060 unsigned HOST_WIDEST_INT nmax
, inc
;
2062 if (GET_CODE (niter
) == AND
2063 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
2065 nmax
= INTVAL (XEXP (niter
, 0));
2066 if (!(nmax
& (nmax
+ 1)))
2068 desc
->niter_max
= nmax
;
2073 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2074 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2076 if (GET_CODE (niter
) == UDIV
)
2078 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
2080 desc
->niter_max
= nmax
;
2083 inc
= INTVAL (XEXP (niter
, 1));
2084 niter
= XEXP (niter
, 0);
2089 /* We could use a binary search here, but for now improving the upper
2090 bound by just one eliminates one important corner case. */
2091 cmp
= gen_rtx_fmt_ee (desc
->signed_p
? LT
: LTU
, VOIDmode
, niter
, mmax
);
2092 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2093 if (cmp
== const_true_rtx
)
2098 fprintf (dump_file
, ";; improved upper bound by one.\n");
2100 desc
->niter_max
= nmax
/ inc
;
2104 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2105 the result into DESC. Very similar to determine_number_of_iterations
2106 (basically its rtl version), complicated by things like subregs. */
2109 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2110 struct niter_desc
*desc
)
2112 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2113 struct rtx_iv iv0
, iv1
, tmp_iv
;
2114 rtx assumption
, may_not_xform
;
2116 enum machine_mode mode
, comp_mode
;
2117 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2118 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2119 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2120 int was_sharp
= false;
2124 /* The meaning of these assumptions is this:
2126 then the rest of information does not have to be valid
2127 if noloop_assumptions then the loop does not roll
2128 if infinite then this exit is never used */
2130 desc
->assumptions
= NULL_RTX
;
2131 desc
->noloop_assumptions
= NULL_RTX
;
2132 desc
->infinite
= NULL_RTX
;
2133 desc
->simple_p
= true;
2135 desc
->const_iter
= false;
2136 desc
->niter_expr
= NULL_RTX
;
2137 desc
->niter_max
= 0;
2139 cond
= GET_CODE (condition
);
2140 gcc_assert (COMPARISON_P (condition
));
2142 mode
= GET_MODE (XEXP (condition
, 0));
2143 if (mode
== VOIDmode
)
2144 mode
= GET_MODE (XEXP (condition
, 1));
2145 /* The constant comparisons should be folded. */
2146 gcc_assert (mode
!= VOIDmode
);
2148 /* We only handle integers or pointers. */
2149 if (GET_MODE_CLASS (mode
) != MODE_INT
2150 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2153 op0
= XEXP (condition
, 0);
2154 if (!iv_analyze (insn
, op0
, &iv0
))
2156 if (iv0
.extend_mode
== VOIDmode
)
2157 iv0
.mode
= iv0
.extend_mode
= mode
;
2159 op1
= XEXP (condition
, 1);
2160 if (!iv_analyze (insn
, op1
, &iv1
))
2162 if (iv1
.extend_mode
== VOIDmode
)
2163 iv1
.mode
= iv1
.extend_mode
= mode
;
2165 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2166 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2169 /* Check condition and normalize it. */
2177 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2178 cond
= swap_condition (cond
);
2190 /* Handle extends. This is relatively nontrivial, so we only try in some
2191 easy cases, when we can canonicalize the ivs (possibly by adding some
2192 assumptions) to shape subreg (base + i * step). This function also fills
2193 in desc->mode and desc->signed_p. */
2195 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2198 comp_mode
= iv0
.extend_mode
;
2200 size
= GET_MODE_BITSIZE (mode
);
2201 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2202 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2203 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2205 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2208 /* We can take care of the case of two induction variables chasing each other
2209 if the test is NE. I have never seen a loop using it, but still it is
2211 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2216 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2217 iv1
.step
= const0_rtx
;
2220 /* This is either infinite loop or the one that ends immediately, depending
2221 on initial values. Unswitching should remove this kind of conditions. */
2222 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2227 if (iv0
.step
== const0_rtx
)
2228 step_val
= -INTVAL (iv1
.step
);
2230 step_val
= INTVAL (iv0
.step
);
2232 /* Ignore loops of while (i-- < 10) type. */
2236 step_is_pow2
= !(step_val
& (step_val
- 1));
2240 /* We do not care about whether the step is power of two in this
2242 step_is_pow2
= false;
2246 /* Some more condition normalization. We must record some assumptions
2247 due to overflows. */
2252 /* We want to take care only of non-sharp relationals; this is easy,
2253 as in cases the overflow would make the transformation unsafe
2254 the loop does not roll. Seemingly it would make more sense to want
2255 to take care of sharp relationals instead, as NE is more similar to
2256 them, but the problem is that here the transformation would be more
2257 difficult due to possibly infinite loops. */
2258 if (iv0
.step
== const0_rtx
)
2260 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2261 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2263 if (assumption
== const_true_rtx
)
2264 goto zero_iter_simplify
;
2265 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2266 iv0
.base
, const1_rtx
);
2270 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2271 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2273 if (assumption
== const_true_rtx
)
2274 goto zero_iter_simplify
;
2275 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2276 iv1
.base
, constm1_rtx
);
2279 if (assumption
!= const0_rtx
)
2280 desc
->noloop_assumptions
=
2281 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2282 cond
= (cond
== LT
) ? LE
: LEU
;
2284 /* It will be useful to be able to tell the difference once more in
2285 LE -> NE reduction. */
2291 /* Take care of trivially infinite loops. */
2294 if (iv0
.step
== const0_rtx
)
2296 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2297 if (rtx_equal_p (tmp
, mode_mmin
))
2300 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2301 /* Fill in the remaining fields somehow. */
2302 goto zero_iter_simplify
;
2307 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2308 if (rtx_equal_p (tmp
, mode_mmax
))
2311 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2312 /* Fill in the remaining fields somehow. */
2313 goto zero_iter_simplify
;
2318 /* If we can we want to take care of NE conditions instead of size
2319 comparisons, as they are much more friendly (most importantly
2320 this takes care of special handling of loops with step 1). We can
2321 do it if we first check that upper bound is greater or equal to
2322 lower bound, their difference is constant c modulo step and that
2323 there is not an overflow. */
2326 if (iv0
.step
== const0_rtx
)
2327 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2330 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2331 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2332 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2333 may_xform
= const0_rtx
;
2334 may_not_xform
= const_true_rtx
;
2336 if (GET_CODE (delta
) == CONST_INT
)
2338 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2340 /* A special case. We have transformed condition of type
2341 for (i = 0; i < 4; i += 4)
2343 for (i = 0; i <= 3; i += 4)
2344 obviously if the test for overflow during that transformation
2345 passed, we cannot overflow here. Most importantly any
2346 loop with sharp end condition and step 1 falls into this
2347 category, so handling this case specially is definitely
2348 worth the troubles. */
2349 may_xform
= const_true_rtx
;
2351 else if (iv0
.step
== const0_rtx
)
2353 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2354 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2355 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2356 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2357 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2359 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2365 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2366 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2367 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2368 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2369 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2371 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2377 if (may_xform
!= const0_rtx
)
2379 /* We perform the transformation always provided that it is not
2380 completely senseless. This is OK, as we would need this assumption
2381 to determine the number of iterations anyway. */
2382 if (may_xform
!= const_true_rtx
)
2384 /* If the step is a power of two and the final value we have
2385 computed overflows, the cycle is infinite. Otherwise it
2386 is nontrivial to compute the number of iterations. */
2388 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2391 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2395 /* We are going to lose some information about upper bound on
2396 number of iterations in this step, so record the information
2398 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2399 if (GET_CODE (iv1
.base
) == CONST_INT
)
2400 up
= INTVAL (iv1
.base
);
2402 up
= INTVAL (mode_mmax
) - inc
;
2403 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2406 desc
->niter_max
= (up
- down
) / inc
+ 1;
2408 if (iv0
.step
== const0_rtx
)
2410 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2411 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2415 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2416 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2419 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2420 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2421 assumption
= simplify_gen_relational (reverse_condition (cond
),
2422 SImode
, mode
, tmp0
, tmp1
);
2423 if (assumption
== const_true_rtx
)
2424 goto zero_iter_simplify
;
2425 else if (assumption
!= const0_rtx
)
2426 desc
->noloop_assumptions
=
2427 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2432 /* Count the number of iterations. */
2435 /* Everything we do here is just arithmetics modulo size of mode. This
2436 makes us able to do more involved computations of number of iterations
2437 than in other cases. First transform the condition into shape
2438 s * i <> c, with s positive. */
2439 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2440 iv0
.base
= const0_rtx
;
2441 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2442 iv1
.step
= const0_rtx
;
2443 if (INTVAL (iv0
.step
) < 0)
2445 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2446 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2448 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2450 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2451 is infinite. Otherwise, the number of iterations is
2452 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2453 s
= INTVAL (iv0
.step
); d
= 1;
2460 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2462 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2463 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2464 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2465 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2467 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2468 inv
= inverse (s
, size
);
2469 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2470 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2474 if (iv1
.step
== const0_rtx
)
2475 /* Condition in shape a + s * i <= b
2476 We must know that b + s does not overflow and a <= b + s and then we
2477 can compute number of iterations as (b + s - a) / s. (It might
2478 seem that we in fact could be more clever about testing the b + s
2479 overflow condition using some information about b - a mod s,
2480 but it was already taken into account during LE -> NE transform). */
2483 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2484 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2486 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2487 lowpart_subreg (mode
, step
,
2493 /* If s is power of 2, we know that the loop is infinite if
2494 a % s <= b % s and b + s overflows. */
2495 assumption
= simplify_gen_relational (reverse_condition (cond
),
2499 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2500 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2501 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2502 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2504 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2508 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2511 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2514 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2515 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2516 assumption
= simplify_gen_relational (reverse_condition (cond
),
2517 SImode
, mode
, tmp0
, tmp
);
2519 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2520 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2524 /* Condition in shape a <= b - s * i
2525 We must know that a - s does not overflow and a - s <= b and then
2526 we can again compute number of iterations as (b - (a - s)) / s. */
2527 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2528 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2529 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2531 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2532 lowpart_subreg (mode
, step
, comp_mode
));
2537 /* If s is power of 2, we know that the loop is infinite if
2538 a % s <= b % s and a - s overflows. */
2539 assumption
= simplify_gen_relational (reverse_condition (cond
),
2543 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2544 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2545 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2546 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2548 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2552 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2555 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2558 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2559 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2560 assumption
= simplify_gen_relational (reverse_condition (cond
),
2563 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2564 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2566 if (assumption
== const_true_rtx
)
2567 goto zero_iter_simplify
;
2568 else if (assumption
!= const0_rtx
)
2569 desc
->noloop_assumptions
=
2570 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2571 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2572 desc
->niter_expr
= delta
;
2575 old_niter
= desc
->niter_expr
;
2577 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2578 if (desc
->assumptions
2579 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2581 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2582 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2583 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2585 /* Rerun the simplification. Consider code (created by copying loop headers)
2597 The first pass determines that i = 0, the second pass uses it to eliminate
2598 noloop assumption. */
2600 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2601 if (desc
->assumptions
2602 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2604 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2605 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2606 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2608 if (desc
->noloop_assumptions
2609 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2612 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2614 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2616 desc
->const_iter
= true;
2617 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2621 if (!desc
->niter_max
)
2622 desc
->niter_max
= determine_max_iter (loop
, desc
);
2624 /* simplify_using_initial_values does a copy propagation on the registers
2625 in the expression for the number of iterations. This prolongs life
2626 ranges of registers and increases register pressure, and usually
2627 brings no gain (and if it happens to do, the cse pass will take care
2628 of it anyway). So prevent this behavior, unless it enabled us to
2629 derive that the number of iterations is a constant. */
2630 desc
->niter_expr
= old_niter
;
2636 /* Simplify the assumptions. */
2637 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2638 if (desc
->assumptions
2639 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2641 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2645 desc
->const_iter
= true;
2647 desc
->niter_max
= 0;
2648 desc
->noloop_assumptions
= NULL_RTX
;
2649 desc
->niter_expr
= const0_rtx
;
2653 desc
->simple_p
= false;
2657 /* Checks whether E is a simple exit from LOOP and stores its description
2661 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2663 basic_block exit_bb
;
2668 desc
->simple_p
= false;
2670 /* It must belong directly to the loop. */
2671 if (exit_bb
->loop_father
!= loop
)
2674 /* It must be tested (at least) once during any iteration. */
2675 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2678 /* It must end in a simple conditional jump. */
2679 if (!any_condjump_p (BB_END (exit_bb
)))
2682 ein
= EDGE_SUCC (exit_bb
, 0);
2684 ein
= EDGE_SUCC (exit_bb
, 1);
2687 desc
->in_edge
= ein
;
2689 /* Test whether the condition is suitable. */
2690 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2693 if (ein
->flags
& EDGE_FALLTHRU
)
2695 condition
= reversed_condition (condition
);
2700 /* Check that we are able to determine number of iterations and fill
2701 in information about it. */
2702 iv_number_of_iterations (loop
, at
, condition
, desc
);
2705 /* Finds a simple exit of LOOP and stores its description into DESC. */
2708 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2713 struct niter_desc act
;
2717 desc
->simple_p
= false;
2718 body
= get_loop_body (loop
);
2720 for (i
= 0; i
< loop
->num_nodes
; i
++)
2722 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2724 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2727 check_simple_exit (loop
, e
, &act
);
2735 /* Prefer constant iterations; the less the better. */
2737 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2740 /* Also if the actual exit may be infinite, while the old one
2741 not, prefer the old one. */
2742 if (act
.infinite
&& !desc
->infinite
)
2754 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2755 fprintf (dump_file
, " simple exit %d -> %d\n",
2756 desc
->out_edge
->src
->index
,
2757 desc
->out_edge
->dest
->index
);
2758 if (desc
->assumptions
)
2760 fprintf (dump_file
, " assumptions: ");
2761 print_rtl (dump_file
, desc
->assumptions
);
2762 fprintf (dump_file
, "\n");
2764 if (desc
->noloop_assumptions
)
2766 fprintf (dump_file
, " does not roll if: ");
2767 print_rtl (dump_file
, desc
->noloop_assumptions
);
2768 fprintf (dump_file
, "\n");
2772 fprintf (dump_file
, " infinite if: ");
2773 print_rtl (dump_file
, desc
->infinite
);
2774 fprintf (dump_file
, "\n");
2777 fprintf (dump_file
, " number of iterations: ");
2778 print_rtl (dump_file
, desc
->niter_expr
);
2779 fprintf (dump_file
, "\n");
2781 fprintf (dump_file
, " upper bound: ");
2782 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2783 fprintf (dump_file
, "\n");
2786 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2792 /* Creates a simple loop description of LOOP if it was not computed
2796 get_simple_loop_desc (struct loop
*loop
)
2798 struct niter_desc
*desc
= simple_loop_desc (loop
);
2803 desc
= XNEW (struct niter_desc
);
2804 iv_analysis_loop_init (loop
);
2805 find_simple_exit (loop
, desc
);
2808 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
2810 const char *wording
;
2812 /* Assume that no overflow happens and that the loop is finite.
2813 We already warned at the tree level if we ran optimizations there. */
2814 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
2819 flag_unsafe_loop_optimizations
2820 ? N_("assuming that the loop is not infinite")
2821 : N_("cannot optimize possibly infinite loops");
2822 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2825 if (desc
->assumptions
)
2828 flag_unsafe_loop_optimizations
2829 ? N_("assuming that the loop counter does not overflow")
2830 : N_("cannot optimize loop, the loop counter may overflow");
2831 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2836 if (flag_unsafe_loop_optimizations
)
2838 desc
->assumptions
= NULL_RTX
;
2839 desc
->infinite
= NULL_RTX
;
2846 /* Releases simple loop description for LOOP. */
2849 free_simple_loop_desc (struct loop
*loop
)
2851 struct niter_desc
*desc
= simple_loop_desc (loop
);