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