2015-05-12 Pierre-Marie de Rodat <derodat@adacore.com>
[official-gcc.git] / gcc / loop-iv.c
blobbf6359da4a082831443c54759dabce69048a8179
1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
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
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This is a simple analysis of induction variables of the loop. The major use
21 is for determining the number of iterations of a loop for loop unrolling,
22 doloop optimization and branch prediction. The iv information is computed
23 on demand.
25 Induction variables are analyzed by walking the use-def chains. When
26 a basic induction variable (biv) is found, it is cached in the bivs
27 hash table. When register is proved to be a biv, its description
28 is stored to DF_REF_DATA of the def reference.
30 The analysis works always with one loop -- you must call
31 iv_analysis_loop_init (loop) for it. All the other functions then work with
32 this loop. When you need to work with another loop, just call
33 iv_analysis_loop_init for it. When you no longer need iv analysis, call
34 iv_analysis_done () to clean up the memory.
36 The available functions are:
38 iv_analyze (insn, reg, iv): Stores the description of the induction variable
39 corresponding to the use of register REG in INSN to IV. Returns true if
40 REG is an induction variable in INSN. false otherwise.
41 If use of REG is not found in INSN, following insns are scanned (so that
42 we may call this function on insn returned by get_condition).
43 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
44 corresponding to DEF, which is a register defined in INSN.
45 iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
46 corresponding to expression EXPR evaluated at INSN. All registers used bu
47 EXPR must also be used in INSN.
50 #include "config.h"
51 #include "system.h"
52 #include "coretypes.h"
53 #include "tm.h"
54 #include "rtl.h"
55 #include "hard-reg-set.h"
56 #include "obstack.h"
57 #include "predict.h"
58 #include "vec.h"
59 #include "hashtab.h"
60 #include "hash-set.h"
61 #include "machmode.h"
62 #include "input.h"
63 #include "function.h"
64 #include "dominance.h"
65 #include "cfg.h"
66 #include "basic-block.h"
67 #include "cfgloop.h"
68 #include "symtab.h"
69 #include "flags.h"
70 #include "statistics.h"
71 #include "double-int.h"
72 #include "real.h"
73 #include "fixed-value.h"
74 #include "alias.h"
75 #include "wide-int.h"
76 #include "inchash.h"
77 #include "tree.h"
78 #include "insn-config.h"
79 #include "expmed.h"
80 #include "dojump.h"
81 #include "explow.h"
82 #include "calls.h"
83 #include "emit-rtl.h"
84 #include "varasm.h"
85 #include "stmt.h"
86 #include "expr.h"
87 #include "intl.h"
88 #include "diagnostic-core.h"
89 #include "df.h"
90 #include "hash-table.h"
91 #include "dumpfile.h"
92 #include "rtl-iter.h"
94 /* Possible return values of iv_get_reaching_def. */
96 enum iv_grd_result
98 /* More than one reaching def, or reaching def that does not
99 dominate the use. */
100 GRD_INVALID,
102 /* The use is trivial invariant of the loop, i.e. is not changed
103 inside the loop. */
104 GRD_INVARIANT,
106 /* The use is reached by initial value and a value from the
107 previous iteration. */
108 GRD_MAYBE_BIV,
110 /* The use has single dominating def. */
111 GRD_SINGLE_DOM
114 /* Information about a biv. */
116 struct biv_entry
118 unsigned regno; /* The register of the biv. */
119 struct rtx_iv iv; /* Value of the biv. */
122 static bool clean_slate = true;
124 static unsigned int iv_ref_table_size = 0;
126 /* Table of rtx_ivs indexed by the df_ref uid field. */
127 static struct rtx_iv ** iv_ref_table;
129 /* Induction variable stored at the reference. */
130 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
131 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
133 /* The current loop. */
135 static struct loop *current_loop;
137 /* Hashtable helper. */
139 struct biv_entry_hasher : typed_free_remove <biv_entry>
141 typedef biv_entry *value_type;
142 typedef rtx_def *compare_type;
143 static inline hashval_t hash (const biv_entry *);
144 static inline bool equal (const biv_entry *, const rtx_def *);
147 /* Returns hash value for biv B. */
149 inline hashval_t
150 biv_entry_hasher::hash (const biv_entry *b)
152 return b->regno;
155 /* Compares biv B and register R. */
157 inline bool
158 biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r)
160 return b->regno == REGNO (r);
163 /* Bivs of the current loop. */
165 static hash_table<biv_entry_hasher> *bivs;
167 static bool iv_analyze_op (rtx_insn *, rtx, struct rtx_iv *);
169 /* Return the RTX code corresponding to the IV extend code EXTEND. */
170 static inline enum rtx_code
171 iv_extend_to_rtx_code (enum iv_extend_code extend)
173 switch (extend)
175 case IV_SIGN_EXTEND:
176 return SIGN_EXTEND;
177 case IV_ZERO_EXTEND:
178 return ZERO_EXTEND;
179 case IV_UNKNOWN_EXTEND:
180 return UNKNOWN;
182 gcc_unreachable ();
185 /* Dumps information about IV to FILE. */
187 extern void dump_iv_info (FILE *, struct rtx_iv *);
188 void
189 dump_iv_info (FILE *file, struct rtx_iv *iv)
191 if (!iv->base)
193 fprintf (file, "not simple");
194 return;
197 if (iv->step == const0_rtx
198 && !iv->first_special)
199 fprintf (file, "invariant ");
201 print_rtl (file, iv->base);
202 if (iv->step != const0_rtx)
204 fprintf (file, " + ");
205 print_rtl (file, iv->step);
206 fprintf (file, " * iteration");
208 fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
210 if (iv->mode != iv->extend_mode)
211 fprintf (file, " %s to %s",
212 rtx_name[iv_extend_to_rtx_code (iv->extend)],
213 GET_MODE_NAME (iv->extend_mode));
215 if (iv->mult != const1_rtx)
217 fprintf (file, " * ");
218 print_rtl (file, iv->mult);
220 if (iv->delta != const0_rtx)
222 fprintf (file, " + ");
223 print_rtl (file, iv->delta);
225 if (iv->first_special)
226 fprintf (file, " (first special)");
229 /* Generates a subreg to get the least significant part of EXPR (in mode
230 INNER_MODE) to OUTER_MODE. */
233 lowpart_subreg (machine_mode outer_mode, rtx expr,
234 machine_mode inner_mode)
236 return simplify_gen_subreg (outer_mode, expr, inner_mode,
237 subreg_lowpart_offset (outer_mode, inner_mode));
240 static void
241 check_iv_ref_table_size (void)
243 if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ())
245 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
246 iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
247 memset (&iv_ref_table[iv_ref_table_size], 0,
248 (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
249 iv_ref_table_size = new_size;
254 /* Checks whether REG is a well-behaved register. */
256 static bool
257 simple_reg_p (rtx reg)
259 unsigned r;
261 if (GET_CODE (reg) == SUBREG)
263 if (!subreg_lowpart_p (reg))
264 return false;
265 reg = SUBREG_REG (reg);
268 if (!REG_P (reg))
269 return false;
271 r = REGNO (reg);
272 if (HARD_REGISTER_NUM_P (r))
273 return false;
275 if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
276 return false;
278 return true;
281 /* Clears the information about ivs stored in df. */
283 static void
284 clear_iv_info (void)
286 unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
287 struct rtx_iv *iv;
289 check_iv_ref_table_size ();
290 for (i = 0; i < n_defs; i++)
292 iv = iv_ref_table[i];
293 if (iv)
295 free (iv);
296 iv_ref_table[i] = NULL;
300 bivs->empty ();
304 /* Prepare the data for an induction variable analysis of a LOOP. */
306 void
307 iv_analysis_loop_init (struct loop *loop)
309 current_loop = loop;
311 /* Clear the information from the analysis of the previous loop. */
312 if (clean_slate)
314 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
315 bivs = new hash_table<biv_entry_hasher> (10);
316 clean_slate = false;
318 else
319 clear_iv_info ();
321 /* Get rid of the ud chains before processing the rescans. Then add
322 the problem back. */
323 df_remove_problem (df_chain);
324 df_process_deferred_rescans ();
325 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
326 df_chain_add_problem (DF_UD_CHAIN);
327 df_note_add_problem ();
328 df_analyze_loop (loop);
329 if (dump_file)
330 df_dump_region (dump_file);
332 check_iv_ref_table_size ();
335 /* Finds the definition of REG that dominates loop latch and stores
336 it to DEF. Returns false if there is not a single definition
337 dominating the latch. If REG has no definition in loop, DEF
338 is set to NULL and true is returned. */
340 static bool
341 latch_dominating_def (rtx reg, df_ref *def)
343 df_ref single_rd = NULL, adef;
344 unsigned regno = REGNO (reg);
345 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
347 for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
349 if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
350 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
351 continue;
353 /* More than one reaching definition. */
354 if (single_rd)
355 return false;
357 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
358 return false;
360 single_rd = adef;
363 *def = single_rd;
364 return true;
367 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
369 static enum iv_grd_result
370 iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
372 df_ref use, adef;
373 basic_block def_bb, use_bb;
374 rtx_insn *def_insn;
375 bool dom_p;
377 *def = NULL;
378 if (!simple_reg_p (reg))
379 return GRD_INVALID;
380 if (GET_CODE (reg) == SUBREG)
381 reg = SUBREG_REG (reg);
382 gcc_assert (REG_P (reg));
384 use = df_find_use (insn, reg);
385 gcc_assert (use != NULL);
387 if (!DF_REF_CHAIN (use))
388 return GRD_INVARIANT;
390 /* More than one reaching def. */
391 if (DF_REF_CHAIN (use)->next)
392 return GRD_INVALID;
394 adef = DF_REF_CHAIN (use)->ref;
396 /* We do not handle setting only part of the register. */
397 if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
398 return GRD_INVALID;
400 def_insn = DF_REF_INSN (adef);
401 def_bb = DF_REF_BB (adef);
402 use_bb = BLOCK_FOR_INSN (insn);
404 if (use_bb == def_bb)
405 dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
406 else
407 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
409 if (dom_p)
411 *def = adef;
412 return GRD_SINGLE_DOM;
415 /* The definition does not dominate the use. This is still OK if
416 this may be a use of a biv, i.e. if the def_bb dominates loop
417 latch. */
418 if (just_once_each_iteration_p (current_loop, def_bb))
419 return GRD_MAYBE_BIV;
421 return GRD_INVALID;
424 /* Sets IV to invariant CST in MODE. Always returns true (just for
425 consistency with other iv manipulation functions that may fail). */
427 static bool
428 iv_constant (struct rtx_iv *iv, rtx cst, machine_mode mode)
430 if (mode == VOIDmode)
431 mode = GET_MODE (cst);
433 iv->mode = mode;
434 iv->base = cst;
435 iv->step = const0_rtx;
436 iv->first_special = false;
437 iv->extend = IV_UNKNOWN_EXTEND;
438 iv->extend_mode = iv->mode;
439 iv->delta = const0_rtx;
440 iv->mult = const1_rtx;
442 return true;
445 /* Evaluates application of subreg to MODE on IV. */
447 static bool
448 iv_subreg (struct rtx_iv *iv, machine_mode mode)
450 /* If iv is invariant, just calculate the new value. */
451 if (iv->step == const0_rtx
452 && !iv->first_special)
454 rtx val = get_iv_value (iv, const0_rtx);
455 val = lowpart_subreg (mode, val,
456 iv->extend == IV_UNKNOWN_EXTEND
457 ? iv->mode : iv->extend_mode);
459 iv->base = val;
460 iv->extend = IV_UNKNOWN_EXTEND;
461 iv->mode = iv->extend_mode = mode;
462 iv->delta = const0_rtx;
463 iv->mult = const1_rtx;
464 return true;
467 if (iv->extend_mode == mode)
468 return true;
470 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
471 return false;
473 iv->extend = IV_UNKNOWN_EXTEND;
474 iv->mode = mode;
476 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
477 simplify_gen_binary (MULT, iv->extend_mode,
478 iv->base, iv->mult));
479 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
480 iv->mult = const1_rtx;
481 iv->delta = const0_rtx;
482 iv->first_special = false;
484 return true;
487 /* Evaluates application of EXTEND to MODE on IV. */
489 static bool
490 iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, machine_mode mode)
492 /* If iv is invariant, just calculate the new value. */
493 if (iv->step == const0_rtx
494 && !iv->first_special)
496 rtx val = get_iv_value (iv, const0_rtx);
497 if (iv->extend_mode != iv->mode
498 && iv->extend != IV_UNKNOWN_EXTEND
499 && iv->extend != extend)
500 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
501 val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
502 val,
503 iv->extend == extend
504 ? iv->extend_mode : iv->mode);
505 iv->base = val;
506 iv->extend = IV_UNKNOWN_EXTEND;
507 iv->mode = iv->extend_mode = mode;
508 iv->delta = const0_rtx;
509 iv->mult = const1_rtx;
510 return true;
513 if (mode != iv->extend_mode)
514 return false;
516 if (iv->extend != IV_UNKNOWN_EXTEND
517 && iv->extend != extend)
518 return false;
520 iv->extend = extend;
522 return true;
525 /* Evaluates negation of IV. */
527 static bool
528 iv_neg (struct rtx_iv *iv)
530 if (iv->extend == IV_UNKNOWN_EXTEND)
532 iv->base = simplify_gen_unary (NEG, iv->extend_mode,
533 iv->base, iv->extend_mode);
534 iv->step = simplify_gen_unary (NEG, iv->extend_mode,
535 iv->step, iv->extend_mode);
537 else
539 iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
540 iv->delta, iv->extend_mode);
541 iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
542 iv->mult, iv->extend_mode);
545 return true;
548 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
550 static bool
551 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
553 machine_mode mode;
554 rtx arg;
556 /* Extend the constant to extend_mode of the other operand if necessary. */
557 if (iv0->extend == IV_UNKNOWN_EXTEND
558 && iv0->mode == iv0->extend_mode
559 && iv0->step == const0_rtx
560 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
562 iv0->extend_mode = iv1->extend_mode;
563 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
564 iv0->base, iv0->mode);
566 if (iv1->extend == IV_UNKNOWN_EXTEND
567 && iv1->mode == iv1->extend_mode
568 && iv1->step == const0_rtx
569 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
571 iv1->extend_mode = iv0->extend_mode;
572 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
573 iv1->base, iv1->mode);
576 mode = iv0->extend_mode;
577 if (mode != iv1->extend_mode)
578 return false;
580 if (iv0->extend == IV_UNKNOWN_EXTEND
581 && iv1->extend == IV_UNKNOWN_EXTEND)
583 if (iv0->mode != iv1->mode)
584 return false;
586 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
587 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
589 return true;
592 /* Handle addition of constant. */
593 if (iv1->extend == IV_UNKNOWN_EXTEND
594 && iv1->mode == mode
595 && iv1->step == const0_rtx)
597 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
598 return true;
601 if (iv0->extend == IV_UNKNOWN_EXTEND
602 && iv0->mode == mode
603 && iv0->step == const0_rtx)
605 arg = iv0->base;
606 *iv0 = *iv1;
607 if (op == MINUS
608 && !iv_neg (iv0))
609 return false;
611 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
612 return true;
615 return false;
618 /* Evaluates multiplication of IV by constant CST. */
620 static bool
621 iv_mult (struct rtx_iv *iv, rtx mby)
623 machine_mode mode = iv->extend_mode;
625 if (GET_MODE (mby) != VOIDmode
626 && GET_MODE (mby) != mode)
627 return false;
629 if (iv->extend == IV_UNKNOWN_EXTEND)
631 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
632 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
634 else
636 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
637 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
640 return true;
643 /* Evaluates shift of IV by constant CST. */
645 static bool
646 iv_shift (struct rtx_iv *iv, rtx mby)
648 machine_mode mode = iv->extend_mode;
650 if (GET_MODE (mby) != VOIDmode
651 && GET_MODE (mby) != mode)
652 return false;
654 if (iv->extend == IV_UNKNOWN_EXTEND)
656 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
657 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
659 else
661 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
662 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
665 return true;
668 /* The recursive part of get_biv_step. Gets the value of the single value
669 defined by DEF wrto initial value of REG inside loop, in shape described
670 at get_biv_step. */
672 static bool
673 get_biv_step_1 (df_ref def, rtx reg,
674 rtx *inner_step, machine_mode *inner_mode,
675 enum iv_extend_code *extend, machine_mode outer_mode,
676 rtx *outer_step)
678 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
679 rtx next, nextr, tmp;
680 enum rtx_code code;
681 rtx_insn *insn = DF_REF_INSN (def);
682 df_ref next_def;
683 enum iv_grd_result res;
685 set = single_set (insn);
686 if (!set)
687 return false;
689 rhs = find_reg_equal_equiv_note (insn);
690 if (rhs)
691 rhs = XEXP (rhs, 0);
692 else
693 rhs = SET_SRC (set);
695 code = GET_CODE (rhs);
696 switch (code)
698 case SUBREG:
699 case REG:
700 next = rhs;
701 break;
703 case PLUS:
704 case MINUS:
705 op0 = XEXP (rhs, 0);
706 op1 = XEXP (rhs, 1);
708 if (code == PLUS && CONSTANT_P (op0))
710 tmp = op0; op0 = op1; op1 = tmp;
713 if (!simple_reg_p (op0)
714 || !CONSTANT_P (op1))
715 return false;
717 if (GET_MODE (rhs) != outer_mode)
719 /* ppc64 uses expressions like
721 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
723 this is equivalent to
725 (set x':DI (plus:DI y:DI 1))
726 (set x:SI (subreg:SI (x':DI)). */
727 if (GET_CODE (op0) != SUBREG)
728 return false;
729 if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
730 return false;
733 next = op0;
734 break;
736 case SIGN_EXTEND:
737 case ZERO_EXTEND:
738 if (GET_MODE (rhs) != outer_mode)
739 return false;
741 op0 = XEXP (rhs, 0);
742 if (!simple_reg_p (op0))
743 return false;
745 next = op0;
746 break;
748 default:
749 return false;
752 if (GET_CODE (next) == SUBREG)
754 if (!subreg_lowpart_p (next))
755 return false;
757 nextr = SUBREG_REG (next);
758 if (GET_MODE (nextr) != outer_mode)
759 return false;
761 else
762 nextr = next;
764 res = iv_get_reaching_def (insn, nextr, &next_def);
766 if (res == GRD_INVALID || res == GRD_INVARIANT)
767 return false;
769 if (res == GRD_MAYBE_BIV)
771 if (!rtx_equal_p (nextr, reg))
772 return false;
774 *inner_step = const0_rtx;
775 *extend = IV_UNKNOWN_EXTEND;
776 *inner_mode = outer_mode;
777 *outer_step = const0_rtx;
779 else if (!get_biv_step_1 (next_def, reg,
780 inner_step, inner_mode, extend, outer_mode,
781 outer_step))
782 return false;
784 if (GET_CODE (next) == SUBREG)
786 machine_mode amode = GET_MODE (next);
788 if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
789 return false;
791 *inner_mode = amode;
792 *inner_step = simplify_gen_binary (PLUS, outer_mode,
793 *inner_step, *outer_step);
794 *outer_step = const0_rtx;
795 *extend = IV_UNKNOWN_EXTEND;
798 switch (code)
800 case REG:
801 case SUBREG:
802 break;
804 case PLUS:
805 case MINUS:
806 if (*inner_mode == outer_mode
807 /* See comment in previous switch. */
808 || GET_MODE (rhs) != outer_mode)
809 *inner_step = simplify_gen_binary (code, outer_mode,
810 *inner_step, op1);
811 else
812 *outer_step = simplify_gen_binary (code, outer_mode,
813 *outer_step, op1);
814 break;
816 case SIGN_EXTEND:
817 case ZERO_EXTEND:
818 gcc_assert (GET_MODE (op0) == *inner_mode
819 && *extend == IV_UNKNOWN_EXTEND
820 && *outer_step == const0_rtx);
822 *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
823 break;
825 default:
826 return false;
829 return true;
832 /* Gets the operation on register REG inside loop, in shape
834 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
836 If the operation cannot be described in this shape, return false.
837 LAST_DEF is the definition of REG that dominates loop latch. */
839 static bool
840 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
841 machine_mode *inner_mode, enum iv_extend_code *extend,
842 machine_mode *outer_mode, rtx *outer_step)
844 *outer_mode = GET_MODE (reg);
846 if (!get_biv_step_1 (last_def, reg,
847 inner_step, inner_mode, extend, *outer_mode,
848 outer_step))
849 return false;
851 gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
852 gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
854 return true;
857 /* Records information that DEF is induction variable IV. */
859 static void
860 record_iv (df_ref def, struct rtx_iv *iv)
862 struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
864 *recorded_iv = *iv;
865 check_iv_ref_table_size ();
866 DF_REF_IV_SET (def, recorded_iv);
869 /* If DEF was already analyzed for bivness, store the description of the biv to
870 IV and return true. Otherwise return false. */
872 static bool
873 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
875 struct biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
877 if (!biv)
878 return false;
880 *iv = biv->iv;
881 return true;
884 static void
885 record_biv (rtx def, struct rtx_iv *iv)
887 struct biv_entry *biv = XNEW (struct biv_entry);
888 biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
890 biv->regno = REGNO (def);
891 biv->iv = *iv;
892 gcc_assert (!*slot);
893 *slot = biv;
896 /* Determines whether DEF is a biv and if so, stores its description
897 to *IV. */
899 static bool
900 iv_analyze_biv (rtx def, struct rtx_iv *iv)
902 rtx inner_step, outer_step;
903 machine_mode inner_mode, outer_mode;
904 enum iv_extend_code extend;
905 df_ref last_def;
907 if (dump_file)
909 fprintf (dump_file, "Analyzing ");
910 print_rtl (dump_file, def);
911 fprintf (dump_file, " for bivness.\n");
914 if (!REG_P (def))
916 if (!CONSTANT_P (def))
917 return false;
919 return iv_constant (iv, def, VOIDmode);
922 if (!latch_dominating_def (def, &last_def))
924 if (dump_file)
925 fprintf (dump_file, " not simple.\n");
926 return false;
929 if (!last_def)
930 return iv_constant (iv, def, VOIDmode);
932 if (analyzed_for_bivness_p (def, iv))
934 if (dump_file)
935 fprintf (dump_file, " already analysed.\n");
936 return iv->base != NULL_RTX;
939 if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
940 &outer_mode, &outer_step))
942 iv->base = NULL_RTX;
943 goto end;
946 /* Loop transforms base to es (base + inner_step) + outer_step,
947 where es means extend of subreg between inner_mode and outer_mode.
948 The corresponding induction variable is
950 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
952 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
953 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
954 iv->mode = inner_mode;
955 iv->extend_mode = outer_mode;
956 iv->extend = extend;
957 iv->mult = const1_rtx;
958 iv->delta = outer_step;
959 iv->first_special = inner_mode != outer_mode;
961 end:
962 if (dump_file)
964 fprintf (dump_file, " ");
965 dump_iv_info (dump_file, iv);
966 fprintf (dump_file, "\n");
969 record_biv (def, iv);
970 return iv->base != NULL_RTX;
973 /* Analyzes expression RHS used at INSN and stores the result to *IV.
974 The mode of the induction variable is MODE. */
976 bool
977 iv_analyze_expr (rtx_insn *insn, rtx rhs, machine_mode mode,
978 struct rtx_iv *iv)
980 rtx mby = NULL_RTX, tmp;
981 rtx op0 = NULL_RTX, op1 = NULL_RTX;
982 struct rtx_iv iv0, iv1;
983 enum rtx_code code = GET_CODE (rhs);
984 machine_mode omode = mode;
986 iv->mode = VOIDmode;
987 iv->base = NULL_RTX;
988 iv->step = NULL_RTX;
990 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
992 if (CONSTANT_P (rhs)
993 || REG_P (rhs)
994 || code == SUBREG)
996 if (!iv_analyze_op (insn, rhs, iv))
997 return false;
999 if (iv->mode == VOIDmode)
1001 iv->mode = mode;
1002 iv->extend_mode = mode;
1005 return true;
1008 switch (code)
1010 case REG:
1011 op0 = rhs;
1012 break;
1014 case SIGN_EXTEND:
1015 case ZERO_EXTEND:
1016 case NEG:
1017 op0 = XEXP (rhs, 0);
1018 omode = GET_MODE (op0);
1019 break;
1021 case PLUS:
1022 case MINUS:
1023 op0 = XEXP (rhs, 0);
1024 op1 = XEXP (rhs, 1);
1025 break;
1027 case MULT:
1028 op0 = XEXP (rhs, 0);
1029 mby = XEXP (rhs, 1);
1030 if (!CONSTANT_P (mby))
1032 tmp = op0;
1033 op0 = mby;
1034 mby = tmp;
1036 if (!CONSTANT_P (mby))
1037 return false;
1038 break;
1040 case ASHIFT:
1041 op0 = XEXP (rhs, 0);
1042 mby = XEXP (rhs, 1);
1043 if (!CONSTANT_P (mby))
1044 return false;
1045 break;
1047 default:
1048 return false;
1051 if (op0
1052 && !iv_analyze_expr (insn, op0, omode, &iv0))
1053 return false;
1055 if (op1
1056 && !iv_analyze_expr (insn, op1, omode, &iv1))
1057 return false;
1059 switch (code)
1061 case SIGN_EXTEND:
1062 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1063 return false;
1064 break;
1066 case ZERO_EXTEND:
1067 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1068 return false;
1069 break;
1071 case NEG:
1072 if (!iv_neg (&iv0))
1073 return false;
1074 break;
1076 case PLUS:
1077 case MINUS:
1078 if (!iv_add (&iv0, &iv1, code))
1079 return false;
1080 break;
1082 case MULT:
1083 if (!iv_mult (&iv0, mby))
1084 return false;
1085 break;
1087 case ASHIFT:
1088 if (!iv_shift (&iv0, mby))
1089 return false;
1090 break;
1092 default:
1093 break;
1096 *iv = iv0;
1097 return iv->base != NULL_RTX;
1100 /* Analyzes iv DEF and stores the result to *IV. */
1102 static bool
1103 iv_analyze_def (df_ref def, struct rtx_iv *iv)
1105 rtx_insn *insn = DF_REF_INSN (def);
1106 rtx reg = DF_REF_REG (def);
1107 rtx set, rhs;
1109 if (dump_file)
1111 fprintf (dump_file, "Analyzing def of ");
1112 print_rtl (dump_file, reg);
1113 fprintf (dump_file, " in insn ");
1114 print_rtl_single (dump_file, insn);
1117 check_iv_ref_table_size ();
1118 if (DF_REF_IV (def))
1120 if (dump_file)
1121 fprintf (dump_file, " already analysed.\n");
1122 *iv = *DF_REF_IV (def);
1123 return iv->base != NULL_RTX;
1126 iv->mode = VOIDmode;
1127 iv->base = NULL_RTX;
1128 iv->step = NULL_RTX;
1130 if (!REG_P (reg))
1131 return false;
1133 set = single_set (insn);
1134 if (!set)
1135 return false;
1137 if (!REG_P (SET_DEST (set)))
1138 return false;
1140 gcc_assert (SET_DEST (set) == reg);
1141 rhs = find_reg_equal_equiv_note (insn);
1142 if (rhs)
1143 rhs = XEXP (rhs, 0);
1144 else
1145 rhs = SET_SRC (set);
1147 iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1148 record_iv (def, iv);
1150 if (dump_file)
1152 print_rtl (dump_file, reg);
1153 fprintf (dump_file, " in insn ");
1154 print_rtl_single (dump_file, insn);
1155 fprintf (dump_file, " is ");
1156 dump_iv_info (dump_file, iv);
1157 fprintf (dump_file, "\n");
1160 return iv->base != NULL_RTX;
1163 /* Analyzes operand OP of INSN and stores the result to *IV. */
1165 static bool
1166 iv_analyze_op (rtx_insn *insn, rtx op, struct rtx_iv *iv)
1168 df_ref def = NULL;
1169 enum iv_grd_result res;
1171 if (dump_file)
1173 fprintf (dump_file, "Analyzing operand ");
1174 print_rtl (dump_file, op);
1175 fprintf (dump_file, " of insn ");
1176 print_rtl_single (dump_file, insn);
1179 if (function_invariant_p (op))
1180 res = GRD_INVARIANT;
1181 else if (GET_CODE (op) == SUBREG)
1183 if (!subreg_lowpart_p (op))
1184 return false;
1186 if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1187 return false;
1189 return iv_subreg (iv, GET_MODE (op));
1191 else
1193 res = iv_get_reaching_def (insn, op, &def);
1194 if (res == GRD_INVALID)
1196 if (dump_file)
1197 fprintf (dump_file, " not simple.\n");
1198 return false;
1202 if (res == GRD_INVARIANT)
1204 iv_constant (iv, op, VOIDmode);
1206 if (dump_file)
1208 fprintf (dump_file, " ");
1209 dump_iv_info (dump_file, iv);
1210 fprintf (dump_file, "\n");
1212 return true;
1215 if (res == GRD_MAYBE_BIV)
1216 return iv_analyze_biv (op, iv);
1218 return iv_analyze_def (def, iv);
1221 /* Analyzes value VAL at INSN and stores the result to *IV. */
1223 bool
1224 iv_analyze (rtx_insn *insn, rtx val, struct rtx_iv *iv)
1226 rtx reg;
1228 /* We must find the insn in that val is used, so that we get to UD chains.
1229 Since the function is sometimes called on result of get_condition,
1230 this does not necessarily have to be directly INSN; scan also the
1231 following insns. */
1232 if (simple_reg_p (val))
1234 if (GET_CODE (val) == SUBREG)
1235 reg = SUBREG_REG (val);
1236 else
1237 reg = val;
1239 while (!df_find_use (insn, reg))
1240 insn = NEXT_INSN (insn);
1243 return iv_analyze_op (insn, val, iv);
1246 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1248 bool
1249 iv_analyze_result (rtx_insn *insn, rtx def, struct rtx_iv *iv)
1251 df_ref adef;
1253 adef = df_find_def (insn, def);
1254 if (!adef)
1255 return false;
1257 return iv_analyze_def (adef, iv);
1260 /* Checks whether definition of register REG in INSN is a basic induction
1261 variable. IV analysis must have been initialized (via a call to
1262 iv_analysis_loop_init) for this function to produce a result. */
1264 bool
1265 biv_p (rtx_insn *insn, rtx reg)
1267 struct rtx_iv iv;
1268 df_ref def, last_def;
1270 if (!simple_reg_p (reg))
1271 return false;
1273 def = df_find_def (insn, reg);
1274 gcc_assert (def != NULL);
1275 if (!latch_dominating_def (reg, &last_def))
1276 return false;
1277 if (last_def != def)
1278 return false;
1280 if (!iv_analyze_biv (reg, &iv))
1281 return false;
1283 return iv.step != const0_rtx;
1286 /* Calculates value of IV at ITERATION-th iteration. */
1289 get_iv_value (struct rtx_iv *iv, rtx iteration)
1291 rtx val;
1293 /* We would need to generate some if_then_else patterns, and so far
1294 it is not needed anywhere. */
1295 gcc_assert (!iv->first_special);
1297 if (iv->step != const0_rtx && iteration != const0_rtx)
1298 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1299 simplify_gen_binary (MULT, iv->extend_mode,
1300 iv->step, iteration));
1301 else
1302 val = iv->base;
1304 if (iv->extend_mode == iv->mode)
1305 return val;
1307 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1309 if (iv->extend == IV_UNKNOWN_EXTEND)
1310 return val;
1312 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1313 iv->extend_mode, val, iv->mode);
1314 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1315 simplify_gen_binary (MULT, iv->extend_mode,
1316 iv->mult, val));
1318 return val;
1321 /* Free the data for an induction variable analysis. */
1323 void
1324 iv_analysis_done (void)
1326 if (!clean_slate)
1328 clear_iv_info ();
1329 clean_slate = true;
1330 df_finish_pass (true);
1331 delete bivs;
1332 bivs = NULL;
1333 free (iv_ref_table);
1334 iv_ref_table = NULL;
1335 iv_ref_table_size = 0;
1339 /* Computes inverse to X modulo (1 << MOD). */
1341 static uint64_t
1342 inverse (uint64_t x, int mod)
1344 uint64_t mask =
1345 ((uint64_t) 1 << (mod - 1) << 1) - 1;
1346 uint64_t rslt = 1;
1347 int i;
1349 for (i = 0; i < mod - 1; i++)
1351 rslt = (rslt * x) & mask;
1352 x = (x * x) & mask;
1355 return rslt;
1358 /* Checks whether any register in X is in set ALT. */
1360 static bool
1361 altered_reg_used (const_rtx x, bitmap alt)
1363 subrtx_iterator::array_type array;
1364 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
1366 const_rtx x = *iter;
1367 if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x)))
1368 return true;
1370 return false;
1373 /* Marks registers altered by EXPR in set ALT. */
1375 static void
1376 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1378 if (GET_CODE (expr) == SUBREG)
1379 expr = SUBREG_REG (expr);
1380 if (!REG_P (expr))
1381 return;
1383 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1386 /* Checks whether RHS is simple enough to process. */
1388 static bool
1389 simple_rhs_p (rtx rhs)
1391 rtx op0, op1;
1393 if (function_invariant_p (rhs)
1394 || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1395 return true;
1397 switch (GET_CODE (rhs))
1399 case PLUS:
1400 case MINUS:
1401 case AND:
1402 op0 = XEXP (rhs, 0);
1403 op1 = XEXP (rhs, 1);
1404 /* Allow reg OP const and reg OP reg. */
1405 if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1406 && !function_invariant_p (op0))
1407 return false;
1408 if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1409 && !function_invariant_p (op1))
1410 return false;
1412 return true;
1414 case ASHIFT:
1415 case ASHIFTRT:
1416 case LSHIFTRT:
1417 case MULT:
1418 op0 = XEXP (rhs, 0);
1419 op1 = XEXP (rhs, 1);
1420 /* Allow reg OP const. */
1421 if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1422 return false;
1423 if (!function_invariant_p (op1))
1424 return false;
1426 return true;
1428 default:
1429 return false;
1433 /* If REGNO has a single definition, return its known value, otherwise return
1434 null. */
1436 static rtx
1437 find_single_def_src (unsigned int regno)
1439 df_ref adef;
1440 rtx set, src;
1442 for (;;)
1444 rtx note;
1445 adef = DF_REG_DEF_CHAIN (regno);
1446 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1447 || DF_REF_IS_ARTIFICIAL (adef))
1448 return NULL_RTX;
1450 set = single_set (DF_REF_INSN (adef));
1451 if (set == NULL || !REG_P (SET_DEST (set))
1452 || REGNO (SET_DEST (set)) != regno)
1453 return NULL_RTX;
1455 note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1457 if (note && function_invariant_p (XEXP (note, 0)))
1459 src = XEXP (note, 0);
1460 break;
1462 src = SET_SRC (set);
1464 if (REG_P (src))
1466 regno = REGNO (src);
1467 continue;
1469 break;
1471 if (!function_invariant_p (src))
1472 return NULL_RTX;
1474 return src;
1477 /* If any registers in *EXPR that have a single definition, try to replace
1478 them with the known-equivalent values. */
1480 static void
1481 replace_single_def_regs (rtx *expr)
1483 subrtx_var_iterator::array_type array;
1484 repeat:
1485 FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)
1487 rtx x = *iter;
1488 if (REG_P (x))
1489 if (rtx new_x = find_single_def_src (REGNO (x)))
1491 *expr = simplify_replace_rtx (*expr, x, new_x);
1492 goto repeat;
1497 /* A subroutine of simplify_using_initial_values, this function examines INSN
1498 to see if it contains a suitable set that we can use to make a replacement.
1499 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1500 the set; return false otherwise. */
1502 static bool
1503 suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src)
1505 rtx set = single_set (insn);
1506 rtx lhs = NULL_RTX, rhs;
1508 if (!set)
1509 return false;
1511 lhs = SET_DEST (set);
1512 if (!REG_P (lhs))
1513 return false;
1515 rhs = find_reg_equal_equiv_note (insn);
1516 if (rhs)
1517 rhs = XEXP (rhs, 0);
1518 else
1519 rhs = SET_SRC (set);
1521 if (!simple_rhs_p (rhs))
1522 return false;
1524 *dest = lhs;
1525 *src = rhs;
1526 return true;
1529 /* Using the data returned by suitable_set_for_replacement, replace DEST
1530 with SRC in *EXPR and return the new expression. Also call
1531 replace_single_def_regs if the replacement changed something. */
1532 static void
1533 replace_in_expr (rtx *expr, rtx dest, rtx src)
1535 rtx old = *expr;
1536 *expr = simplify_replace_rtx (*expr, dest, src);
1537 if (old == *expr)
1538 return;
1539 replace_single_def_regs (expr);
1542 /* Checks whether A implies B. */
1544 static bool
1545 implies_p (rtx a, rtx b)
1547 rtx op0, op1, opb0, opb1, r;
1548 machine_mode mode;
1550 if (rtx_equal_p (a, b))
1551 return true;
1553 if (GET_CODE (a) == EQ)
1555 op0 = XEXP (a, 0);
1556 op1 = XEXP (a, 1);
1558 if (REG_P (op0)
1559 || (GET_CODE (op0) == SUBREG
1560 && REG_P (SUBREG_REG (op0))))
1562 r = simplify_replace_rtx (b, op0, op1);
1563 if (r == const_true_rtx)
1564 return true;
1567 if (REG_P (op1)
1568 || (GET_CODE (op1) == SUBREG
1569 && REG_P (SUBREG_REG (op1))))
1571 r = simplify_replace_rtx (b, op1, op0);
1572 if (r == const_true_rtx)
1573 return true;
1577 if (b == const_true_rtx)
1578 return true;
1580 if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1581 && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1582 || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1583 && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1584 return false;
1586 op0 = XEXP (a, 0);
1587 op1 = XEXP (a, 1);
1588 opb0 = XEXP (b, 0);
1589 opb1 = XEXP (b, 1);
1591 mode = GET_MODE (op0);
1592 if (mode != GET_MODE (opb0))
1593 mode = VOIDmode;
1594 else if (mode == VOIDmode)
1596 mode = GET_MODE (op1);
1597 if (mode != GET_MODE (opb1))
1598 mode = VOIDmode;
1601 /* A < B implies A + 1 <= B. */
1602 if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1603 && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1606 if (GET_CODE (a) == GT)
1608 r = op0;
1609 op0 = op1;
1610 op1 = r;
1613 if (GET_CODE (b) == GE)
1615 r = opb0;
1616 opb0 = opb1;
1617 opb1 = r;
1620 if (SCALAR_INT_MODE_P (mode)
1621 && rtx_equal_p (op1, opb1)
1622 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1623 return true;
1624 return false;
1627 /* A < B or A > B imply A != B. TODO: Likewise
1628 A + n < B implies A != B + n if neither wraps. */
1629 if (GET_CODE (b) == NE
1630 && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1631 || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1633 if (rtx_equal_p (op0, opb0)
1634 && rtx_equal_p (op1, opb1))
1635 return true;
1638 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1639 if (GET_CODE (a) == NE
1640 && op1 == const0_rtx)
1642 if ((GET_CODE (b) == GTU
1643 && opb1 == const0_rtx)
1644 || (GET_CODE (b) == GEU
1645 && opb1 == const1_rtx))
1646 return rtx_equal_p (op0, opb0);
1649 /* A != N is equivalent to A - (N + 1) <u -1. */
1650 if (GET_CODE (a) == NE
1651 && CONST_INT_P (op1)
1652 && GET_CODE (b) == LTU
1653 && opb1 == constm1_rtx
1654 && GET_CODE (opb0) == PLUS
1655 && CONST_INT_P (XEXP (opb0, 1))
1656 /* Avoid overflows. */
1657 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1658 != ((unsigned HOST_WIDE_INT)1
1659 << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1660 && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1661 return rtx_equal_p (op0, XEXP (opb0, 0));
1663 /* Likewise, A != N implies A - N > 0. */
1664 if (GET_CODE (a) == NE
1665 && CONST_INT_P (op1))
1667 if (GET_CODE (b) == GTU
1668 && GET_CODE (opb0) == PLUS
1669 && opb1 == const0_rtx
1670 && CONST_INT_P (XEXP (opb0, 1))
1671 /* Avoid overflows. */
1672 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1673 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1674 && rtx_equal_p (XEXP (opb0, 0), op0))
1675 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1676 if (GET_CODE (b) == GEU
1677 && GET_CODE (opb0) == PLUS
1678 && opb1 == const1_rtx
1679 && CONST_INT_P (XEXP (opb0, 1))
1680 /* Avoid overflows. */
1681 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1682 != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1683 && rtx_equal_p (XEXP (opb0, 0), op0))
1684 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1687 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1688 if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1689 && CONST_INT_P (op1)
1690 && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1691 || INTVAL (op1) >= 0)
1692 && GET_CODE (b) == LTU
1693 && CONST_INT_P (opb1)
1694 && rtx_equal_p (op0, opb0))
1695 return INTVAL (opb1) < 0;
1697 return false;
1700 /* Canonicalizes COND so that
1702 (1) Ensure that operands are ordered according to
1703 swap_commutative_operands_p.
1704 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1705 for GE, GEU, and LEU. */
1708 canon_condition (rtx cond)
1710 rtx tem;
1711 rtx op0, op1;
1712 enum rtx_code code;
1713 machine_mode mode;
1715 code = GET_CODE (cond);
1716 op0 = XEXP (cond, 0);
1717 op1 = XEXP (cond, 1);
1719 if (swap_commutative_operands_p (op0, op1))
1721 code = swap_condition (code);
1722 tem = op0;
1723 op0 = op1;
1724 op1 = tem;
1727 mode = GET_MODE (op0);
1728 if (mode == VOIDmode)
1729 mode = GET_MODE (op1);
1730 gcc_assert (mode != VOIDmode);
1732 if (CONST_SCALAR_INT_P (op1) && GET_MODE_CLASS (mode) != MODE_CC)
1734 rtx_mode_t const_val (op1, mode);
1736 switch (code)
1738 case LE:
1739 if (wi::ne_p (const_val, wi::max_value (mode, SIGNED)))
1741 code = LT;
1742 op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1744 break;
1746 case GE:
1747 if (wi::ne_p (const_val, wi::min_value (mode, SIGNED)))
1749 code = GT;
1750 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1752 break;
1754 case LEU:
1755 if (wi::ne_p (const_val, -1))
1757 code = LTU;
1758 op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1760 break;
1762 case GEU:
1763 if (wi::ne_p (const_val, 0))
1765 code = GTU;
1766 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1768 break;
1770 default:
1771 break;
1775 if (op0 != XEXP (cond, 0)
1776 || op1 != XEXP (cond, 1)
1777 || code != GET_CODE (cond)
1778 || GET_MODE (cond) != SImode)
1779 cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1781 return cond;
1784 /* Reverses CONDition; returns NULL if we cannot. */
1786 static rtx
1787 reversed_condition (rtx cond)
1789 enum rtx_code reversed;
1790 reversed = reversed_comparison_code (cond, NULL);
1791 if (reversed == UNKNOWN)
1792 return NULL_RTX;
1793 else
1794 return gen_rtx_fmt_ee (reversed,
1795 GET_MODE (cond), XEXP (cond, 0),
1796 XEXP (cond, 1));
1799 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1800 set of altered regs. */
1802 void
1803 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1805 rtx rev, reve, exp = *expr;
1807 /* If some register gets altered later, we do not really speak about its
1808 value at the time of comparison. */
1809 if (altered && altered_reg_used (cond, altered))
1810 return;
1812 if (GET_CODE (cond) == EQ
1813 && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1815 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1816 return;
1819 if (!COMPARISON_P (exp))
1820 return;
1822 rev = reversed_condition (cond);
1823 reve = reversed_condition (exp);
1825 cond = canon_condition (cond);
1826 exp = canon_condition (exp);
1827 if (rev)
1828 rev = canon_condition (rev);
1829 if (reve)
1830 reve = canon_condition (reve);
1832 if (rtx_equal_p (exp, cond))
1834 *expr = const_true_rtx;
1835 return;
1838 if (rev && rtx_equal_p (exp, rev))
1840 *expr = const0_rtx;
1841 return;
1844 if (implies_p (cond, exp))
1846 *expr = const_true_rtx;
1847 return;
1850 if (reve && implies_p (cond, reve))
1852 *expr = const0_rtx;
1853 return;
1856 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1857 be false. */
1858 if (rev && implies_p (exp, rev))
1860 *expr = const0_rtx;
1861 return;
1864 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1865 if (rev && reve && implies_p (reve, rev))
1867 *expr = const_true_rtx;
1868 return;
1871 /* We would like to have some other tests here. TODO. */
1873 return;
1876 /* Use relationship between A and *B to eventually eliminate *B.
1877 OP is the operation we consider. */
1879 static void
1880 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1882 switch (op)
1884 case AND:
1885 /* If A implies *B, we may replace *B by true. */
1886 if (implies_p (a, *b))
1887 *b = const_true_rtx;
1888 break;
1890 case IOR:
1891 /* If *B implies A, we may replace *B by false. */
1892 if (implies_p (*b, a))
1893 *b = const0_rtx;
1894 break;
1896 default:
1897 gcc_unreachable ();
1901 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1902 operation we consider. */
1904 static void
1905 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1907 rtx elt;
1909 for (elt = tail; elt; elt = XEXP (elt, 1))
1910 eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1911 for (elt = tail; elt; elt = XEXP (elt, 1))
1912 eliminate_implied_condition (op, XEXP (elt, 0), head);
1915 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1916 is a list, its elements are assumed to be combined using OP. */
1918 static void
1919 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1921 bool expression_valid;
1922 rtx head, tail, last_valid_expr;
1923 rtx_expr_list *cond_list;
1924 rtx_insn *insn;
1925 rtx neutral, aggr;
1926 regset altered, this_altered;
1927 edge e;
1929 if (!*expr)
1930 return;
1932 if (CONSTANT_P (*expr))
1933 return;
1935 if (GET_CODE (*expr) == EXPR_LIST)
1937 head = XEXP (*expr, 0);
1938 tail = XEXP (*expr, 1);
1940 eliminate_implied_conditions (op, &head, tail);
1942 switch (op)
1944 case AND:
1945 neutral = const_true_rtx;
1946 aggr = const0_rtx;
1947 break;
1949 case IOR:
1950 neutral = const0_rtx;
1951 aggr = const_true_rtx;
1952 break;
1954 default:
1955 gcc_unreachable ();
1958 simplify_using_initial_values (loop, UNKNOWN, &head);
1959 if (head == aggr)
1961 XEXP (*expr, 0) = aggr;
1962 XEXP (*expr, 1) = NULL_RTX;
1963 return;
1965 else if (head == neutral)
1967 *expr = tail;
1968 simplify_using_initial_values (loop, op, expr);
1969 return;
1971 simplify_using_initial_values (loop, op, &tail);
1973 if (tail && XEXP (tail, 0) == aggr)
1975 *expr = tail;
1976 return;
1979 XEXP (*expr, 0) = head;
1980 XEXP (*expr, 1) = tail;
1981 return;
1984 gcc_assert (op == UNKNOWN);
1986 replace_single_def_regs (expr);
1987 if (CONSTANT_P (*expr))
1988 return;
1990 e = loop_preheader_edge (loop);
1991 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1992 return;
1994 altered = ALLOC_REG_SET (&reg_obstack);
1995 this_altered = ALLOC_REG_SET (&reg_obstack);
1997 expression_valid = true;
1998 last_valid_expr = *expr;
1999 cond_list = NULL;
2000 while (1)
2002 insn = BB_END (e->src);
2003 if (any_condjump_p (insn))
2005 rtx cond = get_condition (BB_END (e->src), NULL, false, true);
2007 if (cond && (e->flags & EDGE_FALLTHRU))
2008 cond = reversed_condition (cond);
2009 if (cond)
2011 rtx old = *expr;
2012 simplify_using_condition (cond, expr, altered);
2013 if (old != *expr)
2015 rtx note;
2016 if (CONSTANT_P (*expr))
2017 goto out;
2018 for (note = cond_list; note; note = XEXP (note, 1))
2020 simplify_using_condition (XEXP (note, 0), expr, altered);
2021 if (CONSTANT_P (*expr))
2022 goto out;
2025 cond_list = alloc_EXPR_LIST (0, cond, cond_list);
2029 FOR_BB_INSNS_REVERSE (e->src, insn)
2031 rtx src, dest;
2032 rtx old = *expr;
2034 if (!INSN_P (insn))
2035 continue;
2037 CLEAR_REG_SET (this_altered);
2038 note_stores (PATTERN (insn), mark_altered, this_altered);
2039 if (CALL_P (insn))
2041 /* Kill all call clobbered registers. */
2042 unsigned int i;
2043 hard_reg_set_iterator hrsi;
2044 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
2045 0, i, hrsi)
2046 SET_REGNO_REG_SET (this_altered, i);
2049 if (suitable_set_for_replacement (insn, &dest, &src))
2051 rtx_expr_list **pnote, **pnote_next;
2053 replace_in_expr (expr, dest, src);
2054 if (CONSTANT_P (*expr))
2055 goto out;
2057 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2059 rtx note = *pnote;
2060 rtx old_cond = XEXP (note, 0);
2062 pnote_next = (rtx_expr_list **)&XEXP (note, 1);
2063 replace_in_expr (&XEXP (note, 0), dest, src);
2065 /* We can no longer use a condition that has been simplified
2066 to a constant, and simplify_using_condition will abort if
2067 we try. */
2068 if (CONSTANT_P (XEXP (note, 0)))
2070 *pnote = *pnote_next;
2071 pnote_next = pnote;
2072 free_EXPR_LIST_node (note);
2074 /* Retry simplifications with this condition if either the
2075 expression or the condition changed. */
2076 else if (old_cond != XEXP (note, 0) || old != *expr)
2077 simplify_using_condition (XEXP (note, 0), expr, altered);
2080 else
2082 rtx_expr_list **pnote, **pnote_next;
2084 /* If we did not use this insn to make a replacement, any overlap
2085 between stores in this insn and our expression will cause the
2086 expression to become invalid. */
2087 if (altered_reg_used (*expr, this_altered))
2088 goto out;
2090 /* Likewise for the conditions. */
2091 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2093 rtx note = *pnote;
2094 rtx old_cond = XEXP (note, 0);
2096 pnote_next = (rtx_expr_list **)&XEXP (note, 1);
2097 if (altered_reg_used (old_cond, this_altered))
2099 *pnote = *pnote_next;
2100 pnote_next = pnote;
2101 free_EXPR_LIST_node (note);
2106 if (CONSTANT_P (*expr))
2107 goto out;
2109 IOR_REG_SET (altered, this_altered);
2111 /* If the expression now contains regs that have been altered, we
2112 can't return it to the caller. However, it is still valid for
2113 further simplification, so keep searching to see if we can
2114 eventually turn it into a constant. */
2115 if (altered_reg_used (*expr, altered))
2116 expression_valid = false;
2117 if (expression_valid)
2118 last_valid_expr = *expr;
2121 if (!single_pred_p (e->src)
2122 || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2123 break;
2124 e = single_pred_edge (e->src);
2127 out:
2128 free_EXPR_LIST_list (&cond_list);
2129 if (!CONSTANT_P (*expr))
2130 *expr = last_valid_expr;
2131 FREE_REG_SET (altered);
2132 FREE_REG_SET (this_altered);
2135 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2136 that IV occurs as left operands of comparison COND and its signedness
2137 is SIGNED_P to DESC. */
2139 static void
2140 shorten_into_mode (struct rtx_iv *iv, machine_mode mode,
2141 enum rtx_code cond, bool signed_p, struct niter_desc *desc)
2143 rtx mmin, mmax, cond_over, cond_under;
2145 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2146 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2147 iv->base, mmin);
2148 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2149 iv->base, mmax);
2151 switch (cond)
2153 case LE:
2154 case LT:
2155 case LEU:
2156 case LTU:
2157 if (cond_under != const0_rtx)
2158 desc->infinite =
2159 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2160 if (cond_over != const0_rtx)
2161 desc->noloop_assumptions =
2162 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2163 break;
2165 case GE:
2166 case GT:
2167 case GEU:
2168 case GTU:
2169 if (cond_over != const0_rtx)
2170 desc->infinite =
2171 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2172 if (cond_under != const0_rtx)
2173 desc->noloop_assumptions =
2174 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2175 break;
2177 case NE:
2178 if (cond_over != const0_rtx)
2179 desc->infinite =
2180 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2181 if (cond_under != const0_rtx)
2182 desc->infinite =
2183 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2184 break;
2186 default:
2187 gcc_unreachable ();
2190 iv->mode = mode;
2191 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2194 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2195 subregs of the same mode if possible (sometimes it is necessary to add
2196 some assumptions to DESC). */
2198 static bool
2199 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
2200 enum rtx_code cond, struct niter_desc *desc)
2202 machine_mode comp_mode;
2203 bool signed_p;
2205 /* If the ivs behave specially in the first iteration, or are
2206 added/multiplied after extending, we ignore them. */
2207 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2208 return false;
2209 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2210 return false;
2212 /* If there is some extend, it must match signedness of the comparison. */
2213 switch (cond)
2215 case LE:
2216 case LT:
2217 if (iv0->extend == IV_ZERO_EXTEND
2218 || iv1->extend == IV_ZERO_EXTEND)
2219 return false;
2220 signed_p = true;
2221 break;
2223 case LEU:
2224 case LTU:
2225 if (iv0->extend == IV_SIGN_EXTEND
2226 || iv1->extend == IV_SIGN_EXTEND)
2227 return false;
2228 signed_p = false;
2229 break;
2231 case NE:
2232 if (iv0->extend != IV_UNKNOWN_EXTEND
2233 && iv1->extend != IV_UNKNOWN_EXTEND
2234 && iv0->extend != iv1->extend)
2235 return false;
2237 signed_p = false;
2238 if (iv0->extend != IV_UNKNOWN_EXTEND)
2239 signed_p = iv0->extend == IV_SIGN_EXTEND;
2240 if (iv1->extend != IV_UNKNOWN_EXTEND)
2241 signed_p = iv1->extend == IV_SIGN_EXTEND;
2242 break;
2244 default:
2245 gcc_unreachable ();
2248 /* Values of both variables should be computed in the same mode. These
2249 might indeed be different, if we have comparison like
2251 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2253 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2254 in different modes. This does not seem impossible to handle, but
2255 it hardly ever occurs in practice.
2257 The only exception is the case when one of operands is invariant.
2258 For example pentium 3 generates comparisons like
2259 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2260 definitely do not want this prevent the optimization. */
2261 comp_mode = iv0->extend_mode;
2262 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2263 comp_mode = iv1->extend_mode;
2265 if (iv0->extend_mode != comp_mode)
2267 if (iv0->mode != iv0->extend_mode
2268 || iv0->step != const0_rtx)
2269 return false;
2271 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2272 comp_mode, iv0->base, iv0->mode);
2273 iv0->extend_mode = comp_mode;
2276 if (iv1->extend_mode != comp_mode)
2278 if (iv1->mode != iv1->extend_mode
2279 || iv1->step != const0_rtx)
2280 return false;
2282 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2283 comp_mode, iv1->base, iv1->mode);
2284 iv1->extend_mode = comp_mode;
2287 /* Check that both ivs belong to a range of a single mode. If one of the
2288 operands is an invariant, we may need to shorten it into the common
2289 mode. */
2290 if (iv0->mode == iv0->extend_mode
2291 && iv0->step == const0_rtx
2292 && iv0->mode != iv1->mode)
2293 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2295 if (iv1->mode == iv1->extend_mode
2296 && iv1->step == const0_rtx
2297 && iv0->mode != iv1->mode)
2298 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2300 if (iv0->mode != iv1->mode)
2301 return false;
2303 desc->mode = iv0->mode;
2304 desc->signed_p = signed_p;
2306 return true;
2309 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2310 result. This function is called from iv_number_of_iterations with
2311 a number of fields in DESC already filled in. OLD_NITER is the original
2312 expression for the number of iterations, before we tried to simplify it. */
2314 static uint64_t
2315 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
2317 rtx niter = desc->niter_expr;
2318 rtx mmin, mmax, cmp;
2319 uint64_t nmax, inc;
2320 uint64_t andmax = 0;
2322 /* We used to look for constant operand 0 of AND,
2323 but canonicalization should always make this impossible. */
2324 gcc_checking_assert (GET_CODE (niter) != AND
2325 || !CONST_INT_P (XEXP (niter, 0)));
2327 if (GET_CODE (niter) == AND
2328 && CONST_INT_P (XEXP (niter, 1)))
2330 andmax = UINTVAL (XEXP (niter, 1));
2331 niter = XEXP (niter, 0);
2334 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2335 nmax = UINTVAL (mmax) - UINTVAL (mmin);
2337 if (GET_CODE (niter) == UDIV)
2339 if (!CONST_INT_P (XEXP (niter, 1)))
2340 return nmax;
2341 inc = INTVAL (XEXP (niter, 1));
2342 niter = XEXP (niter, 0);
2344 else
2345 inc = 1;
2347 /* We could use a binary search here, but for now improving the upper
2348 bound by just one eliminates one important corner case. */
2349 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2350 desc->mode, old_niter, mmax);
2351 simplify_using_initial_values (loop, UNKNOWN, &cmp);
2352 if (cmp == const_true_rtx)
2354 nmax--;
2356 if (dump_file)
2357 fprintf (dump_file, ";; improved upper bound by one.\n");
2359 nmax /= inc;
2360 if (andmax)
2361 nmax = MIN (nmax, andmax);
2362 if (dump_file)
2363 fprintf (dump_file, ";; Determined upper bound %" PRId64".\n",
2364 nmax);
2365 return nmax;
2368 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2369 the result into DESC. Very similar to determine_number_of_iterations
2370 (basically its rtl version), complicated by things like subregs. */
2372 static void
2373 iv_number_of_iterations (struct loop *loop, rtx_insn *insn, rtx condition,
2374 struct niter_desc *desc)
2376 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2377 struct rtx_iv iv0, iv1, tmp_iv;
2378 rtx assumption, may_not_xform;
2379 enum rtx_code cond;
2380 machine_mode mode, comp_mode;
2381 rtx mmin, mmax, mode_mmin, mode_mmax;
2382 uint64_t s, size, d, inv, max;
2383 int64_t up, down, inc, step_val;
2384 int was_sharp = false;
2385 rtx old_niter;
2386 bool step_is_pow2;
2388 /* The meaning of these assumptions is this:
2389 if !assumptions
2390 then the rest of information does not have to be valid
2391 if noloop_assumptions then the loop does not roll
2392 if infinite then this exit is never used */
2394 desc->assumptions = NULL_RTX;
2395 desc->noloop_assumptions = NULL_RTX;
2396 desc->infinite = NULL_RTX;
2397 desc->simple_p = true;
2399 desc->const_iter = false;
2400 desc->niter_expr = NULL_RTX;
2402 cond = GET_CODE (condition);
2403 gcc_assert (COMPARISON_P (condition));
2405 mode = GET_MODE (XEXP (condition, 0));
2406 if (mode == VOIDmode)
2407 mode = GET_MODE (XEXP (condition, 1));
2408 /* The constant comparisons should be folded. */
2409 gcc_assert (mode != VOIDmode);
2411 /* We only handle integers or pointers. */
2412 if (GET_MODE_CLASS (mode) != MODE_INT
2413 && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2414 goto fail;
2416 op0 = XEXP (condition, 0);
2417 if (!iv_analyze (insn, op0, &iv0))
2418 goto fail;
2419 if (iv0.extend_mode == VOIDmode)
2420 iv0.mode = iv0.extend_mode = mode;
2422 op1 = XEXP (condition, 1);
2423 if (!iv_analyze (insn, op1, &iv1))
2424 goto fail;
2425 if (iv1.extend_mode == VOIDmode)
2426 iv1.mode = iv1.extend_mode = mode;
2428 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2429 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2430 goto fail;
2432 /* Check condition and normalize it. */
2434 switch (cond)
2436 case GE:
2437 case GT:
2438 case GEU:
2439 case GTU:
2440 tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2441 cond = swap_condition (cond);
2442 break;
2443 case NE:
2444 case LE:
2445 case LEU:
2446 case LT:
2447 case LTU:
2448 break;
2449 default:
2450 goto fail;
2453 /* Handle extends. This is relatively nontrivial, so we only try in some
2454 easy cases, when we can canonicalize the ivs (possibly by adding some
2455 assumptions) to shape subreg (base + i * step). This function also fills
2456 in desc->mode and desc->signed_p. */
2458 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2459 goto fail;
2461 comp_mode = iv0.extend_mode;
2462 mode = iv0.mode;
2463 size = GET_MODE_PRECISION (mode);
2464 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2465 mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2466 mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2468 if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2469 goto fail;
2471 /* We can take care of the case of two induction variables chasing each other
2472 if the test is NE. I have never seen a loop using it, but still it is
2473 cool. */
2474 if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2476 if (cond != NE)
2477 goto fail;
2479 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2480 iv1.step = const0_rtx;
2483 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2484 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2486 /* This is either infinite loop or the one that ends immediately, depending
2487 on initial values. Unswitching should remove this kind of conditions. */
2488 if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2489 goto fail;
2491 if (cond != NE)
2493 if (iv0.step == const0_rtx)
2494 step_val = -INTVAL (iv1.step);
2495 else
2496 step_val = INTVAL (iv0.step);
2498 /* Ignore loops of while (i-- < 10) type. */
2499 if (step_val < 0)
2500 goto fail;
2502 step_is_pow2 = !(step_val & (step_val - 1));
2504 else
2506 /* We do not care about whether the step is power of two in this
2507 case. */
2508 step_is_pow2 = false;
2509 step_val = 0;
2512 /* Some more condition normalization. We must record some assumptions
2513 due to overflows. */
2514 switch (cond)
2516 case LT:
2517 case LTU:
2518 /* We want to take care only of non-sharp relationals; this is easy,
2519 as in cases the overflow would make the transformation unsafe
2520 the loop does not roll. Seemingly it would make more sense to want
2521 to take care of sharp relationals instead, as NE is more similar to
2522 them, but the problem is that here the transformation would be more
2523 difficult due to possibly infinite loops. */
2524 if (iv0.step == const0_rtx)
2526 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2527 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2528 mode_mmax);
2529 if (assumption == const_true_rtx)
2530 goto zero_iter_simplify;
2531 iv0.base = simplify_gen_binary (PLUS, comp_mode,
2532 iv0.base, const1_rtx);
2534 else
2536 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2537 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2538 mode_mmin);
2539 if (assumption == const_true_rtx)
2540 goto zero_iter_simplify;
2541 iv1.base = simplify_gen_binary (PLUS, comp_mode,
2542 iv1.base, constm1_rtx);
2545 if (assumption != const0_rtx)
2546 desc->noloop_assumptions =
2547 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2548 cond = (cond == LT) ? LE : LEU;
2550 /* It will be useful to be able to tell the difference once more in
2551 LE -> NE reduction. */
2552 was_sharp = true;
2553 break;
2554 default: ;
2557 /* Take care of trivially infinite loops. */
2558 if (cond != NE)
2560 if (iv0.step == const0_rtx)
2562 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2563 if (rtx_equal_p (tmp, mode_mmin))
2565 desc->infinite =
2566 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2567 /* Fill in the remaining fields somehow. */
2568 goto zero_iter_simplify;
2571 else
2573 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2574 if (rtx_equal_p (tmp, mode_mmax))
2576 desc->infinite =
2577 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2578 /* Fill in the remaining fields somehow. */
2579 goto zero_iter_simplify;
2584 /* If we can we want to take care of NE conditions instead of size
2585 comparisons, as they are much more friendly (most importantly
2586 this takes care of special handling of loops with step 1). We can
2587 do it if we first check that upper bound is greater or equal to
2588 lower bound, their difference is constant c modulo step and that
2589 there is not an overflow. */
2590 if (cond != NE)
2592 if (iv0.step == const0_rtx)
2593 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2594 else
2595 step = iv0.step;
2596 step = lowpart_subreg (mode, step, comp_mode);
2597 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2598 delta = lowpart_subreg (mode, delta, comp_mode);
2599 delta = simplify_gen_binary (UMOD, mode, delta, step);
2600 may_xform = const0_rtx;
2601 may_not_xform = const_true_rtx;
2603 if (CONST_INT_P (delta))
2605 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2607 /* A special case. We have transformed condition of type
2608 for (i = 0; i < 4; i += 4)
2609 into
2610 for (i = 0; i <= 3; i += 4)
2611 obviously if the test for overflow during that transformation
2612 passed, we cannot overflow here. Most importantly any
2613 loop with sharp end condition and step 1 falls into this
2614 category, so handling this case specially is definitely
2615 worth the troubles. */
2616 may_xform = const_true_rtx;
2618 else if (iv0.step == const0_rtx)
2620 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2621 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2622 bound = lowpart_subreg (mode, bound, comp_mode);
2623 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2624 may_xform = simplify_gen_relational (cond, SImode, mode,
2625 bound, tmp);
2626 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2627 SImode, mode,
2628 bound, tmp);
2630 else
2632 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2633 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2634 bound = lowpart_subreg (mode, bound, comp_mode);
2635 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2636 may_xform = simplify_gen_relational (cond, SImode, mode,
2637 tmp, bound);
2638 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2639 SImode, mode,
2640 tmp, bound);
2644 if (may_xform != const0_rtx)
2646 /* We perform the transformation always provided that it is not
2647 completely senseless. This is OK, as we would need this assumption
2648 to determine the number of iterations anyway. */
2649 if (may_xform != const_true_rtx)
2651 /* If the step is a power of two and the final value we have
2652 computed overflows, the cycle is infinite. Otherwise it
2653 is nontrivial to compute the number of iterations. */
2654 if (step_is_pow2)
2655 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2656 desc->infinite);
2657 else
2658 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2659 desc->assumptions);
2662 /* We are going to lose some information about upper bound on
2663 number of iterations in this step, so record the information
2664 here. */
2665 inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2666 if (CONST_INT_P (iv1.base))
2667 up = INTVAL (iv1.base);
2668 else
2669 up = INTVAL (mode_mmax) - inc;
2670 down = INTVAL (CONST_INT_P (iv0.base)
2671 ? iv0.base
2672 : mode_mmin);
2673 max = (uint64_t) (up - down) / inc + 1;
2674 if (!desc->infinite
2675 && !desc->assumptions)
2676 record_niter_bound (loop, max, false, true);
2678 if (iv0.step == const0_rtx)
2680 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2681 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2683 else
2685 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2686 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2689 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2690 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2691 assumption = simplify_gen_relational (reverse_condition (cond),
2692 SImode, mode, tmp0, tmp1);
2693 if (assumption == const_true_rtx)
2694 goto zero_iter_simplify;
2695 else if (assumption != const0_rtx)
2696 desc->noloop_assumptions =
2697 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2698 cond = NE;
2702 /* Count the number of iterations. */
2703 if (cond == NE)
2705 /* Everything we do here is just arithmetics modulo size of mode. This
2706 makes us able to do more involved computations of number of iterations
2707 than in other cases. First transform the condition into shape
2708 s * i <> c, with s positive. */
2709 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2710 iv0.base = const0_rtx;
2711 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2712 iv1.step = const0_rtx;
2713 if (INTVAL (iv0.step) < 0)
2715 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
2716 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
2718 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2720 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2721 is infinite. Otherwise, the number of iterations is
2722 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2723 s = INTVAL (iv0.step); d = 1;
2724 while (s % 2 != 1)
2726 s /= 2;
2727 d *= 2;
2728 size--;
2730 bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1);
2732 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2733 tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2734 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2735 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2737 tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2738 inv = inverse (s, size);
2739 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2740 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2742 else
2744 if (iv1.step == const0_rtx)
2745 /* Condition in shape a + s * i <= b
2746 We must know that b + s does not overflow and a <= b + s and then we
2747 can compute number of iterations as (b + s - a) / s. (It might
2748 seem that we in fact could be more clever about testing the b + s
2749 overflow condition using some information about b - a mod s,
2750 but it was already taken into account during LE -> NE transform). */
2752 step = iv0.step;
2753 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2754 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2756 bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2757 lowpart_subreg (mode, step,
2758 comp_mode));
2759 if (step_is_pow2)
2761 rtx t0, t1;
2763 /* If s is power of 2, we know that the loop is infinite if
2764 a % s <= b % s and b + s overflows. */
2765 assumption = simplify_gen_relational (reverse_condition (cond),
2766 SImode, mode,
2767 tmp1, bound);
2769 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2770 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2771 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2772 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2773 desc->infinite =
2774 alloc_EXPR_LIST (0, assumption, desc->infinite);
2776 else
2778 assumption = simplify_gen_relational (cond, SImode, mode,
2779 tmp1, bound);
2780 desc->assumptions =
2781 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2784 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2785 tmp = lowpart_subreg (mode, tmp, comp_mode);
2786 assumption = simplify_gen_relational (reverse_condition (cond),
2787 SImode, mode, tmp0, tmp);
2789 delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2790 delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2792 else
2794 /* Condition in shape a <= b - s * i
2795 We must know that a - s does not overflow and a - s <= b and then
2796 we can again compute number of iterations as (b - (a - s)) / s. */
2797 step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2798 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2799 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2801 bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2802 lowpart_subreg (mode, step, comp_mode));
2803 if (step_is_pow2)
2805 rtx t0, t1;
2807 /* If s is power of 2, we know that the loop is infinite if
2808 a % s <= b % s and a - s overflows. */
2809 assumption = simplify_gen_relational (reverse_condition (cond),
2810 SImode, mode,
2811 bound, tmp0);
2813 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2814 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2815 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2816 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2817 desc->infinite =
2818 alloc_EXPR_LIST (0, assumption, desc->infinite);
2820 else
2822 assumption = simplify_gen_relational (cond, SImode, mode,
2823 bound, tmp0);
2824 desc->assumptions =
2825 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2828 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2829 tmp = lowpart_subreg (mode, tmp, comp_mode);
2830 assumption = simplify_gen_relational (reverse_condition (cond),
2831 SImode, mode,
2832 tmp, tmp1);
2833 delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2834 delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2836 if (assumption == const_true_rtx)
2837 goto zero_iter_simplify;
2838 else if (assumption != const0_rtx)
2839 desc->noloop_assumptions =
2840 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2841 delta = simplify_gen_binary (UDIV, mode, delta, step);
2842 desc->niter_expr = delta;
2845 old_niter = desc->niter_expr;
2847 simplify_using_initial_values (loop, AND, &desc->assumptions);
2848 if (desc->assumptions
2849 && XEXP (desc->assumptions, 0) == const0_rtx)
2850 goto fail;
2851 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2852 simplify_using_initial_values (loop, IOR, &desc->infinite);
2853 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2855 /* Rerun the simplification. Consider code (created by copying loop headers)
2857 i = 0;
2859 if (0 < n)
2863 i++;
2864 } while (i < n);
2867 The first pass determines that i = 0, the second pass uses it to eliminate
2868 noloop assumption. */
2870 simplify_using_initial_values (loop, AND, &desc->assumptions);
2871 if (desc->assumptions
2872 && XEXP (desc->assumptions, 0) == const0_rtx)
2873 goto fail;
2874 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2875 simplify_using_initial_values (loop, IOR, &desc->infinite);
2876 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2878 if (desc->noloop_assumptions
2879 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2880 goto zero_iter;
2882 if (CONST_INT_P (desc->niter_expr))
2884 uint64_t val = INTVAL (desc->niter_expr);
2886 desc->const_iter = true;
2887 desc->niter = val & GET_MODE_MASK (desc->mode);
2888 if (!desc->infinite
2889 && !desc->assumptions)
2890 record_niter_bound (loop, desc->niter, false, true);
2892 else
2894 max = determine_max_iter (loop, desc, old_niter);
2895 if (!max)
2896 goto zero_iter_simplify;
2897 if (!desc->infinite
2898 && !desc->assumptions)
2899 record_niter_bound (loop, max, false, true);
2901 /* simplify_using_initial_values does a copy propagation on the registers
2902 in the expression for the number of iterations. This prolongs life
2903 ranges of registers and increases register pressure, and usually
2904 brings no gain (and if it happens to do, the cse pass will take care
2905 of it anyway). So prevent this behavior, unless it enabled us to
2906 derive that the number of iterations is a constant. */
2907 desc->niter_expr = old_niter;
2910 return;
2912 zero_iter_simplify:
2913 /* Simplify the assumptions. */
2914 simplify_using_initial_values (loop, AND, &desc->assumptions);
2915 if (desc->assumptions
2916 && XEXP (desc->assumptions, 0) == const0_rtx)
2917 goto fail;
2918 simplify_using_initial_values (loop, IOR, &desc->infinite);
2920 /* Fallthru. */
2921 zero_iter:
2922 desc->const_iter = true;
2923 desc->niter = 0;
2924 record_niter_bound (loop, 0, true, true);
2925 desc->noloop_assumptions = NULL_RTX;
2926 desc->niter_expr = const0_rtx;
2927 return;
2929 fail:
2930 desc->simple_p = false;
2931 return;
2934 /* Checks whether E is a simple exit from LOOP and stores its description
2935 into DESC. */
2937 static void
2938 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2940 basic_block exit_bb;
2941 rtx condition;
2942 rtx_insn *at;
2943 edge ein;
2945 exit_bb = e->src;
2946 desc->simple_p = false;
2948 /* It must belong directly to the loop. */
2949 if (exit_bb->loop_father != loop)
2950 return;
2952 /* It must be tested (at least) once during any iteration. */
2953 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2954 return;
2956 /* It must end in a simple conditional jump. */
2957 if (!any_condjump_p (BB_END (exit_bb)))
2958 return;
2960 ein = EDGE_SUCC (exit_bb, 0);
2961 if (ein == e)
2962 ein = EDGE_SUCC (exit_bb, 1);
2964 desc->out_edge = e;
2965 desc->in_edge = ein;
2967 /* Test whether the condition is suitable. */
2968 if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2969 return;
2971 if (ein->flags & EDGE_FALLTHRU)
2973 condition = reversed_condition (condition);
2974 if (!condition)
2975 return;
2978 /* Check that we are able to determine number of iterations and fill
2979 in information about it. */
2980 iv_number_of_iterations (loop, at, condition, desc);
2983 /* Finds a simple exit of LOOP and stores its description into DESC. */
2985 void
2986 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2988 unsigned i;
2989 basic_block *body;
2990 edge e;
2991 struct niter_desc act;
2992 bool any = false;
2993 edge_iterator ei;
2995 desc->simple_p = false;
2996 body = get_loop_body (loop);
2998 for (i = 0; i < loop->num_nodes; i++)
3000 FOR_EACH_EDGE (e, ei, body[i]->succs)
3002 if (flow_bb_inside_loop_p (loop, e->dest))
3003 continue;
3005 check_simple_exit (loop, e, &act);
3006 if (!act.simple_p)
3007 continue;
3009 if (!any)
3010 any = true;
3011 else
3013 /* Prefer constant iterations; the less the better. */
3014 if (!act.const_iter
3015 || (desc->const_iter && act.niter >= desc->niter))
3016 continue;
3018 /* Also if the actual exit may be infinite, while the old one
3019 not, prefer the old one. */
3020 if (act.infinite && !desc->infinite)
3021 continue;
3024 *desc = act;
3028 if (dump_file)
3030 if (desc->simple_p)
3032 fprintf (dump_file, "Loop %d is simple:\n", loop->num);
3033 fprintf (dump_file, " simple exit %d -> %d\n",
3034 desc->out_edge->src->index,
3035 desc->out_edge->dest->index);
3036 if (desc->assumptions)
3038 fprintf (dump_file, " assumptions: ");
3039 print_rtl (dump_file, desc->assumptions);
3040 fprintf (dump_file, "\n");
3042 if (desc->noloop_assumptions)
3044 fprintf (dump_file, " does not roll if: ");
3045 print_rtl (dump_file, desc->noloop_assumptions);
3046 fprintf (dump_file, "\n");
3048 if (desc->infinite)
3050 fprintf (dump_file, " infinite if: ");
3051 print_rtl (dump_file, desc->infinite);
3052 fprintf (dump_file, "\n");
3055 fprintf (dump_file, " number of iterations: ");
3056 print_rtl (dump_file, desc->niter_expr);
3057 fprintf (dump_file, "\n");
3059 fprintf (dump_file, " upper bound: %li\n",
3060 (long)get_max_loop_iterations_int (loop));
3061 fprintf (dump_file, " realistic bound: %li\n",
3062 (long)get_estimated_loop_iterations_int (loop));
3064 else
3065 fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
3068 free (body);
3071 /* Creates a simple loop description of LOOP if it was not computed
3072 already. */
3074 struct niter_desc *
3075 get_simple_loop_desc (struct loop *loop)
3077 struct niter_desc *desc = simple_loop_desc (loop);
3079 if (desc)
3080 return desc;
3082 /* At least desc->infinite is not always initialized by
3083 find_simple_loop_exit. */
3084 desc = ggc_cleared_alloc<niter_desc> ();
3085 iv_analysis_loop_init (loop);
3086 find_simple_exit (loop, desc);
3087 loop->simple_loop_desc = desc;
3089 if (desc->simple_p && (desc->assumptions || desc->infinite))
3091 const char *wording;
3093 /* Assume that no overflow happens and that the loop is finite.
3094 We already warned at the tree level if we ran optimizations there. */
3095 if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
3097 if (desc->infinite)
3099 wording =
3100 flag_unsafe_loop_optimizations
3101 ? N_("assuming that the loop is not infinite")
3102 : N_("cannot optimize possibly infinite loops");
3103 warning (OPT_Wunsafe_loop_optimizations, "%s",
3104 gettext (wording));
3106 if (desc->assumptions)
3108 wording =
3109 flag_unsafe_loop_optimizations
3110 ? N_("assuming that the loop counter does not overflow")
3111 : N_("cannot optimize loop, the loop counter may overflow");
3112 warning (OPT_Wunsafe_loop_optimizations, "%s",
3113 gettext (wording));
3117 if (flag_unsafe_loop_optimizations)
3119 desc->assumptions = NULL_RTX;
3120 desc->infinite = NULL_RTX;
3124 return desc;
3127 /* Releases simple loop description for LOOP. */
3129 void
3130 free_simple_loop_desc (struct loop *loop)
3132 struct niter_desc *desc = simple_loop_desc (loop);
3134 if (!desc)
3135 return;
3137 ggc_free (desc);
3138 loop->simple_loop_desc = NULL;