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