1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
57 #include "basic-block.h"
61 #include "diagnostic-core.h"
63 #include "hash-table.h"
67 /* Possible return values of iv_get_reaching_def. */
71 /* More than one reaching def, or reaching def that does not
75 /* The use is trivial invariant of the loop, i.e. is not changed
79 /* The use is reached by initial value and a value from the
80 previous iteration. */
83 /* The use has single dominating def. */
87 /* Information about a biv. */
91 unsigned regno
; /* The register of the biv. */
92 struct rtx_iv iv
; /* Value of the biv. */
95 static bool clean_slate
= true;
97 static unsigned int iv_ref_table_size
= 0;
99 /* Table of rtx_ivs indexed by the df_ref uid field. */
100 static struct rtx_iv
** iv_ref_table
;
102 /* Induction variable stored at the reference. */
103 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
104 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
106 /* The current loop. */
108 static struct loop
*current_loop
;
110 /* Hashtable helper. */
112 struct biv_entry_hasher
: typed_free_remove
<biv_entry
>
114 typedef biv_entry value_type
;
115 typedef rtx_def compare_type
;
116 static inline hashval_t
hash (const value_type
*);
117 static inline bool equal (const value_type
*, const compare_type
*);
120 /* Returns hash value for biv B. */
123 biv_entry_hasher::hash (const value_type
*b
)
128 /* Compares biv B and register R. */
131 biv_entry_hasher::equal (const value_type
*b
, const compare_type
*r
)
133 return b
->regno
== REGNO (r
);
136 /* Bivs of the current loop. */
138 static hash_table
<biv_entry_hasher
> *bivs
;
140 static bool iv_analyze_op (rtx_insn
*, rtx
, struct rtx_iv
*);
142 /* Return the RTX code corresponding to the IV extend code EXTEND. */
143 static inline enum rtx_code
144 iv_extend_to_rtx_code (enum iv_extend_code extend
)
152 case IV_UNKNOWN_EXTEND
:
158 /* Dumps information about IV to FILE. */
160 extern void dump_iv_info (FILE *, struct rtx_iv
*);
162 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
166 fprintf (file
, "not simple");
170 if (iv
->step
== const0_rtx
171 && !iv
->first_special
)
172 fprintf (file
, "invariant ");
174 print_rtl (file
, iv
->base
);
175 if (iv
->step
!= const0_rtx
)
177 fprintf (file
, " + ");
178 print_rtl (file
, iv
->step
);
179 fprintf (file
, " * iteration");
181 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
183 if (iv
->mode
!= iv
->extend_mode
)
184 fprintf (file
, " %s to %s",
185 rtx_name
[iv_extend_to_rtx_code (iv
->extend
)],
186 GET_MODE_NAME (iv
->extend_mode
));
188 if (iv
->mult
!= const1_rtx
)
190 fprintf (file
, " * ");
191 print_rtl (file
, iv
->mult
);
193 if (iv
->delta
!= const0_rtx
)
195 fprintf (file
, " + ");
196 print_rtl (file
, iv
->delta
);
198 if (iv
->first_special
)
199 fprintf (file
, " (first special)");
202 /* Generates a subreg to get the least significant part of EXPR (in mode
203 INNER_MODE) to OUTER_MODE. */
206 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
207 enum machine_mode inner_mode
)
209 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
210 subreg_lowpart_offset (outer_mode
, inner_mode
));
214 check_iv_ref_table_size (void)
216 if (iv_ref_table_size
< DF_DEFS_TABLE_SIZE ())
218 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
219 iv_ref_table
= XRESIZEVEC (struct rtx_iv
*, iv_ref_table
, new_size
);
220 memset (&iv_ref_table
[iv_ref_table_size
], 0,
221 (new_size
- iv_ref_table_size
) * sizeof (struct rtx_iv
*));
222 iv_ref_table_size
= new_size
;
227 /* Checks whether REG is a well-behaved register. */
230 simple_reg_p (rtx reg
)
234 if (GET_CODE (reg
) == SUBREG
)
236 if (!subreg_lowpart_p (reg
))
238 reg
= SUBREG_REG (reg
);
245 if (HARD_REGISTER_NUM_P (r
))
248 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
254 /* Clears the information about ivs stored in df. */
259 unsigned i
, n_defs
= DF_DEFS_TABLE_SIZE ();
262 check_iv_ref_table_size ();
263 for (i
= 0; i
< n_defs
; i
++)
265 iv
= iv_ref_table
[i
];
269 iv_ref_table
[i
] = NULL
;
277 /* Prepare the data for an induction variable analysis of a LOOP. */
280 iv_analysis_loop_init (struct loop
*loop
)
284 /* Clear the information from the analysis of the previous loop. */
287 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
288 bivs
= new hash_table
<biv_entry_hasher
> (10);
294 /* Get rid of the ud chains before processing the rescans. Then add
296 df_remove_problem (df_chain
);
297 df_process_deferred_rescans ();
298 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
299 df_chain_add_problem (DF_UD_CHAIN
);
300 df_note_add_problem ();
301 df_analyze_loop (loop
);
303 df_dump_region (dump_file
);
305 check_iv_ref_table_size ();
308 /* Finds the definition of REG that dominates loop latch and stores
309 it to DEF. Returns false if there is not a single definition
310 dominating the latch. If REG has no definition in loop, DEF
311 is set to NULL and true is returned. */
314 latch_dominating_def (rtx reg
, df_ref
*def
)
316 df_ref single_rd
= NULL
, adef
;
317 unsigned regno
= REGNO (reg
);
318 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (current_loop
->latch
);
320 for (adef
= DF_REG_DEF_CHAIN (regno
); adef
; adef
= DF_REF_NEXT_REG (adef
))
322 if (!bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (adef
))
323 || !bitmap_bit_p (&bb_info
->out
, DF_REF_ID (adef
)))
326 /* More than one reaching definition. */
330 if (!just_once_each_iteration_p (current_loop
, DF_REF_BB (adef
)))
340 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
342 static enum iv_grd_result
343 iv_get_reaching_def (rtx_insn
*insn
, rtx reg
, df_ref
*def
)
346 basic_block def_bb
, use_bb
;
351 if (!simple_reg_p (reg
))
353 if (GET_CODE (reg
) == SUBREG
)
354 reg
= SUBREG_REG (reg
);
355 gcc_assert (REG_P (reg
));
357 use
= df_find_use (insn
, reg
);
358 gcc_assert (use
!= NULL
);
360 if (!DF_REF_CHAIN (use
))
361 return GRD_INVARIANT
;
363 /* More than one reaching def. */
364 if (DF_REF_CHAIN (use
)->next
)
367 adef
= DF_REF_CHAIN (use
)->ref
;
369 /* We do not handle setting only part of the register. */
370 if (DF_REF_FLAGS (adef
) & DF_REF_READ_WRITE
)
373 def_insn
= DF_REF_INSN (adef
);
374 def_bb
= DF_REF_BB (adef
);
375 use_bb
= BLOCK_FOR_INSN (insn
);
377 if (use_bb
== def_bb
)
378 dom_p
= (DF_INSN_LUID (def_insn
) < DF_INSN_LUID (insn
));
380 dom_p
= dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
);
385 return GRD_SINGLE_DOM
;
388 /* The definition does not dominate the use. This is still OK if
389 this may be a use of a biv, i.e. if the def_bb dominates loop
391 if (just_once_each_iteration_p (current_loop
, def_bb
))
392 return GRD_MAYBE_BIV
;
397 /* Sets IV to invariant CST in MODE. Always returns true (just for
398 consistency with other iv manipulation functions that may fail). */
401 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
403 if (mode
== VOIDmode
)
404 mode
= GET_MODE (cst
);
408 iv
->step
= const0_rtx
;
409 iv
->first_special
= false;
410 iv
->extend
= IV_UNKNOWN_EXTEND
;
411 iv
->extend_mode
= iv
->mode
;
412 iv
->delta
= const0_rtx
;
413 iv
->mult
= const1_rtx
;
418 /* Evaluates application of subreg to MODE on IV. */
421 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
423 /* If iv is invariant, just calculate the new value. */
424 if (iv
->step
== const0_rtx
425 && !iv
->first_special
)
427 rtx val
= get_iv_value (iv
, const0_rtx
);
428 val
= lowpart_subreg (mode
, val
,
429 iv
->extend
== IV_UNKNOWN_EXTEND
430 ? iv
->mode
: iv
->extend_mode
);
433 iv
->extend
= IV_UNKNOWN_EXTEND
;
434 iv
->mode
= iv
->extend_mode
= mode
;
435 iv
->delta
= const0_rtx
;
436 iv
->mult
= const1_rtx
;
440 if (iv
->extend_mode
== mode
)
443 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
446 iv
->extend
= IV_UNKNOWN_EXTEND
;
449 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
450 simplify_gen_binary (MULT
, iv
->extend_mode
,
451 iv
->base
, iv
->mult
));
452 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
453 iv
->mult
= const1_rtx
;
454 iv
->delta
= const0_rtx
;
455 iv
->first_special
= false;
460 /* Evaluates application of EXTEND to MODE on IV. */
463 iv_extend (struct rtx_iv
*iv
, enum iv_extend_code extend
, enum machine_mode mode
)
465 /* If iv is invariant, just calculate the new value. */
466 if (iv
->step
== const0_rtx
467 && !iv
->first_special
)
469 rtx val
= get_iv_value (iv
, const0_rtx
);
470 if (iv
->extend_mode
!= iv
->mode
471 && iv
->extend
!= IV_UNKNOWN_EXTEND
472 && iv
->extend
!= extend
)
473 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
474 val
= simplify_gen_unary (iv_extend_to_rtx_code (extend
), mode
,
477 ? iv
->extend_mode
: iv
->mode
);
479 iv
->extend
= IV_UNKNOWN_EXTEND
;
480 iv
->mode
= iv
->extend_mode
= mode
;
481 iv
->delta
= const0_rtx
;
482 iv
->mult
= const1_rtx
;
486 if (mode
!= iv
->extend_mode
)
489 if (iv
->extend
!= IV_UNKNOWN_EXTEND
490 && iv
->extend
!= extend
)
498 /* Evaluates negation of IV. */
501 iv_neg (struct rtx_iv
*iv
)
503 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
505 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
506 iv
->base
, iv
->extend_mode
);
507 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
508 iv
->step
, iv
->extend_mode
);
512 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
513 iv
->delta
, iv
->extend_mode
);
514 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
515 iv
->mult
, iv
->extend_mode
);
521 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
524 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
526 enum machine_mode mode
;
529 /* Extend the constant to extend_mode of the other operand if necessary. */
530 if (iv0
->extend
== IV_UNKNOWN_EXTEND
531 && iv0
->mode
== iv0
->extend_mode
532 && iv0
->step
== const0_rtx
533 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
535 iv0
->extend_mode
= iv1
->extend_mode
;
536 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
537 iv0
->base
, iv0
->mode
);
539 if (iv1
->extend
== IV_UNKNOWN_EXTEND
540 && iv1
->mode
== iv1
->extend_mode
541 && iv1
->step
== const0_rtx
542 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
544 iv1
->extend_mode
= iv0
->extend_mode
;
545 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
546 iv1
->base
, iv1
->mode
);
549 mode
= iv0
->extend_mode
;
550 if (mode
!= iv1
->extend_mode
)
553 if (iv0
->extend
== IV_UNKNOWN_EXTEND
554 && iv1
->extend
== IV_UNKNOWN_EXTEND
)
556 if (iv0
->mode
!= iv1
->mode
)
559 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
560 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
565 /* Handle addition of constant. */
566 if (iv1
->extend
== IV_UNKNOWN_EXTEND
568 && iv1
->step
== const0_rtx
)
570 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
574 if (iv0
->extend
== IV_UNKNOWN_EXTEND
576 && iv0
->step
== const0_rtx
)
584 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
591 /* Evaluates multiplication of IV by constant CST. */
594 iv_mult (struct rtx_iv
*iv
, rtx mby
)
596 enum machine_mode mode
= iv
->extend_mode
;
598 if (GET_MODE (mby
) != VOIDmode
599 && GET_MODE (mby
) != mode
)
602 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
604 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
605 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
609 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
610 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
616 /* Evaluates shift of IV by constant CST. */
619 iv_shift (struct rtx_iv
*iv
, rtx mby
)
621 enum machine_mode mode
= iv
->extend_mode
;
623 if (GET_MODE (mby
) != VOIDmode
624 && GET_MODE (mby
) != mode
)
627 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
629 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
630 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
634 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
635 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
641 /* The recursive part of get_biv_step. Gets the value of the single value
642 defined by DEF wrto initial value of REG inside loop, in shape described
646 get_biv_step_1 (df_ref def
, rtx reg
,
647 rtx
*inner_step
, enum machine_mode
*inner_mode
,
648 enum iv_extend_code
*extend
, enum machine_mode outer_mode
,
651 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
652 rtx next
, nextr
, tmp
;
654 rtx_insn
*insn
= DF_REF_INSN (def
);
656 enum iv_grd_result res
;
658 set
= single_set (insn
);
662 rhs
= find_reg_equal_equiv_note (insn
);
668 code
= GET_CODE (rhs
);
681 if (code
== PLUS
&& CONSTANT_P (op0
))
683 tmp
= op0
; op0
= op1
; op1
= tmp
;
686 if (!simple_reg_p (op0
)
687 || !CONSTANT_P (op1
))
690 if (GET_MODE (rhs
) != outer_mode
)
692 /* ppc64 uses expressions like
694 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
696 this is equivalent to
698 (set x':DI (plus:DI y:DI 1))
699 (set x:SI (subreg:SI (x':DI)). */
700 if (GET_CODE (op0
) != SUBREG
)
702 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
711 if (GET_MODE (rhs
) != outer_mode
)
715 if (!simple_reg_p (op0
))
725 if (GET_CODE (next
) == SUBREG
)
727 if (!subreg_lowpart_p (next
))
730 nextr
= SUBREG_REG (next
);
731 if (GET_MODE (nextr
) != outer_mode
)
737 res
= iv_get_reaching_def (insn
, nextr
, &next_def
);
739 if (res
== GRD_INVALID
|| res
== GRD_INVARIANT
)
742 if (res
== GRD_MAYBE_BIV
)
744 if (!rtx_equal_p (nextr
, reg
))
747 *inner_step
= const0_rtx
;
748 *extend
= IV_UNKNOWN_EXTEND
;
749 *inner_mode
= outer_mode
;
750 *outer_step
= const0_rtx
;
752 else if (!get_biv_step_1 (next_def
, reg
,
753 inner_step
, inner_mode
, extend
, outer_mode
,
757 if (GET_CODE (next
) == SUBREG
)
759 enum machine_mode amode
= GET_MODE (next
);
761 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
765 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
766 *inner_step
, *outer_step
);
767 *outer_step
= const0_rtx
;
768 *extend
= IV_UNKNOWN_EXTEND
;
779 if (*inner_mode
== outer_mode
780 /* See comment in previous switch. */
781 || GET_MODE (rhs
) != outer_mode
)
782 *inner_step
= simplify_gen_binary (code
, outer_mode
,
785 *outer_step
= simplify_gen_binary (code
, outer_mode
,
791 gcc_assert (GET_MODE (op0
) == *inner_mode
792 && *extend
== IV_UNKNOWN_EXTEND
793 && *outer_step
== const0_rtx
);
795 *extend
= (code
== SIGN_EXTEND
) ? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
805 /* Gets the operation on register REG inside loop, in shape
807 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
809 If the operation cannot be described in this shape, return false.
810 LAST_DEF is the definition of REG that dominates loop latch. */
813 get_biv_step (df_ref last_def
, rtx reg
, rtx
*inner_step
,
814 enum machine_mode
*inner_mode
, enum iv_extend_code
*extend
,
815 enum machine_mode
*outer_mode
, rtx
*outer_step
)
817 *outer_mode
= GET_MODE (reg
);
819 if (!get_biv_step_1 (last_def
, reg
,
820 inner_step
, inner_mode
, extend
, *outer_mode
,
824 gcc_assert ((*inner_mode
== *outer_mode
) != (*extend
!= IV_UNKNOWN_EXTEND
));
825 gcc_assert (*inner_mode
!= *outer_mode
|| *outer_step
== const0_rtx
);
830 /* Records information that DEF is induction variable IV. */
833 record_iv (df_ref def
, struct rtx_iv
*iv
)
835 struct rtx_iv
*recorded_iv
= XNEW (struct rtx_iv
);
838 check_iv_ref_table_size ();
839 DF_REF_IV_SET (def
, recorded_iv
);
842 /* If DEF was already analyzed for bivness, store the description of the biv to
843 IV and return true. Otherwise return false. */
846 analyzed_for_bivness_p (rtx def
, struct rtx_iv
*iv
)
848 struct biv_entry
*biv
= bivs
->find_with_hash (def
, REGNO (def
));
858 record_biv (rtx def
, struct rtx_iv
*iv
)
860 struct biv_entry
*biv
= XNEW (struct biv_entry
);
861 biv_entry
**slot
= bivs
->find_slot_with_hash (def
, REGNO (def
), INSERT
);
863 biv
->regno
= REGNO (def
);
869 /* Determines whether DEF is a biv and if so, stores its description
873 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
875 rtx inner_step
, outer_step
;
876 enum machine_mode inner_mode
, outer_mode
;
877 enum iv_extend_code extend
;
882 fprintf (dump_file
, "Analyzing ");
883 print_rtl (dump_file
, def
);
884 fprintf (dump_file
, " for bivness.\n");
889 if (!CONSTANT_P (def
))
892 return iv_constant (iv
, def
, VOIDmode
);
895 if (!latch_dominating_def (def
, &last_def
))
898 fprintf (dump_file
, " not simple.\n");
903 return iv_constant (iv
, def
, VOIDmode
);
905 if (analyzed_for_bivness_p (def
, iv
))
908 fprintf (dump_file
, " already analysed.\n");
909 return iv
->base
!= NULL_RTX
;
912 if (!get_biv_step (last_def
, def
, &inner_step
, &inner_mode
, &extend
,
913 &outer_mode
, &outer_step
))
919 /* Loop transforms base to es (base + inner_step) + outer_step,
920 where es means extend of subreg between inner_mode and outer_mode.
921 The corresponding induction variable is
923 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
925 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
926 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
927 iv
->mode
= inner_mode
;
928 iv
->extend_mode
= outer_mode
;
930 iv
->mult
= const1_rtx
;
931 iv
->delta
= outer_step
;
932 iv
->first_special
= inner_mode
!= outer_mode
;
937 fprintf (dump_file
, " ");
938 dump_iv_info (dump_file
, iv
);
939 fprintf (dump_file
, "\n");
942 record_biv (def
, iv
);
943 return iv
->base
!= NULL_RTX
;
946 /* Analyzes expression RHS used at INSN and stores the result to *IV.
947 The mode of the induction variable is MODE. */
950 iv_analyze_expr (rtx_insn
*insn
, rtx rhs
, enum machine_mode mode
,
953 rtx mby
= NULL_RTX
, tmp
;
954 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
955 struct rtx_iv iv0
, iv1
;
956 enum rtx_code code
= GET_CODE (rhs
);
957 enum machine_mode omode
= mode
;
963 gcc_assert (GET_MODE (rhs
) == mode
|| GET_MODE (rhs
) == VOIDmode
);
969 if (!iv_analyze_op (insn
, rhs
, iv
))
972 if (iv
->mode
== VOIDmode
)
975 iv
->extend_mode
= mode
;
991 omode
= GET_MODE (op0
);
1001 op0
= XEXP (rhs
, 0);
1002 mby
= XEXP (rhs
, 1);
1003 if (!CONSTANT_P (mby
))
1009 if (!CONSTANT_P (mby
))
1014 op0
= XEXP (rhs
, 0);
1015 mby
= XEXP (rhs
, 1);
1016 if (!CONSTANT_P (mby
))
1025 && !iv_analyze_expr (insn
, op0
, omode
, &iv0
))
1029 && !iv_analyze_expr (insn
, op1
, omode
, &iv1
))
1035 if (!iv_extend (&iv0
, IV_SIGN_EXTEND
, mode
))
1040 if (!iv_extend (&iv0
, IV_ZERO_EXTEND
, mode
))
1051 if (!iv_add (&iv0
, &iv1
, code
))
1056 if (!iv_mult (&iv0
, mby
))
1061 if (!iv_shift (&iv0
, mby
))
1070 return iv
->base
!= NULL_RTX
;
1073 /* Analyzes iv DEF and stores the result to *IV. */
1076 iv_analyze_def (df_ref def
, struct rtx_iv
*iv
)
1078 rtx_insn
*insn
= DF_REF_INSN (def
);
1079 rtx reg
= DF_REF_REG (def
);
1084 fprintf (dump_file
, "Analyzing def of ");
1085 print_rtl (dump_file
, reg
);
1086 fprintf (dump_file
, " in insn ");
1087 print_rtl_single (dump_file
, insn
);
1090 check_iv_ref_table_size ();
1091 if (DF_REF_IV (def
))
1094 fprintf (dump_file
, " already analysed.\n");
1095 *iv
= *DF_REF_IV (def
);
1096 return iv
->base
!= NULL_RTX
;
1099 iv
->mode
= VOIDmode
;
1100 iv
->base
= NULL_RTX
;
1101 iv
->step
= NULL_RTX
;
1106 set
= single_set (insn
);
1110 if (!REG_P (SET_DEST (set
)))
1113 gcc_assert (SET_DEST (set
) == reg
);
1114 rhs
= find_reg_equal_equiv_note (insn
);
1116 rhs
= XEXP (rhs
, 0);
1118 rhs
= SET_SRC (set
);
1120 iv_analyze_expr (insn
, rhs
, GET_MODE (reg
), iv
);
1121 record_iv (def
, iv
);
1125 print_rtl (dump_file
, reg
);
1126 fprintf (dump_file
, " in insn ");
1127 print_rtl_single (dump_file
, insn
);
1128 fprintf (dump_file
, " is ");
1129 dump_iv_info (dump_file
, iv
);
1130 fprintf (dump_file
, "\n");
1133 return iv
->base
!= NULL_RTX
;
1136 /* Analyzes operand OP of INSN and stores the result to *IV. */
1139 iv_analyze_op (rtx_insn
*insn
, rtx op
, struct rtx_iv
*iv
)
1142 enum iv_grd_result res
;
1146 fprintf (dump_file
, "Analyzing operand ");
1147 print_rtl (dump_file
, op
);
1148 fprintf (dump_file
, " of insn ");
1149 print_rtl_single (dump_file
, insn
);
1152 if (function_invariant_p (op
))
1153 res
= GRD_INVARIANT
;
1154 else if (GET_CODE (op
) == SUBREG
)
1156 if (!subreg_lowpart_p (op
))
1159 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
1162 return iv_subreg (iv
, GET_MODE (op
));
1166 res
= iv_get_reaching_def (insn
, op
, &def
);
1167 if (res
== GRD_INVALID
)
1170 fprintf (dump_file
, " not simple.\n");
1175 if (res
== GRD_INVARIANT
)
1177 iv_constant (iv
, op
, VOIDmode
);
1181 fprintf (dump_file
, " ");
1182 dump_iv_info (dump_file
, iv
);
1183 fprintf (dump_file
, "\n");
1188 if (res
== GRD_MAYBE_BIV
)
1189 return iv_analyze_biv (op
, iv
);
1191 return iv_analyze_def (def
, iv
);
1194 /* Analyzes value VAL at INSN and stores the result to *IV. */
1197 iv_analyze (rtx_insn
*insn
, rtx val
, struct rtx_iv
*iv
)
1201 /* We must find the insn in that val is used, so that we get to UD chains.
1202 Since the function is sometimes called on result of get_condition,
1203 this does not necessarily have to be directly INSN; scan also the
1205 if (simple_reg_p (val
))
1207 if (GET_CODE (val
) == SUBREG
)
1208 reg
= SUBREG_REG (val
);
1212 while (!df_find_use (insn
, reg
))
1213 insn
= NEXT_INSN (insn
);
1216 return iv_analyze_op (insn
, val
, iv
);
1219 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1222 iv_analyze_result (rtx_insn
*insn
, rtx def
, struct rtx_iv
*iv
)
1226 adef
= df_find_def (insn
, def
);
1230 return iv_analyze_def (adef
, iv
);
1233 /* Checks whether definition of register REG in INSN is a basic induction
1234 variable. IV analysis must have been initialized (via a call to
1235 iv_analysis_loop_init) for this function to produce a result. */
1238 biv_p (rtx_insn
*insn
, rtx reg
)
1241 df_ref def
, last_def
;
1243 if (!simple_reg_p (reg
))
1246 def
= df_find_def (insn
, reg
);
1247 gcc_assert (def
!= NULL
);
1248 if (!latch_dominating_def (reg
, &last_def
))
1250 if (last_def
!= def
)
1253 if (!iv_analyze_biv (reg
, &iv
))
1256 return iv
.step
!= const0_rtx
;
1259 /* Calculates value of IV at ITERATION-th iteration. */
1262 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1266 /* We would need to generate some if_then_else patterns, and so far
1267 it is not needed anywhere. */
1268 gcc_assert (!iv
->first_special
);
1270 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1271 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1272 simplify_gen_binary (MULT
, iv
->extend_mode
,
1273 iv
->step
, iteration
));
1277 if (iv
->extend_mode
== iv
->mode
)
1280 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1282 if (iv
->extend
== IV_UNKNOWN_EXTEND
)
1285 val
= simplify_gen_unary (iv_extend_to_rtx_code (iv
->extend
),
1286 iv
->extend_mode
, val
, iv
->mode
);
1287 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1288 simplify_gen_binary (MULT
, iv
->extend_mode
,
1294 /* Free the data for an induction variable analysis. */
1297 iv_analysis_done (void)
1303 df_finish_pass (true);
1306 free (iv_ref_table
);
1307 iv_ref_table
= NULL
;
1308 iv_ref_table_size
= 0;
1312 /* Computes inverse to X modulo (1 << MOD). */
1315 inverse (uint64_t x
, int mod
)
1318 ((uint64_t) 1 << (mod
- 1) << 1) - 1;
1322 for (i
= 0; i
< mod
- 1; i
++)
1324 rslt
= (rslt
* x
) & mask
;
1331 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1334 altered_reg_used (rtx
*reg
, void *alt
)
1339 return REGNO_REG_SET_P ((bitmap
) alt
, REGNO (*reg
));
1342 /* Marks registers altered by EXPR in set ALT. */
1345 mark_altered (rtx expr
, const_rtx by ATTRIBUTE_UNUSED
, void *alt
)
1347 if (GET_CODE (expr
) == SUBREG
)
1348 expr
= SUBREG_REG (expr
);
1352 SET_REGNO_REG_SET ((bitmap
) alt
, REGNO (expr
));
1355 /* Checks whether RHS is simple enough to process. */
1358 simple_rhs_p (rtx rhs
)
1362 if (function_invariant_p (rhs
)
1363 || (REG_P (rhs
) && !HARD_REGISTER_P (rhs
)))
1366 switch (GET_CODE (rhs
))
1371 op0
= XEXP (rhs
, 0);
1372 op1
= XEXP (rhs
, 1);
1373 /* Allow reg OP const and reg OP reg. */
1374 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
))
1375 && !function_invariant_p (op0
))
1377 if (!(REG_P (op1
) && !HARD_REGISTER_P (op1
))
1378 && !function_invariant_p (op1
))
1387 op0
= XEXP (rhs
, 0);
1388 op1
= XEXP (rhs
, 1);
1389 /* Allow reg OP const. */
1390 if (!(REG_P (op0
) && !HARD_REGISTER_P (op0
)))
1392 if (!function_invariant_p (op1
))
1402 /* If REGNO has a single definition, return its known value, otherwise return
1406 find_single_def_src (unsigned int regno
)
1414 adef
= DF_REG_DEF_CHAIN (regno
);
1415 if (adef
== NULL
|| DF_REF_NEXT_REG (adef
) != NULL
1416 || DF_REF_IS_ARTIFICIAL (adef
))
1419 set
= single_set (DF_REF_INSN (adef
));
1420 if (set
== NULL
|| !REG_P (SET_DEST (set
))
1421 || REGNO (SET_DEST (set
)) != regno
)
1424 note
= find_reg_equal_equiv_note (DF_REF_INSN (adef
));
1426 if (note
&& function_invariant_p (XEXP (note
, 0)))
1428 src
= XEXP (note
, 0);
1431 src
= SET_SRC (set
);
1435 regno
= REGNO (src
);
1440 if (!function_invariant_p (src
))
1446 /* If any registers in *EXPR that have a single definition, try to replace
1447 them with the known-equivalent values. */
1450 replace_single_def_regs (rtx
*expr
)
1452 subrtx_var_iterator::array_type array
;
1454 FOR_EACH_SUBRTX_VAR (iter
, array
, *expr
, NONCONST
)
1458 if (rtx new_x
= find_single_def_src (REGNO (x
)))
1460 *expr
= simplify_replace_rtx (*expr
, x
, new_x
);
1466 /* A subroutine of simplify_using_initial_values, this function examines INSN
1467 to see if it contains a suitable set that we can use to make a replacement.
1468 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1469 the set; return false otherwise. */
1472 suitable_set_for_replacement (rtx_insn
*insn
, rtx
*dest
, rtx
*src
)
1474 rtx set
= single_set (insn
);
1475 rtx lhs
= NULL_RTX
, rhs
;
1480 lhs
= SET_DEST (set
);
1484 rhs
= find_reg_equal_equiv_note (insn
);
1486 rhs
= XEXP (rhs
, 0);
1488 rhs
= SET_SRC (set
);
1490 if (!simple_rhs_p (rhs
))
1498 /* Using the data returned by suitable_set_for_replacement, replace DEST
1499 with SRC in *EXPR and return the new expression. Also call
1500 replace_single_def_regs if the replacement changed something. */
1502 replace_in_expr (rtx
*expr
, rtx dest
, rtx src
)
1505 *expr
= simplify_replace_rtx (*expr
, dest
, src
);
1508 replace_single_def_regs (expr
);
1511 /* Checks whether A implies B. */
1514 implies_p (rtx a
, rtx b
)
1516 rtx op0
, op1
, opb0
, opb1
, r
;
1517 enum machine_mode mode
;
1519 if (rtx_equal_p (a
, b
))
1522 if (GET_CODE (a
) == EQ
)
1528 || (GET_CODE (op0
) == SUBREG
1529 && REG_P (SUBREG_REG (op0
))))
1531 r
= simplify_replace_rtx (b
, op0
, op1
);
1532 if (r
== const_true_rtx
)
1537 || (GET_CODE (op1
) == SUBREG
1538 && REG_P (SUBREG_REG (op1
))))
1540 r
= simplify_replace_rtx (b
, op1
, op0
);
1541 if (r
== const_true_rtx
)
1546 if (b
== const_true_rtx
)
1549 if ((GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMM_COMPARE
1550 && GET_RTX_CLASS (GET_CODE (a
)) != RTX_COMPARE
)
1551 || (GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMM_COMPARE
1552 && GET_RTX_CLASS (GET_CODE (b
)) != RTX_COMPARE
))
1560 mode
= GET_MODE (op0
);
1561 if (mode
!= GET_MODE (opb0
))
1563 else if (mode
== VOIDmode
)
1565 mode
= GET_MODE (op1
);
1566 if (mode
!= GET_MODE (opb1
))
1570 /* A < B implies A + 1 <= B. */
1571 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1572 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1575 if (GET_CODE (a
) == GT
)
1582 if (GET_CODE (b
) == GE
)
1589 if (SCALAR_INT_MODE_P (mode
)
1590 && rtx_equal_p (op1
, opb1
)
1591 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1596 /* A < B or A > B imply A != B. TODO: Likewise
1597 A + n < B implies A != B + n if neither wraps. */
1598 if (GET_CODE (b
) == NE
1599 && (GET_CODE (a
) == GT
|| GET_CODE (a
) == GTU
1600 || GET_CODE (a
) == LT
|| GET_CODE (a
) == LTU
))
1602 if (rtx_equal_p (op0
, opb0
)
1603 && rtx_equal_p (op1
, opb1
))
1607 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1608 if (GET_CODE (a
) == NE
1609 && op1
== const0_rtx
)
1611 if ((GET_CODE (b
) == GTU
1612 && opb1
== const0_rtx
)
1613 || (GET_CODE (b
) == GEU
1614 && opb1
== const1_rtx
))
1615 return rtx_equal_p (op0
, opb0
);
1618 /* A != N is equivalent to A - (N + 1) <u -1. */
1619 if (GET_CODE (a
) == NE
1620 && CONST_INT_P (op1
)
1621 && GET_CODE (b
) == LTU
1622 && opb1
== constm1_rtx
1623 && GET_CODE (opb0
) == PLUS
1624 && CONST_INT_P (XEXP (opb0
, 1))
1625 /* Avoid overflows. */
1626 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1627 != ((unsigned HOST_WIDE_INT
)1
1628 << (HOST_BITS_PER_WIDE_INT
- 1)) - 1)
1629 && INTVAL (XEXP (opb0
, 1)) + 1 == -INTVAL (op1
))
1630 return rtx_equal_p (op0
, XEXP (opb0
, 0));
1632 /* Likewise, A != N implies A - N > 0. */
1633 if (GET_CODE (a
) == NE
1634 && CONST_INT_P (op1
))
1636 if (GET_CODE (b
) == GTU
1637 && GET_CODE (opb0
) == PLUS
1638 && opb1
== const0_rtx
1639 && CONST_INT_P (XEXP (opb0
, 1))
1640 /* Avoid overflows. */
1641 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1642 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1643 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1644 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1645 if (GET_CODE (b
) == GEU
1646 && GET_CODE (opb0
) == PLUS
1647 && opb1
== const1_rtx
1648 && CONST_INT_P (XEXP (opb0
, 1))
1649 /* Avoid overflows. */
1650 && ((unsigned HOST_WIDE_INT
) INTVAL (XEXP (opb0
, 1))
1651 != ((unsigned HOST_WIDE_INT
) 1 << (HOST_BITS_PER_WIDE_INT
- 1)))
1652 && rtx_equal_p (XEXP (opb0
, 0), op0
))
1653 return INTVAL (op1
) == -INTVAL (XEXP (opb0
, 1));
1656 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1657 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == GE
)
1658 && CONST_INT_P (op1
)
1659 && ((GET_CODE (a
) == GT
&& op1
== constm1_rtx
)
1660 || INTVAL (op1
) >= 0)
1661 && GET_CODE (b
) == LTU
1662 && CONST_INT_P (opb1
)
1663 && rtx_equal_p (op0
, opb0
))
1664 return INTVAL (opb1
) < 0;
1669 /* Canonicalizes COND so that
1671 (1) Ensure that operands are ordered according to
1672 swap_commutative_operands_p.
1673 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1674 for GE, GEU, and LEU. */
1677 canon_condition (rtx cond
)
1682 enum machine_mode mode
;
1684 code
= GET_CODE (cond
);
1685 op0
= XEXP (cond
, 0);
1686 op1
= XEXP (cond
, 1);
1688 if (swap_commutative_operands_p (op0
, op1
))
1690 code
= swap_condition (code
);
1696 mode
= GET_MODE (op0
);
1697 if (mode
== VOIDmode
)
1698 mode
= GET_MODE (op1
);
1699 gcc_assert (mode
!= VOIDmode
);
1701 if (CONST_INT_P (op1
)
1702 && GET_MODE_CLASS (mode
) != MODE_CC
1703 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1705 HOST_WIDE_INT const_val
= INTVAL (op1
);
1706 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1707 unsigned HOST_WIDE_INT max_val
1708 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1713 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1714 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1717 /* When cross-compiling, const_val might be sign-extended from
1718 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1720 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1721 != (((HOST_WIDE_INT
) 1
1722 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1723 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1727 if (uconst_val
< max_val
)
1728 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1732 if (uconst_val
!= 0)
1733 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1741 if (op0
!= XEXP (cond
, 0)
1742 || op1
!= XEXP (cond
, 1)
1743 || code
!= GET_CODE (cond
)
1744 || GET_MODE (cond
) != SImode
)
1745 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1750 /* Reverses CONDition; returns NULL if we cannot. */
1753 reversed_condition (rtx cond
)
1755 enum rtx_code reversed
;
1756 reversed
= reversed_comparison_code (cond
, NULL
);
1757 if (reversed
== UNKNOWN
)
1760 return gen_rtx_fmt_ee (reversed
,
1761 GET_MODE (cond
), XEXP (cond
, 0),
1765 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1766 set of altered regs. */
1769 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1771 rtx rev
, reve
, exp
= *expr
;
1773 /* If some register gets altered later, we do not really speak about its
1774 value at the time of comparison. */
1776 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1779 if (GET_CODE (cond
) == EQ
1780 && REG_P (XEXP (cond
, 0)) && CONSTANT_P (XEXP (cond
, 1)))
1782 *expr
= simplify_replace_rtx (*expr
, XEXP (cond
, 0), XEXP (cond
, 1));
1786 if (!COMPARISON_P (exp
))
1789 rev
= reversed_condition (cond
);
1790 reve
= reversed_condition (exp
);
1792 cond
= canon_condition (cond
);
1793 exp
= canon_condition (exp
);
1795 rev
= canon_condition (rev
);
1797 reve
= canon_condition (reve
);
1799 if (rtx_equal_p (exp
, cond
))
1801 *expr
= const_true_rtx
;
1805 if (rev
&& rtx_equal_p (exp
, rev
))
1811 if (implies_p (cond
, exp
))
1813 *expr
= const_true_rtx
;
1817 if (reve
&& implies_p (cond
, reve
))
1823 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1825 if (rev
&& implies_p (exp
, rev
))
1831 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1832 if (rev
&& reve
&& implies_p (reve
, rev
))
1834 *expr
= const_true_rtx
;
1838 /* We would like to have some other tests here. TODO. */
1843 /* Use relationship between A and *B to eventually eliminate *B.
1844 OP is the operation we consider. */
1847 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1852 /* If A implies *B, we may replace *B by true. */
1853 if (implies_p (a
, *b
))
1854 *b
= const_true_rtx
;
1858 /* If *B implies A, we may replace *B by false. */
1859 if (implies_p (*b
, a
))
1868 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1869 operation we consider. */
1872 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1876 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1877 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1878 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1879 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1882 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1883 is a list, its elements are assumed to be combined using OP. */
1886 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1888 bool expression_valid
;
1889 rtx head
, tail
, last_valid_expr
;
1890 rtx_expr_list
*cond_list
;
1893 regset altered
, this_altered
;
1899 if (CONSTANT_P (*expr
))
1902 if (GET_CODE (*expr
) == EXPR_LIST
)
1904 head
= XEXP (*expr
, 0);
1905 tail
= XEXP (*expr
, 1);
1907 eliminate_implied_conditions (op
, &head
, tail
);
1912 neutral
= const_true_rtx
;
1917 neutral
= const0_rtx
;
1918 aggr
= const_true_rtx
;
1925 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1928 XEXP (*expr
, 0) = aggr
;
1929 XEXP (*expr
, 1) = NULL_RTX
;
1932 else if (head
== neutral
)
1935 simplify_using_initial_values (loop
, op
, expr
);
1938 simplify_using_initial_values (loop
, op
, &tail
);
1940 if (tail
&& XEXP (tail
, 0) == aggr
)
1946 XEXP (*expr
, 0) = head
;
1947 XEXP (*expr
, 1) = tail
;
1951 gcc_assert (op
== UNKNOWN
);
1953 replace_single_def_regs (expr
);
1954 if (CONSTANT_P (*expr
))
1957 e
= loop_preheader_edge (loop
);
1958 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1961 altered
= ALLOC_REG_SET (®_obstack
);
1962 this_altered
= ALLOC_REG_SET (®_obstack
);
1964 expression_valid
= true;
1965 last_valid_expr
= *expr
;
1969 insn
= BB_END (e
->src
);
1970 if (any_condjump_p (insn
))
1972 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1974 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1975 cond
= reversed_condition (cond
);
1979 simplify_using_condition (cond
, expr
, altered
);
1983 if (CONSTANT_P (*expr
))
1985 for (note
= cond_list
; note
; note
= XEXP (note
, 1))
1987 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
1988 if (CONSTANT_P (*expr
))
1992 cond_list
= alloc_EXPR_LIST (0, cond
, cond_list
);
1996 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
2004 CLEAR_REG_SET (this_altered
);
2005 note_stores (PATTERN (insn
), mark_altered
, this_altered
);
2008 /* Kill all call clobbered registers. */
2010 hard_reg_set_iterator hrsi
;
2011 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call
,
2013 SET_REGNO_REG_SET (this_altered
, i
);
2016 if (suitable_set_for_replacement (insn
, &dest
, &src
))
2018 rtx_expr_list
**pnote
, **pnote_next
;
2020 replace_in_expr (expr
, dest
, src
);
2021 if (CONSTANT_P (*expr
))
2024 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2027 rtx old_cond
= XEXP (note
, 0);
2029 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2030 replace_in_expr (&XEXP (note
, 0), dest
, src
);
2032 /* We can no longer use a condition that has been simplified
2033 to a constant, and simplify_using_condition will abort if
2035 if (CONSTANT_P (XEXP (note
, 0)))
2037 *pnote
= *pnote_next
;
2039 free_EXPR_LIST_node (note
);
2041 /* Retry simplifications with this condition if either the
2042 expression or the condition changed. */
2043 else if (old_cond
!= XEXP (note
, 0) || old
!= *expr
)
2044 simplify_using_condition (XEXP (note
, 0), expr
, altered
);
2049 rtx_expr_list
**pnote
, **pnote_next
;
2051 /* If we did not use this insn to make a replacement, any overlap
2052 between stores in this insn and our expression will cause the
2053 expression to become invalid. */
2054 if (for_each_rtx (expr
, altered_reg_used
, this_altered
))
2057 /* Likewise for the conditions. */
2058 for (pnote
= &cond_list
; *pnote
; pnote
= pnote_next
)
2061 rtx old_cond
= XEXP (note
, 0);
2063 pnote_next
= (rtx_expr_list
**)&XEXP (note
, 1);
2064 if (for_each_rtx (&old_cond
, altered_reg_used
, this_altered
))
2066 *pnote
= *pnote_next
;
2068 free_EXPR_LIST_node (note
);
2073 if (CONSTANT_P (*expr
))
2076 IOR_REG_SET (altered
, this_altered
);
2078 /* If the expression now contains regs that have been altered, we
2079 can't return it to the caller. However, it is still valid for
2080 further simplification, so keep searching to see if we can
2081 eventually turn it into a constant. */
2082 if (for_each_rtx (expr
, altered_reg_used
, altered
))
2083 expression_valid
= false;
2084 if (expression_valid
)
2085 last_valid_expr
= *expr
;
2088 if (!single_pred_p (e
->src
)
2089 || single_pred (e
->src
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2091 e
= single_pred_edge (e
->src
);
2095 free_EXPR_LIST_list (&cond_list
);
2096 if (!CONSTANT_P (*expr
))
2097 *expr
= last_valid_expr
;
2098 FREE_REG_SET (altered
);
2099 FREE_REG_SET (this_altered
);
2102 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2103 that IV occurs as left operands of comparison COND and its signedness
2104 is SIGNED_P to DESC. */
2107 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
2108 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
2110 rtx mmin
, mmax
, cond_over
, cond_under
;
2112 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
2113 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
2115 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
2124 if (cond_under
!= const0_rtx
)
2126 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2127 if (cond_over
!= const0_rtx
)
2128 desc
->noloop_assumptions
=
2129 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
2136 if (cond_over
!= const0_rtx
)
2138 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2139 if (cond_under
!= const0_rtx
)
2140 desc
->noloop_assumptions
=
2141 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
2145 if (cond_over
!= const0_rtx
)
2147 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
2148 if (cond_under
!= const0_rtx
)
2150 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
2158 iv
->extend
= signed_p
? IV_SIGN_EXTEND
: IV_ZERO_EXTEND
;
2161 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2162 subregs of the same mode if possible (sometimes it is necessary to add
2163 some assumptions to DESC). */
2166 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
2167 enum rtx_code cond
, struct niter_desc
*desc
)
2169 enum machine_mode comp_mode
;
2172 /* If the ivs behave specially in the first iteration, or are
2173 added/multiplied after extending, we ignore them. */
2174 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
2176 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
2179 /* If there is some extend, it must match signedness of the comparison. */
2184 if (iv0
->extend
== IV_ZERO_EXTEND
2185 || iv1
->extend
== IV_ZERO_EXTEND
)
2192 if (iv0
->extend
== IV_SIGN_EXTEND
2193 || iv1
->extend
== IV_SIGN_EXTEND
)
2199 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
2200 && iv1
->extend
!= IV_UNKNOWN_EXTEND
2201 && iv0
->extend
!= iv1
->extend
)
2205 if (iv0
->extend
!= IV_UNKNOWN_EXTEND
)
2206 signed_p
= iv0
->extend
== IV_SIGN_EXTEND
;
2207 if (iv1
->extend
!= IV_UNKNOWN_EXTEND
)
2208 signed_p
= iv1
->extend
== IV_SIGN_EXTEND
;
2215 /* Values of both variables should be computed in the same mode. These
2216 might indeed be different, if we have comparison like
2218 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2220 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2221 in different modes. This does not seem impossible to handle, but
2222 it hardly ever occurs in practice.
2224 The only exception is the case when one of operands is invariant.
2225 For example pentium 3 generates comparisons like
2226 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2227 definitely do not want this prevent the optimization. */
2228 comp_mode
= iv0
->extend_mode
;
2229 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
2230 comp_mode
= iv1
->extend_mode
;
2232 if (iv0
->extend_mode
!= comp_mode
)
2234 if (iv0
->mode
!= iv0
->extend_mode
2235 || iv0
->step
!= const0_rtx
)
2238 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2239 comp_mode
, iv0
->base
, iv0
->mode
);
2240 iv0
->extend_mode
= comp_mode
;
2243 if (iv1
->extend_mode
!= comp_mode
)
2245 if (iv1
->mode
!= iv1
->extend_mode
2246 || iv1
->step
!= const0_rtx
)
2249 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
2250 comp_mode
, iv1
->base
, iv1
->mode
);
2251 iv1
->extend_mode
= comp_mode
;
2254 /* Check that both ivs belong to a range of a single mode. If one of the
2255 operands is an invariant, we may need to shorten it into the common
2257 if (iv0
->mode
== iv0
->extend_mode
2258 && iv0
->step
== const0_rtx
2259 && iv0
->mode
!= iv1
->mode
)
2260 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
2262 if (iv1
->mode
== iv1
->extend_mode
2263 && iv1
->step
== const0_rtx
2264 && iv0
->mode
!= iv1
->mode
)
2265 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
2267 if (iv0
->mode
!= iv1
->mode
)
2270 desc
->mode
= iv0
->mode
;
2271 desc
->signed_p
= signed_p
;
2276 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2277 result. This function is called from iv_number_of_iterations with
2278 a number of fields in DESC already filled in. OLD_NITER is the original
2279 expression for the number of iterations, before we tried to simplify it. */
2282 determine_max_iter (struct loop
*loop
, struct niter_desc
*desc
, rtx old_niter
)
2284 rtx niter
= desc
->niter_expr
;
2285 rtx mmin
, mmax
, cmp
;
2287 uint64_t andmax
= 0;
2289 /* We used to look for constant operand 0 of AND,
2290 but canonicalization should always make this impossible. */
2291 gcc_checking_assert (GET_CODE (niter
) != AND
2292 || !CONST_INT_P (XEXP (niter
, 0)));
2294 if (GET_CODE (niter
) == AND
2295 && CONST_INT_P (XEXP (niter
, 1)))
2297 andmax
= UINTVAL (XEXP (niter
, 1));
2298 niter
= XEXP (niter
, 0);
2301 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
2302 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
2304 if (GET_CODE (niter
) == UDIV
)
2306 if (!CONST_INT_P (XEXP (niter
, 1)))
2308 inc
= INTVAL (XEXP (niter
, 1));
2309 niter
= XEXP (niter
, 0);
2314 /* We could use a binary search here, but for now improving the upper
2315 bound by just one eliminates one important corner case. */
2316 cmp
= simplify_gen_relational (desc
->signed_p
? LT
: LTU
, VOIDmode
,
2317 desc
->mode
, old_niter
, mmax
);
2318 simplify_using_initial_values (loop
, UNKNOWN
, &cmp
);
2319 if (cmp
== const_true_rtx
)
2324 fprintf (dump_file
, ";; improved upper bound by one.\n");
2328 nmax
= MIN (nmax
, andmax
);
2330 fprintf (dump_file
, ";; Determined upper bound %"PRId64
".\n",
2335 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2336 the result into DESC. Very similar to determine_number_of_iterations
2337 (basically its rtl version), complicated by things like subregs. */
2340 iv_number_of_iterations (struct loop
*loop
, rtx_insn
*insn
, rtx condition
,
2341 struct niter_desc
*desc
)
2343 rtx op0
, op1
, delta
, step
, bound
, may_xform
, tmp
, tmp0
, tmp1
;
2344 struct rtx_iv iv0
, iv1
, tmp_iv
;
2345 rtx assumption
, may_not_xform
;
2347 enum machine_mode mode
, comp_mode
;
2348 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2349 uint64_t s
, size
, d
, inv
, max
;
2350 int64_t up
, down
, inc
, step_val
;
2351 int was_sharp
= false;
2355 /* The meaning of these assumptions is this:
2357 then the rest of information does not have to be valid
2358 if noloop_assumptions then the loop does not roll
2359 if infinite then this exit is never used */
2361 desc
->assumptions
= NULL_RTX
;
2362 desc
->noloop_assumptions
= NULL_RTX
;
2363 desc
->infinite
= NULL_RTX
;
2364 desc
->simple_p
= true;
2366 desc
->const_iter
= false;
2367 desc
->niter_expr
= NULL_RTX
;
2369 cond
= GET_CODE (condition
);
2370 gcc_assert (COMPARISON_P (condition
));
2372 mode
= GET_MODE (XEXP (condition
, 0));
2373 if (mode
== VOIDmode
)
2374 mode
= GET_MODE (XEXP (condition
, 1));
2375 /* The constant comparisons should be folded. */
2376 gcc_assert (mode
!= VOIDmode
);
2378 /* We only handle integers or pointers. */
2379 if (GET_MODE_CLASS (mode
) != MODE_INT
2380 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2383 op0
= XEXP (condition
, 0);
2384 if (!iv_analyze (insn
, op0
, &iv0
))
2386 if (iv0
.extend_mode
== VOIDmode
)
2387 iv0
.mode
= iv0
.extend_mode
= mode
;
2389 op1
= XEXP (condition
, 1);
2390 if (!iv_analyze (insn
, op1
, &iv1
))
2392 if (iv1
.extend_mode
== VOIDmode
)
2393 iv1
.mode
= iv1
.extend_mode
= mode
;
2395 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2396 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2399 /* Check condition and normalize it. */
2407 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2408 cond
= swap_condition (cond
);
2420 /* Handle extends. This is relatively nontrivial, so we only try in some
2421 easy cases, when we can canonicalize the ivs (possibly by adding some
2422 assumptions) to shape subreg (base + i * step). This function also fills
2423 in desc->mode and desc->signed_p. */
2425 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2428 comp_mode
= iv0
.extend_mode
;
2430 size
= GET_MODE_BITSIZE (mode
);
2431 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2432 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2433 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2435 if (!CONST_INT_P (iv0
.step
) || !CONST_INT_P (iv1
.step
))
2438 /* We can take care of the case of two induction variables chasing each other
2439 if the test is NE. I have never seen a loop using it, but still it is
2441 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2446 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2447 iv1
.step
= const0_rtx
;
2450 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2451 iv1
.step
= lowpart_subreg (mode
, iv1
.step
, comp_mode
);
2453 /* This is either infinite loop or the one that ends immediately, depending
2454 on initial values. Unswitching should remove this kind of conditions. */
2455 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2460 if (iv0
.step
== const0_rtx
)
2461 step_val
= -INTVAL (iv1
.step
);
2463 step_val
= INTVAL (iv0
.step
);
2465 /* Ignore loops of while (i-- < 10) type. */
2469 step_is_pow2
= !(step_val
& (step_val
- 1));
2473 /* We do not care about whether the step is power of two in this
2475 step_is_pow2
= false;
2479 /* Some more condition normalization. We must record some assumptions
2480 due to overflows. */
2485 /* We want to take care only of non-sharp relationals; this is easy,
2486 as in cases the overflow would make the transformation unsafe
2487 the loop does not roll. Seemingly it would make more sense to want
2488 to take care of sharp relationals instead, as NE is more similar to
2489 them, but the problem is that here the transformation would be more
2490 difficult due to possibly infinite loops. */
2491 if (iv0
.step
== const0_rtx
)
2493 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2494 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2496 if (assumption
== const_true_rtx
)
2497 goto zero_iter_simplify
;
2498 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2499 iv0
.base
, const1_rtx
);
2503 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2504 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2506 if (assumption
== const_true_rtx
)
2507 goto zero_iter_simplify
;
2508 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2509 iv1
.base
, constm1_rtx
);
2512 if (assumption
!= const0_rtx
)
2513 desc
->noloop_assumptions
=
2514 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2515 cond
= (cond
== LT
) ? LE
: LEU
;
2517 /* It will be useful to be able to tell the difference once more in
2518 LE -> NE reduction. */
2524 /* Take care of trivially infinite loops. */
2527 if (iv0
.step
== const0_rtx
)
2529 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2530 if (rtx_equal_p (tmp
, mode_mmin
))
2533 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2534 /* Fill in the remaining fields somehow. */
2535 goto zero_iter_simplify
;
2540 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2541 if (rtx_equal_p (tmp
, mode_mmax
))
2544 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2545 /* Fill in the remaining fields somehow. */
2546 goto zero_iter_simplify
;
2551 /* If we can we want to take care of NE conditions instead of size
2552 comparisons, as they are much more friendly (most importantly
2553 this takes care of special handling of loops with step 1). We can
2554 do it if we first check that upper bound is greater or equal to
2555 lower bound, their difference is constant c modulo step and that
2556 there is not an overflow. */
2559 if (iv0
.step
== const0_rtx
)
2560 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2563 step
= lowpart_subreg (mode
, step
, comp_mode
);
2564 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2565 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2566 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2567 may_xform
= const0_rtx
;
2568 may_not_xform
= const_true_rtx
;
2570 if (CONST_INT_P (delta
))
2572 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2574 /* A special case. We have transformed condition of type
2575 for (i = 0; i < 4; i += 4)
2577 for (i = 0; i <= 3; i += 4)
2578 obviously if the test for overflow during that transformation
2579 passed, we cannot overflow here. Most importantly any
2580 loop with sharp end condition and step 1 falls into this
2581 category, so handling this case specially is definitely
2582 worth the troubles. */
2583 may_xform
= const_true_rtx
;
2585 else if (iv0
.step
== const0_rtx
)
2587 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2588 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2589 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2590 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2591 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2593 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2599 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2600 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2601 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2602 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2603 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2605 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2611 if (may_xform
!= const0_rtx
)
2613 /* We perform the transformation always provided that it is not
2614 completely senseless. This is OK, as we would need this assumption
2615 to determine the number of iterations anyway. */
2616 if (may_xform
!= const_true_rtx
)
2618 /* If the step is a power of two and the final value we have
2619 computed overflows, the cycle is infinite. Otherwise it
2620 is nontrivial to compute the number of iterations. */
2622 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2625 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2629 /* We are going to lose some information about upper bound on
2630 number of iterations in this step, so record the information
2632 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2633 if (CONST_INT_P (iv1
.base
))
2634 up
= INTVAL (iv1
.base
);
2636 up
= INTVAL (mode_mmax
) - inc
;
2637 down
= INTVAL (CONST_INT_P (iv0
.base
)
2640 max
= (up
- down
) / inc
+ 1;
2642 && !desc
->assumptions
)
2643 record_niter_bound (loop
, max
, false, true);
2645 if (iv0
.step
== const0_rtx
)
2647 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2648 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2652 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2653 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2656 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2657 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2658 assumption
= simplify_gen_relational (reverse_condition (cond
),
2659 SImode
, mode
, tmp0
, tmp1
);
2660 if (assumption
== const_true_rtx
)
2661 goto zero_iter_simplify
;
2662 else if (assumption
!= const0_rtx
)
2663 desc
->noloop_assumptions
=
2664 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2669 /* Count the number of iterations. */
2672 /* Everything we do here is just arithmetics modulo size of mode. This
2673 makes us able to do more involved computations of number of iterations
2674 than in other cases. First transform the condition into shape
2675 s * i <> c, with s positive. */
2676 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2677 iv0
.base
= const0_rtx
;
2678 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2679 iv1
.step
= const0_rtx
;
2680 if (INTVAL (iv0
.step
) < 0)
2682 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, comp_mode
);
2683 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, comp_mode
);
2685 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2687 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2688 is infinite. Otherwise, the number of iterations is
2689 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2690 s
= INTVAL (iv0
.step
); d
= 1;
2697 bound
= GEN_INT (((uint64_t) 1 << (size
- 1 ) << 1) - 1);
2699 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2700 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, gen_int_mode (d
, mode
));
2701 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2702 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2704 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, gen_int_mode (d
, mode
));
2705 inv
= inverse (s
, size
);
2706 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2707 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2711 if (iv1
.step
== const0_rtx
)
2712 /* Condition in shape a + s * i <= b
2713 We must know that b + s does not overflow and a <= b + s and then we
2714 can compute number of iterations as (b + s - a) / s. (It might
2715 seem that we in fact could be more clever about testing the b + s
2716 overflow condition using some information about b - a mod s,
2717 but it was already taken into account during LE -> NE transform). */
2720 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2721 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2723 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2724 lowpart_subreg (mode
, step
,
2730 /* If s is power of 2, we know that the loop is infinite if
2731 a % s <= b % s and b + s overflows. */
2732 assumption
= simplify_gen_relational (reverse_condition (cond
),
2736 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2737 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2738 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2739 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2741 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2745 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2748 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2751 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2752 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2753 assumption
= simplify_gen_relational (reverse_condition (cond
),
2754 SImode
, mode
, tmp0
, tmp
);
2756 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2757 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2761 /* Condition in shape a <= b - s * i
2762 We must know that a - s does not overflow and a - s <= b and then
2763 we can again compute number of iterations as (b - (a - s)) / s. */
2764 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2765 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2766 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2768 bound
= simplify_gen_binary (PLUS
, mode
, mode_mmin
,
2769 lowpart_subreg (mode
, step
, comp_mode
));
2774 /* If s is power of 2, we know that the loop is infinite if
2775 a % s <= b % s and a - s overflows. */
2776 assumption
= simplify_gen_relational (reverse_condition (cond
),
2780 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2781 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2782 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2783 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2785 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2789 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2792 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2795 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2796 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2797 assumption
= simplify_gen_relational (reverse_condition (cond
),
2800 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2801 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2803 if (assumption
== const_true_rtx
)
2804 goto zero_iter_simplify
;
2805 else if (assumption
!= const0_rtx
)
2806 desc
->noloop_assumptions
=
2807 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2808 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2809 desc
->niter_expr
= delta
;
2812 old_niter
= desc
->niter_expr
;
2814 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2815 if (desc
->assumptions
2816 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2818 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2819 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2820 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2822 /* Rerun the simplification. Consider code (created by copying loop headers)
2834 The first pass determines that i = 0, the second pass uses it to eliminate
2835 noloop assumption. */
2837 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2838 if (desc
->assumptions
2839 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2841 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2842 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2843 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2845 if (desc
->noloop_assumptions
2846 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2849 if (CONST_INT_P (desc
->niter_expr
))
2851 uint64_t val
= INTVAL (desc
->niter_expr
);
2853 desc
->const_iter
= true;
2854 desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2856 && !desc
->assumptions
)
2857 record_niter_bound (loop
, desc
->niter
, false, true);
2861 max
= determine_max_iter (loop
, desc
, old_niter
);
2863 goto zero_iter_simplify
;
2865 && !desc
->assumptions
)
2866 record_niter_bound (loop
, max
, false, true);
2868 /* simplify_using_initial_values does a copy propagation on the registers
2869 in the expression for the number of iterations. This prolongs life
2870 ranges of registers and increases register pressure, and usually
2871 brings no gain (and if it happens to do, the cse pass will take care
2872 of it anyway). So prevent this behavior, unless it enabled us to
2873 derive that the number of iterations is a constant. */
2874 desc
->niter_expr
= old_niter
;
2880 /* Simplify the assumptions. */
2881 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2882 if (desc
->assumptions
2883 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2885 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2889 desc
->const_iter
= true;
2891 record_niter_bound (loop
, 0, true, true);
2892 desc
->noloop_assumptions
= NULL_RTX
;
2893 desc
->niter_expr
= const0_rtx
;
2897 desc
->simple_p
= false;
2901 /* Checks whether E is a simple exit from LOOP and stores its description
2905 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2907 basic_block exit_bb
;
2913 desc
->simple_p
= false;
2915 /* It must belong directly to the loop. */
2916 if (exit_bb
->loop_father
!= loop
)
2919 /* It must be tested (at least) once during any iteration. */
2920 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2923 /* It must end in a simple conditional jump. */
2924 if (!any_condjump_p (BB_END (exit_bb
)))
2927 ein
= EDGE_SUCC (exit_bb
, 0);
2929 ein
= EDGE_SUCC (exit_bb
, 1);
2932 desc
->in_edge
= ein
;
2934 /* Test whether the condition is suitable. */
2935 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2938 if (ein
->flags
& EDGE_FALLTHRU
)
2940 condition
= reversed_condition (condition
);
2945 /* Check that we are able to determine number of iterations and fill
2946 in information about it. */
2947 iv_number_of_iterations (loop
, at
, condition
, desc
);
2950 /* Finds a simple exit of LOOP and stores its description into DESC. */
2953 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2958 struct niter_desc act
;
2962 desc
->simple_p
= false;
2963 body
= get_loop_body (loop
);
2965 for (i
= 0; i
< loop
->num_nodes
; i
++)
2967 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2969 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2972 check_simple_exit (loop
, e
, &act
);
2980 /* Prefer constant iterations; the less the better. */
2982 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2985 /* Also if the actual exit may be infinite, while the old one
2986 not, prefer the old one. */
2987 if (act
.infinite
&& !desc
->infinite
)
2999 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
3000 fprintf (dump_file
, " simple exit %d -> %d\n",
3001 desc
->out_edge
->src
->index
,
3002 desc
->out_edge
->dest
->index
);
3003 if (desc
->assumptions
)
3005 fprintf (dump_file
, " assumptions: ");
3006 print_rtl (dump_file
, desc
->assumptions
);
3007 fprintf (dump_file
, "\n");
3009 if (desc
->noloop_assumptions
)
3011 fprintf (dump_file
, " does not roll if: ");
3012 print_rtl (dump_file
, desc
->noloop_assumptions
);
3013 fprintf (dump_file
, "\n");
3017 fprintf (dump_file
, " infinite if: ");
3018 print_rtl (dump_file
, desc
->infinite
);
3019 fprintf (dump_file
, "\n");
3022 fprintf (dump_file
, " number of iterations: ");
3023 print_rtl (dump_file
, desc
->niter_expr
);
3024 fprintf (dump_file
, "\n");
3026 fprintf (dump_file
, " upper bound: %li\n",
3027 (long)get_max_loop_iterations_int (loop
));
3028 fprintf (dump_file
, " realistic bound: %li\n",
3029 (long)get_estimated_loop_iterations_int (loop
));
3032 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
3038 /* Creates a simple loop description of LOOP if it was not computed
3042 get_simple_loop_desc (struct loop
*loop
)
3044 struct niter_desc
*desc
= simple_loop_desc (loop
);
3049 /* At least desc->infinite is not always initialized by
3050 find_simple_loop_exit. */
3051 desc
= ggc_cleared_alloc
<niter_desc
> ();
3052 iv_analysis_loop_init (loop
);
3053 find_simple_exit (loop
, desc
);
3054 loop
->simple_loop_desc
= desc
;
3056 if (desc
->simple_p
&& (desc
->assumptions
|| desc
->infinite
))
3058 const char *wording
;
3060 /* Assume that no overflow happens and that the loop is finite.
3061 We already warned at the tree level if we ran optimizations there. */
3062 if (!flag_tree_loop_optimize
&& warn_unsafe_loop_optimizations
)
3067 flag_unsafe_loop_optimizations
3068 ? N_("assuming that the loop is not infinite")
3069 : N_("cannot optimize possibly infinite loops");
3070 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3073 if (desc
->assumptions
)
3076 flag_unsafe_loop_optimizations
3077 ? N_("assuming that the loop counter does not overflow")
3078 : N_("cannot optimize loop, the loop counter may overflow");
3079 warning (OPT_Wunsafe_loop_optimizations
, "%s",
3084 if (flag_unsafe_loop_optimizations
)
3086 desc
->assumptions
= NULL_RTX
;
3087 desc
->infinite
= NULL_RTX
;
3094 /* Releases simple loop description for LOOP. */
3097 free_simple_loop_desc (struct loop
*loop
)
3099 struct niter_desc
*desc
= simple_loop_desc (loop
);
3105 loop
->simple_loop_desc
= NULL
;