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