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 variable is analyzed by walking the use-def chains. When a biv
26 is found, it is cached in the bivs hash table. When register is proved
27 to be a giv, its description is stored to DF_REF_DATA of the def reference.
29 The analysis works always with one loop -- you must call
30 iv_analysis_loop_init (loop) for it. All the other functions then work with
31 this loop. When you need to work with another loop, just call
32 iv_analysis_loop_init for it. When you no longer need iv analysis, call
33 iv_analysis_done () to clean up the memory.
35 The available functions are:
37 iv_analyze (insn, reg, iv): Stores the description of the induction variable
38 corresponding to the use of register REG in INSN to IV. Returns true if
39 REG is an induction variable in INSN. false otherwise.
40 If use of REG is not found in INSN, following insns are scanned (so that
41 we may call this function on insn returned by get_condition).
42 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
43 corresponding to DEF, which is a register defined in INSN.
44 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
45 corresponding to expression EXPR evaluated at INSN. All registers used bu
46 EXPR must also be used in INSN.
51 #include "coretypes.h"
54 #include "hard-reg-set.h"
56 #include "basic-block.h"
65 /* Possible return values of iv_get_reaching_def. */
69 /* More than one reaching def, or reaching def that does not
73 /* The use is trivial invariant of the loop, i.e. is not changed
77 /* The use is reached by initial value and a value from the
78 previous iteration. */
81 /* The use has single dominating def. */
85 /* Information about a biv. */
89 unsigned regno
; /* The register of the biv. */
90 struct rtx_iv iv
; /* Value of the biv. */
93 static bool clean_slate
= true;
95 static unsigned int iv_ref_table_size
= 0;
97 /* Table of rtx_ivs indexed by the df_ref uid field. */
98 static struct rtx_iv
** iv_ref_table
;
100 /* Induction variable stored at the reference. */
101 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
102 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
104 /* The current loop. */
106 static struct loop
*current_loop
;
108 /* Bivs of the current loop. */
112 static bool iv_analyze_op (rtx
, rtx
, struct rtx_iv
*);
114 /* Dumps information about IV to FILE. */
116 extern void dump_iv_info (FILE *, struct rtx_iv
*);
118 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
122 fprintf (file
, "not simple");
126 if (iv
->step
== const0_rtx
127 && !iv
->first_special
)
128 fprintf (file
, "invariant ");
130 print_rtl (file
, iv
->base
);
131 if (iv
->step
!= const0_rtx
)
133 fprintf (file
, " + ");
134 print_rtl (file
, iv
->step
);
135 fprintf (file
, " * iteration");
137 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
139 if (iv
->mode
!= iv
->extend_mode
)
140 fprintf (file
, " %s to %s",
141 rtx_name
[iv
->extend
],
142 GET_MODE_NAME (iv
->extend_mode
));
144 if (iv
->mult
!= const1_rtx
)
146 fprintf (file
, " * ");
147 print_rtl (file
, iv
->mult
);
149 if (iv
->delta
!= const0_rtx
)
151 fprintf (file
, " + ");
152 print_rtl (file
, iv
->delta
);
154 if (iv
->first_special
)
155 fprintf (file
, " (first special)");
158 /* Generates a subreg to get the least significant part of EXPR (in mode
159 INNER_MODE) to OUTER_MODE. */
162 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
163 enum machine_mode inner_mode
)
165 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
166 subreg_lowpart_offset (outer_mode
, inner_mode
));
170 check_iv_ref_table_size (void)
172 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE())
174 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
175 iv_ref_table
= xrealloc (iv_ref_table
,
176 sizeof (struct rtx_iv
*) * 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
, struct df_ref
**def
)
298 struct 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
= adef
->next_reg
)
304 if (!bitmap_bit_p (bb_info
->out
, DF_REF_ID (adef
)))
307 /* More than one reaching definition. */
311 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
321 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
323 static enum iv_grd_result
324 iv_get_reaching_def (rtx insn
, rtx reg
, struct df_ref
**def
)
326 struct df_ref
*use
, *adef
;
327 basic_block def_bb
, use_bb
;
332 if (!simple_reg_p (reg
))
334 if (GET_CODE (reg
) == SUBREG
)
335 reg
= SUBREG_REG (reg
);
336 gcc_assert (REG_P (reg
));
338 use
= df_find_use (insn
, reg
);
339 gcc_assert (use
!= NULL
);
341 if (!DF_REF_CHAIN (use
))
342 return GRD_INVARIANT
;
344 /* More than one reaching def. */
345 if (DF_REF_CHAIN (use
)->next
)
348 adef
= DF_REF_CHAIN (use
)->ref
;
350 /* We do not handle setting only part of the register. */
351 if (adef
->flags
& DF_REF_READ_WRITE
)
354 def_insn
= DF_REF_INSN (adef
);
355 def_bb
= DF_REF_BB (adef
);
356 use_bb
= BLOCK_FOR_INSN (insn
);
358 if (use_bb
== def_bb
)
359 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
361 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
366 return GRD_SINGLE_DOM
;
369 /* The definition does not dominate the use. This is still OK if
370 this may be a use of a biv, i.e. if the def_bb dominates loop
372 if (just_once_each_iteration_p (current_loop
, def_bb
))
373 return GRD_MAYBE_BIV
;
378 /* Sets IV to invariant CST in MODE. Always returns true (just for
379 consistency with other iv manipulation functions that may fail). */
382 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
384 if (mode
== VOIDmode
)
385 mode
= GET_MODE (cst
);
389 iv
->step
= const0_rtx
;
390 iv
->first_special
= false;
391 iv
->extend
= UNKNOWN
;
392 iv
->extend_mode
= iv
->mode
;
393 iv
->delta
= const0_rtx
;
394 iv
->mult
= const1_rtx
;
399 /* Evaluates application of subreg to MODE on IV. */
402 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
404 /* If iv is invariant, just calculate the new value. */
405 if (iv
->step
== const0_rtx
406 && !iv
->first_special
)
408 rtx val
= get_iv_value (iv
, const0_rtx
);
409 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
412 iv
->extend
= UNKNOWN
;
413 iv
->mode
= iv
->extend_mode
= mode
;
414 iv
->delta
= const0_rtx
;
415 iv
->mult
= const1_rtx
;
419 if (iv
->extend_mode
== mode
)
422 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
425 iv
->extend
= UNKNOWN
;
428 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
429 simplify_gen_binary (MULT
, iv
->extend_mode
,
430 iv
->base
, iv
->mult
));
431 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
432 iv
->mult
= const1_rtx
;
433 iv
->delta
= const0_rtx
;
434 iv
->first_special
= false;
439 /* Evaluates application of EXTEND to MODE on IV. */
442 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
444 /* If iv is invariant, just calculate the new value. */
445 if (iv
->step
== const0_rtx
446 && !iv
->first_special
)
448 rtx val
= get_iv_value (iv
, const0_rtx
);
449 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
452 iv
->extend
= UNKNOWN
;
453 iv
->mode
= iv
->extend_mode
= mode
;
454 iv
->delta
= const0_rtx
;
455 iv
->mult
= const1_rtx
;
459 if (mode
!= iv
->extend_mode
)
462 if (iv
->extend
!= UNKNOWN
463 && iv
->extend
!= extend
)
471 /* Evaluates negation of IV. */
474 iv_neg (struct rtx_iv
*iv
)
476 if (iv
->extend
== UNKNOWN
)
478 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
479 iv
->base
, iv
->extend_mode
);
480 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
481 iv
->step
, iv
->extend_mode
);
485 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
486 iv
->delta
, iv
->extend_mode
);
487 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
488 iv
->mult
, iv
->extend_mode
);
494 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
497 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
499 enum machine_mode mode
;
502 /* Extend the constant to extend_mode of the other operand if necessary. */
503 if (iv0
->extend
== UNKNOWN
504 && iv0
->mode
== iv0
->extend_mode
505 && iv0
->step
== const0_rtx
506 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
508 iv0
->extend_mode
= iv1
->extend_mode
;
509 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
510 iv0
->base
, iv0
->mode
);
512 if (iv1
->extend
== UNKNOWN
513 && iv1
->mode
== iv1
->extend_mode
514 && iv1
->step
== const0_rtx
515 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
517 iv1
->extend_mode
= iv0
->extend_mode
;
518 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
519 iv1
->base
, iv1
->mode
);
522 mode
= iv0
->extend_mode
;
523 if (mode
!= iv1
->extend_mode
)
526 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
528 if (iv0
->mode
!= iv1
->mode
)
531 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
532 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
537 /* Handle addition of constant. */
538 if (iv1
->extend
== UNKNOWN
540 && iv1
->step
== const0_rtx
)
542 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
546 if (iv0
->extend
== UNKNOWN
548 && iv0
->step
== const0_rtx
)
556 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
563 /* Evaluates multiplication of IV by constant CST. */
566 iv_mult (struct rtx_iv
*iv
, rtx mby
)
568 enum machine_mode mode
= iv
->extend_mode
;
570 if (GET_MODE (mby
) != VOIDmode
571 && GET_MODE (mby
) != mode
)
574 if (iv
->extend
== UNKNOWN
)
576 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
577 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
581 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
582 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
588 /* Evaluates shift of IV by constant CST. */
591 iv_shift (struct rtx_iv
*iv
, rtx mby
)
593 enum machine_mode mode
= iv
->extend_mode
;
595 if (GET_MODE (mby
) != VOIDmode
596 && GET_MODE (mby
) != mode
)
599 if (iv
->extend
== UNKNOWN
)
601 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
602 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
606 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
607 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
613 /* The recursive part of get_biv_step. Gets the value of the single value
614 defined by DEF wrto initial value of REG inside loop, in shape described
618 get_biv_step_1 (struct df_ref
*def
, rtx reg
,
619 rtx
*inner_step
, enum machine_mode
*inner_mode
,
620 enum rtx_code
*extend
, enum machine_mode outer_mode
,
623 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
624 rtx next
, nextr
, tmp
;
626 rtx insn
= DF_REF_INSN (def
);
627 struct df_ref
*next_def
;
628 enum iv_grd_result res
;
630 set
= single_set (insn
);
634 rhs
= find_reg_equal_equiv_note (insn
);
640 code
= GET_CODE (rhs
);
653 if (code
== PLUS
&& CONSTANT_P (op0
))
655 tmp
= op0
; op0
= op1
; op1
= tmp
;
658 if (!simple_reg_p (op0
)
659 || !CONSTANT_P (op1
))
662 if (GET_MODE (rhs
) != outer_mode
)
664 /* ppc64 uses expressions like
666 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
668 this is equivalent to
670 (set x':DI (plus:DI y:DI 1))
671 (set x:SI (subreg:SI (x':DI)). */
672 if (GET_CODE (op0
) != SUBREG
)
674 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
683 if (GET_MODE (rhs
) != outer_mode
)
687 if (!simple_reg_p (op0
))
697 if (GET_CODE (next
) == SUBREG
)
699 if (!subreg_lowpart_p (next
))
702 nextr
= SUBREG_REG (next
);
703 if (GET_MODE (nextr
) != outer_mode
)
709 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
711 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
714 if (res
== GRD_MAYBE_BIV
)
716 if (!rtx_equal_p (nextr
, reg
))
719 *inner_step
= const0_rtx
;
721 *inner_mode
= outer_mode
;
722 *outer_step
= const0_rtx
;
724 else if (!get_biv_step_1 (next_def
, reg
,
725 inner_step
, inner_mode
, extend
, outer_mode
,
729 if (GET_CODE (next
) == SUBREG
)
731 enum machine_mode amode
= GET_MODE (next
);
733 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
737 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
738 *inner_step
, *outer_step
);
739 *outer_step
= const0_rtx
;
751 if (*inner_mode
== outer_mode
752 /* See comment in previous switch. */
753 || GET_MODE (rhs
) != outer_mode
)
754 *inner_step
= simplify_gen_binary (code
, outer_mode
,
757 *outer_step
= simplify_gen_binary (code
, outer_mode
,
763 gcc_assert (GET_MODE (op0
) == *inner_mode
764 && *extend
== UNKNOWN
765 && *outer_step
== const0_rtx
);
777 /* Gets the operation on register REG inside loop, in shape
779 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
781 If the operation cannot be described in this shape, return false.
782 LAST_DEF is the definition of REG that dominates loop latch. */
785 get_biv_step (struct df_ref
*last_def
, rtx reg
, rtx
*inner_step
,
786 enum machine_mode
*inner_mode
, enum rtx_code
*extend
,
787 enum machine_mode
*outer_mode
, rtx
*outer_step
)
789 *outer_mode
= GET_MODE (reg
);
791 if (!get_biv_step_1 (last_def
, reg
,
792 inner_step
, inner_mode
, extend
, *outer_mode
,
796 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= UNKNOWN
));
797 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
802 /* Records information that DEF is induction variable IV. */
805 record_iv (struct df_ref
*def
, struct rtx_iv
*iv
)
807 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
810 check_iv_ref_table_size ();
811 DF_REF_IV_SET (def
, recorded_iv
);
814 /* If DEF was already analyzed for bivness, store the description of the biv to
815 IV and return true. Otherwise return false. */
818 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
820 struct biv_entry
*biv
= htab_find_with_hash (bivs
, def
, REGNO (def
));
830 record_biv (rtx def
, struct rtx_iv
*iv
)
832 struct biv_entry
*biv
= XNEW (struct biv_entry
);
833 void **slot
= htab_find_slot_with_hash (bivs
, def
, REGNO (def
), INSERT
);
835 biv
->regno
= REGNO (def
);
841 /* Determines whether DEF is a biv and if so, stores its description
845 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
847 rtx inner_step
, outer_step
;
848 enum machine_mode inner_mode
, outer_mode
;
849 enum rtx_code extend
;
850 struct df_ref
*last_def
;
854 fprintf (dump_file
, "Analyzing ");
855 print_rtl (dump_file
, def
);
856 fprintf (dump_file
, " for bivness.\n");
861 if (!CONSTANT_P (def
))
864 return iv_constant (iv
, def
, VOIDmode
);
867 if (!latch_dominating_def (def
, &last_def
))
870 fprintf (dump_file
, " not simple.\n");
875 return iv_constant (iv
, def
, VOIDmode
);
877 if (analyzed_for_bivness_p (def
, iv
))
880 fprintf (dump_file
, " already analysed.\n");
881 return iv
->base
!= NULL_RTX
;
884 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
885 &outer_mode
, &outer_step
))
891 /* Loop transforms base to es (base + inner_step) + outer_step,
892 where es means extend of subreg between inner_mode and outer_mode.
893 The corresponding induction variable is
895 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
897 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
898 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
899 iv
->mode
= inner_mode
;
900 iv
->extend_mode
= outer_mode
;
902 iv
->mult
= const1_rtx
;
903 iv
->delta
= outer_step
;
904 iv
->first_special
= inner_mode
!= outer_mode
;
909 fprintf (dump_file
, " ");
910 dump_iv_info (dump_file
, iv
);
911 fprintf (dump_file
, "\n");
914 record_biv (def
, iv
);
915 return iv
->base
!= NULL_RTX
;
918 /* Analyzes expression RHS used at INSN and stores the result to *IV.
919 The mode of the induction variable is MODE. */
922 iv_analyze_expr (rtx insn
, rtx rhs
, enum machine_mode mode
, struct rtx_iv
*iv
)
924 rtx mby
= NULL_RTX
, tmp
;
925 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
926 struct rtx_iv iv0
, iv1
;
927 enum rtx_code code
= GET_CODE (rhs
);
928 enum machine_mode omode
= mode
;
934 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
940 if (!iv_analyze_op (insn
, rhs
, iv
))
943 if (iv
->mode
== VOIDmode
)
946 iv
->extend_mode
= mode
;
962 omode
= GET_MODE (op0
);
974 if (!CONSTANT_P (mby
))
980 if (!CONSTANT_P (mby
))
987 if (!CONSTANT_P (mby
))
996 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1000 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1007 if (!iv_extend (&iv0
, code
, mode
))
1018 if (!iv_add (&iv0
, &iv1
, code
))
1023 if (!iv_mult (&iv0
, mby
))
1028 if (!iv_shift (&iv0
, mby
))
1037 return iv
->base
!= NULL_RTX
;
1040 /* Analyzes iv DEF and stores the result to *IV. */
1043 iv_analyze_def (struct df_ref
*def
, struct rtx_iv
*iv
)
1045 rtx insn
= DF_REF_INSN (def
);
1046 rtx reg
= DF_REF_REG (def
);
1051 fprintf (dump_file
, "Analyzing def of ");
1052 print_rtl (dump_file
, reg
);
1053 fprintf (dump_file
, " in insn ");
1054 print_rtl_single (dump_file
, insn
);
1057 check_iv_ref_table_size ();
1058 if (DF_REF_IV (def
))
1061 fprintf (dump_file
, " already analysed.\n");
1062 *iv
= *DF_REF_IV (def
);
1063 return iv
->base
!= NULL_RTX
;
1066 iv
->mode
= VOIDmode
;
1067 iv
->base
= NULL_RTX
;
1068 iv
->step
= NULL_RTX
;
1073 set
= single_set (insn
);
1077 if (!REG_P (SET_DEST (set
)))
1080 gcc_assert (SET_DEST (set
) == reg
);
1081 rhs
= find_reg_equal_equiv_note (insn
);
1083 rhs
= XEXP (rhs
, 0);
1085 rhs
= SET_SRC (set
);
1087 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1088 record_iv (def
, iv
);
1092 print_rtl (dump_file
, reg
);
1093 fprintf (dump_file
, " in insn ");
1094 print_rtl_single (dump_file
, insn
);
1095 fprintf (dump_file
, " is ");
1096 dump_iv_info (dump_file
, iv
);
1097 fprintf (dump_file
, "\n");
1100 return iv
->base
!= NULL_RTX
;
1103 /* Analyzes operand OP of INSN and stores the result to *IV. */
1106 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1108 struct df_ref
*def
= NULL
;
1109 enum iv_grd_result res
;
1113 fprintf (dump_file
, "Analyzing operand ");
1114 print_rtl (dump_file
, op
);
1115 fprintf (dump_file
, " of insn ");
1116 print_rtl_single (dump_file
, insn
);
1119 if (CONSTANT_P (op
))
1120 res
= GRD_INVARIANT
;
1121 else if (GET_CODE (op
) == SUBREG
)
1123 if (!subreg_lowpart_p (op
))
1126 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1129 return iv_subreg (iv
, GET_MODE (op
));
1133 res
= iv_get_reaching_def (insn
, op
, &def
);
1134 if (res
== GRD_INVALID
)
1137 fprintf (dump_file
, " not simple.\n");
1142 if (res
== GRD_INVARIANT
)
1144 iv_constant (iv
, op
, VOIDmode
);
1148 fprintf (dump_file
, " ");
1149 dump_iv_info (dump_file
, iv
);
1150 fprintf (dump_file
, "\n");
1155 if (res
== GRD_MAYBE_BIV
)
1156 return iv_analyze_biv (op
, iv
);
1158 return iv_analyze_def (def
, iv
);
1161 /* Analyzes value VAL at INSN and stores the result to *IV. */
1164 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
1168 /* We must find the insn in that val is used, so that we get to UD chains.
1169 Since the function is sometimes called on result of get_condition,
1170 this does not necessarily have to be directly INSN; scan also the
1172 if (simple_reg_p (val
))
1174 if (GET_CODE (val
) == SUBREG
)
1175 reg
= SUBREG_REG (val
);
1179 while (!df_find_use (insn
, reg
))
1180 insn
= NEXT_INSN (insn
);
1183 return iv_analyze_op (insn
, val
, iv
);
1186 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1189 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1191 struct df_ref
*adef
;
1193 adef
= df_find_def (insn
, def
);
1197 return iv_analyze_def (adef
, iv
);
1200 /* Checks whether definition of register REG in INSN is a basic induction
1201 variable. IV analysis must have been initialized (via a call to
1202 iv_analysis_loop_init) for this function to produce a result. */
1205 biv_p (rtx insn
, rtx reg
)
1208 struct df_ref
*def
, *last_def
;
1210 if (!simple_reg_p (reg
))
1213 def
= df_find_def (insn
, reg
);
1214 gcc_assert (def
!= NULL
);
1215 if (!latch_dominating_def (reg
, &last_def
))
1217 if (last_def
!= def
)
1220 if (!iv_analyze_biv (reg
, &iv
))
1223 return iv
.step
!= const0_rtx
;
1226 /* Calculates value of IV at ITERATION-th iteration. */
1229 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1233 /* We would need to generate some if_then_else patterns, and so far
1234 it is not needed anywhere. */
1235 gcc_assert (!iv
->first_special
);
1237 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1238 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1239 simplify_gen_binary (MULT
, iv
->extend_mode
,
1240 iv
->step
, iteration
));
1244 if (iv
->extend_mode
== iv
->mode
)
1247 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1249 if (iv
->extend
== UNKNOWN
)
1252 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1253 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1254 simplify_gen_binary (MULT
, iv
->extend_mode
,
1260 /* Free the data for an induction variable analysis. */
1263 iv_analysis_done (void)
1269 df_finish_pass (true);
1271 free (iv_ref_table
);
1272 iv_ref_table
= NULL
;
1273 iv_ref_table_size
= 0;
1278 /* Computes inverse to X modulo (1 << MOD). */
1280 static unsigned HOST_WIDEST_INT
1281 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1283 unsigned HOST_WIDEST_INT mask
=
1284 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1285 unsigned HOST_WIDEST_INT rslt
= 1;
1288 for (i
= 0; i
< mod
- 1; i
++)
1290 rslt
= (rslt
* x
) & mask
;
1297 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1300 altered_reg_used (rtx
*reg
, void *alt
)
1305 return REGNO_REG_SET_P (alt
, REGNO (*reg
));
1308 /* Marks registers altered by EXPR in set ALT. */
1311 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1313 if (GET_CODE (expr
) == SUBREG
)
1314 expr
= SUBREG_REG (expr
);
1318 SET_REGNO_REG_SET (alt
, REGNO (expr
));
1321 /* Checks whether RHS is simple enough to process. */
1324 simple_rhs_p (rtx rhs
)
1328 if (CONSTANT_P (rhs
)
1329 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1332 switch (GET_CODE (rhs
))
1336 op0
= XEXP (rhs
, 0);
1337 op1
= XEXP (rhs
, 1);
1338 /* Allow reg + const sets only. */
1339 if (REG_P (op0
) && !HARD_REGISTER_P (op0
) && CONSTANT_P (op1
))
1341 if (REG_P (op1
) && !HARD_REGISTER_P (op1
) && CONSTANT_P (op0
))
1351 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1355 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1357 rtx set
= single_set (insn
);
1358 rtx lhs
= NULL_RTX
, rhs
;
1363 lhs
= SET_DEST (set
);
1365 || altered_reg_used (&lhs
, altered
))
1371 note_stores (PATTERN (insn
), mark_altered
, altered
);
1376 /* Kill all call clobbered registers. */
1377 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1378 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1379 SET_REGNO_REG_SET (altered
, i
);
1385 rhs
= find_reg_equal_equiv_note (insn
);
1387 rhs
= XEXP (rhs
, 0);
1389 rhs
= SET_SRC (set
);
1391 if (!simple_rhs_p (rhs
))
1394 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1397 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1400 /* Checks whether A implies B. */
1403 implies_p (rtx a
, rtx b
)
1405 rtx op0
, op1
, opb0
, opb1
, r
;
1406 enum machine_mode mode
;
1408 if (GET_CODE (a
) == EQ
)
1415 r
= simplify_replace_rtx (b
, op0
, op1
);
1416 if (r
== const_true_rtx
)
1422 r
= simplify_replace_rtx (b
, op1
, op0
);
1423 if (r
== const_true_rtx
)
1428 if (b
== const_true_rtx
)
1431 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1432 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1433 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1434 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1442 mode
= GET_MODE (op0
);
1443 if (mode
!= GET_MODE (opb0
))
1445 else if (mode
== VOIDmode
)
1447 mode
= GET_MODE (op1
);
1448 if (mode
!= GET_MODE (opb1
))
1452 /* A < B implies A + 1 <= B. */
1453 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1454 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1457 if (GET_CODE (a
) == GT
)
1464 if (GET_CODE (b
) == GE
)
1471 if (SCALAR_INT_MODE_P (mode
)
1472 && rtx_equal_p (op1
, opb1
)
1473 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1478 /* A < B or A > B imply A != B. TODO: Likewise
1479 A + n < B implies A != B + n if neither wraps. */
1480 if (GET_CODE (b
) == NE
1481 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1482 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1484 if (rtx_equal_p (op0
, opb0
)
1485 && rtx_equal_p (op1
, opb1
))
1489 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1490 if (GET_CODE (a
) == NE
1491 && op1
== const0_rtx
)
1493 if ((GET_CODE (b
) == GTU
1494 && opb1
== const0_rtx
)
1495 || (GET_CODE (b
) == GEU
1496 && opb1
== const1_rtx
))
1497 return rtx_equal_p (op0
, opb0
);
1500 /* A != N is equivalent to A - (N + 1) <u -1. */
1501 if (GET_CODE (a
) == NE
1502 && GET_CODE (op1
) == CONST_INT
1503 && GET_CODE (b
) == LTU
1504 && opb1
== constm1_rtx
1505 && GET_CODE (opb0
) == PLUS
1506 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1507 /* Avoid overflows. */
1508 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1509 != ((unsigned HOST_WIDE_INT
)1
1510 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1511 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1512 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1514 /* Likewise, A != N implies A - N > 0. */
1515 if (GET_CODE (a
) == NE
1516 && GET_CODE (op1
) == CONST_INT
)
1518 if (GET_CODE (b
) == GTU
1519 && GET_CODE (opb0
) == PLUS
1520 && opb1
== const0_rtx
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 << (HOST_BITS_PER_WIDE_INT
- 1)))
1525 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1526 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1527 if (GET_CODE (b
) == GEU
1528 && GET_CODE (opb0
) == PLUS
1529 && opb1
== const1_rtx
1530 && GET_CODE (XEXP (opb0
, 1)) == CONST_INT
1531 /* Avoid overflows. */
1532 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1533 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1534 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1535 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1538 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1539 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1540 && GET_CODE (op1
) == CONST_INT
1541 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1542 || INTVAL (op1
) >= 0)
1543 && GET_CODE (b
) == LTU
1544 && GET_CODE (opb1
) == CONST_INT
)
1545 return INTVAL (opb1
) < 0;
1550 /* Canonicalizes COND so that
1552 (1) Ensure that operands are ordered according to
1553 swap_commutative_operands_p.
1554 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1555 for GE, GEU, and LEU. */
1558 canon_condition (rtx cond
)
1563 enum machine_mode mode
;
1565 code
= GET_CODE (cond
);
1566 op0
= XEXP (cond
, 0);
1567 op1
= XEXP (cond
, 1);
1569 if (swap_commutative_operands_p (op0
, op1
))
1571 code
= swap_condition (code
);
1577 mode
= GET_MODE (op0
);
1578 if (mode
== VOIDmode
)
1579 mode
= GET_MODE (op1
);
1580 gcc_assert (mode
!= VOIDmode
);
1582 if (GET_CODE (op1
) == CONST_INT
1583 && GET_MODE_CLASS (mode
) != MODE_CC
1584 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1586 HOST_WIDE_INT const_val
= INTVAL (op1
);
1587 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1588 unsigned HOST_WIDE_INT max_val
1589 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1594 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1595 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1598 /* When cross-compiling, const_val might be sign-extended from
1599 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1601 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1602 != (((HOST_WIDE_INT
) 1
1603 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1604 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1608 if (uconst_val
< max_val
)
1609 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1613 if (uconst_val
!= 0)
1614 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1622 if (op0
!= XEXP (cond
, 0)
1623 || op1
!= XEXP (cond
, 1)
1624 || code
!= GET_CODE (cond
)
1625 || GET_MODE (cond
) != SImode
)
1626 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1631 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1632 set of altered regs. */
1635 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1637 rtx rev
, reve
, exp
= *expr
;
1639 if (!COMPARISON_P (exp
))
1642 /* If some register gets altered later, we do not really speak about its
1643 value at the time of comparison. */
1645 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1648 rev
= reversed_condition (cond
);
1649 reve
= reversed_condition (exp
);
1651 cond
= canon_condition (cond
);
1652 exp
= canon_condition (exp
);
1654 rev
= canon_condition (rev
);
1656 reve
= canon_condition (reve
);
1658 if (rtx_equal_p (exp
, cond
))
1660 *expr
= const_true_rtx
;
1665 if (rev
&& rtx_equal_p (exp
, rev
))
1671 if (implies_p (cond
, exp
))
1673 *expr
= const_true_rtx
;
1677 if (reve
&& implies_p (cond
, reve
))
1683 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1685 if (rev
&& implies_p (exp
, rev
))
1691 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1692 if (rev
&& reve
&& implies_p (reve
, rev
))
1694 *expr
= const_true_rtx
;
1698 /* We would like to have some other tests here. TODO. */
1703 /* Use relationship between A and *B to eventually eliminate *B.
1704 OP is the operation we consider. */
1707 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1712 /* If A implies *B, we may replace *B by true. */
1713 if (implies_p (a
, *b
))
1714 *b
= const_true_rtx
;
1718 /* If *B implies A, we may replace *B by false. */
1719 if (implies_p (*b
, a
))
1728 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1729 operation we consider. */
1732 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1736 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1737 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1738 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1739 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1742 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1743 is a list, its elements are assumed to be combined using OP. */
1746 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1748 rtx head
, tail
, insn
;
1756 if (CONSTANT_P (*expr
))
1759 if (GET_CODE (*expr
) == EXPR_LIST
)
1761 head
= XEXP (*expr
, 0);
1762 tail
= XEXP (*expr
, 1);
1764 eliminate_implied_conditions (op
, &head
, tail
);
1769 neutral
= const_true_rtx
;
1774 neutral
= const0_rtx
;
1775 aggr
= const_true_rtx
;
1782 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1785 XEXP (*expr
, 0) = aggr
;
1786 XEXP (*expr
, 1) = NULL_RTX
;
1789 else if (head
== neutral
)
1792 simplify_using_initial_values (loop
, op
, expr
);
1795 simplify_using_initial_values (loop
, op
, &tail
);
1797 if (tail
&& XEXP (tail
, 0) == aggr
)
1803 XEXP (*expr
, 0) = head
;
1804 XEXP (*expr
, 1) = tail
;
1808 gcc_assert (op
== UNKNOWN
);
1810 e
= loop_preheader_edge (loop
);
1811 if (e
->src
== ENTRY_BLOCK_PTR
)
1814 altered
= ALLOC_REG_SET (®_obstack
);
1818 insn
= BB_END (e
->src
);
1819 if (any_condjump_p (insn
))
1821 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1823 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1824 cond
= reversed_condition (cond
);
1827 simplify_using_condition (cond
, expr
, altered
);
1828 if (CONSTANT_P (*expr
))
1830 FREE_REG_SET (altered
);
1836 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1841 simplify_using_assignment (insn
, expr
, altered
);
1842 if (CONSTANT_P (*expr
))
1844 FREE_REG_SET (altered
);
1847 if (for_each_rtx (expr
, altered_reg_used
, altered
))
1849 FREE_REG_SET (altered
);
1854 if (!single_pred_p (e
->src
)
1855 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
1857 e
= single_pred_edge (e
->src
);
1860 FREE_REG_SET (altered
);
1863 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1864 that IV occurs as left operands of comparison COND and its signedness
1865 is SIGNED_P to DESC. */
1868 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1869 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1871 rtx mmin
, mmax
, cond_over
, cond_under
;
1873 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1874 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1876 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1885 if (cond_under
!= const0_rtx
)
1887 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1888 if (cond_over
!= const0_rtx
)
1889 desc
->noloop_assumptions
=
1890 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1897 if (cond_over
!= const0_rtx
)
1899 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1900 if (cond_under
!= const0_rtx
)
1901 desc
->noloop_assumptions
=
1902 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1906 if (cond_over
!= const0_rtx
)
1908 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1909 if (cond_under
!= const0_rtx
)
1911 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1919 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1922 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1923 subregs of the same mode if possible (sometimes it is necessary to add
1924 some assumptions to DESC). */
1927 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1928 enum rtx_code cond
, struct niter_desc
*desc
)
1930 enum machine_mode comp_mode
;
1933 /* If the ivs behave specially in the first iteration, or are
1934 added/multiplied after extending, we ignore them. */
1935 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1937 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1940 /* If there is some extend, it must match signedness of the comparison. */
1945 if (iv0
->extend
== ZERO_EXTEND
1946 || iv1
->extend
== ZERO_EXTEND
)
1953 if (iv0
->extend
== SIGN_EXTEND
1954 || iv1
->extend
== SIGN_EXTEND
)
1960 if (iv0
->extend
!= UNKNOWN
1961 && iv1
->extend
!= UNKNOWN
1962 && iv0
->extend
!= iv1
->extend
)
1966 if (iv0
->extend
!= UNKNOWN
)
1967 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1968 if (iv1
->extend
!= UNKNOWN
)
1969 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1976 /* Values of both variables should be computed in the same mode. These
1977 might indeed be different, if we have comparison like
1979 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1981 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1982 in different modes. This does not seem impossible to handle, but
1983 it hardly ever occurs in practice.
1985 The only exception is the case when one of operands is invariant.
1986 For example pentium 3 generates comparisons like
1987 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1988 definitely do not want this prevent the optimization. */
1989 comp_mode
= iv0
->extend_mode
;
1990 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1991 comp_mode
= iv1
->extend_mode
;
1993 if (iv0
->extend_mode
!= comp_mode
)
1995 if (iv0
->mode
!= iv0
->extend_mode
1996 || iv0
->step
!= const0_rtx
)
1999 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2000 comp_mode
, iv0
->base
, iv0
->mode
);
2001 iv0
->extend_mode
= comp_mode
;
2004 if (iv1
->extend_mode
!= comp_mode
)
2006 if (iv1
->mode
!= iv1
->extend_mode
2007 || iv1
->step
!= const0_rtx
)
2010 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2011 comp_mode
, iv1
->base
, iv1
->mode
);
2012 iv1
->extend_mode
= comp_mode
;
2015 /* Check that both ivs belong to a range of a single mode. If one of the
2016 operands is an invariant, we may need to shorten it into the common
2018 if (iv0
->mode
== iv0
->extend_mode
2019 && iv0
->step
== const0_rtx
2020 && iv0
->mode
!= iv1
->mode
)
2021 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2023 if (iv1
->mode
== iv1
->extend_mode
2024 && iv1
->step
== const0_rtx
2025 && iv0
->mode
!= iv1
->mode
)
2026 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2028 if (iv0
->mode
!= iv1
->mode
)
2031 desc
->mode
= iv0
->mode
;
2032 desc
->signed_p
= signed_p
;
2037 /* Tries to estimate the maximum number of iterations. */
2039 static unsigned HOST_WIDEST_INT
2040 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
)
2042 rtx niter
= desc
->niter_expr
;
2043 rtx mmin
, mmax
, cmp
;
2044 unsigned HOST_WIDEST_INT nmax
, inc
;
2046 if (GET_CODE (niter
) == AND
2047 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
2049 nmax
= INTVAL (XEXP (niter
, 0));
2050 if (!(nmax
& (nmax
+ 1)))
2052 desc
->niter_max
= nmax
;
2057 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2058 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2060 if (GET_CODE (niter
) == UDIV
)
2062 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
2064 desc
->niter_max
= nmax
;
2067 inc
= INTVAL (XEXP (niter
, 1));
2068 niter
= XEXP (niter
, 0);
2073 /* We could use a binary search here, but for now improving the upper
2074 bound by just one eliminates one important corner case. */
2075 cmp
= gen_rtx_fmt_ee (desc
->signed_p
? LT
: LTU
, VOIDmode
, niter
, mmax
);
2076 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2077 if (cmp
== const_true_rtx
)
2082 fprintf (dump_file
, ";; improved upper bound by one.\n");
2084 desc
->niter_max
= nmax
/ inc
;
2088 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2089 the result into DESC. Very similar to determine_number_of_iterations
2090 (basically its rtl version), complicated by things like subregs. */
2093 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2094 struct niter_desc
*desc
)
2096 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2097 struct rtx_iv iv0
, iv1
, tmp_iv
;
2098 rtx assumption
, may_not_xform
;
2100 enum machine_mode mode
, comp_mode
;
2101 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2102 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2103 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2104 int was_sharp
= false;
2108 /* The meaning of these assumptions is this:
2110 then the rest of information does not have to be valid
2111 if noloop_assumptions then the loop does not roll
2112 if infinite then this exit is never used */
2114 desc
->assumptions
= NULL_RTX
;
2115 desc
->noloop_assumptions
= NULL_RTX
;
2116 desc
->infinite
= NULL_RTX
;
2117 desc
->simple_p
= true;
2119 desc
->const_iter
= false;
2120 desc
->niter_expr
= NULL_RTX
;
2121 desc
->niter_max
= 0;
2123 cond
= GET_CODE (condition
);
2124 gcc_assert (COMPARISON_P (condition
));
2126 mode
= GET_MODE (XEXP (condition
, 0));
2127 if (mode
== VOIDmode
)
2128 mode
= GET_MODE (XEXP (condition
, 1));
2129 /* The constant comparisons should be folded. */
2130 gcc_assert (mode
!= VOIDmode
);
2132 /* We only handle integers or pointers. */
2133 if (GET_MODE_CLASS (mode
) != MODE_INT
2134 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2137 op0
= XEXP (condition
, 0);
2138 if (!iv_analyze (insn
, op0
, &iv0
))
2140 if (iv0
.extend_mode
== VOIDmode
)
2141 iv0
.mode
= iv0
.extend_mode
= mode
;
2143 op1
= XEXP (condition
, 1);
2144 if (!iv_analyze (insn
, op1
, &iv1
))
2146 if (iv1
.extend_mode
== VOIDmode
)
2147 iv1
.mode
= iv1
.extend_mode
= mode
;
2149 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2150 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2153 /* Check condition and normalize it. */
2161 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2162 cond
= swap_condition (cond
);
2174 /* Handle extends. This is relatively nontrivial, so we only try in some
2175 easy cases, when we can canonicalize the ivs (possibly by adding some
2176 assumptions) to shape subreg (base + i * step). This function also fills
2177 in desc->mode and desc->signed_p. */
2179 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2182 comp_mode
= iv0
.extend_mode
;
2184 size
= GET_MODE_BITSIZE (mode
);
2185 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2186 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2187 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2189 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2192 /* We can take care of the case of two induction variables chasing each other
2193 if the test is NE. I have never seen a loop using it, but still it is
2195 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2200 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2201 iv1
.step
= const0_rtx
;
2204 /* This is either infinite loop or the one that ends immediately, depending
2205 on initial values. Unswitching should remove this kind of conditions. */
2206 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2211 if (iv0
.step
== const0_rtx
)
2212 step_val
= -INTVAL (iv1
.step
);
2214 step_val
= INTVAL (iv0
.step
);
2216 /* Ignore loops of while (i-- < 10) type. */
2220 step_is_pow2
= !(step_val
& (step_val
- 1));
2224 /* We do not care about whether the step is power of two in this
2226 step_is_pow2
= false;
2230 /* Some more condition normalization. We must record some assumptions
2231 due to overflows. */
2236 /* We want to take care only of non-sharp relationals; this is easy,
2237 as in cases the overflow would make the transformation unsafe
2238 the loop does not roll. Seemingly it would make more sense to want
2239 to take care of sharp relationals instead, as NE is more similar to
2240 them, but the problem is that here the transformation would be more
2241 difficult due to possibly infinite loops. */
2242 if (iv0
.step
== const0_rtx
)
2244 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2245 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2247 if (assumption
== const_true_rtx
)
2248 goto zero_iter_simplify
;
2249 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2250 iv0
.base
, const1_rtx
);
2254 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2255 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2257 if (assumption
== const_true_rtx
)
2258 goto zero_iter_simplify
;
2259 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2260 iv1
.base
, constm1_rtx
);
2263 if (assumption
!= const0_rtx
)
2264 desc
->noloop_assumptions
=
2265 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2266 cond
= (cond
== LT
) ? LE
: LEU
;
2268 /* It will be useful to be able to tell the difference once more in
2269 LE -> NE reduction. */
2275 /* Take care of trivially infinite loops. */
2278 if (iv0
.step
== const0_rtx
)
2280 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2281 if (rtx_equal_p (tmp
, mode_mmin
))
2284 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2285 /* Fill in the remaining fields somehow. */
2286 goto zero_iter_simplify
;
2291 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2292 if (rtx_equal_p (tmp
, mode_mmax
))
2295 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2296 /* Fill in the remaining fields somehow. */
2297 goto zero_iter_simplify
;
2302 /* If we can we want to take care of NE conditions instead of size
2303 comparisons, as they are much more friendly (most importantly
2304 this takes care of special handling of loops with step 1). We can
2305 do it if we first check that upper bound is greater or equal to
2306 lower bound, their difference is constant c modulo step and that
2307 there is not an overflow. */
2310 if (iv0
.step
== const0_rtx
)
2311 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2314 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2315 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2316 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2317 may_xform
= const0_rtx
;
2318 may_not_xform
= const_true_rtx
;
2320 if (GET_CODE (delta
) == CONST_INT
)
2322 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2324 /* A special case. We have transformed condition of type
2325 for (i = 0; i < 4; i += 4)
2327 for (i = 0; i <= 3; i += 4)
2328 obviously if the test for overflow during that transformation
2329 passed, we cannot overflow here. Most importantly any
2330 loop with sharp end condition and step 1 falls into this
2331 category, so handling this case specially is definitely
2332 worth the troubles. */
2333 may_xform
= const_true_rtx
;
2335 else if (iv0
.step
== const0_rtx
)
2337 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2338 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2339 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2340 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2341 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2343 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2349 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2350 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2351 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2352 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2353 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2355 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2361 if (may_xform
!= const0_rtx
)
2363 /* We perform the transformation always provided that it is not
2364 completely senseless. This is OK, as we would need this assumption
2365 to determine the number of iterations anyway. */
2366 if (may_xform
!= const_true_rtx
)
2368 /* If the step is a power of two and the final value we have
2369 computed overflows, the cycle is infinite. Otherwise it
2370 is nontrivial to compute the number of iterations. */
2372 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2375 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2379 /* We are going to lose some information about upper bound on
2380 number of iterations in this step, so record the information
2382 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2383 if (GET_CODE (iv1
.base
) == CONST_INT
)
2384 up
= INTVAL (iv1
.base
);
2386 up
= INTVAL (mode_mmax
) - inc
;
2387 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2390 desc
->niter_max
= (up
- down
) / inc
+ 1;
2392 if (iv0
.step
== const0_rtx
)
2394 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2395 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2399 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2400 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2403 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2404 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2405 assumption
= simplify_gen_relational (reverse_condition (cond
),
2406 SImode
, mode
, tmp0
, tmp1
);
2407 if (assumption
== const_true_rtx
)
2408 goto zero_iter_simplify
;
2409 else if (assumption
!= const0_rtx
)
2410 desc
->noloop_assumptions
=
2411 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2416 /* Count the number of iterations. */
2419 /* Everything we do here is just arithmetics modulo size of mode. This
2420 makes us able to do more involved computations of number of iterations
2421 than in other cases. First transform the condition into shape
2422 s * i <> c, with s positive. */
2423 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2424 iv0
.base
= const0_rtx
;
2425 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2426 iv1
.step
= const0_rtx
;
2427 if (INTVAL (iv0
.step
) < 0)
2429 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2430 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2432 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2434 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2435 is infinite. Otherwise, the number of iterations is
2436 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2437 s
= INTVAL (iv0
.step
); d
= 1;
2444 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2446 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2447 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2448 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2449 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2451 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2452 inv
= inverse (s
, size
);
2453 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2454 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2458 if (iv1
.step
== const0_rtx
)
2459 /* Condition in shape a + s * i <= b
2460 We must know that b + s does not overflow and a <= b + s and then we
2461 can compute number of iterations as (b + s - a) / s. (It might
2462 seem that we in fact could be more clever about testing the b + s
2463 overflow condition using some information about b - a mod s,
2464 but it was already taken into account during LE -> NE transform). */
2467 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2468 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2470 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2471 lowpart_subreg (mode
, step
,
2477 /* If s is power of 2, we know that the loop is infinite if
2478 a % s <= b % s and b + s overflows. */
2479 assumption
= simplify_gen_relational (reverse_condition (cond
),
2483 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2484 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2485 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2486 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2488 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2492 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2495 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2498 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2499 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2500 assumption
= simplify_gen_relational (reverse_condition (cond
),
2501 SImode
, mode
, tmp0
, tmp
);
2503 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2504 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2508 /* Condition in shape a <= b - s * i
2509 We must know that a - s does not overflow and a - s <= b and then
2510 we can again compute number of iterations as (b - (a - s)) / s. */
2511 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2512 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2513 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2515 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2516 lowpart_subreg (mode
, step
, comp_mode
));
2521 /* If s is power of 2, we know that the loop is infinite if
2522 a % s <= b % s and a - s overflows. */
2523 assumption
= simplify_gen_relational (reverse_condition (cond
),
2527 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2528 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2529 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2530 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2532 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2536 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2539 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2542 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2543 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2544 assumption
= simplify_gen_relational (reverse_condition (cond
),
2547 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2548 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2550 if (assumption
== const_true_rtx
)
2551 goto zero_iter_simplify
;
2552 else if (assumption
!= const0_rtx
)
2553 desc
->noloop_assumptions
=
2554 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2555 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2556 desc
->niter_expr
= delta
;
2559 old_niter
= desc
->niter_expr
;
2561 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2562 if (desc
->assumptions
2563 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2565 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2566 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2567 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2569 /* Rerun the simplification. Consider code (created by copying loop headers)
2581 The first pass determines that i = 0, the second pass uses it to eliminate
2582 noloop assumption. */
2584 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2585 if (desc
->assumptions
2586 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2588 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2589 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2590 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2592 if (desc
->noloop_assumptions
2593 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2596 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2598 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2600 desc
->const_iter
= true;
2601 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2605 if (!desc
->niter_max
)
2606 desc
->niter_max
= determine_max_iter (loop
, desc
);
2608 /* simplify_using_initial_values does a copy propagation on the registers
2609 in the expression for the number of iterations. This prolongs life
2610 ranges of registers and increases register pressure, and usually
2611 brings no gain (and if it happens to do, the cse pass will take care
2612 of it anyway). So prevent this behavior, unless it enabled us to
2613 derive that the number of iterations is a constant. */
2614 desc
->niter_expr
= old_niter
;
2620 /* Simplify the assumptions. */
2621 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2622 if (desc
->assumptions
2623 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2625 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2629 desc
->const_iter
= true;
2631 desc
->niter_max
= 0;
2632 desc
->noloop_assumptions
= NULL_RTX
;
2633 desc
->niter_expr
= const0_rtx
;
2637 desc
->simple_p
= false;
2641 /* Checks whether E is a simple exit from LOOP and stores its description
2645 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2647 basic_block exit_bb
;
2652 desc
->simple_p
= false;
2654 /* It must belong directly to the loop. */
2655 if (exit_bb
->loop_father
!= loop
)
2658 /* It must be tested (at least) once during any iteration. */
2659 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2662 /* It must end in a simple conditional jump. */
2663 if (!any_condjump_p (BB_END (exit_bb
)))
2666 ein
= EDGE_SUCC (exit_bb
, 0);
2668 ein
= EDGE_SUCC (exit_bb
, 1);
2671 desc
->in_edge
= ein
;
2673 /* Test whether the condition is suitable. */
2674 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2677 if (ein
->flags
& EDGE_FALLTHRU
)
2679 condition
= reversed_condition (condition
);
2684 /* Check that we are able to determine number of iterations and fill
2685 in information about it. */
2686 iv_number_of_iterations (loop
, at
, condition
, desc
);
2689 /* Finds a simple exit of LOOP and stores its description into DESC. */
2692 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2697 struct niter_desc act
;
2701 desc
->simple_p
= false;
2702 body
= get_loop_body (loop
);
2704 for (i
= 0; i
< loop
->num_nodes
; i
++)
2706 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2708 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2711 check_simple_exit (loop
, e
, &act
);
2719 /* Prefer constant iterations; the less the better. */
2721 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2724 /* Also if the actual exit may be infinite, while the old one
2725 not, prefer the old one. */
2726 if (act
.infinite
&& !desc
->infinite
)
2738 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2739 fprintf (dump_file
, " simple exit %d -> %d\n",
2740 desc
->out_edge
->src
->index
,
2741 desc
->out_edge
->dest
->index
);
2742 if (desc
->assumptions
)
2744 fprintf (dump_file
, " assumptions: ");
2745 print_rtl (dump_file
, desc
->assumptions
);
2746 fprintf (dump_file
, "\n");
2748 if (desc
->noloop_assumptions
)
2750 fprintf (dump_file
, " does not roll if: ");
2751 print_rtl (dump_file
, desc
->noloop_assumptions
);
2752 fprintf (dump_file
, "\n");
2756 fprintf (dump_file
, " infinite if: ");
2757 print_rtl (dump_file
, desc
->infinite
);
2758 fprintf (dump_file
, "\n");
2761 fprintf (dump_file
, " number of iterations: ");
2762 print_rtl (dump_file
, desc
->niter_expr
);
2763 fprintf (dump_file
, "\n");
2765 fprintf (dump_file
, " upper bound: ");
2766 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2767 fprintf (dump_file
, "\n");
2770 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2776 /* Creates a simple loop description of LOOP if it was not computed
2780 get_simple_loop_desc (struct loop
*loop
)
2782 struct niter_desc
*desc
= simple_loop_desc (loop
);
2787 desc
= XNEW (struct niter_desc
);
2788 iv_analysis_loop_init (loop
);
2789 find_simple_exit (loop
, desc
);
2792 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
2794 const char *wording
;
2796 /* Assume that no overflow happens and that the loop is finite.
2797 We already warned at the tree level if we ran optimizations there. */
2798 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
2803 flag_unsafe_loop_optimizations
2804 ? N_("assuming that the loop is not infinite")
2805 : N_("cannot optimize possibly infinite loops");
2806 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2809 if (desc
->assumptions
)
2812 flag_unsafe_loop_optimizations
2813 ? N_("assuming that the loop counter does not overflow")
2814 : N_("cannot optimize loop, the loop counter may overflow");
2815 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2820 if (flag_unsafe_loop_optimizations
)
2822 desc
->assumptions
= NULL_RTX
;
2823 desc
->infinite
= NULL_RTX
;
2830 /* Releases simple loop description for LOOP. */
2833 free_simple_loop_desc (struct loop
*loop
)
2835 struct niter_desc
*desc
= simple_loop_desc (loop
);