1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 /* This is just a very simplistic analysis of induction variables of the loop.
22 The major use is for determining the number of iterations of a loop for
23 loop unrolling, doloop optimization and branch prediction. For this we
24 are only interested in bivs and a fairly limited set of givs that are
25 needed in the exit condition. We also only compute the iv information on
28 The interesting registers are determined. A register is interesting if
30 -- it is set only in the blocks that dominate the latch of the current loop
31 -- all its sets are simple -- i.e. in the form we understand
33 We also number the insns sequentially in each basic block. For a use of the
34 interesting reg, it is now easy to find a reaching definition (there may be
37 Induction variable is then simply analyzed by walking the use-def
42 iv_analysis_loop_init (loop);
43 insn = iv_get_reaching_def (where, reg);
44 if (iv_analyze (insn, reg, &iv))
48 iv_analysis_done (); */
52 #include "coretypes.h"
55 #include "hard-reg-set.h"
57 #include "basic-block.h"
62 /* The insn information. */
69 /* The previous definition of the register defined by the single
73 /* The description of the iv. */
77 static struct insn_info
*insn_info
;
79 /* The last definition of register. */
85 static struct rtx_iv
*bivs
;
87 /* Maximal insn number for that there is place in insn_info array. */
89 static unsigned max_insn_no
;
91 /* Maximal register number for that there is place in bivs and last_def
94 static unsigned max_reg_no
;
96 /* Dumps information about IV to FILE. */
98 extern void dump_iv_info (FILE *, struct rtx_iv
*);
100 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
104 fprintf (file
, "not simple");
108 if (iv
->step
== const0_rtx
109 && !iv
->first_special
)
110 fprintf (file
, "invariant ");
112 print_rtl (file
, iv
->base
);
113 if (iv
->step
!= const0_rtx
)
115 fprintf (file
, " + ");
116 print_rtl (file
, iv
->step
);
117 fprintf (file
, " * iteration");
119 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
121 if (iv
->mode
!= iv
->extend_mode
)
122 fprintf (file
, " %s to %s",
123 rtx_name
[iv
->extend
],
124 GET_MODE_NAME (iv
->extend_mode
));
126 if (iv
->mult
!= const1_rtx
)
128 fprintf (file
, " * ");
129 print_rtl (file
, iv
->mult
);
131 if (iv
->delta
!= const0_rtx
)
133 fprintf (file
, " + ");
134 print_rtl (file
, iv
->delta
);
136 if (iv
->first_special
)
137 fprintf (file
, " (first special)");
140 /* Assigns luids to insns in basic block BB. */
143 assign_luids (basic_block bb
)
148 FOR_BB_INSNS (bb
, insn
)
150 uid
= INSN_UID (insn
);
151 insn_info
[uid
].luid
= i
++;
152 insn_info
[uid
].prev_def
= NULL_RTX
;
153 insn_info
[uid
].iv
.analysed
= false;
157 /* Generates a subreg to get the least significant part of EXPR (in mode
158 INNER_MODE) to OUTER_MODE. */
161 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
162 enum machine_mode inner_mode
)
164 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
165 subreg_lowpart_offset (outer_mode
, inner_mode
));
168 /* Checks whether REG is a well-behaved register. */
171 simple_reg_p (rtx reg
)
175 if (GET_CODE (reg
) == SUBREG
)
177 if (!subreg_lowpart_p (reg
))
179 reg
= SUBREG_REG (reg
);
186 if (HARD_REGISTER_NUM_P (r
))
189 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
192 if (last_def
[r
] == const0_rtx
)
198 /* Checks whether assignment LHS = RHS is simple enough for us to process. */
201 simple_set_p (rtx lhs
, rtx rhs
)
206 || !simple_reg_p (lhs
))
209 if (CONSTANT_P (rhs
))
212 switch (GET_CODE (rhs
))
216 return simple_reg_p (rhs
);
221 return simple_reg_p (XEXP (rhs
, 0));
230 if (!simple_reg_p (op0
)
231 && !CONSTANT_P (op0
))
234 if (!simple_reg_p (op1
)
235 && !CONSTANT_P (op1
))
238 if (GET_CODE (rhs
) == MULT
240 && !CONSTANT_P (op1
))
243 if (GET_CODE (rhs
) == ASHIFT
254 /* Mark single SET in INSN. */
257 mark_single_set (rtx insn
, rtx set
)
259 rtx def
= SET_DEST (set
), src
;
262 src
= find_reg_equal_equiv_note (insn
);
268 if (!simple_set_p (SET_DEST (set
), src
))
272 uid
= INSN_UID (insn
);
274 bivs
[regno
].analysed
= false;
275 insn_info
[uid
].prev_def
= last_def
[regno
];
276 last_def
[regno
] = insn
;
281 /* Invalidate register REG unless it is equal to EXCEPT. */
284 kill_sets (rtx reg
, rtx by ATTRIBUTE_UNUSED
, void *except
)
286 if (GET_CODE (reg
) == SUBREG
)
287 reg
= SUBREG_REG (reg
);
293 last_def
[REGNO (reg
)] = const0_rtx
;
296 /* Marks sets in basic block BB. If DOM is true, BB dominates the loop
300 mark_sets (basic_block bb
, bool dom
)
304 FOR_BB_INSNS (bb
, insn
)
310 && (set
= single_set (insn
)))
311 def
= mark_single_set (insn
, set
);
315 note_stores (PATTERN (insn
), kill_sets
, def
);
319 /* Prepare the data for an induction variable analysis of a LOOP. */
322 iv_analysis_loop_init (struct loop
*loop
)
324 basic_block
*body
= get_loop_body_in_dom_order (loop
);
327 if ((unsigned) get_max_uid () >= max_insn_no
)
329 /* Add some reserve for insns and registers produced in optimizations. */
330 max_insn_no
= get_max_uid () + 100;
333 insn_info
= xmalloc (max_insn_no
* sizeof (struct insn_info
));
336 if ((unsigned) max_reg_num () >= max_reg_no
)
338 max_reg_no
= max_reg_num () + 100;
341 last_def
= xmalloc (max_reg_no
* sizeof (rtx
));
344 bivs
= xmalloc (max_reg_no
* sizeof (struct rtx_iv
));
347 memset (last_def
, 0, max_reg_num () * sizeof (rtx
));
349 for (b
= 0; b
< loop
->num_nodes
; b
++)
351 assign_luids (body
[b
]);
352 mark_sets (body
[b
], just_once_each_iteration_p (loop
, body
[b
]));
358 /* Gets definition of REG reaching the INSN. If REG is not simple, const0_rtx
359 is returned. If INSN is before the first def in the loop, NULL_RTX is
363 iv_get_reaching_def (rtx insn
, rtx reg
)
365 unsigned regno
, luid
, auid
;
369 if (GET_CODE (reg
) == SUBREG
)
371 if (!subreg_lowpart_p (reg
))
373 reg
= SUBREG_REG (reg
);
380 || last_def
[regno
] == const0_rtx
)
381 return last_def
[regno
];
383 bb
= BLOCK_FOR_INSN (insn
);
384 luid
= insn_info
[INSN_UID (insn
)].luid
;
386 ainsn
= last_def
[regno
];
389 abb
= BLOCK_FOR_INSN (ainsn
);
391 if (dominated_by_p (CDI_DOMINATORS
, bb
, abb
))
394 auid
= INSN_UID (ainsn
);
395 ainsn
= insn_info
[auid
].prev_def
;
403 abb
= BLOCK_FOR_INSN (ainsn
);
407 auid
= INSN_UID (ainsn
);
408 if (luid
> insn_info
[auid
].luid
)
411 ainsn
= insn_info
[auid
].prev_def
;
417 /* Sets IV to invariant CST in MODE. Always returns true (just for
418 consistency with other iv manipulation functions that may fail). */
421 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
423 if (mode
== VOIDmode
)
424 mode
= GET_MODE (cst
);
429 iv
->step
= const0_rtx
;
430 iv
->first_special
= false;
431 iv
->extend
= UNKNOWN
;
432 iv
->extend_mode
= iv
->mode
;
433 iv
->delta
= const0_rtx
;
434 iv
->mult
= const1_rtx
;
439 /* Evaluates application of subreg to MODE on IV. */
442 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
444 /* If iv is invariant, just calculate the new value. */
445 if (iv
->step
== const0_rtx
446 && !iv
->first_special
)
448 rtx val
= get_iv_value (iv
, const0_rtx
);
449 val
= lowpart_subreg (mode
, val
, iv
->extend_mode
);
452 iv
->extend
= UNKNOWN
;
453 iv
->mode
= iv
->extend_mode
= mode
;
454 iv
->delta
= const0_rtx
;
455 iv
->mult
= const1_rtx
;
459 if (iv
->extend_mode
== mode
)
462 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
465 iv
->extend
= UNKNOWN
;
468 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
469 simplify_gen_binary (MULT
, iv
->extend_mode
,
470 iv
->base
, iv
->mult
));
471 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
472 iv
->mult
= const1_rtx
;
473 iv
->delta
= const0_rtx
;
474 iv
->first_special
= false;
479 /* Evaluates application of EXTEND to MODE on IV. */
482 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
484 /* If iv is invariant, just calculate the new value. */
485 if (iv
->step
== const0_rtx
486 && !iv
->first_special
)
488 rtx val
= get_iv_value (iv
, const0_rtx
);
489 val
= simplify_gen_unary (extend
, mode
, val
, iv
->extend_mode
);
492 iv
->extend
= UNKNOWN
;
493 iv
->mode
= iv
->extend_mode
= mode
;
494 iv
->delta
= const0_rtx
;
495 iv
->mult
= const1_rtx
;
499 if (mode
!= iv
->extend_mode
)
502 if (iv
->extend
!= UNKNOWN
503 && iv
->extend
!= extend
)
511 /* Evaluates negation of IV. */
514 iv_neg (struct rtx_iv
*iv
)
516 if (iv
->extend
== UNKNOWN
)
518 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
519 iv
->base
, iv
->extend_mode
);
520 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
521 iv
->step
, iv
->extend_mode
);
525 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
526 iv
->delta
, iv
->extend_mode
);
527 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
528 iv
->mult
, iv
->extend_mode
);
534 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
537 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
539 enum machine_mode mode
;
542 /* Extend the constant to extend_mode of the other operand if necessary. */
543 if (iv0
->extend
== UNKNOWN
544 && iv0
->mode
== iv0
->extend_mode
545 && iv0
->step
== const0_rtx
546 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
548 iv0
->extend_mode
= iv1
->extend_mode
;
549 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
550 iv0
->base
, iv0
->mode
);
552 if (iv1
->extend
== UNKNOWN
553 && iv1
->mode
== iv1
->extend_mode
554 && iv1
->step
== const0_rtx
555 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
557 iv1
->extend_mode
= iv0
->extend_mode
;
558 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
559 iv1
->base
, iv1
->mode
);
562 mode
= iv0
->extend_mode
;
563 if (mode
!= iv1
->extend_mode
)
566 if (iv0
->extend
== UNKNOWN
&& iv1
->extend
== UNKNOWN
)
568 if (iv0
->mode
!= iv1
->mode
)
571 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
572 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
577 /* Handle addition of constant. */
578 if (iv1
->extend
== UNKNOWN
580 && iv1
->step
== const0_rtx
)
582 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
586 if (iv0
->extend
== UNKNOWN
588 && iv0
->step
== const0_rtx
)
596 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
603 /* Evaluates multiplication of IV by constant CST. */
606 iv_mult (struct rtx_iv
*iv
, rtx mby
)
608 enum machine_mode mode
= iv
->extend_mode
;
610 if (GET_MODE (mby
) != VOIDmode
611 && GET_MODE (mby
) != mode
)
614 if (iv
->extend
== UNKNOWN
)
616 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
617 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
621 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
622 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
628 /* Evaluates shift of IV by constant CST. */
631 iv_shift (struct rtx_iv
*iv
, rtx mby
)
633 enum machine_mode mode
= iv
->extend_mode
;
635 if (GET_MODE (mby
) != VOIDmode
636 && GET_MODE (mby
) != mode
)
639 if (iv
->extend
== UNKNOWN
)
641 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
642 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
646 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
647 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
653 /* The recursive part of get_biv_step. Gets the value of the single value
654 defined in INSN wrto initial value of REG inside loop, in shape described
658 get_biv_step_1 (rtx insn
, rtx reg
,
659 rtx
*inner_step
, enum machine_mode
*inner_mode
,
660 enum rtx_code
*extend
, enum machine_mode outer_mode
,
663 rtx set
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
664 rtx next
, nextr
, def_insn
, tmp
;
667 set
= single_set (insn
);
668 rhs
= find_reg_equal_equiv_note (insn
);
674 code
= GET_CODE (rhs
);
687 if (code
== PLUS
&& CONSTANT_P (op0
))
689 tmp
= op0
; op0
= op1
; op1
= tmp
;
692 if (!simple_reg_p (op0
)
693 || !CONSTANT_P (op1
))
696 if (GET_MODE (rhs
) != outer_mode
)
698 /* ppc64 uses expressions like
700 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
702 this is equivalent to
704 (set x':DI (plus:DI y:DI 1))
705 (set x:SI (subreg:SI (x':DI)). */
706 if (GET_CODE (op0
) != SUBREG
)
708 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
717 if (GET_MODE (rhs
) != outer_mode
)
721 if (!simple_reg_p (op0
))
731 if (GET_CODE (next
) == SUBREG
)
733 if (!subreg_lowpart_p (next
))
736 nextr
= SUBREG_REG (next
);
737 if (GET_MODE (nextr
) != outer_mode
)
743 def_insn
= iv_get_reaching_def (insn
, nextr
);
744 if (def_insn
== const0_rtx
)
749 if (!rtx_equal_p (nextr
, reg
))
752 *inner_step
= const0_rtx
;
754 *inner_mode
= outer_mode
;
755 *outer_step
= const0_rtx
;
757 else if (!get_biv_step_1 (def_insn
, reg
,
758 inner_step
, inner_mode
, extend
, outer_mode
,
762 if (GET_CODE (next
) == SUBREG
)
764 enum machine_mode amode
= GET_MODE (next
);
766 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
770 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
771 *inner_step
, *outer_step
);
772 *outer_step
= const0_rtx
;
784 if (*inner_mode
== outer_mode
785 /* See comment in previous switch. */
786 || GET_MODE (rhs
) != outer_mode
)
787 *inner_step
= simplify_gen_binary (code
, outer_mode
,
790 *outer_step
= simplify_gen_binary (code
, outer_mode
,
796 if (GET_MODE (op0
) != *inner_mode
797 || *extend
!= UNKNOWN
798 || *outer_step
!= const0_rtx
)
811 /* Gets the operation on register REG inside loop, in shape
813 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
815 If the operation cannot be described in this shape, return false. */
818 get_biv_step (rtx reg
, rtx
*inner_step
, enum machine_mode
*inner_mode
,
819 enum rtx_code
*extend
, enum machine_mode
*outer_mode
,
822 *outer_mode
= GET_MODE (reg
);
824 if (!get_biv_step_1 (last_def
[REGNO (reg
)], reg
,
825 inner_step
, inner_mode
, extend
, *outer_mode
,
829 if (*inner_mode
!= *outer_mode
830 && *extend
== UNKNOWN
)
833 if (*inner_mode
== *outer_mode
834 && *extend
!= UNKNOWN
)
837 if (*inner_mode
== *outer_mode
838 && *outer_step
!= const0_rtx
)
844 /* Determines whether DEF is a biv and if so, stores its description
848 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
851 rtx inner_step
, outer_step
;
852 enum machine_mode inner_mode
, outer_mode
;
853 enum rtx_code extend
;
857 fprintf (dump_file
, "Analysing ");
858 print_rtl (dump_file
, def
);
859 fprintf (dump_file
, " for bivness.\n");
864 if (!CONSTANT_P (def
))
867 return iv_constant (iv
, def
, VOIDmode
);
871 if (last_def
[regno
] == const0_rtx
)
874 fprintf (dump_file
, " not simple.\n");
878 if (last_def
[regno
] && bivs
[regno
].analysed
)
881 fprintf (dump_file
, " already analysed.\n");
884 return iv
->base
!= NULL_RTX
;
887 if (!last_def
[regno
])
889 iv_constant (iv
, def
, VOIDmode
);
894 if (!get_biv_step (def
, &inner_step
, &inner_mode
, &extend
,
895 &outer_mode
, &outer_step
))
901 /* Loop transforms base to es (base + inner_step) + outer_step,
902 where es means extend of subreg between inner_mode and outer_mode.
903 The corresponding induction variable is
905 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
907 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
908 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
909 iv
->mode
= inner_mode
;
910 iv
->extend_mode
= outer_mode
;
912 iv
->mult
= const1_rtx
;
913 iv
->delta
= outer_step
;
914 iv
->first_special
= inner_mode
!= outer_mode
;
919 fprintf (dump_file
, " ");
920 dump_iv_info (dump_file
, iv
);
921 fprintf (dump_file
, "\n");
926 return iv
->base
!= NULL_RTX
;
929 /* Analyzes operand OP of INSN and stores the result to *IV. */
932 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
936 bool inv
= CONSTANT_P (op
);
940 fprintf (dump_file
, "Analysing operand ");
941 print_rtl (dump_file
, op
);
942 fprintf (dump_file
, " of insn ");
943 print_rtl_single (dump_file
, insn
);
946 if (GET_CODE (op
) == SUBREG
)
948 if (!subreg_lowpart_p (op
))
951 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
954 return iv_subreg (iv
, GET_MODE (op
));
960 if (!last_def
[regno
])
962 else if (last_def
[regno
] == const0_rtx
)
965 fprintf (dump_file
, " not simple.\n");
972 iv_constant (iv
, op
, VOIDmode
);
976 fprintf (dump_file
, " ");
977 dump_iv_info (dump_file
, iv
);
978 fprintf (dump_file
, "\n");
983 def_insn
= iv_get_reaching_def (insn
, op
);
984 if (def_insn
== const0_rtx
)
987 fprintf (dump_file
, " not simple.\n");
991 return iv_analyze (def_insn
, op
, iv
);
994 /* Analyzes iv DEF defined in INSN and stores the result to *IV. */
997 iv_analyze (rtx insn
, rtx def
, struct rtx_iv
*iv
)
1000 rtx set
, rhs
, mby
= NULL_RTX
, tmp
;
1001 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
1002 struct rtx_iv iv0
, iv1
;
1003 enum machine_mode amode
;
1006 if (insn
== const0_rtx
)
1009 if (GET_CODE (def
) == SUBREG
)
1011 if (!subreg_lowpart_p (def
))
1014 if (!iv_analyze (insn
, SUBREG_REG (def
), iv
))
1017 return iv_subreg (iv
, GET_MODE (def
));
1021 return iv_analyze_biv (def
, iv
);
1025 fprintf (dump_file
, "Analysing def of ");
1026 print_rtl (dump_file
, def
);
1027 fprintf (dump_file
, " in insn ");
1028 print_rtl_single (dump_file
, insn
);
1031 uid
= INSN_UID (insn
);
1032 if (insn_info
[uid
].iv
.analysed
)
1035 fprintf (dump_file
, " already analysed.\n");
1036 *iv
= insn_info
[uid
].iv
;
1037 return iv
->base
!= NULL_RTX
;
1040 iv
->mode
= VOIDmode
;
1041 iv
->base
= NULL_RTX
;
1042 iv
->step
= NULL_RTX
;
1044 set
= single_set (insn
);
1045 rhs
= find_reg_equal_equiv_note (insn
);
1047 rhs
= XEXP (rhs
, 0);
1049 rhs
= SET_SRC (set
);
1050 code
= GET_CODE (rhs
);
1052 if (CONSTANT_P (rhs
))
1055 amode
= GET_MODE (def
);
1062 if (!subreg_lowpart_p (rhs
))
1074 op0
= XEXP (rhs
, 0);
1079 op0
= XEXP (rhs
, 0);
1080 op1
= XEXP (rhs
, 1);
1084 op0
= XEXP (rhs
, 0);
1085 mby
= XEXP (rhs
, 1);
1086 if (!CONSTANT_P (mby
))
1088 if (!CONSTANT_P (op0
))
1097 if (CONSTANT_P (XEXP (rhs
, 0)))
1099 op0
= XEXP (rhs
, 0);
1100 mby
= XEXP (rhs
, 1);
1107 amode
= GET_MODE (rhs
);
1112 if (!iv_analyze_op (insn
, op0
, &iv0
))
1115 if (iv0
.mode
== VOIDmode
)
1118 iv0
.extend_mode
= amode
;
1124 if (!iv_analyze_op (insn
, op1
, &iv1
))
1127 if (iv1
.mode
== VOIDmode
)
1130 iv1
.extend_mode
= amode
;
1138 if (!iv_extend (&iv0
, code
, amode
))
1149 if (!iv_add (&iv0
, &iv1
, code
))
1154 if (!iv_mult (&iv0
, mby
))
1159 if (!iv_shift (&iv0
, mby
))
1170 iv
->analysed
= true;
1171 insn_info
[uid
].iv
= *iv
;
1175 print_rtl (dump_file
, def
);
1176 fprintf (dump_file
, " in insn ");
1177 print_rtl_single (dump_file
, insn
);
1178 fprintf (dump_file
, " is ");
1179 dump_iv_info (dump_file
, iv
);
1180 fprintf (dump_file
, "\n");
1183 return iv
->base
!= NULL_RTX
;
1186 /* Checks whether definition of register REG in INSN a basic induction
1187 variable. IV analysis must have been initialized (via a call to
1188 iv_analysis_loop_init) for this function to produce a result. */
1191 biv_p (rtx insn
, rtx reg
)
1198 if (last_def
[REGNO (reg
)] != insn
)
1201 return iv_analyze_biv (reg
, &iv
);
1204 /* Calculates value of IV at ITERATION-th iteration. */
1207 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1211 /* We would need to generate some if_then_else patterns, and so far
1212 it is not needed anywhere. */
1213 if (iv
->first_special
)
1216 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1217 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1218 simplify_gen_binary (MULT
, iv
->extend_mode
,
1219 iv
->step
, iteration
));
1223 if (iv
->extend_mode
== iv
->mode
)
1226 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1228 if (iv
->extend
== UNKNOWN
)
1231 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1232 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1233 simplify_gen_binary (MULT
, iv
->extend_mode
,
1239 /* Free the data for an induction variable analysis. */
1242 iv_analysis_done (void)
1263 /* Computes inverse to X modulo (1 << MOD). */
1265 static unsigned HOST_WIDEST_INT
1266 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1268 unsigned HOST_WIDEST_INT mask
=
1269 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1270 unsigned HOST_WIDEST_INT rslt
= 1;
1273 for (i
= 0; i
< mod
- 1; i
++)
1275 rslt
= (rslt
* x
) & mask
;
1282 /* Tries to estimate the maximum number of iterations. */
1284 static unsigned HOST_WIDEST_INT
1285 determine_max_iter (struct niter_desc
*desc
)
1287 rtx niter
= desc
->niter_expr
;
1288 rtx mmin
, mmax
, left
, right
;
1289 unsigned HOST_WIDEST_INT nmax
, inc
;
1291 if (GET_CODE (niter
) == AND
1292 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
1294 nmax
= INTVAL (XEXP (niter
, 0));
1295 if (!(nmax
& (nmax
+ 1)))
1297 desc
->niter_max
= nmax
;
1302 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
1303 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1305 if (GET_CODE (niter
) == UDIV
)
1307 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
1309 desc
->niter_max
= nmax
;
1312 inc
= INTVAL (XEXP (niter
, 1));
1313 niter
= XEXP (niter
, 0);
1318 if (GET_CODE (niter
) == PLUS
)
1320 left
= XEXP (niter
, 0);
1321 right
= XEXP (niter
, 0);
1323 if (GET_CODE (right
) == CONST_INT
)
1324 right
= GEN_INT (-INTVAL (right
));
1326 else if (GET_CODE (niter
) == MINUS
)
1328 left
= XEXP (niter
, 0);
1329 right
= XEXP (niter
, 0);
1337 if (GET_CODE (left
) == CONST_INT
)
1339 if (GET_CODE (right
) == CONST_INT
)
1341 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1343 desc
->niter_max
= nmax
/ inc
;
1347 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1350 altered_reg_used (rtx
*reg
, void *alt
)
1355 return REGNO_REG_SET_P (alt
, REGNO (*reg
));
1358 /* Marks registers altered by EXPR in set ALT. */
1361 mark_altered (rtx expr
, rtx by ATTRIBUTE_UNUSED
, void *alt
)
1363 if (GET_CODE (expr
) == SUBREG
)
1364 expr
= SUBREG_REG (expr
);
1368 SET_REGNO_REG_SET (alt
, REGNO (expr
));
1371 /* Checks whether RHS is simple enough to process. */
1374 simple_rhs_p (rtx rhs
)
1378 if (CONSTANT_P (rhs
)
1382 switch (GET_CODE (rhs
))
1386 op0
= XEXP (rhs
, 0);
1387 op1
= XEXP (rhs
, 1);
1388 /* Allow reg + const sets only. */
1389 if (REG_P (op0
) && CONSTANT_P (op1
))
1391 if (REG_P (op1
) && CONSTANT_P (op0
))
1401 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1405 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1407 rtx set
= single_set (insn
);
1408 rtx lhs
= NULL_RTX
, rhs
;
1413 lhs
= SET_DEST (set
);
1415 || altered_reg_used (&lhs
, altered
))
1421 note_stores (PATTERN (insn
), mark_altered
, altered
);
1426 /* Kill all call clobbered registers. */
1427 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1428 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1429 SET_REGNO_REG_SET (altered
, i
);
1435 rhs
= find_reg_equal_equiv_note (insn
);
1437 rhs
= XEXP (rhs
, 0);
1439 rhs
= SET_SRC (set
);
1441 if (!simple_rhs_p (rhs
))
1444 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1447 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1450 /* Checks whether A implies B. */
1453 implies_p (rtx a
, rtx b
)
1455 rtx op0
, op1
, opb0
, opb1
, r
;
1456 enum machine_mode mode
;
1458 if (GET_CODE (a
) == EQ
)
1465 r
= simplify_replace_rtx (b
, op0
, op1
);
1466 if (r
== const_true_rtx
)
1472 r
= simplify_replace_rtx (b
, op1
, op0
);
1473 if (r
== const_true_rtx
)
1478 /* A < B implies A + 1 <= B. */
1479 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1480 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1487 if (GET_CODE (a
) == GT
)
1494 if (GET_CODE (b
) == GE
)
1501 mode
= GET_MODE (op0
);
1502 if (mode
!= GET_MODE (opb0
))
1504 else if (mode
== VOIDmode
)
1506 mode
= GET_MODE (op1
);
1507 if (mode
!= GET_MODE (opb1
))
1511 if (mode
!= VOIDmode
1512 && rtx_equal_p (op1
, opb1
)
1513 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1520 /* Canonicalizes COND so that
1522 (1) Ensure that operands are ordered according to
1523 swap_commutative_operands_p.
1524 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1525 for GE, GEU, and LEU. */
1528 canon_condition (rtx cond
)
1533 enum machine_mode mode
;
1535 code
= GET_CODE (cond
);
1536 op0
= XEXP (cond
, 0);
1537 op1
= XEXP (cond
, 1);
1539 if (swap_commutative_operands_p (op0
, op1
))
1541 code
= swap_condition (code
);
1547 mode
= GET_MODE (op0
);
1548 if (mode
== VOIDmode
)
1549 mode
= GET_MODE (op1
);
1550 if (mode
== VOIDmode
)
1553 if (GET_CODE (op1
) == CONST_INT
1554 && GET_MODE_CLASS (mode
) != MODE_CC
1555 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1557 HOST_WIDE_INT const_val
= INTVAL (op1
);
1558 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1559 unsigned HOST_WIDE_INT max_val
1560 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1565 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1566 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1569 /* When cross-compiling, const_val might be sign-extended from
1570 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1572 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1573 != (((HOST_WIDE_INT
) 1
1574 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1575 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1579 if (uconst_val
< max_val
)
1580 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1584 if (uconst_val
!= 0)
1585 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1593 if (op0
!= XEXP (cond
, 0)
1594 || op1
!= XEXP (cond
, 1)
1595 || code
!= GET_CODE (cond
)
1596 || GET_MODE (cond
) != SImode
)
1597 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1602 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1603 set of altered regs. */
1606 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1608 rtx rev
, reve
, exp
= *expr
;
1610 if (!COMPARISON_P (exp
))
1613 /* If some register gets altered later, we do not really speak about its
1614 value at the time of comparison. */
1616 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1619 rev
= reversed_condition (cond
);
1620 reve
= reversed_condition (exp
);
1622 cond
= canon_condition (cond
);
1623 exp
= canon_condition (exp
);
1625 rev
= canon_condition (rev
);
1627 reve
= canon_condition (reve
);
1629 if (rtx_equal_p (exp
, cond
))
1631 *expr
= const_true_rtx
;
1636 if (rev
&& rtx_equal_p (exp
, rev
))
1642 if (implies_p (cond
, exp
))
1644 *expr
= const_true_rtx
;
1648 if (reve
&& implies_p (cond
, reve
))
1654 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1656 if (rev
&& implies_p (exp
, rev
))
1662 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1663 if (rev
&& reve
&& implies_p (reve
, rev
))
1665 *expr
= const_true_rtx
;
1669 /* We would like to have some other tests here. TODO. */
1674 /* Use relationship between A and *B to eventually eliminate *B.
1675 OP is the operation we consider. */
1678 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1682 /* If A implies *B, we may replace *B by true. */
1683 if (implies_p (a
, *b
))
1684 *b
= const_true_rtx
;
1688 /* If *B implies A, we may replace *B by false. */
1689 if (implies_p (*b
, a
))
1696 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1697 operation we consider. */
1700 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1704 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1705 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1706 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1707 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1710 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1711 is a list, its elements are assumed to be combined using OP. */
1714 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1716 rtx head
, tail
, insn
;
1724 if (CONSTANT_P (*expr
))
1727 if (GET_CODE (*expr
) == EXPR_LIST
)
1729 head
= XEXP (*expr
, 0);
1730 tail
= XEXP (*expr
, 1);
1732 eliminate_implied_conditions (op
, &head
, tail
);
1736 neutral
= const_true_rtx
;
1741 neutral
= const0_rtx
;
1742 aggr
= const_true_rtx
;
1747 simplify_using_initial_values (loop
, UNKNOWN
, &head
);
1750 XEXP (*expr
, 0) = aggr
;
1751 XEXP (*expr
, 1) = NULL_RTX
;
1754 else if (head
== neutral
)
1757 simplify_using_initial_values (loop
, op
, expr
);
1760 simplify_using_initial_values (loop
, op
, &tail
);
1762 if (tail
&& XEXP (tail
, 0) == aggr
)
1768 XEXP (*expr
, 0) = head
;
1769 XEXP (*expr
, 1) = tail
;
1776 e
= loop_preheader_edge (loop
);
1777 if (e
->src
== ENTRY_BLOCK_PTR
)
1780 altered
= ALLOC_REG_SET (®_obstack
);
1786 insn
= BB_END (e
->src
);
1787 if (any_condjump_p (insn
))
1789 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1791 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1792 cond
= reversed_condition (cond
);
1795 simplify_using_condition (cond
, expr
, altered
);
1796 if (CONSTANT_P (*expr
))
1798 FREE_REG_SET (altered
);
1804 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1809 simplify_using_assignment (insn
, expr
, altered
);
1810 if (CONSTANT_P (*expr
))
1812 FREE_REG_SET (altered
);
1817 /* This is a bit subtle. Store away e->src in tmp_bb, since we
1818 modify `e' and this can invalidate the subsequent count of
1819 e->src's predecessors by looking at the wrong block. */
1821 e
= EDGE_PRED (tmp_bb
, 0);
1822 if (EDGE_COUNT (tmp_bb
->preds
) > 1
1823 || e
->src
== ENTRY_BLOCK_PTR
)
1827 FREE_REG_SET (altered
);
1830 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1831 that IV occurs as left operands of comparison COND and its signedness
1832 is SIGNED_P to DESC. */
1835 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1836 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1838 rtx mmin
, mmax
, cond_over
, cond_under
;
1840 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1841 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1843 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1852 if (cond_under
!= const0_rtx
)
1854 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1855 if (cond_over
!= const0_rtx
)
1856 desc
->noloop_assumptions
=
1857 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1864 if (cond_over
!= const0_rtx
)
1866 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1867 if (cond_under
!= const0_rtx
)
1868 desc
->noloop_assumptions
=
1869 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1873 if (cond_over
!= const0_rtx
)
1875 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1876 if (cond_under
!= const0_rtx
)
1878 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1886 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1889 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1890 subregs of the same mode if possible (sometimes it is necessary to add
1891 some assumptions to DESC). */
1894 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1895 enum rtx_code cond
, struct niter_desc
*desc
)
1897 enum machine_mode comp_mode
;
1900 /* If the ivs behave specially in the first iteration, or are
1901 added/multiplied after extending, we ignore them. */
1902 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1904 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1907 /* If there is some extend, it must match signedness of the comparison. */
1912 if (iv0
->extend
== ZERO_EXTEND
1913 || iv1
->extend
== ZERO_EXTEND
)
1920 if (iv0
->extend
== SIGN_EXTEND
1921 || iv1
->extend
== SIGN_EXTEND
)
1927 if (iv0
->extend
!= UNKNOWN
1928 && iv1
->extend
!= UNKNOWN
1929 && iv0
->extend
!= iv1
->extend
)
1933 if (iv0
->extend
!= UNKNOWN
)
1934 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1935 if (iv1
->extend
!= UNKNOWN
)
1936 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1943 /* Values of both variables should be computed in the same mode. These
1944 might indeed be different, if we have comparison like
1946 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1948 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1949 in different modes. This does not seem impossible to handle, but
1950 it hardly ever occurs in practice.
1952 The only exception is the case when one of operands is invariant.
1953 For example pentium 3 generates comparisons like
1954 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1955 definitely do not want this prevent the optimization. */
1956 comp_mode
= iv0
->extend_mode
;
1957 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1958 comp_mode
= iv1
->extend_mode
;
1960 if (iv0
->extend_mode
!= comp_mode
)
1962 if (iv0
->mode
!= iv0
->extend_mode
1963 || iv0
->step
!= const0_rtx
)
1966 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1967 comp_mode
, iv0
->base
, iv0
->mode
);
1968 iv0
->extend_mode
= comp_mode
;
1971 if (iv1
->extend_mode
!= comp_mode
)
1973 if (iv1
->mode
!= iv1
->extend_mode
1974 || iv1
->step
!= const0_rtx
)
1977 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1978 comp_mode
, iv1
->base
, iv1
->mode
);
1979 iv1
->extend_mode
= comp_mode
;
1982 /* Check that both ivs belong to a range of a single mode. If one of the
1983 operands is an invariant, we may need to shorten it into the common
1985 if (iv0
->mode
== iv0
->extend_mode
1986 && iv0
->step
== const0_rtx
1987 && iv0
->mode
!= iv1
->mode
)
1988 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
1990 if (iv1
->mode
== iv1
->extend_mode
1991 && iv1
->step
== const0_rtx
1992 && iv0
->mode
!= iv1
->mode
)
1993 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
1995 if (iv0
->mode
!= iv1
->mode
)
1998 desc
->mode
= iv0
->mode
;
1999 desc
->signed_p
= signed_p
;
2004 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2005 the result into DESC. Very similar to determine_number_of_iterations
2006 (basically its rtl version), complicated by things like subregs. */
2009 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2010 struct niter_desc
*desc
)
2012 rtx op0
, op1
, delta
, step
, bound
, may_xform
, def_insn
, tmp
, tmp0
, tmp1
;
2013 struct rtx_iv iv0
, iv1
, tmp_iv
;
2014 rtx assumption
, may_not_xform
;
2016 enum machine_mode mode
, comp_mode
;
2017 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2018 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2019 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2020 int was_sharp
= false;
2024 /* The meaning of these assumptions is this:
2026 then the rest of information does not have to be valid
2027 if noloop_assumptions then the loop does not roll
2028 if infinite then this exit is never used */
2030 desc
->assumptions
= NULL_RTX
;
2031 desc
->noloop_assumptions
= NULL_RTX
;
2032 desc
->infinite
= NULL_RTX
;
2033 desc
->simple_p
= true;
2035 desc
->const_iter
= false;
2036 desc
->niter_expr
= NULL_RTX
;
2037 desc
->niter_max
= 0;
2039 cond
= GET_CODE (condition
);
2040 if (!COMPARISON_P (condition
))
2043 mode
= GET_MODE (XEXP (condition
, 0));
2044 if (mode
== VOIDmode
)
2045 mode
= GET_MODE (XEXP (condition
, 1));
2046 /* The constant comparisons should be folded. */
2047 if (mode
== VOIDmode
)
2050 /* We only handle integers or pointers. */
2051 if (GET_MODE_CLASS (mode
) != MODE_INT
2052 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2055 op0
= XEXP (condition
, 0);
2056 def_insn
= iv_get_reaching_def (insn
, op0
);
2057 if (!iv_analyze (def_insn
, op0
, &iv0
))
2059 if (iv0
.extend_mode
== VOIDmode
)
2060 iv0
.mode
= iv0
.extend_mode
= mode
;
2062 op1
= XEXP (condition
, 1);
2063 def_insn
= iv_get_reaching_def (insn
, op1
);
2064 if (!iv_analyze (def_insn
, op1
, &iv1
))
2066 if (iv1
.extend_mode
== VOIDmode
)
2067 iv1
.mode
= iv1
.extend_mode
= mode
;
2069 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2070 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2073 /* Check condition and normalize it. */
2081 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2082 cond
= swap_condition (cond
);
2094 /* Handle extends. This is relatively nontrivial, so we only try in some
2095 easy cases, when we can canonicalize the ivs (possibly by adding some
2096 assumptions) to shape subreg (base + i * step). This function also fills
2097 in desc->mode and desc->signed_p. */
2099 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2102 comp_mode
= iv0
.extend_mode
;
2104 size
= GET_MODE_BITSIZE (mode
);
2105 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2106 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2107 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2109 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2112 /* We can take care of the case of two induction variables chasing each other
2113 if the test is NE. I have never seen a loop using it, but still it is
2115 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2120 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2121 iv1
.step
= const0_rtx
;
2124 /* This is either infinite loop or the one that ends immediately, depending
2125 on initial values. Unswitching should remove this kind of conditions. */
2126 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2131 if (iv0
.step
== const0_rtx
)
2132 step_val
= -INTVAL (iv1
.step
);
2134 step_val
= INTVAL (iv0
.step
);
2136 /* Ignore loops of while (i-- < 10) type. */
2140 step_is_pow2
= !(step_val
& (step_val
- 1));
2144 /* We do not care about whether the step is power of two in this
2146 step_is_pow2
= false;
2150 /* Some more condition normalization. We must record some assumptions
2151 due to overflows. */
2156 /* We want to take care only of non-sharp relationals; this is easy,
2157 as in cases the overflow would make the transformation unsafe
2158 the loop does not roll. Seemingly it would make more sense to want
2159 to take care of sharp relationals instead, as NE is more similar to
2160 them, but the problem is that here the transformation would be more
2161 difficult due to possibly infinite loops. */
2162 if (iv0
.step
== const0_rtx
)
2164 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2165 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2167 if (assumption
== const_true_rtx
)
2169 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2170 iv0
.base
, const1_rtx
);
2174 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2175 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2177 if (assumption
== const_true_rtx
)
2179 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2180 iv1
.base
, constm1_rtx
);
2183 if (assumption
!= const0_rtx
)
2184 desc
->noloop_assumptions
=
2185 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2186 cond
= (cond
== LT
) ? LE
: LEU
;
2188 /* It will be useful to be able to tell the difference once more in
2189 LE -> NE reduction. */
2195 /* Take care of trivially infinite loops. */
2198 if (iv0
.step
== const0_rtx
)
2200 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2201 if (rtx_equal_p (tmp
, mode_mmin
))
2204 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2210 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2211 if (rtx_equal_p (tmp
, mode_mmax
))
2214 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2220 /* If we can we want to take care of NE conditions instead of size
2221 comparisons, as they are much more friendly (most importantly
2222 this takes care of special handling of loops with step 1). We can
2223 do it if we first check that upper bound is greater or equal to
2224 lower bound, their difference is constant c modulo step and that
2225 there is not an overflow. */
2228 if (iv0
.step
== const0_rtx
)
2229 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2232 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2233 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2234 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2235 may_xform
= const0_rtx
;
2236 may_not_xform
= const_true_rtx
;
2238 if (GET_CODE (delta
) == CONST_INT
)
2240 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2242 /* A special case. We have transformed condition of type
2243 for (i = 0; i < 4; i += 4)
2245 for (i = 0; i <= 3; i += 4)
2246 obviously if the test for overflow during that transformation
2247 passed, we cannot overflow here. Most importantly any
2248 loop with sharp end condition and step 1 falls into this
2249 category, so handling this case specially is definitely
2250 worth the troubles. */
2251 may_xform
= const_true_rtx
;
2253 else if (iv0
.step
== const0_rtx
)
2255 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2256 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2257 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2258 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2259 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2261 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2267 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2268 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2269 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2270 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2271 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2273 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2279 if (may_xform
!= const0_rtx
)
2281 /* We perform the transformation always provided that it is not
2282 completely senseless. This is OK, as we would need this assumption
2283 to determine the number of iterations anyway. */
2284 if (may_xform
!= const_true_rtx
)
2286 /* If the step is a power of two and the final value we have
2287 computed overflows, the cycle is infinite. Otherwise it
2288 is nontrivial to compute the number of iterations. */
2290 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2293 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2297 /* We are going to lose some information about upper bound on
2298 number of iterations in this step, so record the information
2300 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2301 if (GET_CODE (iv1
.base
) == CONST_INT
)
2302 up
= INTVAL (iv1
.base
);
2304 up
= INTVAL (mode_mmax
) - inc
;
2305 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2308 desc
->niter_max
= (up
- down
) / inc
+ 1;
2310 if (iv0
.step
== const0_rtx
)
2312 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2313 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2317 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2318 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2321 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2322 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2323 assumption
= simplify_gen_relational (reverse_condition (cond
),
2324 SImode
, mode
, tmp0
, tmp1
);
2325 if (assumption
== const_true_rtx
)
2327 else if (assumption
!= const0_rtx
)
2328 desc
->noloop_assumptions
=
2329 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2334 /* Count the number of iterations. */
2337 /* Everything we do here is just arithmetics modulo size of mode. This
2338 makes us able to do more involved computations of number of iterations
2339 than in other cases. First transform the condition into shape
2340 s * i <> c, with s positive. */
2341 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2342 iv0
.base
= const0_rtx
;
2343 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2344 iv1
.step
= const0_rtx
;
2345 if (INTVAL (iv0
.step
) < 0)
2347 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2348 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2350 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2352 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2353 is infinite. Otherwise, the number of iterations is
2354 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2355 s
= INTVAL (iv0
.step
); d
= 1;
2362 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2364 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2365 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2366 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2367 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2369 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2370 inv
= inverse (s
, size
);
2371 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2372 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2376 if (iv1
.step
== const0_rtx
)
2377 /* Condition in shape a + s * i <= b
2378 We must know that b + s does not overflow and a <= b + s and then we
2379 can compute number of iterations as (b + s - a) / s. (It might
2380 seem that we in fact could be more clever about testing the b + s
2381 overflow condition using some information about b - a mod s,
2382 but it was already taken into account during LE -> NE transform). */
2385 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2386 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2388 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2389 lowpart_subreg (mode
, step
,
2395 /* If s is power of 2, we know that the loop is infinite if
2396 a % s <= b % s and b + s overflows. */
2397 assumption
= simplify_gen_relational (reverse_condition (cond
),
2401 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2402 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2403 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2404 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2406 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2410 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2413 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2416 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2417 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2418 assumption
= simplify_gen_relational (reverse_condition (cond
),
2419 SImode
, mode
, tmp0
, tmp
);
2421 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2422 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2426 /* Condition in shape a <= b - s * i
2427 We must know that a - s does not overflow and a - s <= b and then
2428 we can again compute number of iterations as (b - (a - s)) / s. */
2429 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2430 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2431 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2433 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmin
,
2434 lowpart_subreg (mode
, step
, comp_mode
));
2439 /* If s is power of 2, we know that the loop is infinite if
2440 a % s <= b % s and a - s overflows. */
2441 assumption
= simplify_gen_relational (reverse_condition (cond
),
2445 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2446 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2447 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2448 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2450 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2454 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2457 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2460 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2461 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2462 assumption
= simplify_gen_relational (reverse_condition (cond
),
2465 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2466 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2468 if (assumption
== const_true_rtx
)
2470 else if (assumption
!= const0_rtx
)
2471 desc
->noloop_assumptions
=
2472 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2473 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2474 desc
->niter_expr
= delta
;
2477 old_niter
= desc
->niter_expr
;
2479 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2480 if (desc
->assumptions
2481 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2483 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2484 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2485 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2487 /* Rerun the simplification. Consider code (created by copying loop headers)
2499 The first pass determines that i = 0, the second pass uses it to eliminate
2500 noloop assumption. */
2502 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2503 if (desc
->assumptions
2504 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2506 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2507 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2508 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2510 if (desc
->noloop_assumptions
2511 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2514 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2516 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2518 desc
->const_iter
= true;
2519 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2523 if (!desc
->niter_max
)
2524 desc
->niter_max
= determine_max_iter (desc
);
2526 /* simplify_using_initial_values does a copy propagation on the registers
2527 in the expression for the number of iterations. This prolongs life
2528 ranges of registers and increases register pressure, and usually
2529 brings no gain (and if it happens to do, the cse pass will take care
2530 of it anyway). So prevent this behavior, unless it enabled us to
2531 derive that the number of iterations is a constant. */
2532 desc
->niter_expr
= old_niter
;
2538 desc
->simple_p
= false;
2542 desc
->const_iter
= true;
2544 desc
->niter_max
= 0;
2545 desc
->niter_expr
= const0_rtx
;
2549 /* Checks whether E is a simple exit from LOOP and stores its description
2553 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2555 basic_block exit_bb
;
2560 desc
->simple_p
= false;
2562 /* It must belong directly to the loop. */
2563 if (exit_bb
->loop_father
!= loop
)
2566 /* It must be tested (at least) once during any iteration. */
2567 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2570 /* It must end in a simple conditional jump. */
2571 if (!any_condjump_p (BB_END (exit_bb
)))
2574 ein
= EDGE_SUCC (exit_bb
, 0);
2576 ein
= EDGE_SUCC (exit_bb
, 1);
2579 desc
->in_edge
= ein
;
2581 /* Test whether the condition is suitable. */
2582 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2585 if (ein
->flags
& EDGE_FALLTHRU
)
2587 condition
= reversed_condition (condition
);
2592 /* Check that we are able to determine number of iterations and fill
2593 in information about it. */
2594 iv_number_of_iterations (loop
, at
, condition
, desc
);
2597 /* Finds a simple exit of LOOP and stores its description into DESC. */
2600 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2605 struct niter_desc act
;
2609 desc
->simple_p
= false;
2610 body
= get_loop_body (loop
);
2612 for (i
= 0; i
< loop
->num_nodes
; i
++)
2614 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2616 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2619 check_simple_exit (loop
, e
, &act
);
2623 /* Prefer constant iterations; the less the better. */
2626 else if (!act
.const_iter
2627 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2637 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2638 fprintf (dump_file
, " simple exit %d -> %d\n",
2639 desc
->out_edge
->src
->index
,
2640 desc
->out_edge
->dest
->index
);
2641 if (desc
->assumptions
)
2643 fprintf (dump_file
, " assumptions: ");
2644 print_rtl (dump_file
, desc
->assumptions
);
2645 fprintf (dump_file
, "\n");
2647 if (desc
->noloop_assumptions
)
2649 fprintf (dump_file
, " does not roll if: ");
2650 print_rtl (dump_file
, desc
->noloop_assumptions
);
2651 fprintf (dump_file
, "\n");
2655 fprintf (dump_file
, " infinite if: ");
2656 print_rtl (dump_file
, desc
->infinite
);
2657 fprintf (dump_file
, "\n");
2660 fprintf (dump_file
, " number of iterations: ");
2661 print_rtl (dump_file
, desc
->niter_expr
);
2662 fprintf (dump_file
, "\n");
2664 fprintf (dump_file
, " upper bound: ");
2665 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2666 fprintf (dump_file
, "\n");
2669 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2675 /* Creates a simple loop description of LOOP if it was not computed
2679 get_simple_loop_desc (struct loop
*loop
)
2681 struct niter_desc
*desc
= simple_loop_desc (loop
);
2686 desc
= xmalloc (sizeof (struct niter_desc
));
2687 iv_analysis_loop_init (loop
);
2688 find_simple_exit (loop
, desc
);
2694 /* Releases simple loop description for LOOP. */
2697 free_simple_loop_desc (struct loop
*loop
)
2699 struct niter_desc
*desc
= simple_loop_desc (loop
);