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