]> git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/loop-iv.c
c++: Handle multiple aggregate overloads [PR95319].
[thirdparty/gcc.git] / gcc / loop-iv.c
1 /* Rtl-level induction variable analysis.
2 Copyright (C) 2004-2020 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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.
24
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.
29
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.
35
36 The available functions are:
37
38 iv_analyze (insn, mode, reg, iv): Stores the description of the induction
39 variable corresponding to the use of register REG in INSN to IV, given
40 that REG has mode MODE. Returns true if REG is an induction variable
41 in INSN. false otherwise. If a use of REG is not found in INSN,
42 the following insns are scanned (so that we may call this function
43 on insns returned by get_condition).
44 iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
45 corresponding to DEF, which is a register defined in INSN.
46 iv_analyze_expr (insn, mode, expr, iv): Stores to IV the description of iv
47 corresponding to expression EXPR evaluated at INSN. All registers used bu
48 EXPR must also be used in INSN. MODE is the mode of EXPR.
49 */
50
51 #include "config.h"
52 #include "system.h"
53 #include "coretypes.h"
54 #include "backend.h"
55 #include "rtl.h"
56 #include "df.h"
57 #include "memmodel.h"
58 #include "emit-rtl.h"
59 #include "diagnostic-core.h"
60 #include "cfgloop.h"
61 #include "intl.h"
62 #include "dumpfile.h"
63 #include "rtl-iter.h"
64 #include "tree-ssa-loop-niter.h"
65 #include "regs.h"
66 #include "function-abi.h"
67
68 /* Possible return values of iv_get_reaching_def. */
69
70 enum iv_grd_result
71 {
72 /* More than one reaching def, or reaching def that does not
73 dominate the use. */
74 GRD_INVALID,
75
76 /* The use is trivial invariant of the loop, i.e. is not changed
77 inside the loop. */
78 GRD_INVARIANT,
79
80 /* The use is reached by initial value and a value from the
81 previous iteration. */
82 GRD_MAYBE_BIV,
83
84 /* The use has single dominating def. */
85 GRD_SINGLE_DOM
86 };
87
88 /* Information about a biv. */
89
90 class biv_entry
91 {
92 public:
93 unsigned regno; /* The register of the biv. */
94 class rtx_iv iv; /* Value of the biv. */
95 };
96
97 static bool clean_slate = true;
98
99 static unsigned int iv_ref_table_size = 0;
100
101 /* Table of rtx_ivs indexed by the df_ref uid field. */
102 static class rtx_iv ** iv_ref_table;
103
104 /* Induction variable stored at the reference. */
105 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
106 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
107
108 /* The current loop. */
109
110 static class loop *current_loop;
111
112 /* Hashtable helper. */
113
114 struct biv_entry_hasher : free_ptr_hash <biv_entry>
115 {
116 typedef rtx_def *compare_type;
117 static inline hashval_t hash (const biv_entry *);
118 static inline bool equal (const biv_entry *, const rtx_def *);
119 };
120
121 /* Returns hash value for biv B. */
122
123 inline hashval_t
124 biv_entry_hasher::hash (const biv_entry *b)
125 {
126 return b->regno;
127 }
128
129 /* Compares biv B and register R. */
130
131 inline bool
132 biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r)
133 {
134 return b->regno == REGNO (r);
135 }
136
137 /* Bivs of the current loop. */
138
139 static hash_table<biv_entry_hasher> *bivs;
140
141 static bool iv_analyze_op (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);
142
143 /* Return the RTX code corresponding to the IV extend code EXTEND. */
144 static inline enum rtx_code
145 iv_extend_to_rtx_code (enum iv_extend_code extend)
146 {
147 switch (extend)
148 {
149 case IV_SIGN_EXTEND:
150 return SIGN_EXTEND;
151 case IV_ZERO_EXTEND:
152 return ZERO_EXTEND;
153 case IV_UNKNOWN_EXTEND:
154 return UNKNOWN;
155 }
156 gcc_unreachable ();
157 }
158
159 /* Dumps information about IV to FILE. */
160
161 extern void dump_iv_info (FILE *, class rtx_iv *);
162 void
163 dump_iv_info (FILE *file, class rtx_iv *iv)
164 {
165 if (!iv->base)
166 {
167 fprintf (file, "not simple");
168 return;
169 }
170
171 if (iv->step == const0_rtx
172 && !iv->first_special)
173 fprintf (file, "invariant ");
174
175 print_rtl (file, iv->base);
176 if (iv->step != const0_rtx)
177 {
178 fprintf (file, " + ");
179 print_rtl (file, iv->step);
180 fprintf (file, " * iteration");
181 }
182 fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
183
184 if (iv->mode != iv->extend_mode)
185 fprintf (file, " %s to %s",
186 rtx_name[iv_extend_to_rtx_code (iv->extend)],
187 GET_MODE_NAME (iv->extend_mode));
188
189 if (iv->mult != const1_rtx)
190 {
191 fprintf (file, " * ");
192 print_rtl (file, iv->mult);
193 }
194 if (iv->delta != const0_rtx)
195 {
196 fprintf (file, " + ");
197 print_rtl (file, iv->delta);
198 }
199 if (iv->first_special)
200 fprintf (file, " (first special)");
201 }
202
203 static void
204 check_iv_ref_table_size (void)
205 {
206 if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ())
207 {
208 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
209 iv_ref_table = XRESIZEVEC (class rtx_iv *, iv_ref_table, new_size);
210 memset (&iv_ref_table[iv_ref_table_size], 0,
211 (new_size - iv_ref_table_size) * sizeof (class rtx_iv *));
212 iv_ref_table_size = new_size;
213 }
214 }
215
216
217 /* Checks whether REG is a well-behaved register. */
218
219 static bool
220 simple_reg_p (rtx reg)
221 {
222 unsigned r;
223
224 if (GET_CODE (reg) == SUBREG)
225 {
226 if (!subreg_lowpart_p (reg))
227 return false;
228 reg = SUBREG_REG (reg);
229 }
230
231 if (!REG_P (reg))
232 return false;
233
234 r = REGNO (reg);
235 if (HARD_REGISTER_NUM_P (r))
236 return false;
237
238 if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
239 return false;
240
241 return true;
242 }
243
244 /* Clears the information about ivs stored in df. */
245
246 static void
247 clear_iv_info (void)
248 {
249 unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
250 class rtx_iv *iv;
251
252 check_iv_ref_table_size ();
253 for (i = 0; i < n_defs; i++)
254 {
255 iv = iv_ref_table[i];
256 if (iv)
257 {
258 free (iv);
259 iv_ref_table[i] = NULL;
260 }
261 }
262
263 bivs->empty ();
264 }
265
266
267 /* Prepare the data for an induction variable analysis of a LOOP. */
268
269 void
270 iv_analysis_loop_init (class loop *loop)
271 {
272 current_loop = loop;
273
274 /* Clear the information from the analysis of the previous loop. */
275 if (clean_slate)
276 {
277 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
278 bivs = new hash_table<biv_entry_hasher> (10);
279 clean_slate = false;
280 }
281 else
282 clear_iv_info ();
283
284 /* Get rid of the ud chains before processing the rescans. Then add
285 the problem back. */
286 df_remove_problem (df_chain);
287 df_process_deferred_rescans ();
288 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
289 df_chain_add_problem (DF_UD_CHAIN);
290 df_note_add_problem ();
291 df_analyze_loop (loop);
292 if (dump_file)
293 df_dump_region (dump_file);
294
295 check_iv_ref_table_size ();
296 }
297
298 /* Finds the definition of REG that dominates loop latch and stores
299 it to DEF. Returns false if there is not a single definition
300 dominating the latch. If REG has no definition in loop, DEF
301 is set to NULL and true is returned. */
302
303 static bool
304 latch_dominating_def (rtx reg, df_ref *def)
305 {
306 df_ref single_rd = NULL, adef;
307 unsigned regno = REGNO (reg);
308 class df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
309
310 for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
311 {
312 if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
313 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
314 continue;
315
316 /* More than one reaching definition. */
317 if (single_rd)
318 return false;
319
320 if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
321 return false;
322
323 single_rd = adef;
324 }
325
326 *def = single_rd;
327 return true;
328 }
329
330 /* Gets definition of REG reaching its use in INSN and stores it to DEF. */
331
332 static enum iv_grd_result
333 iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
334 {
335 df_ref use, adef;
336 basic_block def_bb, use_bb;
337 rtx_insn *def_insn;
338 bool dom_p;
339
340 *def = NULL;
341 if (!simple_reg_p (reg))
342 return GRD_INVALID;
343 if (GET_CODE (reg) == SUBREG)
344 reg = SUBREG_REG (reg);
345 gcc_assert (REG_P (reg));
346
347 use = df_find_use (insn, reg);
348 gcc_assert (use != NULL);
349
350 if (!DF_REF_CHAIN (use))
351 return GRD_INVARIANT;
352
353 /* More than one reaching def. */
354 if (DF_REF_CHAIN (use)->next)
355 return GRD_INVALID;
356
357 adef = DF_REF_CHAIN (use)->ref;
358
359 /* We do not handle setting only part of the register. */
360 if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
361 return GRD_INVALID;
362
363 def_insn = DF_REF_INSN (adef);
364 def_bb = DF_REF_BB (adef);
365 use_bb = BLOCK_FOR_INSN (insn);
366
367 if (use_bb == def_bb)
368 dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
369 else
370 dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
371
372 if (dom_p)
373 {
374 *def = adef;
375 return GRD_SINGLE_DOM;
376 }
377
378 /* The definition does not dominate the use. This is still OK if
379 this may be a use of a biv, i.e. if the def_bb dominates loop
380 latch. */
381 if (just_once_each_iteration_p (current_loop, def_bb))
382 return GRD_MAYBE_BIV;
383
384 return GRD_INVALID;
385 }
386
387 /* Sets IV to invariant CST in MODE. Always returns true (just for
388 consistency with other iv manipulation functions that may fail). */
389
390 static bool
391 iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)
392 {
393 iv->mode = mode;
394 iv->base = cst;
395 iv->step = const0_rtx;
396 iv->first_special = false;
397 iv->extend = IV_UNKNOWN_EXTEND;
398 iv->extend_mode = iv->mode;
399 iv->delta = const0_rtx;
400 iv->mult = const1_rtx;
401
402 return true;
403 }
404
405 /* Evaluates application of subreg to MODE on IV. */
406
407 static bool
408 iv_subreg (class rtx_iv *iv, scalar_int_mode mode)
409 {
410 /* If iv is invariant, just calculate the new value. */
411 if (iv->step == const0_rtx
412 && !iv->first_special)
413 {
414 rtx val = get_iv_value (iv, const0_rtx);
415 val = lowpart_subreg (mode, val,
416 iv->extend == IV_UNKNOWN_EXTEND
417 ? iv->mode : iv->extend_mode);
418
419 iv->base = val;
420 iv->extend = IV_UNKNOWN_EXTEND;
421 iv->mode = iv->extend_mode = mode;
422 iv->delta = const0_rtx;
423 iv->mult = const1_rtx;
424 return true;
425 }
426
427 if (iv->extend_mode == mode)
428 return true;
429
430 if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
431 return false;
432
433 iv->extend = IV_UNKNOWN_EXTEND;
434 iv->mode = mode;
435
436 iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
437 simplify_gen_binary (MULT, iv->extend_mode,
438 iv->base, iv->mult));
439 iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
440 iv->mult = const1_rtx;
441 iv->delta = const0_rtx;
442 iv->first_special = false;
443
444 return true;
445 }
446
447 /* Evaluates application of EXTEND to MODE on IV. */
448
449 static bool
450 iv_extend (class rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)
451 {
452 /* If iv is invariant, just calculate the new value. */
453 if (iv->step == const0_rtx
454 && !iv->first_special)
455 {
456 rtx val = get_iv_value (iv, const0_rtx);
457 if (iv->extend_mode != iv->mode
458 && iv->extend != IV_UNKNOWN_EXTEND
459 && iv->extend != extend)
460 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
461 val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
462 val,
463 iv->extend == extend
464 ? iv->extend_mode : iv->mode);
465 iv->base = val;
466 iv->extend = IV_UNKNOWN_EXTEND;
467 iv->mode = iv->extend_mode = mode;
468 iv->delta = const0_rtx;
469 iv->mult = const1_rtx;
470 return true;
471 }
472
473 if (mode != iv->extend_mode)
474 return false;
475
476 if (iv->extend != IV_UNKNOWN_EXTEND
477 && iv->extend != extend)
478 return false;
479
480 iv->extend = extend;
481
482 return true;
483 }
484
485 /* Evaluates negation of IV. */
486
487 static bool
488 iv_neg (class rtx_iv *iv)
489 {
490 if (iv->extend == IV_UNKNOWN_EXTEND)
491 {
492 iv->base = simplify_gen_unary (NEG, iv->extend_mode,
493 iv->base, iv->extend_mode);
494 iv->step = simplify_gen_unary (NEG, iv->extend_mode,
495 iv->step, iv->extend_mode);
496 }
497 else
498 {
499 iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
500 iv->delta, iv->extend_mode);
501 iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
502 iv->mult, iv->extend_mode);
503 }
504
505 return true;
506 }
507
508 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
509
510 static bool
511 iv_add (class rtx_iv *iv0, class rtx_iv *iv1, enum rtx_code op)
512 {
513 scalar_int_mode mode;
514 rtx arg;
515
516 /* Extend the constant to extend_mode of the other operand if necessary. */
517 if (iv0->extend == IV_UNKNOWN_EXTEND
518 && iv0->mode == iv0->extend_mode
519 && iv0->step == const0_rtx
520 && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
521 {
522 iv0->extend_mode = iv1->extend_mode;
523 iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
524 iv0->base, iv0->mode);
525 }
526 if (iv1->extend == IV_UNKNOWN_EXTEND
527 && iv1->mode == iv1->extend_mode
528 && iv1->step == const0_rtx
529 && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
530 {
531 iv1->extend_mode = iv0->extend_mode;
532 iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
533 iv1->base, iv1->mode);
534 }
535
536 mode = iv0->extend_mode;
537 if (mode != iv1->extend_mode)
538 return false;
539
540 if (iv0->extend == IV_UNKNOWN_EXTEND
541 && iv1->extend == IV_UNKNOWN_EXTEND)
542 {
543 if (iv0->mode != iv1->mode)
544 return false;
545
546 iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
547 iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
548
549 return true;
550 }
551
552 /* Handle addition of constant. */
553 if (iv1->extend == IV_UNKNOWN_EXTEND
554 && iv1->mode == mode
555 && iv1->step == const0_rtx)
556 {
557 iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
558 return true;
559 }
560
561 if (iv0->extend == IV_UNKNOWN_EXTEND
562 && iv0->mode == mode
563 && iv0->step == const0_rtx)
564 {
565 arg = iv0->base;
566 *iv0 = *iv1;
567 if (op == MINUS
568 && !iv_neg (iv0))
569 return false;
570
571 iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
572 return true;
573 }
574
575 return false;
576 }
577
578 /* Evaluates multiplication of IV by constant CST. */
579
580 static bool
581 iv_mult (class rtx_iv *iv, rtx mby)
582 {
583 scalar_int_mode mode = iv->extend_mode;
584
585 if (GET_MODE (mby) != VOIDmode
586 && GET_MODE (mby) != mode)
587 return false;
588
589 if (iv->extend == IV_UNKNOWN_EXTEND)
590 {
591 iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
592 iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
593 }
594 else
595 {
596 iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
597 iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
598 }
599
600 return true;
601 }
602
603 /* Evaluates shift of IV by constant CST. */
604
605 static bool
606 iv_shift (class rtx_iv *iv, rtx mby)
607 {
608 scalar_int_mode mode = iv->extend_mode;
609
610 if (GET_MODE (mby) != VOIDmode
611 && GET_MODE (mby) != mode)
612 return false;
613
614 if (iv->extend == IV_UNKNOWN_EXTEND)
615 {
616 iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
617 iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
618 }
619 else
620 {
621 iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
622 iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
623 }
624
625 return true;
626 }
627
628 /* The recursive part of get_biv_step. Gets the value of the single value
629 defined by DEF wrto initial value of REG inside loop, in shape described
630 at get_biv_step. */
631
632 static bool
633 get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg,
634 rtx *inner_step, scalar_int_mode *inner_mode,
635 enum iv_extend_code *extend,
636 rtx *outer_step)
637 {
638 rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
639 rtx next, nextr;
640 enum rtx_code code;
641 rtx_insn *insn = DF_REF_INSN (def);
642 df_ref next_def;
643 enum iv_grd_result res;
644
645 set = single_set (insn);
646 if (!set)
647 return false;
648
649 rhs = find_reg_equal_equiv_note (insn);
650 if (rhs)
651 rhs = XEXP (rhs, 0);
652 else
653 rhs = SET_SRC (set);
654
655 code = GET_CODE (rhs);
656 switch (code)
657 {
658 case SUBREG:
659 case REG:
660 next = rhs;
661 break;
662
663 case PLUS:
664 case MINUS:
665 op0 = XEXP (rhs, 0);
666 op1 = XEXP (rhs, 1);
667
668 if (code == PLUS && CONSTANT_P (op0))
669 std::swap (op0, op1);
670
671 if (!simple_reg_p (op0)
672 || !CONSTANT_P (op1))
673 return false;
674
675 if (GET_MODE (rhs) != outer_mode)
676 {
677 /* ppc64 uses expressions like
678
679 (set x:SI (plus:SI (subreg:SI y:DI) 1)).
680
681 this is equivalent to
682
683 (set x':DI (plus:DI y:DI 1))
684 (set x:SI (subreg:SI (x':DI)). */
685 if (GET_CODE (op0) != SUBREG)
686 return false;
687 if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
688 return false;
689 }
690
691 next = op0;
692 break;
693
694 case SIGN_EXTEND:
695 case ZERO_EXTEND:
696 if (GET_MODE (rhs) != outer_mode)
697 return false;
698
699 op0 = XEXP (rhs, 0);
700 if (!simple_reg_p (op0))
701 return false;
702
703 next = op0;
704 break;
705
706 default:
707 return false;
708 }
709
710 if (GET_CODE (next) == SUBREG)
711 {
712 if (!subreg_lowpart_p (next))
713 return false;
714
715 nextr = SUBREG_REG (next);
716 if (GET_MODE (nextr) != outer_mode)
717 return false;
718 }
719 else
720 nextr = next;
721
722 res = iv_get_reaching_def (insn, nextr, &next_def);
723
724 if (res == GRD_INVALID || res == GRD_INVARIANT)
725 return false;
726
727 if (res == GRD_MAYBE_BIV)
728 {
729 if (!rtx_equal_p (nextr, reg))
730 return false;
731
732 *inner_step = const0_rtx;
733 *extend = IV_UNKNOWN_EXTEND;
734 *inner_mode = outer_mode;
735 *outer_step = const0_rtx;
736 }
737 else if (!get_biv_step_1 (next_def, outer_mode, reg,
738 inner_step, inner_mode, extend,
739 outer_step))
740 return false;
741
742 if (GET_CODE (next) == SUBREG)
743 {
744 scalar_int_mode amode;
745 if (!is_a <scalar_int_mode> (GET_MODE (next), &amode)
746 || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
747 return false;
748
749 *inner_mode = amode;
750 *inner_step = simplify_gen_binary (PLUS, outer_mode,
751 *inner_step, *outer_step);
752 *outer_step = const0_rtx;
753 *extend = IV_UNKNOWN_EXTEND;
754 }
755
756 switch (code)
757 {
758 case REG:
759 case SUBREG:
760 break;
761
762 case PLUS:
763 case MINUS:
764 if (*inner_mode == outer_mode
765 /* See comment in previous switch. */
766 || GET_MODE (rhs) != outer_mode)
767 *inner_step = simplify_gen_binary (code, outer_mode,
768 *inner_step, op1);
769 else
770 *outer_step = simplify_gen_binary (code, outer_mode,
771 *outer_step, op1);
772 break;
773
774 case SIGN_EXTEND:
775 case ZERO_EXTEND:
776 gcc_assert (GET_MODE (op0) == *inner_mode
777 && *extend == IV_UNKNOWN_EXTEND
778 && *outer_step == const0_rtx);
779
780 *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
781 break;
782
783 default:
784 return false;
785 }
786
787 return true;
788 }
789
790 /* Gets the operation on register REG inside loop, in shape
791
792 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
793
794 If the operation cannot be described in this shape, return false.
795 LAST_DEF is the definition of REG that dominates loop latch. */
796
797 static bool
798 get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
799 rtx *inner_step, scalar_int_mode *inner_mode,
800 enum iv_extend_code *extend, rtx *outer_step)
801 {
802 if (!get_biv_step_1 (last_def, outer_mode, reg,
803 inner_step, inner_mode, extend,
804 outer_step))
805 return false;
806
807 gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
808 gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx);
809
810 return true;
811 }
812
813 /* Records information that DEF is induction variable IV. */
814
815 static void
816 record_iv (df_ref def, class rtx_iv *iv)
817 {
818 class rtx_iv *recorded_iv = XNEW (class rtx_iv);
819
820 *recorded_iv = *iv;
821 check_iv_ref_table_size ();
822 DF_REF_IV_SET (def, recorded_iv);
823 }
824
825 /* If DEF was already analyzed for bivness, store the description of the biv to
826 IV and return true. Otherwise return false. */
827
828 static bool
829 analyzed_for_bivness_p (rtx def, class rtx_iv *iv)
830 {
831 class biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
832
833 if (!biv)
834 return false;
835
836 *iv = biv->iv;
837 return true;
838 }
839
840 static void
841 record_biv (rtx def, class rtx_iv *iv)
842 {
843 class biv_entry *biv = XNEW (class biv_entry);
844 biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
845
846 biv->regno = REGNO (def);
847 biv->iv = *iv;
848 gcc_assert (!*slot);
849 *slot = biv;
850 }
851
852 /* Determines whether DEF is a biv and if so, stores its description
853 to *IV. OUTER_MODE is the mode of DEF. */
854
855 static bool
856 iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)
857 {
858 rtx inner_step, outer_step;
859 scalar_int_mode inner_mode;
860 enum iv_extend_code extend;
861 df_ref last_def;
862
863 if (dump_file)
864 {
865 fprintf (dump_file, "Analyzing ");
866 print_rtl (dump_file, def);
867 fprintf (dump_file, " for bivness.\n");
868 }
869
870 if (!REG_P (def))
871 {
872 if (!CONSTANT_P (def))
873 return false;
874
875 return iv_constant (iv, outer_mode, def);
876 }
877
878 if (!latch_dominating_def (def, &last_def))
879 {
880 if (dump_file)
881 fprintf (dump_file, " not simple.\n");
882 return false;
883 }
884
885 if (!last_def)
886 return iv_constant (iv, outer_mode, def);
887
888 if (analyzed_for_bivness_p (def, iv))
889 {
890 if (dump_file)
891 fprintf (dump_file, " already analysed.\n");
892 return iv->base != NULL_RTX;
893 }
894
895 if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
896 &extend, &outer_step))
897 {
898 iv->base = NULL_RTX;
899 goto end;
900 }
901
902 /* Loop transforms base to es (base + inner_step) + outer_step,
903 where es means extend of subreg between inner_mode and outer_mode.
904 The corresponding induction variable is
905
906 es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
907
908 iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
909 iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
910 iv->mode = inner_mode;
911 iv->extend_mode = outer_mode;
912 iv->extend = extend;
913 iv->mult = const1_rtx;
914 iv->delta = outer_step;
915 iv->first_special = inner_mode != outer_mode;
916
917 end:
918 if (dump_file)
919 {
920 fprintf (dump_file, " ");
921 dump_iv_info (dump_file, iv);
922 fprintf (dump_file, "\n");
923 }
924
925 record_biv (def, iv);
926 return iv->base != NULL_RTX;
927 }
928
929 /* Analyzes expression RHS used at INSN and stores the result to *IV.
930 The mode of the induction variable is MODE. */
931
932 bool
933 iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
934 class rtx_iv *iv)
935 {
936 rtx mby = NULL_RTX;
937 rtx op0 = NULL_RTX, op1 = NULL_RTX;
938 class rtx_iv iv0, iv1;
939 enum rtx_code code = GET_CODE (rhs);
940 scalar_int_mode omode = mode;
941
942 iv->base = NULL_RTX;
943 iv->step = NULL_RTX;
944
945 gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
946
947 if (CONSTANT_P (rhs)
948 || REG_P (rhs)
949 || code == SUBREG)
950 return iv_analyze_op (insn, mode, rhs, iv);
951
952 switch (code)
953 {
954 case REG:
955 op0 = rhs;
956 break;
957
958 case SIGN_EXTEND:
959 case ZERO_EXTEND:
960 case NEG:
961 op0 = XEXP (rhs, 0);
962 /* We don't know how many bits there are in a sign-extended constant. */
963 if (!is_a <scalar_int_mode> (GET_MODE (op0), &omode))
964 return false;
965 break;
966
967 case PLUS:
968 case MINUS:
969 op0 = XEXP (rhs, 0);
970 op1 = XEXP (rhs, 1);
971 break;
972
973 case MULT:
974 op0 = XEXP (rhs, 0);
975 mby = XEXP (rhs, 1);
976 if (!CONSTANT_P (mby))
977 std::swap (op0, mby);
978 if (!CONSTANT_P (mby))
979 return false;
980 break;
981
982 case ASHIFT:
983 op0 = XEXP (rhs, 0);
984 mby = XEXP (rhs, 1);
985 if (!CONSTANT_P (mby))
986 return false;
987 break;
988
989 default:
990 return false;
991 }
992
993 if (op0
994 && !iv_analyze_expr (insn, omode, op0, &iv0))
995 return false;
996
997 if (op1
998 && !iv_analyze_expr (insn, omode, op1, &iv1))
999 return false;
1000
1001 switch (code)
1002 {
1003 case SIGN_EXTEND:
1004 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1005 return false;
1006 break;
1007
1008 case ZERO_EXTEND:
1009 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1010 return false;
1011 break;
1012
1013 case NEG:
1014 if (!iv_neg (&iv0))
1015 return false;
1016 break;
1017
1018 case PLUS:
1019 case MINUS:
1020 if (!iv_add (&iv0, &iv1, code))
1021 return false;
1022 break;
1023
1024 case MULT:
1025 if (!iv_mult (&iv0, mby))
1026 return false;
1027 break;
1028
1029 case ASHIFT:
1030 if (!iv_shift (&iv0, mby))
1031 return false;
1032 break;
1033
1034 default:
1035 break;
1036 }
1037
1038 *iv = iv0;
1039 return iv->base != NULL_RTX;
1040 }
1041
1042 /* Analyzes iv DEF and stores the result to *IV. */
1043
1044 static bool
1045 iv_analyze_def (df_ref def, class rtx_iv *iv)
1046 {
1047 rtx_insn *insn = DF_REF_INSN (def);
1048 rtx reg = DF_REF_REG (def);
1049 rtx set, rhs;
1050
1051 if (dump_file)
1052 {
1053 fprintf (dump_file, "Analyzing def of ");
1054 print_rtl (dump_file, reg);
1055 fprintf (dump_file, " in insn ");
1056 print_rtl_single (dump_file, insn);
1057 }
1058
1059 check_iv_ref_table_size ();
1060 if (DF_REF_IV (def))
1061 {
1062 if (dump_file)
1063 fprintf (dump_file, " already analysed.\n");
1064 *iv = *DF_REF_IV (def);
1065 return iv->base != NULL_RTX;
1066 }
1067
1068 iv->base = NULL_RTX;
1069 iv->step = NULL_RTX;
1070
1071 scalar_int_mode mode;
1072 if (!REG_P (reg) || !is_a <scalar_int_mode> (GET_MODE (reg), &mode))
1073 return false;
1074
1075 set = single_set (insn);
1076 if (!set)
1077 return false;
1078
1079 if (!REG_P (SET_DEST (set)))
1080 return false;
1081
1082 gcc_assert (SET_DEST (set) == reg);
1083 rhs = find_reg_equal_equiv_note (insn);
1084 if (rhs)
1085 rhs = XEXP (rhs, 0);
1086 else
1087 rhs = SET_SRC (set);
1088
1089 iv_analyze_expr (insn, mode, rhs, iv);
1090 record_iv (def, iv);
1091
1092 if (dump_file)
1093 {
1094 print_rtl (dump_file, reg);
1095 fprintf (dump_file, " in insn ");
1096 print_rtl_single (dump_file, insn);
1097 fprintf (dump_file, " is ");
1098 dump_iv_info (dump_file, iv);
1099 fprintf (dump_file, "\n");
1100 }
1101
1102 return iv->base != NULL_RTX;
1103 }
1104
1105 /* Analyzes operand OP of INSN and stores the result to *IV. MODE is the
1106 mode of OP. */
1107
1108 static bool
1109 iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, class rtx_iv *iv)
1110 {
1111 df_ref def = NULL;
1112 enum iv_grd_result res;
1113
1114 if (dump_file)
1115 {
1116 fprintf (dump_file, "Analyzing operand ");
1117 print_rtl (dump_file, op);
1118 fprintf (dump_file, " of insn ");
1119 print_rtl_single (dump_file, insn);
1120 }
1121
1122 if (function_invariant_p (op))
1123 res = GRD_INVARIANT;
1124 else if (GET_CODE (op) == SUBREG)
1125 {
1126 scalar_int_mode inner_mode;
1127 if (!subreg_lowpart_p (op)
1128 || !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op)), &inner_mode))
1129 return false;
1130
1131 if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op), iv))
1132 return false;
1133
1134 return iv_subreg (iv, mode);
1135 }
1136 else
1137 {
1138 res = iv_get_reaching_def (insn, op, &def);
1139 if (res == GRD_INVALID)
1140 {
1141 if (dump_file)
1142 fprintf (dump_file, " not simple.\n");
1143 return false;
1144 }
1145 }
1146
1147 if (res == GRD_INVARIANT)
1148 {
1149 iv_constant (iv, mode, op);
1150
1151 if (dump_file)
1152 {
1153 fprintf (dump_file, " ");
1154 dump_iv_info (dump_file, iv);
1155 fprintf (dump_file, "\n");
1156 }
1157 return true;
1158 }
1159
1160 if (res == GRD_MAYBE_BIV)
1161 return iv_analyze_biv (mode, op, iv);
1162
1163 return iv_analyze_def (def, iv);
1164 }
1165
1166 /* Analyzes value VAL at INSN and stores the result to *IV. MODE is the
1167 mode of VAL. */
1168
1169 bool
1170 iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, class rtx_iv *iv)
1171 {
1172 rtx reg;
1173
1174 /* We must find the insn in that val is used, so that we get to UD chains.
1175 Since the function is sometimes called on result of get_condition,
1176 this does not necessarily have to be directly INSN; scan also the
1177 following insns. */
1178 if (simple_reg_p (val))
1179 {
1180 if (GET_CODE (val) == SUBREG)
1181 reg = SUBREG_REG (val);
1182 else
1183 reg = val;
1184
1185 while (!df_find_use (insn, reg))
1186 insn = NEXT_INSN (insn);
1187 }
1188
1189 return iv_analyze_op (insn, mode, val, iv);
1190 }
1191
1192 /* Analyzes definition of DEF in INSN and stores the result to IV. */
1193
1194 bool
1195 iv_analyze_result (rtx_insn *insn, rtx def, class rtx_iv *iv)
1196 {
1197 df_ref adef;
1198
1199 adef = df_find_def (insn, def);
1200 if (!adef)
1201 return false;
1202
1203 return iv_analyze_def (adef, iv);
1204 }
1205
1206 /* Checks whether definition of register REG in INSN is a basic induction
1207 variable. MODE is the mode of REG.
1208
1209 IV analysis must have been initialized (via a call to
1210 iv_analysis_loop_init) for this function to produce a result. */
1211
1212 bool
1213 biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)
1214 {
1215 class rtx_iv iv;
1216 df_ref def, last_def;
1217
1218 if (!simple_reg_p (reg))
1219 return false;
1220
1221 def = df_find_def (insn, reg);
1222 gcc_assert (def != NULL);
1223 if (!latch_dominating_def (reg, &last_def))
1224 return false;
1225 if (last_def != def)
1226 return false;
1227
1228 if (!iv_analyze_biv (mode, reg, &iv))
1229 return false;
1230
1231 return iv.step != const0_rtx;
1232 }
1233
1234 /* Calculates value of IV at ITERATION-th iteration. */
1235
1236 rtx
1237 get_iv_value (class rtx_iv *iv, rtx iteration)
1238 {
1239 rtx val;
1240
1241 /* We would need to generate some if_then_else patterns, and so far
1242 it is not needed anywhere. */
1243 gcc_assert (!iv->first_special);
1244
1245 if (iv->step != const0_rtx && iteration != const0_rtx)
1246 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1247 simplify_gen_binary (MULT, iv->extend_mode,
1248 iv->step, iteration));
1249 else
1250 val = iv->base;
1251
1252 if (iv->extend_mode == iv->mode)
1253 return val;
1254
1255 val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1256
1257 if (iv->extend == IV_UNKNOWN_EXTEND)
1258 return val;
1259
1260 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1261 iv->extend_mode, val, iv->mode);
1262 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1263 simplify_gen_binary (MULT, iv->extend_mode,
1264 iv->mult, val));
1265
1266 return val;
1267 }
1268
1269 /* Free the data for an induction variable analysis. */
1270
1271 void
1272 iv_analysis_done (void)
1273 {
1274 if (!clean_slate)
1275 {
1276 clear_iv_info ();
1277 clean_slate = true;
1278 df_finish_pass (true);
1279 delete bivs;
1280 bivs = NULL;
1281 free (iv_ref_table);
1282 iv_ref_table = NULL;
1283 iv_ref_table_size = 0;
1284 }
1285 }
1286
1287 /* Computes inverse to X modulo (1 << MOD). */
1288
1289 static uint64_t
1290 inverse (uint64_t x, int mod)
1291 {
1292 uint64_t mask =
1293 ((uint64_t) 1 << (mod - 1) << 1) - 1;
1294 uint64_t rslt = 1;
1295 int i;
1296
1297 for (i = 0; i < mod - 1; i++)
1298 {
1299 rslt = (rslt * x) & mask;
1300 x = (x * x) & mask;
1301 }
1302
1303 return rslt;
1304 }
1305
1306 /* Checks whether any register in X is in set ALT. */
1307
1308 static bool
1309 altered_reg_used (const_rtx x, bitmap alt)
1310 {
1311 subrtx_iterator::array_type array;
1312 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
1313 {
1314 const_rtx x = *iter;
1315 if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x)))
1316 return true;
1317 }
1318 return false;
1319 }
1320
1321 /* Marks registers altered by EXPR in set ALT. */
1322
1323 static void
1324 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1325 {
1326 if (GET_CODE (expr) == SUBREG)
1327 expr = SUBREG_REG (expr);
1328 if (!REG_P (expr))
1329 return;
1330
1331 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1332 }
1333
1334 /* Checks whether RHS is simple enough to process. */
1335
1336 static bool
1337 simple_rhs_p (rtx rhs)
1338 {
1339 rtx op0, op1;
1340
1341 if (function_invariant_p (rhs)
1342 || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1343 return true;
1344
1345 switch (GET_CODE (rhs))
1346 {
1347 case PLUS:
1348 case MINUS:
1349 case AND:
1350 op0 = XEXP (rhs, 0);
1351 op1 = XEXP (rhs, 1);
1352 /* Allow reg OP const and reg OP reg. */
1353 if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1354 && !function_invariant_p (op0))
1355 return false;
1356 if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1357 && !function_invariant_p (op1))
1358 return false;
1359
1360 return true;
1361
1362 case ASHIFT:
1363 case ASHIFTRT:
1364 case LSHIFTRT:
1365 case MULT:
1366 op0 = XEXP (rhs, 0);
1367 op1 = XEXP (rhs, 1);
1368 /* Allow reg OP const. */
1369 if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1370 return false;
1371 if (!function_invariant_p (op1))
1372 return false;
1373
1374 return true;
1375
1376 default:
1377 return false;
1378 }
1379 }
1380
1381 /* If REGNO has a single definition, return its known value, otherwise return
1382 null. */
1383
1384 static rtx
1385 find_single_def_src (unsigned int regno)
1386 {
1387 rtx src = NULL_RTX;
1388
1389 /* Don't look through unbounded number of single definition REG copies,
1390 there might be loops for sources with uninitialized variables. */
1391 for (int cnt = 0; cnt < 128; cnt++)
1392 {
1393 df_ref adef = DF_REG_DEF_CHAIN (regno);
1394 if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1395 || DF_REF_IS_ARTIFICIAL (adef))
1396 return NULL_RTX;
1397
1398 rtx set = single_set (DF_REF_INSN (adef));
1399 if (set == NULL || !REG_P (SET_DEST (set))
1400 || REGNO (SET_DEST (set)) != regno)
1401 return NULL_RTX;
1402
1403 rtx note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1404 if (note && function_invariant_p (XEXP (note, 0)))
1405 {
1406 src = XEXP (note, 0);
1407 break;
1408 }
1409 src = SET_SRC (set);
1410
1411 if (REG_P (src))
1412 {
1413 regno = REGNO (src);
1414 continue;
1415 }
1416 break;
1417 }
1418 if (!function_invariant_p (src))
1419 return NULL_RTX;
1420
1421 return src;
1422 }
1423
1424 /* If any registers in *EXPR that have a single definition, try to replace
1425 them with the known-equivalent values. */
1426
1427 static void
1428 replace_single_def_regs (rtx *expr)
1429 {
1430 subrtx_var_iterator::array_type array;
1431 repeat:
1432 FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)
1433 {
1434 rtx x = *iter;
1435 if (REG_P (x))
1436 if (rtx new_x = find_single_def_src (REGNO (x)))
1437 {
1438 *expr = simplify_replace_rtx (*expr, x, new_x);
1439 goto repeat;
1440 }
1441 }
1442 }
1443
1444 /* A subroutine of simplify_using_initial_values, this function examines INSN
1445 to see if it contains a suitable set that we can use to make a replacement.
1446 If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1447 the set; return false otherwise. */
1448
1449 static bool
1450 suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src)
1451 {
1452 rtx set = single_set (insn);
1453 rtx lhs = NULL_RTX, rhs;
1454
1455 if (!set)
1456 return false;
1457
1458 lhs = SET_DEST (set);
1459 if (!REG_P (lhs))
1460 return false;
1461
1462 rhs = find_reg_equal_equiv_note (insn);
1463 if (rhs)
1464 rhs = XEXP (rhs, 0);
1465 else
1466 rhs = SET_SRC (set);
1467
1468 if (!simple_rhs_p (rhs))
1469 return false;
1470
1471 *dest = lhs;
1472 *src = rhs;
1473 return true;
1474 }
1475
1476 /* Using the data returned by suitable_set_for_replacement, replace DEST
1477 with SRC in *EXPR and return the new expression. Also call
1478 replace_single_def_regs if the replacement changed something. */
1479 static void
1480 replace_in_expr (rtx *expr, rtx dest, rtx src)
1481 {
1482 rtx old = *expr;
1483 *expr = simplify_replace_rtx (*expr, dest, src);
1484 if (old == *expr)
1485 return;
1486 replace_single_def_regs (expr);
1487 }
1488
1489 /* Checks whether A implies B. */
1490
1491 static bool
1492 implies_p (rtx a, rtx b)
1493 {
1494 rtx op0, op1, opb0, opb1;
1495 machine_mode mode;
1496
1497 if (rtx_equal_p (a, b))
1498 return true;
1499
1500 if (GET_CODE (a) == EQ)
1501 {
1502 op0 = XEXP (a, 0);
1503 op1 = XEXP (a, 1);
1504
1505 if (REG_P (op0)
1506 || (GET_CODE (op0) == SUBREG
1507 && REG_P (SUBREG_REG (op0))))
1508 {
1509 rtx r = simplify_replace_rtx (b, op0, op1);
1510 if (r == const_true_rtx)
1511 return true;
1512 }
1513
1514 if (REG_P (op1)
1515 || (GET_CODE (op1) == SUBREG
1516 && REG_P (SUBREG_REG (op1))))
1517 {
1518 rtx r = simplify_replace_rtx (b, op1, op0);
1519 if (r == const_true_rtx)
1520 return true;
1521 }
1522 }
1523
1524 if (b == const_true_rtx)
1525 return true;
1526
1527 if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1528 && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1529 || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1530 && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1531 return false;
1532
1533 op0 = XEXP (a, 0);
1534 op1 = XEXP (a, 1);
1535 opb0 = XEXP (b, 0);
1536 opb1 = XEXP (b, 1);
1537
1538 mode = GET_MODE (op0);
1539 if (mode != GET_MODE (opb0))
1540 mode = VOIDmode;
1541 else if (mode == VOIDmode)
1542 {
1543 mode = GET_MODE (op1);
1544 if (mode != GET_MODE (opb1))
1545 mode = VOIDmode;
1546 }
1547
1548 /* A < B implies A + 1 <= B. */
1549 if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1550 && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1551 {
1552
1553 if (GET_CODE (a) == GT)
1554 std::swap (op0, op1);
1555
1556 if (GET_CODE (b) == GE)
1557 std::swap (opb0, opb1);
1558
1559 if (SCALAR_INT_MODE_P (mode)
1560 && rtx_equal_p (op1, opb1)
1561 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1562 return true;
1563 return false;
1564 }
1565
1566 /* A < B or A > B imply A != B. TODO: Likewise
1567 A + n < B implies A != B + n if neither wraps. */
1568 if (GET_CODE (b) == NE
1569 && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1570 || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1571 {
1572 if (rtx_equal_p (op0, opb0)
1573 && rtx_equal_p (op1, opb1))
1574 return true;
1575 }
1576
1577 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1578 if (GET_CODE (a) == NE
1579 && op1 == const0_rtx)
1580 {
1581 if ((GET_CODE (b) == GTU
1582 && opb1 == const0_rtx)
1583 || (GET_CODE (b) == GEU
1584 && opb1 == const1_rtx))
1585 return rtx_equal_p (op0, opb0);
1586 }
1587
1588 /* A != N is equivalent to A - (N + 1) <u -1. */
1589 if (GET_CODE (a) == NE
1590 && CONST_INT_P (op1)
1591 && GET_CODE (b) == LTU
1592 && opb1 == constm1_rtx
1593 && GET_CODE (opb0) == PLUS
1594 && CONST_INT_P (XEXP (opb0, 1))
1595 /* Avoid overflows. */
1596 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1597 != ((unsigned HOST_WIDE_INT)1
1598 << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1599 && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1600 return rtx_equal_p (op0, XEXP (opb0, 0));
1601
1602 /* Likewise, A != N implies A - N > 0. */
1603 if (GET_CODE (a) == NE
1604 && CONST_INT_P (op1))
1605 {
1606 if (GET_CODE (b) == GTU
1607 && GET_CODE (opb0) == PLUS
1608 && opb1 == const0_rtx
1609 && CONST_INT_P (XEXP (opb0, 1))
1610 /* Avoid overflows. */
1611 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1612 != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
1613 && rtx_equal_p (XEXP (opb0, 0), op0))
1614 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1615 if (GET_CODE (b) == GEU
1616 && GET_CODE (opb0) == PLUS
1617 && opb1 == const1_rtx
1618 && CONST_INT_P (XEXP (opb0, 1))
1619 /* Avoid overflows. */
1620 && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1621 != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
1622 && rtx_equal_p (XEXP (opb0, 0), op0))
1623 return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1624 }
1625
1626 /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1627 if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1628 && CONST_INT_P (op1)
1629 && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1630 || INTVAL (op1) >= 0)
1631 && GET_CODE (b) == LTU
1632 && CONST_INT_P (opb1)
1633 && rtx_equal_p (op0, opb0))
1634 return INTVAL (opb1) < 0;
1635
1636 return false;
1637 }
1638
1639 /* Canonicalizes COND so that
1640
1641 (1) Ensure that operands are ordered according to
1642 swap_commutative_operands_p.
1643 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1644 for GE, GEU, and LEU. */
1645
1646 rtx
1647 canon_condition (rtx cond)
1648 {
1649 rtx op0, op1;
1650 enum rtx_code code;
1651 machine_mode mode;
1652
1653 code = GET_CODE (cond);
1654 op0 = XEXP (cond, 0);
1655 op1 = XEXP (cond, 1);
1656
1657 if (swap_commutative_operands_p (op0, op1))
1658 {
1659 code = swap_condition (code);
1660 std::swap (op0, op1);
1661 }
1662
1663 mode = GET_MODE (op0);
1664 if (mode == VOIDmode)
1665 mode = GET_MODE (op1);
1666 gcc_assert (mode != VOIDmode);
1667
1668 if (CONST_SCALAR_INT_P (op1) && GET_MODE_CLASS (mode) != MODE_CC)
1669 {
1670 rtx_mode_t const_val (op1, mode);
1671
1672 switch (code)
1673 {
1674 case LE:
1675 if (wi::ne_p (const_val, wi::max_value (mode, SIGNED)))
1676 {
1677 code = LT;
1678 op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1679 }
1680 break;
1681
1682 case GE:
1683 if (wi::ne_p (const_val, wi::min_value (mode, SIGNED)))
1684 {
1685 code = GT;
1686 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1687 }
1688 break;
1689
1690 case LEU:
1691 if (wi::ne_p (const_val, -1))
1692 {
1693 code = LTU;
1694 op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1695 }
1696 break;
1697
1698 case GEU:
1699 if (wi::ne_p (const_val, 0))
1700 {
1701 code = GTU;
1702 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1703 }
1704 break;
1705
1706 default:
1707 break;
1708 }
1709 }
1710
1711 if (op0 != XEXP (cond, 0)
1712 || op1 != XEXP (cond, 1)
1713 || code != GET_CODE (cond)
1714 || GET_MODE (cond) != SImode)
1715 cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1716
1717 return cond;
1718 }
1719
1720 /* Reverses CONDition; returns NULL if we cannot. */
1721
1722 static rtx
1723 reversed_condition (rtx cond)
1724 {
1725 enum rtx_code reversed;
1726 reversed = reversed_comparison_code (cond, NULL);
1727 if (reversed == UNKNOWN)
1728 return NULL_RTX;
1729 else
1730 return gen_rtx_fmt_ee (reversed,
1731 GET_MODE (cond), XEXP (cond, 0),
1732 XEXP (cond, 1));
1733 }
1734
1735 /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1736 set of altered regs. */
1737
1738 void
1739 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1740 {
1741 rtx rev, reve, exp = *expr;
1742
1743 /* If some register gets altered later, we do not really speak about its
1744 value at the time of comparison. */
1745 if (altered && altered_reg_used (cond, altered))
1746 return;
1747
1748 if (GET_CODE (cond) == EQ
1749 && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1750 {
1751 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1752 return;
1753 }
1754
1755 if (!COMPARISON_P (exp))
1756 return;
1757
1758 rev = reversed_condition (cond);
1759 reve = reversed_condition (exp);
1760
1761 cond = canon_condition (cond);
1762 exp = canon_condition (exp);
1763 if (rev)
1764 rev = canon_condition (rev);
1765 if (reve)
1766 reve = canon_condition (reve);
1767
1768 if (rtx_equal_p (exp, cond))
1769 {
1770 *expr = const_true_rtx;
1771 return;
1772 }
1773
1774 if (rev && rtx_equal_p (exp, rev))
1775 {
1776 *expr = const0_rtx;
1777 return;
1778 }
1779
1780 if (implies_p (cond, exp))
1781 {
1782 *expr = const_true_rtx;
1783 return;
1784 }
1785
1786 if (reve && implies_p (cond, reve))
1787 {
1788 *expr = const0_rtx;
1789 return;
1790 }
1791
1792 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1793 be false. */
1794 if (rev && implies_p (exp, rev))
1795 {
1796 *expr = const0_rtx;
1797 return;
1798 }
1799
1800 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1801 if (rev && reve && implies_p (reve, rev))
1802 {
1803 *expr = const_true_rtx;
1804 return;
1805 }
1806
1807 /* We would like to have some other tests here. TODO. */
1808
1809 return;
1810 }
1811
1812 /* Use relationship between A and *B to eventually eliminate *B.
1813 OP is the operation we consider. */
1814
1815 static void
1816 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1817 {
1818 switch (op)
1819 {
1820 case AND:
1821 /* If A implies *B, we may replace *B by true. */
1822 if (implies_p (a, *b))
1823 *b = const_true_rtx;
1824 break;
1825
1826 case IOR:
1827 /* If *B implies A, we may replace *B by false. */
1828 if (implies_p (*b, a))
1829 *b = const0_rtx;
1830 break;
1831
1832 default:
1833 gcc_unreachable ();
1834 }
1835 }
1836
1837 /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1838 operation we consider. */
1839
1840 static void
1841 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1842 {
1843 rtx elt;
1844
1845 for (elt = tail; elt; elt = XEXP (elt, 1))
1846 eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1847 for (elt = tail; elt; elt = XEXP (elt, 1))
1848 eliminate_implied_condition (op, XEXP (elt, 0), head);
1849 }
1850
1851 /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1852 is a list, its elements are assumed to be combined using OP. */
1853
1854 static void
1855 simplify_using_initial_values (class loop *loop, enum rtx_code op, rtx *expr)
1856 {
1857 bool expression_valid;
1858 rtx head, tail, last_valid_expr;
1859 rtx_expr_list *cond_list;
1860 rtx_insn *insn;
1861 rtx neutral, aggr;
1862 regset altered, this_altered;
1863 edge e;
1864
1865 if (!*expr)
1866 return;
1867
1868 if (CONSTANT_P (*expr))
1869 return;
1870
1871 if (GET_CODE (*expr) == EXPR_LIST)
1872 {
1873 head = XEXP (*expr, 0);
1874 tail = XEXP (*expr, 1);
1875
1876 eliminate_implied_conditions (op, &head, tail);
1877
1878 switch (op)
1879 {
1880 case AND:
1881 neutral = const_true_rtx;
1882 aggr = const0_rtx;
1883 break;
1884
1885 case IOR:
1886 neutral = const0_rtx;
1887 aggr = const_true_rtx;
1888 break;
1889
1890 default:
1891 gcc_unreachable ();
1892 }
1893
1894 simplify_using_initial_values (loop, UNKNOWN, &head);
1895 if (head == aggr)
1896 {
1897 XEXP (*expr, 0) = aggr;
1898 XEXP (*expr, 1) = NULL_RTX;
1899 return;
1900 }
1901 else if (head == neutral)
1902 {
1903 *expr = tail;
1904 simplify_using_initial_values (loop, op, expr);
1905 return;
1906 }
1907 simplify_using_initial_values (loop, op, &tail);
1908
1909 if (tail && XEXP (tail, 0) == aggr)
1910 {
1911 *expr = tail;
1912 return;
1913 }
1914
1915 XEXP (*expr, 0) = head;
1916 XEXP (*expr, 1) = tail;
1917 return;
1918 }
1919
1920 gcc_assert (op == UNKNOWN);
1921
1922 replace_single_def_regs (expr);
1923 if (CONSTANT_P (*expr))
1924 return;
1925
1926 e = loop_preheader_edge (loop);
1927 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1928 return;
1929
1930 altered = ALLOC_REG_SET (&reg_obstack);
1931 this_altered = ALLOC_REG_SET (&reg_obstack);
1932
1933 expression_valid = true;
1934 last_valid_expr = *expr;
1935 cond_list = NULL;
1936 while (1)
1937 {
1938 insn = BB_END (e->src);
1939 if (any_condjump_p (insn))
1940 {
1941 rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1942
1943 if (cond && (e->flags & EDGE_FALLTHRU))
1944 cond = reversed_condition (cond);
1945 if (cond)
1946 {
1947 rtx old = *expr;
1948 simplify_using_condition (cond, expr, altered);
1949 if (old != *expr)
1950 {
1951 rtx note;
1952 if (CONSTANT_P (*expr))
1953 goto out;
1954 for (note = cond_list; note; note = XEXP (note, 1))
1955 {
1956 simplify_using_condition (XEXP (note, 0), expr, altered);
1957 if (CONSTANT_P (*expr))
1958 goto out;
1959 }
1960 }
1961 cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1962 }
1963 }
1964
1965 FOR_BB_INSNS_REVERSE (e->src, insn)
1966 {
1967 rtx src, dest;
1968 rtx old = *expr;
1969
1970 if (!INSN_P (insn))
1971 continue;
1972
1973 CLEAR_REG_SET (this_altered);
1974 note_stores (insn, mark_altered, this_altered);
1975 if (CALL_P (insn))
1976 {
1977 /* Kill all registers that might be clobbered by the call.
1978 We don't track modes of hard registers, so we need to be
1979 conservative and assume that partial kills are full kills. */
1980 function_abi callee_abi = insn_callee_abi (insn);
1981 IOR_REG_SET_HRS (this_altered,
1982 callee_abi.full_and_partial_reg_clobbers ());
1983 }
1984
1985 if (suitable_set_for_replacement (insn, &dest, &src))
1986 {
1987 rtx_expr_list **pnote, **pnote_next;
1988
1989 replace_in_expr (expr, dest, src);
1990 if (CONSTANT_P (*expr))
1991 goto out;
1992
1993 for (pnote = &cond_list; *pnote; pnote = pnote_next)
1994 {
1995 rtx_expr_list *note = *pnote;
1996 rtx old_cond = XEXP (note, 0);
1997
1998 pnote_next = (rtx_expr_list **)&XEXP (note, 1);
1999 replace_in_expr (&XEXP (note, 0), dest, src);
2000
2001 /* We can no longer use a condition that has been simplified
2002 to a constant, and simplify_using_condition will abort if
2003 we try. */
2004 if (CONSTANT_P (XEXP (note, 0)))
2005 {
2006 *pnote = *pnote_next;
2007 pnote_next = pnote;
2008 free_EXPR_LIST_node (note);
2009 }
2010 /* Retry simplifications with this condition if either the
2011 expression or the condition changed. */
2012 else if (old_cond != XEXP (note, 0) || old != *expr)
2013 simplify_using_condition (XEXP (note, 0), expr, altered);
2014 }
2015 }
2016 else
2017 {
2018 rtx_expr_list **pnote, **pnote_next;
2019
2020 /* If we did not use this insn to make a replacement, any overlap
2021 between stores in this insn and our expression will cause the
2022 expression to become invalid. */
2023 if (altered_reg_used (*expr, this_altered))
2024 goto out;
2025
2026 /* Likewise for the conditions. */
2027 for (pnote = &cond_list; *pnote; pnote = pnote_next)
2028 {
2029 rtx_expr_list *note = *pnote;
2030 rtx old_cond = XEXP (note, 0);
2031
2032 pnote_next = (rtx_expr_list **)&XEXP (note, 1);
2033 if (altered_reg_used (old_cond, this_altered))
2034 {
2035 *pnote = *pnote_next;
2036 pnote_next = pnote;
2037 free_EXPR_LIST_node (note);
2038 }
2039 }
2040 }
2041
2042 if (CONSTANT_P (*expr))
2043 goto out;
2044
2045 IOR_REG_SET (altered, this_altered);
2046
2047 /* If the expression now contains regs that have been altered, we
2048 can't return it to the caller. However, it is still valid for
2049 further simplification, so keep searching to see if we can
2050 eventually turn it into a constant. */
2051 if (altered_reg_used (*expr, altered))
2052 expression_valid = false;
2053 if (expression_valid)
2054 last_valid_expr = *expr;
2055 }
2056
2057 if (!single_pred_p (e->src)
2058 || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2059 break;
2060 e = single_pred_edge (e->src);
2061 }
2062
2063 out:
2064 free_EXPR_LIST_list (&cond_list);
2065 if (!CONSTANT_P (*expr))
2066 *expr = last_valid_expr;
2067 FREE_REG_SET (altered);
2068 FREE_REG_SET (this_altered);
2069 }
2070
2071 /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2072 that IV occurs as left operands of comparison COND and its signedness
2073 is SIGNED_P to DESC. */
2074
2075 static void
2076 shorten_into_mode (class rtx_iv *iv, scalar_int_mode mode,
2077 enum rtx_code cond, bool signed_p, class niter_desc *desc)
2078 {
2079 rtx mmin, mmax, cond_over, cond_under;
2080
2081 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2082 cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2083 iv->base, mmin);
2084 cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2085 iv->base, mmax);
2086
2087 switch (cond)
2088 {
2089 case LE:
2090 case LT:
2091 case LEU:
2092 case LTU:
2093 if (cond_under != const0_rtx)
2094 desc->infinite =
2095 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2096 if (cond_over != const0_rtx)
2097 desc->noloop_assumptions =
2098 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2099 break;
2100
2101 case GE:
2102 case GT:
2103 case GEU:
2104 case GTU:
2105 if (cond_over != const0_rtx)
2106 desc->infinite =
2107 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2108 if (cond_under != const0_rtx)
2109 desc->noloop_assumptions =
2110 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2111 break;
2112
2113 case NE:
2114 if (cond_over != const0_rtx)
2115 desc->infinite =
2116 alloc_EXPR_LIST (0, cond_over, desc->infinite);
2117 if (cond_under != const0_rtx)
2118 desc->infinite =
2119 alloc_EXPR_LIST (0, cond_under, desc->infinite);
2120 break;
2121
2122 default:
2123 gcc_unreachable ();
2124 }
2125
2126 iv->mode = mode;
2127 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2128 }
2129
2130 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2131 subregs of the same mode if possible (sometimes it is necessary to add
2132 some assumptions to DESC). */
2133
2134 static bool
2135 canonicalize_iv_subregs (class rtx_iv *iv0, class rtx_iv *iv1,
2136 enum rtx_code cond, class niter_desc *desc)
2137 {
2138 scalar_int_mode comp_mode;
2139 bool signed_p;
2140
2141 /* If the ivs behave specially in the first iteration, or are
2142 added/multiplied after extending, we ignore them. */
2143 if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2144 return false;
2145 if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2146 return false;
2147
2148 /* If there is some extend, it must match signedness of the comparison. */
2149 switch (cond)
2150 {
2151 case LE:
2152 case LT:
2153 if (iv0->extend == IV_ZERO_EXTEND
2154 || iv1->extend == IV_ZERO_EXTEND)
2155 return false;
2156 signed_p = true;
2157 break;
2158
2159 case LEU:
2160 case LTU:
2161 if (iv0->extend == IV_SIGN_EXTEND
2162 || iv1->extend == IV_SIGN_EXTEND)
2163 return false;
2164 signed_p = false;
2165 break;
2166
2167 case NE:
2168 if (iv0->extend != IV_UNKNOWN_EXTEND
2169 && iv1->extend != IV_UNKNOWN_EXTEND
2170 && iv0->extend != iv1->extend)
2171 return false;
2172
2173 signed_p = false;
2174 if (iv0->extend != IV_UNKNOWN_EXTEND)
2175 signed_p = iv0->extend == IV_SIGN_EXTEND;
2176 if (iv1->extend != IV_UNKNOWN_EXTEND)
2177 signed_p = iv1->extend == IV_SIGN_EXTEND;
2178 break;
2179
2180 default:
2181 gcc_unreachable ();
2182 }
2183
2184 /* Values of both variables should be computed in the same mode. These
2185 might indeed be different, if we have comparison like
2186
2187 (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2188
2189 and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2190 in different modes. This does not seem impossible to handle, but
2191 it hardly ever occurs in practice.
2192
2193 The only exception is the case when one of operands is invariant.
2194 For example pentium 3 generates comparisons like
2195 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2196 definitely do not want this prevent the optimization. */
2197 comp_mode = iv0->extend_mode;
2198 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2199 comp_mode = iv1->extend_mode;
2200
2201 if (iv0->extend_mode != comp_mode)
2202 {
2203 if (iv0->mode != iv0->extend_mode
2204 || iv0->step != const0_rtx)
2205 return false;
2206
2207 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2208 comp_mode, iv0->base, iv0->mode);
2209 iv0->extend_mode = comp_mode;
2210 }
2211
2212 if (iv1->extend_mode != comp_mode)
2213 {
2214 if (iv1->mode != iv1->extend_mode
2215 || iv1->step != const0_rtx)
2216 return false;
2217
2218 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2219 comp_mode, iv1->base, iv1->mode);
2220 iv1->extend_mode = comp_mode;
2221 }
2222
2223 /* Check that both ivs belong to a range of a single mode. If one of the
2224 operands is an invariant, we may need to shorten it into the common
2225 mode. */
2226 if (iv0->mode == iv0->extend_mode
2227 && iv0->step == const0_rtx
2228 && iv0->mode != iv1->mode)
2229 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2230
2231 if (iv1->mode == iv1->extend_mode
2232 && iv1->step == const0_rtx
2233 && iv0->mode != iv1->mode)
2234 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2235
2236 if (iv0->mode != iv1->mode)
2237 return false;
2238
2239 desc->mode = iv0->mode;
2240 desc->signed_p = signed_p;
2241
2242 return true;
2243 }
2244
2245 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2246 result. This function is called from iv_number_of_iterations with
2247 a number of fields in DESC already filled in. OLD_NITER is the original
2248 expression for the number of iterations, before we tried to simplify it. */
2249
2250 static uint64_t
2251 determine_max_iter (class loop *loop, class niter_desc *desc, rtx old_niter)
2252 {
2253 rtx niter = desc->niter_expr;
2254 rtx mmin, mmax, cmp;
2255 uint64_t nmax, inc;
2256 uint64_t andmax = 0;
2257
2258 /* We used to look for constant operand 0 of AND,
2259 but canonicalization should always make this impossible. */
2260 gcc_checking_assert (GET_CODE (niter) != AND
2261 || !CONST_INT_P (XEXP (niter, 0)));
2262
2263 if (GET_CODE (niter) == AND
2264 && CONST_INT_P (XEXP (niter, 1)))
2265 {
2266 andmax = UINTVAL (XEXP (niter, 1));
2267 niter = XEXP (niter, 0);
2268 }
2269
2270 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2271 nmax = UINTVAL (mmax) - UINTVAL (mmin);
2272
2273 if (GET_CODE (niter) == UDIV)
2274 {
2275 if (!CONST_INT_P (XEXP (niter, 1)))
2276 return nmax;
2277 inc = INTVAL (XEXP (niter, 1));
2278 niter = XEXP (niter, 0);
2279 }
2280 else
2281 inc = 1;
2282
2283 /* We could use a binary search here, but for now improving the upper
2284 bound by just one eliminates one important corner case. */
2285 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2286 desc->mode, old_niter, mmax);
2287 simplify_using_initial_values (loop, UNKNOWN, &cmp);
2288 if (cmp == const_true_rtx)
2289 {
2290 nmax--;
2291
2292 if (dump_file)
2293 fprintf (dump_file, ";; improved upper bound by one.\n");
2294 }
2295 nmax /= inc;
2296 if (andmax)
2297 nmax = MIN (nmax, andmax);
2298 if (dump_file)
2299 fprintf (dump_file, ";; Determined upper bound %" PRId64".\n",
2300 nmax);
2301 return nmax;
2302 }
2303
2304 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2305 the result into DESC. Very similar to determine_number_of_iterations
2306 (basically its rtl version), complicated by things like subregs. */
2307
2308 static void
2309 iv_number_of_iterations (class loop *loop, rtx_insn *insn, rtx condition,
2310 class niter_desc *desc)
2311 {
2312 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2313 class rtx_iv iv0, iv1;
2314 rtx assumption, may_not_xform;
2315 enum rtx_code cond;
2316 machine_mode nonvoid_mode;
2317 scalar_int_mode comp_mode;
2318 rtx mmin, mmax, mode_mmin, mode_mmax;
2319 uint64_t s, size, d, inv, max, up, down;
2320 int64_t inc, step_val;
2321 int was_sharp = false;
2322 rtx old_niter;
2323 bool step_is_pow2;
2324
2325 /* The meaning of these assumptions is this:
2326 if !assumptions
2327 then the rest of information does not have to be valid
2328 if noloop_assumptions then the loop does not roll
2329 if infinite then this exit is never used */
2330
2331 desc->assumptions = NULL_RTX;
2332 desc->noloop_assumptions = NULL_RTX;
2333 desc->infinite = NULL_RTX;
2334 desc->simple_p = true;
2335
2336 desc->const_iter = false;
2337 desc->niter_expr = NULL_RTX;
2338
2339 cond = GET_CODE (condition);
2340 gcc_assert (COMPARISON_P (condition));
2341
2342 nonvoid_mode = GET_MODE (XEXP (condition, 0));
2343 if (nonvoid_mode == VOIDmode)
2344 nonvoid_mode = GET_MODE (XEXP (condition, 1));
2345 /* The constant comparisons should be folded. */
2346 gcc_assert (nonvoid_mode != VOIDmode);
2347
2348 /* We only handle integers or pointers. */
2349 scalar_int_mode mode;
2350 if (!is_a <scalar_int_mode> (nonvoid_mode, &mode))
2351 goto fail;
2352
2353 op0 = XEXP (condition, 0);
2354 if (!iv_analyze (insn, mode, op0, &iv0))
2355 goto fail;
2356
2357 op1 = XEXP (condition, 1);
2358 if (!iv_analyze (insn, mode, op1, &iv1))
2359 goto fail;
2360
2361 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2362 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2363 goto fail;
2364
2365 /* Check condition and normalize it. */
2366
2367 switch (cond)
2368 {
2369 case GE:
2370 case GT:
2371 case GEU:
2372 case GTU:
2373 std::swap (iv0, iv1);
2374 cond = swap_condition (cond);
2375 break;
2376 case NE:
2377 case LE:
2378 case LEU:
2379 case LT:
2380 case LTU:
2381 break;
2382 default:
2383 goto fail;
2384 }
2385
2386 /* Handle extends. This is relatively nontrivial, so we only try in some
2387 easy cases, when we can canonicalize the ivs (possibly by adding some
2388 assumptions) to shape subreg (base + i * step). This function also fills
2389 in desc->mode and desc->signed_p. */
2390
2391 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2392 goto fail;
2393
2394 comp_mode = iv0.extend_mode;
2395 mode = iv0.mode;
2396 size = GET_MODE_PRECISION (mode);
2397 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2398 mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2399 mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2400
2401 if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2402 goto fail;
2403
2404 /* We can take care of the case of two induction variables chasing each other
2405 if the test is NE. I have never seen a loop using it, but still it is
2406 cool. */
2407 if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2408 {
2409 if (cond != NE)
2410 goto fail;
2411
2412 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2413 iv1.step = const0_rtx;
2414 }
2415
2416 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2417 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2418
2419 /* This is either infinite loop or the one that ends immediately, depending
2420 on initial values. Unswitching should remove this kind of conditions. */
2421 if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2422 goto fail;
2423
2424 if (cond != NE)
2425 {
2426 if (iv0.step == const0_rtx)
2427 step_val = -INTVAL (iv1.step);
2428 else
2429 step_val = INTVAL (iv0.step);
2430
2431 /* Ignore loops of while (i-- < 10) type. */
2432 if (step_val < 0)
2433 goto fail;
2434
2435 step_is_pow2 = !(step_val & (step_val - 1));
2436 }
2437 else
2438 {
2439 /* We do not care about whether the step is power of two in this
2440 case. */
2441 step_is_pow2 = false;
2442 step_val = 0;
2443 }
2444
2445 /* Some more condition normalization. We must record some assumptions
2446 due to overflows. */
2447 switch (cond)
2448 {
2449 case LT:
2450 case LTU:
2451 /* We want to take care only of non-sharp relationals; this is easy,
2452 as in cases the overflow would make the transformation unsafe
2453 the loop does not roll. Seemingly it would make more sense to want
2454 to take care of sharp relationals instead, as NE is more similar to
2455 them, but the problem is that here the transformation would be more
2456 difficult due to possibly infinite loops. */
2457 if (iv0.step == const0_rtx)
2458 {
2459 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2460 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2461 mode_mmax);
2462 if (assumption == const_true_rtx)
2463 goto zero_iter_simplify;
2464 iv0.base = simplify_gen_binary (PLUS, comp_mode,
2465 iv0.base, const1_rtx);
2466 }
2467 else
2468 {
2469 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2470 assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2471 mode_mmin);
2472 if (assumption == const_true_rtx)
2473 goto zero_iter_simplify;
2474 iv1.base = simplify_gen_binary (PLUS, comp_mode,
2475 iv1.base, constm1_rtx);
2476 }
2477
2478 if (assumption != const0_rtx)
2479 desc->noloop_assumptions =
2480 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2481 cond = (cond == LT) ? LE : LEU;
2482
2483 /* It will be useful to be able to tell the difference once more in
2484 LE -> NE reduction. */
2485 was_sharp = true;
2486 break;
2487 default: ;
2488 }
2489
2490 /* Take care of trivially infinite loops. */
2491 if (cond != NE)
2492 {
2493 if (iv0.step == const0_rtx)
2494 {
2495 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2496 if (rtx_equal_p (tmp, mode_mmin))
2497 {
2498 desc->infinite =
2499 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2500 /* Fill in the remaining fields somehow. */
2501 goto zero_iter_simplify;
2502 }
2503 }
2504 else
2505 {
2506 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2507 if (rtx_equal_p (tmp, mode_mmax))
2508 {
2509 desc->infinite =
2510 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2511 /* Fill in the remaining fields somehow. */
2512 goto zero_iter_simplify;
2513 }
2514 }
2515 }
2516
2517 /* If we can we want to take care of NE conditions instead of size
2518 comparisons, as they are much more friendly (most importantly
2519 this takes care of special handling of loops with step 1). We can
2520 do it if we first check that upper bound is greater or equal to
2521 lower bound, their difference is constant c modulo step and that
2522 there is not an overflow. */
2523 if (cond != NE)
2524 {
2525 if (iv0.step == const0_rtx)
2526 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2527 else
2528 step = iv0.step;
2529 step = lowpart_subreg (mode, step, comp_mode);
2530 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2531 delta = lowpart_subreg (mode, delta, comp_mode);
2532 delta = simplify_gen_binary (UMOD, mode, delta, step);
2533 may_xform = const0_rtx;
2534 may_not_xform = const_true_rtx;
2535
2536 if (CONST_INT_P (delta))
2537 {
2538 if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2539 {
2540 /* A special case. We have transformed condition of type
2541 for (i = 0; i < 4; i += 4)
2542 into
2543 for (i = 0; i <= 3; i += 4)
2544 obviously if the test for overflow during that transformation
2545 passed, we cannot overflow here. Most importantly any
2546 loop with sharp end condition and step 1 falls into this
2547 category, so handling this case specially is definitely
2548 worth the troubles. */
2549 may_xform = const_true_rtx;
2550 }
2551 else if (iv0.step == const0_rtx)
2552 {
2553 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2554 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2555 bound = lowpart_subreg (mode, bound, comp_mode);
2556 tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2557 may_xform = simplify_gen_relational (cond, SImode, mode,
2558 bound, tmp);
2559 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2560 SImode, mode,
2561 bound, tmp);
2562 }
2563 else
2564 {
2565 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2566 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2567 bound = lowpart_subreg (mode, bound, comp_mode);
2568 tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2569 may_xform = simplify_gen_relational (cond, SImode, mode,
2570 tmp, bound);
2571 may_not_xform = simplify_gen_relational (reverse_condition (cond),
2572 SImode, mode,
2573 tmp, bound);
2574 }
2575 }
2576
2577 if (may_xform != const0_rtx)
2578 {
2579 /* We perform the transformation always provided that it is not
2580 completely senseless. This is OK, as we would need this assumption
2581 to determine the number of iterations anyway. */
2582 if (may_xform != const_true_rtx)
2583 {
2584 /* If the step is a power of two and the final value we have
2585 computed overflows, the cycle is infinite. Otherwise it
2586 is nontrivial to compute the number of iterations. */
2587 if (step_is_pow2)
2588 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2589 desc->infinite);
2590 else
2591 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2592 desc->assumptions);
2593 }
2594
2595 /* We are going to lose some information about upper bound on
2596 number of iterations in this step, so record the information
2597 here. */
2598 inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2599 if (CONST_INT_P (iv1.base))
2600 up = INTVAL (iv1.base);
2601 else
2602 up = INTVAL (mode_mmax) - inc;
2603 down = INTVAL (CONST_INT_P (iv0.base)
2604 ? iv0.base
2605 : mode_mmin);
2606 max = (up - down) / inc + 1;
2607 if (!desc->infinite
2608 && !desc->assumptions)
2609 record_niter_bound (loop, max, false, true);
2610
2611 if (iv0.step == const0_rtx)
2612 {
2613 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2614 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2615 }
2616 else
2617 {
2618 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2619 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2620 }
2621
2622 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2623 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2624 assumption = simplify_gen_relational (reverse_condition (cond),
2625 SImode, mode, tmp0, tmp1);
2626 if (assumption == const_true_rtx)
2627 goto zero_iter_simplify;
2628 else if (assumption != const0_rtx)
2629 desc->noloop_assumptions =
2630 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2631 cond = NE;
2632 }
2633 }
2634
2635 /* Count the number of iterations. */
2636 if (cond == NE)
2637 {
2638 /* Everything we do here is just arithmetics modulo size of mode. This
2639 makes us able to do more involved computations of number of iterations
2640 than in other cases. First transform the condition into shape
2641 s * i <> c, with s positive. */
2642 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2643 iv0.base = const0_rtx;
2644 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2645 iv1.step = const0_rtx;
2646 if (INTVAL (iv0.step) < 0)
2647 {
2648 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
2649 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
2650 }
2651 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2652
2653 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2654 is infinite. Otherwise, the number of iterations is
2655 (inverse(s/d) * (c/d)) mod (size of mode/d). */
2656 s = INTVAL (iv0.step); d = 1;
2657 while (s % 2 != 1)
2658 {
2659 s /= 2;
2660 d *= 2;
2661 size--;
2662 }
2663 bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1);
2664
2665 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2666 tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2667 assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2668 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2669
2670 tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2671 inv = inverse (s, size);
2672 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2673 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2674 }
2675 else
2676 {
2677 if (iv1.step == const0_rtx)
2678 /* Condition in shape a + s * i <= b
2679 We must know that b + s does not overflow and a <= b + s and then we
2680 can compute number of iterations as (b + s - a) / s. (It might
2681 seem that we in fact could be more clever about testing the b + s
2682 overflow condition using some information about b - a mod s,
2683 but it was already taken into account during LE -> NE transform). */
2684 {
2685 step = iv0.step;
2686 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2687 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2688
2689 bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2690 lowpart_subreg (mode, step,
2691 comp_mode));
2692 if (step_is_pow2)
2693 {
2694 rtx t0, t1;
2695
2696 /* If s is power of 2, we know that the loop is infinite if
2697 a % s <= b % s and b + s overflows. */
2698 assumption = simplify_gen_relational (reverse_condition (cond),
2699 SImode, mode,
2700 tmp1, bound);
2701
2702 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2703 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2704 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2705 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2706 desc->infinite =
2707 alloc_EXPR_LIST (0, assumption, desc->infinite);
2708 }
2709 else
2710 {
2711 assumption = simplify_gen_relational (cond, SImode, mode,
2712 tmp1, bound);
2713 desc->assumptions =
2714 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2715 }
2716
2717 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2718 tmp = lowpart_subreg (mode, tmp, comp_mode);
2719 assumption = simplify_gen_relational (reverse_condition (cond),
2720 SImode, mode, tmp0, tmp);
2721
2722 delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2723 delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2724 }
2725 else
2726 {
2727 /* Condition in shape a <= b - s * i
2728 We must know that a - s does not overflow and a - s <= b and then
2729 we can again compute number of iterations as (b - (a - s)) / s. */
2730 step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2731 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2732 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2733
2734 bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2735 lowpart_subreg (mode, step, comp_mode));
2736 if (step_is_pow2)
2737 {
2738 rtx t0, t1;
2739
2740 /* If s is power of 2, we know that the loop is infinite if
2741 a % s <= b % s and a - s overflows. */
2742 assumption = simplify_gen_relational (reverse_condition (cond),
2743 SImode, mode,
2744 bound, tmp0);
2745
2746 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2747 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2748 tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2749 assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2750 desc->infinite =
2751 alloc_EXPR_LIST (0, assumption, desc->infinite);
2752 }
2753 else
2754 {
2755 assumption = simplify_gen_relational (cond, SImode, mode,
2756 bound, tmp0);
2757 desc->assumptions =
2758 alloc_EXPR_LIST (0, assumption, desc->assumptions);
2759 }
2760
2761 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2762 tmp = lowpart_subreg (mode, tmp, comp_mode);
2763 assumption = simplify_gen_relational (reverse_condition (cond),
2764 SImode, mode,
2765 tmp, tmp1);
2766 delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2767 delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2768 }
2769 if (assumption == const_true_rtx)
2770 goto zero_iter_simplify;
2771 else if (assumption != const0_rtx)
2772 desc->noloop_assumptions =
2773 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2774 delta = simplify_gen_binary (UDIV, mode, delta, step);
2775 desc->niter_expr = delta;
2776 }
2777
2778 old_niter = desc->niter_expr;
2779
2780 simplify_using_initial_values (loop, AND, &desc->assumptions);
2781 if (desc->assumptions
2782 && XEXP (desc->assumptions, 0) == const0_rtx)
2783 goto fail;
2784 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2785 simplify_using_initial_values (loop, IOR, &desc->infinite);
2786 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2787
2788 /* Rerun the simplification. Consider code (created by copying loop headers)
2789
2790 i = 0;
2791
2792 if (0 < n)
2793 {
2794 do
2795 {
2796 i++;
2797 } while (i < n);
2798 }
2799
2800 The first pass determines that i = 0, the second pass uses it to eliminate
2801 noloop assumption. */
2802
2803 simplify_using_initial_values (loop, AND, &desc->assumptions);
2804 if (desc->assumptions
2805 && XEXP (desc->assumptions, 0) == const0_rtx)
2806 goto fail;
2807 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2808 simplify_using_initial_values (loop, IOR, &desc->infinite);
2809 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2810
2811 if (desc->noloop_assumptions
2812 && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2813 goto zero_iter;
2814
2815 if (CONST_INT_P (desc->niter_expr))
2816 {
2817 uint64_t val = INTVAL (desc->niter_expr);
2818
2819 desc->const_iter = true;
2820 desc->niter = val & GET_MODE_MASK (desc->mode);
2821 if (!desc->infinite
2822 && !desc->assumptions)
2823 record_niter_bound (loop, desc->niter, false, true);
2824 }
2825 else
2826 {
2827 max = determine_max_iter (loop, desc, old_niter);
2828 if (!max)
2829 goto zero_iter_simplify;
2830 if (!desc->infinite
2831 && !desc->assumptions)
2832 record_niter_bound (loop, max, false, true);
2833
2834 /* simplify_using_initial_values does a copy propagation on the registers
2835 in the expression for the number of iterations. This prolongs life
2836 ranges of registers and increases register pressure, and usually
2837 brings no gain (and if it happens to do, the cse pass will take care
2838 of it anyway). So prevent this behavior, unless it enabled us to
2839 derive that the number of iterations is a constant. */
2840 desc->niter_expr = old_niter;
2841 }
2842
2843 return;
2844
2845 zero_iter_simplify:
2846 /* Simplify the assumptions. */
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->infinite);
2852
2853 /* Fallthru. */
2854 zero_iter:
2855 desc->const_iter = true;
2856 desc->niter = 0;
2857 record_niter_bound (loop, 0, true, true);
2858 desc->noloop_assumptions = NULL_RTX;
2859 desc->niter_expr = const0_rtx;
2860 return;
2861
2862 fail:
2863 desc->simple_p = false;
2864 return;
2865 }
2866
2867 /* Checks whether E is a simple exit from LOOP and stores its description
2868 into DESC. */
2869
2870 static void
2871 check_simple_exit (class loop *loop, edge e, class niter_desc *desc)
2872 {
2873 basic_block exit_bb;
2874 rtx condition;
2875 rtx_insn *at;
2876 edge ein;
2877
2878 exit_bb = e->src;
2879 desc->simple_p = false;
2880
2881 /* It must belong directly to the loop. */
2882 if (exit_bb->loop_father != loop)
2883 return;
2884
2885 /* It must be tested (at least) once during any iteration. */
2886 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2887 return;
2888
2889 /* It must end in a simple conditional jump. */
2890 if (!any_condjump_p (BB_END (exit_bb)))
2891 return;
2892
2893 ein = EDGE_SUCC (exit_bb, 0);
2894 if (ein == e)
2895 ein = EDGE_SUCC (exit_bb, 1);
2896
2897 desc->out_edge = e;
2898 desc->in_edge = ein;
2899
2900 /* Test whether the condition is suitable. */
2901 if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2902 return;
2903
2904 if (ein->flags & EDGE_FALLTHRU)
2905 {
2906 condition = reversed_condition (condition);
2907 if (!condition)
2908 return;
2909 }
2910
2911 /* Check that we are able to determine number of iterations and fill
2912 in information about it. */
2913 iv_number_of_iterations (loop, at, condition, desc);
2914 }
2915
2916 /* Finds a simple exit of LOOP and stores its description into DESC. */
2917
2918 static void
2919 find_simple_exit (class loop *loop, class niter_desc *desc)
2920 {
2921 unsigned i;
2922 basic_block *body;
2923 edge e;
2924 class niter_desc act;
2925 bool any = false;
2926 edge_iterator ei;
2927
2928 desc->simple_p = false;
2929 body = get_loop_body (loop);
2930
2931 for (i = 0; i < loop->num_nodes; i++)
2932 {
2933 FOR_EACH_EDGE (e, ei, body[i]->succs)
2934 {
2935 if (flow_bb_inside_loop_p (loop, e->dest))
2936 continue;
2937
2938 check_simple_exit (loop, e, &act);
2939 if (!act.simple_p)
2940 continue;
2941
2942 if (!any)
2943 any = true;
2944 else
2945 {
2946 /* Prefer constant iterations; the less the better. */
2947 if (!act.const_iter
2948 || (desc->const_iter && act.niter >= desc->niter))
2949 continue;
2950
2951 /* Also if the actual exit may be infinite, while the old one
2952 not, prefer the old one. */
2953 if (act.infinite && !desc->infinite)
2954 continue;
2955 }
2956
2957 *desc = act;
2958 }
2959 }
2960
2961 if (dump_file)
2962 {
2963 if (desc->simple_p)
2964 {
2965 fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2966 fprintf (dump_file, " simple exit %d -> %d\n",
2967 desc->out_edge->src->index,
2968 desc->out_edge->dest->index);
2969 if (desc->assumptions)
2970 {
2971 fprintf (dump_file, " assumptions: ");
2972 print_rtl (dump_file, desc->assumptions);
2973 fprintf (dump_file, "\n");
2974 }
2975 if (desc->noloop_assumptions)
2976 {
2977 fprintf (dump_file, " does not roll if: ");
2978 print_rtl (dump_file, desc->noloop_assumptions);
2979 fprintf (dump_file, "\n");
2980 }
2981 if (desc->infinite)
2982 {
2983 fprintf (dump_file, " infinite if: ");
2984 print_rtl (dump_file, desc->infinite);
2985 fprintf (dump_file, "\n");
2986 }
2987
2988 fprintf (dump_file, " number of iterations: ");
2989 print_rtl (dump_file, desc->niter_expr);
2990 fprintf (dump_file, "\n");
2991
2992 fprintf (dump_file, " upper bound: %li\n",
2993 (long)get_max_loop_iterations_int (loop));
2994 fprintf (dump_file, " likely upper bound: %li\n",
2995 (long)get_likely_max_loop_iterations_int (loop));
2996 fprintf (dump_file, " realistic bound: %li\n",
2997 (long)get_estimated_loop_iterations_int (loop));
2998 }
2999 else
3000 fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
3001 }
3002
3003 /* Fix up the finiteness if possible. We can only do it for single exit,
3004 since the loop is finite, but it's possible that we predicate one loop
3005 exit to be finite which can not be determined as finite in middle-end as
3006 well. It results in incorrect predicate information on the exit condition
3007 expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite,
3008 it means _1 can exactly divide -8. */
3009 if (desc->infinite && single_exit (loop) && finite_loop_p (loop))
3010 {
3011 desc->infinite = NULL_RTX;
3012 if (dump_file)
3013 fprintf (dump_file, " infinite updated to finite.\n");
3014 }
3015
3016 free (body);
3017 }
3018
3019 /* Creates a simple loop description of LOOP if it was not computed
3020 already. */
3021
3022 class niter_desc *
3023 get_simple_loop_desc (class loop *loop)
3024 {
3025 class niter_desc *desc = simple_loop_desc (loop);
3026
3027 if (desc)
3028 return desc;
3029
3030 /* At least desc->infinite is not always initialized by
3031 find_simple_loop_exit. */
3032 desc = ggc_cleared_alloc<niter_desc> ();
3033 iv_analysis_loop_init (loop);
3034 find_simple_exit (loop, desc);
3035 loop->simple_loop_desc = desc;
3036 return desc;
3037 }
3038
3039 /* Releases simple loop description for LOOP. */
3040
3041 void
3042 free_simple_loop_desc (class loop *loop)
3043 {
3044 class niter_desc *desc = simple_loop_desc (loop);
3045
3046 if (!desc)
3047 return;
3048
3049 ggc_free (desc);
3050 loop->simple_loop_desc = NULL;
3051 }