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