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