1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004 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"
56 #include "basic-block.h"
61 /* The insn information. */
68 /* The previous definition of the register defined by the single
72 /* The description of the iv. */
76 static struct insn_info
*insn_info
;
78 /* The last definition of register. */
84 static struct rtx_iv
*bivs
;
86 /* Maximal insn number for that there is place in insn_info array. */
88 static unsigned max_insn_no
;
90 /* Maximal register number for that there is place in bivs and last_def
93 static unsigned max_reg_no
;
95 /* Dumps information about IV to FILE. */
97 extern void dump_iv_info (FILE *, struct rtx_iv
*);
99 dump_iv_info (FILE *file
, struct rtx_iv
*iv
)
103 fprintf (file
, "not simple");
107 if (iv
->step
== const0_rtx
)
109 fprintf (file
, "invariant ");
110 print_rtl (file
, iv
->base
);
114 print_rtl (file
, iv
->base
);
115 fprintf (file
, " + ");
116 print_rtl (file
, iv
->step
);
117 fprintf (file
, " * iteration");
118 fprintf (file
, " (in %s)", GET_MODE_NAME (iv
->mode
));
120 if (iv
->mode
!= iv
->extend_mode
)
121 fprintf (file
, " %s to %s",
122 rtx_name
[iv
->extend
],
123 GET_MODE_NAME (iv
->extend_mode
));
125 if (iv
->mult
!= const1_rtx
)
127 fprintf (file
, " * ");
128 print_rtl (file
, iv
->mult
);
130 if (iv
->delta
!= const0_rtx
)
132 fprintf (file
, " + ");
133 print_rtl (file
, iv
->delta
);
135 if (iv
->first_special
)
136 fprintf (file
, " (first special)");
139 /* Assigns luids to insns in basic block BB. */
142 assign_luids (basic_block bb
)
147 FOR_BB_INSNS (bb
, insn
)
149 uid
= INSN_UID (insn
);
150 insn_info
[uid
].luid
= i
++;
151 insn_info
[uid
].prev_def
= NULL_RTX
;
152 insn_info
[uid
].iv
.analysed
= false;
156 /* Generates a subreg to get the least significant part of EXPR (in mode
157 INNER_MODE) to OUTER_MODE. */
160 lowpart_subreg (enum machine_mode outer_mode
, rtx expr
,
161 enum machine_mode inner_mode
)
163 return simplify_gen_subreg (outer_mode
, expr
, inner_mode
,
164 subreg_lowpart_offset (outer_mode
, inner_mode
));
167 /* Checks whether REG is a well-behaved register. */
170 simple_reg_p (rtx reg
)
174 if (GET_CODE (reg
) == SUBREG
)
176 if (!subreg_lowpart_p (reg
))
178 reg
= SUBREG_REG (reg
);
185 if (HARD_REGISTER_NUM_P (r
))
188 if (GET_MODE_CLASS (GET_MODE (reg
)) != MODE_INT
)
191 if (last_def
[r
] == const0_rtx
)
197 /* Checks whether assignment LHS = RHS is simple enough for us to process. */
200 simple_set_p (rtx lhs
, rtx rhs
)
205 || !simple_reg_p (lhs
))
208 if (CONSTANT_P (rhs
))
211 switch (GET_CODE (rhs
))
215 return simple_reg_p (rhs
);
220 return simple_reg_p (XEXP (rhs
, 0));
229 if (!simple_reg_p (op0
)
230 && !CONSTANT_P (op0
))
233 if (!simple_reg_p (op1
)
234 && !CONSTANT_P (op1
))
237 if (GET_CODE (rhs
) == MULT
239 && !CONSTANT_P (op1
))
242 if (GET_CODE (rhs
) == ASHIFT
253 /* Mark single SET in INSN. */
256 mark_single_set (rtx insn
, rtx set
)
258 rtx def
= SET_DEST (set
), src
;
261 src
= find_reg_equal_equiv_note (insn
);
267 if (!simple_set_p (SET_DEST (set
), src
))
271 uid
= INSN_UID (insn
);
273 bivs
[regno
].analysed
= false;
274 insn_info
[uid
].prev_def
= last_def
[regno
];
275 last_def
[regno
] = insn
;
280 /* Invalidate register REG unless it is equal to EXCEPT. */
283 kill_sets (rtx reg
, rtx by ATTRIBUTE_UNUSED
, void *except
)
285 if (GET_CODE (reg
) == SUBREG
)
286 reg
= SUBREG_REG (reg
);
292 last_def
[REGNO (reg
)] = const0_rtx
;
295 /* Marks sets in basic block BB. If DOM is true, BB dominates the loop
299 mark_sets (basic_block bb
, bool dom
)
303 FOR_BB_INSNS (bb
, insn
)
309 && (set
= single_set (insn
)))
310 def
= mark_single_set (insn
, set
);
314 note_stores (PATTERN (insn
), kill_sets
, def
);
318 /* Prepare the data for an induction variable analysis of a LOOP. */
321 iv_analysis_loop_init (struct loop
*loop
)
323 basic_block
*body
= get_loop_body_in_dom_order (loop
);
326 if ((unsigned) get_max_uid () >= max_insn_no
)
328 /* Add some reserve for insns and registers produced in optimizations. */
329 max_insn_no
= get_max_uid () + 100;
332 insn_info
= xmalloc (max_insn_no
* sizeof (struct insn_info
));
335 if ((unsigned) max_reg_num () >= max_reg_no
)
337 max_reg_no
= max_reg_num () + 100;
340 last_def
= xmalloc (max_reg_no
* sizeof (rtx
));
343 bivs
= xmalloc (max_reg_no
* sizeof (struct rtx_iv
));
346 memset (last_def
, 0, max_reg_num () * sizeof (rtx
));
348 for (b
= 0; b
< loop
->num_nodes
; b
++)
350 assign_luids (body
[b
]);
351 mark_sets (body
[b
], just_once_each_iteration_p (loop
, body
[b
]));
357 /* Gets definition of REG reaching the INSN. If REG is not simple, const0_rtx
358 is returned. If INSN is before the first def in the loop, NULL_RTX is
362 iv_get_reaching_def (rtx insn
, rtx reg
)
364 unsigned regno
, luid
, auid
;
368 if (GET_CODE (reg
) == SUBREG
)
370 if (!subreg_lowpart_p (reg
))
372 reg
= SUBREG_REG (reg
);
379 || last_def
[regno
] == const0_rtx
)
380 return last_def
[regno
];
382 bb
= BLOCK_FOR_INSN (insn
);
383 luid
= insn_info
[INSN_UID (insn
)].luid
;
385 ainsn
= last_def
[regno
];
388 abb
= BLOCK_FOR_INSN (ainsn
);
390 if (dominated_by_p (CDI_DOMINATORS
, bb
, abb
))
393 auid
= INSN_UID (ainsn
);
394 ainsn
= insn_info
[auid
].prev_def
;
402 abb
= BLOCK_FOR_INSN (ainsn
);
406 auid
= INSN_UID (ainsn
);
407 if (luid
> insn_info
[auid
].luid
)
410 ainsn
= insn_info
[auid
].prev_def
;
416 /* Sets IV to invariant CST in MODE. Always returns true (just for
417 consistency with other iv manipulation functions that may fail). */
420 iv_constant (struct rtx_iv
*iv
, rtx cst
, enum machine_mode mode
)
422 if (mode
== VOIDmode
)
423 mode
= GET_MODE (cst
);
428 iv
->step
= const0_rtx
;
429 iv
->first_special
= false;
431 iv
->extend_mode
= iv
->mode
;
432 iv
->delta
= const0_rtx
;
433 iv
->mult
= const1_rtx
;
438 /* Evaluates application of subreg to MODE on IV. */
441 iv_subreg (struct rtx_iv
*iv
, enum machine_mode mode
)
443 if (iv
->extend_mode
== mode
)
446 if (GET_MODE_BITSIZE (mode
) > GET_MODE_BITSIZE (iv
->mode
))
452 iv
->base
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
453 simplify_gen_binary (MULT
, iv
->extend_mode
,
454 iv
->base
, iv
->mult
));
455 iv
->step
= simplify_gen_binary (MULT
, iv
->extend_mode
, iv
->step
, iv
->mult
);
456 iv
->mult
= const1_rtx
;
457 iv
->delta
= const0_rtx
;
458 iv
->first_special
= false;
463 /* Evaluates application of EXTEND to MODE on IV. */
466 iv_extend (struct rtx_iv
*iv
, enum rtx_code extend
, enum machine_mode mode
)
468 if (mode
!= iv
->extend_mode
)
471 if (iv
->extend
!= NIL
472 && iv
->extend
!= extend
)
480 /* Evaluates negation of IV. */
483 iv_neg (struct rtx_iv
*iv
)
485 if (iv
->extend
== NIL
)
487 iv
->base
= simplify_gen_unary (NEG
, iv
->extend_mode
,
488 iv
->base
, iv
->extend_mode
);
489 iv
->step
= simplify_gen_unary (NEG
, iv
->extend_mode
,
490 iv
->step
, iv
->extend_mode
);
494 iv
->delta
= simplify_gen_unary (NEG
, iv
->extend_mode
,
495 iv
->delta
, iv
->extend_mode
);
496 iv
->mult
= simplify_gen_unary (NEG
, iv
->extend_mode
,
497 iv
->mult
, iv
->extend_mode
);
503 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
506 iv_add (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
, enum rtx_code op
)
508 enum machine_mode mode
;
511 /* Extend the constant to extend_mode of the other operand if necessary. */
512 if (iv0
->extend
== NIL
513 && iv0
->mode
== iv0
->extend_mode
514 && iv0
->step
== const0_rtx
515 && GET_MODE_SIZE (iv0
->extend_mode
) < GET_MODE_SIZE (iv1
->extend_mode
))
517 iv0
->extend_mode
= iv1
->extend_mode
;
518 iv0
->base
= simplify_gen_unary (ZERO_EXTEND
, iv0
->extend_mode
,
519 iv0
->base
, iv0
->mode
);
521 if (iv1
->extend
== NIL
522 && iv1
->mode
== iv1
->extend_mode
523 && iv1
->step
== const0_rtx
524 && GET_MODE_SIZE (iv1
->extend_mode
) < GET_MODE_SIZE (iv0
->extend_mode
))
526 iv1
->extend_mode
= iv0
->extend_mode
;
527 iv1
->base
= simplify_gen_unary (ZERO_EXTEND
, iv1
->extend_mode
,
528 iv1
->base
, iv1
->mode
);
531 mode
= iv0
->extend_mode
;
532 if (mode
!= iv1
->extend_mode
)
535 if (iv0
->extend
== NIL
&& iv1
->extend
== NIL
)
537 if (iv0
->mode
!= iv1
->mode
)
540 iv0
->base
= simplify_gen_binary (op
, mode
, iv0
->base
, iv1
->base
);
541 iv0
->step
= simplify_gen_binary (op
, mode
, iv0
->step
, iv1
->step
);
546 /* Handle addition of constant. */
547 if (iv1
->extend
== NIL
549 && iv1
->step
== const0_rtx
)
551 iv0
->delta
= simplify_gen_binary (op
, mode
, iv0
->delta
, iv1
->base
);
555 if (iv0
->extend
== NIL
557 && iv0
->step
== const0_rtx
)
565 iv0
->delta
= simplify_gen_binary (PLUS
, mode
, iv0
->delta
, arg
);
572 /* Evaluates multiplication of IV by constant CST. */
575 iv_mult (struct rtx_iv
*iv
, rtx mby
)
577 enum machine_mode mode
= iv
->extend_mode
;
579 if (GET_MODE (mby
) != VOIDmode
580 && GET_MODE (mby
) != mode
)
583 if (iv
->extend
== NIL
)
585 iv
->base
= simplify_gen_binary (MULT
, mode
, iv
->base
, mby
);
586 iv
->step
= simplify_gen_binary (MULT
, mode
, iv
->step
, mby
);
590 iv
->delta
= simplify_gen_binary (MULT
, mode
, iv
->delta
, mby
);
591 iv
->mult
= simplify_gen_binary (MULT
, mode
, iv
->mult
, mby
);
597 /* Evaluates shift of IV by constant CST. */
600 iv_shift (struct rtx_iv
*iv
, rtx mby
)
602 enum machine_mode mode
= iv
->extend_mode
;
604 if (GET_MODE (mby
) != VOIDmode
605 && GET_MODE (mby
) != mode
)
608 if (iv
->extend
== NIL
)
610 iv
->base
= simplify_gen_binary (ASHIFT
, mode
, iv
->base
, mby
);
611 iv
->step
= simplify_gen_binary (ASHIFT
, mode
, iv
->step
, mby
);
615 iv
->delta
= simplify_gen_binary (ASHIFT
, mode
, iv
->delta
, mby
);
616 iv
->mult
= simplify_gen_binary (ASHIFT
, mode
, iv
->mult
, mby
);
622 /* The recursive part of get_biv_step. Gets the value of the single value
623 defined in INSN wrto initial value of REG inside loop, in shape described
627 get_biv_step_1 (rtx insn
, rtx reg
,
628 rtx
*inner_step
, enum machine_mode
*inner_mode
,
629 enum rtx_code
*extend
, enum machine_mode outer_mode
,
632 rtx set
, lhs
, rhs
, op0
= NULL_RTX
, op1
= NULL_RTX
;
633 rtx next
, nextr
, def_insn
, tmp
;
636 set
= single_set (insn
);
637 rhs
= find_reg_equal_equiv_note (insn
);
642 lhs
= SET_DEST (set
);
644 code
= GET_CODE (rhs
);
657 if (code
== PLUS
&& CONSTANT_P (op0
))
659 tmp
= op0
; op0
= op1
; op1
= tmp
;
662 if (!simple_reg_p (op0
)
663 || !CONSTANT_P (op1
))
666 if (GET_MODE (rhs
) != outer_mode
)
668 /* ppc64 uses expressions like
670 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
672 this is equivalent to
674 (set x':DI (plus:DI y:DI 1))
675 (set x:SI (subreg:SI (x':DI)). */
676 if (GET_CODE (op0
) != SUBREG
)
678 if (GET_MODE (SUBREG_REG (op0
)) != outer_mode
)
687 if (GET_MODE (rhs
) != outer_mode
)
691 if (!simple_reg_p (op0
))
701 if (GET_CODE (next
) == SUBREG
)
703 if (!subreg_lowpart_p (next
))
706 nextr
= SUBREG_REG (next
);
707 if (GET_MODE (nextr
) != outer_mode
)
713 def_insn
= iv_get_reaching_def (insn
, nextr
);
714 if (def_insn
== const0_rtx
)
719 if (!rtx_equal_p (nextr
, reg
))
722 *inner_step
= const0_rtx
;
724 *inner_mode
= outer_mode
;
725 *outer_step
= const0_rtx
;
727 else if (!get_biv_step_1 (def_insn
, reg
,
728 inner_step
, inner_mode
, extend
, outer_mode
,
732 if (GET_CODE (next
) == SUBREG
)
734 enum machine_mode amode
= GET_MODE (next
);
736 if (GET_MODE_SIZE (amode
) > GET_MODE_SIZE (*inner_mode
))
740 *inner_step
= simplify_gen_binary (PLUS
, outer_mode
,
741 *inner_step
, *outer_step
);
742 *outer_step
= const0_rtx
;
754 if (*inner_mode
== outer_mode
755 /* See comment in previous switch. */
756 || GET_MODE (rhs
) != outer_mode
)
757 *inner_step
= simplify_gen_binary (code
, outer_mode
,
760 *outer_step
= simplify_gen_binary (code
, outer_mode
,
766 if (GET_MODE (op0
) != *inner_mode
768 || *outer_step
!= const0_rtx
)
781 /* Gets the operation on register REG inside loop, in shape
783 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
785 If the operation cannot be described in this shape, return false. */
788 get_biv_step (rtx reg
, rtx
*inner_step
, enum machine_mode
*inner_mode
,
789 enum rtx_code
*extend
, enum machine_mode
*outer_mode
,
792 *outer_mode
= GET_MODE (reg
);
794 if (!get_biv_step_1 (last_def
[REGNO (reg
)], reg
,
795 inner_step
, inner_mode
, extend
, *outer_mode
,
799 if (*inner_mode
!= *outer_mode
803 if (*inner_mode
== *outer_mode
807 if (*inner_mode
== *outer_mode
808 && *outer_step
!= const0_rtx
)
814 /* Determines whether DEF is a biv and if so, stores its description
818 iv_analyze_biv (rtx def
, struct rtx_iv
*iv
)
821 rtx inner_step
, outer_step
;
822 enum machine_mode inner_mode
, outer_mode
;
823 enum rtx_code extend
;
827 fprintf (dump_file
, "Analysing ");
828 print_rtl (dump_file
, def
);
829 fprintf (dump_file
, " for bivness.\n");
834 if (!CONSTANT_P (def
))
837 return iv_constant (iv
, def
, VOIDmode
);
841 if (last_def
[regno
] == const0_rtx
)
844 fprintf (dump_file
, " not simple.\n");
848 if (last_def
[regno
] && bivs
[regno
].analysed
)
851 fprintf (dump_file
, " already analysed.\n");
854 return iv
->base
!= NULL_RTX
;
857 if (!last_def
[regno
])
859 iv_constant (iv
, def
, VOIDmode
);
864 if (!get_biv_step (def
, &inner_step
, &inner_mode
, &extend
,
865 &outer_mode
, &outer_step
))
871 /* Loop transforms base to es (base + inner_step) + outer_step,
872 where es means extend of subreg between inner_mode and outer_mode.
873 The corresponding induction variable is
875 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
877 iv
->base
= simplify_gen_binary (MINUS
, outer_mode
, def
, outer_step
);
878 iv
->step
= simplify_gen_binary (PLUS
, outer_mode
, inner_step
, outer_step
);
879 iv
->mode
= inner_mode
;
880 iv
->extend_mode
= outer_mode
;
882 iv
->mult
= const1_rtx
;
883 iv
->delta
= outer_step
;
884 iv
->first_special
= inner_mode
!= outer_mode
;
889 fprintf (dump_file
, " ");
890 dump_iv_info (dump_file
, iv
);
891 fprintf (dump_file
, "\n");
896 return iv
->base
!= NULL_RTX
;
899 /* Analyzes operand OP of INSN and stores the result to *IV. */
902 iv_analyze_op (rtx insn
, rtx op
, struct rtx_iv
*iv
)
906 bool inv
= CONSTANT_P (op
);
910 fprintf (dump_file
, "Analysing operand ");
911 print_rtl (dump_file
, op
);
912 fprintf (dump_file
, " of insn ");
913 print_rtl_single (dump_file
, insn
);
916 if (GET_CODE (op
) == SUBREG
)
918 if (!subreg_lowpart_p (op
))
921 if (!iv_analyze_op (insn
, SUBREG_REG (op
), iv
))
924 return iv_subreg (iv
, GET_MODE (op
));
930 if (!last_def
[regno
])
932 else if (last_def
[regno
] == const0_rtx
)
935 fprintf (dump_file
, " not simple.\n");
942 iv_constant (iv
, op
, VOIDmode
);
946 fprintf (dump_file
, " ");
947 dump_iv_info (dump_file
, iv
);
948 fprintf (dump_file
, "\n");
953 def_insn
= iv_get_reaching_def (insn
, op
);
954 if (def_insn
== const0_rtx
)
957 fprintf (dump_file
, " not simple.\n");
961 return iv_analyze (def_insn
, op
, iv
);
964 /* Analyzes iv DEF defined in INSN and stores the result to *IV. */
967 iv_analyze (rtx insn
, rtx def
, struct rtx_iv
*iv
)
970 rtx set
, rhs
, mby
= NULL_RTX
, tmp
;
971 rtx op0
= NULL_RTX
, op1
= NULL_RTX
;
972 struct rtx_iv iv0
, iv1
;
973 enum machine_mode amode
;
976 if (insn
== const0_rtx
)
979 if (GET_CODE (def
) == SUBREG
)
981 if (!subreg_lowpart_p (def
))
984 if (!iv_analyze (insn
, SUBREG_REG (def
), iv
))
987 return iv_subreg (iv
, GET_MODE (def
));
991 return iv_analyze_biv (def
, iv
);
995 fprintf (dump_file
, "Analysing def of ");
996 print_rtl (dump_file
, def
);
997 fprintf (dump_file
, " in insn ");
998 print_rtl_single (dump_file
, insn
);
1001 uid
= INSN_UID (insn
);
1002 if (insn_info
[uid
].iv
.analysed
)
1005 fprintf (dump_file
, " already analysed.\n");
1006 *iv
= insn_info
[uid
].iv
;
1007 return iv
->base
!= NULL_RTX
;
1010 iv
->mode
= VOIDmode
;
1011 iv
->base
= NULL_RTX
;
1012 iv
->step
= NULL_RTX
;
1014 set
= single_set (insn
);
1015 rhs
= find_reg_equal_equiv_note (insn
);
1017 rhs
= XEXP (rhs
, 0);
1019 rhs
= SET_SRC (set
);
1020 code
= GET_CODE (rhs
);
1022 if (CONSTANT_P (rhs
))
1025 amode
= GET_MODE (def
);
1032 if (!subreg_lowpart_p (rhs
))
1044 op0
= XEXP (rhs
, 0);
1049 op0
= XEXP (rhs
, 0);
1050 op1
= XEXP (rhs
, 1);
1054 op0
= XEXP (rhs
, 0);
1055 mby
= XEXP (rhs
, 1);
1056 if (!CONSTANT_P (mby
))
1058 if (!CONSTANT_P (op0
))
1067 if (CONSTANT_P (XEXP (rhs
, 0)))
1069 op0
= XEXP (rhs
, 0);
1070 mby
= XEXP (rhs
, 1);
1077 amode
= GET_MODE (rhs
);
1082 if (!iv_analyze_op (insn
, op0
, &iv0
))
1085 if (iv0
.mode
== VOIDmode
)
1088 iv0
.extend_mode
= amode
;
1094 if (!iv_analyze_op (insn
, op1
, &iv1
))
1097 if (iv1
.mode
== VOIDmode
)
1100 iv1
.extend_mode
= amode
;
1108 if (!iv_extend (&iv0
, code
, amode
))
1119 if (!iv_add (&iv0
, &iv1
, code
))
1124 if (!iv_mult (&iv0
, mby
))
1129 if (!iv_shift (&iv0
, mby
))
1140 iv
->analysed
= true;
1141 insn_info
[uid
].iv
= *iv
;
1145 print_rtl (dump_file
, def
);
1146 fprintf (dump_file
, " in insn ");
1147 print_rtl_single (dump_file
, insn
);
1148 fprintf (dump_file
, " is ");
1149 dump_iv_info (dump_file
, iv
);
1150 fprintf (dump_file
, "\n");
1153 return iv
->base
!= NULL_RTX
;
1156 /* Calculates value of IV at ITERATION-th iteration. */
1159 get_iv_value (struct rtx_iv
*iv
, rtx iteration
)
1163 /* We would need to generate some if_then_else patterns, and so far
1164 it is not needed anywhere. */
1165 if (iv
->first_special
)
1168 if (iv
->step
!= const0_rtx
&& iteration
!= const0_rtx
)
1169 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->base
,
1170 simplify_gen_binary (MULT
, iv
->extend_mode
,
1171 iv
->step
, iteration
));
1175 if (iv
->extend_mode
== iv
->mode
)
1178 val
= lowpart_subreg (iv
->mode
, val
, iv
->extend_mode
);
1180 if (iv
->extend
== NIL
)
1183 val
= simplify_gen_unary (iv
->extend
, iv
->extend_mode
, val
, iv
->mode
);
1184 val
= simplify_gen_binary (PLUS
, iv
->extend_mode
, iv
->delta
,
1185 simplify_gen_binary (MULT
, iv
->extend_mode
,
1191 /* Free the data for an induction variable analysis. */
1194 iv_analysis_done (void)
1215 /* Computes inverse to X modulo (1 << MOD). */
1217 static unsigned HOST_WIDEST_INT
1218 inverse (unsigned HOST_WIDEST_INT x
, int mod
)
1220 unsigned HOST_WIDEST_INT mask
=
1221 ((unsigned HOST_WIDEST_INT
) 1 << (mod
- 1) << 1) - 1;
1222 unsigned HOST_WIDEST_INT rslt
= 1;
1225 for (i
= 0; i
< mod
- 1; i
++)
1227 rslt
= (rslt
* x
) & mask
;
1234 /* Tries to estimate the maximum number of iterations. */
1236 static unsigned HOST_WIDEST_INT
1237 determine_max_iter (struct niter_desc
*desc
)
1239 rtx niter
= desc
->niter_expr
;
1240 rtx mmin
, mmax
, left
, right
;
1241 unsigned HOST_WIDEST_INT nmax
, inc
;
1243 if (GET_CODE (niter
) == AND
1244 && GET_CODE (XEXP (niter
, 0)) == CONST_INT
)
1246 nmax
= INTVAL (XEXP (niter
, 0));
1247 if (!(nmax
& (nmax
+ 1)))
1249 desc
->niter_max
= nmax
;
1254 get_mode_bounds (desc
->mode
, desc
->signed_p
, desc
->mode
, &mmin
, &mmax
);
1255 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1257 if (GET_CODE (niter
) == UDIV
)
1259 if (GET_CODE (XEXP (niter
, 1)) != CONST_INT
)
1261 desc
->niter_max
= nmax
;
1264 inc
= INTVAL (XEXP (niter
, 1));
1265 niter
= XEXP (niter
, 0);
1270 if (GET_CODE (niter
) == PLUS
)
1272 left
= XEXP (niter
, 0);
1273 right
= XEXP (niter
, 0);
1275 if (GET_CODE (right
) == CONST_INT
)
1276 right
= GEN_INT (-INTVAL (right
));
1278 else if (GET_CODE (niter
) == MINUS
)
1280 left
= XEXP (niter
, 0);
1281 right
= XEXP (niter
, 0);
1289 if (GET_CODE (left
) == CONST_INT
)
1291 if (GET_CODE (right
) == CONST_INT
)
1293 nmax
= INTVAL (mmax
) - INTVAL (mmin
);
1295 desc
->niter_max
= nmax
/ inc
;
1299 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1302 altered_reg_used (rtx
*reg
, void *alt
)
1307 return REGNO_REG_SET_P (alt
, REGNO (*reg
));
1310 /* Marks registers altered by EXPR in set ALT. */
1313 mark_altered (rtx expr
, rtx by ATTRIBUTE_UNUSED
, void *alt
)
1315 if (GET_CODE (expr
) == SUBREG
)
1316 expr
= SUBREG_REG (expr
);
1320 SET_REGNO_REG_SET (alt
, REGNO (expr
));
1323 /* Checks whether RHS is simple enough to process. */
1326 simple_rhs_p (rtx rhs
)
1330 if (CONSTANT_P (rhs
)
1334 switch (GET_CODE (rhs
))
1338 op0
= XEXP (rhs
, 0);
1339 op1
= XEXP (rhs
, 1);
1340 /* Allow reg + const sets only. */
1341 if (REG_P (op0
) && CONSTANT_P (op1
))
1343 if (REG_P (op1
) && CONSTANT_P (op0
))
1353 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1357 simplify_using_assignment (rtx insn
, rtx
*expr
, regset altered
)
1359 rtx set
= single_set (insn
);
1365 lhs
= SET_DEST (set
);
1367 || altered_reg_used (&lhs
, altered
))
1373 note_stores (PATTERN (insn
), mark_altered
, altered
);
1378 /* Kill all call clobbered registers. */
1379 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1380 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1381 SET_REGNO_REG_SET (altered
, i
);
1387 rhs
= find_reg_equal_equiv_note (insn
);
1389 rhs
= XEXP (rhs
, 0);
1391 rhs
= SET_SRC (set
);
1393 if (!simple_rhs_p (rhs
))
1396 if (for_each_rtx (&rhs
, altered_reg_used
, altered
))
1399 *expr
= simplify_replace_rtx (*expr
, lhs
, rhs
);
1402 /* Checks whether A implies B. */
1405 implies_p (rtx a
, rtx b
)
1407 rtx op0
, op1
, opb0
, opb1
, r
;
1408 enum machine_mode mode
;
1410 if (GET_CODE (a
) == EQ
)
1417 r
= simplify_replace_rtx (b
, op0
, op1
);
1418 if (r
== const_true_rtx
)
1424 r
= simplify_replace_rtx (b
, op1
, op0
);
1425 if (r
== const_true_rtx
)
1430 /* A < B implies A + 1 <= B. */
1431 if ((GET_CODE (a
) == GT
|| GET_CODE (a
) == LT
)
1432 && (GET_CODE (b
) == GE
|| GET_CODE (b
) == LE
))
1439 if (GET_CODE (a
) == GT
)
1446 if (GET_CODE (b
) == GE
)
1453 mode
= GET_MODE (op0
);
1454 if (mode
!= GET_MODE (opb0
))
1456 else if (mode
== VOIDmode
)
1458 mode
= GET_MODE (op1
);
1459 if (mode
!= GET_MODE (opb1
))
1463 if (mode
!= VOIDmode
1464 && rtx_equal_p (op1
, opb1
)
1465 && simplify_gen_binary (MINUS
, mode
, opb0
, op0
) == const1_rtx
)
1472 /* Canonicalizes COND so that
1474 (1) Ensure that operands are ordered according to
1475 swap_commutative_operands_p.
1476 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1477 for GE, GEU, and LEU. */
1480 canon_condition (rtx cond
)
1485 enum machine_mode mode
;
1487 code
= GET_CODE (cond
);
1488 op0
= XEXP (cond
, 0);
1489 op1
= XEXP (cond
, 1);
1491 if (swap_commutative_operands_p (op0
, op1
))
1493 code
= swap_condition (code
);
1499 mode
= GET_MODE (op0
);
1500 if (mode
== VOIDmode
)
1501 mode
= GET_MODE (op1
);
1502 if (mode
== VOIDmode
)
1505 if (GET_CODE (op1
) == CONST_INT
1506 && GET_MODE_CLASS (mode
) != MODE_CC
1507 && GET_MODE_BITSIZE (mode
) <= HOST_BITS_PER_WIDE_INT
)
1509 HOST_WIDE_INT const_val
= INTVAL (op1
);
1510 unsigned HOST_WIDE_INT uconst_val
= const_val
;
1511 unsigned HOST_WIDE_INT max_val
1512 = (unsigned HOST_WIDE_INT
) GET_MODE_MASK (mode
);
1517 if ((unsigned HOST_WIDE_INT
) const_val
!= max_val
>> 1)
1518 code
= LT
, op1
= gen_int_mode (const_val
+ 1, GET_MODE (op0
));
1521 /* When cross-compiling, const_val might be sign-extended from
1522 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1524 if ((HOST_WIDE_INT
) (const_val
& max_val
)
1525 != (((HOST_WIDE_INT
) 1
1526 << (GET_MODE_BITSIZE (GET_MODE (op0
)) - 1))))
1527 code
= GT
, op1
= gen_int_mode (const_val
- 1, mode
);
1531 if (uconst_val
< max_val
)
1532 code
= LTU
, op1
= gen_int_mode (uconst_val
+ 1, mode
);
1536 if (uconst_val
!= 0)
1537 code
= GTU
, op1
= gen_int_mode (uconst_val
- 1, mode
);
1545 if (op0
!= XEXP (cond
, 0)
1546 || op1
!= XEXP (cond
, 1)
1547 || code
!= GET_CODE (cond
)
1548 || GET_MODE (cond
) != SImode
)
1549 cond
= gen_rtx_fmt_ee (code
, SImode
, op0
, op1
);
1554 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1555 set of altered regs. */
1558 simplify_using_condition (rtx cond
, rtx
*expr
, regset altered
)
1560 rtx rev
, reve
, exp
= *expr
;
1562 if (!COMPARISON_P (exp
))
1565 /* If some register gets altered later, we do not really speak about its
1566 value at the time of comparison. */
1568 && for_each_rtx (&cond
, altered_reg_used
, altered
))
1571 rev
= reversed_condition (cond
);
1572 reve
= reversed_condition (exp
);
1574 cond
= canon_condition (cond
);
1575 exp
= canon_condition (exp
);
1577 rev
= canon_condition (rev
);
1579 reve
= canon_condition (reve
);
1581 if (rtx_equal_p (exp
, cond
))
1583 *expr
= const_true_rtx
;
1588 if (rev
&& rtx_equal_p (exp
, rev
))
1594 if (implies_p (cond
, exp
))
1596 *expr
= const_true_rtx
;
1600 if (reve
&& implies_p (cond
, reve
))
1606 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1608 if (rev
&& implies_p (exp
, rev
))
1614 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1615 if (rev
&& reve
&& implies_p (reve
, rev
))
1617 *expr
= const_true_rtx
;
1621 /* We would like to have some other tests here. TODO. */
1626 /* Use relationship between A and *B to eventually eliminate *B.
1627 OP is the operation we consider. */
1630 eliminate_implied_condition (enum rtx_code op
, rtx a
, rtx
*b
)
1634 /* If A implies *B, we may replace *B by true. */
1635 if (implies_p (a
, *b
))
1636 *b
= const_true_rtx
;
1640 /* If *B implies A, we may replace *B by false. */
1641 if (implies_p (*b
, a
))
1648 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1649 operation we consider. */
1652 eliminate_implied_conditions (enum rtx_code op
, rtx
*head
, rtx tail
)
1656 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1657 eliminate_implied_condition (op
, *head
, &XEXP (elt
, 0));
1658 for (elt
= tail
; elt
; elt
= XEXP (elt
, 1))
1659 eliminate_implied_condition (op
, XEXP (elt
, 0), head
);
1662 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1663 is a list, its elements are assumed to be combined using OP. */
1666 simplify_using_initial_values (struct loop
*loop
, enum rtx_code op
, rtx
*expr
)
1668 rtx head
, tail
, insn
;
1671 regset_head altered_head
;
1677 if (CONSTANT_P (*expr
))
1680 if (GET_CODE (*expr
) == EXPR_LIST
)
1682 head
= XEXP (*expr
, 0);
1683 tail
= XEXP (*expr
, 1);
1685 eliminate_implied_conditions (op
, &head
, tail
);
1689 neutral
= const_true_rtx
;
1694 neutral
= const0_rtx
;
1695 aggr
= const_true_rtx
;
1700 simplify_using_initial_values (loop
, NIL
, &head
);
1703 XEXP (*expr
, 0) = aggr
;
1704 XEXP (*expr
, 1) = NULL_RTX
;
1707 else if (head
== neutral
)
1710 simplify_using_initial_values (loop
, op
, expr
);
1713 simplify_using_initial_values (loop
, op
, &tail
);
1715 if (tail
&& XEXP (tail
, 0) == aggr
)
1721 XEXP (*expr
, 0) = head
;
1722 XEXP (*expr
, 1) = tail
;
1729 e
= loop_preheader_edge (loop
);
1730 if (e
->src
== ENTRY_BLOCK_PTR
)
1733 altered
= INITIALIZE_REG_SET (altered_head
);
1737 insn
= BB_END (e
->src
);
1738 if (any_condjump_p (insn
))
1740 rtx cond
= get_condition (BB_END (e
->src
), NULL
, false, true);
1742 if (cond
&& (e
->flags
& EDGE_FALLTHRU
))
1743 cond
= reversed_condition (cond
);
1746 simplify_using_condition (cond
, expr
, altered
);
1747 if (CONSTANT_P (*expr
))
1749 FREE_REG_SET (altered
);
1755 FOR_BB_INSNS_REVERSE (e
->src
, insn
)
1760 simplify_using_assignment (insn
, expr
, altered
);
1761 if (CONSTANT_P (*expr
))
1763 FREE_REG_SET (altered
);
1770 || e
->src
== ENTRY_BLOCK_PTR
)
1774 FREE_REG_SET (altered
);
1777 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1778 that IV occurs as left operands of comparison COND and its signedness
1779 is SIGNED_P to DESC. */
1782 shorten_into_mode (struct rtx_iv
*iv
, enum machine_mode mode
,
1783 enum rtx_code cond
, bool signed_p
, struct niter_desc
*desc
)
1785 rtx mmin
, mmax
, cond_over
, cond_under
;
1787 get_mode_bounds (mode
, signed_p
, iv
->extend_mode
, &mmin
, &mmax
);
1788 cond_under
= simplify_gen_relational (LT
, SImode
, iv
->extend_mode
,
1790 cond_over
= simplify_gen_relational (GT
, SImode
, iv
->extend_mode
,
1799 if (cond_under
!= const0_rtx
)
1801 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1802 if (cond_over
!= const0_rtx
)
1803 desc
->noloop_assumptions
=
1804 alloc_EXPR_LIST (0, cond_over
, desc
->noloop_assumptions
);
1811 if (cond_over
!= const0_rtx
)
1813 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1814 if (cond_under
!= const0_rtx
)
1815 desc
->noloop_assumptions
=
1816 alloc_EXPR_LIST (0, cond_under
, desc
->noloop_assumptions
);
1820 if (cond_over
!= const0_rtx
)
1822 alloc_EXPR_LIST (0, cond_over
, desc
->infinite
);
1823 if (cond_under
!= const0_rtx
)
1825 alloc_EXPR_LIST (0, cond_under
, desc
->infinite
);
1833 iv
->extend
= signed_p
? SIGN_EXTEND
: ZERO_EXTEND
;
1836 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1837 subregs of the same mode if possible (sometimes it is necessary to add
1838 some assumptions to DESC). */
1841 canonicalize_iv_subregs (struct rtx_iv
*iv0
, struct rtx_iv
*iv1
,
1842 enum rtx_code cond
, struct niter_desc
*desc
)
1844 enum machine_mode comp_mode
;
1847 /* If the ivs behave specially in the first iteration, or are
1848 added/multiplied after extending, we ignore them. */
1849 if (iv0
->first_special
|| iv0
->mult
!= const1_rtx
|| iv0
->delta
!= const0_rtx
)
1851 if (iv1
->first_special
|| iv1
->mult
!= const1_rtx
|| iv1
->delta
!= const0_rtx
)
1854 /* If there is some extend, it must match signedness of the comparison. */
1859 if (iv0
->extend
== ZERO_EXTEND
1860 || iv1
->extend
== ZERO_EXTEND
)
1867 if (iv0
->extend
== SIGN_EXTEND
1868 || iv1
->extend
== SIGN_EXTEND
)
1874 if (iv0
->extend
!= NIL
1875 && iv1
->extend
!= NIL
1876 && iv0
->extend
!= iv1
->extend
)
1880 if (iv0
->extend
!= NIL
)
1881 signed_p
= iv0
->extend
== SIGN_EXTEND
;
1882 if (iv1
->extend
!= NIL
)
1883 signed_p
= iv1
->extend
== SIGN_EXTEND
;
1890 /* Values of both variables should be computed in the same mode. These
1891 might indeed be different, if we have comparison like
1893 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1895 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1896 in different modes. This does not seem impossible to handle, but
1897 it hardly ever occurs in practice.
1899 The only exception is the case when one of operands is invariant.
1900 For example pentium 3 generates comparisons like
1901 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1902 definitely do not want this prevent the optimization. */
1903 comp_mode
= iv0
->extend_mode
;
1904 if (GET_MODE_BITSIZE (comp_mode
) < GET_MODE_BITSIZE (iv1
->extend_mode
))
1905 comp_mode
= iv1
->extend_mode
;
1907 if (iv0
->extend_mode
!= comp_mode
)
1909 if (iv0
->mode
!= iv0
->extend_mode
1910 || iv0
->step
!= const0_rtx
)
1913 iv0
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1914 comp_mode
, iv0
->base
, iv0
->mode
);
1915 iv0
->extend_mode
= comp_mode
;
1918 if (iv1
->extend_mode
!= comp_mode
)
1920 if (iv1
->mode
!= iv1
->extend_mode
1921 || iv1
->step
!= const0_rtx
)
1924 iv1
->base
= simplify_gen_unary (signed_p
? SIGN_EXTEND
: ZERO_EXTEND
,
1925 comp_mode
, iv1
->base
, iv1
->mode
);
1926 iv1
->extend_mode
= comp_mode
;
1929 /* Check that both ivs belong to a range of a single mode. If one of the
1930 operands is an invariant, we may need to shorten it into the common
1932 if (iv0
->mode
== iv0
->extend_mode
1933 && iv0
->step
== const0_rtx
1934 && iv0
->mode
!= iv1
->mode
)
1935 shorten_into_mode (iv0
, iv1
->mode
, cond
, signed_p
, desc
);
1937 if (iv1
->mode
== iv1
->extend_mode
1938 && iv1
->step
== const0_rtx
1939 && iv0
->mode
!= iv1
->mode
)
1940 shorten_into_mode (iv1
, iv0
->mode
, swap_condition (cond
), signed_p
, desc
);
1942 if (iv0
->mode
!= iv1
->mode
)
1945 desc
->mode
= iv0
->mode
;
1946 desc
->signed_p
= signed_p
;
1951 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1952 the result into DESC. Very similar to determine_number_of_iterations
1953 (basically its rtl version), complicated by things like subregs. */
1956 iv_number_of_iterations (struct loop
*loop
, rtx insn
, rtx condition
,
1957 struct niter_desc
*desc
)
1959 rtx op0
, op1
, delta
, step
, bound
, may_xform
, def_insn
, tmp
, tmp0
, tmp1
;
1960 struct rtx_iv iv0
, iv1
, tmp_iv
;
1961 rtx assumption
, may_not_xform
;
1963 enum machine_mode mode
, comp_mode
;
1964 rtx mmin
, mmax
, mode_mmin
, mode_mmax
;
1965 unsigned HOST_WIDEST_INT s
, size
, d
, inv
;
1966 HOST_WIDEST_INT up
, down
, inc
;
1967 int was_sharp
= false;
1970 /* The meaning of these assumptions is this:
1972 then the rest of information does not have to be valid
1973 if noloop_assumptions then the loop does not roll
1974 if infinite then this exit is never used */
1976 desc
->assumptions
= NULL_RTX
;
1977 desc
->noloop_assumptions
= NULL_RTX
;
1978 desc
->infinite
= NULL_RTX
;
1979 desc
->simple_p
= true;
1981 desc
->const_iter
= false;
1982 desc
->niter_expr
= NULL_RTX
;
1983 desc
->niter_max
= 0;
1985 cond
= GET_CODE (condition
);
1986 if (!COMPARISON_P (condition
))
1989 mode
= GET_MODE (XEXP (condition
, 0));
1990 if (mode
== VOIDmode
)
1991 mode
= GET_MODE (XEXP (condition
, 1));
1992 /* The constant comparisons should be folded. */
1993 if (mode
== VOIDmode
)
1996 /* We only handle integers or pointers. */
1997 if (GET_MODE_CLASS (mode
) != MODE_INT
1998 && GET_MODE_CLASS (mode
) != MODE_PARTIAL_INT
)
2001 op0
= XEXP (condition
, 0);
2002 def_insn
= iv_get_reaching_def (insn
, op0
);
2003 if (!iv_analyze (def_insn
, op0
, &iv0
))
2005 if (iv0
.extend_mode
== VOIDmode
)
2006 iv0
.mode
= iv0
.extend_mode
= mode
;
2008 op1
= XEXP (condition
, 1);
2009 def_insn
= iv_get_reaching_def (insn
, op1
);
2010 if (!iv_analyze (def_insn
, op1
, &iv1
))
2012 if (iv1
.extend_mode
== VOIDmode
)
2013 iv1
.mode
= iv1
.extend_mode
= mode
;
2015 if (GET_MODE_BITSIZE (iv0
.extend_mode
) > HOST_BITS_PER_WIDE_INT
2016 || GET_MODE_BITSIZE (iv1
.extend_mode
) > HOST_BITS_PER_WIDE_INT
)
2019 /* Check condition and normalize it. */
2027 tmp_iv
= iv0
; iv0
= iv1
; iv1
= tmp_iv
;
2028 cond
= swap_condition (cond
);
2040 /* Handle extends. This is relatively nontrivial, so we only try in some
2041 easy cases, when we can canonicalize the ivs (possibly by adding some
2042 assumptions) to shape subreg (base + i * step). This function also fills
2043 in desc->mode and desc->signed_p. */
2045 if (!canonicalize_iv_subregs (&iv0
, &iv1
, cond
, desc
))
2048 comp_mode
= iv0
.extend_mode
;
2050 size
= GET_MODE_BITSIZE (mode
);
2051 get_mode_bounds (mode
, (cond
== LE
|| cond
== LT
), comp_mode
, &mmin
, &mmax
);
2052 mode_mmin
= lowpart_subreg (mode
, mmin
, comp_mode
);
2053 mode_mmax
= lowpart_subreg (mode
, mmax
, comp_mode
);
2055 if (GET_CODE (iv0
.step
) != CONST_INT
|| GET_CODE (iv1
.step
) != CONST_INT
)
2058 /* We can take care of the case of two induction variables chasing each other
2059 if the test is NE. I have never seen a loop using it, but still it is
2061 if (iv0
.step
!= const0_rtx
&& iv1
.step
!= const0_rtx
)
2066 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2067 iv1
.step
= const0_rtx
;
2070 /* This is either infinite loop or the one that ends immediately, depending
2071 on initial values. Unswitching should remove this kind of conditions. */
2072 if (iv0
.step
== const0_rtx
&& iv1
.step
== const0_rtx
)
2075 /* Ignore loops of while (i-- < 10) type. */
2077 && (INTVAL (iv0
.step
) < 0 || INTVAL (iv1
.step
) > 0))
2080 /* Some more condition normalization. We must record some assumptions
2081 due to overflows. */
2086 /* We want to take care only of non-sharp relationals; this is easy,
2087 as in cases the overflow would make the transformation unsafe
2088 the loop does not roll. Seemingly it would make more sense to want
2089 to take care of sharp relationals instead, as NE is more similar to
2090 them, but the problem is that here the transformation would be more
2091 difficult due to possibly infinite loops. */
2092 if (iv0
.step
== const0_rtx
)
2094 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2095 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2097 if (assumption
== const_true_rtx
)
2099 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2100 iv0
.base
, const1_rtx
);
2104 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2105 assumption
= simplify_gen_relational (EQ
, SImode
, mode
, tmp
,
2107 if (assumption
== const_true_rtx
)
2109 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
,
2110 iv1
.base
, constm1_rtx
);
2113 if (assumption
!= const0_rtx
)
2114 desc
->noloop_assumptions
=
2115 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2116 cond
= (cond
== LT
) ? LE
: LEU
;
2118 /* It will be useful to be able to tell the difference once more in
2119 LE -> NE reduction. */
2125 /* Take care of trivially infinite loops. */
2128 if (iv0
.step
== const0_rtx
)
2130 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2131 if (rtx_equal_p (tmp
, mode_mmin
))
2134 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2140 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2141 if (rtx_equal_p (tmp
, mode_mmax
))
2144 alloc_EXPR_LIST (0, const_true_rtx
, NULL_RTX
);
2150 /* If we can we want to take care of NE conditions instead of size
2151 comparisons, as they are much more friendly (most importantly
2152 this takes care of special handling of loops with step 1). We can
2153 do it if we first check that upper bound is greater or equal to
2154 lower bound, their difference is constant c modulo step and that
2155 there is not an overflow. */
2158 if (iv0
.step
== const0_rtx
)
2159 step
= simplify_gen_unary (NEG
, comp_mode
, iv1
.step
, comp_mode
);
2162 delta
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2163 delta
= lowpart_subreg (mode
, delta
, comp_mode
);
2164 delta
= simplify_gen_binary (UMOD
, mode
, delta
, step
);
2165 may_xform
= const0_rtx
;
2166 may_not_xform
= const_true_rtx
;
2168 if (GET_CODE (delta
) == CONST_INT
)
2170 if (was_sharp
&& INTVAL (delta
) == INTVAL (step
) - 1)
2172 /* A special case. We have transformed condition of type
2173 for (i = 0; i < 4; i += 4)
2175 for (i = 0; i <= 3; i += 4)
2176 obviously if the test for overflow during that transformation
2177 passed, we cannot overflow here. Most importantly any
2178 loop with sharp end condition and step 1 falls into this
2179 category, so handling this case specially is definitely
2180 worth the troubles. */
2181 may_xform
= const_true_rtx
;
2183 else if (iv0
.step
== const0_rtx
)
2185 bound
= simplify_gen_binary (PLUS
, comp_mode
, mmin
, step
);
2186 bound
= simplify_gen_binary (MINUS
, comp_mode
, bound
, delta
);
2187 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2188 tmp
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2189 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2191 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2197 bound
= simplify_gen_binary (MINUS
, comp_mode
, mmax
, step
);
2198 bound
= simplify_gen_binary (PLUS
, comp_mode
, bound
, delta
);
2199 bound
= lowpart_subreg (mode
, bound
, comp_mode
);
2200 tmp
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2201 may_xform
= simplify_gen_relational (cond
, SImode
, mode
,
2203 may_not_xform
= simplify_gen_relational (reverse_condition (cond
),
2209 if (may_xform
!= const0_rtx
)
2211 /* We perform the transformation always provided that it is not
2212 completely senseless. This is OK, as we would need this assumption
2213 to determine the number of iterations anyway. */
2214 if (may_xform
!= const_true_rtx
)
2216 /* If the step is a power of two and the final value we have
2217 computed overflows, the cycle is infinite. Otherwise it
2218 is nontrivial to compute the number of iterations. */
2220 if ((s
& (s
- 1)) == 0)
2221 desc
->infinite
= alloc_EXPR_LIST (0, may_not_xform
,
2224 desc
->assumptions
= alloc_EXPR_LIST (0, may_xform
,
2228 /* We are going to lose some information about upper bound on
2229 number of iterations in this step, so record the information
2231 inc
= INTVAL (iv0
.step
) - INTVAL (iv1
.step
);
2232 if (GET_CODE (iv1
.base
) == CONST_INT
)
2233 up
= INTVAL (iv1
.base
);
2235 up
= INTVAL (mode_mmax
) - inc
;
2236 down
= INTVAL (GET_CODE (iv0
.base
) == CONST_INT
2239 desc
->niter_max
= (up
- down
) / inc
+ 1;
2241 if (iv0
.step
== const0_rtx
)
2243 iv0
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, delta
);
2244 iv0
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.base
, step
);
2248 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, delta
);
2249 iv1
.base
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, step
);
2252 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2253 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2254 assumption
= simplify_gen_relational (reverse_condition (cond
),
2255 SImode
, mode
, tmp0
, tmp1
);
2256 if (assumption
== const_true_rtx
)
2258 else if (assumption
!= const0_rtx
)
2259 desc
->noloop_assumptions
=
2260 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2265 /* Count the number of iterations. */
2268 /* Everything we do here is just arithmetics modulo size of mode. This
2269 makes us able to do more involved computations of number of iterations
2270 than in other cases. First transform the condition into shape
2271 s * i <> c, with s positive. */
2272 iv1
.base
= simplify_gen_binary (MINUS
, comp_mode
, iv1
.base
, iv0
.base
);
2273 iv0
.base
= const0_rtx
;
2274 iv0
.step
= simplify_gen_binary (MINUS
, comp_mode
, iv0
.step
, iv1
.step
);
2275 iv1
.step
= const0_rtx
;
2276 if (INTVAL (iv0
.step
) < 0)
2278 iv0
.step
= simplify_gen_unary (NEG
, comp_mode
, iv0
.step
, mode
);
2279 iv1
.base
= simplify_gen_unary (NEG
, comp_mode
, iv1
.base
, mode
);
2281 iv0
.step
= lowpart_subreg (mode
, iv0
.step
, comp_mode
);
2283 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2284 is infinite. Otherwise, the number of iterations is
2285 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2286 s
= INTVAL (iv0
.step
); d
= 1;
2293 bound
= GEN_INT (((unsigned HOST_WIDEST_INT
) 1 << (size
- 1 ) << 1) - 1);
2295 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2296 tmp
= simplify_gen_binary (UMOD
, mode
, tmp1
, GEN_INT (d
));
2297 assumption
= simplify_gen_relational (NE
, SImode
, mode
, tmp
, const0_rtx
);
2298 desc
->infinite
= alloc_EXPR_LIST (0, assumption
, desc
->infinite
);
2300 tmp
= simplify_gen_binary (UDIV
, mode
, tmp1
, GEN_INT (d
));
2301 inv
= inverse (s
, size
);
2302 inv
= trunc_int_for_mode (inv
, mode
);
2303 tmp
= simplify_gen_binary (MULT
, mode
, tmp
, GEN_INT (inv
));
2304 desc
->niter_expr
= simplify_gen_binary (AND
, mode
, tmp
, bound
);
2308 if (iv1
.step
== const0_rtx
)
2309 /* Condition in shape a + s * i <= b
2310 We must know that b + s does not overflow and a <= b + s and then we
2311 can compute number of iterations as (b + s - a) / s. (It might
2312 seem that we in fact could be more clever about testing the b + s
2313 overflow condition using some information about b - a mod s,
2314 but it was already taken into account during LE -> NE transform). */
2317 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2318 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2320 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmax
,
2321 lowpart_subreg (mode
, step
, comp_mode
));
2322 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2325 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2327 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv1
.base
, iv0
.step
);
2328 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2329 assumption
= simplify_gen_relational (reverse_condition (cond
),
2330 SImode
, mode
, tmp0
, tmp
);
2332 delta
= simplify_gen_binary (PLUS
, mode
, tmp1
, step
);
2333 delta
= simplify_gen_binary (MINUS
, mode
, delta
, tmp0
);
2337 /* Condition in shape a <= b - s * i
2338 We must know that a - s does not overflow and a - s <= b and then
2339 we can again compute number of iterations as (b - (a - s)) / s. */
2340 step
= simplify_gen_unary (NEG
, mode
, iv1
.step
, mode
);
2341 tmp0
= lowpart_subreg (mode
, iv0
.base
, comp_mode
);
2342 tmp1
= lowpart_subreg (mode
, iv1
.base
, comp_mode
);
2344 bound
= simplify_gen_binary (MINUS
, mode
, mode_mmin
,
2345 lowpart_subreg (mode
, step
, comp_mode
));
2346 assumption
= simplify_gen_relational (cond
, SImode
, mode
,
2349 alloc_EXPR_LIST (0, assumption
, desc
->assumptions
);
2351 tmp
= simplify_gen_binary (PLUS
, comp_mode
, iv0
.base
, iv1
.step
);
2352 tmp
= lowpart_subreg (mode
, tmp
, comp_mode
);
2353 assumption
= simplify_gen_relational (reverse_condition (cond
),
2356 delta
= simplify_gen_binary (MINUS
, mode
, tmp0
, step
);
2357 delta
= simplify_gen_binary (MINUS
, mode
, tmp1
, delta
);
2359 if (assumption
== const_true_rtx
)
2361 else if (assumption
!= const0_rtx
)
2362 desc
->noloop_assumptions
=
2363 alloc_EXPR_LIST (0, assumption
, desc
->noloop_assumptions
);
2364 delta
= simplify_gen_binary (UDIV
, mode
, delta
, step
);
2365 desc
->niter_expr
= delta
;
2368 old_niter
= desc
->niter_expr
;
2370 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2371 if (desc
->assumptions
2372 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2374 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2375 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2376 simplify_using_initial_values (loop
, NIL
, &desc
->niter_expr
);
2378 /* Rerun the simplification. Consider code (created by copying loop headers)
2390 The first pass determines that i = 0, the second pass uses it to eliminate
2391 noloop assumption. */
2393 simplify_using_initial_values (loop
, AND
, &desc
->assumptions
);
2394 if (desc
->assumptions
2395 && XEXP (desc
->assumptions
, 0) == const0_rtx
)
2397 simplify_using_initial_values (loop
, IOR
, &desc
->noloop_assumptions
);
2398 simplify_using_initial_values (loop
, IOR
, &desc
->infinite
);
2399 simplify_using_initial_values (loop
, NIL
, &desc
->niter_expr
);
2401 if (desc
->noloop_assumptions
2402 && XEXP (desc
->noloop_assumptions
, 0) == const_true_rtx
)
2405 if (GET_CODE (desc
->niter_expr
) == CONST_INT
)
2407 unsigned HOST_WIDEST_INT val
= INTVAL (desc
->niter_expr
);
2409 desc
->const_iter
= true;
2410 desc
->niter_max
= desc
->niter
= val
& GET_MODE_MASK (desc
->mode
);
2414 if (!desc
->niter_max
)
2415 desc
->niter_max
= determine_max_iter (desc
);
2417 /* simplify_using_initial_values does a copy propagation on the registers
2418 in the expression for the number of iterations. This prolongs life
2419 ranges of registers and increases register pressure, and usually
2420 brings no gain (and if it happens to do, the cse pass will take care
2421 of it anyway). So prevent this behavior, unless it enabled us to
2422 derive that the number of iterations is a constant. */
2423 desc
->niter_expr
= old_niter
;
2429 desc
->simple_p
= false;
2433 desc
->const_iter
= true;
2435 desc
->niter_max
= 0;
2436 desc
->niter_expr
= const0_rtx
;
2440 /* Checks whether E is a simple exit from LOOP and stores its description
2444 check_simple_exit (struct loop
*loop
, edge e
, struct niter_desc
*desc
)
2446 basic_block exit_bb
;
2451 desc
->simple_p
= false;
2453 /* It must belong directly to the loop. */
2454 if (exit_bb
->loop_father
!= loop
)
2457 /* It must be tested (at least) once during any iteration. */
2458 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit_bb
))
2461 /* It must end in a simple conditional jump. */
2462 if (!any_condjump_p (BB_END (exit_bb
)))
2472 /* Test whether the condition is suitable. */
2473 if (!(condition
= get_condition (BB_END (ei
->src
), &at
, false, false)))
2476 if (ei
->flags
& EDGE_FALLTHRU
)
2478 condition
= reversed_condition (condition
);
2483 /* Check that we are able to determine number of iterations and fill
2484 in information about it. */
2485 iv_number_of_iterations (loop
, at
, condition
, desc
);
2488 /* Finds a simple exit of LOOP and stores its description into DESC. */
2491 find_simple_exit (struct loop
*loop
, struct niter_desc
*desc
)
2496 struct niter_desc act
;
2499 desc
->simple_p
= false;
2500 body
= get_loop_body (loop
);
2502 for (i
= 0; i
< loop
->num_nodes
; i
++)
2504 for (e
= body
[i
]->succ
; e
; e
= e
->succ_next
)
2506 if (flow_bb_inside_loop_p (loop
, e
->dest
))
2509 check_simple_exit (loop
, e
, &act
);
2513 /* Prefer constant iterations; the less the better. */
2516 else if (!act
.const_iter
2517 || (desc
->const_iter
&& act
.niter
>= desc
->niter
))
2527 fprintf (dump_file
, "Loop %d is simple:\n", loop
->num
);
2528 fprintf (dump_file
, " simple exit %d -> %d\n",
2529 desc
->out_edge
->src
->index
,
2530 desc
->out_edge
->dest
->index
);
2531 if (desc
->assumptions
)
2533 fprintf (dump_file
, " assumptions: ");
2534 print_rtl (dump_file
, desc
->assumptions
);
2535 fprintf (dump_file
, "\n");
2537 if (desc
->noloop_assumptions
)
2539 fprintf (dump_file
, " does not roll if: ");
2540 print_rtl (dump_file
, desc
->noloop_assumptions
);
2541 fprintf (dump_file
, "\n");
2545 fprintf (dump_file
, " infinite if: ");
2546 print_rtl (dump_file
, desc
->infinite
);
2547 fprintf (dump_file
, "\n");
2550 fprintf (dump_file
, " number of iterations: ");
2551 print_rtl (dump_file
, desc
->niter_expr
);
2552 fprintf (dump_file
, "\n");
2554 fprintf (dump_file
, " upper bound: ");
2555 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter_max
);
2556 fprintf (dump_file
, "\n");
2559 fprintf (dump_file
, "Loop %d is not simple.\n", loop
->num
);
2565 /* Creates a simple loop description of LOOP if it was not computed
2569 get_simple_loop_desc (struct loop
*loop
)
2571 struct niter_desc
*desc
= simple_loop_desc (loop
);
2576 desc
= xmalloc (sizeof (struct niter_desc
));
2577 iv_analysis_loop_init (loop
);
2578 find_simple_exit (loop
, desc
);
2584 /* Releases simple loop description for LOOP. */
2587 free_simple_loop_desc (struct loop
*loop
)
2589 struct niter_desc
*desc
= simple_loop_desc (loop
);