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"
59 #include "dominance.h"
61 #include "basic-block.h"
67 #include "insn-config.h"
77 #include "diagnostic-core.h"
82 /* Possible return values of iv_get_reaching_def. */
86 /* More than one reaching def, or reaching def that does not
90 /* The use is trivial invariant of the loop, i.e. is not changed
94 /* The use is reached by initial value and a value from the
95 previous iteration. */
98 /* The use has single dominating def. */
102 /* Information about a biv. */
106 unsigned regno
; /* The register of the biv. */
107 struct rtx_iv iv
; /* Value of the biv. */
110 static bool clean_slate
= true;
112 static unsigned int iv_ref_table_size
= 0;
114 /* Table of rtx_ivs indexed by the df_ref uid field. */
115 static struct rtx_iv
** iv_ref_table
;
117 /* Induction variable stored at the reference. */
118 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
119 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
121 /* The current loop. */
123 static struct loop
*current_loop
;
125 /* Hashtable helper. */
127 struct biv_entry_hasher
: free_ptr_hash
<biv_entry
>
129 typedef rtx_def
*compare_type
;
130 static inline hashval_t
hash (const biv_entry
*);
131 static inline bool equal (const biv_entry
*, const rtx_def
*);
134 /* Returns hash value for biv B. */
137 biv_entry_hasher::hash (const biv_entry
*b
)
142 /* Compares biv B and register R. */
145 biv_entry_hasher::equal (const biv_entry
*b
, const rtx_def
*r
)
147 return b
->regno
== REGNO (r
);
150 /* Bivs of the current loop. */
152 static hash_table
<biv_entry_hasher
> *bivs
;
154 static bool iv_analyze_op (rtx_insn
*, rtx
, struct rtx_iv
*);
156 /* Return the RTX code corresponding to the IV extend code EXTEND. */
157 static inline enum rtx_code
158 iv_extend_to_rtx_code (enum iv_extend_code extend
)
166 case IV_UNKNOWN_EXTEND
:
172 /* Dumps information about IV to FILE. */
174 extern void dump_iv_info (FILE *, struct rtx_iv
*);
176 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
180 fprintf (file
, "not simple");
184 if (iv
->step
== const0_rtx
185 && !iv
->first_special
)
186 fprintf (file
, "invariant ");
188 print_rtl (file
, iv
->base
);
189 if (iv
->step
!= const0_rtx
)
191 fprintf (file
, " + ");
192 print_rtl (file
, iv
->step
);
193 fprintf (file
, " * iteration");
195 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
197 if (iv
->mode
!= iv
->extend_mode
)
198 fprintf (file
, " %s to %s",
199 rtx_name
[iv_extend_to_rtx_code (iv
->extend
)],
200 GET_MODE_NAME (iv
->extend_mode
));
202 if (iv
->mult
!= const1_rtx
)
204 fprintf (file
, " * ");
205 print_rtl (file
, iv
->mult
);
207 if (iv
->delta
!= const0_rtx
)
209 fprintf (file
, " + ");
210 print_rtl (file
, iv
->delta
);
212 if (iv
->first_special
)
213 fprintf (file
, " (first special)");
216 /* Generates a subreg to get the least significant part of EXPR (in mode
217 INNER_MODE) to OUTER_MODE. */
220 lowpart_subreg (machine_mode outer_mode
, rtx expr
,
221 machine_mode inner_mode
)
223 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
224 subreg_lowpart_offset (outer_mode
, inner_mode
));
228 check_iv_ref_table_size (void)
230 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
232 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
233 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
234 memset (&iv_ref_table
[iv_ref_table_size
], 0,
235 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
236 iv_ref_table_size
= new_size
;
241 /* Checks whether REG is a well-behaved register. */
244 simple_reg_p (rtx reg
)
248 if (GET_CODE (reg
) == SUBREG
)
250 if (!subreg_lowpart_p (reg
))
252 reg
= SUBREG_REG (reg
);
259 if (HARD_REGISTER_NUM_P (r
))
262 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
268 /* Clears the information about ivs stored in df. */
273 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
276 check_iv_ref_table_size ();
277 for (i
= 0; i
< n_defs
; i
++)
279 iv
= iv_ref_table
[i
];
283 iv_ref_table
[i
] = NULL
;
291 /* Prepare the data for an induction variable analysis of a LOOP. */
294 iv_analysis_loop_init (struct loop
*loop
)
298 /* Clear the information from the analysis of the previous loop. */
301 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
302 bivs
= new hash_table
<biv_entry_hasher
> (10);
308 /* Get rid of the ud chains before processing the rescans. Then add
310 df_remove_problem (df_chain
);
311 df_process_deferred_rescans ();
312 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
313 df_chain_add_problem (DF_UD_CHAIN
);
314 df_note_add_problem ();
315 df_analyze_loop (loop
);
317 df_dump_region (dump_file
);
319 check_iv_ref_table_size ();
322 /* Finds the definition of REG that dominates loop latch and stores
323 it to DEF. Returns false if there is not a single definition
324 dominating the latch. If REG has no definition in loop, DEF
325 is set to NULL and true is returned. */
328 latch_dominating_def (rtx reg
, df_ref
*def
)
330 df_ref single_rd
= NULL
, adef
;
331 unsigned regno
= REGNO (reg
);
332 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
334 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
336 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
337 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
340 /* More than one reaching definition. */
344 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
354 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
356 static enum iv_grd_result
357 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
360 basic_block def_bb
, use_bb
;
365 if (!simple_reg_p (reg
))
367 if (GET_CODE (reg
) == SUBREG
)
368 reg
= SUBREG_REG (reg
);
369 gcc_assert (REG_P (reg
));
371 use
= df_find_use (insn
, reg
);
372 gcc_assert (use
!= NULL
);
374 if (!DF_REF_CHAIN (use
))
375 return GRD_INVARIANT
;
377 /* More than one reaching def. */
378 if (DF_REF_CHAIN (use
)->next
)
381 adef
= DF_REF_CHAIN (use
)->ref
;
383 /* We do not handle setting only part of the register. */
384 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
387 def_insn
= DF_REF_INSN (adef
);
388 def_bb
= DF_REF_BB (adef
);
389 use_bb
= BLOCK_FOR_INSN (insn
);
391 if (use_bb
== def_bb
)
392 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
394 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
399 return GRD_SINGLE_DOM
;
402 /* The definition does not dominate the use. This is still OK if
403 this may be a use of a biv, i.e. if the def_bb dominates loop
405 if (just_once_each_iteration_p (current_loop
, def_bb
))
406 return GRD_MAYBE_BIV
;
411 /* Sets IV to invariant CST in MODE. Always returns true (just for
412 consistency with other iv manipulation functions that may fail). */
415 iv_constant (struct rtx_iv
*iv
, rtx cst
, machine_mode mode
)
417 if (mode
== VOIDmode
)
418 mode
= GET_MODE (cst
);
422 iv
->step
= const0_rtx
;
423 iv
->first_special
= false;
424 iv
->extend
= IV_UNKNOWN_EXTEND
;
425 iv
->extend_mode
= iv
->mode
;
426 iv
->delta
= const0_rtx
;
427 iv
->mult
= const1_rtx
;
432 /* Evaluates application of subreg to MODE on IV. */
435 iv_subreg (struct rtx_iv
*iv
, machine_mode mode
)
437 /* If iv is invariant, just calculate the new value. */
438 if (iv
->step
== const0_rtx
439 && !iv
->first_special
)
441 rtx val
= get_iv_value (iv
, const0_rtx
);
442 val
= lowpart_subreg (mode
, val
,
443 iv
->extend
== IV_UNKNOWN_EXTEND
444 ? iv
->mode
: iv
->extend_mode
);
447 iv
->extend
= IV_UNKNOWN_EXTEND
;
448 iv
->mode
= iv
->extend_mode
= mode
;
449 iv
->delta
= const0_rtx
;
450 iv
->mult
= const1_rtx
;
454 if (iv
->extend_mode
== mode
)
457 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
460 iv
->extend
= IV_UNKNOWN_EXTEND
;
463 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
464 simplify_gen_binary (MULT
, iv
->extend_mode
,
465 iv
->base
, iv
->mult
));
466 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
467 iv
->mult
= const1_rtx
;
468 iv
->delta
= const0_rtx
;
469 iv
->first_special
= false;
474 /* Evaluates application of EXTEND to MODE on IV. */
477 iv_extend (struct rtx_iv
*iv
, enum iv_extend_code extend
, machine_mode mode
)
479 /* If iv is invariant, just calculate the new value. */
480 if (iv
->step
== const0_rtx
481 && !iv
->first_special
)
483 rtx val
= get_iv_value (iv
, const0_rtx
);
484 if (iv
->extend_mode
!= iv
->mode
485 && iv
->extend
!= IV_UNKNOWN_EXTEND
486 && iv
->extend
!= extend
)
487 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
488 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
491 ? iv
->extend_mode
: iv
->mode
);
493 iv
->extend
= IV_UNKNOWN_EXTEND
;
494 iv
->mode
= iv
->extend_mode
= mode
;
495 iv
->delta
= const0_rtx
;
496 iv
->mult
= const1_rtx
;
500 if (mode
!= iv
->extend_mode
)
503 if (iv
->extend
!= IV_UNKNOWN_EXTEND
504 && iv
->extend
!= extend
)
512 /* Evaluates negation of IV. */
515 iv_neg (struct rtx_iv
*iv
)
517 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
519 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
520 iv
->base
, iv
->extend_mode
);
521 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
522 iv
->step
, iv
->extend_mode
);
526 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
527 iv
->delta
, iv
->extend_mode
);
528 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
529 iv
->mult
, iv
->extend_mode
);
535 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
538 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
543 /* Extend the constant to extend_mode of the other operand if necessary. */
544 if (iv0
->extend
== IV_UNKNOWN_EXTEND
545 && iv0
->mode
== iv0
->extend_mode
546 && iv0
->step
== const0_rtx
547 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
549 iv0
->extend_mode
= iv1
->extend_mode
;
550 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
551 iv0
->base
, iv0
->mode
);
553 if (iv1
->extend
== IV_UNKNOWN_EXTEND
554 && iv1
->mode
== iv1
->extend_mode
555 && iv1
->step
== const0_rtx
556 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
558 iv1
->extend_mode
= iv0
->extend_mode
;
559 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
560 iv1
->base
, iv1
->mode
);
563 mode
= iv0
->extend_mode
;
564 if (mode
!= iv1
->extend_mode
)
567 if (iv0
->extend
== IV_UNKNOWN_EXTEND
568 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
570 if (iv0
->mode
!= iv1
->mode
)
573 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
574 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
579 /* Handle addition of constant. */
580 if (iv1
->extend
== IV_UNKNOWN_EXTEND
582 && iv1
->step
== const0_rtx
)
584 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
588 if (iv0
->extend
== IV_UNKNOWN_EXTEND
590 && iv0
->step
== const0_rtx
)
598 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
605 /* Evaluates multiplication of IV by constant CST. */
608 iv_mult (struct rtx_iv
*iv
, rtx mby
)
610 machine_mode mode
= iv
->extend_mode
;
612 if (GET_MODE (mby
) != VOIDmode
613 && GET_MODE (mby
) != mode
)
616 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
618 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
619 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
623 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
624 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
630 /* Evaluates shift of IV by constant CST. */
633 iv_shift (struct rtx_iv
*iv
, rtx mby
)
635 machine_mode mode
= iv
->extend_mode
;
637 if (GET_MODE (mby
) != VOIDmode
638 && GET_MODE (mby
) != mode
)
641 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
643 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
644 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
648 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
649 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
655 /* The recursive part of get_biv_step. Gets the value of the single value
656 defined by DEF wrto initial value of REG inside loop, in shape described
660 get_biv_step_1 (df_ref def
, rtx reg
,
661 rtx
*inner_step
, machine_mode
*inner_mode
,
662 enum iv_extend_code
*extend
, machine_mode outer_mode
,
665 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
668 rtx_insn
*insn
= DF_REF_INSN (def
);
670 enum iv_grd_result res
;
672 set
= single_set (insn
);
676 rhs
= find_reg_equal_equiv_note (insn
);
682 code
= GET_CODE (rhs
);
695 if (code
== PLUS
&& CONSTANT_P (op0
))
696 std::swap (op0
, op1
);
698 if (!simple_reg_p (op0
)
699 || !CONSTANT_P (op1
))
702 if (GET_MODE (rhs
) != outer_mode
)
704 /* ppc64 uses expressions like
706 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
708 this is equivalent to
710 (set x':DI (plus:DI y:DI 1))
711 (set x:SI (subreg:SI (x':DI)). */
712 if (GET_CODE (op0
) != SUBREG
)
714 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
723 if (GET_MODE (rhs
) != outer_mode
)
727 if (!simple_reg_p (op0
))
737 if (GET_CODE (next
) == SUBREG
)
739 if (!subreg_lowpart_p (next
))
742 nextr
= SUBREG_REG (next
);
743 if (GET_MODE (nextr
) != outer_mode
)
749 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
751 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
754 if (res
== GRD_MAYBE_BIV
)
756 if (!rtx_equal_p (nextr
, reg
))
759 *inner_step
= const0_rtx
;
760 *extend
= IV_UNKNOWN_EXTEND
;
761 *inner_mode
= outer_mode
;
762 *outer_step
= const0_rtx
;
764 else if (!get_biv_step_1 (next_def
, reg
,
765 inner_step
, inner_mode
, extend
, outer_mode
,
769 if (GET_CODE (next
) == SUBREG
)
771 machine_mode amode
= GET_MODE (next
);
773 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
777 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
778 *inner_step
, *outer_step
);
779 *outer_step
= const0_rtx
;
780 *extend
= IV_UNKNOWN_EXTEND
;
791 if (*inner_mode
== outer_mode
792 /* See comment in previous switch. */
793 || GET_MODE (rhs
) != outer_mode
)
794 *inner_step
= simplify_gen_binary (code
, outer_mode
,
797 *outer_step
= simplify_gen_binary (code
, outer_mode
,
803 gcc_assert (GET_MODE (op0
) == *inner_mode
804 && *extend
== IV_UNKNOWN_EXTEND
805 && *outer_step
== const0_rtx
);
807 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
817 /* Gets the operation on register REG inside loop, in shape
819 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
821 If the operation cannot be described in this shape, return false.
822 LAST_DEF is the definition of REG that dominates loop latch. */
825 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
826 machine_mode
*inner_mode
, enum iv_extend_code
*extend
,
827 machine_mode
*outer_mode
, rtx
*outer_step
)
829 *outer_mode
= GET_MODE (reg
);
831 if (!get_biv_step_1 (last_def
, reg
,
832 inner_step
, inner_mode
, extend
, *outer_mode
,
836 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
837 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
842 /* Records information that DEF is induction variable IV. */
845 record_iv (df_ref def
, struct rtx_iv
*iv
)
847 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
850 check_iv_ref_table_size ();
851 DF_REF_IV_SET (def
, recorded_iv
);
854 /* If DEF was already analyzed for bivness, store the description of the biv to
855 IV and return true. Otherwise return false. */
858 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
860 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
870 record_biv (rtx def
, struct rtx_iv
*iv
)
872 struct biv_entry
*biv
= XNEW (struct biv_entry
);
873 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
875 biv
->regno
= REGNO (def
);
881 /* Determines whether DEF is a biv and if so, stores its description
885 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
887 rtx inner_step
, outer_step
;
888 machine_mode inner_mode
, outer_mode
;
889 enum iv_extend_code extend
;
894 fprintf (dump_file
, "Analyzing ");
895 print_rtl (dump_file
, def
);
896 fprintf (dump_file
, " for bivness.\n");
901 if (!CONSTANT_P (def
))
904 return iv_constant (iv
, def
, VOIDmode
);
907 if (!latch_dominating_def (def
, &last_def
))
910 fprintf (dump_file
, " not simple.\n");
915 return iv_constant (iv
, def
, VOIDmode
);
917 if (analyzed_for_bivness_p (def
, iv
))
920 fprintf (dump_file
, " already analysed.\n");
921 return iv
->base
!= NULL_RTX
;
924 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
925 &outer_mode
, &outer_step
))
931 /* Loop transforms base to es (base + inner_step) + outer_step,
932 where es means extend of subreg between inner_mode and outer_mode.
933 The corresponding induction variable is
935 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
937 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
938 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
939 iv
->mode
= inner_mode
;
940 iv
->extend_mode
= outer_mode
;
942 iv
->mult
= const1_rtx
;
943 iv
->delta
= outer_step
;
944 iv
->first_special
= inner_mode
!= outer_mode
;
949 fprintf (dump_file
, " ");
950 dump_iv_info (dump_file
, iv
);
951 fprintf (dump_file
, "\n");
954 record_biv (def
, iv
);
955 return iv
->base
!= NULL_RTX
;
958 /* Analyzes expression RHS used at INSN and stores the result to *IV.
959 The mode of the induction variable is MODE. */
962 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, machine_mode mode
,
966 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
967 struct rtx_iv iv0
, iv1
;
968 enum rtx_code code
= GET_CODE (rhs
);
969 machine_mode omode
= mode
;
975 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
981 if (!iv_analyze_op (insn
, rhs
, iv
))
984 if (iv
->mode
== VOIDmode
)
987 iv
->extend_mode
= mode
;
1002 op0
= XEXP (rhs
, 0);
1003 omode
= GET_MODE (op0
);
1008 op0
= XEXP (rhs
, 0);
1009 op1
= XEXP (rhs
, 1);
1013 op0
= XEXP (rhs
, 0);
1014 mby
= XEXP (rhs
, 1);
1015 if (!CONSTANT_P (mby
))
1016 std::swap (op0
, mby
);
1017 if (!CONSTANT_P (mby
))
1022 op0
= XEXP (rhs
, 0);
1023 mby
= XEXP (rhs
, 1);
1024 if (!CONSTANT_P (mby
))
1033 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1037 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1043 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1048 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1059 if (!iv_add (&iv0
, &iv1
, code
))
1064 if (!iv_mult (&iv0
, mby
))
1069 if (!iv_shift (&iv0
, mby
))
1078 return iv
->base
!= NULL_RTX
;
1081 /* Analyzes iv DEF and stores the result to *IV. */
1084 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1086 rtx_insn
*insn
= DF_REF_INSN (def
);
1087 rtx reg
= DF_REF_REG (def
);
1092 fprintf (dump_file
, "Analyzing def of ");
1093 print_rtl (dump_file
, reg
);
1094 fprintf (dump_file
, " in insn ");
1095 print_rtl_single (dump_file
, insn
);
1098 check_iv_ref_table_size ();
1099 if (DF_REF_IV (def
))
1102 fprintf (dump_file
, " already analysed.\n");
1103 *iv
= *DF_REF_IV (def
);
1104 return iv
->base
!= NULL_RTX
;
1107 iv
->mode
= VOIDmode
;
1108 iv
->base
= NULL_RTX
;
1109 iv
->step
= NULL_RTX
;
1114 set
= single_set (insn
);
1118 if (!REG_P (SET_DEST (set
)))
1121 gcc_assert (SET_DEST (set
) == reg
);
1122 rhs
= find_reg_equal_equiv_note (insn
);
1124 rhs
= XEXP (rhs
, 0);
1126 rhs
= SET_SRC (set
);
1128 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1129 record_iv (def
, iv
);
1133 print_rtl (dump_file
, reg
);
1134 fprintf (dump_file
, " in insn ");
1135 print_rtl_single (dump_file
, insn
);
1136 fprintf (dump_file
, " is ");
1137 dump_iv_info (dump_file
, iv
);
1138 fprintf (dump_file
, "\n");
1141 return iv
->base
!= NULL_RTX
;
1144 /* Analyzes operand OP of INSN and stores the result to *IV. */
1147 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1150 enum iv_grd_result res
;
1154 fprintf (dump_file
, "Analyzing operand ");
1155 print_rtl (dump_file
, op
);
1156 fprintf (dump_file
, " of insn ");
1157 print_rtl_single (dump_file
, insn
);
1160 if (function_invariant_p (op
))
1161 res
= GRD_INVARIANT
;
1162 else if (GET_CODE (op
) == SUBREG
)
1164 if (!subreg_lowpart_p (op
))
1167 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1170 return iv_subreg (iv
, GET_MODE (op
));
1174 res
= iv_get_reaching_def (insn
, op
, &def
);
1175 if (res
== GRD_INVALID
)
1178 fprintf (dump_file
, " not simple.\n");
1183 if (res
== GRD_INVARIANT
)
1185 iv_constant (iv
, op
, VOIDmode
);
1189 fprintf (dump_file
, " ");
1190 dump_iv_info (dump_file
, iv
);
1191 fprintf (dump_file
, "\n");
1196 if (res
== GRD_MAYBE_BIV
)
1197 return iv_analyze_biv (op
, iv
);
1199 return iv_analyze_def (def
, iv
);
1202 /* Analyzes value VAL at INSN and stores the result to *IV. */
1205 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1209 /* We must find the insn in that val is used, so that we get to UD chains.
1210 Since the function is sometimes called on result of get_condition,
1211 this does not necessarily have to be directly INSN; scan also the
1213 if (simple_reg_p (val
))
1215 if (GET_CODE (val
) == SUBREG
)
1216 reg
= SUBREG_REG (val
);
1220 while (!df_find_use (insn
, reg
))
1221 insn
= NEXT_INSN (insn
);
1224 return iv_analyze_op (insn
, val
, iv
);
1227 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1230 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1234 adef
= df_find_def (insn
, def
);
1238 return iv_analyze_def (adef
, iv
);
1241 /* Checks whether definition of register REG in INSN is a basic induction
1242 variable. IV analysis must have been initialized (via a call to
1243 iv_analysis_loop_init) for this function to produce a result. */
1246 biv_p (rtx_insn
*insn
, rtx reg
)
1249 df_ref def
, last_def
;
1251 if (!simple_reg_p (reg
))
1254 def
= df_find_def (insn
, reg
);
1255 gcc_assert (def
!= NULL
);
1256 if (!latch_dominating_def (reg
, &last_def
))
1258 if (last_def
!= def
)
1261 if (!iv_analyze_biv (reg
, &iv
))
1264 return iv
.step
!= const0_rtx
;
1267 /* Calculates value of IV at ITERATION-th iteration. */
1270 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1274 /* We would need to generate some if_then_else patterns, and so far
1275 it is not needed anywhere. */
1276 gcc_assert (!iv
->first_special
);
1278 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1279 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1280 simplify_gen_binary (MULT
, iv
->extend_mode
,
1281 iv
->step
, iteration
));
1285 if (iv
->extend_mode
== iv
->mode
)
1288 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1290 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1293 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1294 iv
->extend_mode
, val
, iv
->mode
);
1295 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1296 simplify_gen_binary (MULT
, iv
->extend_mode
,
1302 /* Free the data for an induction variable analysis. */
1305 iv_analysis_done (void)
1311 df_finish_pass (true);
1314 free (iv_ref_table
);
1315 iv_ref_table
= NULL
;
1316 iv_ref_table_size
= 0;
1320 /* Computes inverse to X modulo (1 << MOD). */
1323 inverse (uint64_t x
, int mod
)
1326 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1330 for (i
= 0; i
< mod
- 1; i
++)
1332 rslt
= (rslt
* x
) & mask
;
1339 /* Checks whether any register in X is in set ALT. */
1342 altered_reg_used (const_rtx x
, bitmap alt
)
1344 subrtx_iterator::array_type array
;
1345 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
1347 const_rtx x
= *iter
;
1348 if (REG_P (x
) && REGNO_REG_SET_P (alt
, REGNO (x
)))
1354 /* Marks registers altered by EXPR in set ALT. */
1357 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1359 if (GET_CODE (expr
) == SUBREG
)
1360 expr
= SUBREG_REG (expr
);
1364 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1367 /* Checks whether RHS is simple enough to process. */
1370 simple_rhs_p (rtx rhs
)
1374 if (function_invariant_p (rhs
)
1375 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1378 switch (GET_CODE (rhs
))
1383 op0
= XEXP (rhs
, 0);
1384 op1
= XEXP (rhs
, 1);
1385 /* Allow reg OP const and reg OP reg. */
1386 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1387 && !function_invariant_p (op0
))
1389 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1390 && !function_invariant_p (op1
))
1399 op0
= XEXP (rhs
, 0);
1400 op1
= XEXP (rhs
, 1);
1401 /* Allow reg OP const. */
1402 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1404 if (!function_invariant_p (op1
))
1414 /* If REGNO has a single definition, return its known value, otherwise return
1418 find_single_def_src (unsigned int regno
)
1426 adef
= DF_REG_DEF_CHAIN (regno
);
1427 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1428 || DF_REF_IS_ARTIFICIAL (adef
))
1431 set
= single_set (DF_REF_INSN (adef
));
1432 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1433 || REGNO (SET_DEST (set
)) != regno
)
1436 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1438 if (note
&& function_invariant_p (XEXP (note
, 0)))
1440 src
= XEXP (note
, 0);
1443 src
= SET_SRC (set
);
1447 regno
= REGNO (src
);
1452 if (!function_invariant_p (src
))
1458 /* If any registers in *EXPR that have a single definition, try to replace
1459 them with the known-equivalent values. */
1462 replace_single_def_regs (rtx
*expr
)
1464 subrtx_var_iterator::array_type array
;
1466 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1470 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1472 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1478 /* A subroutine of simplify_using_initial_values, this function examines INSN
1479 to see if it contains a suitable set that we can use to make a replacement.
1480 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1481 the set; return false otherwise. */
1484 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1486 rtx set
= single_set (insn
);
1487 rtx lhs
= NULL_RTX
, rhs
;
1492 lhs
= SET_DEST (set
);
1496 rhs
= find_reg_equal_equiv_note (insn
);
1498 rhs
= XEXP (rhs
, 0);
1500 rhs
= SET_SRC (set
);
1502 if (!simple_rhs_p (rhs
))
1510 /* Using the data returned by suitable_set_for_replacement, replace DEST
1511 with SRC in *EXPR and return the new expression. Also call
1512 replace_single_def_regs if the replacement changed something. */
1514 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1517 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1520 replace_single_def_regs (expr
);
1523 /* Checks whether A implies B. */
1526 implies_p (rtx a
, rtx b
)
1528 rtx op0
, op1
, opb0
, opb1
;
1531 if (rtx_equal_p (a
, b
))
1534 if (GET_CODE (a
) == EQ
)
1540 || (GET_CODE (op0
) == SUBREG
1541 && REG_P (SUBREG_REG (op0
))))
1543 rtx r
= simplify_replace_rtx (b
, op0
, op1
);
1544 if (r
== const_true_rtx
)
1549 || (GET_CODE (op1
) == SUBREG
1550 && REG_P (SUBREG_REG (op1
))))
1552 rtx r
= simplify_replace_rtx (b
, op1
, op0
);
1553 if (r
== const_true_rtx
)
1558 if (b
== const_true_rtx
)
1561 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1562 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1563 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1564 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1572 mode
= GET_MODE (op0
);
1573 if (mode
!= GET_MODE (opb0
))
1575 else if (mode
== VOIDmode
)
1577 mode
= GET_MODE (op1
);
1578 if (mode
!= GET_MODE (opb1
))
1582 /* A < B implies A + 1 <= B. */
1583 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1584 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1587 if (GET_CODE (a
) == GT
)
1588 std::swap (op0
, op1
);
1590 if (GET_CODE (b
) == GE
)
1591 std::swap (opb0
, opb1
);
1593 if (SCALAR_INT_MODE_P (mode
)
1594 && rtx_equal_p (op1
, opb1
)
1595 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1600 /* A < B or A > B imply A != B. TODO: Likewise
1601 A + n < B implies A != B + n if neither wraps. */
1602 if (GET_CODE (b
) == NE
1603 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1604 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1606 if (rtx_equal_p (op0
, opb0
)
1607 && rtx_equal_p (op1
, opb1
))
1611 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1612 if (GET_CODE (a
) == NE
1613 && op1
== const0_rtx
)
1615 if ((GET_CODE (b
) == GTU
1616 && opb1
== const0_rtx
)
1617 || (GET_CODE (b
) == GEU
1618 && opb1
== const1_rtx
))
1619 return rtx_equal_p (op0
, opb0
);
1622 /* A != N is equivalent to A - (N + 1) <u -1. */
1623 if (GET_CODE (a
) == NE
1624 && CONST_INT_P (op1
)
1625 && GET_CODE (b
) == LTU
1626 && opb1
== constm1_rtx
1627 && GET_CODE (opb0
) == PLUS
1628 && CONST_INT_P (XEXP (opb0
, 1))
1629 /* Avoid overflows. */
1630 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1631 != ((unsigned HOST_WIDE_INT
)1
1632 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1633 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1634 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1636 /* Likewise, A != N implies A - N > 0. */
1637 if (GET_CODE (a
) == NE
1638 && CONST_INT_P (op1
))
1640 if (GET_CODE (b
) == GTU
1641 && GET_CODE (opb0
) == PLUS
1642 && opb1
== const0_rtx
1643 && CONST_INT_P (XEXP (opb0
, 1))
1644 /* Avoid overflows. */
1645 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1646 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1647 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1648 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1649 if (GET_CODE (b
) == GEU
1650 && GET_CODE (opb0
) == PLUS
1651 && opb1
== const1_rtx
1652 && CONST_INT_P (XEXP (opb0
, 1))
1653 /* Avoid overflows. */
1654 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1655 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1656 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1657 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1660 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1661 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1662 && CONST_INT_P (op1
)
1663 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1664 || INTVAL (op1
) >= 0)
1665 && GET_CODE (b
) == LTU
1666 && CONST_INT_P (opb1
)
1667 && rtx_equal_p (op0
, opb0
))
1668 return INTVAL (opb1
) < 0;
1673 /* Canonicalizes COND so that
1675 (1) Ensure that operands are ordered according to
1676 swap_commutative_operands_p.
1677 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1678 for GE, GEU, and LEU. */
1681 canon_condition (rtx cond
)
1687 code
= GET_CODE (cond
);
1688 op0
= XEXP (cond
, 0);
1689 op1
= XEXP (cond
, 1);
1691 if (swap_commutative_operands_p (op0
, op1
))
1693 code
= swap_condition (code
);
1694 std::swap (op0
, op1
);
1697 mode
= GET_MODE (op0
);
1698 if (mode
== VOIDmode
)
1699 mode
= GET_MODE (op1
);
1700 gcc_assert (mode
!= VOIDmode
);
1702 if (CONST_SCALAR_INT_P (op1
) && GET_MODE_CLASS (mode
) != MODE_CC
)
1704 rtx_mode_t
const_val (op1
, mode
);
1709 if (wi::ne_p (const_val
, wi::max_value (mode
, SIGNED
)))
1712 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1717 if (wi::ne_p (const_val
, wi::min_value (mode
, SIGNED
)))
1720 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1725 if (wi::ne_p (const_val
, -1))
1728 op1
= immed_wide_int_const (wi::add (const_val
, 1), mode
);
1733 if (wi::ne_p (const_val
, 0))
1736 op1
= immed_wide_int_const (wi::sub (const_val
, 1), mode
);
1745 if (op0
!= XEXP (cond
, 0)
1746 || op1
!= XEXP (cond
, 1)
1747 || code
!= GET_CODE (cond
)
1748 || GET_MODE (cond
) != SImode
)
1749 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1754 /* Reverses CONDition; returns NULL if we cannot. */
1757 reversed_condition (rtx cond
)
1759 enum rtx_code reversed
;
1760 reversed
= reversed_comparison_code (cond
, NULL
);
1761 if (reversed
== UNKNOWN
)
1764 return gen_rtx_fmt_ee (reversed
,
1765 GET_MODE (cond
), XEXP (cond
, 0),
1769 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1770 set of altered regs. */
1773 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1775 rtx rev
, reve
, exp
= *expr
;
1777 /* If some register gets altered later, we do not really speak about its
1778 value at the time of comparison. */
1779 if (altered
&& altered_reg_used (cond
, altered
))
1782 if (GET_CODE (cond
) == EQ
1783 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1785 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1789 if (!COMPARISON_P (exp
))
1792 rev
= reversed_condition (cond
);
1793 reve
= reversed_condition (exp
);
1795 cond
= canon_condition (cond
);
1796 exp
= canon_condition (exp
);
1798 rev
= canon_condition (rev
);
1800 reve
= canon_condition (reve
);
1802 if (rtx_equal_p (exp
, cond
))
1804 *expr
= const_true_rtx
;
1808 if (rev
&& rtx_equal_p (exp
, rev
))
1814 if (implies_p (cond
, exp
))
1816 *expr
= const_true_rtx
;
1820 if (reve
&& implies_p (cond
, reve
))
1826 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1828 if (rev
&& implies_p (exp
, rev
))
1834 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1835 if (rev
&& reve
&& implies_p (reve
, rev
))
1837 *expr
= const_true_rtx
;
1841 /* We would like to have some other tests here. TODO. */
1846 /* Use relationship between A and *B to eventually eliminate *B.
1847 OP is the operation we consider. */
1850 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1855 /* If A implies *B, we may replace *B by true. */
1856 if (implies_p (a
, *b
))
1857 *b
= const_true_rtx
;
1861 /* If *B implies A, we may replace *B by false. */
1862 if (implies_p (*b
, a
))
1871 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1872 operation we consider. */
1875 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1879 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1880 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1881 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1882 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1885 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1886 is a list, its elements are assumed to be combined using OP. */
1889 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1891 bool expression_valid
;
1892 rtx head
, tail
, last_valid_expr
;
1893 rtx_expr_list
*cond_list
;
1896 regset altered
, this_altered
;
1902 if (CONSTANT_P (*expr
))
1905 if (GET_CODE (*expr
) == EXPR_LIST
)
1907 head
= XEXP (*expr
, 0);
1908 tail
= XEXP (*expr
, 1);
1910 eliminate_implied_conditions (op
, &head
, tail
);
1915 neutral
= const_true_rtx
;
1920 neutral
= const0_rtx
;
1921 aggr
= const_true_rtx
;
1928 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1931 XEXP (*expr
, 0) = aggr
;
1932 XEXP (*expr
, 1) = NULL_RTX
;
1935 else if (head
== neutral
)
1938 simplify_using_initial_values (loop
, op
, expr
);
1941 simplify_using_initial_values (loop
, op
, &tail
);
1943 if (tail
&& XEXP (tail
, 0) == aggr
)
1949 XEXP (*expr
, 0) = head
;
1950 XEXP (*expr
, 1) = tail
;
1954 gcc_assert (op
== UNKNOWN
);
1956 replace_single_def_regs (expr
);
1957 if (CONSTANT_P (*expr
))
1960 e
= loop_preheader_edge (loop
);
1961 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1964 altered
= ALLOC_REG_SET (®_obstack
);
1965 this_altered
= ALLOC_REG_SET (®_obstack
);
1967 expression_valid
= true;
1968 last_valid_expr
= *expr
;
1972 insn
= BB_END (e
->src
);
1973 if (any_condjump_p (insn
))
1975 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1977 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1978 cond
= reversed_condition (cond
);
1982 simplify_using_condition (cond
, expr
, altered
);
1986 if (CONSTANT_P (*expr
))
1988 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1990 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1991 if (CONSTANT_P (*expr
))
1995 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1999 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
2007 CLEAR_REG_SET (this_altered
);
2008 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
2011 /* Kill all call clobbered registers. */
2013 hard_reg_set_iterator hrsi
;
2014 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2016 SET_REGNO_REG_SET (this_altered
, i
);
2019 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2021 rtx_expr_list
**pnote
, **pnote_next
;
2023 replace_in_expr (expr
, dest
, src
);
2024 if (CONSTANT_P (*expr
))
2027 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2029 rtx_expr_list
*note
= *pnote
;
2030 rtx old_cond
= XEXP (note
, 0);
2032 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2033 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2035 /* We can no longer use a condition that has been simplified
2036 to a constant, and simplify_using_condition will abort if
2038 if (CONSTANT_P (XEXP (note
, 0)))
2040 *pnote
= *pnote_next
;
2042 free_EXPR_LIST_node (note
);
2044 /* Retry simplifications with this condition if either the
2045 expression or the condition changed. */
2046 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2047 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2052 rtx_expr_list
**pnote
, **pnote_next
;
2054 /* If we did not use this insn to make a replacement, any overlap
2055 between stores in this insn and our expression will cause the
2056 expression to become invalid. */
2057 if (altered_reg_used (*expr
, this_altered
))
2060 /* Likewise for the conditions. */
2061 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2063 rtx_expr_list
*note
= *pnote
;
2064 rtx old_cond
= XEXP (note
, 0);
2066 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2067 if (altered_reg_used (old_cond
, this_altered
))
2069 *pnote
= *pnote_next
;
2071 free_EXPR_LIST_node (note
);
2076 if (CONSTANT_P (*expr
))
2079 IOR_REG_SET (altered
, this_altered
);
2081 /* If the expression now contains regs that have been altered, we
2082 can't return it to the caller. However, it is still valid for
2083 further simplification, so keep searching to see if we can
2084 eventually turn it into a constant. */
2085 if (altered_reg_used (*expr
, altered
))
2086 expression_valid
= false;
2087 if (expression_valid
)
2088 last_valid_expr
= *expr
;
2091 if (!single_pred_p (e
->src
)
2092 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2094 e
= single_pred_edge (e
->src
);
2098 free_EXPR_LIST_list (&cond_list
);
2099 if (!CONSTANT_P (*expr
))
2100 *expr
= last_valid_expr
;
2101 FREE_REG_SET (altered
);
2102 FREE_REG_SET (this_altered
);
2105 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2106 that IV occurs as left operands of comparison COND and its signedness
2107 is SIGNED_P to DESC. */
2110 shorten_into_mode (struct rtx_iv
*iv
, machine_mode mode
,
2111 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2113 rtx mmin
, mmax
, cond_over
, cond_under
;
2115 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2116 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2118 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2127 if (cond_under
!= const0_rtx
)
2129 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2130 if (cond_over
!= const0_rtx
)
2131 desc
->noloop_assumptions
=
2132 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2139 if (cond_over
!= const0_rtx
)
2141 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2142 if (cond_under
!= const0_rtx
)
2143 desc
->noloop_assumptions
=
2144 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2148 if (cond_over
!= const0_rtx
)
2150 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2151 if (cond_under
!= const0_rtx
)
2153 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2161 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2164 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2165 subregs of the same mode if possible (sometimes it is necessary to add
2166 some assumptions to DESC). */
2169 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2170 enum rtx_code cond
, struct niter_desc
*desc
)
2172 machine_mode comp_mode
;
2175 /* If the ivs behave specially in the first iteration, or are
2176 added/multiplied after extending, we ignore them. */
2177 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2179 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2182 /* If there is some extend, it must match signedness of the comparison. */
2187 if (iv0
->extend
== IV_ZERO_EXTEND
2188 || iv1
->extend
== IV_ZERO_EXTEND
)
2195 if (iv0
->extend
== IV_SIGN_EXTEND
2196 || iv1
->extend
== IV_SIGN_EXTEND
)
2202 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2203 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2204 && iv0
->extend
!= iv1
->extend
)
2208 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2209 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2210 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2211 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2218 /* Values of both variables should be computed in the same mode. These
2219 might indeed be different, if we have comparison like
2221 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2223 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2224 in different modes. This does not seem impossible to handle, but
2225 it hardly ever occurs in practice.
2227 The only exception is the case when one of operands is invariant.
2228 For example pentium 3 generates comparisons like
2229 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2230 definitely do not want this prevent the optimization. */
2231 comp_mode
= iv0
->extend_mode
;
2232 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2233 comp_mode
= iv1
->extend_mode
;
2235 if (iv0
->extend_mode
!= comp_mode
)
2237 if (iv0
->mode
!= iv0
->extend_mode
2238 || iv0
->step
!= const0_rtx
)
2241 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2242 comp_mode
, iv0
->base
, iv0
->mode
);
2243 iv0
->extend_mode
= comp_mode
;
2246 if (iv1
->extend_mode
!= comp_mode
)
2248 if (iv1
->mode
!= iv1
->extend_mode
2249 || iv1
->step
!= const0_rtx
)
2252 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2253 comp_mode
, iv1
->base
, iv1
->mode
);
2254 iv1
->extend_mode
= comp_mode
;
2257 /* Check that both ivs belong to a range of a single mode. If one of the
2258 operands is an invariant, we may need to shorten it into the common
2260 if (iv0
->mode
== iv0
->extend_mode
2261 && iv0
->step
== const0_rtx
2262 && iv0
->mode
!= iv1
->mode
)
2263 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2265 if (iv1
->mode
== iv1
->extend_mode
2266 && iv1
->step
== const0_rtx
2267 && iv0
->mode
!= iv1
->mode
)
2268 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2270 if (iv0
->mode
!= iv1
->mode
)
2273 desc
->mode
= iv0
->mode
;
2274 desc
->signed_p
= signed_p
;
2279 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2280 result. This function is called from iv_number_of_iterations with
2281 a number of fields in DESC already filled in. OLD_NITER is the original
2282 expression for the number of iterations, before we tried to simplify it. */
2285 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2287 rtx niter
= desc
->niter_expr
;
2288 rtx mmin
, mmax
, cmp
;
2290 uint64_t andmax
= 0;
2292 /* We used to look for constant operand 0 of AND,
2293 but canonicalization should always make this impossible. */
2294 gcc_checking_assert (GET_CODE (niter
) != AND
2295 || !CONST_INT_P (XEXP (niter
, 0)));
2297 if (GET_CODE (niter
) == AND
2298 && CONST_INT_P (XEXP (niter
, 1)))
2300 andmax
= UINTVAL (XEXP (niter
, 1));
2301 niter
= XEXP (niter
, 0);
2304 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2305 nmax
= UINTVAL (mmax
) - UINTVAL (mmin
);
2307 if (GET_CODE (niter
) == UDIV
)
2309 if (!CONST_INT_P (XEXP (niter
, 1)))
2311 inc
= INTVAL (XEXP (niter
, 1));
2312 niter
= XEXP (niter
, 0);
2317 /* We could use a binary search here, but for now improving the upper
2318 bound by just one eliminates one important corner case. */
2319 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2320 desc
->mode
, old_niter
, mmax
);
2321 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2322 if (cmp
== const_true_rtx
)
2327 fprintf (dump_file
, ";; improved upper bound by one.\n");
2331 nmax
= MIN (nmax
, andmax
);
2333 fprintf (dump_file
, ";; Determined upper bound %" PRId64
".\n",
2338 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2339 the result into DESC. Very similar to determine_number_of_iterations
2340 (basically its rtl version), complicated by things like subregs. */
2343 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2344 struct niter_desc
*desc
)
2346 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2347 struct rtx_iv iv0
, iv1
;
2348 rtx assumption
, may_not_xform
;
2350 machine_mode mode
, comp_mode
;
2351 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2352 uint64_t s
, size
, d
, inv
, max
;
2353 int64_t up
, down
, inc
, step_val
;
2354 int was_sharp
= false;
2358 /* The meaning of these assumptions is this:
2360 then the rest of information does not have to be valid
2361 if noloop_assumptions then the loop does not roll
2362 if infinite then this exit is never used */
2364 desc
->assumptions
= NULL_RTX
;
2365 desc
->noloop_assumptions
= NULL_RTX
;
2366 desc
->infinite
= NULL_RTX
;
2367 desc
->simple_p
= true;
2369 desc
->const_iter
= false;
2370 desc
->niter_expr
= NULL_RTX
;
2372 cond
= GET_CODE (condition
);
2373 gcc_assert (COMPARISON_P (condition
));
2375 mode
= GET_MODE (XEXP (condition
, 0));
2376 if (mode
== VOIDmode
)
2377 mode
= GET_MODE (XEXP (condition
, 1));
2378 /* The constant comparisons should be folded. */
2379 gcc_assert (mode
!= VOIDmode
);
2381 /* We only handle integers or pointers. */
2382 if (GET_MODE_CLASS (mode
) != MODE_INT
2383 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2386 op0
= XEXP (condition
, 0);
2387 if (!iv_analyze (insn
, op0
, &iv0
))
2389 if (iv0
.extend_mode
== VOIDmode
)
2390 iv0
.mode
= iv0
.extend_mode
= mode
;
2392 op1
= XEXP (condition
, 1);
2393 if (!iv_analyze (insn
, op1
, &iv1
))
2395 if (iv1
.extend_mode
== VOIDmode
)
2396 iv1
.mode
= iv1
.extend_mode
= mode
;
2398 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2399 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2402 /* Check condition and normalize it. */
2410 std::swap (iv0
, iv1
);
2411 cond
= swap_condition (cond
);
2423 /* Handle extends. This is relatively nontrivial, so we only try in some
2424 easy cases, when we can canonicalize the ivs (possibly by adding some
2425 assumptions) to shape subreg (base + i * step). This function also fills
2426 in desc->mode and desc->signed_p. */
2428 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2431 comp_mode
= iv0
.extend_mode
;
2433 size
= GET_MODE_PRECISION (mode
);
2434 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2435 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2436 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2438 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2441 /* We can take care of the case of two induction variables chasing each other
2442 if the test is NE. I have never seen a loop using it, but still it is
2444 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2449 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2450 iv1
.step
= const0_rtx
;
2453 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2454 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2456 /* This is either infinite loop or the one that ends immediately, depending
2457 on initial values. Unswitching should remove this kind of conditions. */
2458 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2463 if (iv0
.step
== const0_rtx
)
2464 step_val
= -INTVAL (iv1
.step
);
2466 step_val
= INTVAL (iv0
.step
);
2468 /* Ignore loops of while (i-- < 10) type. */
2472 step_is_pow2
= !(step_val
& (step_val
- 1));
2476 /* We do not care about whether the step is power of two in this
2478 step_is_pow2
= false;
2482 /* Some more condition normalization. We must record some assumptions
2483 due to overflows. */
2488 /* We want to take care only of non-sharp relationals; this is easy,
2489 as in cases the overflow would make the transformation unsafe
2490 the loop does not roll. Seemingly it would make more sense to want
2491 to take care of sharp relationals instead, as NE is more similar to
2492 them, but the problem is that here the transformation would be more
2493 difficult due to possibly infinite loops. */
2494 if (iv0
.step
== const0_rtx
)
2496 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2497 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2499 if (assumption
== const_true_rtx
)
2500 goto zero_iter_simplify
;
2501 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2502 iv0
.base
, const1_rtx
);
2506 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2507 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2509 if (assumption
== const_true_rtx
)
2510 goto zero_iter_simplify
;
2511 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2512 iv1
.base
, constm1_rtx
);
2515 if (assumption
!= const0_rtx
)
2516 desc
->noloop_assumptions
=
2517 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2518 cond
= (cond
== LT
) ? LE
: LEU
;
2520 /* It will be useful to be able to tell the difference once more in
2521 LE -> NE reduction. */
2527 /* Take care of trivially infinite loops. */
2530 if (iv0
.step
== const0_rtx
)
2532 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2533 if (rtx_equal_p (tmp
, mode_mmin
))
2536 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2537 /* Fill in the remaining fields somehow. */
2538 goto zero_iter_simplify
;
2543 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2544 if (rtx_equal_p (tmp
, mode_mmax
))
2547 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2548 /* Fill in the remaining fields somehow. */
2549 goto zero_iter_simplify
;
2554 /* If we can we want to take care of NE conditions instead of size
2555 comparisons, as they are much more friendly (most importantly
2556 this takes care of special handling of loops with step 1). We can
2557 do it if we first check that upper bound is greater or equal to
2558 lower bound, their difference is constant c modulo step and that
2559 there is not an overflow. */
2562 if (iv0
.step
== const0_rtx
)
2563 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2566 step
= lowpart_subreg (mode
, step
, comp_mode
);
2567 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2568 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2569 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2570 may_xform
= const0_rtx
;
2571 may_not_xform
= const_true_rtx
;
2573 if (CONST_INT_P (delta
))
2575 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2577 /* A special case. We have transformed condition of type
2578 for (i = 0; i < 4; i += 4)
2580 for (i = 0; i <= 3; i += 4)
2581 obviously if the test for overflow during that transformation
2582 passed, we cannot overflow here. Most importantly any
2583 loop with sharp end condition and step 1 falls into this
2584 category, so handling this case specially is definitely
2585 worth the troubles. */
2586 may_xform
= const_true_rtx
;
2588 else if (iv0
.step
== const0_rtx
)
2590 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2591 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2592 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2593 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2594 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2596 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2602 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2603 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2604 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2605 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2606 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2608 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2614 if (may_xform
!= const0_rtx
)
2616 /* We perform the transformation always provided that it is not
2617 completely senseless. This is OK, as we would need this assumption
2618 to determine the number of iterations anyway. */
2619 if (may_xform
!= const_true_rtx
)
2621 /* If the step is a power of two and the final value we have
2622 computed overflows, the cycle is infinite. Otherwise it
2623 is nontrivial to compute the number of iterations. */
2625 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2628 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2632 /* We are going to lose some information about upper bound on
2633 number of iterations in this step, so record the information
2635 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2636 if (CONST_INT_P (iv1
.base
))
2637 up
= INTVAL (iv1
.base
);
2639 up
= INTVAL (mode_mmax
) - inc
;
2640 down
= INTVAL (CONST_INT_P (iv0
.base
)
2643 max
= (uint64_t) (up
- down
) / inc
+ 1;
2645 && !desc
->assumptions
)
2646 record_niter_bound (loop
, max
, false, true);
2648 if (iv0
.step
== const0_rtx
)
2650 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2651 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2655 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2656 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2659 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2660 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2661 assumption
= simplify_gen_relational (reverse_condition (cond
),
2662 SImode
, mode
, tmp0
, tmp1
);
2663 if (assumption
== const_true_rtx
)
2664 goto zero_iter_simplify
;
2665 else if (assumption
!= const0_rtx
)
2666 desc
->noloop_assumptions
=
2667 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2672 /* Count the number of iterations. */
2675 /* Everything we do here is just arithmetics modulo size of mode. This
2676 makes us able to do more involved computations of number of iterations
2677 than in other cases. First transform the condition into shape
2678 s * i <> c, with s positive. */
2679 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2680 iv0
.base
= const0_rtx
;
2681 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2682 iv1
.step
= const0_rtx
;
2683 if (INTVAL (iv0
.step
) < 0)
2685 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2686 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2688 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2690 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2691 is infinite. Otherwise, the number of iterations is
2692 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2693 s
= INTVAL (iv0
.step
); d
= 1;
2700 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2702 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2703 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2704 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2705 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2707 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2708 inv
= inverse (s
, size
);
2709 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2710 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2714 if (iv1
.step
== const0_rtx
)
2715 /* Condition in shape a + s * i <= b
2716 We must know that b + s does not overflow and a <= b + s and then we
2717 can compute number of iterations as (b + s - a) / s. (It might
2718 seem that we in fact could be more clever about testing the b + s
2719 overflow condition using some information about b - a mod s,
2720 but it was already taken into account during LE -> NE transform). */
2723 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2724 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2726 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2727 lowpart_subreg (mode
, step
,
2733 /* If s is power of 2, we know that the loop is infinite if
2734 a % s <= b % s and b + s overflows. */
2735 assumption
= simplify_gen_relational (reverse_condition (cond
),
2739 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2740 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2741 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2742 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2744 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2748 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2751 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2754 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2755 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2756 assumption
= simplify_gen_relational (reverse_condition (cond
),
2757 SImode
, mode
, tmp0
, tmp
);
2759 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2760 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2764 /* Condition in shape a <= b - s * i
2765 We must know that a - s does not overflow and a - s <= b and then
2766 we can again compute number of iterations as (b - (a - s)) / s. */
2767 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2768 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2769 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2771 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2772 lowpart_subreg (mode
, step
, comp_mode
));
2777 /* If s is power of 2, we know that the loop is infinite if
2778 a % s <= b % s and a - s overflows. */
2779 assumption
= simplify_gen_relational (reverse_condition (cond
),
2783 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2784 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2785 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2786 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2788 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2792 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2795 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2798 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2799 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2800 assumption
= simplify_gen_relational (reverse_condition (cond
),
2803 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2804 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2806 if (assumption
== const_true_rtx
)
2807 goto zero_iter_simplify
;
2808 else if (assumption
!= const0_rtx
)
2809 desc
->noloop_assumptions
=
2810 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2811 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2812 desc
->niter_expr
= delta
;
2815 old_niter
= desc
->niter_expr
;
2817 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2818 if (desc
->assumptions
2819 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2821 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2822 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2823 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2825 /* Rerun the simplification. Consider code (created by copying loop headers)
2837 The first pass determines that i = 0, the second pass uses it to eliminate
2838 noloop assumption. */
2840 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2841 if (desc
->assumptions
2842 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2844 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2845 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2846 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2848 if (desc
->noloop_assumptions
2849 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2852 if (CONST_INT_P (desc
->niter_expr
))
2854 uint64_t val
= INTVAL (desc
->niter_expr
);
2856 desc
->const_iter
= true;
2857 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2859 && !desc
->assumptions
)
2860 record_niter_bound (loop
, desc
->niter
, false, true);
2864 max
= determine_max_iter (loop
, desc
, old_niter
);
2866 goto zero_iter_simplify
;
2868 && !desc
->assumptions
)
2869 record_niter_bound (loop
, max
, false, true);
2871 /* simplify_using_initial_values does a copy propagation on the registers
2872 in the expression for the number of iterations. This prolongs life
2873 ranges of registers and increases register pressure, and usually
2874 brings no gain (and if it happens to do, the cse pass will take care
2875 of it anyway). So prevent this behavior, unless it enabled us to
2876 derive that the number of iterations is a constant. */
2877 desc
->niter_expr
= old_niter
;
2883 /* Simplify the assumptions. */
2884 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2885 if (desc
->assumptions
2886 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2888 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2892 desc
->const_iter
= true;
2894 record_niter_bound (loop
, 0, true, true);
2895 desc
->noloop_assumptions
= NULL_RTX
;
2896 desc
->niter_expr
= const0_rtx
;
2900 desc
->simple_p
= false;
2904 /* Checks whether E is a simple exit from LOOP and stores its description
2908 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2910 basic_block exit_bb
;
2916 desc
->simple_p
= false;
2918 /* It must belong directly to the loop. */
2919 if (exit_bb
->loop_father
!= loop
)
2922 /* It must be tested (at least) once during any iteration. */
2923 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2926 /* It must end in a simple conditional jump. */
2927 if (!any_condjump_p (BB_END (exit_bb
)))
2930 ein
= EDGE_SUCC (exit_bb
, 0);
2932 ein
= EDGE_SUCC (exit_bb
, 1);
2935 desc
->in_edge
= ein
;
2937 /* Test whether the condition is suitable. */
2938 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2941 if (ein
->flags
& EDGE_FALLTHRU
)
2943 condition
= reversed_condition (condition
);
2948 /* Check that we are able to determine number of iterations and fill
2949 in information about it. */
2950 iv_number_of_iterations (loop
, at
, condition
, desc
);
2953 /* Finds a simple exit of LOOP and stores its description into DESC. */
2956 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2961 struct niter_desc act
;
2965 desc
->simple_p
= false;
2966 body
= get_loop_body (loop
);
2968 for (i
= 0; i
< loop
->num_nodes
; i
++)
2970 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2972 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2975 check_simple_exit (loop
, e
, &act
);
2983 /* Prefer constant iterations; the less the better. */
2985 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2988 /* Also if the actual exit may be infinite, while the old one
2989 not, prefer the old one. */
2990 if (act
.infinite
&& !desc
->infinite
)
3002 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
3003 fprintf (dump_file
, " simple exit %d -> %d\n",
3004 desc
->out_edge
->src
->index
,
3005 desc
->out_edge
->dest
->index
);
3006 if (desc
->assumptions
)
3008 fprintf (dump_file
, " assumptions: ");
3009 print_rtl (dump_file
, desc
->assumptions
);
3010 fprintf (dump_file
, "\n");
3012 if (desc
->noloop_assumptions
)
3014 fprintf (dump_file
, " does not roll if: ");
3015 print_rtl (dump_file
, desc
->noloop_assumptions
);
3016 fprintf (dump_file
, "\n");
3020 fprintf (dump_file
, " infinite if: ");
3021 print_rtl (dump_file
, desc
->infinite
);
3022 fprintf (dump_file
, "\n");
3025 fprintf (dump_file
, " number of iterations: ");
3026 print_rtl (dump_file
, desc
->niter_expr
);
3027 fprintf (dump_file
, "\n");
3029 fprintf (dump_file
, " upper bound: %li\n",
3030 (long)get_max_loop_iterations_int (loop
));
3031 fprintf (dump_file
, " realistic bound: %li\n",
3032 (long)get_estimated_loop_iterations_int (loop
));
3035 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3041 /* Creates a simple loop description of LOOP if it was not computed
3045 get_simple_loop_desc (struct loop
*loop
)
3047 struct niter_desc
*desc
= simple_loop_desc (loop
);
3052 /* At least desc->infinite is not always initialized by
3053 find_simple_loop_exit. */
3054 desc
= ggc_cleared_alloc
<niter_desc
> ();
3055 iv_analysis_loop_init (loop
);
3056 find_simple_exit (loop
, desc
);
3057 loop
->simple_loop_desc
= desc
;
3059 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3061 const char *wording
;
3063 /* Assume that no overflow happens and that the loop is finite.
3064 We already warned at the tree level if we ran optimizations there. */
3065 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3070 flag_unsafe_loop_optimizations
3071 ? N_("assuming that the loop is not infinite")
3072 : N_("cannot optimize possibly infinite loops");
3073 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3076 if (desc
->assumptions
)
3079 flag_unsafe_loop_optimizations
3080 ? N_("assuming that the loop counter does not overflow")
3081 : N_("cannot optimize loop, the loop counter may overflow");
3082 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3087 if (flag_unsafe_loop_optimizations
)
3089 desc
->assumptions
= NULL_RTX
;
3090 desc
->infinite
= NULL_RTX
;
3097 /* Releases simple loop description for LOOP. */
3100 free_simple_loop_desc (struct loop
*loop
)
3102 struct niter_desc
*desc
= simple_loop_desc (loop
);
3108 loop
->simple_loop_desc
= NULL
;