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