1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
64 #include "dominance.h"
66 #include "basic-block.h"
71 #include "diagnostic-core.h"
73 #include "hash-table.h"
77 /* Possible return values of iv_get_reaching_def. */
81 /* More than one reaching def, or reaching def that does not
85 /* The use is trivial invariant of the loop, i.e. is not changed
89 /* The use is reached by initial value and a value from the
90 previous iteration. */
93 /* The use has single dominating def. */
97 /* Information about a biv. */
101 unsigned regno
; /* The register of the biv. */
102 struct rtx_iv iv
; /* Value of the biv. */
105 static bool clean_slate
= true;
107 static unsigned int iv_ref_table_size
= 0;
109 /* Table of rtx_ivs indexed by the df_ref uid field. */
110 static struct rtx_iv
** iv_ref_table
;
112 /* Induction variable stored at the reference. */
113 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
114 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
116 /* The current loop. */
118 static struct loop
*current_loop
;
120 /* Hashtable helper. */
122 struct biv_entry_hasher
: typed_free_remove
<biv_entry
>
124 typedef biv_entry value_type
;
125 typedef rtx_def compare_type
;
126 static inline hashval_t
hash (const value_type
*);
127 static inline bool equal (const value_type
*, const compare_type
*);
130 /* Returns hash value for biv B. */
133 biv_entry_hasher::hash (const value_type
*b
)
138 /* Compares biv B and register R. */
141 biv_entry_hasher::equal (const value_type
*b
, const compare_type
*r
)
143 return b
->regno
== REGNO (r
);
146 /* Bivs of the current loop. */
148 static hash_table
<biv_entry_hasher
> *bivs
;
150 static bool iv_analyze_op (rtx_insn
*, rtx
, struct rtx_iv
*);
152 /* Return the RTX code corresponding to the IV extend code EXTEND. */
153 static inline enum rtx_code
154 iv_extend_to_rtx_code (enum iv_extend_code extend
)
162 case IV_UNKNOWN_EXTEND
:
168 /* Dumps information about IV to FILE. */
170 extern void dump_iv_info (FILE *, struct rtx_iv
*);
172 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
176 fprintf (file
, "not simple");
180 if (iv
->step
== const0_rtx
181 && !iv
->first_special
)
182 fprintf (file
, "invariant ");
184 print_rtl (file
, iv
->base
);
185 if (iv
->step
!= const0_rtx
)
187 fprintf (file
, " + ");
188 print_rtl (file
, iv
->step
);
189 fprintf (file
, " * iteration");
191 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
193 if (iv
->mode
!= iv
->extend_mode
)
194 fprintf (file
, " %s to %s",
195 rtx_name
[iv_extend_to_rtx_code (iv
->extend
)],
196 GET_MODE_NAME (iv
->extend_mode
));
198 if (iv
->mult
!= const1_rtx
)
200 fprintf (file
, " * ");
201 print_rtl (file
, iv
->mult
);
203 if (iv
->delta
!= const0_rtx
)
205 fprintf (file
, " + ");
206 print_rtl (file
, iv
->delta
);
208 if (iv
->first_special
)
209 fprintf (file
, " (first special)");
212 /* Generates a subreg to get the least significant part of EXPR (in mode
213 INNER_MODE) to OUTER_MODE. */
216 lowpart_subreg (machine_mode outer_mode
, rtx expr
,
217 machine_mode inner_mode
)
219 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
220 subreg_lowpart_offset (outer_mode
, inner_mode
));
224 check_iv_ref_table_size (void)
226 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
228 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
229 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
230 memset (&iv_ref_table
[iv_ref_table_size
], 0,
231 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
232 iv_ref_table_size
= new_size
;
237 /* Checks whether REG is a well-behaved register. */
240 simple_reg_p (rtx reg
)
244 if (GET_CODE (reg
) == SUBREG
)
246 if (!subreg_lowpart_p (reg
))
248 reg
= SUBREG_REG (reg
);
255 if (HARD_REGISTER_NUM_P (r
))
258 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
264 /* Clears the information about ivs stored in df. */
269 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
272 check_iv_ref_table_size ();
273 for (i
= 0; i
< n_defs
; i
++)
275 iv
= iv_ref_table
[i
];
279 iv_ref_table
[i
] = NULL
;
287 /* Prepare the data for an induction variable analysis of a LOOP. */
290 iv_analysis_loop_init (struct loop
*loop
)
294 /* Clear the information from the analysis of the previous loop. */
297 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
298 bivs
= new hash_table
<biv_entry_hasher
> (10);
304 /* Get rid of the ud chains before processing the rescans. Then add
306 df_remove_problem (df_chain
);
307 df_process_deferred_rescans ();
308 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
309 df_chain_add_problem (DF_UD_CHAIN
);
310 df_note_add_problem ();
311 df_analyze_loop (loop
);
313 df_dump_region (dump_file
);
315 check_iv_ref_table_size ();
318 /* Finds the definition of REG that dominates loop latch and stores
319 it to DEF. Returns false if there is not a single definition
320 dominating the latch. If REG has no definition in loop, DEF
321 is set to NULL and true is returned. */
324 latch_dominating_def (rtx reg
, df_ref
*def
)
326 df_ref single_rd
= NULL
, adef
;
327 unsigned regno
= REGNO (reg
);
328 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
330 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
332 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
333 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
336 /* More than one reaching definition. */
340 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
350 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
352 static enum iv_grd_result
353 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
356 basic_block def_bb
, use_bb
;
361 if (!simple_reg_p (reg
))
363 if (GET_CODE (reg
) == SUBREG
)
364 reg
= SUBREG_REG (reg
);
365 gcc_assert (REG_P (reg
));
367 use
= df_find_use (insn
, reg
);
368 gcc_assert (use
!= NULL
);
370 if (!DF_REF_CHAIN (use
))
371 return GRD_INVARIANT
;
373 /* More than one reaching def. */
374 if (DF_REF_CHAIN (use
)->next
)
377 adef
= DF_REF_CHAIN (use
)->ref
;
379 /* We do not handle setting only part of the register. */
380 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
383 def_insn
= DF_REF_INSN (adef
);
384 def_bb
= DF_REF_BB (adef
);
385 use_bb
= BLOCK_FOR_INSN (insn
);
387 if (use_bb
== def_bb
)
388 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
390 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
395 return GRD_SINGLE_DOM
;
398 /* The definition does not dominate the use. This is still OK if
399 this may be a use of a biv, i.e. if the def_bb dominates loop
401 if (just_once_each_iteration_p (current_loop
, def_bb
))
402 return GRD_MAYBE_BIV
;
407 /* Sets IV to invariant CST in MODE. Always returns true (just for
408 consistency with other iv manipulation functions that may fail). */
411 iv_constant (struct rtx_iv
*iv
, rtx cst
, machine_mode mode
)
413 if (mode
== VOIDmode
)
414 mode
= GET_MODE (cst
);
418 iv
->step
= const0_rtx
;
419 iv
->first_special
= false;
420 iv
->extend
= IV_UNKNOWN_EXTEND
;
421 iv
->extend_mode
= iv
->mode
;
422 iv
->delta
= const0_rtx
;
423 iv
->mult
= const1_rtx
;
428 /* Evaluates application of subreg to MODE on IV. */
431 iv_subreg (struct rtx_iv
*iv
, machine_mode mode
)
433 /* If iv is invariant, just calculate the new value. */
434 if (iv
->step
== const0_rtx
435 && !iv
->first_special
)
437 rtx val
= get_iv_value (iv
, const0_rtx
);
438 val
= lowpart_subreg (mode
, val
,
439 iv
->extend
== IV_UNKNOWN_EXTEND
440 ? iv
->mode
: iv
->extend_mode
);
443 iv
->extend
= IV_UNKNOWN_EXTEND
;
444 iv
->mode
= iv
->extend_mode
= mode
;
445 iv
->delta
= const0_rtx
;
446 iv
->mult
= const1_rtx
;
450 if (iv
->extend_mode
== mode
)
453 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
456 iv
->extend
= IV_UNKNOWN_EXTEND
;
459 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
460 simplify_gen_binary (MULT
, iv
->extend_mode
,
461 iv
->base
, iv
->mult
));
462 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
463 iv
->mult
= const1_rtx
;
464 iv
->delta
= const0_rtx
;
465 iv
->first_special
= false;
470 /* Evaluates application of EXTEND to MODE on IV. */
473 iv_extend (struct rtx_iv
*iv
, enum iv_extend_code extend
, machine_mode mode
)
475 /* If iv is invariant, just calculate the new value. */
476 if (iv
->step
== const0_rtx
477 && !iv
->first_special
)
479 rtx val
= get_iv_value (iv
, const0_rtx
);
480 if (iv
->extend_mode
!= iv
->mode
481 && iv
->extend
!= IV_UNKNOWN_EXTEND
482 && iv
->extend
!= extend
)
483 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
484 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
487 ? iv
->extend_mode
: iv
->mode
);
489 iv
->extend
= IV_UNKNOWN_EXTEND
;
490 iv
->mode
= iv
->extend_mode
= mode
;
491 iv
->delta
= const0_rtx
;
492 iv
->mult
= const1_rtx
;
496 if (mode
!= iv
->extend_mode
)
499 if (iv
->extend
!= IV_UNKNOWN_EXTEND
500 && iv
->extend
!= extend
)
508 /* Evaluates negation of IV. */
511 iv_neg (struct rtx_iv
*iv
)
513 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
515 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
516 iv
->base
, iv
->extend_mode
);
517 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
518 iv
->step
, iv
->extend_mode
);
522 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
523 iv
->delta
, iv
->extend_mode
);
524 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
525 iv
->mult
, iv
->extend_mode
);
531 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
534 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
539 /* Extend the constant to extend_mode of the other operand if necessary. */
540 if (iv0
->extend
== IV_UNKNOWN_EXTEND
541 && iv0
->mode
== iv0
->extend_mode
542 && iv0
->step
== const0_rtx
543 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
545 iv0
->extend_mode
= iv1
->extend_mode
;
546 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
547 iv0
->base
, iv0
->mode
);
549 if (iv1
->extend
== IV_UNKNOWN_EXTEND
550 && iv1
->mode
== iv1
->extend_mode
551 && iv1
->step
== const0_rtx
552 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
554 iv1
->extend_mode
= iv0
->extend_mode
;
555 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
556 iv1
->base
, iv1
->mode
);
559 mode
= iv0
->extend_mode
;
560 if (mode
!= iv1
->extend_mode
)
563 if (iv0
->extend
== IV_UNKNOWN_EXTEND
564 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
566 if (iv0
->mode
!= iv1
->mode
)
569 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
570 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
575 /* Handle addition of constant. */
576 if (iv1
->extend
== IV_UNKNOWN_EXTEND
578 && iv1
->step
== const0_rtx
)
580 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
584 if (iv0
->extend
== IV_UNKNOWN_EXTEND
586 && iv0
->step
== const0_rtx
)
594 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
601 /* Evaluates multiplication of IV by constant CST. */
604 iv_mult (struct rtx_iv
*iv
, rtx mby
)
606 machine_mode mode
= iv
->extend_mode
;
608 if (GET_MODE (mby
) != VOIDmode
609 && GET_MODE (mby
) != mode
)
612 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
614 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
615 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
619 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
620 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
626 /* Evaluates shift of IV by constant CST. */
629 iv_shift (struct rtx_iv
*iv
, rtx mby
)
631 machine_mode mode
= iv
->extend_mode
;
633 if (GET_MODE (mby
) != VOIDmode
634 && GET_MODE (mby
) != mode
)
637 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
639 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
640 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
644 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
645 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
651 /* The recursive part of get_biv_step. Gets the value of the single value
652 defined by DEF wrto initial value of REG inside loop, in shape described
656 get_biv_step_1 (df_ref def
, rtx reg
,
657 rtx
*inner_step
, machine_mode
*inner_mode
,
658 enum iv_extend_code
*extend
, machine_mode outer_mode
,
661 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
662 rtx next
, nextr
, tmp
;
664 rtx_insn
*insn
= DF_REF_INSN (def
);
666 enum iv_grd_result res
;
668 set
= single_set (insn
);
672 rhs
= find_reg_equal_equiv_note (insn
);
678 code
= GET_CODE (rhs
);
691 if (code
== PLUS
&& CONSTANT_P (op0
))
693 tmp
= op0
; op0
= op1
; op1
= tmp
;
696 if (!simple_reg_p (op0
)
697 || !CONSTANT_P (op1
))
700 if (GET_MODE (rhs
) != outer_mode
)
702 /* ppc64 uses expressions like
704 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
706 this is equivalent to
708 (set x':DI (plus:DI y:DI 1))
709 (set x:SI (subreg:SI (x':DI)). */
710 if (GET_CODE (op0
) != SUBREG
)
712 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
721 if (GET_MODE (rhs
) != outer_mode
)
725 if (!simple_reg_p (op0
))
735 if (GET_CODE (next
) == SUBREG
)
737 if (!subreg_lowpart_p (next
))
740 nextr
= SUBREG_REG (next
);
741 if (GET_MODE (nextr
) != outer_mode
)
747 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
749 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
752 if (res
== GRD_MAYBE_BIV
)
754 if (!rtx_equal_p (nextr
, reg
))
757 *inner_step
= const0_rtx
;
758 *extend
= IV_UNKNOWN_EXTEND
;
759 *inner_mode
= outer_mode
;
760 *outer_step
= const0_rtx
;
762 else if (!get_biv_step_1 (next_def
, reg
,
763 inner_step
, inner_mode
, extend
, outer_mode
,
767 if (GET_CODE (next
) == SUBREG
)
769 machine_mode amode
= GET_MODE (next
);
771 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
775 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
776 *inner_step
, *outer_step
);
777 *outer_step
= const0_rtx
;
778 *extend
= IV_UNKNOWN_EXTEND
;
789 if (*inner_mode
== outer_mode
790 /* See comment in previous switch. */
791 || GET_MODE (rhs
) != outer_mode
)
792 *inner_step
= simplify_gen_binary (code
, outer_mode
,
795 *outer_step
= simplify_gen_binary (code
, outer_mode
,
801 gcc_assert (GET_MODE (op0
) == *inner_mode
802 && *extend
== IV_UNKNOWN_EXTEND
803 && *outer_step
== const0_rtx
);
805 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
815 /* Gets the operation on register REG inside loop, in shape
817 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
819 If the operation cannot be described in this shape, return false.
820 LAST_DEF is the definition of REG that dominates loop latch. */
823 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
824 machine_mode
*inner_mode
, enum iv_extend_code
*extend
,
825 machine_mode
*outer_mode
, rtx
*outer_step
)
827 *outer_mode
= GET_MODE (reg
);
829 if (!get_biv_step_1 (last_def
, reg
,
830 inner_step
, inner_mode
, extend
, *outer_mode
,
834 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
835 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
840 /* Records information that DEF is induction variable IV. */
843 record_iv (df_ref def
, struct rtx_iv
*iv
)
845 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
848 check_iv_ref_table_size ();
849 DF_REF_IV_SET (def
, recorded_iv
);
852 /* If DEF was already analyzed for bivness, store the description of the biv to
853 IV and return true. Otherwise return false. */
856 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
858 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
868 record_biv (rtx def
, struct rtx_iv
*iv
)
870 struct biv_entry
*biv
= XNEW (struct biv_entry
);
871 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
873 biv
->regno
= REGNO (def
);
879 /* Determines whether DEF is a biv and if so, stores its description
883 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
885 rtx inner_step
, outer_step
;
886 machine_mode inner_mode
, outer_mode
;
887 enum iv_extend_code extend
;
892 fprintf (dump_file
, "Analyzing ");
893 print_rtl (dump_file
, def
);
894 fprintf (dump_file
, " for bivness.\n");
899 if (!CONSTANT_P (def
))
902 return iv_constant (iv
, def
, VOIDmode
);
905 if (!latch_dominating_def (def
, &last_def
))
908 fprintf (dump_file
, " not simple.\n");
913 return iv_constant (iv
, def
, VOIDmode
);
915 if (analyzed_for_bivness_p (def
, iv
))
918 fprintf (dump_file
, " already analysed.\n");
919 return iv
->base
!= NULL_RTX
;
922 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
923 &outer_mode
, &outer_step
))
929 /* Loop transforms base to es (base + inner_step) + outer_step,
930 where es means extend of subreg between inner_mode and outer_mode.
931 The corresponding induction variable is
933 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
935 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
936 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
937 iv
->mode
= inner_mode
;
938 iv
->extend_mode
= outer_mode
;
940 iv
->mult
= const1_rtx
;
941 iv
->delta
= outer_step
;
942 iv
->first_special
= inner_mode
!= outer_mode
;
947 fprintf (dump_file
, " ");
948 dump_iv_info (dump_file
, iv
);
949 fprintf (dump_file
, "\n");
952 record_biv (def
, iv
);
953 return iv
->base
!= NULL_RTX
;
956 /* Analyzes expression RHS used at INSN and stores the result to *IV.
957 The mode of the induction variable is MODE. */
960 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, machine_mode mode
,
963 rtx mby
= NULL_RTX
, tmp
;
964 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
965 struct rtx_iv iv0
, iv1
;
966 enum rtx_code code
= GET_CODE (rhs
);
967 machine_mode omode
= mode
;
973 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
979 if (!iv_analyze_op (insn
, rhs
, iv
))
982 if (iv
->mode
== VOIDmode
)
985 iv
->extend_mode
= mode
;
1000 op0
= XEXP (rhs
, 0);
1001 omode
= GET_MODE (op0
);
1006 op0
= XEXP (rhs
, 0);
1007 op1
= XEXP (rhs
, 1);
1011 op0
= XEXP (rhs
, 0);
1012 mby
= XEXP (rhs
, 1);
1013 if (!CONSTANT_P (mby
))
1019 if (!CONSTANT_P (mby
))
1024 op0
= XEXP (rhs
, 0);
1025 mby
= XEXP (rhs
, 1);
1026 if (!CONSTANT_P (mby
))
1035 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1039 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1045 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1050 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1061 if (!iv_add (&iv0
, &iv1
, code
))
1066 if (!iv_mult (&iv0
, mby
))
1071 if (!iv_shift (&iv0
, mby
))
1080 return iv
->base
!= NULL_RTX
;
1083 /* Analyzes iv DEF and stores the result to *IV. */
1086 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1088 rtx_insn
*insn
= DF_REF_INSN (def
);
1089 rtx reg
= DF_REF_REG (def
);
1094 fprintf (dump_file
, "Analyzing def of ");
1095 print_rtl (dump_file
, reg
);
1096 fprintf (dump_file
, " in insn ");
1097 print_rtl_single (dump_file
, insn
);
1100 check_iv_ref_table_size ();
1101 if (DF_REF_IV (def
))
1104 fprintf (dump_file
, " already analysed.\n");
1105 *iv
= *DF_REF_IV (def
);
1106 return iv
->base
!= NULL_RTX
;
1109 iv
->mode
= VOIDmode
;
1110 iv
->base
= NULL_RTX
;
1111 iv
->step
= NULL_RTX
;
1116 set
= single_set (insn
);
1120 if (!REG_P (SET_DEST (set
)))
1123 gcc_assert (SET_DEST (set
) == reg
);
1124 rhs
= find_reg_equal_equiv_note (insn
);
1126 rhs
= XEXP (rhs
, 0);
1128 rhs
= SET_SRC (set
);
1130 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1131 record_iv (def
, iv
);
1135 print_rtl (dump_file
, reg
);
1136 fprintf (dump_file
, " in insn ");
1137 print_rtl_single (dump_file
, insn
);
1138 fprintf (dump_file
, " is ");
1139 dump_iv_info (dump_file
, iv
);
1140 fprintf (dump_file
, "\n");
1143 return iv
->base
!= NULL_RTX
;
1146 /* Analyzes operand OP of INSN and stores the result to *IV. */
1149 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1152 enum iv_grd_result res
;
1156 fprintf (dump_file
, "Analyzing operand ");
1157 print_rtl (dump_file
, op
);
1158 fprintf (dump_file
, " of insn ");
1159 print_rtl_single (dump_file
, insn
);
1162 if (function_invariant_p (op
))
1163 res
= GRD_INVARIANT
;
1164 else if (GET_CODE (op
) == SUBREG
)
1166 if (!subreg_lowpart_p (op
))
1169 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1172 return iv_subreg (iv
, GET_MODE (op
));
1176 res
= iv_get_reaching_def (insn
, op
, &def
);
1177 if (res
== GRD_INVALID
)
1180 fprintf (dump_file
, " not simple.\n");
1185 if (res
== GRD_INVARIANT
)
1187 iv_constant (iv
, op
, VOIDmode
);
1191 fprintf (dump_file
, " ");
1192 dump_iv_info (dump_file
, iv
);
1193 fprintf (dump_file
, "\n");
1198 if (res
== GRD_MAYBE_BIV
)
1199 return iv_analyze_biv (op
, iv
);
1201 return iv_analyze_def (def
, iv
);
1204 /* Analyzes value VAL at INSN and stores the result to *IV. */
1207 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1211 /* We must find the insn in that val is used, so that we get to UD chains.
1212 Since the function is sometimes called on result of get_condition,
1213 this does not necessarily have to be directly INSN; scan also the
1215 if (simple_reg_p (val
))
1217 if (GET_CODE (val
) == SUBREG
)
1218 reg
= SUBREG_REG (val
);
1222 while (!df_find_use (insn
, reg
))
1223 insn
= NEXT_INSN (insn
);
1226 return iv_analyze_op (insn
, val
, iv
);
1229 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1232 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1236 adef
= df_find_def (insn
, def
);
1240 return iv_analyze_def (adef
, iv
);
1243 /* Checks whether definition of register REG in INSN is a basic induction
1244 variable. IV analysis must have been initialized (via a call to
1245 iv_analysis_loop_init) for this function to produce a result. */
1248 biv_p (rtx_insn
*insn
, rtx reg
)
1251 df_ref def
, last_def
;
1253 if (!simple_reg_p (reg
))
1256 def
= df_find_def (insn
, reg
);
1257 gcc_assert (def
!= NULL
);
1258 if (!latch_dominating_def (reg
, &last_def
))
1260 if (last_def
!= def
)
1263 if (!iv_analyze_biv (reg
, &iv
))
1266 return iv
.step
!= const0_rtx
;
1269 /* Calculates value of IV at ITERATION-th iteration. */
1272 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1276 /* We would need to generate some if_then_else patterns, and so far
1277 it is not needed anywhere. */
1278 gcc_assert (!iv
->first_special
);
1280 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1281 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1282 simplify_gen_binary (MULT
, iv
->extend_mode
,
1283 iv
->step
, iteration
));
1287 if (iv
->extend_mode
== iv
->mode
)
1290 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1292 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1295 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1296 iv
->extend_mode
, val
, iv
->mode
);
1297 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1298 simplify_gen_binary (MULT
, iv
->extend_mode
,
1304 /* Free the data for an induction variable analysis. */
1307 iv_analysis_done (void)
1313 df_finish_pass (true);
1316 free (iv_ref_table
);
1317 iv_ref_table
= NULL
;
1318 iv_ref_table_size
= 0;
1322 /* Computes inverse to X modulo (1 << MOD). */
1325 inverse (uint64_t x
, int mod
)
1328 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1332 for (i
= 0; i
< mod
- 1; i
++)
1334 rslt
= (rslt
* x
) & mask
;
1341 /* Checks whether any register in X is in set ALT. */
1344 altered_reg_used (const_rtx x
, bitmap alt
)
1346 subrtx_iterator::array_type array
;
1347 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
1349 const_rtx x
= *iter
;
1350 if (REG_P (x
) && REGNO_REG_SET_P (alt
, REGNO (x
)))
1356 /* Marks registers altered by EXPR in set ALT. */
1359 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1361 if (GET_CODE (expr
) == SUBREG
)
1362 expr
= SUBREG_REG (expr
);
1366 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1369 /* Checks whether RHS is simple enough to process. */
1372 simple_rhs_p (rtx rhs
)
1376 if (function_invariant_p (rhs
)
1377 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1380 switch (GET_CODE (rhs
))
1385 op0
= XEXP (rhs
, 0);
1386 op1
= XEXP (rhs
, 1);
1387 /* Allow reg OP const and reg OP reg. */
1388 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1389 && !function_invariant_p (op0
))
1391 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1392 && !function_invariant_p (op1
))
1401 op0
= XEXP (rhs
, 0);
1402 op1
= XEXP (rhs
, 1);
1403 /* Allow reg OP const. */
1404 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1406 if (!function_invariant_p (op1
))
1416 /* If REGNO has a single definition, return its known value, otherwise return
1420 find_single_def_src (unsigned int regno
)
1428 adef
= DF_REG_DEF_CHAIN (regno
);
1429 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1430 || DF_REF_IS_ARTIFICIAL (adef
))
1433 set
= single_set (DF_REF_INSN (adef
));
1434 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1435 || REGNO (SET_DEST (set
)) != regno
)
1438 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1440 if (note
&& function_invariant_p (XEXP (note
, 0)))
1442 src
= XEXP (note
, 0);
1445 src
= SET_SRC (set
);
1449 regno
= REGNO (src
);
1454 if (!function_invariant_p (src
))
1460 /* If any registers in *EXPR that have a single definition, try to replace
1461 them with the known-equivalent values. */
1464 replace_single_def_regs (rtx
*expr
)
1466 subrtx_var_iterator::array_type array
;
1468 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1472 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1474 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1480 /* A subroutine of simplify_using_initial_values, this function examines INSN
1481 to see if it contains a suitable set that we can use to make a replacement.
1482 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1483 the set; return false otherwise. */
1486 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1488 rtx set
= single_set (insn
);
1489 rtx lhs
= NULL_RTX
, rhs
;
1494 lhs
= SET_DEST (set
);
1498 rhs
= find_reg_equal_equiv_note (insn
);
1500 rhs
= XEXP (rhs
, 0);
1502 rhs
= SET_SRC (set
);
1504 if (!simple_rhs_p (rhs
))
1512 /* Using the data returned by suitable_set_for_replacement, replace DEST
1513 with SRC in *EXPR and return the new expression. Also call
1514 replace_single_def_regs if the replacement changed something. */
1516 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1519 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1522 replace_single_def_regs (expr
);
1525 /* Checks whether A implies B. */
1528 implies_p (rtx a
, rtx b
)
1530 rtx op0
, op1
, opb0
, opb1
, r
;
1533 if (rtx_equal_p (a
, b
))
1536 if (GET_CODE (a
) == EQ
)
1542 || (GET_CODE (op0
) == SUBREG
1543 && REG_P (SUBREG_REG (op0
))))
1545 r
= simplify_replace_rtx (b
, op0
, op1
);
1546 if (r
== const_true_rtx
)
1551 || (GET_CODE (op1
) == SUBREG
1552 && REG_P (SUBREG_REG (op1
))))
1554 r
= simplify_replace_rtx (b
, op1
, op0
);
1555 if (r
== const_true_rtx
)
1560 if (b
== const_true_rtx
)
1563 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1564 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1565 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1566 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1574 mode
= GET_MODE (op0
);
1575 if (mode
!= GET_MODE (opb0
))
1577 else if (mode
== VOIDmode
)
1579 mode
= GET_MODE (op1
);
1580 if (mode
!= GET_MODE (opb1
))
1584 /* A < B implies A + 1 <= B. */
1585 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1586 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1589 if (GET_CODE (a
) == GT
)
1596 if (GET_CODE (b
) == GE
)
1603 if (SCALAR_INT_MODE_P (mode
)
1604 && rtx_equal_p (op1
, opb1
)
1605 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1610 /* A < B or A > B imply A != B. TODO: Likewise
1611 A + n < B implies A != B + n if neither wraps. */
1612 if (GET_CODE (b
) == NE
1613 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1614 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1616 if (rtx_equal_p (op0
, opb0
)
1617 && rtx_equal_p (op1
, opb1
))
1621 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1622 if (GET_CODE (a
) == NE
1623 && op1
== const0_rtx
)
1625 if ((GET_CODE (b
) == GTU
1626 && opb1
== const0_rtx
)
1627 || (GET_CODE (b
) == GEU
1628 && opb1
== const1_rtx
))
1629 return rtx_equal_p (op0
, opb0
);
1632 /* A != N is equivalent to A - (N + 1) <u -1. */
1633 if (GET_CODE (a
) == NE
1634 && CONST_INT_P (op1
)
1635 && GET_CODE (b
) == LTU
1636 && opb1
== constm1_rtx
1637 && GET_CODE (opb0
) == PLUS
1638 && CONST_INT_P (XEXP (opb0
, 1))
1639 /* Avoid overflows. */
1640 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1641 != ((unsigned HOST_WIDE_INT
)1
1642 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1643 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1644 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1646 /* Likewise, A != N implies A - N > 0. */
1647 if (GET_CODE (a
) == NE
1648 && CONST_INT_P (op1
))
1650 if (GET_CODE (b
) == GTU
1651 && GET_CODE (opb0
) == PLUS
1652 && opb1
== const0_rtx
1653 && CONST_INT_P (XEXP (opb0
, 1))
1654 /* Avoid overflows. */
1655 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1656 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1657 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1658 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1659 if (GET_CODE (b
) == GEU
1660 && GET_CODE (opb0
) == PLUS
1661 && opb1
== const1_rtx
1662 && CONST_INT_P (XEXP (opb0
, 1))
1663 /* Avoid overflows. */
1664 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1665 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1666 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1667 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1670 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1671 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1672 && CONST_INT_P (op1
)
1673 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1674 || INTVAL (op1
) >= 0)
1675 && GET_CODE (b
) == LTU
1676 && CONST_INT_P (opb1
)
1677 && rtx_equal_p (op0
, opb0
))
1678 return INTVAL (opb1
) < 0;
1683 /* Canonicalizes COND so that
1685 (1) Ensure that operands are ordered according to
1686 swap_commutative_operands_p.
1687 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1688 for GE, GEU, and LEU. */
1691 canon_condition (rtx cond
)
1698 code
= GET_CODE (cond
);
1699 op0
= XEXP (cond
, 0);
1700 op1
= XEXP (cond
, 1);
1702 if (swap_commutative_operands_p (op0
, op1
))
1704 code
= swap_condition (code
);
1710 mode
= GET_MODE (op0
);
1711 if (mode
== VOIDmode
)
1712 mode
= GET_MODE (op1
);
1713 gcc_assert (mode
!= VOIDmode
);
1715 if (CONST_INT_P (op1
)
1716 && GET_MODE_CLASS (mode
) != MODE_CC
1717 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1719 HOST_WIDE_INT const_val
= INTVAL (op1
);
1720 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1721 unsigned HOST_WIDE_INT max_val
1722 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1727 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1728 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1731 /* When cross-compiling, const_val might be sign-extended from
1732 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1734 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1735 != (((HOST_WIDE_INT
) 1
1736 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1737 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1741 if (uconst_val
< max_val
)
1742 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1746 if (uconst_val
!= 0)
1747 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1755 if (op0
!= XEXP (cond
, 0)
1756 || op1
!= XEXP (cond
, 1)
1757 || code
!= GET_CODE (cond
)
1758 || GET_MODE (cond
) != SImode
)
1759 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1764 /* Reverses CONDition; returns NULL if we cannot. */
1767 reversed_condition (rtx cond
)
1769 enum rtx_code reversed
;
1770 reversed
= reversed_comparison_code (cond
, NULL
);
1771 if (reversed
== UNKNOWN
)
1774 return gen_rtx_fmt_ee (reversed
,
1775 GET_MODE (cond
), XEXP (cond
, 0),
1779 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1780 set of altered regs. */
1783 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1785 rtx rev
, reve
, exp
= *expr
;
1787 /* If some register gets altered later, we do not really speak about its
1788 value at the time of comparison. */
1789 if (altered
&& altered_reg_used (cond
, altered
))
1792 if (GET_CODE (cond
) == EQ
1793 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1795 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1799 if (!COMPARISON_P (exp
))
1802 rev
= reversed_condition (cond
);
1803 reve
= reversed_condition (exp
);
1805 cond
= canon_condition (cond
);
1806 exp
= canon_condition (exp
);
1808 rev
= canon_condition (rev
);
1810 reve
= canon_condition (reve
);
1812 if (rtx_equal_p (exp
, cond
))
1814 *expr
= const_true_rtx
;
1818 if (rev
&& rtx_equal_p (exp
, rev
))
1824 if (implies_p (cond
, exp
))
1826 *expr
= const_true_rtx
;
1830 if (reve
&& implies_p (cond
, reve
))
1836 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1838 if (rev
&& implies_p (exp
, rev
))
1844 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1845 if (rev
&& reve
&& implies_p (reve
, rev
))
1847 *expr
= const_true_rtx
;
1851 /* We would like to have some other tests here. TODO. */
1856 /* Use relationship between A and *B to eventually eliminate *B.
1857 OP is the operation we consider. */
1860 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1865 /* If A implies *B, we may replace *B by true. */
1866 if (implies_p (a
, *b
))
1867 *b
= const_true_rtx
;
1871 /* If *B implies A, we may replace *B by false. */
1872 if (implies_p (*b
, a
))
1881 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1882 operation we consider. */
1885 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1889 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1890 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1891 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1892 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1895 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1896 is a list, its elements are assumed to be combined using OP. */
1899 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1901 bool expression_valid
;
1902 rtx head
, tail
, last_valid_expr
;
1903 rtx_expr_list
*cond_list
;
1906 regset altered
, this_altered
;
1912 if (CONSTANT_P (*expr
))
1915 if (GET_CODE (*expr
) == EXPR_LIST
)
1917 head
= XEXP (*expr
, 0);
1918 tail
= XEXP (*expr
, 1);
1920 eliminate_implied_conditions (op
, &head
, tail
);
1925 neutral
= const_true_rtx
;
1930 neutral
= const0_rtx
;
1931 aggr
= const_true_rtx
;
1938 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1941 XEXP (*expr
, 0) = aggr
;
1942 XEXP (*expr
, 1) = NULL_RTX
;
1945 else if (head
== neutral
)
1948 simplify_using_initial_values (loop
, op
, expr
);
1951 simplify_using_initial_values (loop
, op
, &tail
);
1953 if (tail
&& XEXP (tail
, 0) == aggr
)
1959 XEXP (*expr
, 0) = head
;
1960 XEXP (*expr
, 1) = tail
;
1964 gcc_assert (op
== UNKNOWN
);
1966 replace_single_def_regs (expr
);
1967 if (CONSTANT_P (*expr
))
1970 e
= loop_preheader_edge (loop
);
1971 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1974 altered
= ALLOC_REG_SET (®_obstack
);
1975 this_altered
= ALLOC_REG_SET (®_obstack
);
1977 expression_valid
= true;
1978 last_valid_expr
= *expr
;
1982 insn
= BB_END (e
->src
);
1983 if (any_condjump_p (insn
))
1985 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1987 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1988 cond
= reversed_condition (cond
);
1992 simplify_using_condition (cond
, expr
, altered
);
1996 if (CONSTANT_P (*expr
))
1998 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
2000 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2001 if (CONSTANT_P (*expr
))
2005 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
2009 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
2017 CLEAR_REG_SET (this_altered
);
2018 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
2021 /* Kill all call clobbered registers. */
2023 hard_reg_set_iterator hrsi
;
2024 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2026 SET_REGNO_REG_SET (this_altered
, i
);
2029 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2031 rtx_expr_list
**pnote
, **pnote_next
;
2033 replace_in_expr (expr
, dest
, src
);
2034 if (CONSTANT_P (*expr
))
2037 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2040 rtx old_cond
= XEXP (note
, 0);
2042 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2043 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2045 /* We can no longer use a condition that has been simplified
2046 to a constant, and simplify_using_condition will abort if
2048 if (CONSTANT_P (XEXP (note
, 0)))
2050 *pnote
= *pnote_next
;
2052 free_EXPR_LIST_node (note
);
2054 /* Retry simplifications with this condition if either the
2055 expression or the condition changed. */
2056 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2057 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2062 rtx_expr_list
**pnote
, **pnote_next
;
2064 /* If we did not use this insn to make a replacement, any overlap
2065 between stores in this insn and our expression will cause the
2066 expression to become invalid. */
2067 if (altered_reg_used (*expr
, this_altered
))
2070 /* Likewise for the conditions. */
2071 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2074 rtx old_cond
= XEXP (note
, 0);
2076 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2077 if (altered_reg_used (old_cond
, this_altered
))
2079 *pnote
= *pnote_next
;
2081 free_EXPR_LIST_node (note
);
2086 if (CONSTANT_P (*expr
))
2089 IOR_REG_SET (altered
, this_altered
);
2091 /* If the expression now contains regs that have been altered, we
2092 can't return it to the caller. However, it is still valid for
2093 further simplification, so keep searching to see if we can
2094 eventually turn it into a constant. */
2095 if (altered_reg_used (*expr
, altered
))
2096 expression_valid
= false;
2097 if (expression_valid
)
2098 last_valid_expr
= *expr
;
2101 if (!single_pred_p (e
->src
)
2102 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2104 e
= single_pred_edge (e
->src
);
2108 free_EXPR_LIST_list (&cond_list
);
2109 if (!CONSTANT_P (*expr
))
2110 *expr
= last_valid_expr
;
2111 FREE_REG_SET (altered
);
2112 FREE_REG_SET (this_altered
);
2115 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2116 that IV occurs as left operands of comparison COND and its signedness
2117 is SIGNED_P to DESC. */
2120 shorten_into_mode (struct rtx_iv
*iv
, machine_mode mode
,
2121 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2123 rtx mmin
, mmax
, cond_over
, cond_under
;
2125 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2126 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2128 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2137 if (cond_under
!= const0_rtx
)
2139 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2140 if (cond_over
!= const0_rtx
)
2141 desc
->noloop_assumptions
=
2142 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2149 if (cond_over
!= const0_rtx
)
2151 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2152 if (cond_under
!= const0_rtx
)
2153 desc
->noloop_assumptions
=
2154 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2158 if (cond_over
!= const0_rtx
)
2160 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2161 if (cond_under
!= const0_rtx
)
2163 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2171 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2174 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2175 subregs of the same mode if possible (sometimes it is necessary to add
2176 some assumptions to DESC). */
2179 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2180 enum rtx_code cond
, struct niter_desc
*desc
)
2182 machine_mode comp_mode
;
2185 /* If the ivs behave specially in the first iteration, or are
2186 added/multiplied after extending, we ignore them. */
2187 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2189 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2192 /* If there is some extend, it must match signedness of the comparison. */
2197 if (iv0
->extend
== IV_ZERO_EXTEND
2198 || iv1
->extend
== IV_ZERO_EXTEND
)
2205 if (iv0
->extend
== IV_SIGN_EXTEND
2206 || iv1
->extend
== IV_SIGN_EXTEND
)
2212 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2213 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2214 && iv0
->extend
!= iv1
->extend
)
2218 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2219 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2220 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2221 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2228 /* Values of both variables should be computed in the same mode. These
2229 might indeed be different, if we have comparison like
2231 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2233 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2234 in different modes. This does not seem impossible to handle, but
2235 it hardly ever occurs in practice.
2237 The only exception is the case when one of operands is invariant.
2238 For example pentium 3 generates comparisons like
2239 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2240 definitely do not want this prevent the optimization. */
2241 comp_mode
= iv0
->extend_mode
;
2242 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2243 comp_mode
= iv1
->extend_mode
;
2245 if (iv0
->extend_mode
!= comp_mode
)
2247 if (iv0
->mode
!= iv0
->extend_mode
2248 || iv0
->step
!= const0_rtx
)
2251 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2252 comp_mode
, iv0
->base
, iv0
->mode
);
2253 iv0
->extend_mode
= comp_mode
;
2256 if (iv1
->extend_mode
!= comp_mode
)
2258 if (iv1
->mode
!= iv1
->extend_mode
2259 || iv1
->step
!= const0_rtx
)
2262 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2263 comp_mode
, iv1
->base
, iv1
->mode
);
2264 iv1
->extend_mode
= comp_mode
;
2267 /* Check that both ivs belong to a range of a single mode. If one of the
2268 operands is an invariant, we may need to shorten it into the common
2270 if (iv0
->mode
== iv0
->extend_mode
2271 && iv0
->step
== const0_rtx
2272 && iv0
->mode
!= iv1
->mode
)
2273 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2275 if (iv1
->mode
== iv1
->extend_mode
2276 && iv1
->step
== const0_rtx
2277 && iv0
->mode
!= iv1
->mode
)
2278 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2280 if (iv0
->mode
!= iv1
->mode
)
2283 desc
->mode
= iv0
->mode
;
2284 desc
->signed_p
= signed_p
;
2289 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2290 result. This function is called from iv_number_of_iterations with
2291 a number of fields in DESC already filled in. OLD_NITER is the original
2292 expression for the number of iterations, before we tried to simplify it. */
2295 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2297 rtx niter
= desc
->niter_expr
;
2298 rtx mmin
, mmax
, cmp
;
2300 uint64_t andmax
= 0;
2302 /* We used to look for constant operand 0 of AND,
2303 but canonicalization should always make this impossible. */
2304 gcc_checking_assert (GET_CODE (niter
) != AND
2305 || !CONST_INT_P (XEXP (niter
, 0)));
2307 if (GET_CODE (niter
) == AND
2308 && CONST_INT_P (XEXP (niter
, 1)))
2310 andmax
= UINTVAL (XEXP (niter
, 1));
2311 niter
= XEXP (niter
, 0);
2314 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2315 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2317 if (GET_CODE (niter
) == UDIV
)
2319 if (!CONST_INT_P (XEXP (niter
, 1)))
2321 inc
= INTVAL (XEXP (niter
, 1));
2322 niter
= XEXP (niter
, 0);
2327 /* We could use a binary search here, but for now improving the upper
2328 bound by just one eliminates one important corner case. */
2329 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2330 desc
->mode
, old_niter
, mmax
);
2331 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2332 if (cmp
== const_true_rtx
)
2337 fprintf (dump_file
, ";; improved upper bound by one.\n");
2341 nmax
= MIN (nmax
, andmax
);
2343 fprintf (dump_file
, ";; Determined upper bound %"PRId64
".\n",
2348 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2349 the result into DESC. Very similar to determine_number_of_iterations
2350 (basically its rtl version), complicated by things like subregs. */
2353 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2354 struct niter_desc
*desc
)
2356 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2357 struct rtx_iv iv0
, iv1
, tmp_iv
;
2358 rtx assumption
, may_not_xform
;
2360 machine_mode mode
, comp_mode
;
2361 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2362 uint64_t s
, size
, d
, inv
, max
;
2363 int64_t up
, down
, inc
, step_val
;
2364 int was_sharp
= false;
2368 /* The meaning of these assumptions is this:
2370 then the rest of information does not have to be valid
2371 if noloop_assumptions then the loop does not roll
2372 if infinite then this exit is never used */
2374 desc
->assumptions
= NULL_RTX
;
2375 desc
->noloop_assumptions
= NULL_RTX
;
2376 desc
->infinite
= NULL_RTX
;
2377 desc
->simple_p
= true;
2379 desc
->const_iter
= false;
2380 desc
->niter_expr
= NULL_RTX
;
2382 cond
= GET_CODE (condition
);
2383 gcc_assert (COMPARISON_P (condition
));
2385 mode
= GET_MODE (XEXP (condition
, 0));
2386 if (mode
== VOIDmode
)
2387 mode
= GET_MODE (XEXP (condition
, 1));
2388 /* The constant comparisons should be folded. */
2389 gcc_assert (mode
!= VOIDmode
);
2391 /* We only handle integers or pointers. */
2392 if (GET_MODE_CLASS (mode
) != MODE_INT
2393 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2396 op0
= XEXP (condition
, 0);
2397 if (!iv_analyze (insn
, op0
, &iv0
))
2399 if (iv0
.extend_mode
== VOIDmode
)
2400 iv0
.mode
= iv0
.extend_mode
= mode
;
2402 op1
= XEXP (condition
, 1);
2403 if (!iv_analyze (insn
, op1
, &iv1
))
2405 if (iv1
.extend_mode
== VOIDmode
)
2406 iv1
.mode
= iv1
.extend_mode
= mode
;
2408 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2409 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2412 /* Check condition and normalize it. */
2420 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2421 cond
= swap_condition (cond
);
2433 /* Handle extends. This is relatively nontrivial, so we only try in some
2434 easy cases, when we can canonicalize the ivs (possibly by adding some
2435 assumptions) to shape subreg (base + i * step). This function also fills
2436 in desc->mode and desc->signed_p. */
2438 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2441 comp_mode
= iv0
.extend_mode
;
2443 size
= GET_MODE_PRECISION (mode
);
2444 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2445 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2446 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2448 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2451 /* We can take care of the case of two induction variables chasing each other
2452 if the test is NE. I have never seen a loop using it, but still it is
2454 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2459 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2460 iv1
.step
= const0_rtx
;
2463 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2464 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2466 /* This is either infinite loop or the one that ends immediately, depending
2467 on initial values. Unswitching should remove this kind of conditions. */
2468 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2473 if (iv0
.step
== const0_rtx
)
2474 step_val
= -INTVAL (iv1
.step
);
2476 step_val
= INTVAL (iv0
.step
);
2478 /* Ignore loops of while (i-- < 10) type. */
2482 step_is_pow2
= !(step_val
& (step_val
- 1));
2486 /* We do not care about whether the step is power of two in this
2488 step_is_pow2
= false;
2492 /* Some more condition normalization. We must record some assumptions
2493 due to overflows. */
2498 /* We want to take care only of non-sharp relationals; this is easy,
2499 as in cases the overflow would make the transformation unsafe
2500 the loop does not roll. Seemingly it would make more sense to want
2501 to take care of sharp relationals instead, as NE is more similar to
2502 them, but the problem is that here the transformation would be more
2503 difficult due to possibly infinite loops. */
2504 if (iv0
.step
== const0_rtx
)
2506 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2507 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2509 if (assumption
== const_true_rtx
)
2510 goto zero_iter_simplify
;
2511 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2512 iv0
.base
, const1_rtx
);
2516 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2517 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2519 if (assumption
== const_true_rtx
)
2520 goto zero_iter_simplify
;
2521 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2522 iv1
.base
, constm1_rtx
);
2525 if (assumption
!= const0_rtx
)
2526 desc
->noloop_assumptions
=
2527 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2528 cond
= (cond
== LT
) ? LE
: LEU
;
2530 /* It will be useful to be able to tell the difference once more in
2531 LE -> NE reduction. */
2537 /* Take care of trivially infinite loops. */
2540 if (iv0
.step
== const0_rtx
)
2542 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2543 if (rtx_equal_p (tmp
, mode_mmin
))
2546 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2547 /* Fill in the remaining fields somehow. */
2548 goto zero_iter_simplify
;
2553 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2554 if (rtx_equal_p (tmp
, mode_mmax
))
2557 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2558 /* Fill in the remaining fields somehow. */
2559 goto zero_iter_simplify
;
2564 /* If we can we want to take care of NE conditions instead of size
2565 comparisons, as they are much more friendly (most importantly
2566 this takes care of special handling of loops with step 1). We can
2567 do it if we first check that upper bound is greater or equal to
2568 lower bound, their difference is constant c modulo step and that
2569 there is not an overflow. */
2572 if (iv0
.step
== const0_rtx
)
2573 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2576 step
= lowpart_subreg (mode
, step
, comp_mode
);
2577 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2578 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2579 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2580 may_xform
= const0_rtx
;
2581 may_not_xform
= const_true_rtx
;
2583 if (CONST_INT_P (delta
))
2585 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2587 /* A special case. We have transformed condition of type
2588 for (i = 0; i < 4; i += 4)
2590 for (i = 0; i <= 3; i += 4)
2591 obviously if the test for overflow during that transformation
2592 passed, we cannot overflow here. Most importantly any
2593 loop with sharp end condition and step 1 falls into this
2594 category, so handling this case specially is definitely
2595 worth the troubles. */
2596 may_xform
= const_true_rtx
;
2598 else if (iv0
.step
== const0_rtx
)
2600 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2601 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2602 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2603 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2604 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2606 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2612 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2613 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2614 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2615 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2616 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2618 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2624 if (may_xform
!= const0_rtx
)
2626 /* We perform the transformation always provided that it is not
2627 completely senseless. This is OK, as we would need this assumption
2628 to determine the number of iterations anyway. */
2629 if (may_xform
!= const_true_rtx
)
2631 /* If the step is a power of two and the final value we have
2632 computed overflows, the cycle is infinite. Otherwise it
2633 is nontrivial to compute the number of iterations. */
2635 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2638 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2642 /* We are going to lose some information about upper bound on
2643 number of iterations in this step, so record the information
2645 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2646 if (CONST_INT_P (iv1
.base
))
2647 up
= INTVAL (iv1
.base
);
2649 up
= INTVAL (mode_mmax
) - inc
;
2650 down
= INTVAL (CONST_INT_P (iv0
.base
)
2653 max
= (uint64_t) (up
- down
) / inc
+ 1;
2655 && !desc
->assumptions
)
2656 record_niter_bound (loop
, max
, false, true);
2658 if (iv0
.step
== const0_rtx
)
2660 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2661 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2665 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2666 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2669 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2670 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2671 assumption
= simplify_gen_relational (reverse_condition (cond
),
2672 SImode
, mode
, tmp0
, tmp1
);
2673 if (assumption
== const_true_rtx
)
2674 goto zero_iter_simplify
;
2675 else if (assumption
!= const0_rtx
)
2676 desc
->noloop_assumptions
=
2677 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2682 /* Count the number of iterations. */
2685 /* Everything we do here is just arithmetics modulo size of mode. This
2686 makes us able to do more involved computations of number of iterations
2687 than in other cases. First transform the condition into shape
2688 s * i <> c, with s positive. */
2689 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2690 iv0
.base
= const0_rtx
;
2691 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2692 iv1
.step
= const0_rtx
;
2693 if (INTVAL (iv0
.step
) < 0)
2695 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2696 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2698 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2700 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2701 is infinite. Otherwise, the number of iterations is
2702 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2703 s
= INTVAL (iv0
.step
); d
= 1;
2710 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2712 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2713 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2714 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2715 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2717 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2718 inv
= inverse (s
, size
);
2719 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2720 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2724 if (iv1
.step
== const0_rtx
)
2725 /* Condition in shape a + s * i <= b
2726 We must know that b + s does not overflow and a <= b + s and then we
2727 can compute number of iterations as (b + s - a) / s. (It might
2728 seem that we in fact could be more clever about testing the b + s
2729 overflow condition using some information about b - a mod s,
2730 but it was already taken into account during LE -> NE transform). */
2733 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2734 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2736 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2737 lowpart_subreg (mode
, step
,
2743 /* If s is power of 2, we know that the loop is infinite if
2744 a % s <= b % s and b + s overflows. */
2745 assumption
= simplify_gen_relational (reverse_condition (cond
),
2749 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2750 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2751 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2752 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2754 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2758 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2761 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2764 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2765 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2766 assumption
= simplify_gen_relational (reverse_condition (cond
),
2767 SImode
, mode
, tmp0
, tmp
);
2769 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2770 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2774 /* Condition in shape a <= b - s * i
2775 We must know that a - s does not overflow and a - s <= b and then
2776 we can again compute number of iterations as (b - (a - s)) / s. */
2777 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2778 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2779 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2781 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2782 lowpart_subreg (mode
, step
, comp_mode
));
2787 /* If s is power of 2, we know that the loop is infinite if
2788 a % s <= b % s and a - s overflows. */
2789 assumption
= simplify_gen_relational (reverse_condition (cond
),
2793 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2794 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2795 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2796 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2798 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2802 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2805 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2808 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2809 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2810 assumption
= simplify_gen_relational (reverse_condition (cond
),
2813 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2814 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2816 if (assumption
== const_true_rtx
)
2817 goto zero_iter_simplify
;
2818 else if (assumption
!= const0_rtx
)
2819 desc
->noloop_assumptions
=
2820 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2821 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2822 desc
->niter_expr
= delta
;
2825 old_niter
= desc
->niter_expr
;
2827 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2828 if (desc
->assumptions
2829 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2831 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2832 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2833 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2835 /* Rerun the simplification. Consider code (created by copying loop headers)
2847 The first pass determines that i = 0, the second pass uses it to eliminate
2848 noloop assumption. */
2850 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2851 if (desc
->assumptions
2852 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2854 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2855 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2856 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2858 if (desc
->noloop_assumptions
2859 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2862 if (CONST_INT_P (desc
->niter_expr
))
2864 uint64_t val
= INTVAL (desc
->niter_expr
);
2866 desc
->const_iter
= true;
2867 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2869 && !desc
->assumptions
)
2870 record_niter_bound (loop
, desc
->niter
, false, true);
2874 max
= determine_max_iter (loop
, desc
, old_niter
);
2876 goto zero_iter_simplify
;
2878 && !desc
->assumptions
)
2879 record_niter_bound (loop
, max
, false, true);
2881 /* simplify_using_initial_values does a copy propagation on the registers
2882 in the expression for the number of iterations. This prolongs life
2883 ranges of registers and increases register pressure, and usually
2884 brings no gain (and if it happens to do, the cse pass will take care
2885 of it anyway). So prevent this behavior, unless it enabled us to
2886 derive that the number of iterations is a constant. */
2887 desc
->niter_expr
= old_niter
;
2893 /* Simplify the assumptions. */
2894 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2895 if (desc
->assumptions
2896 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2898 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2902 desc
->const_iter
= true;
2904 record_niter_bound (loop
, 0, true, true);
2905 desc
->noloop_assumptions
= NULL_RTX
;
2906 desc
->niter_expr
= const0_rtx
;
2910 desc
->simple_p
= false;
2914 /* Checks whether E is a simple exit from LOOP and stores its description
2918 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2920 basic_block exit_bb
;
2926 desc
->simple_p
= false;
2928 /* It must belong directly to the loop. */
2929 if (exit_bb
->loop_father
!= loop
)
2932 /* It must be tested (at least) once during any iteration. */
2933 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2936 /* It must end in a simple conditional jump. */
2937 if (!any_condjump_p (BB_END (exit_bb
)))
2940 ein
= EDGE_SUCC (exit_bb
, 0);
2942 ein
= EDGE_SUCC (exit_bb
, 1);
2945 desc
->in_edge
= ein
;
2947 /* Test whether the condition is suitable. */
2948 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2951 if (ein
->flags
& EDGE_FALLTHRU
)
2953 condition
= reversed_condition (condition
);
2958 /* Check that we are able to determine number of iterations and fill
2959 in information about it. */
2960 iv_number_of_iterations (loop
, at
, condition
, desc
);
2963 /* Finds a simple exit of LOOP and stores its description into DESC. */
2966 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2971 struct niter_desc act
;
2975 desc
->simple_p
= false;
2976 body
= get_loop_body (loop
);
2978 for (i
= 0; i
< loop
->num_nodes
; i
++)
2980 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2982 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2985 check_simple_exit (loop
, e
, &act
);
2993 /* Prefer constant iterations; the less the better. */
2995 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2998 /* Also if the actual exit may be infinite, while the old one
2999 not, prefer the old one. */
3000 if (act
.infinite
&& !desc
->infinite
)
3012 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
3013 fprintf (dump_file
, " simple exit %d -> %d\n",
3014 desc
->out_edge
->src
->index
,
3015 desc
->out_edge
->dest
->index
);
3016 if (desc
->assumptions
)
3018 fprintf (dump_file
, " assumptions: ");
3019 print_rtl (dump_file
, desc
->assumptions
);
3020 fprintf (dump_file
, "\n");
3022 if (desc
->noloop_assumptions
)
3024 fprintf (dump_file
, " does not roll if: ");
3025 print_rtl (dump_file
, desc
->noloop_assumptions
);
3026 fprintf (dump_file
, "\n");
3030 fprintf (dump_file
, " infinite if: ");
3031 print_rtl (dump_file
, desc
->infinite
);
3032 fprintf (dump_file
, "\n");
3035 fprintf (dump_file
, " number of iterations: ");
3036 print_rtl (dump_file
, desc
->niter_expr
);
3037 fprintf (dump_file
, "\n");
3039 fprintf (dump_file
, " upper bound: %li\n",
3040 (long)get_max_loop_iterations_int (loop
));
3041 fprintf (dump_file
, " realistic bound: %li\n",
3042 (long)get_estimated_loop_iterations_int (loop
));
3045 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3051 /* Creates a simple loop description of LOOP if it was not computed
3055 get_simple_loop_desc (struct loop
*loop
)
3057 struct niter_desc
*desc
= simple_loop_desc (loop
);
3062 /* At least desc->infinite is not always initialized by
3063 find_simple_loop_exit. */
3064 desc
= ggc_cleared_alloc
<niter_desc
> ();
3065 iv_analysis_loop_init (loop
);
3066 find_simple_exit (loop
, desc
);
3067 loop
->simple_loop_desc
= desc
;
3069 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3071 const char *wording
;
3073 /* Assume that no overflow happens and that the loop is finite.
3074 We already warned at the tree level if we ran optimizations there. */
3075 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3080 flag_unsafe_loop_optimizations
3081 ? N_("assuming that the loop is not infinite")
3082 : N_("cannot optimize possibly infinite loops");
3083 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3086 if (desc
->assumptions
)
3089 flag_unsafe_loop_optimizations
3090 ? N_("assuming that the loop counter does not overflow")
3091 : N_("cannot optimize loop, the loop counter may overflow");
3092 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3097 if (flag_unsafe_loop_optimizations
)
3099 desc
->assumptions
= NULL_RTX
;
3100 desc
->infinite
= NULL_RTX
;
3107 /* Releases simple loop description for LOOP. */
3110 free_simple_loop_desc (struct loop
*loop
)
3112 struct niter_desc
*desc
= simple_loop_desc (loop
);
3118 loop
->simple_loop_desc
= NULL
;