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