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
);
1784 insn
= BB_END (e
->src
);
1785 if (any_condjump_p (insn
))
1787 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1789 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1790 cond
= reversed_condition (cond
);
1793 simplify_using_condition (cond
, expr
, altered
);
1794 if (CONSTANT_P (*expr
))
1796 FREE_REG_SET (altered
);
1802 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1807 simplify_using_assignment (insn
, expr
, altered
);
1808 if (CONSTANT_P (*expr
))
1810 FREE_REG_SET (altered
);
1815 if (!single_pred_p (e
->src
)
1816 || single_pred (e
->src
) == ENTRY_BLOCK_PTR
)
1818 e
= single_pred_edge (e
->src
);
1821 FREE_REG_SET (altered
);
1824 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1825 that IV occurs as left operands of comparison COND and its signedness
1826 is SIGNED_P to DESC. */
1829 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1830 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1832 rtx mmin
, mmax
, cond_over
, cond_under
;
1834 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1835 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1837 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1846 if (cond_under
!= const0_rtx
)
1848 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1849 if (cond_over
!= const0_rtx
)
1850 desc
->noloop_assumptions
=
1851 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1858 if (cond_over
!= const0_rtx
)
1860 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1861 if (cond_under
!= const0_rtx
)
1862 desc
->noloop_assumptions
=
1863 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1867 if (cond_over
!= const0_rtx
)
1869 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1870 if (cond_under
!= const0_rtx
)
1872 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1880 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1883 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1884 subregs of the same mode if possible (sometimes it is necessary to add
1885 some assumptions to DESC). */
1888 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1889 enum rtx_code cond
, struct niter_desc
*desc
)
1891 enum machine_mode comp_mode
;
1894 /* If the ivs behave specially in the first iteration, or are
1895 added/multiplied after extending, we ignore them. */
1896 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1898 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1901 /* If there is some extend, it must match signedness of the comparison. */
1906 if (iv0
->extend
== ZERO_EXTEND
1907 || iv1
->extend
== ZERO_EXTEND
)
1914 if (iv0
->extend
== SIGN_EXTEND
1915 || iv1
->extend
== SIGN_EXTEND
)
1921 if (iv0
->extend
!= UNKNOWN
1922 && iv1
->extend
!= UNKNOWN
1923 && iv0
->extend
!= iv1
->extend
)
1927 if (iv0
->extend
!= UNKNOWN
)
1928 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1929 if (iv1
->extend
!= UNKNOWN
)
1930 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1937 /* Values of both variables should be computed in the same mode. These
1938 might indeed be different, if we have comparison like
1940 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1942 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1943 in different modes. This does not seem impossible to handle, but
1944 it hardly ever occurs in practice.
1946 The only exception is the case when one of operands is invariant.
1947 For example pentium 3 generates comparisons like
1948 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1949 definitely do not want this prevent the optimization. */
1950 comp_mode
= iv0
->extend_mode
;
1951 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1952 comp_mode
= iv1
->extend_mode
;
1954 if (iv0
->extend_mode
!= comp_mode
)
1956 if (iv0
->mode
!= iv0
->extend_mode
1957 || iv0
->step
!= const0_rtx
)
1960 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1961 comp_mode
, iv0
->base
, iv0
->mode
);
1962 iv0
->extend_mode
= comp_mode
;
1965 if (iv1
->extend_mode
!= comp_mode
)
1967 if (iv1
->mode
!= iv1
->extend_mode
1968 || iv1
->step
!= const0_rtx
)
1971 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1972 comp_mode
, iv1
->base
, iv1
->mode
);
1973 iv1
->extend_mode
= comp_mode
;
1976 /* Check that both ivs belong to a range of a single mode. If one of the
1977 operands is an invariant, we may need to shorten it into the common
1979 if (iv0
->mode
== iv0
->extend_mode
1980 && iv0
->step
== const0_rtx
1981 && iv0
->mode
!= iv1
->mode
)
1982 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
1984 if (iv1
->mode
== iv1
->extend_mode
1985 && iv1
->step
== const0_rtx
1986 && iv0
->mode
!= iv1
->mode
)
1987 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
1989 if (iv0
->mode
!= iv1
->mode
)
1992 desc
->mode
= iv0
->mode
;
1993 desc
->signed_p
= signed_p
;
1998 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1999 the result into DESC. Very similar to determine_number_of_iterations
2000 (basically its rtl version), complicated by things like subregs. */
2003 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
2004 struct niter_desc
*desc
)
2006 rtx op0
, op1
, delta
, step
, bound
, may_xform
, def_insn
, tmp
, tmp0
, tmp1
;
2007 struct rtx_iv iv0
, iv1
, tmp_iv
;
2008 rtx assumption
, may_not_xform
;
2010 enum machine_mode mode
, comp_mode
;
2011 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
2012 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
2013 HOST_WIDEST_INT up
, down
, inc
, step_val
;
2014 int was_sharp
= false;
2018 /* The meaning of these assumptions is this:
2020 then the rest of information does not have to be valid
2021 if noloop_assumptions then the loop does not roll
2022 if infinite then this exit is never used */
2024 desc
->assumptions
= NULL_RTX
;
2025 desc
->noloop_assumptions
= NULL_RTX
;
2026 desc
->infinite
= NULL_RTX
;
2027 desc
->simple_p
= true;
2029 desc
->const_iter
= false;
2030 desc
->niter_expr
= NULL_RTX
;
2031 desc
->niter_max
= 0;
2033 cond
= GET_CODE (condition
);
2034 if (!COMPARISON_P (condition
))
2037 mode
= GET_MODE (XEXP (condition
, 0));
2038 if (mode
== VOIDmode
)
2039 mode
= GET_MODE (XEXP (condition
, 1));
2040 /* The constant comparisons should be folded. */
2041 if (mode
== VOIDmode
)
2044 /* We only handle integers or pointers. */
2045 if (GET_MODE_CLASS (mode
) != MODE_INT
2046 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2049 op0
= XEXP (condition
, 0);
2050 def_insn
= iv_get_reaching_def (insn
, op0
);
2051 if (!iv_analyze (def_insn
, op0
, &iv0
))
2053 if (iv0
.extend_mode
== VOIDmode
)
2054 iv0
.mode
= iv0
.extend_mode
= mode
;
2056 op1
= XEXP (condition
, 1);
2057 def_insn
= iv_get_reaching_def (insn
, op1
);
2058 if (!iv_analyze (def_insn
, op1
, &iv1
))
2060 if (iv1
.extend_mode
== VOIDmode
)
2061 iv1
.mode
= iv1
.extend_mode
= mode
;
2063 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2064 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2067 /* Check condition and normalize it. */
2075 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2076 cond
= swap_condition (cond
);
2088 /* Handle extends. This is relatively nontrivial, so we only try in some
2089 easy cases, when we can canonicalize the ivs (possibly by adding some
2090 assumptions) to shape subreg (base + i * step). This function also fills
2091 in desc->mode and desc->signed_p. */
2093 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2096 comp_mode
= iv0
.extend_mode
;
2098 size
= GET_MODE_BITSIZE (mode
);
2099 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2100 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2101 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2103 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2106 /* We can take care of the case of two induction variables chasing each other
2107 if the test is NE. I have never seen a loop using it, but still it is
2109 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2114 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2115 iv1
.step
= const0_rtx
;
2118 /* This is either infinite loop or the one that ends immediately, depending
2119 on initial values. Unswitching should remove this kind of conditions. */
2120 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2125 if (iv0
.step
== const0_rtx
)
2126 step_val
= -INTVAL (iv1
.step
);
2128 step_val
= INTVAL (iv0
.step
);
2130 /* Ignore loops of while (i-- < 10) type. */
2134 step_is_pow2
= !(step_val
& (step_val
- 1));
2138 /* We do not care about whether the step is power of two in this
2140 step_is_pow2
= false;
2144 /* Some more condition normalization. We must record some assumptions
2145 due to overflows. */
2150 /* We want to take care only of non-sharp relationals; this is easy,
2151 as in cases the overflow would make the transformation unsafe
2152 the loop does not roll. Seemingly it would make more sense to want
2153 to take care of sharp relationals instead, as NE is more similar to
2154 them, but the problem is that here the transformation would be more
2155 difficult due to possibly infinite loops. */
2156 if (iv0
.step
== const0_rtx
)
2158 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2159 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2161 if (assumption
== const_true_rtx
)
2163 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2164 iv0
.base
, const1_rtx
);
2168 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2169 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2171 if (assumption
== const_true_rtx
)
2173 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2174 iv1
.base
, constm1_rtx
);
2177 if (assumption
!= const0_rtx
)
2178 desc
->noloop_assumptions
=
2179 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2180 cond
= (cond
== LT
) ? LE
: LEU
;
2182 /* It will be useful to be able to tell the difference once more in
2183 LE -> NE reduction. */
2189 /* Take care of trivially infinite loops. */
2192 if (iv0
.step
== const0_rtx
)
2194 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2195 if (rtx_equal_p (tmp
, mode_mmin
))
2198 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2204 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2205 if (rtx_equal_p (tmp
, mode_mmax
))
2208 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2214 /* If we can we want to take care of NE conditions instead of size
2215 comparisons, as they are much more friendly (most importantly
2216 this takes care of special handling of loops with step 1). We can
2217 do it if we first check that upper bound is greater or equal to
2218 lower bound, their difference is constant c modulo step and that
2219 there is not an overflow. */
2222 if (iv0
.step
== const0_rtx
)
2223 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2226 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2227 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2228 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2229 may_xform
= const0_rtx
;
2230 may_not_xform
= const_true_rtx
;
2232 if (GET_CODE (delta
) == CONST_INT
)
2234 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2236 /* A special case. We have transformed condition of type
2237 for (i = 0; i < 4; i += 4)
2239 for (i = 0; i <= 3; i += 4)
2240 obviously if the test for overflow during that transformation
2241 passed, we cannot overflow here. Most importantly any
2242 loop with sharp end condition and step 1 falls into this
2243 category, so handling this case specially is definitely
2244 worth the troubles. */
2245 may_xform
= const_true_rtx
;
2247 else if (iv0
.step
== const0_rtx
)
2249 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2250 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2251 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2252 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2253 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2255 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2261 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2262 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2263 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2264 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2265 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2267 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2273 if (may_xform
!= const0_rtx
)
2275 /* We perform the transformation always provided that it is not
2276 completely senseless. This is OK, as we would need this assumption
2277 to determine the number of iterations anyway. */
2278 if (may_xform
!= const_true_rtx
)
2280 /* If the step is a power of two and the final value we have
2281 computed overflows, the cycle is infinite. Otherwise it
2282 is nontrivial to compute the number of iterations. */
2284 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2287 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2291 /* We are going to lose some information about upper bound on
2292 number of iterations in this step, so record the information
2294 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2295 if (GET_CODE (iv1
.base
) == CONST_INT
)
2296 up
= INTVAL (iv1
.base
);
2298 up
= INTVAL (mode_mmax
) - inc
;
2299 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2302 desc
->niter_max
= (up
- down
) / inc
+ 1;
2304 if (iv0
.step
== const0_rtx
)
2306 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2307 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2311 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2312 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2315 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2316 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2317 assumption
= simplify_gen_relational (reverse_condition (cond
),
2318 SImode
, mode
, tmp0
, tmp1
);
2319 if (assumption
== const_true_rtx
)
2321 else if (assumption
!= const0_rtx
)
2322 desc
->noloop_assumptions
=
2323 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2328 /* Count the number of iterations. */
2331 /* Everything we do here is just arithmetics modulo size of mode. This
2332 makes us able to do more involved computations of number of iterations
2333 than in other cases. First transform the condition into shape
2334 s * i <> c, with s positive. */
2335 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2336 iv0
.base
= const0_rtx
;
2337 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2338 iv1
.step
= const0_rtx
;
2339 if (INTVAL (iv0
.step
) < 0)
2341 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2342 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2344 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2346 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2347 is infinite. Otherwise, the number of iterations is
2348 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2349 s
= INTVAL (iv0
.step
); d
= 1;
2356 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2358 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2359 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2360 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2361 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2363 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2364 inv
= inverse (s
, size
);
2365 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, gen_int_mode (inv
, mode
));
2366 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2370 if (iv1
.step
== const0_rtx
)
2371 /* Condition in shape a + s * i <= b
2372 We must know that b + s does not overflow and a <= b + s and then we
2373 can compute number of iterations as (b + s - a) / s. (It might
2374 seem that we in fact could be more clever about testing the b + s
2375 overflow condition using some information about b - a mod s,
2376 but it was already taken into account during LE -> NE transform). */
2379 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2380 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2382 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2383 lowpart_subreg (mode
, step
,
2389 /* If s is power of 2, we know that the loop is infinite if
2390 a % s <= b % s and b + s overflows. */
2391 assumption
= simplify_gen_relational (reverse_condition (cond
),
2395 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2396 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2397 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2398 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2400 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2404 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2407 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2410 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2411 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2412 assumption
= simplify_gen_relational (reverse_condition (cond
),
2413 SImode
, mode
, tmp0
, tmp
);
2415 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2416 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2420 /* Condition in shape a <= b - s * i
2421 We must know that a - s does not overflow and a - s <= b and then
2422 we can again compute number of iterations as (b - (a - s)) / s. */
2423 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2424 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2425 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2427 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmin
,
2428 lowpart_subreg (mode
, step
, comp_mode
));
2433 /* If s is power of 2, we know that the loop is infinite if
2434 a % s <= b % s and a - s overflows. */
2435 assumption
= simplify_gen_relational (reverse_condition (cond
),
2439 t0
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp0
), step
);
2440 t1
= simplify_gen_binary (UMOD
, mode
, copy_rtx (tmp1
), step
);
2441 tmp
= simplify_gen_relational (cond
, SImode
, mode
, t0
, t1
);
2442 assumption
= simplify_gen_binary (AND
, SImode
, assumption
, tmp
);
2444 alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2448 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2451 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2454 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2455 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2456 assumption
= simplify_gen_relational (reverse_condition (cond
),
2459 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2460 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2462 if (assumption
== const_true_rtx
)
2464 else if (assumption
!= const0_rtx
)
2465 desc
->noloop_assumptions
=
2466 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2467 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2468 desc
->niter_expr
= delta
;
2471 old_niter
= desc
->niter_expr
;
2473 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2474 if (desc
->assumptions
2475 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2477 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2478 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2479 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2481 /* Rerun the simplification. Consider code (created by copying loop headers)
2493 The first pass determines that i = 0, the second pass uses it to eliminate
2494 noloop assumption. */
2496 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2497 if (desc
->assumptions
2498 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2500 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2501 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2502 simplify_using_initial_values (loop
, UNKNOWN
, &desc
->niter_expr
);
2504 if (desc
->noloop_assumptions
2505 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2508 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2510 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2512 desc
->const_iter
= true;
2513 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2517 if (!desc
->niter_max
)
2518 desc
->niter_max
= determine_max_iter (desc
);
2520 /* simplify_using_initial_values does a copy propagation on the registers
2521 in the expression for the number of iterations. This prolongs life
2522 ranges of registers and increases register pressure, and usually
2523 brings no gain (and if it happens to do, the cse pass will take care
2524 of it anyway). So prevent this behavior, unless it enabled us to
2525 derive that the number of iterations is a constant. */
2526 desc
->niter_expr
= old_niter
;
2532 desc
->simple_p
= false;
2536 desc
->const_iter
= true;
2538 desc
->niter_max
= 0;
2539 desc
->niter_expr
= const0_rtx
;
2543 /* Checks whether E is a simple exit from LOOP and stores its description
2547 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2549 basic_block exit_bb
;
2554 desc
->simple_p
= false;
2556 /* It must belong directly to the loop. */
2557 if (exit_bb
->loop_father
!= loop
)
2560 /* It must be tested (at least) once during any iteration. */
2561 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2564 /* It must end in a simple conditional jump. */
2565 if (!any_condjump_p (BB_END (exit_bb
)))
2568 ein
= EDGE_SUCC (exit_bb
, 0);
2570 ein
= EDGE_SUCC (exit_bb
, 1);
2573 desc
->in_edge
= ein
;
2575 /* Test whether the condition is suitable. */
2576 if (!(condition
= get_condition (BB_END (ein
->src
), &at
, false, false)))
2579 if (ein
->flags
& EDGE_FALLTHRU
)
2581 condition
= reversed_condition (condition
);
2586 /* Check that we are able to determine number of iterations and fill
2587 in information about it. */
2588 iv_number_of_iterations (loop
, at
, condition
, desc
);
2591 /* Finds a simple exit of LOOP and stores its description into DESC. */
2594 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2599 struct niter_desc act
;
2603 desc
->simple_p
= false;
2604 body
= get_loop_body (loop
);
2606 for (i
= 0; i
< loop
->num_nodes
; i
++)
2608 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
2610 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2613 check_simple_exit (loop
, e
, &act
);
2617 /* Prefer constant iterations; the less the better. */
2620 else if (!act
.const_iter
2621 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2631 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2632 fprintf (dump_file
, " simple exit %d -> %d\n",
2633 desc
->out_edge
->src
->index
,
2634 desc
->out_edge
->dest
->index
);
2635 if (desc
->assumptions
)
2637 fprintf (dump_file
, " assumptions: ");
2638 print_rtl (dump_file
, desc
->assumptions
);
2639 fprintf (dump_file
, "\n");
2641 if (desc
->noloop_assumptions
)
2643 fprintf (dump_file
, " does not roll if: ");
2644 print_rtl (dump_file
, desc
->noloop_assumptions
);
2645 fprintf (dump_file
, "\n");
2649 fprintf (dump_file
, " infinite if: ");
2650 print_rtl (dump_file
, desc
->infinite
);
2651 fprintf (dump_file
, "\n");
2654 fprintf (dump_file
, " number of iterations: ");
2655 print_rtl (dump_file
, desc
->niter_expr
);
2656 fprintf (dump_file
, "\n");
2658 fprintf (dump_file
, " upper bound: ");
2659 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2660 fprintf (dump_file
, "\n");
2663 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2669 /* Creates a simple loop description of LOOP if it was not computed
2673 get_simple_loop_desc (struct loop
*loop
)
2675 struct niter_desc
*desc
= simple_loop_desc (loop
);
2680 desc
= xmalloc (sizeof (struct niter_desc
));
2681 iv_analysis_loop_init (loop
);
2682 find_simple_exit (loop
, desc
);
2688 /* Releases simple loop description for LOOP. */
2691 free_simple_loop_desc (struct loop
*loop
)
2693 struct niter_desc
*desc
= simple_loop_desc (loop
);