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, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This is a simple analysis of induction variables of the loop. The major use
22 is for determining the number of iterations of a loop for loop unrolling,
23 doloop optimization and branch prediction. The iv information is computed
26 Induction variable is analyzed by walking the use-def chains. When a biv
27 is found, it is cached in the bivs hash table. When register is proved
28 to be a giv, its description is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
48 iv_current_loop_df (): Returns the dataflow object for the current loop used
53 #include "coretypes.h"
56 #include "hard-reg-set.h"
58 #include "basic-block.h"
67 /* Possible return values of iv_get_reaching_def. */
71 /* More than one reaching def, or reaching def that does not
75 /* The use is trivial invariant of the loop, i.e. is not changed
79 /* The use is reached by initial value and a value from the
80 previous iteration. */
83 /* The use has single dominating def. */
87 /* Information about a biv. */
91 unsigned regno; /* The register of the biv. */
92 struct rtx_iv iv; /* Value of the biv. */
95 /* Induction variable stored at the reference. */
96 #define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF))
97 #define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV)
99 /* The current loop. */
101 static struct loop *current_loop;
103 /* Dataflow information for the current loop. */
105 static struct df *df = NULL;
107 /* Bivs of the current loop. */
111 /* Return the dataflow object for the current loop. */
113 iv_current_loop_df (void)
118 static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
120 /* Dumps information about IV to FILE. */
122 extern void dump_iv_info (FILE *, struct rtx_iv *);
124 dump_iv_info (FILE *file, struct rtx_iv *iv)
128 fprintf (file, "not simple");
132 if (iv->step == const0_rtx
133 && !iv->first_special)
134 fprintf (file, "invariant ");
136 print_rtl (file, iv->base);
137 if (iv->step != const0_rtx)
139 fprintf (file, " + ");
140 print_rtl (file, iv->step);
141 fprintf (file, " * iteration");
143 fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
145 if (iv->mode != iv->extend_mode)
146 fprintf (file, " %s to %s",
147 rtx_name[iv->extend],
148 GET_MODE_NAME (iv->extend_mode));
150 if (iv->mult != const1_rtx)
152 fprintf (file, " * ");
153 print_rtl (file, iv->mult);
155 if (iv->delta != const0_rtx)
157 fprintf (file, " + ");
158 print_rtl (file, iv->delta);
160 if (iv->first_special)
161 fprintf (file, " (first special)");
164 /* Generates a subreg to get the least significant part of EXPR (in mode
165 INNER_MODE) to OUTER_MODE. */
168 lowpart_subreg (enum machine_mode outer_mode, rtx expr,
169 enum machine_mode inner_mode)
171 return simplify_gen_subreg (outer_mode, expr, inner_mode,
172 subreg_lowpart_offset (outer_mode, inner_mode));
175 /* Checks whether REG is a well-behaved register. */
178 simple_reg_p (rtx reg)
182 if (GET_CODE (reg) == SUBREG)
184 if (!subreg_lowpart_p (reg))
186 reg = SUBREG_REG (reg);
193 if (HARD_REGISTER_NUM_P (r))
196 if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
202 /* Clears the information about ivs stored in df. */
207 unsigned i, n_defs = DF_DEFS_SIZE (df);
211 for (i = 0; i < n_defs; i++)
213 def = DF_DEFS_GET (df, i);
214 iv = DF_REF_IV (def);
218 DF_REF_IV_SET (def, NULL);
224 /* Returns hash value for biv B. */
227 biv_hash (const void *b)
229 return ((const struct biv_entry *) b)->regno;
232 /* Compares biv B and register R. */
235 biv_eq (const void *b, const void *r)
237 return ((const struct biv_entry *) b)->regno == REGNO ((rtx) r);
240 /* Prepare the data for an induction variable analysis of a LOOP. */
243 iv_analysis_loop_init (struct loop *loop)
245 basic_block *body = get_loop_body_in_dom_order (loop), bb;
246 bitmap blocks = BITMAP_ALLOC (NULL);
248 bool first_time = (df == NULL);
252 /* Clear the information from the analysis of the previous loop. */
255 df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
256 df_chain_add_problem (df, DF_UD_CHAIN);
257 bivs = htab_create (10, biv_hash, biv_eq, free);
262 for (i = 0; i < loop->num_nodes; i++)
265 bitmap_set_bit (blocks, bb->index);
267 df_set_blocks (df, blocks);
269 BITMAP_FREE (blocks);
273 /* Finds the definition of REG that dominates loop latch and stores
274 it to DEF. Returns false if there is not a single definition
275 dominating the latch. If REG has no definition in loop, DEF
276 is set to NULL and true is returned. */
279 latch_dominating_def (rtx reg, struct df_ref **def)
281 struct df_ref *single_rd = NULL, *adef;
282 unsigned regno = REGNO (reg);
283 struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
284 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, current_loop->latch);
286 for (adef = reg_info->reg_chain; adef; adef = adef->next_reg)
288 if (!bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
291 /* More than one reaching definition. */
295 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
305 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
307 static enum iv_grd_result
308 iv_get_reaching_def (rtx insn, rtx reg, struct df_ref **def)
310 struct df_ref *use, *adef;
311 basic_block def_bb, use_bb;
316 if (!simple_reg_p (reg))
318 if (GET_CODE (reg) == SUBREG)
319 reg = SUBREG_REG (reg);
320 gcc_assert (REG_P (reg));
322 use = df_find_use (df, insn, reg);
323 gcc_assert (use != NULL);
325 if (!DF_REF_CHAIN (use))
326 return GRD_INVARIANT;
328 /* More than one reaching def. */
329 if (DF_REF_CHAIN (use)->next)
332 adef = DF_REF_CHAIN (use)->ref;
333 def_insn = DF_REF_INSN (adef);
334 def_bb = DF_REF_BB (adef);
335 use_bb = BLOCK_FOR_INSN (insn);
337 if (use_bb == def_bb)
338 dom_p = (DF_INSN_LUID (df, def_insn) < DF_INSN_LUID (df, insn));
340 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
345 return GRD_SINGLE_DOM;
348 /* The definition does not dominate the use. This is still OK if
349 this may be a use of a biv, i.e. if the def_bb dominates loop
351 if (just_once_each_iteration_p (current_loop, def_bb))
352 return GRD_MAYBE_BIV;
357 /* Sets IV to invariant CST in MODE. Always returns true (just for
358 consistency with other iv manipulation functions that may fail). */
361 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
363 if (mode == VOIDmode)
364 mode = GET_MODE (cst);
368 iv->step = const0_rtx;
369 iv->first_special = false;
370 iv->extend = UNKNOWN;
371 iv->extend_mode = iv->mode;
372 iv->delta = const0_rtx;
373 iv->mult = const1_rtx;
378 /* Evaluates application of subreg to MODE on IV. */
381 iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
383 /* If iv is invariant, just calculate the new value. */
384 if (iv->step == const0_rtx
385 && !iv->first_special)
387 rtx val = get_iv_value (iv, const0_rtx);
388 val = lowpart_subreg (mode, val, iv->extend_mode);
391 iv->extend = UNKNOWN;
392 iv->mode = iv->extend_mode = mode;
393 iv->delta = const0_rtx;
394 iv->mult = const1_rtx;
398 if (iv->extend_mode == mode)
401 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
404 iv->extend = UNKNOWN;
407 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
408 simplify_gen_binary (MULT, iv->extend_mode,
409 iv->base, iv->mult));
410 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
411 iv->mult = const1_rtx;
412 iv->delta = const0_rtx;
413 iv->first_special = false;
418 /* Evaluates application of EXTEND to MODE on IV. */
421 iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
423 /* If iv is invariant, just calculate the new value. */
424 if (iv->step == const0_rtx
425 && !iv->first_special)
427 rtx val = get_iv_value (iv, const0_rtx);
428 val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
431 iv->extend = UNKNOWN;
432 iv->mode = iv->extend_mode = mode;
433 iv->delta = const0_rtx;
434 iv->mult = const1_rtx;
438 if (mode != iv->extend_mode)
441 if (iv->extend != UNKNOWN
442 && iv->extend != extend)
450 /* Evaluates negation of IV. */
453 iv_neg (struct rtx_iv *iv)
455 if (iv->extend == UNKNOWN)
457 iv->base = simplify_gen_unary (NEG, iv->extend_mode,
458 iv->base, iv->extend_mode);
459 iv->step = simplify_gen_unary (NEG, iv->extend_mode,
460 iv->step, iv->extend_mode);
464 iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
465 iv->delta, iv->extend_mode);
466 iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
467 iv->mult, iv->extend_mode);
473 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
476 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
478 enum machine_mode mode;
481 /* Extend the constant to extend_mode of the other operand if necessary. */
482 if (iv0->extend == UNKNOWN
483 && iv0->mode == iv0->extend_mode
484 && iv0->step == const0_rtx
485 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
487 iv0->extend_mode = iv1->extend_mode;
488 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
489 iv0->base, iv0->mode);
491 if (iv1->extend == UNKNOWN
492 && iv1->mode == iv1->extend_mode
493 && iv1->step == const0_rtx
494 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
496 iv1->extend_mode = iv0->extend_mode;
497 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
498 iv1->base, iv1->mode);
501 mode = iv0->extend_mode;
502 if (mode != iv1->extend_mode)
505 if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
507 if (iv0->mode != iv1->mode)
510 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
511 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
516 /* Handle addition of constant. */
517 if (iv1->extend == UNKNOWN
519 && iv1->step == const0_rtx)
521 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
525 if (iv0->extend == UNKNOWN
527 && iv0->step == const0_rtx)
535 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
542 /* Evaluates multiplication of IV by constant CST. */
545 iv_mult (struct rtx_iv *iv, rtx mby)
547 enum machine_mode mode = iv->extend_mode;
549 if (GET_MODE (mby) != VOIDmode
550 && GET_MODE (mby) != mode)
553 if (iv->extend == UNKNOWN)
555 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
556 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
560 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
561 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
567 /* Evaluates shift of IV by constant CST. */
570 iv_shift (struct rtx_iv *iv, rtx mby)
572 enum machine_mode mode = iv->extend_mode;
574 if (GET_MODE (mby) != VOIDmode
575 && GET_MODE (mby) != mode)
578 if (iv->extend == UNKNOWN)
580 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
581 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
585 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
586 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
592 /* The recursive part of get_biv_step. Gets the value of the single value
593 defined by DEF wrto initial value of REG inside loop, in shape described
597 get_biv_step_1 (struct df_ref *def, rtx reg,
598 rtx *inner_step, enum machine_mode *inner_mode,
599 enum rtx_code *extend, enum machine_mode outer_mode,
602 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
603 rtx next, nextr, tmp;
605 rtx insn = DF_REF_INSN (def);
606 struct df_ref *next_def;
607 enum iv_grd_result res;
609 set = single_set (insn);
613 rhs = find_reg_equal_equiv_note (insn);
619 code = GET_CODE (rhs);
632 if (code == PLUS && CONSTANT_P (op0))
634 tmp = op0; op0 = op1; op1 = tmp;
637 if (!simple_reg_p (op0)
638 || !CONSTANT_P (op1))
641 if (GET_MODE (rhs) != outer_mode)
643 /* ppc64 uses expressions like
645 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
647 this is equivalent to
649 (set x':DI (plus:DI y:DI 1))
650 (set x:SI (subreg:SI (x':DI)). */
651 if (GET_CODE (op0) != SUBREG)
653 if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
662 if (GET_MODE (rhs) != outer_mode)
666 if (!simple_reg_p (op0))
676 if (GET_CODE (next) == SUBREG)
678 if (!subreg_lowpart_p (next))
681 nextr = SUBREG_REG (next);
682 if (GET_MODE (nextr) != outer_mode)
688 res = iv_get_reaching_def (insn, nextr, &next_def);
690 if (res == GRD_INVALID || res == GRD_INVARIANT)
693 if (res == GRD_MAYBE_BIV)
695 if (!rtx_equal_p (nextr, reg))
698 *inner_step = const0_rtx;
700 *inner_mode = outer_mode;
701 *outer_step = const0_rtx;
703 else if (!get_biv_step_1 (next_def, reg,
704 inner_step, inner_mode, extend, outer_mode,
708 if (GET_CODE (next) == SUBREG)
710 enum machine_mode amode = GET_MODE (next);
712 if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
716 *inner_step = simplify_gen_binary (PLUS, outer_mode,
717 *inner_step, *outer_step);
718 *outer_step = const0_rtx;
730 if (*inner_mode == outer_mode
731 /* See comment in previous switch. */
732 || GET_MODE (rhs) != outer_mode)
733 *inner_step = simplify_gen_binary (code, outer_mode,
736 *outer_step = simplify_gen_binary (code, outer_mode,
742 gcc_assert (GET_MODE (op0) == *inner_mode
743 && *extend == UNKNOWN
744 && *outer_step == const0_rtx);
756 /* Gets the operation on register REG inside loop, in shape
758 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
760 If the operation cannot be described in this shape, return false.
761 LAST_DEF is the definition of REG that dominates loop latch. */
764 get_biv_step (struct df_ref *last_def, rtx reg, rtx *inner_step,
765 enum machine_mode *inner_mode, enum rtx_code *extend,
766 enum machine_mode *outer_mode, rtx *outer_step)
768 *outer_mode = GET_MODE (reg);
770 if (!get_biv_step_1 (last_def, reg,
771 inner_step, inner_mode, extend, *outer_mode,
775 gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
776 gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
781 /* Records information that DEF is induction variable IV. */
784 record_iv (struct df_ref *def, struct rtx_iv *iv)
786 struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
789 DF_REF_IV_SET (def, recorded_iv);
792 /* If DEF was already analyzed for bivness, store the description of the biv to
793 IV and return true. Otherwise return false. */
796 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
798 struct biv_entry *biv = htab_find_with_hash (bivs, def, REGNO (def));
808 record_biv (rtx def, struct rtx_iv *iv)
810 struct biv_entry *biv = XNEW (struct biv_entry);
811 void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
813 biv->regno = REGNO (def);
819 /* Determines whether DEF is a biv and if so, stores its description
823 iv_analyze_biv (rtx def, struct rtx_iv *iv)
825 rtx inner_step, outer_step;
826 enum machine_mode inner_mode, outer_mode;
827 enum rtx_code extend;
828 struct df_ref *last_def;
832 fprintf (dump_file, "Analyzing ");
833 print_rtl (dump_file, def);
834 fprintf (dump_file, " for bivness.\n");
839 if (!CONSTANT_P (def))
842 return iv_constant (iv, def, VOIDmode);
845 if (!latch_dominating_def (def, &last_def))
848 fprintf (dump_file, " not simple.\n");
853 return iv_constant (iv, def, VOIDmode);
855 if (analyzed_for_bivness_p (def, iv))
858 fprintf (dump_file, " already analysed.\n");
859 return iv->base != NULL_RTX;
862 if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
863 &outer_mode, &outer_step))
869 /* Loop transforms base to es (base + inner_step) + outer_step,
870 where es means extend of subreg between inner_mode and outer_mode.
871 The corresponding induction variable is
873 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
875 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
876 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
877 iv->mode = inner_mode;
878 iv->extend_mode = outer_mode;
880 iv->mult = const1_rtx;
881 iv->delta = outer_step;
882 iv->first_special = inner_mode != outer_mode;
887 fprintf (dump_file, " ");
888 dump_iv_info (dump_file, iv);
889 fprintf (dump_file, "\n");
892 record_biv (def, iv);
893 return iv->base != NULL_RTX;
896 /* Analyzes expression RHS used at INSN and stores the result to *IV.
897 The mode of the induction variable is MODE. */
900 iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
902 rtx mby = NULL_RTX, tmp;
903 rtx op0 = NULL_RTX, op1 = NULL_RTX;
904 struct rtx_iv iv0, iv1;
905 enum rtx_code code = GET_CODE (rhs);
906 enum machine_mode omode = mode;
912 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
918 if (!iv_analyze_op (insn, rhs, iv))
921 if (iv->mode == VOIDmode)
924 iv->extend_mode = mode;
940 omode = GET_MODE (op0);
952 if (!CONSTANT_P (mby))
958 if (!CONSTANT_P (mby))
965 if (!CONSTANT_P (mby))
974 && !iv_analyze_expr (insn, op0, omode, &iv0))
978 && !iv_analyze_expr (insn, op1, omode, &iv1))
985 if (!iv_extend (&iv0, code, mode))
996 if (!iv_add (&iv0, &iv1, code))
1001 if (!iv_mult (&iv0, mby))
1006 if (!iv_shift (&iv0, mby))
1015 return iv->base != NULL_RTX;
1018 /* Analyzes iv DEF and stores the result to *IV. */
1021 iv_analyze_def (struct df_ref *def, struct rtx_iv *iv)
1023 rtx insn = DF_REF_INSN (def);
1024 rtx reg = DF_REF_REG (def);
1029 fprintf (dump_file, "Analysing def of ");
1030 print_rtl (dump_file, reg);
1031 fprintf (dump_file, " in insn ");
1032 print_rtl_single (dump_file, insn);
1035 if (DF_REF_IV (def))
1038 fprintf (dump_file, " already analysed.\n");
1039 *iv = *DF_REF_IV (def);
1040 return iv->base != NULL_RTX;
1043 iv->mode = VOIDmode;
1044 iv->base = NULL_RTX;
1045 iv->step = NULL_RTX;
1047 set = single_set (insn);
1048 if (!set || SET_DEST (set) != reg)
1051 rhs = find_reg_equal_equiv_note (insn);
1053 rhs = XEXP (rhs, 0);
1055 rhs = SET_SRC (set);
1057 iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1058 record_iv (def, iv);
1062 print_rtl (dump_file, reg);
1063 fprintf (dump_file, " in insn ");
1064 print_rtl_single (dump_file, insn);
1065 fprintf (dump_file, " is ");
1066 dump_iv_info (dump_file, iv);
1067 fprintf (dump_file, "\n");
1070 return iv->base != NULL_RTX;
1073 /* Analyzes operand OP of INSN and stores the result to *IV. */
1076 iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
1078 struct df_ref *def = NULL;
1079 enum iv_grd_result res;
1083 fprintf (dump_file, "Analysing operand ");
1084 print_rtl (dump_file, op);
1085 fprintf (dump_file, " of insn ");
1086 print_rtl_single (dump_file, insn);
1089 if (CONSTANT_P (op))
1090 res = GRD_INVARIANT;
1091 else if (GET_CODE (op) == SUBREG)
1093 if (!subreg_lowpart_p (op))
1096 if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1099 return iv_subreg (iv, GET_MODE (op));
1103 res = iv_get_reaching_def (insn, op, &def);
1104 if (res == GRD_INVALID)
1107 fprintf (dump_file, " not simple.\n");
1112 if (res == GRD_INVARIANT)
1114 iv_constant (iv, op, VOIDmode);
1118 fprintf (dump_file, " ");
1119 dump_iv_info (dump_file, iv);
1120 fprintf (dump_file, "\n");
1125 if (res == GRD_MAYBE_BIV)
1126 return iv_analyze_biv (op, iv);
1128 return iv_analyze_def (def, iv);
1131 /* Analyzes value VAL at INSN and stores the result to *IV. */
1134 iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
1138 /* We must find the insn in that val is used, so that we get to UD chains.
1139 Since the function is sometimes called on result of get_condition,
1140 this does not necessarily have to be directly INSN; scan also the
1142 if (simple_reg_p (val))
1144 if (GET_CODE (val) == SUBREG)
1145 reg = SUBREG_REG (val);
1149 while (!df_find_use (df, insn, reg))
1150 insn = NEXT_INSN (insn);
1153 return iv_analyze_op (insn, val, iv);
1156 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1159 iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
1161 struct df_ref *adef;
1163 adef = df_find_def (df, insn, def);
1167 return iv_analyze_def (adef, iv);
1170 /* Checks whether definition of register REG in INSN is a basic induction
1171 variable. IV analysis must have been initialized (via a call to
1172 iv_analysis_loop_init) for this function to produce a result. */
1175 biv_p (rtx insn, rtx reg)
1178 struct df_ref *def, *last_def;
1180 if (!simple_reg_p (reg))
1183 def = df_find_def (df, insn, reg);
1184 gcc_assert (def != NULL);
1185 if (!latch_dominating_def (reg, &last_def))
1187 if (last_def != def)
1190 if (!iv_analyze_biv (reg, &iv))
1193 return iv.step != const0_rtx;
1196 /* Calculates value of IV at ITERATION-th iteration. */
1199 get_iv_value (struct rtx_iv *iv, rtx iteration)
1203 /* We would need to generate some if_then_else patterns, and so far
1204 it is not needed anywhere. */
1205 gcc_assert (!iv->first_special);
1207 if (iv->step != const0_rtx && iteration != const0_rtx)
1208 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1209 simplify_gen_binary (MULT, iv->extend_mode,
1210 iv->step, iteration));
1214 if (iv->extend_mode == iv->mode)
1217 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1219 if (iv->extend == UNKNOWN)
1222 val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
1223 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1224 simplify_gen_binary (MULT, iv->extend_mode,
1230 /* Free the data for an induction variable analysis. */
1233 iv_analysis_done (void)
1245 /* Computes inverse to X modulo (1 << MOD). */
1247 static unsigned HOST_WIDEST_INT
1248 inverse (unsigned HOST_WIDEST_INT x, int mod)
1250 unsigned HOST_WIDEST_INT mask =
1251 ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
1252 unsigned HOST_WIDEST_INT rslt = 1;
1255 for (i = 0; i < mod - 1; i++)
1257 rslt = (rslt * x) & mask;
1264 /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
1267 altered_reg_used (rtx *reg, void *alt)
1272 return REGNO_REG_SET_P (alt, REGNO (*reg));
1275 /* Marks registers altered by EXPR in set ALT. */
1278 mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
1280 if (GET_CODE (expr) == SUBREG)
1281 expr = SUBREG_REG (expr);
1285 SET_REGNO_REG_SET (alt, REGNO (expr));
1288 /* Checks whether RHS is simple enough to process. */
1291 simple_rhs_p (rtx rhs)
1295 if (CONSTANT_P (rhs)
1299 switch (GET_CODE (rhs))
1303 op0 = XEXP (rhs, 0);
1304 op1 = XEXP (rhs, 1);
1305 /* Allow reg + const sets only. */
1306 if (REG_P (op0) && CONSTANT_P (op1))
1308 if (REG_P (op1) && CONSTANT_P (op0))
1318 /* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
1322 simplify_using_assignment (rtx insn, rtx *expr, regset altered)
1324 rtx set = single_set (insn);
1325 rtx lhs = NULL_RTX, rhs;
1330 lhs = SET_DEST (set);
1332 || altered_reg_used (&lhs, altered))
1338 note_stores (PATTERN (insn), mark_altered, altered);
1343 /* Kill all call clobbered registers. */
1344 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1345 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1346 SET_REGNO_REG_SET (altered, i);
1352 rhs = find_reg_equal_equiv_note (insn);
1354 rhs = XEXP (rhs, 0);
1356 rhs = SET_SRC (set);
1358 if (!simple_rhs_p (rhs))
1361 if (for_each_rtx (&rhs, altered_reg_used, altered))
1364 *expr = simplify_replace_rtx (*expr, lhs, rhs);
1367 /* Checks whether A implies B. */
1370 implies_p (rtx a, rtx b)
1372 rtx op0, op1, opb0, opb1, r;
1373 enum machine_mode mode;
1375 if (GET_CODE (a) == EQ)
1382 r = simplify_replace_rtx (b, op0, op1);
1383 if (r == const_true_rtx)
1389 r = simplify_replace_rtx (b, op1, op0);
1390 if (r == const_true_rtx)
1395 /* A < B implies A + 1 <= B. */
1396 if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1397 && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1404 if (GET_CODE (a) == GT)
1411 if (GET_CODE (b) == GE)
1418 mode = GET_MODE (op0);
1419 if (mode != GET_MODE (opb0))
1421 else if (mode == VOIDmode)
1423 mode = GET_MODE (op1);
1424 if (mode != GET_MODE (opb1))
1428 if (SCALAR_INT_MODE_P (mode)
1429 && rtx_equal_p (op1, opb1)
1430 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1437 /* Canonicalizes COND so that
1439 (1) Ensure that operands are ordered according to
1440 swap_commutative_operands_p.
1441 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1442 for GE, GEU, and LEU. */
1445 canon_condition (rtx cond)
1450 enum machine_mode mode;
1452 code = GET_CODE (cond);
1453 op0 = XEXP (cond, 0);
1454 op1 = XEXP (cond, 1);
1456 if (swap_commutative_operands_p (op0, op1))
1458 code = swap_condition (code);
1464 mode = GET_MODE (op0);
1465 if (mode == VOIDmode)
1466 mode = GET_MODE (op1);
1467 gcc_assert (mode != VOIDmode);
1469 if (GET_CODE (op1) == CONST_INT
1470 && GET_MODE_CLASS (mode) != MODE_CC
1471 && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1473 HOST_WIDE_INT const_val = INTVAL (op1);
1474 unsigned HOST_WIDE_INT uconst_val = const_val;
1475 unsigned HOST_WIDE_INT max_val
1476 = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1481 if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1482 code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1485 /* When cross-compiling, const_val might be sign-extended from
1486 BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1488 if ((HOST_WIDE_INT) (const_val & max_val)
1489 != (((HOST_WIDE_INT) 1
1490 << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1491 code = GT, op1 = gen_int_mode (const_val - 1, mode);
1495 if (uconst_val < max_val)
1496 code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1500 if (uconst_val != 0)
1501 code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1509 if (op0 != XEXP (cond, 0)
1510 || op1 != XEXP (cond, 1)
1511 || code != GET_CODE (cond)
1512 || GET_MODE (cond) != SImode)
1513 cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1518 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1519 set of altered regs. */
1522 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1524 rtx rev, reve, exp = *expr;
1526 if (!COMPARISON_P (exp))
1529 /* If some register gets altered later, we do not really speak about its
1530 value at the time of comparison. */
1532 && for_each_rtx (&cond, altered_reg_used, altered))
1535 rev = reversed_condition (cond);
1536 reve = reversed_condition (exp);
1538 cond = canon_condition (cond);
1539 exp = canon_condition (exp);
1541 rev = canon_condition (rev);
1543 reve = canon_condition (reve);
1545 if (rtx_equal_p (exp, cond))
1547 *expr = const_true_rtx;
1552 if (rev && rtx_equal_p (exp, rev))
1558 if (implies_p (cond, exp))
1560 *expr = const_true_rtx;
1564 if (reve && implies_p (cond, reve))
1570 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1572 if (rev && implies_p (exp, rev))
1578 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1579 if (rev && reve && implies_p (reve, rev))
1581 *expr = const_true_rtx;
1585 /* We would like to have some other tests here. TODO. */
1590 /* Use relationship between A and *B to eventually eliminate *B.
1591 OP is the operation we consider. */
1594 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1599 /* If A implies *B, we may replace *B by true. */
1600 if (implies_p (a, *b))
1601 *b = const_true_rtx;
1605 /* If *B implies A, we may replace *B by false. */
1606 if (implies_p (*b, a))
1615 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1616 operation we consider. */
1619 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1623 for (elt = tail; elt; elt = XEXP (elt, 1))
1624 eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1625 for (elt = tail; elt; elt = XEXP (elt, 1))
1626 eliminate_implied_condition (op, XEXP (elt, 0), head);
1629 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1630 is a list, its elements are assumed to be combined using OP. */
1633 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1635 rtx head, tail, insn;
1643 if (CONSTANT_P (*expr))
1646 if (GET_CODE (*expr) == EXPR_LIST)
1648 head = XEXP (*expr, 0);
1649 tail = XEXP (*expr, 1);
1651 eliminate_implied_conditions (op, &head, tail);
1656 neutral = const_true_rtx;
1661 neutral = const0_rtx;
1662 aggr = const_true_rtx;
1669 simplify_using_initial_values (loop, UNKNOWN, &head);
1672 XEXP (*expr, 0) = aggr;
1673 XEXP (*expr, 1) = NULL_RTX;
1676 else if (head == neutral)
1679 simplify_using_initial_values (loop, op, expr);
1682 simplify_using_initial_values (loop, op, &tail);
1684 if (tail && XEXP (tail, 0) == aggr)
1690 XEXP (*expr, 0) = head;
1691 XEXP (*expr, 1) = tail;
1695 gcc_assert (op == UNKNOWN);
1697 e = loop_preheader_edge (loop);
1698 if (e->src == ENTRY_BLOCK_PTR)
1701 altered = ALLOC_REG_SET (®_obstack);
1705 insn = BB_END (e->src);
1706 if (any_condjump_p (insn))
1708 rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1710 if (cond && (e->flags & EDGE_FALLTHRU))
1711 cond = reversed_condition (cond);
1714 simplify_using_condition (cond, expr, altered);
1715 if (CONSTANT_P (*expr))
1717 FREE_REG_SET (altered);
1723 FOR_BB_INSNS_REVERSE (e->src, insn)
1728 simplify_using_assignment (insn, expr, altered);
1729 if (CONSTANT_P (*expr))
1731 FREE_REG_SET (altered);
1736 if (!single_pred_p (e->src)
1737 || single_pred (e->src) == ENTRY_BLOCK_PTR)
1739 e = single_pred_edge (e->src);
1742 FREE_REG_SET (altered);
1745 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
1746 that IV occurs as left operands of comparison COND and its signedness
1747 is SIGNED_P to DESC. */
1750 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1751 enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1753 rtx mmin, mmax, cond_over, cond_under;
1755 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1756 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1758 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1767 if (cond_under != const0_rtx)
1769 alloc_EXPR_LIST (0, cond_under, desc->infinite);
1770 if (cond_over != const0_rtx)
1771 desc->noloop_assumptions =
1772 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1779 if (cond_over != const0_rtx)
1781 alloc_EXPR_LIST (0, cond_over, desc->infinite);
1782 if (cond_under != const0_rtx)
1783 desc->noloop_assumptions =
1784 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1788 if (cond_over != const0_rtx)
1790 alloc_EXPR_LIST (0, cond_over, desc->infinite);
1791 if (cond_under != const0_rtx)
1793 alloc_EXPR_LIST (0, cond_under, desc->infinite);
1801 iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1804 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1805 subregs of the same mode if possible (sometimes it is necessary to add
1806 some assumptions to DESC). */
1809 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1810 enum rtx_code cond, struct niter_desc *desc)
1812 enum machine_mode comp_mode;
1815 /* If the ivs behave specially in the first iteration, or are
1816 added/multiplied after extending, we ignore them. */
1817 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1819 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1822 /* If there is some extend, it must match signedness of the comparison. */
1827 if (iv0->extend == ZERO_EXTEND
1828 || iv1->extend == ZERO_EXTEND)
1835 if (iv0->extend == SIGN_EXTEND
1836 || iv1->extend == SIGN_EXTEND)
1842 if (iv0->extend != UNKNOWN
1843 && iv1->extend != UNKNOWN
1844 && iv0->extend != iv1->extend)
1848 if (iv0->extend != UNKNOWN)
1849 signed_p = iv0->extend == SIGN_EXTEND;
1850 if (iv1->extend != UNKNOWN)
1851 signed_p = iv1->extend == SIGN_EXTEND;
1858 /* Values of both variables should be computed in the same mode. These
1859 might indeed be different, if we have comparison like
1861 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1863 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1864 in different modes. This does not seem impossible to handle, but
1865 it hardly ever occurs in practice.
1867 The only exception is the case when one of operands is invariant.
1868 For example pentium 3 generates comparisons like
1869 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
1870 definitely do not want this prevent the optimization. */
1871 comp_mode = iv0->extend_mode;
1872 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
1873 comp_mode = iv1->extend_mode;
1875 if (iv0->extend_mode != comp_mode)
1877 if (iv0->mode != iv0->extend_mode
1878 || iv0->step != const0_rtx)
1881 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1882 comp_mode, iv0->base, iv0->mode);
1883 iv0->extend_mode = comp_mode;
1886 if (iv1->extend_mode != comp_mode)
1888 if (iv1->mode != iv1->extend_mode
1889 || iv1->step != const0_rtx)
1892 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1893 comp_mode, iv1->base, iv1->mode);
1894 iv1->extend_mode = comp_mode;
1897 /* Check that both ivs belong to a range of a single mode. If one of the
1898 operands is an invariant, we may need to shorten it into the common
1900 if (iv0->mode == iv0->extend_mode
1901 && iv0->step == const0_rtx
1902 && iv0->mode != iv1->mode)
1903 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
1905 if (iv1->mode == iv1->extend_mode
1906 && iv1->step == const0_rtx
1907 && iv0->mode != iv1->mode)
1908 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
1910 if (iv0->mode != iv1->mode)
1913 desc->mode = iv0->mode;
1914 desc->signed_p = signed_p;
1919 /* Tries to estimate the maximum number of iterations. */
1921 static unsigned HOST_WIDEST_INT
1922 determine_max_iter (struct niter_desc *desc)
1924 rtx niter = desc->niter_expr;
1925 rtx mmin, mmax, left, right;
1926 unsigned HOST_WIDEST_INT nmax, inc;
1928 if (GET_CODE (niter) == AND
1929 && GET_CODE (XEXP (niter, 0)) == CONST_INT)
1931 nmax = INTVAL (XEXP (niter, 0));
1932 if (!(nmax & (nmax + 1)))
1934 desc->niter_max = nmax;
1939 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
1940 nmax = INTVAL (mmax) - INTVAL (mmin);
1942 if (GET_CODE (niter) == UDIV)
1944 if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
1946 desc->niter_max = nmax;
1949 inc = INTVAL (XEXP (niter, 1));
1950 niter = XEXP (niter, 0);
1955 if (GET_CODE (niter) == PLUS)
1957 left = XEXP (niter, 0);
1958 right = XEXP (niter, 0);
1960 if (GET_CODE (right) == CONST_INT)
1961 right = GEN_INT (-INTVAL (right));
1963 else if (GET_CODE (niter) == MINUS)
1965 left = XEXP (niter, 0);
1966 right = XEXP (niter, 0);
1974 if (GET_CODE (left) == CONST_INT)
1976 if (GET_CODE (right) == CONST_INT)
1978 nmax = INTVAL (mmax) - INTVAL (mmin);
1980 desc->niter_max = nmax / inc;
1984 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1985 the result into DESC. Very similar to determine_number_of_iterations
1986 (basically its rtl version), complicated by things like subregs. */
1989 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
1990 struct niter_desc *desc)
1992 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
1993 struct rtx_iv iv0, iv1, tmp_iv;
1994 rtx assumption, may_not_xform;
1996 enum machine_mode mode, comp_mode;
1997 rtx mmin, mmax, mode_mmin, mode_mmax;
1998 unsigned HOST_WIDEST_INT s, size, d, inv;
1999 HOST_WIDEST_INT up, down, inc, step_val;
2000 int was_sharp = false;
2004 /* The meaning of these assumptions is this:
2006 then the rest of information does not have to be valid
2007 if noloop_assumptions then the loop does not roll
2008 if infinite then this exit is never used */
2010 desc->assumptions = NULL_RTX;
2011 desc->noloop_assumptions = NULL_RTX;
2012 desc->infinite = NULL_RTX;
2013 desc->simple_p = true;
2015 desc->const_iter = false;
2016 desc->niter_expr = NULL_RTX;
2017 desc->niter_max = 0;
2019 cond = GET_CODE (condition);
2020 gcc_assert (COMPARISON_P (condition));
2022 mode = GET_MODE (XEXP (condition, 0));
2023 if (mode == VOIDmode)
2024 mode = GET_MODE (XEXP (condition, 1));
2025 /* The constant comparisons should be folded. */
2026 gcc_assert (mode != VOIDmode);
2028 /* We only handle integers or pointers. */
2029 if (GET_MODE_CLASS (mode) != MODE_INT
2030 && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2033 op0 = XEXP (condition, 0);
2034 if (!iv_analyze (insn, op0, &iv0))
2036 if (iv0.extend_mode == VOIDmode)
2037 iv0.mode = iv0.extend_mode = mode;
2039 op1 = XEXP (condition, 1);
2040 if (!iv_analyze (insn, op1, &iv1))
2042 if (iv1.extend_mode == VOIDmode)
2043 iv1.mode = iv1.extend_mode = mode;
2045 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2046 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2049 /* Check condition and normalize it. */
2057 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2058 cond = swap_condition (cond);
2070 /* Handle extends. This is relatively nontrivial, so we only try in some
2071 easy cases, when we can canonicalize the ivs (possibly by adding some
2072 assumptions) to shape subreg (base + i * step). This function also fills
2073 in desc->mode and desc->signed_p. */
2075 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2078 comp_mode = iv0.extend_mode;
2080 size = GET_MODE_BITSIZE (mode);
2081 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2082 mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2083 mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2085 if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2088 /* We can take care of the case of two induction variables chasing each other
2089 if the test is NE. I have never seen a loop using it, but still it is
2091 if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2096 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2097 iv1.step = const0_rtx;
2100 /* This is either infinite loop or the one that ends immediately, depending
2101 on initial values. Unswitching should remove this kind of conditions. */
2102 if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2107 if (iv0.step == const0_rtx)
2108 step_val = -INTVAL (iv1.step);
2110 step_val = INTVAL (iv0.step);
2112 /* Ignore loops of while (i-- < 10) type. */
2116 step_is_pow2 = !(step_val & (step_val - 1));
2120 /* We do not care about whether the step is power of two in this
2122 step_is_pow2 = false;
2126 /* Some more condition normalization. We must record some assumptions
2127 due to overflows. */
2132 /* We want to take care only of non-sharp relationals; this is easy,
2133 as in cases the overflow would make the transformation unsafe
2134 the loop does not roll. Seemingly it would make more sense to want
2135 to take care of sharp relationals instead, as NE is more similar to
2136 them, but the problem is that here the transformation would be more
2137 difficult due to possibly infinite loops. */
2138 if (iv0.step == const0_rtx)
2140 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2141 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2143 if (assumption == const_true_rtx)
2144 goto zero_iter_simplify;
2145 iv0.base = simplify_gen_binary (PLUS, comp_mode,
2146 iv0.base, const1_rtx);
2150 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2151 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2153 if (assumption == const_true_rtx)
2154 goto zero_iter_simplify;
2155 iv1.base = simplify_gen_binary (PLUS, comp_mode,
2156 iv1.base, constm1_rtx);
2159 if (assumption != const0_rtx)
2160 desc->noloop_assumptions =
2161 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2162 cond = (cond == LT) ? LE : LEU;
2164 /* It will be useful to be able to tell the difference once more in
2165 LE -> NE reduction. */
2171 /* Take care of trivially infinite loops. */
2174 if (iv0.step == const0_rtx)
2176 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2177 if (rtx_equal_p (tmp, mode_mmin))
2180 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2181 /* Fill in the remaining fields somehow. */
2182 goto zero_iter_simplify;
2187 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2188 if (rtx_equal_p (tmp, mode_mmax))
2191 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2192 /* Fill in the remaining fields somehow. */
2193 goto zero_iter_simplify;
2198 /* If we can we want to take care of NE conditions instead of size
2199 comparisons, as they are much more friendly (most importantly
2200 this takes care of special handling of loops with step 1). We can
2201 do it if we first check that upper bound is greater or equal to
2202 lower bound, their difference is constant c modulo step and that
2203 there is not an overflow. */
2206 if (iv0.step == const0_rtx)
2207 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2210 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2211 delta = lowpart_subreg (mode, delta, comp_mode);
2212 delta = simplify_gen_binary (UMOD, mode, delta, step);
2213 may_xform = const0_rtx;
2214 may_not_xform = const_true_rtx;
2216 if (GET_CODE (delta) == CONST_INT)
2218 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2220 /* A special case. We have transformed condition of type
2221 for (i = 0; i < 4; i += 4)
2223 for (i = 0; i <= 3; i += 4)
2224 obviously if the test for overflow during that transformation
2225 passed, we cannot overflow here. Most importantly any
2226 loop with sharp end condition and step 1 falls into this
2227 category, so handling this case specially is definitely
2228 worth the troubles. */
2229 may_xform = const_true_rtx;
2231 else if (iv0.step == const0_rtx)
2233 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2234 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2235 bound = lowpart_subreg (mode, bound, comp_mode);
2236 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2237 may_xform = simplify_gen_relational (cond, SImode, mode,
2239 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2245 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2246 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2247 bound = lowpart_subreg (mode, bound, comp_mode);
2248 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2249 may_xform = simplify_gen_relational (cond, SImode, mode,
2251 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2257 if (may_xform != const0_rtx)
2259 /* We perform the transformation always provided that it is not
2260 completely senseless. This is OK, as we would need this assumption
2261 to determine the number of iterations anyway. */
2262 if (may_xform != const_true_rtx)
2264 /* If the step is a power of two and the final value we have
2265 computed overflows, the cycle is infinite. Otherwise it
2266 is nontrivial to compute the number of iterations. */
2268 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2271 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2275 /* We are going to lose some information about upper bound on
2276 number of iterations in this step, so record the information
2278 inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2279 if (GET_CODE (iv1.base) == CONST_INT)
2280 up = INTVAL (iv1.base);
2282 up = INTVAL (mode_mmax) - inc;
2283 down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2286 desc->niter_max = (up - down) / inc + 1;
2288 if (iv0.step == const0_rtx)
2290 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2291 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2295 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2296 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2299 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2300 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2301 assumption = simplify_gen_relational (reverse_condition (cond),
2302 SImode, mode, tmp0, tmp1);
2303 if (assumption == const_true_rtx)
2304 goto zero_iter_simplify;
2305 else if (assumption != const0_rtx)
2306 desc->noloop_assumptions =
2307 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2312 /* Count the number of iterations. */
2315 /* Everything we do here is just arithmetics modulo size of mode. This
2316 makes us able to do more involved computations of number of iterations
2317 than in other cases. First transform the condition into shape
2318 s * i <> c, with s positive. */
2319 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2320 iv0.base = const0_rtx;
2321 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2322 iv1.step = const0_rtx;
2323 if (INTVAL (iv0.step) < 0)
2325 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2326 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2328 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2330 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2331 is infinite. Otherwise, the number of iterations is
2332 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2333 s = INTVAL (iv0.step); d = 1;
2340 bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2342 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2343 tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2344 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2345 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2347 tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2348 inv = inverse (s, size);
2349 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2350 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2354 if (iv1.step == const0_rtx)
2355 /* Condition in shape a + s * i <= b
2356 We must know that b + s does not overflow and a <= b + s and then we
2357 can compute number of iterations as (b + s - a) / s. (It might
2358 seem that we in fact could be more clever about testing the b + s
2359 overflow condition using some information about b - a mod s,
2360 but it was already taken into account during LE -> NE transform). */
2363 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2364 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2366 bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2367 lowpart_subreg (mode, step,
2373 /* If s is power of 2, we know that the loop is infinite if
2374 a % s <= b % s and b + s overflows. */
2375 assumption = simplify_gen_relational (reverse_condition (cond),
2379 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2380 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2381 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2382 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2384 alloc_EXPR_LIST (0, assumption, desc->infinite);
2388 assumption = simplify_gen_relational (cond, SImode, mode,
2391 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2394 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2395 tmp = lowpart_subreg (mode, tmp, comp_mode);
2396 assumption = simplify_gen_relational (reverse_condition (cond),
2397 SImode, mode, tmp0, tmp);
2399 delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2400 delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2404 /* Condition in shape a <= b - s * i
2405 We must know that a - s does not overflow and a - s <= b and then
2406 we can again compute number of iterations as (b - (a - s)) / s. */
2407 step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2408 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2409 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2411 bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2412 lowpart_subreg (mode, step, comp_mode));
2417 /* If s is power of 2, we know that the loop is infinite if
2418 a % s <= b % s and a - s overflows. */
2419 assumption = simplify_gen_relational (reverse_condition (cond),
2423 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2424 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2425 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2426 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2428 alloc_EXPR_LIST (0, assumption, desc->infinite);
2432 assumption = simplify_gen_relational (cond, SImode, mode,
2435 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2438 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2439 tmp = lowpart_subreg (mode, tmp, comp_mode);
2440 assumption = simplify_gen_relational (reverse_condition (cond),
2443 delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2444 delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2446 if (assumption == const_true_rtx)
2447 goto zero_iter_simplify;
2448 else if (assumption != const0_rtx)
2449 desc->noloop_assumptions =
2450 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2451 delta = simplify_gen_binary (UDIV, mode, delta, step);
2452 desc->niter_expr = delta;
2455 old_niter = desc->niter_expr;
2457 simplify_using_initial_values (loop, AND, &desc->assumptions);
2458 if (desc->assumptions
2459 && XEXP (desc->assumptions, 0) == const0_rtx)
2461 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2462 simplify_using_initial_values (loop, IOR, &desc->infinite);
2463 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2465 /* Rerun the simplification. Consider code (created by copying loop headers)
2477 The first pass determines that i = 0, the second pass uses it to eliminate
2478 noloop assumption. */
2480 simplify_using_initial_values (loop, AND, &desc->assumptions);
2481 if (desc->assumptions
2482 && XEXP (desc->assumptions, 0) == const0_rtx)
2484 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2485 simplify_using_initial_values (loop, IOR, &desc->infinite);
2486 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2488 if (desc->noloop_assumptions
2489 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2492 if (GET_CODE (desc->niter_expr) == CONST_INT)
2494 unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2496 desc->const_iter = true;
2497 desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2501 if (!desc->niter_max)
2502 desc->niter_max = determine_max_iter (desc);
2504 /* simplify_using_initial_values does a copy propagation on the registers
2505 in the expression for the number of iterations. This prolongs life
2506 ranges of registers and increases register pressure, and usually
2507 brings no gain (and if it happens to do, the cse pass will take care
2508 of it anyway). So prevent this behavior, unless it enabled us to
2509 derive that the number of iterations is a constant. */
2510 desc->niter_expr = old_niter;
2516 /* Simplify the assumptions. */
2517 simplify_using_initial_values (loop, AND, &desc->assumptions);
2518 if (desc->assumptions
2519 && XEXP (desc->assumptions, 0) == const0_rtx)
2521 simplify_using_initial_values (loop, IOR, &desc->infinite);
2525 desc->const_iter = true;
2527 desc->niter_max = 0;
2528 desc->noloop_assumptions = NULL_RTX;
2529 desc->niter_expr = const0_rtx;
2533 desc->simple_p = false;
2537 /* Checks whether E is a simple exit from LOOP and stores its description
2541 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2543 basic_block exit_bb;
2548 desc->simple_p = false;
2550 /* It must belong directly to the loop. */
2551 if (exit_bb->loop_father != loop)
2554 /* It must be tested (at least) once during any iteration. */
2555 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2558 /* It must end in a simple conditional jump. */
2559 if (!any_condjump_p (BB_END (exit_bb)))
2562 ein = EDGE_SUCC (exit_bb, 0);
2564 ein = EDGE_SUCC (exit_bb, 1);
2567 desc->in_edge = ein;
2569 /* Test whether the condition is suitable. */
2570 if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2573 if (ein->flags & EDGE_FALLTHRU)
2575 condition = reversed_condition (condition);
2580 /* Check that we are able to determine number of iterations and fill
2581 in information about it. */
2582 iv_number_of_iterations (loop, at, condition, desc);
2585 /* Finds a simple exit of LOOP and stores its description into DESC. */
2588 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2593 struct niter_desc act;
2597 desc->simple_p = false;
2598 body = get_loop_body (loop);
2600 for (i = 0; i < loop->num_nodes; i++)
2602 FOR_EACH_EDGE (e, ei, body[i]->succs)
2604 if (flow_bb_inside_loop_p (loop, e->dest))
2607 check_simple_exit (loop, e, &act);
2615 /* Prefer constant iterations; the less the better. */
2617 || (desc->const_iter && act.niter >= desc->niter))
2620 /* Also if the actual exit may be infinite, while the old one
2621 not, prefer the old one. */
2622 if (act.infinite && !desc->infinite)
2634 fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2635 fprintf (dump_file, " simple exit %d -> %d\n",
2636 desc->out_edge->src->index,
2637 desc->out_edge->dest->index);
2638 if (desc->assumptions)
2640 fprintf (dump_file, " assumptions: ");
2641 print_rtl (dump_file, desc->assumptions);
2642 fprintf (dump_file, "\n");
2644 if (desc->noloop_assumptions)
2646 fprintf (dump_file, " does not roll if: ");
2647 print_rtl (dump_file, desc->noloop_assumptions);
2648 fprintf (dump_file, "\n");
2652 fprintf (dump_file, " infinite if: ");
2653 print_rtl (dump_file, desc->infinite);
2654 fprintf (dump_file, "\n");
2657 fprintf (dump_file, " number of iterations: ");
2658 print_rtl (dump_file, desc->niter_expr);
2659 fprintf (dump_file, "\n");
2661 fprintf (dump_file, " upper bound: ");
2662 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2663 fprintf (dump_file, "\n");
2666 fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2672 /* Creates a simple loop description of LOOP if it was not computed
2676 get_simple_loop_desc (struct loop *loop)
2678 struct niter_desc *desc = simple_loop_desc (loop);
2683 desc = XNEW (struct niter_desc);
2684 iv_analysis_loop_init (loop);
2685 find_simple_exit (loop, desc);
2688 if (desc->simple_p && (desc->assumptions || desc->infinite))
2690 const char *wording;
2692 /* Assume that no overflow happens and that the loop is finite.
2693 We already warned at the tree level if we ran optimizations there. */
2694 if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
2699 flag_unsafe_loop_optimizations
2700 ? N_("assuming that the loop is not infinite")
2701 : N_("cannot optimize possibly infinite loops");
2702 warning (OPT_Wunsafe_loop_optimizations, "%s",
2705 if (desc->assumptions)
2708 flag_unsafe_loop_optimizations
2709 ? N_("assuming that the loop counter does not overflow")
2710 : N_("cannot optimize loop, the loop counter may overflow");
2711 warning (OPT_Wunsafe_loop_optimizations, "%s",
2716 if (flag_unsafe_loop_optimizations)
2718 desc->assumptions = NULL_RTX;
2719 desc->infinite = NULL_RTX;
2726 /* Releases simple loop description for LOOP. */
2729 free_simple_loop_desc (struct loop *loop)
2731 struct niter_desc *desc = simple_loop_desc (loop);