Mercurial > hg > CbC > CbC_gcc

comparison gcc/loop-iv.c @ 0:a06113de4d67

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