1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This is a simple analysis of induction variables of the loop. The major use
22 is for determining the number of iterations of a loop for loop unrolling,
23 doloop optimization and branch prediction. The iv information is computed
26 Induction variables are analyzed by walking the use-def chains. When
27 a basic induction variable (biv) is found, it is cached in the bivs
28 hash table. When register is proved to be a biv, its description
29 is stored to DF_REF_DATA of the def reference.
31 The analysis works always with one loop -- you must call
32 iv_analysis_loop_init (loop) for it. All the other functions then work with
33 this loop. When you need to work with another loop, just call
34 iv_analysis_loop_init for it. When you no longer need iv analysis, call
35 iv_analysis_done () to clean up the memory.
37 The available functions are:
39 iv_analyze (insn, reg, iv): Stores the description of the induction variable
40 corresponding to the use of register REG in INSN to IV. Returns true if
41 REG is an induction variable in INSN. false otherwise.
42 If use of REG is not found in INSN, following insns are scanned (so that
43 we may call this function on insn returned by get_condition).
44 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
45 corresponding to DEF, which is a register defined in INSN.
46 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
47 corresponding to expression EXPR evaluated at INSN. All registers used bu
48 EXPR must also be used in INSN.
53 #include "coretypes.h"
56 #include "hard-reg-set.h"
58 #include "basic-block.h"
63 #include "diagnostic-core.h"
67 /* Possible return values of iv_get_reaching_def. */
71 /* More than one reaching def, or reaching def that does not
75 /* The use is trivial invariant of the loop, i.e. is not changed
79 /* The use is reached by initial value and a value from the
80 previous iteration. */
83 /* The use has single dominating def. */
87 /* Information about a biv. */
91 unsigned regno
; /* The register of the biv. */
92 struct rtx_iv iv
; /* Value of the biv. */
95 static bool clean_slate
= true;
97 static unsigned int iv_ref_table_size
= 0;
99 /* Table of rtx_ivs indexed by the df_ref uid field. */
100 static struct rtx_iv
** iv_ref_table
;
102 /* Induction variable stored at the reference. */
103 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
104 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
106 /* The current loop. */
108 static struct loop
*current_loop
;
110 /* Bivs of the current loop. */
114 static bool iv_analyze_op (rtx
, rtx
, struct rtx_iv
*);
116 /* Dumps information about IV to FILE. */
118 extern void dump_iv_info (FILE *, struct rtx_iv
*);
120 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
124 fprintf (file
, "not simple");
128 if (iv
->step
== const0_rtx
129 && !iv
->first_special
)
130 fprintf (file
, "invariant ");
132 print_rtl (file
, iv
->base
);
133 if (iv
->step
!= const0_rtx
)
135 fprintf (file
, " + ");
136 print_rtl (file
, iv
->step
);
137 fprintf (file
, " * iteration");
139 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
141 if (iv
->mode
!= iv
->extend_mode
)
142 fprintf (file
, " %s to %s",
143 rtx_name
[iv
->extend
],
144 GET_MODE_NAME (iv
->extend_mode
));
146 if (iv
->mult
!= const1_rtx
)
148 fprintf (file
, " * ");
149 print_rtl (file
, iv
->mult
);
151 if (iv
->delta
!= const0_rtx
)
153 fprintf (file
, " + ");
154 print_rtl (file
, iv
->delta
);
156 if (iv
->first_special
)
157 fprintf (file
, " (first special)");
160 /* Generates a subreg to get the least significant part of EXPR (in mode
161 INNER_MODE) to OUTER_MODE. */
164 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
165 enum machine_mode inner_mode
)
167 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
168 subreg_lowpart_offset (outer_mode
, inner_mode
));
172 check_iv_ref_table_size (void)
174 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE())
176 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
177 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
178 memset (&iv_ref_table
[iv_ref_table_size
], 0,
179 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
180 iv_ref_table_size
= new_size
;
185 /* Checks whether REG is a well-behaved register. */
188 simple_reg_p (rtx reg
)
192 if (GET_CODE (reg
) == SUBREG
)
194 if (!subreg_lowpart_p (reg
))
196 reg
= SUBREG_REG (reg
);
203 if (HARD_REGISTER_NUM_P (r
))
206 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
212 /* Clears the information about ivs stored in df. */
217 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
220 check_iv_ref_table_size ();
221 for (i
= 0; i
< n_defs
; i
++)
223 iv
= iv_ref_table
[i
];
227 iv_ref_table
[i
] = NULL
;
234 /* Returns hash value for biv B. */
237 biv_hash (const void *b
)
239 return ((const struct biv_entry
*) b
)->regno
;
242 /* Compares biv B and register R. */
245 biv_eq (const void *b
, const void *r
)
247 return ((const struct biv_entry
*) b
)->regno
== REGNO ((const_rtx
) r
);
250 /* Prepare the data for an induction variable analysis of a LOOP. */
253 iv_analysis_loop_init (struct loop
*loop
)
255 basic_block
*body
= get_loop_body_in_dom_order (loop
), bb
;
256 bitmap blocks
= BITMAP_ALLOC (NULL
);
261 /* Clear the information from the analysis of the previous loop. */
264 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
265 bivs
= htab_create (10, biv_hash
, biv_eq
, free
);
271 for (i
= 0; i
< loop
->num_nodes
; i
++)
274 bitmap_set_bit (blocks
, bb
->index
);
276 /* Get rid of the ud chains before processing the rescans. Then add
278 df_remove_problem (df_chain
);
279 df_process_deferred_rescans ();
280 df_chain_add_problem (DF_UD_CHAIN
);
281 df_note_add_problem ();
282 df_set_blocks (blocks
);
285 df_dump_region (dump_file
);
287 check_iv_ref_table_size ();
288 BITMAP_FREE (blocks
);
292 /* Finds the definition of REG that dominates loop latch and stores
293 it to DEF. Returns false if there is not a single definition
294 dominating the latch. If REG has no definition in loop, DEF
295 is set to NULL and true is returned. */
298 latch_dominating_def (rtx reg
, df_ref
*def
)
300 df_ref single_rd
= NULL
, adef
;
301 unsigned regno
= REGNO (reg
);
302 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
304 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
306 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
307 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
310 /* More than one reaching definition. */
314 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
324 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
326 static enum iv_grd_result
327 iv_get_reaching_def (rtx insn
, rtx reg
, df_ref
*def
)
330 basic_block def_bb
, use_bb
;
335 if (!simple_reg_p (reg
))
337 if (GET_CODE (reg
) == SUBREG
)
338 reg
= SUBREG_REG (reg
);
339 gcc_assert (REG_P (reg
));
341 use
= df_find_use (insn
, reg
);
342 gcc_assert (use
!= NULL
);
344 if (!DF_REF_CHAIN (use
))
345 return GRD_INVARIANT
;
347 /* More than one reaching def. */
348 if (DF_REF_CHAIN (use
)->next
)
351 adef
= DF_REF_CHAIN (use
)->ref
;
353 /* We do not handle setting only part of the register. */
354 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
357 def_insn
= DF_REF_INSN (adef
);
358 def_bb
= DF_REF_BB (adef
);
359 use_bb
= BLOCK_FOR_INSN (insn
);
361 if (use_bb
== def_bb
)
362 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
364 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
369 return GRD_SINGLE_DOM
;
372 /* The definition does not dominate the use. This is still OK if
373 this may be a use of a biv, i.e. if the def_bb dominates loop
375 if (just_once_each_iteration_p (current_loop
, def_bb
))
376 return GRD_MAYBE_BIV
;
381 /* Sets IV to invariant CST in MODE. Always returns true (just for
382 consistency with other iv manipulation functions that may fail). */
385 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
387 if (mode
== VOIDmode
)
388 mode
= GET_MODE (cst
);
392 iv
->step
= const0_rtx
;
393 iv
->first_special
= false;
394 iv
->extend
= UNKNOWN
;
395 iv
->extend_mode
= iv
->mode
;
396 iv
->delta
= const0_rtx
;
397 iv
->mult
= const1_rtx
;
402 /* Evaluates application of subreg to MODE on IV. */
405 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
407 /* If iv is invariant, just calculate the new value. */
408 if (iv
->step
== const0_rtx
409 && !iv
->first_special
)
411 rtx val
= get_iv_value (iv
, const0_rtx
);
412 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
415 iv
->extend
= UNKNOWN
;
416 iv
->mode
= iv
->extend_mode
= mode
;
417 iv
->delta
= const0_rtx
;
418 iv
->mult
= const1_rtx
;
422 if (iv
->extend_mode
== mode
)
425 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
428 iv
->extend
= UNKNOWN
;
431 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
432 simplify_gen_binary (MULT
, iv
->extend_mode
,
433 iv
->base
, iv
->mult
));
434 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
435 iv
->mult
= const1_rtx
;
436 iv
->delta
= const0_rtx
;
437 iv
->first_special
= false;
442 /* Evaluates application of EXTEND to MODE on IV. */
445 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
447 /* If iv is invariant, just calculate the new value. */
448 if (iv
->step
== const0_rtx
449 && !iv
->first_special
)
451 rtx val
= get_iv_value (iv
, const0_rtx
);
452 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
455 iv
->extend
= UNKNOWN
;
456 iv
->mode
= iv
->extend_mode
= mode
;
457 iv
->delta
= const0_rtx
;
458 iv
->mult
= const1_rtx
;
462 if (mode
!= iv
->extend_mode
)
465 if (iv
->extend
!= UNKNOWN
466 && iv
->extend
!= extend
)
474 /* Evaluates negation of IV. */
477 iv_neg (struct rtx_iv
*iv
)
479 if (iv
->extend
== UNKNOWN
)
481 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
482 iv
->base
, iv
->extend_mode
);
483 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
484 iv
->step
, iv
->extend_mode
);
488 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
489 iv
->delta
, iv
->extend_mode
);
490 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
491 iv
->mult
, iv
->extend_mode
);
497 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
500 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
502 enum machine_mode mode
;
505 /* Extend the constant to extend_mode of the other operand if necessary. */
506 if (iv0
->extend
== UNKNOWN
507 && iv0
->mode
== iv0
->extend_mode
508 && iv0
->step
== const0_rtx
509 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
511 iv0
->extend_mode
= iv1
->extend_mode
;
512 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
513 iv0
->base
, iv0
->mode
);
515 if (iv1
->extend
== UNKNOWN
516 && iv1
->mode
== iv1
->extend_mode
517 && iv1
->step
== const0_rtx
518 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
520 iv1
->extend_mode
= iv0
->extend_mode
;
521 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
522 iv1
->base
, iv1
->mode
);
525 mode
= iv0
->extend_mode
;
526 if (mode
!= iv1
->extend_mode
)
529 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
531 if (iv0
->mode
!= iv1
->mode
)
534 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
535 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
540 /* Handle addition of constant. */
541 if (iv1
->extend
== UNKNOWN
543 && iv1
->step
== const0_rtx
)
545 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
549 if (iv0
->extend
== UNKNOWN
551 && iv0
->step
== const0_rtx
)
559 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
566 /* Evaluates multiplication of IV by constant CST. */
569 iv_mult (struct rtx_iv
*iv
, rtx mby
)
571 enum machine_mode mode
= iv
->extend_mode
;
573 if (GET_MODE (mby
) != VOIDmode
574 && GET_MODE (mby
) != mode
)
577 if (iv
->extend
== UNKNOWN
)
579 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
580 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
584 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
585 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
591 /* Evaluates shift of IV by constant CST. */
594 iv_shift (struct rtx_iv
*iv
, rtx mby
)
596 enum machine_mode mode
= iv
->extend_mode
;
598 if (GET_MODE (mby
) != VOIDmode
599 && GET_MODE (mby
) != mode
)
602 if (iv
->extend
== UNKNOWN
)
604 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
605 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
609 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
610 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
616 /* The recursive part of get_biv_step. Gets the value of the single value
617 defined by DEF wrto initial value of REG inside loop, in shape described
621 get_biv_step_1 (df_ref def
, rtx reg
,
622 rtx
*inner_step
, enum machine_mode
*inner_mode
,
623 enum rtx_code
*extend
, enum machine_mode outer_mode
,
626 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
627 rtx next
, nextr
, tmp
;
629 rtx insn
= DF_REF_INSN (def
);
631 enum iv_grd_result res
;
633 set
= single_set (insn
);
637 rhs
= find_reg_equal_equiv_note (insn
);
643 code
= GET_CODE (rhs
);
656 if (code
== PLUS
&& CONSTANT_P (op0
))
658 tmp
= op0
; op0
= op1
; op1
= tmp
;
661 if (!simple_reg_p (op0
)
662 || !CONSTANT_P (op1
))
665 if (GET_MODE (rhs
) != outer_mode
)
667 /* ppc64 uses expressions like
669 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
671 this is equivalent to
673 (set x':DI (plus:DI y:DI 1))
674 (set x:SI (subreg:SI (x':DI)). */
675 if (GET_CODE (op0
) != SUBREG
)
677 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
686 if (GET_MODE (rhs
) != outer_mode
)
690 if (!simple_reg_p (op0
))
700 if (GET_CODE (next
) == SUBREG
)
702 if (!subreg_lowpart_p (next
))
705 nextr
= SUBREG_REG (next
);
706 if (GET_MODE (nextr
) != outer_mode
)
712 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
714 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
717 if (res
== GRD_MAYBE_BIV
)
719 if (!rtx_equal_p (nextr
, reg
))
722 *inner_step
= const0_rtx
;
724 *inner_mode
= outer_mode
;
725 *outer_step
= const0_rtx
;
727 else if (!get_biv_step_1 (next_def
, reg
,
728 inner_step
, inner_mode
, extend
, outer_mode
,
732 if (GET_CODE (next
) == SUBREG
)
734 enum machine_mode amode
= GET_MODE (next
);
736 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
740 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
741 *inner_step
, *outer_step
);
742 *outer_step
= const0_rtx
;
754 if (*inner_mode
== outer_mode
755 /* See comment in previous switch. */
756 || GET_MODE (rhs
) != outer_mode
)
757 *inner_step
= simplify_gen_binary (code
, outer_mode
,
760 *outer_step
= simplify_gen_binary (code
, outer_mode
,
766 gcc_assert (GET_MODE (op0
) == *inner_mode
767 && *extend
== UNKNOWN
768 && *outer_step
== const0_rtx
);
780 /* Gets the operation on register REG inside loop, in shape
782 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
784 If the operation cannot be described in this shape, return false.
785 LAST_DEF is the definition of REG that dominates loop latch. */
788 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
789 enum machine_mode
*inner_mode
, enum rtx_code
*extend
,
790 enum machine_mode
*outer_mode
, rtx
*outer_step
)
792 *outer_mode
= GET_MODE (reg
);
794 if (!get_biv_step_1 (last_def
, reg
,
795 inner_step
, inner_mode
, extend
, *outer_mode
,
799 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= UNKNOWN
));
800 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
805 /* Records information that DEF is induction variable IV. */
808 record_iv (df_ref def
, struct rtx_iv
*iv
)
810 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
813 check_iv_ref_table_size ();
814 DF_REF_IV_SET (def
, recorded_iv
);
817 /* If DEF was already analyzed for bivness, store the description of the biv to
818 IV and return true. Otherwise return false. */
821 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
823 struct biv_entry
*biv
=
824 (struct biv_entry
*) htab_find_with_hash (bivs
, def
, REGNO (def
));
834 record_biv (rtx def
, struct rtx_iv
*iv
)
836 struct biv_entry
*biv
= XNEW (struct biv_entry
);
837 void **slot
= htab_find_slot_with_hash (bivs
, def
, REGNO (def
), INSERT
);
839 biv
->regno
= REGNO (def
);
845 /* Determines whether DEF is a biv and if so, stores its description
849 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
851 rtx inner_step
, outer_step
;
852 enum machine_mode inner_mode
, outer_mode
;
853 enum rtx_code extend
;
858 fprintf (dump_file
, "Analyzing ");
859 print_rtl (dump_file
, def
);
860 fprintf (dump_file
, " for bivness.\n");
865 if (!CONSTANT_P (def
))
868 return iv_constant (iv
, def
, VOIDmode
);
871 if (!latch_dominating_def (def
, &last_def
))
874 fprintf (dump_file
, " not simple.\n");
879 return iv_constant (iv
, def
, VOIDmode
);
881 if (analyzed_for_bivness_p (def
, iv
))
884 fprintf (dump_file
, " already analysed.\n");
885 return iv
->base
!= NULL_RTX
;
888 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
889 &outer_mode
, &outer_step
))
895 /* Loop transforms base to es (base + inner_step) + outer_step,
896 where es means extend of subreg between inner_mode and outer_mode.
897 The corresponding induction variable is
899 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
901 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
902 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
903 iv
->mode
= inner_mode
;
904 iv
->extend_mode
= outer_mode
;
906 iv
->mult
= const1_rtx
;
907 iv
->delta
= outer_step
;
908 iv
->first_special
= inner_mode
!= outer_mode
;
913 fprintf (dump_file
, " ");
914 dump_iv_info (dump_file
, iv
);
915 fprintf (dump_file
, "\n");
918 record_biv (def
, iv
);
919 return iv
->base
!= NULL_RTX
;
922 /* Analyzes expression RHS used at INSN and stores the result to *IV.
923 The mode of the induction variable is MODE. */
926 iv_analyze_expr (rtx insn
, rtx rhs
, enum machine_mode mode
, struct rtx_iv
*iv
)
928 rtx mby
= NULL_RTX
, tmp
;
929 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
930 struct rtx_iv iv0
, iv1
;
931 enum rtx_code code
= GET_CODE (rhs
);
932 enum machine_mode omode
= mode
;
938 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
944 if (!iv_analyze_op (insn
, rhs
, iv
))
947 if (iv
->mode
== VOIDmode
)
950 iv
->extend_mode
= mode
;
966 omode
= GET_MODE (op0
);
978 if (!CONSTANT_P (mby
))
984 if (!CONSTANT_P (mby
))
991 if (!CONSTANT_P (mby
))
1000 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1004 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1011 if (!iv_extend (&iv0
, code
, mode
))
1022 if (!iv_add (&iv0
, &iv1
, code
))
1027 if (!iv_mult (&iv0
, mby
))
1032 if (!iv_shift (&iv0
, mby
))
1041 return iv
->base
!= NULL_RTX
;
1044 /* Analyzes iv DEF and stores the result to *IV. */
1047 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1049 rtx insn
= DF_REF_INSN (def
);
1050 rtx reg
= DF_REF_REG (def
);
1055 fprintf (dump_file
, "Analyzing def of ");
1056 print_rtl (dump_file
, reg
);
1057 fprintf (dump_file
, " in insn ");
1058 print_rtl_single (dump_file
, insn
);
1061 check_iv_ref_table_size ();
1062 if (DF_REF_IV (def
))
1065 fprintf (dump_file
, " already analysed.\n");
1066 *iv
= *DF_REF_IV (def
);
1067 return iv
->base
!= NULL_RTX
;
1070 iv
->mode
= VOIDmode
;
1071 iv
->base
= NULL_RTX
;
1072 iv
->step
= NULL_RTX
;
1077 set
= single_set (insn
);
1081 if (!REG_P (SET_DEST (set
)))
1084 gcc_assert (SET_DEST (set
) == reg
);
1085 rhs
= find_reg_equal_equiv_note (insn
);
1087 rhs
= XEXP (rhs
, 0);
1089 rhs
= SET_SRC (set
);
1091 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1092 record_iv (def
, iv
);
1096 print_rtl (dump_file
, reg
);
1097 fprintf (dump_file
, " in insn ");
1098 print_rtl_single (dump_file
, insn
);
1099 fprintf (dump_file
, " is ");
1100 dump_iv_info (dump_file
, iv
);
1101 fprintf (dump_file
, "\n");
1104 return iv
->base
!= NULL_RTX
;
1107 /* Analyzes operand OP of INSN and stores the result to *IV. */
1110 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
1113 enum iv_grd_result res
;
1117 fprintf (dump_file
, "Analyzing operand ");
1118 print_rtl (dump_file
, op
);
1119 fprintf (dump_file
, " of insn ");
1120 print_rtl_single (dump_file
, insn
);
1123 if (function_invariant_p (op
))
1124 res
= GRD_INVARIANT
;
1125 else if (GET_CODE (op
) == SUBREG
)
1127 if (!subreg_lowpart_p (op
))
1130 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1133 return iv_subreg (iv
, GET_MODE (op
));
1137 res
= iv_get_reaching_def (insn
, op
, &def
);
1138 if (res
== GRD_INVALID
)
1141 fprintf (dump_file
, " not simple.\n");
1146 if (res
== GRD_INVARIANT
)
1148 iv_constant (iv
, op
, VOIDmode
);
1152 fprintf (dump_file
, " ");
1153 dump_iv_info (dump_file
, iv
);
1154 fprintf (dump_file
, "\n");
1159 if (res
== GRD_MAYBE_BIV
)
1160 return iv_analyze_biv (op
, iv
);
1162 return iv_analyze_def (def
, iv
);
1165 /* Analyzes value VAL at INSN and stores the result to *IV. */
1168 iv_analyze (rtx insn
, rtx val
, struct rtx_iv
*iv
)
1172 /* We must find the insn in that val is used, so that we get to UD chains.
1173 Since the function is sometimes called on result of get_condition,
1174 this does not necessarily have to be directly INSN; scan also the
1176 if (simple_reg_p (val
))
1178 if (GET_CODE (val
) == SUBREG
)
1179 reg
= SUBREG_REG (val
);
1183 while (!df_find_use (insn
, reg
))
1184 insn
= NEXT_INSN (insn
);
1187 return iv_analyze_op (insn
, val
, iv
);
1190 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1193 iv_analyze_result (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1197 adef
= df_find_def (insn
, def
);
1201 return iv_analyze_def (adef
, iv
);
1204 /* Checks whether definition of register REG in INSN is a basic induction
1205 variable. IV analysis must have been initialized (via a call to
1206 iv_analysis_loop_init) for this function to produce a result. */
1209 biv_p (rtx insn
, rtx reg
)
1212 df_ref def
, last_def
;
1214 if (!simple_reg_p (reg
))
1217 def
= df_find_def (insn
, reg
);
1218 gcc_assert (def
!= NULL
);
1219 if (!latch_dominating_def (reg
, &last_def
))
1221 if (last_def
!= def
)
1224 if (!iv_analyze_biv (reg
, &iv
))
1227 return iv
.step
!= const0_rtx
;
1230 /* Calculates value of IV at ITERATION-th iteration. */
1233 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1237 /* We would need to generate some if_then_else patterns, and so far
1238 it is not needed anywhere. */
1239 gcc_assert (!iv
->first_special
);
1241 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1242 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1243 simplify_gen_binary (MULT
, iv
->extend_mode
,
1244 iv
->step
, iteration
));
1248 if (iv
->extend_mode
== iv
->mode
)
1251 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1253 if (iv
->extend
== UNKNOWN
)
1256 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1257 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1258 simplify_gen_binary (MULT
, iv
->extend_mode
,
1264 /* Free the data for an induction variable analysis. */
1267 iv_analysis_done (void)
1273 df_finish_pass (true);
1275 free (iv_ref_table
);
1276 iv_ref_table
= NULL
;
1277 iv_ref_table_size
= 0;
1282 /* Computes inverse to X modulo (1 << MOD). */
1284 static unsigned HOST_WIDEST_INT
1285 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1287 unsigned HOST_WIDEST_INT mask
=
1288 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1289 unsigned HOST_WIDEST_INT rslt
= 1;
1292 for (i
= 0; i
< mod
- 1; i
++)
1294 rslt
= (rslt
* x
) & mask
;
1301 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1304 altered_reg_used (rtx
*reg
, void *alt
)
1309 return REGNO_REG_SET_P ((bitmap
) alt
, REGNO (*reg
));
1312 /* Marks registers altered by EXPR in set ALT. */
1315 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1317 if (GET_CODE (expr
) == SUBREG
)
1318 expr
= SUBREG_REG (expr
);
1322 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1325 /* Checks whether RHS is simple enough to process. */
1328 simple_rhs_p (rtx rhs
)
1332 if (function_invariant_p (rhs
)
1333 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1336 switch (GET_CODE (rhs
))
1341 op0
= XEXP (rhs
, 0);
1342 op1
= XEXP (rhs
, 1);
1343 /* Allow reg OP const and reg OP reg. */
1344 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1345 && !function_invariant_p (op0
))
1347 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1348 && !function_invariant_p (op1
))
1357 op0
= XEXP (rhs
, 0);
1358 op1
= XEXP (rhs
, 1);
1359 /* Allow reg OP const. */
1360 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1362 if (!function_invariant_p (op1
))
1372 /* If REG has a single definition, replace it with its known value in EXPR.
1373 Callback for for_each_rtx. */
1376 replace_single_def_regs (rtx
*reg
, void *expr1
)
1381 rtx
*expr
= (rtx
*)expr1
;
1386 regno
= REGNO (*reg
);
1390 adef
= DF_REG_DEF_CHAIN (regno
);
1391 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1392 || DF_REF_IS_ARTIFICIAL (adef
))
1395 set
= single_set (DF_REF_INSN (adef
));
1396 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1397 || REGNO (SET_DEST (set
)) != regno
)
1400 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1402 if (note
&& function_invariant_p (XEXP (note
, 0)))
1404 src
= XEXP (note
, 0);
1407 src
= SET_SRC (set
);
1411 regno
= REGNO (src
);
1416 if (!function_invariant_p (src
))
1419 *expr
= simplify_replace_rtx (*expr
, *reg
, src
);
1423 /* A subroutine of simplify_using_initial_values, this function examines INSN
1424 to see if it contains a suitable set that we can use to make a replacement.
1425 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1426 the set; return false otherwise. */
1429 suitable_set_for_replacement (rtx insn
, rtx
*dest
, rtx
*src
)
1431 rtx set
= single_set (insn
);
1432 rtx lhs
= NULL_RTX
, rhs
;
1437 lhs
= SET_DEST (set
);
1441 rhs
= find_reg_equal_equiv_note (insn
);
1443 rhs
= XEXP (rhs
, 0);
1445 rhs
= SET_SRC (set
);
1447 if (!simple_rhs_p (rhs
))
1455 /* Using the data returned by suitable_set_for_replacement, replace DEST
1456 with SRC in *EXPR and return the new expression. Also call
1457 replace_single_def_regs if the replacement changed something. */
1459 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1462 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1465 while (for_each_rtx (expr
, replace_single_def_regs
, expr
) != 0)
1469 /* Checks whether A implies B. */
1472 implies_p (rtx a
, rtx b
)
1474 rtx op0
, op1
, opb0
, opb1
, r
;
1475 enum machine_mode mode
;
1477 if (GET_CODE (a
) == EQ
)
1484 r
= simplify_replace_rtx (b
, op0
, op1
);
1485 if (r
== const_true_rtx
)
1491 r
= simplify_replace_rtx (b
, op1
, op0
);
1492 if (r
== const_true_rtx
)
1497 if (b
== const_true_rtx
)
1500 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1501 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1502 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1503 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1511 mode
= GET_MODE (op0
);
1512 if (mode
!= GET_MODE (opb0
))
1514 else if (mode
== VOIDmode
)
1516 mode
= GET_MODE (op1
);
1517 if (mode
!= GET_MODE (opb1
))
1521 /* A < B implies A + 1 <= B. */
1522 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1523 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1526 if (GET_CODE (a
) == GT
)
1533 if (GET_CODE (b
) == GE
)
1540 if (SCALAR_INT_MODE_P (mode
)
1541 && rtx_equal_p (op1
, opb1
)
1542 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1547 /* A < B or A > B imply A != B. TODO: Likewise
1548 A + n < B implies A != B + n if neither wraps. */
1549 if (GET_CODE (b
) == NE
1550 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1551 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1553 if (rtx_equal_p (op0
, opb0
)
1554 && rtx_equal_p (op1
, opb1
))
1558 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1559 if (GET_CODE (a
) == NE
1560 && op1
== const0_rtx
)
1562 if ((GET_CODE (b
) == GTU
1563 && opb1
== const0_rtx
)
1564 || (GET_CODE (b
) == GEU
1565 && opb1
== const1_rtx
))
1566 return rtx_equal_p (op0
, opb0
);
1569 /* A != N is equivalent to A - (N + 1) <u -1. */
1570 if (GET_CODE (a
) == NE
1571 && CONST_INT_P (op1
)
1572 && GET_CODE (b
) == LTU
1573 && opb1
== constm1_rtx
1574 && GET_CODE (opb0
) == PLUS
1575 && CONST_INT_P (XEXP (opb0
, 1))
1576 /* Avoid overflows. */
1577 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1578 != ((unsigned HOST_WIDE_INT
)1
1579 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1580 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1581 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1583 /* Likewise, A != N implies A - N > 0. */
1584 if (GET_CODE (a
) == NE
1585 && CONST_INT_P (op1
))
1587 if (GET_CODE (b
) == GTU
1588 && GET_CODE (opb0
) == PLUS
1589 && opb1
== const0_rtx
1590 && CONST_INT_P (XEXP (opb0
, 1))
1591 /* Avoid overflows. */
1592 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1593 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1594 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1595 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1596 if (GET_CODE (b
) == GEU
1597 && GET_CODE (opb0
) == PLUS
1598 && opb1
== const1_rtx
1599 && CONST_INT_P (XEXP (opb0
, 1))
1600 /* Avoid overflows. */
1601 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1602 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1603 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1604 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1607 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1608 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1609 && CONST_INT_P (op1
)
1610 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1611 || INTVAL (op1
) >= 0)
1612 && GET_CODE (b
) == LTU
1613 && CONST_INT_P (opb1
)
1614 && rtx_equal_p (op0
, opb0
))
1615 return INTVAL (opb1
) < 0;
1620 /* Canonicalizes COND so that
1622 (1) Ensure that operands are ordered according to
1623 swap_commutative_operands_p.
1624 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1625 for GE, GEU, and LEU. */
1628 canon_condition (rtx cond
)
1633 enum machine_mode mode
;
1635 code
= GET_CODE (cond
);
1636 op0
= XEXP (cond
, 0);
1637 op1
= XEXP (cond
, 1);
1639 if (swap_commutative_operands_p (op0
, op1
))
1641 code
= swap_condition (code
);
1647 mode
= GET_MODE (op0
);
1648 if (mode
== VOIDmode
)
1649 mode
= GET_MODE (op1
);
1650 gcc_assert (mode
!= VOIDmode
);
1652 if (CONST_INT_P (op1
)
1653 && GET_MODE_CLASS (mode
) != MODE_CC
1654 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1656 HOST_WIDE_INT const_val
= INTVAL (op1
);
1657 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1658 unsigned HOST_WIDE_INT max_val
1659 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1664 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1665 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1668 /* When cross-compiling, const_val might be sign-extended from
1669 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1671 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1672 != (((HOST_WIDE_INT
) 1
1673 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1674 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1678 if (uconst_val
< max_val
)
1679 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1683 if (uconst_val
!= 0)
1684 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1692 if (op0
!= XEXP (cond
, 0)
1693 || op1
!= XEXP (cond
, 1)
1694 || code
!= GET_CODE (cond
)
1695 || GET_MODE (cond
) != SImode
)
1696 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1701 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1702 set of altered regs. */
1705 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1707 rtx rev
, reve
, exp
= *expr
;
1709 /* If some register gets altered later, we do not really speak about its
1710 value at the time of comparison. */
1712 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1715 if (GET_CODE (cond
) == EQ
1716 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1718 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1722 if (!COMPARISON_P (exp
))
1725 rev
= reversed_condition (cond
);
1726 reve
= reversed_condition (exp
);
1728 cond
= canon_condition (cond
);
1729 exp
= canon_condition (exp
);
1731 rev
= canon_condition (rev
);
1733 reve
= canon_condition (reve
);
1735 if (rtx_equal_p (exp
, cond
))
1737 *expr
= const_true_rtx
;
1741 if (rev
&& rtx_equal_p (exp
, rev
))
1747 if (implies_p (cond
, exp
))
1749 *expr
= const_true_rtx
;
1753 if (reve
&& implies_p (cond
, reve
))
1759 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1761 if (rev
&& implies_p (exp
, rev
))
1767 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1768 if (rev
&& reve
&& implies_p (reve
, rev
))
1770 *expr
= const_true_rtx
;
1774 /* We would like to have some other tests here. TODO. */
1779 /* Use relationship between A and *B to eventually eliminate *B.
1780 OP is the operation we consider. */
1783 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1788 /* If A implies *B, we may replace *B by true. */
1789 if (implies_p (a
, *b
))
1790 *b
= const_true_rtx
;
1794 /* If *B implies A, we may replace *B by false. */
1795 if (implies_p (*b
, a
))
1804 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1805 operation we consider. */
1808 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1812 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1813 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1814 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1815 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1818 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1819 is a list, its elements are assumed to be combined using OP. */
1822 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1824 bool expression_valid
;
1825 rtx head
, tail
, insn
, cond_list
, last_valid_expr
;
1827 regset altered
, this_altered
;
1833 if (CONSTANT_P (*expr
))
1836 if (GET_CODE (*expr
) == EXPR_LIST
)
1838 head
= XEXP (*expr
, 0);
1839 tail
= XEXP (*expr
, 1);
1841 eliminate_implied_conditions (op
, &head
, tail
);
1846 neutral
= const_true_rtx
;
1851 neutral
= const0_rtx
;
1852 aggr
= const_true_rtx
;
1859 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1862 XEXP (*expr
, 0) = aggr
;
1863 XEXP (*expr
, 1) = NULL_RTX
;
1866 else if (head
== neutral
)
1869 simplify_using_initial_values (loop
, op
, expr
);
1872 simplify_using_initial_values (loop
, op
, &tail
);
1874 if (tail
&& XEXP (tail
, 0) == aggr
)
1880 XEXP (*expr
, 0) = head
;
1881 XEXP (*expr
, 1) = tail
;
1885 gcc_assert (op
== UNKNOWN
);
1888 if (for_each_rtx (expr
, replace_single_def_regs
, expr
) == 0)
1890 if (CONSTANT_P (*expr
))
1893 e
= loop_preheader_edge (loop
);
1894 if (e
->src
== ENTRY_BLOCK_PTR
)
1897 altered
= ALLOC_REG_SET (®_obstack
);
1898 this_altered
= ALLOC_REG_SET (®_obstack
);
1900 expression_valid
= true;
1901 last_valid_expr
= *expr
;
1902 cond_list
= NULL_RTX
;
1905 insn
= BB_END (e
->src
);
1906 if (any_condjump_p (insn
))
1908 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1910 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1911 cond
= reversed_condition (cond
);
1915 simplify_using_condition (cond
, expr
, altered
);
1919 if (CONSTANT_P (*expr
))
1921 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1923 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1924 if (CONSTANT_P (*expr
))
1928 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1932 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1940 CLEAR_REG_SET (this_altered
);
1941 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
1946 /* Kill all call clobbered registers. */
1947 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1948 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1949 SET_REGNO_REG_SET (this_altered
, i
);
1952 if (suitable_set_for_replacement (insn
, &dest
, &src
))
1954 rtx
*pnote
, *pnote_next
;
1956 replace_in_expr (expr
, dest
, src
);
1957 if (CONSTANT_P (*expr
))
1960 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
1963 rtx old_cond
= XEXP (note
, 0);
1965 pnote_next
= &XEXP (note
, 1);
1966 replace_in_expr (&XEXP (note
, 0), dest
, src
);
1968 /* We can no longer use a condition that has been simplified
1969 to a constant, and simplify_using_condition will abort if
1971 if (CONSTANT_P (XEXP (note
, 0)))
1973 *pnote
= *pnote_next
;
1975 free_EXPR_LIST_node (note
);
1977 /* Retry simplifications with this condition if either the
1978 expression or the condition changed. */
1979 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
1980 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1984 /* If we did not use this insn to make a replacement, any overlap
1985 between stores in this insn and our expression will cause the
1986 expression to become invalid. */
1987 if (for_each_rtx (expr
, altered_reg_used
, this_altered
))
1990 if (CONSTANT_P (*expr
))
1993 IOR_REG_SET (altered
, this_altered
);
1995 /* If the expression now contains regs that have been altered, we
1996 can't return it to the caller. However, it is still valid for
1997 further simplification, so keep searching to see if we can
1998 eventually turn it into a constant. */
1999 if (for_each_rtx (expr
, altered_reg_used
, altered
))
2000 expression_valid
= false;
2001 if (expression_valid
)
2002 last_valid_expr
= *expr
;
2005 if (!single_pred_p (e
->src
)
2006 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
2008 e
= single_pred_edge (e
->src
);
2012 free_EXPR_LIST_list (&cond_list
);
2013 if (!CONSTANT_P (*expr
))
2014 *expr
= last_valid_expr
;
2015 FREE_REG_SET (altered
);
2016 FREE_REG_SET (this_altered
);
2019 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2020 that IV occurs as left operands of comparison COND and its signedness
2021 is SIGNED_P to DESC. */
2024 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
2025 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2027 rtx mmin
, mmax
, cond_over
, cond_under
;
2029 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2030 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2032 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2041 if (cond_under
!= const0_rtx
)
2043 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2044 if (cond_over
!= const0_rtx
)
2045 desc
->noloop_assumptions
=
2046 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2053 if (cond_over
!= const0_rtx
)
2055 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2056 if (cond_under
!= const0_rtx
)
2057 desc
->noloop_assumptions
=
2058 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2062 if (cond_over
!= const0_rtx
)
2064 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2065 if (cond_under
!= const0_rtx
)
2067 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2075 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
2078 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2079 subregs of the same mode if possible (sometimes it is necessary to add
2080 some assumptions to DESC). */
2083 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2084 enum rtx_code cond
, struct niter_desc
*desc
)
2086 enum machine_mode comp_mode
;
2089 /* If the ivs behave specially in the first iteration, or are
2090 added/multiplied after extending, we ignore them. */
2091 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2093 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2096 /* If there is some extend, it must match signedness of the comparison. */
2101 if (iv0
->extend
== ZERO_EXTEND
2102 || iv1
->extend
== ZERO_EXTEND
)
2109 if (iv0
->extend
== SIGN_EXTEND
2110 || iv1
->extend
== SIGN_EXTEND
)
2116 if (iv0
->extend
!= UNKNOWN
2117 && iv1
->extend
!= UNKNOWN
2118 && iv0
->extend
!= iv1
->extend
)
2122 if (iv0
->extend
!= UNKNOWN
)
2123 signed_p
= iv0
->extend
== SIGN_EXTEND
;
2124 if (iv1
->extend
!= UNKNOWN
)
2125 signed_p
= iv1
->extend
== SIGN_EXTEND
;
2132 /* Values of both variables should be computed in the same mode. These
2133 might indeed be different, if we have comparison like
2135 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2137 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2138 in different modes. This does not seem impossible to handle, but
2139 it hardly ever occurs in practice.
2141 The only exception is the case when one of operands is invariant.
2142 For example pentium 3 generates comparisons like
2143 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2144 definitely do not want this prevent the optimization. */
2145 comp_mode
= iv0
->extend_mode
;
2146 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2147 comp_mode
= iv1
->extend_mode
;
2149 if (iv0
->extend_mode
!= comp_mode
)
2151 if (iv0
->mode
!= iv0
->extend_mode
2152 || iv0
->step
!= const0_rtx
)
2155 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2156 comp_mode
, iv0
->base
, iv0
->mode
);
2157 iv0
->extend_mode
= comp_mode
;
2160 if (iv1
->extend_mode
!= comp_mode
)
2162 if (iv1
->mode
!= iv1
->extend_mode
2163 || iv1
->step
!= const0_rtx
)
2166 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2167 comp_mode
, iv1
->base
, iv1
->mode
);
2168 iv1
->extend_mode
= comp_mode
;
2171 /* Check that both ivs belong to a range of a single mode. If one of the
2172 operands is an invariant, we may need to shorten it into the common
2174 if (iv0
->mode
== iv0
->extend_mode
2175 && iv0
->step
== const0_rtx
2176 && iv0
->mode
!= iv1
->mode
)
2177 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2179 if (iv1
->mode
== iv1
->extend_mode
2180 && iv1
->step
== const0_rtx
2181 && iv0
->mode
!= iv1
->mode
)
2182 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2184 if (iv0
->mode
!= iv1
->mode
)
2187 desc
->mode
= iv0
->mode
;
2188 desc
->signed_p
= signed_p
;
2193 /* Tries to estimate the maximum number of iterations in LOOP, and store the
2194 result in DESC. This function is called from iv_number_of_iterations with
2195 a number of fields in DESC already filled in. OLD_NITER is the original
2196 expression for the number of iterations, before we tried to simplify it. */
2198 static unsigned HOST_WIDEST_INT
2199 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2201 rtx niter
= desc
->niter_expr
;
2202 rtx mmin
, mmax
, cmp
;
2203 unsigned HOST_WIDEST_INT nmax
, inc
;
2205 if (GET_CODE (niter
) == AND
2206 && CONST_INT_P (XEXP (niter
, 0)))
2208 nmax
= INTVAL (XEXP (niter
, 0));
2209 if (!(nmax
& (nmax
+ 1)))
2211 desc
->niter_max
= nmax
;
2216 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2217 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2219 if (GET_CODE (niter
) == UDIV
)
2221 if (!CONST_INT_P (XEXP (niter
, 1)))
2223 desc
->niter_max
= nmax
;
2226 inc
= INTVAL (XEXP (niter
, 1));
2227 niter
= XEXP (niter
, 0);
2232 /* We could use a binary search here, but for now improving the upper
2233 bound by just one eliminates one important corner case. */
2234 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2235 desc
->mode
, old_niter
, mmax
);
2236 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2237 if (cmp
== const_true_rtx
)
2242 fprintf (dump_file
, ";; improved upper bound by one.\n");
2244 desc
->niter_max
= nmax
/ inc
;
2248 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2249 the result into DESC. Very similar to determine_number_of_iterations
2250 (basically its rtl version), complicated by things like subregs. */
2253 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2254 struct niter_desc
*desc
)
2256 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2257 struct rtx_iv iv0
, iv1
, tmp_iv
;
2258 rtx assumption
, may_not_xform
;
2260 enum machine_mode mode
, comp_mode
;
2261 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2262 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2263 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2264 int was_sharp
= false;
2268 /* The meaning of these assumptions is this:
2270 then the rest of information does not have to be valid
2271 if noloop_assumptions then the loop does not roll
2272 if infinite then this exit is never used */
2274 desc
->assumptions
= NULL_RTX
;
2275 desc
->noloop_assumptions
= NULL_RTX
;
2276 desc
->infinite
= NULL_RTX
;
2277 desc
->simple_p
= true;
2279 desc
->const_iter
= false;
2280 desc
->niter_expr
= NULL_RTX
;
2281 desc
->niter_max
= 0;
2283 cond
= GET_CODE (condition
);
2284 gcc_assert (COMPARISON_P (condition
));
2286 mode
= GET_MODE (XEXP (condition
, 0));
2287 if (mode
== VOIDmode
)
2288 mode
= GET_MODE (XEXP (condition
, 1));
2289 /* The constant comparisons should be folded. */
2290 gcc_assert (mode
!= VOIDmode
);
2292 /* We only handle integers or pointers. */
2293 if (GET_MODE_CLASS (mode
) != MODE_INT
2294 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2297 op0
= XEXP (condition
, 0);
2298 if (!iv_analyze (insn
, op0
, &iv0
))
2300 if (iv0
.extend_mode
== VOIDmode
)
2301 iv0
.mode
= iv0
.extend_mode
= mode
;
2303 op1
= XEXP (condition
, 1);
2304 if (!iv_analyze (insn
, op1
, &iv1
))
2306 if (iv1
.extend_mode
== VOIDmode
)
2307 iv1
.mode
= iv1
.extend_mode
= mode
;
2309 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2310 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2313 /* Check condition and normalize it. */
2321 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2322 cond
= swap_condition (cond
);
2334 /* Handle extends. This is relatively nontrivial, so we only try in some
2335 easy cases, when we can canonicalize the ivs (possibly by adding some
2336 assumptions) to shape subreg (base + i * step). This function also fills
2337 in desc->mode and desc->signed_p. */
2339 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2342 comp_mode
= iv0
.extend_mode
;
2344 size
= GET_MODE_BITSIZE (mode
);
2345 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2346 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2347 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2349 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2352 /* We can take care of the case of two induction variables chasing each other
2353 if the test is NE. I have never seen a loop using it, but still it is
2355 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2360 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2361 iv1
.step
= const0_rtx
;
2364 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2365 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2367 /* This is either infinite loop or the one that ends immediately, depending
2368 on initial values. Unswitching should remove this kind of conditions. */
2369 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2374 if (iv0
.step
== const0_rtx
)
2375 step_val
= -INTVAL (iv1
.step
);
2377 step_val
= INTVAL (iv0
.step
);
2379 /* Ignore loops of while (i-- < 10) type. */
2383 step_is_pow2
= !(step_val
& (step_val
- 1));
2387 /* We do not care about whether the step is power of two in this
2389 step_is_pow2
= false;
2393 /* Some more condition normalization. We must record some assumptions
2394 due to overflows. */
2399 /* We want to take care only of non-sharp relationals; this is easy,
2400 as in cases the overflow would make the transformation unsafe
2401 the loop does not roll. Seemingly it would make more sense to want
2402 to take care of sharp relationals instead, as NE is more similar to
2403 them, but the problem is that here the transformation would be more
2404 difficult due to possibly infinite loops. */
2405 if (iv0
.step
== const0_rtx
)
2407 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2408 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2410 if (assumption
== const_true_rtx
)
2411 goto zero_iter_simplify
;
2412 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2413 iv0
.base
, const1_rtx
);
2417 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2418 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2420 if (assumption
== const_true_rtx
)
2421 goto zero_iter_simplify
;
2422 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2423 iv1
.base
, constm1_rtx
);
2426 if (assumption
!= const0_rtx
)
2427 desc
->noloop_assumptions
=
2428 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2429 cond
= (cond
== LT
) ? LE
: LEU
;
2431 /* It will be useful to be able to tell the difference once more in
2432 LE -> NE reduction. */
2438 /* Take care of trivially infinite loops. */
2441 if (iv0
.step
== const0_rtx
)
2443 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2444 if (rtx_equal_p (tmp
, mode_mmin
))
2447 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2448 /* Fill in the remaining fields somehow. */
2449 goto zero_iter_simplify
;
2454 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2455 if (rtx_equal_p (tmp
, mode_mmax
))
2458 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2459 /* Fill in the remaining fields somehow. */
2460 goto zero_iter_simplify
;
2465 /* If we can we want to take care of NE conditions instead of size
2466 comparisons, as they are much more friendly (most importantly
2467 this takes care of special handling of loops with step 1). We can
2468 do it if we first check that upper bound is greater or equal to
2469 lower bound, their difference is constant c modulo step and that
2470 there is not an overflow. */
2473 if (iv0
.step
== const0_rtx
)
2474 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2477 step
= lowpart_subreg (mode
, step
, comp_mode
);
2478 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2479 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2480 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2481 may_xform
= const0_rtx
;
2482 may_not_xform
= const_true_rtx
;
2484 if (CONST_INT_P (delta
))
2486 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2488 /* A special case. We have transformed condition of type
2489 for (i = 0; i < 4; i += 4)
2491 for (i = 0; i <= 3; i += 4)
2492 obviously if the test for overflow during that transformation
2493 passed, we cannot overflow here. Most importantly any
2494 loop with sharp end condition and step 1 falls into this
2495 category, so handling this case specially is definitely
2496 worth the troubles. */
2497 may_xform
= const_true_rtx
;
2499 else if (iv0
.step
== const0_rtx
)
2501 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2502 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2503 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2504 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2505 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2507 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2513 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2514 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2515 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2516 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2517 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2519 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2525 if (may_xform
!= const0_rtx
)
2527 /* We perform the transformation always provided that it is not
2528 completely senseless. This is OK, as we would need this assumption
2529 to determine the number of iterations anyway. */
2530 if (may_xform
!= const_true_rtx
)
2532 /* If the step is a power of two and the final value we have
2533 computed overflows, the cycle is infinite. Otherwise it
2534 is nontrivial to compute the number of iterations. */
2536 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2539 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2543 /* We are going to lose some information about upper bound on
2544 number of iterations in this step, so record the information
2546 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2547 if (CONST_INT_P (iv1
.base
))
2548 up
= INTVAL (iv1
.base
);
2550 up
= INTVAL (mode_mmax
) - inc
;
2551 down
= INTVAL (CONST_INT_P (iv0
.base
)
2554 desc
->niter_max
= (up
- down
) / inc
+ 1;
2556 if (iv0
.step
== const0_rtx
)
2558 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2559 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2563 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2564 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2567 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2568 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2569 assumption
= simplify_gen_relational (reverse_condition (cond
),
2570 SImode
, mode
, tmp0
, tmp1
);
2571 if (assumption
== const_true_rtx
)
2572 goto zero_iter_simplify
;
2573 else if (assumption
!= const0_rtx
)
2574 desc
->noloop_assumptions
=
2575 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2580 /* Count the number of iterations. */
2583 /* Everything we do here is just arithmetics modulo size of mode. This
2584 makes us able to do more involved computations of number of iterations
2585 than in other cases. First transform the condition into shape
2586 s * i <> c, with s positive. */
2587 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2588 iv0
.base
= const0_rtx
;
2589 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2590 iv1
.step
= const0_rtx
;
2591 if (INTVAL (iv0
.step
) < 0)
2593 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2594 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2596 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2598 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2599 is infinite. Otherwise, the number of iterations is
2600 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2601 s
= INTVAL (iv0
.step
); d
= 1;
2608 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2610 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2611 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2612 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2613 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2615 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2616 inv
= inverse (s
, size
);
2617 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2618 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2622 if (iv1
.step
== const0_rtx
)
2623 /* Condition in shape a + s * i <= b
2624 We must know that b + s does not overflow and a <= b + s and then we
2625 can compute number of iterations as (b + s - a) / s. (It might
2626 seem that we in fact could be more clever about testing the b + s
2627 overflow condition using some information about b - a mod s,
2628 but it was already taken into account during LE -> NE transform). */
2631 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2632 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2634 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2635 lowpart_subreg (mode
, step
,
2641 /* If s is power of 2, we know that the loop is infinite if
2642 a % s <= b % s and b + s overflows. */
2643 assumption
= simplify_gen_relational (reverse_condition (cond
),
2647 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2648 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2649 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2650 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2652 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2656 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2659 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2662 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2663 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2664 assumption
= simplify_gen_relational (reverse_condition (cond
),
2665 SImode
, mode
, tmp0
, tmp
);
2667 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2668 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2672 /* Condition in shape a <= b - s * i
2673 We must know that a - s does not overflow and a - s <= b and then
2674 we can again compute number of iterations as (b - (a - s)) / s. */
2675 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2676 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2677 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2679 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2680 lowpart_subreg (mode
, step
, comp_mode
));
2685 /* If s is power of 2, we know that the loop is infinite if
2686 a % s <= b % s and a - s overflows. */
2687 assumption
= simplify_gen_relational (reverse_condition (cond
),
2691 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2692 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2693 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2694 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2696 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2700 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2703 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2706 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2707 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2708 assumption
= simplify_gen_relational (reverse_condition (cond
),
2711 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2712 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2714 if (assumption
== const_true_rtx
)
2715 goto zero_iter_simplify
;
2716 else if (assumption
!= const0_rtx
)
2717 desc
->noloop_assumptions
=
2718 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2719 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2720 desc
->niter_expr
= delta
;
2723 old_niter
= desc
->niter_expr
;
2725 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2726 if (desc
->assumptions
2727 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2729 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2730 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2731 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2733 /* Rerun the simplification. Consider code (created by copying loop headers)
2745 The first pass determines that i = 0, the second pass uses it to eliminate
2746 noloop assumption. */
2748 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2749 if (desc
->assumptions
2750 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2752 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2753 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2754 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2756 if (desc
->noloop_assumptions
2757 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2760 if (CONST_INT_P (desc
->niter_expr
))
2762 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2764 desc
->const_iter
= true;
2765 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2769 if (!desc
->niter_max
)
2770 desc
->niter_max
= determine_max_iter (loop
, desc
, old_niter
);
2772 /* simplify_using_initial_values does a copy propagation on the registers
2773 in the expression for the number of iterations. This prolongs life
2774 ranges of registers and increases register pressure, and usually
2775 brings no gain (and if it happens to do, the cse pass will take care
2776 of it anyway). So prevent this behavior, unless it enabled us to
2777 derive that the number of iterations is a constant. */
2778 desc
->niter_expr
= old_niter
;
2784 /* Simplify the assumptions. */
2785 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2786 if (desc
->assumptions
2787 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2789 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2793 desc
->const_iter
= true;
2795 desc
->niter_max
= 0;
2796 desc
->noloop_assumptions
= NULL_RTX
;
2797 desc
->niter_expr
= const0_rtx
;
2801 desc
->simple_p
= false;
2805 /* Checks whether E is a simple exit from LOOP and stores its description
2809 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2811 basic_block exit_bb
;
2816 desc
->simple_p
= false;
2818 /* It must belong directly to the loop. */
2819 if (exit_bb
->loop_father
!= loop
)
2822 /* It must be tested (at least) once during any iteration. */
2823 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2826 /* It must end in a simple conditional jump. */
2827 if (!any_condjump_p (BB_END (exit_bb
)))
2830 ein
= EDGE_SUCC (exit_bb
, 0);
2832 ein
= EDGE_SUCC (exit_bb
, 1);
2835 desc
->in_edge
= ein
;
2837 /* Test whether the condition is suitable. */
2838 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2841 if (ein
->flags
& EDGE_FALLTHRU
)
2843 condition
= reversed_condition (condition
);
2848 /* Check that we are able to determine number of iterations and fill
2849 in information about it. */
2850 iv_number_of_iterations (loop
, at
, condition
, desc
);
2853 /* Finds a simple exit of LOOP and stores its description into DESC. */
2856 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2861 struct niter_desc act
;
2865 desc
->simple_p
= false;
2866 body
= get_loop_body (loop
);
2868 for (i
= 0; i
< loop
->num_nodes
; i
++)
2870 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2872 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2875 check_simple_exit (loop
, e
, &act
);
2883 /* Prefer constant iterations; the less the better. */
2885 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2888 /* Also if the actual exit may be infinite, while the old one
2889 not, prefer the old one. */
2890 if (act
.infinite
&& !desc
->infinite
)
2902 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2903 fprintf (dump_file
, " simple exit %d -> %d\n",
2904 desc
->out_edge
->src
->index
,
2905 desc
->out_edge
->dest
->index
);
2906 if (desc
->assumptions
)
2908 fprintf (dump_file
, " assumptions: ");
2909 print_rtl (dump_file
, desc
->assumptions
);
2910 fprintf (dump_file
, "\n");
2912 if (desc
->noloop_assumptions
)
2914 fprintf (dump_file
, " does not roll if: ");
2915 print_rtl (dump_file
, desc
->noloop_assumptions
);
2916 fprintf (dump_file
, "\n");
2920 fprintf (dump_file
, " infinite if: ");
2921 print_rtl (dump_file
, desc
->infinite
);
2922 fprintf (dump_file
, "\n");
2925 fprintf (dump_file
, " number of iterations: ");
2926 print_rtl (dump_file
, desc
->niter_expr
);
2927 fprintf (dump_file
, "\n");
2929 fprintf (dump_file
, " upper bound: ");
2930 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2931 fprintf (dump_file
, "\n");
2934 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2940 /* Creates a simple loop description of LOOP if it was not computed
2944 get_simple_loop_desc (struct loop
*loop
)
2946 struct niter_desc
*desc
= simple_loop_desc (loop
);
2951 /* At least desc->infinite is not always initialized by
2952 find_simple_loop_exit. */
2953 desc
= XCNEW (struct niter_desc
);
2954 iv_analysis_loop_init (loop
);
2955 find_simple_exit (loop
, desc
);
2958 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
2960 const char *wording
;
2962 /* Assume that no overflow happens and that the loop is finite.
2963 We already warned at the tree level if we ran optimizations there. */
2964 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
2969 flag_unsafe_loop_optimizations
2970 ? N_("assuming that the loop is not infinite")
2971 : N_("cannot optimize possibly infinite loops");
2972 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2975 if (desc
->assumptions
)
2978 flag_unsafe_loop_optimizations
2979 ? N_("assuming that the loop counter does not overflow")
2980 : N_("cannot optimize loop, the loop counter may overflow");
2981 warning (OPT_Wunsafe_loop_optimizations
, "%s",
2986 if (flag_unsafe_loop_optimizations
)
2988 desc
->assumptions
= NULL_RTX
;
2989 desc
->infinite
= NULL_RTX
;
2996 /* Releases simple loop description for LOOP. */
2999 free_simple_loop_desc (struct loop
*loop
)
3001 struct niter_desc
*desc
= simple_loop_desc (loop
);