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