Branch data Line data Source code
1 : : /* Rtl-level induction variable analysis.
2 : : Copyright (C) 2004-2025 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 : 119021 : biv_entry_hasher::hash (const biv_entry *b)
125 : : {
126 : 119021 : return b->regno;
127 : : }
128 : :
129 : : /* Compares biv B and register R. */
130 : :
131 : : inline bool
132 : 139153 : biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r)
133 : : {
134 : 139153 : 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 : 10 : iv_extend_to_rtx_code (enum iv_extend_code extend)
146 : : {
147 : 10 : 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 : 570 : dump_iv_info (FILE *file, class rtx_iv *iv)
164 : : {
165 : 570 : if (!iv->base)
166 : : {
167 : 57 : fprintf (file, "not simple");
168 : 57 : return;
169 : : }
170 : :
171 : 513 : if (iv->step == const0_rtx
172 : 221 : && !iv->first_special)
173 : 221 : fprintf (file, "invariant ");
174 : :
175 : 513 : print_rtl (file, iv->base);
176 : 513 : if (iv->step != const0_rtx)
177 : : {
178 : 292 : fprintf (file, " + ");
179 : 292 : print_rtl (file, iv->step);
180 : 292 : fprintf (file, " * iteration");
181 : : }
182 : 513 : fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
183 : :
184 : 513 : 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 : 513 : if (iv->mult != const1_rtx)
190 : : {
191 : 0 : fprintf (file, " * ");
192 : 0 : print_rtl (file, iv->mult);
193 : : }
194 : 513 : if (iv->delta != const0_rtx)
195 : : {
196 : 0 : fprintf (file, " + ");
197 : 0 : print_rtl (file, iv->delta);
198 : : }
199 : 513 : if (iv->first_special)
200 : 0 : fprintf (file, " (first special)");
201 : : }
202 : :
203 : : static void
204 : 2665938 : check_iv_ref_table_size (void)
205 : : {
206 : 2665938 : if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ())
207 : : {
208 : 268187 : unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
209 : 268187 : iv_ref_table = XRESIZEVEC (class rtx_iv *, iv_ref_table, new_size);
210 : 268187 : memset (&iv_ref_table[iv_ref_table_size], 0,
211 : 268187 : (new_size - iv_ref_table_size) * sizeof (class rtx_iv *));
212 : 268187 : iv_ref_table_size = new_size;
213 : : }
214 : 2665938 : }
215 : :
216 : :
217 : : /* Checks whether REG is a well-behaved register. */
218 : :
219 : : static bool
220 : 3874706 : simple_reg_p (rtx reg)
221 : : {
222 : 3874706 : unsigned r;
223 : :
224 : 3874706 : if (GET_CODE (reg) == SUBREG)
225 : : {
226 : 12385 : if (!subreg_lowpart_p (reg))
227 : : return false;
228 : 12359 : reg = SUBREG_REG (reg);
229 : : }
230 : :
231 : 3874680 : if (!REG_P (reg))
232 : : return false;
233 : :
234 : 3569615 : r = REGNO (reg);
235 : 3569615 : if (HARD_REGISTER_NUM_P (r))
236 : : return false;
237 : :
238 : 3534108 : 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 : 646806 : clear_iv_info (void)
248 : : {
249 : 646806 : unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
250 : 646806 : class rtx_iv *iv;
251 : :
252 : 646806 : check_iv_ref_table_size ();
253 : 77019030 : for (i = 0; i < n_defs; i++)
254 : : {
255 : 75725418 : iv = iv_ref_table[i];
256 : 75725418 : if (iv)
257 : : {
258 : 681933 : free (iv);
259 : 681933 : iv_ref_table[i] = NULL;
260 : : }
261 : : }
262 : :
263 : 646806 : bivs->empty ();
264 : 646806 : }
265 : :
266 : :
267 : : /* Prepare the data for an induction variable analysis of a LOOP. */
268 : :
269 : : void
270 : 646806 : iv_analysis_loop_init (class loop *loop)
271 : : {
272 : 646806 : current_loop = loop;
273 : :
274 : : /* Clear the information from the analysis of the previous loop. */
275 : 646806 : if (clean_slate)
276 : : {
277 : 188268 : df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
278 : 188268 : bivs = new hash_table<biv_entry_hasher> (10);
279 : 188268 : clean_slate = false;
280 : : }
281 : : else
282 : 458538 : clear_iv_info ();
283 : :
284 : : /* Get rid of the ud chains before processing the rescans. Then add
285 : : the problem back. */
286 : 646806 : df_remove_problem (df_chain);
287 : 646806 : df_process_deferred_rescans ();
288 : 646806 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
289 : 646806 : df_chain_add_problem (DF_UD_CHAIN);
290 : 646806 : df_note_add_problem ();
291 : 646806 : df_analyze_loop (loop);
292 : 646806 : if (dump_file)
293 : 174 : df_dump_region (dump_file);
294 : :
295 : 646806 : check_iv_ref_table_size ();
296 : 646806 : }
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 : 684995 : latch_dominating_def (rtx reg, df_ref *def)
305 : : {
306 : 684995 : df_ref single_rd = NULL, adef;
307 : 684995 : unsigned regno = REGNO (reg);
308 : 684995 : class df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
309 : :
310 : 2206116 : for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
311 : : {
312 : 1521144 : if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
313 : 1521144 : || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
314 : 857058 : continue;
315 : :
316 : : /* More than one reaching definition. */
317 : 664086 : if (single_rd)
318 : : return false;
319 : :
320 : 664086 : if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
321 : : return false;
322 : :
323 : : single_rd = adef;
324 : : }
325 : :
326 : 684972 : *def = single_rd;
327 : 684972 : 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 : 2075317 : iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
334 : : {
335 : 2075317 : df_ref use, adef;
336 : 2075317 : basic_block def_bb, use_bb;
337 : 2075317 : rtx_insn *def_insn;
338 : 2075317 : bool dom_p;
339 : :
340 : 2075317 : *def = NULL;
341 : 2075317 : if (!simple_reg_p (reg))
342 : : return GRD_INVALID;
343 : 1984012 : if (GET_CODE (reg) == SUBREG)
344 : 0 : reg = SUBREG_REG (reg);
345 : 1984012 : gcc_assert (REG_P (reg));
346 : :
347 : 1984012 : use = df_find_use (insn, reg);
348 : 1984012 : gcc_assert (use != NULL);
349 : :
350 : 1984012 : if (!DF_REF_CHAIN (use))
351 : : return GRD_INVARIANT;
352 : :
353 : : /* More than one reaching def. */
354 : 1694971 : if (DF_REF_CHAIN (use)->next)
355 : : return GRD_INVALID;
356 : :
357 : 1669467 : adef = DF_REF_CHAIN (use)->ref;
358 : :
359 : : /* We do not handle setting only part of the register. */
360 : 1669467 : if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
361 : : return GRD_INVALID;
362 : :
363 : 1669463 : def_insn = DF_REF_INSN (adef);
364 : 1669463 : def_bb = DF_REF_BB (adef);
365 : 1669463 : use_bb = BLOCK_FOR_INSN (insn);
366 : :
367 : 1669463 : if (use_bb == def_bb)
368 : 1536530 : dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
369 : : else
370 : 132933 : dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
371 : :
372 : 1669463 : if (dom_p)
373 : : {
374 : 657175 : *def = adef;
375 : 657175 : 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 : 1012288 : 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 : 929170 : iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)
392 : : {
393 : 929170 : iv->mode = mode;
394 : 929170 : iv->base = cst;
395 : 929170 : iv->step = const0_rtx;
396 : 929170 : iv->first_special = false;
397 : 929170 : iv->extend = IV_UNKNOWN_EXTEND;
398 : 929170 : iv->extend_mode = iv->mode;
399 : 929170 : iv->delta = const0_rtx;
400 : 929170 : iv->mult = const1_rtx;
401 : :
402 : 929170 : return true;
403 : : }
404 : :
405 : : /* Evaluates application of subreg to MODE on IV. */
406 : :
407 : : static bool
408 : 5702 : iv_subreg (class rtx_iv *iv, scalar_int_mode mode)
409 : : {
410 : : /* If iv is invariant, just calculate the new value. */
411 : 5702 : if (iv->step == const0_rtx
412 : 74 : && !iv->first_special)
413 : : {
414 : 72 : rtx val = get_iv_value (iv, const0_rtx);
415 : 72 : val = lowpart_subreg (mode, val,
416 : 72 : iv->extend == IV_UNKNOWN_EXTEND
417 : : ? iv->mode : iv->extend_mode);
418 : :
419 : 72 : iv->base = val;
420 : 72 : iv->extend = IV_UNKNOWN_EXTEND;
421 : 72 : iv->mode = iv->extend_mode = mode;
422 : 72 : iv->delta = const0_rtx;
423 : 72 : iv->mult = const1_rtx;
424 : 72 : return true;
425 : : }
426 : :
427 : 5630 : if (iv->extend_mode == mode)
428 : : return true;
429 : :
430 : 16890 : if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
431 : : return false;
432 : :
433 : 5630 : iv->extend = IV_UNKNOWN_EXTEND;
434 : 5630 : iv->mode = mode;
435 : :
436 : 5630 : 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 : 5630 : iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
440 : 5630 : iv->mult = const1_rtx;
441 : 5630 : iv->delta = const0_rtx;
442 : 5630 : iv->first_special = false;
443 : :
444 : 5630 : return true;
445 : : }
446 : :
447 : : /* Evaluates application of EXTEND to MODE on IV. */
448 : :
449 : : static bool
450 : 595 : 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 : 595 : if (iv->step == const0_rtx
454 : 10 : && !iv->first_special)
455 : : {
456 : 10 : rtx val = get_iv_value (iv, const0_rtx);
457 : 10 : if (iv->extend_mode != iv->mode
458 : 0 : && iv->extend != IV_UNKNOWN_EXTEND
459 : 10 : && iv->extend != extend)
460 : 0 : val = lowpart_subreg (iv->mode, val, iv->extend_mode);
461 : 10 : val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
462 : : val,
463 : 10 : iv->extend == extend
464 : : ? iv->extend_mode : iv->mode);
465 : 10 : iv->base = val;
466 : 10 : iv->extend = IV_UNKNOWN_EXTEND;
467 : 10 : iv->mode = iv->extend_mode = mode;
468 : 10 : iv->delta = const0_rtx;
469 : 10 : iv->mult = const1_rtx;
470 : 10 : return true;
471 : : }
472 : :
473 : 585 : if (mode != iv->extend_mode)
474 : : return false;
475 : :
476 : 6 : if (iv->extend != IV_UNKNOWN_EXTEND
477 : 0 : && iv->extend != extend)
478 : : return false;
479 : :
480 : 6 : iv->extend = extend;
481 : :
482 : 6 : return true;
483 : : }
484 : :
485 : : /* Evaluates negation of IV. */
486 : :
487 : : static bool
488 : 33 : iv_neg (class rtx_iv *iv)
489 : : {
490 : 33 : if (iv->extend == IV_UNKNOWN_EXTEND)
491 : : {
492 : 33 : iv->base = simplify_gen_unary (NEG, iv->extend_mode,
493 : : iv->base, iv->extend_mode);
494 : 33 : 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 : 33 : return true;
506 : : }
507 : :
508 : : /* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
509 : :
510 : : static bool
511 : 459964 : iv_add (class rtx_iv *iv0, class rtx_iv *iv1, enum rtx_code op)
512 : : {
513 : 459964 : scalar_int_mode mode;
514 : 459964 : rtx arg;
515 : :
516 : : /* Extend the constant to extend_mode of the other operand if necessary. */
517 : 459964 : if (iv0->extend == IV_UNKNOWN_EXTEND
518 : 459963 : && iv0->mode == iv0->extend_mode
519 : 459281 : && iv0->step == const0_rtx
520 : 463855 : && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
521 : : {
522 : 302 : iv0->extend_mode = iv1->extend_mode;
523 : 302 : iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
524 : : iv0->base, iv0->mode);
525 : : }
526 : 459964 : if (iv1->extend == IV_UNKNOWN_EXTEND
527 : 459964 : && iv1->mode == iv1->extend_mode
528 : 459662 : && iv1->step == const0_rtx
529 : 1836721 : && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
530 : : {
531 : 682 : iv1->extend_mode = iv0->extend_mode;
532 : 682 : iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
533 : : iv1->base, iv1->mode);
534 : : }
535 : :
536 : 459964 : mode = iv0->extend_mode;
537 : 459964 : if (mode != iv1->extend_mode)
538 : : return false;
539 : :
540 : 459964 : if (iv0->extend == IV_UNKNOWN_EXTEND
541 : 459963 : && iv1->extend == IV_UNKNOWN_EXTEND)
542 : : {
543 : 459963 : if (iv0->mode != iv1->mode)
544 : : return false;
545 : :
546 : 459963 : iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
547 : 459963 : iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
548 : :
549 : 459963 : 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 : 36 : iv_mult (class rtx_iv *iv, rtx mby)
582 : : {
583 : 36 : scalar_int_mode mode = iv->extend_mode;
584 : :
585 : 36 : if (GET_MODE (mby) != VOIDmode
586 : 36 : && GET_MODE (mby) != mode)
587 : : return false;
588 : :
589 : 36 : if (iv->extend == IV_UNKNOWN_EXTEND)
590 : : {
591 : 36 : iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
592 : 36 : 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 : 166 : iv_shift (class rtx_iv *iv, rtx mby)
607 : : {
608 : 166 : scalar_int_mode mode = iv->extend_mode;
609 : :
610 : 166 : if (GET_MODE (mby) != VOIDmode
611 : 166 : && GET_MODE (mby) != mode)
612 : : return false;
613 : :
614 : 166 : if (iv->extend == IV_UNKNOWN_EXTEND)
615 : : {
616 : 166 : iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
617 : 166 : 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 : 538543 : 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 : 538543 : rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
639 : 538543 : rtx next, nextr;
640 : 538543 : enum rtx_code code, prev_code = UNKNOWN;
641 : 538543 : rtx_insn *insn = DF_REF_INSN (def);
642 : 538543 : df_ref next_def;
643 : 538543 : enum iv_grd_result res;
644 : :
645 : 538543 : set = single_set (insn);
646 : 538543 : if (!set)
647 : : return false;
648 : :
649 : 537049 : rhs = find_reg_equal_equiv_note (insn);
650 : 537049 : if (rhs)
651 : 2407 : rhs = XEXP (rhs, 0);
652 : : else
653 : 534642 : rhs = SET_SRC (set);
654 : :
655 : 537049 : code = GET_CODE (rhs);
656 : 537049 : switch (code)
657 : : {
658 : : case SUBREG:
659 : : case REG:
660 : : next = rhs;
661 : : break;
662 : :
663 : 491664 : case PLUS:
664 : 491664 : case MINUS:
665 : 491664 : op0 = XEXP (rhs, 0);
666 : 491664 : op1 = XEXP (rhs, 1);
667 : :
668 : 491664 : if (code == PLUS && CONSTANT_P (op0))
669 : : std::swap (op0, op1);
670 : :
671 : 491664 : if (!simple_reg_p (op0)
672 : 491664 : || !CONSTANT_P (op1))
673 : : return false;
674 : :
675 : 472598 : 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 : 222 : if (GET_CODE (op0) != SUBREG)
686 : : return false;
687 : 9 : if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
688 : : return false;
689 : : }
690 : :
691 : : next = op0;
692 : : break;
693 : :
694 : 394 : case SIGN_EXTEND:
695 : 394 : case ZERO_EXTEND:
696 : 394 : if (GET_MODE (rhs) != outer_mode)
697 : : return false;
698 : :
699 : 390 : 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 : 390 : 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 : 0 : op1 = simplify_gen_unary (code, outer_mode, op1, GET_MODE (rhs));
718 : 0 : prev_code = code;
719 : 0 : code = PLUS;
720 : : }
721 : :
722 : 390 : if (!simple_reg_p (op0))
723 : : return false;
724 : :
725 : : next = op0;
726 : : break;
727 : :
728 : : default:
729 : : return false;
730 : : }
731 : :
732 : 496743 : if (GET_CODE (next) == SUBREG)
733 : : {
734 : 964 : if (!subreg_lowpart_p (next))
735 : : return false;
736 : :
737 : 919 : nextr = SUBREG_REG (next);
738 : 919 : if (GET_MODE (nextr) != outer_mode)
739 : : return false;
740 : : }
741 : : else
742 : : nextr = next;
743 : :
744 : 495798 : res = iv_get_reaching_def (insn, nextr, &next_def);
745 : :
746 : 495798 : if (res == GRD_INVALID || res == GRD_INVARIANT)
747 : : return false;
748 : :
749 : 491655 : if (res == GRD_MAYBE_BIV)
750 : : {
751 : 472177 : if (!rtx_equal_p (nextr, reg))
752 : : return false;
753 : :
754 : 471536 : *inner_step = const0_rtx;
755 : 471536 : *extend = IV_UNKNOWN_EXTEND;
756 : 471536 : *inner_mode = outer_mode;
757 : 471536 : *outer_step = const0_rtx;
758 : : }
759 : 19478 : else if (!get_biv_step_1 (next_def, outer_mode, reg,
760 : : inner_step, inner_mode, extend,
761 : : outer_step))
762 : : return false;
763 : :
764 : 479024 : if (GET_CODE (next) == SUBREG)
765 : : {
766 : 14 : scalar_int_mode amode;
767 : 14 : if (!is_a <scalar_int_mode> (GET_MODE (next), &amode)
768 : 28 : || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
769 : 59519 : return false;
770 : :
771 : 14 : *inner_mode = amode;
772 : 14 : *inner_step = simplify_gen_binary (PLUS, outer_mode,
773 : : *inner_step, *outer_step);
774 : 14 : *outer_step = const0_rtx;
775 : 14 : *extend = IV_UNKNOWN_EXTEND;
776 : : }
777 : :
778 : 479024 : switch (code)
779 : : {
780 : : case REG:
781 : : case SUBREG:
782 : : break;
783 : :
784 : 471533 : case PLUS:
785 : 471533 : case MINUS:
786 : 471533 : if (*inner_mode == outer_mode
787 : : /* See comment in previous switch. */
788 : 471533 : || GET_MODE (rhs) != outer_mode)
789 : 471532 : *inner_step = simplify_gen_binary (code, outer_mode,
790 : : *inner_step, op1);
791 : : else
792 : 1 : *outer_step = simplify_gen_binary (code, outer_mode,
793 : : *outer_step, op1);
794 : :
795 : 471533 : if (prev_code == SIGN_EXTEND)
796 : 0 : *extend = IV_SIGN_EXTEND;
797 : 471533 : else if (prev_code == ZERO_EXTEND)
798 : 0 : *extend = IV_ZERO_EXTEND;
799 : : break;
800 : :
801 : 14 : case SIGN_EXTEND:
802 : 14 : case ZERO_EXTEND:
803 : 14 : gcc_assert (GET_MODE (op0) == *inner_mode
804 : : && *extend == IV_UNKNOWN_EXTEND
805 : : && *outer_step == const0_rtx);
806 : :
807 : 14 : *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
808 : 14 : break;
809 : :
810 : : default:
811 : : return false;
812 : : }
813 : :
814 : : return true;
815 : : }
816 : :
817 : : /* Gets the operation on register REG inside loop, in shape
818 : :
819 : : OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
820 : :
821 : : If the operation cannot be described in this shape, return false.
822 : : LAST_DEF is the definition of REG that dominates loop latch. */
823 : :
824 : : static bool
825 : 519065 : get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
826 : : rtx *inner_step, scalar_int_mode *inner_mode,
827 : : enum iv_extend_code *extend, rtx *outer_step)
828 : : {
829 : 519065 : if (!get_biv_step_1 (last_def, outer_mode, reg,
830 : : inner_step, inner_mode, extend,
831 : : outer_step))
832 : : return false;
833 : :
834 : 471536 : gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
835 : 471536 : gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx);
836 : :
837 : : return true;
838 : : }
839 : :
840 : : /* Records information that DEF is induction variable IV. */
841 : :
842 : : static void
843 : 681933 : record_iv (df_ref def, class rtx_iv *iv)
844 : : {
845 : 681933 : class rtx_iv *recorded_iv = XNEW (class rtx_iv);
846 : :
847 : 681933 : *recorded_iv = *iv;
848 : 681933 : check_iv_ref_table_size ();
849 : 681933 : DF_REF_IV_SET (def, recorded_iv);
850 : 681933 : }
851 : :
852 : : /* If DEF was already analyzed for bivness, store the description of the biv to
853 : : IV and return true. Otherwise return false. */
854 : :
855 : : static bool
856 : 600478 : analyzed_for_bivness_p (rtx def, class rtx_iv *iv)
857 : : {
858 : 600478 : class biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
859 : :
860 : 600478 : if (!biv)
861 : : return false;
862 : :
863 : 81413 : *iv = biv->iv;
864 : 81413 : return true;
865 : : }
866 : :
867 : : static void
868 : 519065 : record_biv (rtx def, class rtx_iv *iv)
869 : : {
870 : 519065 : class biv_entry *biv = XNEW (class biv_entry);
871 : 519065 : biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
872 : :
873 : 519065 : biv->regno = REGNO (def);
874 : 519065 : biv->iv = *iv;
875 : 519065 : gcc_assert (!*slot);
876 : 519065 : *slot = biv;
877 : 519065 : }
878 : :
879 : : /* Determines whether DEF is a biv and if so, stores its description
880 : : to *IV. OUTER_MODE is the mode of DEF. */
881 : :
882 : : static bool
883 : 600478 : iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)
884 : : {
885 : 600478 : rtx inner_step, outer_step;
886 : 600478 : scalar_int_mode inner_mode;
887 : 600478 : enum iv_extend_code extend;
888 : 600478 : df_ref last_def;
889 : :
890 : 600478 : if (dump_file)
891 : : {
892 : 217 : fprintf (dump_file, "Analyzing ");
893 : 217 : print_rtl (dump_file, def);
894 : 217 : fprintf (dump_file, " for bivness.\n");
895 : : }
896 : :
897 : 600478 : if (!REG_P (def))
898 : : {
899 : 0 : if (!CONSTANT_P (def))
900 : : return false;
901 : :
902 : 0 : return iv_constant (iv, outer_mode, def);
903 : : }
904 : :
905 : 600478 : if (!latch_dominating_def (def, &last_def))
906 : : {
907 : 0 : if (dump_file)
908 : 0 : fprintf (dump_file, " not simple.\n");
909 : 0 : return false;
910 : : }
911 : :
912 : 600478 : if (!last_def)
913 : 0 : return iv_constant (iv, outer_mode, def);
914 : :
915 : 600478 : if (analyzed_for_bivness_p (def, iv))
916 : : {
917 : 81413 : if (dump_file)
918 : 71 : fprintf (dump_file, " already analysed.\n");
919 : 81413 : return iv->base != NULL_RTX;
920 : : }
921 : :
922 : 519065 : if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
923 : : &extend, &outer_step))
924 : : {
925 : 47529 : iv->base = NULL_RTX;
926 : 47529 : goto end;
927 : : }
928 : :
929 : : /* Loop transforms base to es (base + inner_step) + outer_step,
930 : : where es means extend of subreg between inner_mode and outer_mode.
931 : : The corresponding induction variable is
932 : :
933 : : es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
934 : :
935 : 471536 : iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
936 : 471536 : iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
937 : 471536 : iv->mode = inner_mode;
938 : 471536 : iv->extend_mode = outer_mode;
939 : 471536 : iv->extend = extend;
940 : 471536 : iv->mult = const1_rtx;
941 : 471536 : iv->delta = outer_step;
942 : 471536 : iv->first_special = inner_mode != outer_mode;
943 : :
944 : 519065 : end:
945 : 519065 : if (dump_file)
946 : : {
947 : 146 : fprintf (dump_file, " ");
948 : 146 : dump_iv_info (dump_file, iv);
949 : 146 : fprintf (dump_file, "\n");
950 : : }
951 : :
952 : 519065 : record_biv (def, iv);
953 : 519065 : return iv->base != NULL_RTX;
954 : : }
955 : :
956 : : /* Analyzes expression RHS used at INSN and stores the result to *IV.
957 : : The mode of the induction variable is MODE. */
958 : :
959 : : bool
960 : 1657611 : iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
961 : : class rtx_iv *iv)
962 : : {
963 : 1657611 : rtx mby = NULL_RTX;
964 : 1657611 : rtx op0 = NULL_RTX, op1 = NULL_RTX;
965 : 1657611 : class rtx_iv iv0, iv1;
966 : 1657611 : enum rtx_code code = GET_CODE (rhs);
967 : 1657611 : scalar_int_mode omode = mode;
968 : :
969 : 1657611 : iv->base = NULL_RTX;
970 : 1657611 : iv->step = NULL_RTX;
971 : :
972 : 1657611 : gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
973 : :
974 : 1657611 : if (CONSTANT_P (rhs)
975 : 1198833 : || REG_P (rhs)
976 : 654710 : || code == SUBREG)
977 : 1004780 : return iv_analyze_op (insn, mode, rhs, iv);
978 : :
979 : 652831 : switch (code)
980 : : {
981 : : case REG:
982 : : op0 = rhs;
983 : : break;
984 : :
985 : 10480 : case SIGN_EXTEND:
986 : 10480 : case ZERO_EXTEND:
987 : 10480 : case NEG:
988 : 10480 : op0 = XEXP (rhs, 0);
989 : : /* We don't know how many bits there are in a sign-extended constant. */
990 : 203096 : if (!is_a <scalar_int_mode> (GET_MODE (op0), &omode))
991 : : return false;
992 : : break;
993 : :
994 : 501148 : case PLUS:
995 : 501148 : case MINUS:
996 : 501148 : op0 = XEXP (rhs, 0);
997 : 501148 : op1 = XEXP (rhs, 1);
998 : 501148 : break;
999 : :
1000 : 1769 : case MULT:
1001 : 1769 : op0 = XEXP (rhs, 0);
1002 : 1769 : mby = XEXP (rhs, 1);
1003 : 1769 : if (!CONSTANT_P (mby))
1004 : 1306 : std::swap (op0, mby);
1005 : 1769 : if (!CONSTANT_P (mby))
1006 : : return false;
1007 : : break;
1008 : :
1009 : 2449 : case ASHIFT:
1010 : 2449 : op0 = XEXP (rhs, 0);
1011 : 2449 : mby = XEXP (rhs, 1);
1012 : 2449 : if (!CONSTANT_P (mby))
1013 : : return false;
1014 : : break;
1015 : :
1016 : : default:
1017 : : return false;
1018 : : }
1019 : :
1020 : 514493 : if (op0
1021 : 514493 : && !iv_analyze_expr (insn, omode, op0, &iv0))
1022 : : return false;
1023 : :
1024 : 462015 : if (op1
1025 : 462015 : && !iv_analyze_expr (insn, omode, op1, &iv1))
1026 : : return false;
1027 : :
1028 : 460794 : switch (code)
1029 : : {
1030 : 47 : case SIGN_EXTEND:
1031 : 47 : if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1032 : : return false;
1033 : : break;
1034 : :
1035 : 548 : case ZERO_EXTEND:
1036 : 548 : if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1037 : : return false;
1038 : : break;
1039 : :
1040 : 33 : case NEG:
1041 : 33 : if (!iv_neg (&iv0))
1042 : : return false;
1043 : : break;
1044 : :
1045 : 459964 : case PLUS:
1046 : 459964 : case MINUS:
1047 : 459964 : if (!iv_add (&iv0, &iv1, code))
1048 : : return false;
1049 : : break;
1050 : :
1051 : 36 : case MULT:
1052 : 36 : if (!iv_mult (&iv0, mby))
1053 : : return false;
1054 : : break;
1055 : :
1056 : 166 : case ASHIFT:
1057 : 166 : if (!iv_shift (&iv0, mby))
1058 : : return false;
1059 : : break;
1060 : :
1061 : : default:
1062 : : break;
1063 : : }
1064 : :
1065 : 460215 : *iv = iv0;
1066 : 460215 : return iv->base != NULL_RTX;
1067 : : }
1068 : :
1069 : : /* Analyzes iv DEF and stores the result to *IV. */
1070 : :
1071 : : static bool
1072 : 690393 : iv_analyze_def (df_ref def, class rtx_iv *iv)
1073 : : {
1074 : 690393 : rtx_insn *insn = DF_REF_INSN (def);
1075 : 690393 : rtx reg = DF_REF_REG (def);
1076 : 690393 : rtx set, rhs;
1077 : :
1078 : 690393 : if (dump_file)
1079 : : {
1080 : 203 : fprintf (dump_file, "Analyzing def of ");
1081 : 203 : print_rtl (dump_file, reg);
1082 : 203 : fprintf (dump_file, " in insn ");
1083 : 203 : print_rtl_single (dump_file, insn);
1084 : : }
1085 : :
1086 : 690393 : check_iv_ref_table_size ();
1087 : 690393 : if (DF_REF_IV (def))
1088 : : {
1089 : 7946 : if (dump_file)
1090 : 0 : fprintf (dump_file, " already analysed.\n");
1091 : 7946 : *iv = *DF_REF_IV (def);
1092 : 7946 : return iv->base != NULL_RTX;
1093 : : }
1094 : :
1095 : 682447 : iv->base = NULL_RTX;
1096 : 682447 : iv->step = NULL_RTX;
1097 : :
1098 : 682447 : scalar_int_mode mode;
1099 : 682803 : if (!REG_P (reg) || !is_a <scalar_int_mode> (GET_MODE (reg), &mode))
1100 : : return false;
1101 : :
1102 : 682289 : set = single_set (insn);
1103 : 682289 : if (!set)
1104 : : return false;
1105 : :
1106 : 681933 : if (!REG_P (SET_DEST (set)))
1107 : : return false;
1108 : :
1109 : 681933 : gcc_assert (SET_DEST (set) == reg);
1110 : 681933 : rhs = find_reg_equal_equiv_note (insn);
1111 : 681933 : if (rhs)
1112 : 7425 : rhs = XEXP (rhs, 0);
1113 : : else
1114 : 674508 : rhs = SET_SRC (set);
1115 : :
1116 : 681933 : iv_analyze_expr (insn, mode, rhs, iv);
1117 : 681933 : record_iv (def, iv);
1118 : :
1119 : 681933 : if (dump_file)
1120 : : {
1121 : 203 : print_rtl (dump_file, reg);
1122 : 203 : fprintf (dump_file, " in insn ");
1123 : 203 : print_rtl_single (dump_file, insn);
1124 : 203 : fprintf (dump_file, " is ");
1125 : 203 : dump_iv_info (dump_file, iv);
1126 : 203 : fprintf (dump_file, "\n");
1127 : : }
1128 : :
1129 : 681933 : return iv->base != NULL_RTX;
1130 : : }
1131 : :
1132 : : /* Analyzes operand OP of INSN and stores the result to *IV. MODE is the
1133 : : mode of OP. */
1134 : :
1135 : : static bool
1136 : 2237155 : iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, class rtx_iv *iv)
1137 : : {
1138 : 2237155 : df_ref def = NULL;
1139 : 2237155 : enum iv_grd_result res;
1140 : :
1141 : 2237155 : if (dump_file)
1142 : : {
1143 : 513 : fprintf (dump_file, "Analyzing operand ");
1144 : 513 : print_rtl (dump_file, op);
1145 : 513 : fprintf (dump_file, " of insn ");
1146 : 513 : print_rtl_single (dump_file, insn);
1147 : : }
1148 : :
1149 : 2237155 : if (function_invariant_p (op))
1150 : : res = GRD_INVARIANT;
1151 : 1593763 : else if (GET_CODE (op) == SUBREG)
1152 : : {
1153 : 14244 : scalar_int_mode inner_mode;
1154 : 14244 : if (!subreg_lowpart_p (op)
1155 : 22272 : || !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op)), &inner_mode))
1156 : : return false;
1157 : :
1158 : 13730 : if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op), iv))
1159 : : return false;
1160 : :
1161 : 5702 : return iv_subreg (iv, mode);
1162 : : }
1163 : : else
1164 : : {
1165 : 1579519 : res = iv_get_reaching_def (insn, op, &def);
1166 : 1579519 : if (res == GRD_INVALID)
1167 : : {
1168 : 119144 : if (dump_file)
1169 : 6 : fprintf (dump_file, " not simple.\n");
1170 : 119144 : return false;
1171 : : }
1172 : : }
1173 : :
1174 : 1460375 : if (res == GRD_INVARIANT)
1175 : : {
1176 : 929170 : iv_constant (iv, mode, op);
1177 : :
1178 : 929170 : if (dump_file)
1179 : : {
1180 : 221 : fprintf (dump_file, " ");
1181 : 221 : dump_iv_info (dump_file, iv);
1182 : 221 : fprintf (dump_file, "\n");
1183 : : }
1184 : 929170 : return true;
1185 : : }
1186 : :
1187 : 1174597 : if (res == GRD_MAYBE_BIV)
1188 : 536900 : return iv_analyze_biv (mode, op, iv);
1189 : :
1190 : 637697 : return iv_analyze_def (def, iv);
1191 : : }
1192 : :
1193 : : /* Analyzes value VAL at INSN and stores the result to *IV. MODE is the
1194 : : mode of VAL. */
1195 : :
1196 : : bool
1197 : 1218645 : iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, class rtx_iv *iv)
1198 : : {
1199 : 1218645 : rtx reg;
1200 : :
1201 : : /* We must find the insn in that val is used, so that we get to UD chains.
1202 : : Since the function is sometimes called on result of get_condition,
1203 : : this does not necessarily have to be directly INSN; scan also the
1204 : : following insns. */
1205 : 1218645 : if (simple_reg_p (val))
1206 : : {
1207 : 973569 : if (GET_CODE (val) == SUBREG)
1208 : 12339 : reg = SUBREG_REG (val);
1209 : : else
1210 : 973569 : reg = val;
1211 : :
1212 : 973569 : while (!df_find_use (insn, reg))
1213 : 0 : insn = NEXT_INSN (insn);
1214 : : }
1215 : :
1216 : 1218645 : return iv_analyze_op (insn, mode, val, iv);
1217 : : }
1218 : :
1219 : : /* Analyzes definition of DEF in INSN and stores the result to IV. */
1220 : :
1221 : : bool
1222 : 52696 : iv_analyze_result (rtx_insn *insn, rtx def, class rtx_iv *iv)
1223 : : {
1224 : 52696 : df_ref adef;
1225 : :
1226 : 52696 : adef = df_find_def (insn, def);
1227 : 52696 : if (!adef)
1228 : : return false;
1229 : :
1230 : 52696 : return iv_analyze_def (adef, iv);
1231 : : }
1232 : :
1233 : : /* Checks whether definition of register REG in INSN is a basic induction
1234 : : variable. MODE is the mode of REG.
1235 : :
1236 : : IV analysis must have been initialized (via a call to
1237 : : iv_analysis_loop_init) for this function to produce a result. */
1238 : :
1239 : : bool
1240 : 88690 : biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)
1241 : : {
1242 : 88690 : class rtx_iv iv;
1243 : 88690 : df_ref def, last_def;
1244 : :
1245 : 88690 : if (!simple_reg_p (reg))
1246 : : return false;
1247 : :
1248 : 84517 : def = df_find_def (insn, reg);
1249 : 84517 : gcc_assert (def != NULL);
1250 : 84517 : if (!latch_dominating_def (reg, &last_def))
1251 : : return false;
1252 : 84494 : if (last_def != def)
1253 : : return false;
1254 : :
1255 : 63578 : if (!iv_analyze_biv (mode, reg, &iv))
1256 : : return false;
1257 : :
1258 : 52697 : return iv.step != const0_rtx;
1259 : : }
1260 : :
1261 : : /* Calculates value of IV at ITERATION-th iteration. */
1262 : :
1263 : : rtx
1264 : 82 : get_iv_value (class rtx_iv *iv, rtx iteration)
1265 : : {
1266 : 82 : rtx val;
1267 : :
1268 : : /* We would need to generate some if_then_else patterns, and so far
1269 : : it is not needed anywhere. */
1270 : 82 : gcc_assert (!iv->first_special);
1271 : :
1272 : 82 : if (iv->step != const0_rtx && iteration != const0_rtx)
1273 : 0 : val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1274 : : simplify_gen_binary (MULT, iv->extend_mode,
1275 : : iv->step, iteration));
1276 : : else
1277 : 82 : val = iv->base;
1278 : :
1279 : 82 : if (iv->extend_mode == iv->mode)
1280 : : return val;
1281 : :
1282 : 0 : val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1283 : :
1284 : 0 : if (iv->extend == IV_UNKNOWN_EXTEND)
1285 : : return val;
1286 : :
1287 : 0 : val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1288 : : iv->extend_mode, val, iv->mode);
1289 : 0 : val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1290 : : simplify_gen_binary (MULT, iv->extend_mode,
1291 : : iv->mult, val));
1292 : :
1293 : 0 : return val;
1294 : : }
1295 : :
1296 : : /* Free the data for an induction variable analysis. */
1297 : :
1298 : : void
1299 : 220924 : iv_analysis_done (void)
1300 : : {
1301 : 220924 : if (!clean_slate)
1302 : : {
1303 : 188268 : clear_iv_info ();
1304 : 188268 : clean_slate = true;
1305 : 188268 : df_finish_pass (true);
1306 : 188268 : delete bivs;
1307 : 188268 : bivs = NULL;
1308 : 188268 : free (iv_ref_table);
1309 : 188268 : iv_ref_table = NULL;
1310 : 188268 : iv_ref_table_size = 0;
1311 : : }
1312 : 220924 : }
1313 : :
1314 : : /* Computes inverse to X modulo (1 << MOD). */
1315 : :
1316 : : static uint64_t
1317 : 397984 : inverse (uint64_t x, int mod)
1318 : : {
1319 : 397984 : uint64_t mask =
1320 : 397984 : ((uint64_t) 1 << (mod - 1) << 1) - 1;
1321 : 397984 : uint64_t rslt = 1;
1322 : 397984 : int i;
1323 : :
1324 : 22139724 : for (i = 0; i < mod - 1; i++)
1325 : : {
1326 : 21741740 : rslt = (rslt * x) & mask;
1327 : 21741740 : x = (x * x) & mask;
1328 : : }
1329 : :
1330 : 397984 : return rslt;
1331 : : }
1332 : :
1333 : : /* Checks whether any register in X is in set ALT. */
1334 : :
1335 : : static bool
1336 : 44376776 : altered_reg_used (const_rtx x, bitmap alt)
1337 : : {
1338 : 44376776 : subrtx_iterator::array_type array;
1339 : 279853538 : FOR_EACH_SUBRTX (iter, array, x, NONCONST)
1340 : : {
1341 : 236188246 : const_rtx x = *iter;
1342 : 236188246 : if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x)))
1343 : 711484 : return true;
1344 : : }
1345 : 43665292 : return false;
1346 : 44376776 : }
1347 : :
1348 : : /* Marks registers altered by EXPR in set ALT. */
1349 : :
1350 : : static void
1351 : 10500788 : mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1352 : : {
1353 : 10500788 : if (GET_CODE (expr) == SUBREG)
1354 : 0 : expr = SUBREG_REG (expr);
1355 : 10500788 : if (!REG_P (expr))
1356 : : return;
1357 : :
1358 : 9095967 : SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1359 : : }
1360 : :
1361 : : /* Checks whether RHS is simple enough to process. */
1362 : :
1363 : : static bool
1364 : 6936014 : simple_rhs_p (rtx rhs)
1365 : : {
1366 : 6936014 : rtx op0, op1;
1367 : :
1368 : 6936014 : if (function_invariant_p (rhs)
1369 : 6936014 : || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1370 : : return true;
1371 : :
1372 : 4535435 : switch (GET_CODE (rhs))
1373 : : {
1374 : 1356174 : case PLUS:
1375 : 1356174 : case MINUS:
1376 : 1356174 : case AND:
1377 : 1356174 : op0 = XEXP (rhs, 0);
1378 : 1356174 : op1 = XEXP (rhs, 1);
1379 : : /* Allow reg OP const and reg OP reg. */
1380 : 1257345 : if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1381 : 1430470 : && !function_invariant_p (op0))
1382 : : return false;
1383 : 605440 : if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1384 : 1192724 : && !function_invariant_p (op1))
1385 : : return false;
1386 : :
1387 : : return true;
1388 : :
1389 : 617158 : case ASHIFT:
1390 : 617158 : case ASHIFTRT:
1391 : 617158 : case LSHIFTRT:
1392 : 617158 : case MULT:
1393 : 617158 : op0 = XEXP (rhs, 0);
1394 : 617158 : op1 = XEXP (rhs, 1);
1395 : : /* Allow reg OP const. */
1396 : 617158 : if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1397 : : return false;
1398 : 601578 : if (!function_invariant_p (op1))
1399 : : return false;
1400 : :
1401 : : return true;
1402 : :
1403 : : default:
1404 : : return false;
1405 : : }
1406 : : }
1407 : :
1408 : : /* If any registers in *EXPR that have a single definition, try to replace
1409 : : them with the known-equivalent values. */
1410 : :
1411 : : static void
1412 : 2437849 : replace_single_def_regs (rtx *expr)
1413 : : {
1414 : 2437849 : subrtx_var_iterator::array_type array;
1415 : 2511825 : repeat:
1416 : 15469582 : FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)
1417 : : {
1418 : 13031733 : rtx x = *iter;
1419 : 13031733 : if (REG_P (x))
1420 : 3709215 : if (rtx new_x = df_find_single_def_src (x))
1421 : : {
1422 : 73976 : *expr = simplify_replace_rtx (*expr, x, new_x);
1423 : 73976 : goto repeat;
1424 : : }
1425 : : }
1426 : 2437849 : }
1427 : :
1428 : : /* A subroutine of simplify_using_initial_values, this function examines INSN
1429 : : to see if it contains a suitable set that we can use to make a replacement.
1430 : : If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1431 : : the set; return false otherwise. */
1432 : :
1433 : : static bool
1434 : 16807803 : suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src)
1435 : : {
1436 : 16807803 : rtx set = single_set (insn);
1437 : 16807803 : rtx lhs = NULL_RTX, rhs;
1438 : :
1439 : 16807803 : if (!set)
1440 : : return false;
1441 : :
1442 : 8339448 : lhs = SET_DEST (set);
1443 : 8339448 : if (!REG_P (lhs))
1444 : : return false;
1445 : :
1446 : 6936014 : rhs = find_reg_equal_equiv_note (insn);
1447 : 6936014 : if (rhs)
1448 : 433253 : rhs = XEXP (rhs, 0);
1449 : : else
1450 : 6502761 : rhs = SET_SRC (set);
1451 : :
1452 : 6936014 : if (!simple_rhs_p (rhs))
1453 : : return false;
1454 : :
1455 : 4103190 : *dest = lhs;
1456 : 4103190 : *src = rhs;
1457 : 4103190 : return true;
1458 : : }
1459 : :
1460 : : /* Using the data returned by suitable_set_for_replacement, replace DEST
1461 : : with SRC in *EXPR and return the new expression. Also call
1462 : : replace_single_def_regs if the replacement changed something. */
1463 : : static void
1464 : 5455079 : replace_in_expr (rtx *expr, rtx dest, rtx src)
1465 : : {
1466 : 5455079 : rtx old = *expr;
1467 : 5455079 : *expr = simplify_replace_rtx (*expr, dest, src);
1468 : 5455079 : if (old == *expr)
1469 : : return;
1470 : 1215267 : replace_single_def_regs (expr);
1471 : : }
1472 : :
1473 : : /* Checks whether A implies B. */
1474 : :
1475 : : static bool
1476 : 2204492 : implies_p (rtx a, rtx b)
1477 : : {
1478 : 2204492 : rtx op0, op1, opb0, opb1;
1479 : 2204492 : machine_mode mode;
1480 : :
1481 : 2204492 : if (rtx_equal_p (a, b))
1482 : : return true;
1483 : :
1484 : 2200850 : if (GET_CODE (a) == EQ)
1485 : : {
1486 : 415884 : op0 = XEXP (a, 0);
1487 : 415884 : op1 = XEXP (a, 1);
1488 : :
1489 : 415884 : if (REG_P (op0)
1490 : 229645 : || (GET_CODE (op0) == SUBREG
1491 : 4420 : && REG_P (SUBREG_REG (op0))))
1492 : : {
1493 : 189525 : rtx r = simplify_replace_rtx (b, op0, op1);
1494 : 189525 : if (r == const_true_rtx)
1495 : : return true;
1496 : : }
1497 : :
1498 : 400359 : if (REG_P (op1)
1499 : 315726 : || (GET_CODE (op1) == SUBREG
1500 : 1388 : && REG_P (SUBREG_REG (op1))))
1501 : : {
1502 : 86021 : rtx r = simplify_replace_rtx (b, op1, op0);
1503 : 86021 : if (r == const_true_rtx)
1504 : : return true;
1505 : : }
1506 : : }
1507 : :
1508 : 2185301 : if (b == const_true_rtx)
1509 : : return true;
1510 : :
1511 : 2185301 : if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1512 : : && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1513 : 2177589 : || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1514 : : && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1515 : : return false;
1516 : :
1517 : 2157909 : op0 = XEXP (a, 0);
1518 : 2157909 : op1 = XEXP (a, 1);
1519 : 2157909 : opb0 = XEXP (b, 0);
1520 : 2157909 : opb1 = XEXP (b, 1);
1521 : :
1522 : 2157909 : mode = GET_MODE (op0);
1523 : 2157909 : if (mode != GET_MODE (opb0))
1524 : : mode = VOIDmode;
1525 : 1851787 : else if (mode == VOIDmode)
1526 : : {
1527 : 0 : mode = GET_MODE (op1);
1528 : 0 : if (mode != GET_MODE (opb1))
1529 : 306122 : mode = VOIDmode;
1530 : : }
1531 : :
1532 : : /* A < B implies A + 1 <= B. */
1533 : 2157909 : if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1534 : 470223 : && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1535 : : {
1536 : :
1537 : 32384 : if (GET_CODE (a) == GT)
1538 : 19425 : std::swap (op0, op1);
1539 : :
1540 : 32384 : if (GET_CODE (b) == GE)
1541 : 12766 : std::swap (opb0, opb1);
1542 : :
1543 : 32384 : if (SCALAR_INT_MODE_P (mode)
1544 : 31733 : && rtx_equal_p (op1, opb1)
1545 : 34925 : && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1546 : : return true;
1547 : 32144 : return false;
1548 : : }
1549 : :
1550 : : /* A < B or A > B imply A != B. TODO: Likewise
1551 : : A + n < B implies A != B + n if neither wraps. */
1552 : 2125525 : if (GET_CODE (b) == NE
1553 : : && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1554 : : || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1555 : : {
1556 : 161388 : if (rtx_equal_p (op0, opb0)
1557 : 161388 : && rtx_equal_p (op1, opb1))
1558 : : return true;
1559 : : }
1560 : :
1561 : : /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1562 : 2099298 : if (GET_CODE (a) == NE
1563 : 557039 : && op1 == const0_rtx)
1564 : : {
1565 : 325544 : if ((GET_CODE (b) == GTU
1566 : 27356 : && opb1 == const0_rtx)
1567 : 325544 : || (GET_CODE (b) == GEU
1568 : 7127 : && opb1 == const1_rtx))
1569 : 0 : return rtx_equal_p (op0, opb0);
1570 : : }
1571 : :
1572 : : /* A != N is equivalent to A - (N + 1) <u -1. */
1573 : 2099298 : if (GET_CODE (a) == NE
1574 : 557039 : && CONST_INT_P (op1)
1575 : 413067 : && GET_CODE (b) == LTU
1576 : 66262 : && opb1 == constm1_rtx
1577 : 24255 : && GET_CODE (opb0) == PLUS
1578 : 7053 : && CONST_INT_P (XEXP (opb0, 1))
1579 : : /* Avoid overflows. */
1580 : 416 : && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1581 : : != (HOST_WIDE_INT_1U
1582 : : << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1583 : 416 : && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1584 : 195 : return rtx_equal_p (op0, XEXP (opb0, 0));
1585 : :
1586 : : /* Likewise, A != N implies A - N > 0. */
1587 : 2099103 : if (GET_CODE (a) == NE
1588 : 556844 : && CONST_INT_P (op1))
1589 : : {
1590 : 412872 : if (GET_CODE (b) == GTU
1591 : 41057 : && GET_CODE (opb0) == PLUS
1592 : 20514 : && opb1 == const0_rtx
1593 : 0 : && CONST_INT_P (XEXP (opb0, 1))
1594 : : /* Avoid overflows. */
1595 : 0 : && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1596 : : != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
1597 : 412872 : && rtx_equal_p (XEXP (opb0, 0), op0))
1598 : 0 : return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1599 : 412872 : if (GET_CODE (b) == GEU
1600 : 9671 : && GET_CODE (opb0) == PLUS
1601 : 3306 : && opb1 == const1_rtx
1602 : 0 : && CONST_INT_P (XEXP (opb0, 1))
1603 : : /* Avoid overflows. */
1604 : 0 : && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1605 : : != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
1606 : 412872 : && rtx_equal_p (XEXP (opb0, 0), op0))
1607 : 0 : return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1608 : : }
1609 : :
1610 : : /* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1611 : 2099103 : if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1612 : 294222 : && CONST_INT_P (op1)
1613 : 212166 : && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1614 : 184739 : || INTVAL (op1) >= 0)
1615 : 201398 : && GET_CODE (b) == LTU
1616 : 12479 : && CONST_INT_P (opb1)
1617 : 2111186 : && rtx_equal_p (op0, opb0))
1618 : 1013 : return INTVAL (opb1) < 0;
1619 : :
1620 : : return false;
1621 : : }
1622 : :
1623 : : /* Canonicalizes COND so that
1624 : :
1625 : : (1) Ensure that operands are ordered according to
1626 : : swap_commutative_operands_p.
1627 : : (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1628 : : for GE, GEU, and LEU. */
1629 : :
1630 : : rtx
1631 : 2181135 : canon_condition (rtx cond)
1632 : : {
1633 : 2181135 : rtx op0, op1;
1634 : 2181135 : enum rtx_code code;
1635 : 2181135 : machine_mode mode;
1636 : :
1637 : 2181135 : code = GET_CODE (cond);
1638 : 2181135 : op0 = XEXP (cond, 0);
1639 : 2181135 : op1 = XEXP (cond, 1);
1640 : :
1641 : 2181135 : if (swap_commutative_operands_p (op0, op1))
1642 : : {
1643 : 208914 : code = swap_condition (code);
1644 : 208914 : std::swap (op0, op1);
1645 : : }
1646 : :
1647 : 2181135 : mode = GET_MODE (op0);
1648 : 2181135 : if (mode == VOIDmode)
1649 : 0 : mode = GET_MODE (op1);
1650 : 2181135 : gcc_assert (mode != VOIDmode);
1651 : :
1652 : 2181135 : if (CONST_SCALAR_INT_P (op1) && GET_MODE_CLASS (mode) != MODE_CC)
1653 : : {
1654 : 1570108 : rtx_mode_t const_val (op1, mode);
1655 : :
1656 : 1570108 : switch (code)
1657 : : {
1658 : 85760 : case LE:
1659 : 85760 : if (wi::ne_p (const_val, wi::max_value (mode, SIGNED)))
1660 : : {
1661 : 85760 : code = LT;
1662 : 85760 : op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1663 : : }
1664 : : break;
1665 : :
1666 : 116908 : case GE:
1667 : 116908 : if (wi::ne_p (const_val, wi::min_value (mode, SIGNED)))
1668 : : {
1669 : 116908 : code = GT;
1670 : 116908 : op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1671 : : }
1672 : : break;
1673 : :
1674 : 45033 : case LEU:
1675 : 45033 : if (wi::ne_p (const_val, -1))
1676 : : {
1677 : 45033 : code = LTU;
1678 : 45033 : op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1679 : : }
1680 : : break;
1681 : :
1682 : 150755 : case GEU:
1683 : 150755 : if (wi::ne_p (const_val, 0))
1684 : : {
1685 : 150755 : code = GTU;
1686 : 150755 : op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1687 : : }
1688 : : break;
1689 : :
1690 : : default:
1691 : : break;
1692 : : }
1693 : : }
1694 : :
1695 : 2181135 : if (op0 != XEXP (cond, 0)
1696 : 1972221 : || op1 != XEXP (cond, 1)
1697 : 1632035 : || code != GET_CODE (cond)
1698 : 1632035 : || GET_MODE (cond) != SImode)
1699 : 1617780 : cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1700 : :
1701 : 2181135 : return cond;
1702 : : }
1703 : :
1704 : : /* Reverses CONDition; returns NULL if we cannot. */
1705 : :
1706 : : static rtx
1707 : 1901852 : reversed_condition (rtx cond)
1708 : : {
1709 : 1901852 : enum rtx_code reversed;
1710 : 1901852 : reversed = reversed_comparison_code (cond, NULL);
1711 : 1901852 : if (reversed == UNKNOWN)
1712 : : return NULL_RTX;
1713 : : else
1714 : 1893875 : return gen_rtx_fmt_ee (reversed,
1715 : : GET_MODE (cond), XEXP (cond, 0),
1716 : : XEXP (cond, 1));
1717 : : }
1718 : :
1719 : : /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1720 : : set of altered regs. */
1721 : :
1722 : : void
1723 : 1324740 : simplify_using_condition (rtx cond, rtx *expr, regset altered)
1724 : : {
1725 : 1324740 : rtx rev, reve, exp = *expr;
1726 : :
1727 : : /* If some register gets altered later, we do not really speak about its
1728 : : value at the time of comparison. */
1729 : 1324740 : if (altered && altered_reg_used (cond, altered))
1730 : : return;
1731 : :
1732 : 1308846 : if (GET_CODE (cond) == EQ
1733 : 220159 : && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1734 : : {
1735 : 78086 : *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1736 : 78086 : return;
1737 : : }
1738 : :
1739 : 1230760 : if (!COMPARISON_P (exp))
1740 : : return;
1741 : :
1742 : 545619 : rev = reversed_condition (cond);
1743 : 545619 : reve = reversed_condition (exp);
1744 : :
1745 : 545619 : cond = canon_condition (cond);
1746 : 545619 : exp = canon_condition (exp);
1747 : 545619 : if (rev)
1748 : 544278 : rev = canon_condition (rev);
1749 : 545619 : if (reve)
1750 : 545619 : reve = canon_condition (reve);
1751 : :
1752 : 545619 : if (rtx_equal_p (exp, cond))
1753 : : {
1754 : 8299 : *expr = const_true_rtx;
1755 : 8299 : return;
1756 : : }
1757 : :
1758 : 537320 : if (rev && rtx_equal_p (exp, rev))
1759 : : {
1760 : 5669 : *expr = const0_rtx;
1761 : 5669 : return;
1762 : : }
1763 : :
1764 : 531651 : if (implies_p (cond, exp))
1765 : : {
1766 : 27381 : *expr = const_true_rtx;
1767 : 27381 : return;
1768 : : }
1769 : :
1770 : 504270 : if (reve && implies_p (cond, reve))
1771 : : {
1772 : 287 : *expr = const0_rtx;
1773 : 287 : return;
1774 : : }
1775 : :
1776 : : /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
1777 : : be false. */
1778 : 503983 : if (rev && implies_p (exp, rev))
1779 : : {
1780 : 5785 : *expr = const0_rtx;
1781 : 5785 : return;
1782 : : }
1783 : :
1784 : : /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
1785 : 498198 : if (rev && reve && implies_p (reve, rev))
1786 : : {
1787 : 1439 : *expr = const_true_rtx;
1788 : 1439 : return;
1789 : : }
1790 : :
1791 : : /* We would like to have some other tests here. TODO. */
1792 : :
1793 : : return;
1794 : : }
1795 : :
1796 : : /* Use relationship between A and *B to eventually eliminate *B.
1797 : : OP is the operation we consider. */
1798 : :
1799 : : static void
1800 : 169072 : eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1801 : : {
1802 : 169072 : switch (op)
1803 : : {
1804 : 0 : case AND:
1805 : : /* If A implies *B, we may replace *B by true. */
1806 : 0 : if (implies_p (a, *b))
1807 : 0 : *b = const_true_rtx;
1808 : : break;
1809 : :
1810 : 169072 : case IOR:
1811 : : /* If *B implies A, we may replace *B by false. */
1812 : 169072 : if (implies_p (*b, a))
1813 : 11968 : *b = const0_rtx;
1814 : : break;
1815 : :
1816 : 0 : default:
1817 : 0 : gcc_unreachable ();
1818 : : }
1819 : 169072 : }
1820 : :
1821 : : /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1822 : : operation we consider. */
1823 : :
1824 : : static void
1825 : 705970 : eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1826 : : {
1827 : 705970 : rtx elt;
1828 : :
1829 : 790506 : for (elt = tail; elt; elt = XEXP (elt, 1))
1830 : 84536 : eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1831 : 790506 : for (elt = tail; elt; elt = XEXP (elt, 1))
1832 : 84536 : eliminate_implied_condition (op, XEXP (elt, 0), head);
1833 : 705970 : }
1834 : :
1835 : : /* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
1836 : : is a list, its elements are assumed to be combined using OP. */
1837 : :
1838 : : static void
1839 : 5044939 : simplify_using_initial_values (class loop *loop, enum rtx_code op, rtx *expr)
1840 : : {
1841 : 5044939 : bool expression_valid;
1842 : 5044939 : rtx head, tail, last_valid_expr;
1843 : 5044939 : rtx_expr_list *cond_list;
1844 : 5044939 : rtx_insn *insn;
1845 : 5044939 : rtx neutral, aggr;
1846 : 5044939 : regset altered, this_altered;
1847 : 5044939 : edge e;
1848 : :
1849 : 5044939 : if (!*expr)
1850 : 3822357 : return;
1851 : :
1852 : 2485221 : if (CONSTANT_P (*expr))
1853 : : return;
1854 : :
1855 : 1928552 : if (GET_CODE (*expr) == EXPR_LIST)
1856 : : {
1857 : 705970 : head = XEXP (*expr, 0);
1858 : 705970 : tail = XEXP (*expr, 1);
1859 : :
1860 : 705970 : eliminate_implied_conditions (op, &head, tail);
1861 : :
1862 : 705970 : switch (op)
1863 : : {
1864 : 4920 : case AND:
1865 : 4920 : neutral = const_true_rtx;
1866 : 4920 : aggr = const0_rtx;
1867 : 4920 : break;
1868 : :
1869 : 701050 : case IOR:
1870 : 701050 : neutral = const0_rtx;
1871 : 701050 : aggr = const_true_rtx;
1872 : 701050 : break;
1873 : :
1874 : 0 : default:
1875 : 0 : gcc_unreachable ();
1876 : : }
1877 : :
1878 : 705970 : simplify_using_initial_values (loop, UNKNOWN, &head);
1879 : 705970 : if (head == aggr)
1880 : : {
1881 : 110 : XEXP (*expr, 0) = aggr;
1882 : 110 : XEXP (*expr, 1) = NULL_RTX;
1883 : 110 : return;
1884 : : }
1885 : 705860 : else if (head == neutral)
1886 : : {
1887 : 387372 : *expr = tail;
1888 : 387372 : simplify_using_initial_values (loop, op, expr);
1889 : 387372 : return;
1890 : : }
1891 : 318488 : simplify_using_initial_values (loop, op, &tail);
1892 : :
1893 : 318488 : if (tail && XEXP (tail, 0) == aggr)
1894 : : {
1895 : 0 : *expr = tail;
1896 : 0 : return;
1897 : : }
1898 : :
1899 : 318488 : XEXP (*expr, 0) = head;
1900 : 318488 : XEXP (*expr, 1) = tail;
1901 : 318488 : return;
1902 : : }
1903 : :
1904 : 1222582 : gcc_assert (op == UNKNOWN);
1905 : :
1906 : 1222582 : replace_single_def_regs (expr);
1907 : 1222582 : if (CONSTANT_P (*expr))
1908 : : return;
1909 : :
1910 : 1222582 : e = loop_preheader_edge (loop);
1911 : 1222582 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1912 : : return;
1913 : :
1914 : 1222582 : altered = ALLOC_REG_SET (®_obstack);
1915 : 1222582 : this_altered = ALLOC_REG_SET (®_obstack);
1916 : :
1917 : 1222582 : expression_valid = true;
1918 : 1222582 : last_valid_expr = *expr;
1919 : 1222582 : cond_list = NULL;
1920 : 2257357 : while (1)
1921 : : {
1922 : 2257357 : insn = BB_END (e->src);
1923 : 2257357 : if (any_condjump_p (insn) && onlyjump_p (insn))
1924 : : {
1925 : 988484 : rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1926 : :
1927 : 988484 : if (cond && (e->flags & EDGE_FALLTHRU))
1928 : 623541 : cond = reversed_condition (cond);
1929 : 978900 : if (cond)
1930 : : {
1931 : 975860 : rtx old = *expr;
1932 : 975860 : simplify_using_condition (cond, expr, altered);
1933 : 975860 : if (old != *expr)
1934 : : {
1935 : 43056 : rtx note;
1936 : 43056 : if (CONSTANT_P (*expr))
1937 : 42415 : goto out;
1938 : 998 : for (note = cond_list; note; note = XEXP (note, 1))
1939 : : {
1940 : 477 : simplify_using_condition (XEXP (note, 0), expr, altered);
1941 : 477 : if (CONSTANT_P (*expr))
1942 : 120 : goto out;
1943 : : }
1944 : : }
1945 : 933325 : cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1946 : : }
1947 : : }
1948 : :
1949 : 20621433 : FOR_BB_INSNS_REVERSE (e->src, insn)
1950 : : {
1951 : 19139194 : rtx src, dest;
1952 : 19139194 : rtx old = *expr;
1953 : :
1954 : 19139194 : if (!INSN_P (insn))
1955 : 2331391 : continue;
1956 : :
1957 : 16807803 : CLEAR_REG_SET (this_altered);
1958 : 16807803 : note_stores (insn, mark_altered, this_altered);
1959 : 16807803 : if (CALL_P (insn))
1960 : : {
1961 : : /* Kill all registers that might be clobbered by the call.
1962 : : We don't track modes of hard registers, so we need to be
1963 : : conservative and assume that partial kills are full kills. */
1964 : 144281 : function_abi callee_abi = insn_callee_abi (insn);
1965 : 144281 : IOR_REG_SET_HRS (this_altered,
1966 : : callee_abi.full_and_partial_reg_clobbers ());
1967 : : }
1968 : :
1969 : 16807803 : if (suitable_set_for_replacement (insn, &dest, &src))
1970 : : {
1971 : 4103190 : rtx_expr_list **pnote, **pnote_next;
1972 : :
1973 : 4103190 : replace_in_expr (expr, dest, src);
1974 : 4103190 : if (CONSTANT_P (*expr))
1975 : 732583 : goto out;
1976 : :
1977 : 5134673 : for (pnote = &cond_list; *pnote; pnote = pnote_next)
1978 : : {
1979 : 1351889 : rtx_expr_list *note = *pnote;
1980 : 1351889 : rtx old_cond = XEXP (note, 0);
1981 : :
1982 : 1351889 : pnote_next = (rtx_expr_list **)&XEXP (note, 1);
1983 : 1351889 : replace_in_expr (&XEXP (note, 0), dest, src);
1984 : :
1985 : : /* We can no longer use a condition that has been simplified
1986 : : to a constant, and simplify_using_condition will abort if
1987 : : we try. */
1988 : 1351889 : if (CONSTANT_P (XEXP (note, 0)))
1989 : : {
1990 : 24 : *pnote = *pnote_next;
1991 : 24 : pnote_next = pnote;
1992 : 24 : free_EXPR_LIST_node (note);
1993 : : }
1994 : : /* Retry simplifications with this condition if either the
1995 : : expression or the condition changed. */
1996 : 1351865 : else if (old_cond != XEXP (note, 0) || old != *expr)
1997 : 348403 : simplify_using_condition (XEXP (note, 0), expr, altered);
1998 : : }
1999 : : }
2000 : : else
2001 : : {
2002 : 12704613 : rtx_expr_list **pnote, **pnote_next;
2003 : :
2004 : : /* If we did not use this insn to make a replacement, any overlap
2005 : : between stores in this insn and our expression will cause the
2006 : : expression to become invalid. */
2007 : 12704613 : if (altered_reg_used (*expr, this_altered))
2008 : 405127 : goto out;
2009 : :
2010 : : /* Likewise for the conditions. */
2011 : 26571689 : for (pnote = &cond_list; *pnote; pnote = pnote_next)
2012 : : {
2013 : 14272203 : rtx_expr_list *note = *pnote;
2014 : 14272203 : rtx old_cond = XEXP (note, 0);
2015 : :
2016 : 14272203 : pnote_next = (rtx_expr_list **)&XEXP (note, 1);
2017 : 14272203 : if (altered_reg_used (old_cond, this_altered))
2018 : : {
2019 : 199039 : *pnote = *pnote_next;
2020 : 199039 : pnote_next = pnote;
2021 : 199039 : free_EXPR_LIST_node (note);
2022 : : }
2023 : : }
2024 : : }
2025 : :
2026 : 16082270 : if (CONSTANT_P (*expr))
2027 : 7050 : goto out;
2028 : :
2029 : 16075220 : IOR_REG_SET (altered, this_altered);
2030 : :
2031 : : /* If the expression now contains regs that have been altered, we
2032 : : can't return it to the caller. However, it is still valid for
2033 : : further simplification, so keep searching to see if we can
2034 : : eventually turn it into a constant. */
2035 : 16075220 : if (altered_reg_used (*expr, altered))
2036 : : expression_valid = false;
2037 : 15983796 : if (expression_valid)
2038 : 15982555 : last_valid_expr = *expr;
2039 : : }
2040 : :
2041 : 1482239 : if (!single_pred_p (e->src)
2042 : 1482239 : || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2043 : : break;
2044 : : e = single_pred_edge (e->src);
2045 : : }
2046 : :
2047 : 1222582 : out:
2048 : 1222582 : free_EXPR_LIST_list (&cond_list);
2049 : 1222582 : if (!CONSTANT_P (*expr))
2050 : 852591 : *expr = last_valid_expr;
2051 : 1222582 : FREE_REG_SET (altered);
2052 : 1222582 : FREE_REG_SET (this_altered);
2053 : : }
2054 : :
2055 : : /* Transforms invariant IV into MODE. Adds assumptions based on the fact
2056 : : that IV occurs as left operands of comparison COND and its signedness
2057 : : is SIGNED_P to DESC. */
2058 : :
2059 : : static void
2060 : 1 : shorten_into_mode (class rtx_iv *iv, scalar_int_mode mode,
2061 : : enum rtx_code cond, bool signed_p, class niter_desc *desc)
2062 : : {
2063 : 1 : rtx mmin, mmax, cond_over, cond_under;
2064 : :
2065 : 1 : get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2066 : 1 : cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2067 : : iv->base, mmin);
2068 : 1 : cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2069 : : iv->base, mmax);
2070 : :
2071 : 1 : switch (cond)
2072 : : {
2073 : 0 : case LE:
2074 : 0 : case LT:
2075 : 0 : case LEU:
2076 : 0 : case LTU:
2077 : 0 : if (cond_under != const0_rtx)
2078 : 0 : desc->infinite =
2079 : 0 : alloc_EXPR_LIST (0, cond_under, desc->infinite);
2080 : 0 : if (cond_over != const0_rtx)
2081 : 0 : desc->noloop_assumptions =
2082 : 0 : alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2083 : : break;
2084 : :
2085 : 1 : case GE:
2086 : 1 : case GT:
2087 : 1 : case GEU:
2088 : 1 : case GTU:
2089 : 1 : if (cond_over != const0_rtx)
2090 : 1 : desc->infinite =
2091 : 1 : alloc_EXPR_LIST (0, cond_over, desc->infinite);
2092 : 1 : if (cond_under != const0_rtx)
2093 : 1 : desc->noloop_assumptions =
2094 : 1 : alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2095 : : break;
2096 : :
2097 : 0 : case NE:
2098 : 0 : if (cond_over != const0_rtx)
2099 : 0 : desc->infinite =
2100 : 0 : alloc_EXPR_LIST (0, cond_over, desc->infinite);
2101 : 0 : if (cond_under != const0_rtx)
2102 : 0 : desc->infinite =
2103 : 0 : alloc_EXPR_LIST (0, cond_under, desc->infinite);
2104 : : break;
2105 : :
2106 : 0 : default:
2107 : 0 : gcc_unreachable ();
2108 : : }
2109 : :
2110 : 1 : iv->mode = mode;
2111 : 1 : iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2112 : 1 : }
2113 : :
2114 : : /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2115 : : subregs of the same mode if possible (sometimes it is necessary to add
2116 : : some assumptions to DESC). */
2117 : :
2118 : : static bool
2119 : 433799 : canonicalize_iv_subregs (class rtx_iv *iv0, class rtx_iv *iv1,
2120 : : enum rtx_code cond, class niter_desc *desc)
2121 : : {
2122 : 433799 : scalar_int_mode comp_mode;
2123 : 433799 : bool signed_p;
2124 : :
2125 : : /* If the ivs behave specially in the first iteration, or are
2126 : : added/multiplied after extending, we ignore them. */
2127 : 433799 : if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2128 : : return false;
2129 : 433798 : if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2130 : : return false;
2131 : :
2132 : : /* If there is some extend, it must match signedness of the comparison. */
2133 : 433798 : switch (cond)
2134 : : {
2135 : 31413 : case LE:
2136 : 31413 : case LT:
2137 : 31413 : if (iv0->extend == IV_ZERO_EXTEND
2138 : 31413 : || iv1->extend == IV_ZERO_EXTEND)
2139 : : return false;
2140 : : signed_p = true;
2141 : : break;
2142 : :
2143 : 37976 : case LEU:
2144 : 37976 : case LTU:
2145 : 37976 : if (iv0->extend == IV_SIGN_EXTEND
2146 : 37976 : || iv1->extend == IV_SIGN_EXTEND)
2147 : : return false;
2148 : : signed_p = false;
2149 : : break;
2150 : :
2151 : 364409 : case NE:
2152 : 364409 : if (iv0->extend != IV_UNKNOWN_EXTEND
2153 : 0 : && iv1->extend != IV_UNKNOWN_EXTEND
2154 : 0 : && iv0->extend != iv1->extend)
2155 : : return false;
2156 : :
2157 : 364409 : signed_p = false;
2158 : 364409 : if (iv0->extend != IV_UNKNOWN_EXTEND)
2159 : 0 : signed_p = iv0->extend == IV_SIGN_EXTEND;
2160 : 364409 : if (iv1->extend != IV_UNKNOWN_EXTEND)
2161 : 0 : signed_p = iv1->extend == IV_SIGN_EXTEND;
2162 : : break;
2163 : :
2164 : 0 : default:
2165 : 0 : gcc_unreachable ();
2166 : : }
2167 : :
2168 : : /* Values of both variables should be computed in the same mode. These
2169 : : might indeed be different, if we have comparison like
2170 : :
2171 : : (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2172 : :
2173 : : and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2174 : : in different modes. This does not seem impossible to handle, but
2175 : : it hardly ever occurs in practice.
2176 : :
2177 : : The only exception is the case when one of operands is invariant.
2178 : : For example pentium 3 generates comparisons like
2179 : : (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2180 : : definitely do not want this prevent the optimization. */
2181 : 433798 : comp_mode = iv0->extend_mode;
2182 : 1301394 : if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2183 : 433798 : comp_mode = iv1->extend_mode;
2184 : :
2185 : 433798 : if (iv0->extend_mode != comp_mode)
2186 : : {
2187 : 266 : if (iv0->mode != iv0->extend_mode
2188 : 266 : || iv0->step != const0_rtx)
2189 : : return false;
2190 : :
2191 : 266 : iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2192 : : comp_mode, iv0->base, iv0->mode);
2193 : 266 : iv0->extend_mode = comp_mode;
2194 : : }
2195 : :
2196 : 433798 : if (iv1->extend_mode != comp_mode)
2197 : : {
2198 : 5328 : if (iv1->mode != iv1->extend_mode
2199 : 5328 : || iv1->step != const0_rtx)
2200 : : return false;
2201 : :
2202 : 5322 : iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2203 : : comp_mode, iv1->base, iv1->mode);
2204 : 5322 : iv1->extend_mode = comp_mode;
2205 : : }
2206 : :
2207 : : /* Check that both ivs belong to a range of a single mode. If one of the
2208 : : operands is an invariant, we may need to shorten it into the common
2209 : : mode. */
2210 : 433792 : if (iv0->mode == iv0->extend_mode
2211 : 428203 : && iv0->step == const0_rtx
2212 : 558244 : && iv0->mode != iv1->mode)
2213 : 0 : shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2214 : :
2215 : 433792 : if (iv1->mode == iv1->extend_mode
2216 : 428204 : && iv1->step == const0_rtx
2217 : 741470 : && iv0->mode != iv1->mode)
2218 : 1 : shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2219 : :
2220 : 433792 : if (iv0->mode != iv1->mode)
2221 : : return false;
2222 : :
2223 : 433792 : desc->mode = iv0->mode;
2224 : 433792 : desc->signed_p = signed_p;
2225 : :
2226 : 433792 : return true;
2227 : : }
2228 : :
2229 : : /* Tries to estimate the maximum number of iterations in LOOP, and return the
2230 : : result. This function is called from iv_number_of_iterations with
2231 : : a number of fields in DESC already filled in. OLD_NITER is the original
2232 : : expression for the number of iterations, before we tried to simplify it. */
2233 : :
2234 : : static uint64_t
2235 : 220013 : determine_max_iter (class loop *loop, class niter_desc *desc, rtx old_niter)
2236 : : {
2237 : 220013 : rtx niter = desc->niter_expr;
2238 : 220013 : rtx mmin, mmax, cmp;
2239 : 220013 : uint64_t nmax, inc;
2240 : 220013 : uint64_t andmax = 0;
2241 : :
2242 : : /* We used to look for constant operand 0 of AND,
2243 : : but canonicalization should always make this impossible. */
2244 : 220013 : gcc_checking_assert (GET_CODE (niter) != AND
2245 : : || !CONST_INT_P (XEXP (niter, 0)));
2246 : :
2247 : 220013 : if (GET_CODE (niter) == AND
2248 : 10005 : && CONST_INT_P (XEXP (niter, 1)))
2249 : : {
2250 : 10005 : andmax = UINTVAL (XEXP (niter, 1));
2251 : 10005 : niter = XEXP (niter, 0);
2252 : : }
2253 : :
2254 : 220013 : get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2255 : 220013 : nmax = UINTVAL (mmax) - UINTVAL (mmin);
2256 : :
2257 : 220013 : if (GET_CODE (niter) == UDIV)
2258 : : {
2259 : 2772 : if (!CONST_INT_P (XEXP (niter, 1)))
2260 : : return nmax;
2261 : 2772 : inc = INTVAL (XEXP (niter, 1));
2262 : 2772 : niter = XEXP (niter, 0);
2263 : : }
2264 : : else
2265 : : inc = 1;
2266 : :
2267 : : /* We could use a binary search here, but for now improving the upper
2268 : : bound by just one eliminates one important corner case. */
2269 : 220013 : cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2270 : : desc->mode, old_niter, mmax);
2271 : 220013 : simplify_using_initial_values (loop, UNKNOWN, &cmp);
2272 : 220013 : if (cmp == const_true_rtx)
2273 : : {
2274 : 125936 : nmax--;
2275 : :
2276 : 125936 : if (dump_file)
2277 : 15 : fprintf (dump_file, ";; improved upper bound by one.\n");
2278 : : }
2279 : 220013 : nmax /= inc;
2280 : 220013 : if (andmax)
2281 : 10005 : nmax = MIN (nmax, andmax);
2282 : 220013 : if (dump_file)
2283 : 24 : fprintf (dump_file, ";; Determined upper bound %" PRId64".\n",
2284 : : nmax);
2285 : : return nmax;
2286 : : }
2287 : :
2288 : : /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2289 : : the result into DESC. Very similar to determine_number_of_iterations
2290 : : (basically its rtl version), complicated by things like subregs. */
2291 : :
2292 : : static void
2293 : 744107 : iv_number_of_iterations (class loop *loop, rtx_insn *insn, rtx condition,
2294 : : class niter_desc *desc)
2295 : : {
2296 : 744107 : rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2297 : 744107 : class rtx_iv iv0, iv1;
2298 : 744107 : rtx assumption, may_not_xform;
2299 : 744107 : enum rtx_code cond;
2300 : 744107 : machine_mode nonvoid_mode;
2301 : 744107 : scalar_int_mode comp_mode;
2302 : 744107 : rtx mmin, mmax, mode_mmin, mode_mmax;
2303 : 744107 : uint64_t s, size, d, inv, max, up, down;
2304 : 744107 : int64_t inc, step_val;
2305 : 744107 : int was_sharp = false;
2306 : 744107 : rtx old_niter;
2307 : 744107 : bool step_is_pow2;
2308 : :
2309 : : /* The meaning of these assumptions is this:
2310 : : if !assumptions
2311 : : then the rest of information does not have to be valid
2312 : : if noloop_assumptions then the loop does not roll
2313 : : if infinite then this exit is never used */
2314 : :
2315 : 744107 : desc->assumptions = NULL_RTX;
2316 : 744107 : desc->noloop_assumptions = NULL_RTX;
2317 : 744107 : desc->infinite = NULL_RTX;
2318 : 744107 : desc->simple_p = true;
2319 : :
2320 : 744107 : desc->const_iter = false;
2321 : 744107 : desc->niter_expr = NULL_RTX;
2322 : :
2323 : 744107 : cond = GET_CODE (condition);
2324 : 744107 : gcc_assert (COMPARISON_P (condition));
2325 : :
2326 : 744107 : nonvoid_mode = GET_MODE (XEXP (condition, 0));
2327 : 744107 : if (nonvoid_mode == VOIDmode)
2328 : 0 : nonvoid_mode = GET_MODE (XEXP (condition, 1));
2329 : : /* The constant comparisons should be folded. */
2330 : 744107 : gcc_assert (nonvoid_mode != VOIDmode);
2331 : :
2332 : : /* We only handle integers or pointers. */
2333 : 744107 : scalar_int_mode mode;
2334 : 744107 : if (!is_a <scalar_int_mode> (nonvoid_mode, &mode))
2335 : 491 : goto fail;
2336 : :
2337 : 743616 : op0 = XEXP (condition, 0);
2338 : 743616 : if (!iv_analyze (insn, mode, op0, &iv0))
2339 : 268587 : goto fail;
2340 : :
2341 : 475029 : op1 = XEXP (condition, 1);
2342 : 475029 : if (!iv_analyze (insn, mode, op1, &iv1))
2343 : 39199 : goto fail;
2344 : :
2345 : 871361 : if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2346 : 871361 : || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2347 : 301 : goto fail;
2348 : :
2349 : : /* Check condition and normalize it. */
2350 : :
2351 : 435529 : switch (cond)
2352 : : {
2353 : 26294 : case GE:
2354 : 26294 : case GT:
2355 : 26294 : case GEU:
2356 : 26294 : case GTU:
2357 : 26294 : std::swap (iv0, iv1);
2358 : 26294 : cond = swap_condition (cond);
2359 : 26294 : break;
2360 : : case NE:
2361 : : case LE:
2362 : : case LEU:
2363 : : case LT:
2364 : : case LTU:
2365 : : break;
2366 : 1730 : default:
2367 : 1730 : goto fail;
2368 : : }
2369 : :
2370 : : /* Handle extends. This is relatively nontrivial, so we only try in some
2371 : : easy cases, when we can canonicalize the ivs (possibly by adding some
2372 : : assumptions) to shape subreg (base + i * step). This function also fills
2373 : : in desc->mode and desc->signed_p. */
2374 : :
2375 : 433799 : if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2376 : 7 : goto fail;
2377 : :
2378 : 433792 : comp_mode = iv0.extend_mode;
2379 : 433792 : mode = iv0.mode;
2380 : 433792 : size = GET_MODE_PRECISION (mode);
2381 : 433792 : get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2382 : 433792 : mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2383 : 433792 : mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2384 : :
2385 : 433792 : if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2386 : 0 : goto fail;
2387 : :
2388 : : /* We can take care of the case of two induction variables chasing each other
2389 : : if the test is NE. I have never seen a loop using it, but still it is
2390 : : cool. */
2391 : 433792 : if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2392 : : {
2393 : 340 : if (cond != NE)
2394 : 167 : goto fail;
2395 : :
2396 : 173 : iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2397 : 173 : iv1.step = const0_rtx;
2398 : : }
2399 : :
2400 : 433625 : iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2401 : 433625 : iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2402 : :
2403 : : /* This is either infinite loop or the one that ends immediately, depending
2404 : : on initial values. Unswitching should remove this kind of conditions. */
2405 : 433625 : if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2406 : 4385 : goto fail;
2407 : :
2408 : 429240 : if (cond != NE)
2409 : : {
2410 : 66344 : if (iv0.step == const0_rtx)
2411 : 5602 : step_val = -INTVAL (iv1.step);
2412 : : else
2413 : 60742 : step_val = INTVAL (iv0.step);
2414 : :
2415 : : /* Ignore loops of while (i-- < 10) type. */
2416 : 66344 : if (step_val < 0)
2417 : 2582 : goto fail;
2418 : :
2419 : 63762 : step_is_pow2 = !(step_val & (step_val - 1));
2420 : : }
2421 : : else
2422 : : {
2423 : : /* We do not care about whether the step is power of two in this
2424 : : case. */
2425 : : step_is_pow2 = false;
2426 : 439161 : step_val = 0;
2427 : : }
2428 : :
2429 : : /* Some more condition normalization. We must record some assumptions
2430 : : due to overflows. */
2431 : 63762 : switch (cond)
2432 : : {
2433 : 51259 : case LT:
2434 : 51259 : case LTU:
2435 : : /* We want to take care only of non-sharp relationals; this is easy,
2436 : : as in cases the overflow would make the transformation unsafe
2437 : : the loop does not roll. Seemingly it would make more sense to want
2438 : : to take care of sharp relationals instead, as NE is more similar to
2439 : : them, but the problem is that here the transformation would be more
2440 : : difficult due to possibly infinite loops. */
2441 : 51259 : if (iv0.step == const0_rtx)
2442 : : {
2443 : 3684 : tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2444 : 3684 : assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2445 : : mode_mmax);
2446 : 3684 : if (assumption == const_true_rtx)
2447 : 0 : goto zero_iter_simplify;
2448 : 3684 : iv0.base = simplify_gen_binary (PLUS, comp_mode,
2449 : : iv0.base, const1_rtx);
2450 : : }
2451 : : else
2452 : : {
2453 : 47575 : tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2454 : 47575 : assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2455 : : mode_mmin);
2456 : 47575 : if (assumption == const_true_rtx)
2457 : 0 : goto zero_iter_simplify;
2458 : 47575 : iv1.base = simplify_gen_binary (PLUS, comp_mode,
2459 : : iv1.base, constm1_rtx);
2460 : : }
2461 : :
2462 : 51259 : if (assumption != const0_rtx)
2463 : 42775 : desc->noloop_assumptions =
2464 : 42775 : alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2465 : 51259 : cond = (cond == LT) ? LE : LEU;
2466 : :
2467 : : /* It will be useful to be able to tell the difference once more in
2468 : : LE -> NE reduction. */
2469 : : was_sharp = true;
2470 : : break;
2471 : 375399 : default: ;
2472 : : }
2473 : :
2474 : : /* Take care of trivially infinite loops. */
2475 : 375399 : if (cond != NE)
2476 : : {
2477 : 63762 : if (iv0.step == const0_rtx)
2478 : : {
2479 : 4743 : tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2480 : 4743 : if (rtx_equal_p (tmp, mode_mmin))
2481 : : {
2482 : 0 : desc->infinite =
2483 : 0 : alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2484 : : /* Fill in the remaining fields somehow. */
2485 : 0 : goto zero_iter_simplify;
2486 : : }
2487 : : }
2488 : : else
2489 : : {
2490 : 59019 : tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2491 : 59019 : if (rtx_equal_p (tmp, mode_mmax))
2492 : : {
2493 : 0 : desc->infinite =
2494 : 0 : alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2495 : : /* Fill in the remaining fields somehow. */
2496 : 0 : goto zero_iter_simplify;
2497 : : }
2498 : : }
2499 : : }
2500 : :
2501 : : /* If we can we want to take care of NE conditions instead of size
2502 : : comparisons, as they are much more friendly (most importantly
2503 : : this takes care of special handling of loops with step 1). We can
2504 : : do it if we first check that upper bound is greater or equal to
2505 : : lower bound, their difference is constant c modulo step and that
2506 : : there is not an overflow. */
2507 : 63762 : if (cond != NE)
2508 : : {
2509 : 63762 : if (iv0.step == const0_rtx)
2510 : 4743 : step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2511 : : else
2512 : : step = iv0.step;
2513 : 63762 : step = lowpart_subreg (mode, step, comp_mode);
2514 : 63762 : delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2515 : 63762 : delta = lowpart_subreg (mode, delta, comp_mode);
2516 : 63762 : delta = simplify_gen_binary (UMOD, mode, delta, step);
2517 : 63762 : may_xform = const0_rtx;
2518 : 63762 : may_not_xform = const_true_rtx;
2519 : :
2520 : 63762 : if (CONST_INT_P (delta))
2521 : : {
2522 : 35088 : if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2523 : : {
2524 : : /* A special case. We have transformed condition of type
2525 : : for (i = 0; i < 4; i += 4)
2526 : : into
2527 : : for (i = 0; i <= 3; i += 4)
2528 : : obviously if the test for overflow during that transformation
2529 : : passed, we cannot overflow here. Most importantly any
2530 : : loop with sharp end condition and step 1 falls into this
2531 : : category, so handling this case specially is definitely
2532 : : worth the troubles. */
2533 : : may_xform = const_true_rtx;
2534 : : }
2535 : 7871 : else if (iv0.step == const0_rtx)
2536 : : {
2537 : 670 : bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2538 : 670 : bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2539 : 670 : bound = lowpart_subreg (mode, bound, comp_mode);
2540 : 670 : tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2541 : 670 : may_xform = simplify_gen_relational (cond, SImode, mode,
2542 : : bound, tmp);
2543 : 670 : may_not_xform = simplify_gen_relational (reverse_condition (cond),
2544 : : SImode, mode,
2545 : : bound, tmp);
2546 : : }
2547 : : else
2548 : : {
2549 : 7201 : bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2550 : 7201 : bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2551 : 7201 : bound = lowpart_subreg (mode, bound, comp_mode);
2552 : 7201 : tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2553 : 7201 : may_xform = simplify_gen_relational (cond, SImode, mode,
2554 : : tmp, bound);
2555 : 7201 : may_not_xform = simplify_gen_relational (reverse_condition (cond),
2556 : : SImode, mode,
2557 : : tmp, bound);
2558 : : }
2559 : : }
2560 : :
2561 : 63762 : if (may_xform != const0_rtx)
2562 : : {
2563 : : /* We perform the transformation always provided that it is not
2564 : : completely senseless. This is OK, as we would need this assumption
2565 : : to determine the number of iterations anyway. */
2566 : 35088 : if (may_xform != const_true_rtx)
2567 : : {
2568 : : /* If the step is a power of two and the final value we have
2569 : : computed overflows, the cycle is infinite. Otherwise it
2570 : : is nontrivial to compute the number of iterations. */
2571 : 7710 : if (step_is_pow2)
2572 : 7710 : desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2573 : : desc->infinite);
2574 : : else
2575 : 0 : desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2576 : : desc->assumptions);
2577 : : }
2578 : :
2579 : : /* We are going to lose some information about upper bound on
2580 : : number of iterations in this step, so record the information
2581 : : here. */
2582 : 35088 : inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2583 : 35088 : if (CONST_INT_P (iv1.base))
2584 : 469 : up = INTVAL (iv1.base);
2585 : : else
2586 : 34619 : up = INTVAL (mode_mmax) - inc;
2587 : 35088 : down = INTVAL (CONST_INT_P (iv0.base)
2588 : : ? iv0.base
2589 : : : mode_mmin);
2590 : 35088 : max = (up - down) / inc + 1;
2591 : 35088 : if (!desc->infinite
2592 : 27378 : && !desc->assumptions)
2593 : 27378 : record_niter_bound (loop, max, false, true);
2594 : :
2595 : 35088 : if (iv0.step == const0_rtx)
2596 : : {
2597 : 1774 : iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2598 : 1774 : iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2599 : : }
2600 : : else
2601 : : {
2602 : 33314 : iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2603 : 33314 : iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2604 : : }
2605 : :
2606 : 35088 : tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2607 : 35088 : tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2608 : 35088 : assumption = simplify_gen_relational (reverse_condition (cond),
2609 : : SImode, mode, tmp0, tmp1);
2610 : 35088 : if (assumption == const_true_rtx)
2611 : 0 : goto zero_iter_simplify;
2612 : 35088 : else if (assumption != const0_rtx)
2613 : 35088 : desc->noloop_assumptions =
2614 : 35088 : alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2615 : : cond = NE;
2616 : : }
2617 : : }
2618 : :
2619 : : /* Count the number of iterations. */
2620 : 28674 : if (cond == NE)
2621 : : {
2622 : : /* Everything we do here is just arithmetics modulo size of mode. This
2623 : : makes us able to do more involved computations of number of iterations
2624 : : than in other cases. First transform the condition into shape
2625 : : s * i <> c, with s positive. */
2626 : 397984 : iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2627 : 397984 : iv0.base = const0_rtx;
2628 : 397984 : iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2629 : 397984 : iv1.step = const0_rtx;
2630 : 397984 : if (INTVAL (iv0.step) < 0)
2631 : : {
2632 : 135351 : iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
2633 : 135351 : iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
2634 : : }
2635 : 397984 : iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2636 : :
2637 : : /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2638 : : is infinite. Otherwise, the number of iterations is
2639 : : (inverse(s/d) * (c/d)) mod (size of mode/d). */
2640 : 397984 : s = INTVAL (iv0.step); d = 1;
2641 : 916444 : while (s % 2 != 1)
2642 : : {
2643 : 518460 : s /= 2;
2644 : 518460 : d *= 2;
2645 : 518460 : size--;
2646 : : }
2647 : 397984 : bound = gen_int_mode (((uint64_t) 1 << (size - 1) << 1) - 1, mode);
2648 : :
2649 : 397984 : tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2650 : 397984 : tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2651 : 397984 : assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2652 : 397984 : desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2653 : :
2654 : 397984 : tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2655 : 397984 : inv = inverse (s, size);
2656 : 397984 : tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2657 : 397984 : desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2658 : : }
2659 : : else
2660 : : {
2661 : 28674 : if (iv1.step == const0_rtx)
2662 : : /* Condition in shape a + s * i <= b
2663 : : We must know that b + s does not overflow and a <= b + s and then we
2664 : : can compute number of iterations as (b + s - a) / s. (It might
2665 : : seem that we in fact could be more clever about testing the b + s
2666 : : overflow condition using some information about b - a mod s,
2667 : : but it was already taken into account during LE -> NE transform). */
2668 : : {
2669 : 25705 : step = iv0.step;
2670 : 25705 : tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2671 : 25705 : tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2672 : :
2673 : 25705 : bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2674 : : lowpart_subreg (mode, step,
2675 : : comp_mode));
2676 : 25705 : if (step_is_pow2)
2677 : : {
2678 : 23957 : rtx t0, t1;
2679 : :
2680 : : /* If s is power of 2, we know that the loop is infinite if
2681 : : a % s <= b % s and b + s overflows. */
2682 : 23957 : assumption = simplify_gen_relational (reverse_condition (cond),
2683 : : SImode, mode,
2684 : : tmp1, bound);
2685 : :
2686 : 23957 : t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2687 : 23957 : t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2688 : 23957 : tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2689 : 23957 : assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2690 : 23957 : desc->infinite =
2691 : 23957 : alloc_EXPR_LIST (0, assumption, desc->infinite);
2692 : : }
2693 : : else
2694 : : {
2695 : 1748 : assumption = simplify_gen_relational (cond, SImode, mode,
2696 : : tmp1, bound);
2697 : 1748 : desc->assumptions =
2698 : 1748 : alloc_EXPR_LIST (0, assumption, desc->assumptions);
2699 : : }
2700 : :
2701 : 25705 : tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2702 : 25705 : tmp = lowpart_subreg (mode, tmp, comp_mode);
2703 : 25705 : assumption = simplify_gen_relational (reverse_condition (cond),
2704 : : SImode, mode, tmp0, tmp);
2705 : :
2706 : 25705 : delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2707 : 25705 : delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2708 : : }
2709 : : else
2710 : : {
2711 : : /* Condition in shape a <= b - s * i
2712 : : We must know that a - s does not overflow and a - s <= b and then
2713 : : we can again compute number of iterations as (b - (a - s)) / s. */
2714 : 2969 : step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2715 : 2969 : tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2716 : 2969 : tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2717 : :
2718 : 2969 : bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2719 : : lowpart_subreg (mode, step, comp_mode));
2720 : 2969 : if (step_is_pow2)
2721 : : {
2722 : 1921 : rtx t0, t1;
2723 : :
2724 : : /* If s is power of 2, we know that the loop is infinite if
2725 : : a % s <= b % s and a - s overflows. */
2726 : 1921 : assumption = simplify_gen_relational (reverse_condition (cond),
2727 : : SImode, mode,
2728 : : bound, tmp0);
2729 : :
2730 : 1921 : t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2731 : 1921 : t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2732 : 1921 : tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2733 : 1921 : assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2734 : 1921 : desc->infinite =
2735 : 1921 : alloc_EXPR_LIST (0, assumption, desc->infinite);
2736 : : }
2737 : : else
2738 : : {
2739 : 1048 : assumption = simplify_gen_relational (cond, SImode, mode,
2740 : : bound, tmp0);
2741 : 1048 : desc->assumptions =
2742 : 1048 : alloc_EXPR_LIST (0, assumption, desc->assumptions);
2743 : : }
2744 : :
2745 : 2969 : tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2746 : 2969 : tmp = lowpart_subreg (mode, tmp, comp_mode);
2747 : 2969 : assumption = simplify_gen_relational (reverse_condition (cond),
2748 : : SImode, mode,
2749 : : tmp, tmp1);
2750 : 2969 : delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2751 : 2969 : delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2752 : : }
2753 : 28674 : if (assumption == const_true_rtx)
2754 : 0 : goto zero_iter_simplify;
2755 : 28674 : else if (assumption != const0_rtx)
2756 : 28490 : desc->noloop_assumptions =
2757 : 28490 : alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2758 : 28674 : delta = simplify_gen_binary (UDIV, mode, delta, step);
2759 : 28674 : desc->niter_expr = delta;
2760 : : }
2761 : :
2762 : 426658 : old_niter = desc->niter_expr;
2763 : :
2764 : 426658 : simplify_using_initial_values (loop, AND, &desc->assumptions);
2765 : 426658 : if (desc->assumptions
2766 : 2148 : && XEXP (desc->assumptions, 0) == const0_rtx)
2767 : 24 : goto fail;
2768 : 426634 : simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2769 : 426634 : simplify_using_initial_values (loop, IOR, &desc->infinite);
2770 : 426634 : simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2771 : :
2772 : : /* Rerun the simplification. Consider code (created by copying loop headers)
2773 : :
2774 : : i = 0;
2775 : :
2776 : : if (0 < n)
2777 : : {
2778 : : do
2779 : : {
2780 : : i++;
2781 : : } while (i < n);
2782 : : }
2783 : :
2784 : : The first pass determines that i = 0, the second pass uses it to eliminate
2785 : : noloop assumption. */
2786 : :
2787 : 426634 : simplify_using_initial_values (loop, AND, &desc->assumptions);
2788 : 426634 : if (desc->assumptions
2789 : 2124 : && XEXP (desc->assumptions, 0) == const0_rtx)
2790 : 0 : goto fail;
2791 : 426634 : simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2792 : 426634 : simplify_using_initial_values (loop, IOR, &desc->infinite);
2793 : 426634 : simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2794 : :
2795 : 426634 : if (desc->noloop_assumptions
2796 : 53964 : && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2797 : 0 : goto zero_iter;
2798 : :
2799 : 426634 : if (CONST_INT_P (desc->niter_expr))
2800 : : {
2801 : 206621 : uint64_t val = INTVAL (desc->niter_expr);
2802 : :
2803 : 206621 : desc->const_iter = true;
2804 : 206621 : desc->niter = val & GET_MODE_MASK (desc->mode);
2805 : 206621 : if (!desc->infinite
2806 : 206552 : && !desc->assumptions)
2807 : 206552 : record_niter_bound (loop, desc->niter, false, true);
2808 : : }
2809 : : else
2810 : : {
2811 : 220013 : max = determine_max_iter (loop, desc, old_niter);
2812 : 220013 : if (!max)
2813 : 0 : goto zero_iter_simplify;
2814 : 220013 : if (!desc->infinite
2815 : 144946 : && !desc->assumptions)
2816 : 142822 : record_niter_bound (loop, max, false, true);
2817 : :
2818 : : /* simplify_using_initial_values does a copy propagation on the registers
2819 : : in the expression for the number of iterations. This prolongs life
2820 : : ranges of registers and increases register pressure, and usually
2821 : : brings no gain (and if it happens to do, the cse pass will take care
2822 : : of it anyway). So prevent this behavior, unless it enabled us to
2823 : : derive that the number of iterations is a constant. */
2824 : 220013 : desc->niter_expr = old_niter;
2825 : : }
2826 : :
2827 : : return;
2828 : :
2829 : 0 : zero_iter_simplify:
2830 : : /* Simplify the assumptions. */
2831 : 0 : simplify_using_initial_values (loop, AND, &desc->assumptions);
2832 : 0 : if (desc->assumptions
2833 : 0 : && XEXP (desc->assumptions, 0) == const0_rtx)
2834 : 0 : goto fail;
2835 : 0 : simplify_using_initial_values (loop, IOR, &desc->infinite);
2836 : :
2837 : : /* Fallthru. */
2838 : 0 : zero_iter:
2839 : 0 : desc->const_iter = true;
2840 : 0 : desc->niter = 0;
2841 : 0 : record_niter_bound (loop, 0, true, true);
2842 : 0 : desc->noloop_assumptions = NULL_RTX;
2843 : 0 : desc->niter_expr = const0_rtx;
2844 : 0 : return;
2845 : :
2846 : 317473 : fail:
2847 : 317473 : desc->simple_p = false;
2848 : 317473 : return;
2849 : : }
2850 : :
2851 : : /* Checks whether E is a simple exit from LOOP and stores its description
2852 : : into DESC. */
2853 : :
2854 : : static void
2855 : 1145204 : check_simple_exit (class loop *loop, edge e, class niter_desc *desc)
2856 : : {
2857 : 1145204 : basic_block exit_bb;
2858 : 1145204 : rtx condition;
2859 : 1145204 : rtx_insn *at;
2860 : 1145204 : edge ein;
2861 : :
2862 : 1145204 : exit_bb = e->src;
2863 : 1145204 : desc->simple_p = false;
2864 : :
2865 : : /* It must belong directly to the loop. */
2866 : 1145204 : if (exit_bb->loop_father != loop)
2867 : 401097 : return;
2868 : :
2869 : : /* It must be tested (at least) once during any iteration. */
2870 : 1050490 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2871 : : return;
2872 : :
2873 : : /* It must end in a simple conditional jump. */
2874 : 845806 : if (!any_condjump_p (BB_END (exit_bb)) || !onlyjump_p (BB_END (exit_bb)))
2875 : 67408 : return;
2876 : :
2877 : 778398 : ein = EDGE_SUCC (exit_bb, 0);
2878 : 778398 : if (ein == e)
2879 : 233847 : ein = EDGE_SUCC (exit_bb, 1);
2880 : :
2881 : 778398 : desc->out_edge = e;
2882 : 778398 : desc->in_edge = ein;
2883 : :
2884 : : /* Test whether the condition is suitable. */
2885 : 778398 : if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2886 : : return;
2887 : :
2888 : 747703 : if (ein->flags & EDGE_FALLTHRU)
2889 : : {
2890 : 187073 : condition = reversed_condition (condition);
2891 : 187073 : if (!condition)
2892 : : return;
2893 : : }
2894 : :
2895 : : /* Check that we are able to determine number of iterations and fill
2896 : : in information about it. */
2897 : 744107 : iv_number_of_iterations (loop, at, condition, desc);
2898 : : }
2899 : :
2900 : : /* Finds a simple exit of LOOP and stores its description into DESC. */
2901 : :
2902 : : static void
2903 : 596284 : find_simple_exit (class loop *loop, class niter_desc *desc)
2904 : : {
2905 : 596284 : unsigned i;
2906 : 596284 : basic_block *body;
2907 : 596284 : edge e;
2908 : 596284 : class niter_desc act;
2909 : 596284 : bool any = false;
2910 : 596284 : edge_iterator ei;
2911 : :
2912 : 596284 : desc->simple_p = false;
2913 : 596284 : body = get_loop_body (loop);
2914 : :
2915 : 4963883 : for (i = 0; i < loop->num_nodes; i++)
2916 : : {
2917 : 9663729 : FOR_EACH_EDGE (e, ei, body[i]->succs)
2918 : : {
2919 : 5892414 : if (flow_bb_inside_loop_p (loop, e->dest))
2920 : 4747210 : continue;
2921 : :
2922 : 1145204 : check_simple_exit (loop, e, &act);
2923 : 1145204 : if (!act.simple_p)
2924 : 718570 : continue;
2925 : :
2926 : 426634 : if (!any)
2927 : : any = true;
2928 : : else
2929 : : {
2930 : : /* Prefer constant iterations; the less the better. */
2931 : 16218 : if (!act.const_iter
2932 : 1176 : || (desc->const_iter && act.niter >= desc->niter))
2933 : 15372 : continue;
2934 : :
2935 : : /* Also if the actual exit may be infinite, while the old one
2936 : : not, prefer the old one. */
2937 : 846 : if (act.infinite && !desc->infinite)
2938 : 12 : continue;
2939 : : }
2940 : :
2941 : 411250 : *desc = act;
2942 : : }
2943 : : }
2944 : :
2945 : 596284 : if (dump_file)
2946 : : {
2947 : 103 : if (desc->simple_p)
2948 : : {
2949 : 75 : fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2950 : 75 : fprintf (dump_file, " simple exit %d -> %d\n",
2951 : 75 : desc->out_edge->src->index,
2952 : 75 : desc->out_edge->dest->index);
2953 : 75 : if (desc->assumptions)
2954 : : {
2955 : 0 : fprintf (dump_file, " assumptions: ");
2956 : 0 : print_rtl (dump_file, desc->assumptions);
2957 : 0 : fprintf (dump_file, "\n");
2958 : : }
2959 : 75 : if (desc->noloop_assumptions)
2960 : : {
2961 : 8 : fprintf (dump_file, " does not roll if: ");
2962 : 8 : print_rtl (dump_file, desc->noloop_assumptions);
2963 : 8 : fprintf (dump_file, "\n");
2964 : : }
2965 : 75 : if (desc->infinite)
2966 : : {
2967 : 19 : fprintf (dump_file, " infinite if: ");
2968 : 19 : print_rtl (dump_file, desc->infinite);
2969 : 19 : fprintf (dump_file, "\n");
2970 : : }
2971 : :
2972 : 75 : fprintf (dump_file, " number of iterations: ");
2973 : 75 : print_rtl (dump_file, desc->niter_expr);
2974 : 75 : fprintf (dump_file, "\n");
2975 : :
2976 : 75 : fprintf (dump_file, " upper bound: %li\n",
2977 : : (long)get_max_loop_iterations_int (loop));
2978 : 75 : fprintf (dump_file, " likely upper bound: %li\n",
2979 : : (long)get_likely_max_loop_iterations_int (loop));
2980 : 75 : fprintf (dump_file, " realistic bound: %li\n",
2981 : : (long)get_estimated_loop_iterations_int (loop));
2982 : : }
2983 : : else
2984 : 28 : fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2985 : : }
2986 : :
2987 : : /* Fix up the finiteness if possible. We can only do it for single exit,
2988 : : since the loop is finite, but it's possible that we predicate one loop
2989 : : exit to be finite which can not be determined as finite in middle-end as
2990 : : well. It results in incorrect predicate information on the exit condition
2991 : : expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite,
2992 : : it means _1 can exactly divide -8. */
2993 : 596284 : if (desc->infinite && single_exit (loop) && finite_loop_p (loop))
2994 : : {
2995 : 33438 : desc->infinite = NULL_RTX;
2996 : 33438 : if (dump_file)
2997 : 19 : fprintf (dump_file, " infinite updated to finite.\n");
2998 : : }
2999 : :
3000 : 596284 : free (body);
3001 : 596284 : }
3002 : :
3003 : : /* Creates a simple loop description of LOOP if it was not computed
3004 : : already. */
3005 : :
3006 : : class niter_desc *
3007 : 1002623 : get_simple_loop_desc (class loop *loop)
3008 : : {
3009 : 1002623 : class niter_desc *desc = simple_loop_desc (loop);
3010 : :
3011 : 1002623 : if (desc)
3012 : : return desc;
3013 : :
3014 : : /* At least desc->infinite is not always initialized by
3015 : : find_simple_loop_exit. */
3016 : 596284 : desc = ggc_cleared_alloc<niter_desc> ();
3017 : 596284 : iv_analysis_loop_init (loop);
3018 : 596284 : find_simple_exit (loop, desc);
3019 : 596284 : loop->simple_loop_desc = desc;
3020 : 596284 : return desc;
3021 : : }
3022 : :
3023 : : /* Releases simple loop description for LOOP. */
3024 : :
3025 : : void
3026 : 6057753 : free_simple_loop_desc (class loop *loop)
3027 : : {
3028 : 6057753 : class niter_desc *desc = simple_loop_desc (loop);
3029 : :
3030 : 6057753 : if (!desc)
3031 : : return;
3032 : :
3033 : 596284 : ggc_free (desc);
3034 : 596284 : loop->simple_loop_desc = NULL;
3035 : : }
|
