|
0
|
1 /* RTL-level loop invariant motion.
|
|
|
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 implements the loop invariant motion pass. It is very simple
|
|
|
22 (no calls, no loads/stores, etc.). This should be sufficient to cleanup
|
|
|
23 things like address arithmetics -- other more complicated invariants should
|
|
|
24 be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
|
|
|
25
|
|
|
26 We proceed loop by loop -- it is simpler than trying to handle things
|
|
|
27 globally and should not lose much. First we inspect all sets inside loop
|
|
|
28 and create a dependency graph on insns (saying "to move this insn, you must
|
|
|
29 also move the following insns").
|
|
|
30
|
|
|
31 We then need to determine what to move. We estimate the number of registers
|
|
|
32 used and move as many invariants as possible while we still have enough free
|
|
|
33 registers. We prefer the expensive invariants.
|
|
|
34
|
|
|
35 Then we move the selected invariants out of the loop, creating a new
|
|
|
36 temporaries for them if necessary. */
|
|
|
37
|
|
|
38 #include "config.h"
|
|
|
39 #include "system.h"
|
|
|
40 #include "coretypes.h"
|
|
|
41 #include "tm.h"
|
|
|
42 #include "rtl.h"
|
|
|
43 #include "tm_p.h"
|
|
|
44 #include "hard-reg-set.h"
|
|
|
45 #include "obstack.h"
|
|
|
46 #include "basic-block.h"
|
|
|
47 #include "cfgloop.h"
|
|
|
48 #include "expr.h"
|
|
|
49 #include "recog.h"
|
|
|
50 #include "output.h"
|
|
|
51 #include "function.h"
|
|
|
52 #include "flags.h"
|
|
|
53 #include "df.h"
|
|
|
54 #include "hashtab.h"
|
|
|
55 #include "except.h"
|
|
|
56 #include "params.h"
|
|
|
57
|
|
|
58 /* The data stored for the loop. */
|
|
|
59
|
|
|
60 struct loop_data
|
|
|
61 {
|
|
|
62 struct loop *outermost_exit; /* The outermost exit of the loop. */
|
|
|
63 bool has_call; /* True if the loop contains a call. */
|
|
|
64 };
|
|
|
65
|
|
|
66 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
|
|
|
67
|
|
|
68 /* The description of an use. */
|
|
|
69
|
|
|
70 struct use
|
|
|
71 {
|
|
|
72 rtx *pos; /* Position of the use. */
|
|
|
73 rtx insn; /* The insn in that the use occurs. */
|
|
|
74
|
|
|
75 struct use *next; /* Next use in the list. */
|
|
|
76 };
|
|
|
77
|
|
|
78 /* The description of a def. */
|
|
|
79
|
|
|
80 struct def
|
|
|
81 {
|
|
|
82 struct use *uses; /* The list of uses that are uniquely reached
|
|
|
83 by it. */
|
|
|
84 unsigned n_uses; /* Number of such uses. */
|
|
|
85 unsigned invno; /* The corresponding invariant. */
|
|
|
86 };
|
|
|
87
|
|
|
88 /* The data stored for each invariant. */
|
|
|
89
|
|
|
90 struct invariant
|
|
|
91 {
|
|
|
92 /* The number of the invariant. */
|
|
|
93 unsigned invno;
|
|
|
94
|
|
|
95 /* The number of the invariant with the same value. */
|
|
|
96 unsigned eqto;
|
|
|
97
|
|
|
98 /* If we moved the invariant out of the loop, the register that contains its
|
|
|
99 value. */
|
|
|
100 rtx reg;
|
|
|
101
|
|
|
102 /* The definition of the invariant. */
|
|
|
103 struct def *def;
|
|
|
104
|
|
|
105 /* The insn in that it is defined. */
|
|
|
106 rtx insn;
|
|
|
107
|
|
|
108 /* Whether it is always executed. */
|
|
|
109 bool always_executed;
|
|
|
110
|
|
|
111 /* Whether to move the invariant. */
|
|
|
112 bool move;
|
|
|
113
|
|
|
114 /* Cost of the invariant. */
|
|
|
115 unsigned cost;
|
|
|
116
|
|
|
117 /* The invariants it depends on. */
|
|
|
118 bitmap depends_on;
|
|
|
119
|
|
|
120 /* Used for detecting already visited invariants during determining
|
|
|
121 costs of movements. */
|
|
|
122 unsigned stamp;
|
|
|
123 };
|
|
|
124
|
|
|
125 /* Table of invariants indexed by the df_ref uid field. */
|
|
|
126
|
|
|
127 static unsigned int invariant_table_size = 0;
|
|
|
128 static struct invariant ** invariant_table;
|
|
|
129
|
|
|
130 /* Entry for hash table of invariant expressions. */
|
|
|
131
|
|
|
132 struct invariant_expr_entry
|
|
|
133 {
|
|
|
134 /* The invariant. */
|
|
|
135 struct invariant *inv;
|
|
|
136
|
|
|
137 /* Its value. */
|
|
|
138 rtx expr;
|
|
|
139
|
|
|
140 /* Its mode. */
|
|
|
141 enum machine_mode mode;
|
|
|
142
|
|
|
143 /* Its hash. */
|
|
|
144 hashval_t hash;
|
|
|
145 };
|
|
|
146
|
|
|
147 /* The actual stamp for marking already visited invariants during determining
|
|
|
148 costs of movements. */
|
|
|
149
|
|
|
150 static unsigned actual_stamp;
|
|
|
151
|
|
|
152 typedef struct invariant *invariant_p;
|
|
|
153
|
|
|
154 DEF_VEC_P(invariant_p);
|
|
|
155 DEF_VEC_ALLOC_P(invariant_p, heap);
|
|
|
156
|
|
|
157 /* The invariants. */
|
|
|
158
|
|
|
159 static VEC(invariant_p,heap) *invariants;
|
|
|
160
|
|
|
161 /* Check the size of the invariant table and realloc if necessary. */
|
|
|
162
|
|
|
163 static void
|
|
|
164 check_invariant_table_size (void)
|
|
|
165 {
|
|
|
166 if (invariant_table_size < DF_DEFS_TABLE_SIZE())
|
|
|
167 {
|
|
|
168 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
|
|
|
169 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
|
|
|
170 memset (&invariant_table[invariant_table_size], 0,
|
|
|
171 (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
|
|
|
172 invariant_table_size = new_size;
|
|
|
173 }
|
|
|
174 }
|
|
|
175
|
|
|
176 /* Test for possibility of invariantness of X. */
|
|
|
177
|
|
|
178 static bool
|
|
|
179 check_maybe_invariant (rtx x)
|
|
|
180 {
|
|
|
181 enum rtx_code code = GET_CODE (x);
|
|
|
182 int i, j;
|
|
|
183 const char *fmt;
|
|
|
184
|
|
|
185 switch (code)
|
|
|
186 {
|
|
|
187 case CONST_INT:
|
|
|
188 case CONST_DOUBLE:
|
|
|
189 case CONST_FIXED:
|
|
|
190 case SYMBOL_REF:
|
|
|
191 case CONST:
|
|
|
192 case LABEL_REF:
|
|
|
193 return true;
|
|
|
194
|
|
|
195 case PC:
|
|
|
196 case CC0:
|
|
|
197 case UNSPEC_VOLATILE:
|
|
|
198 case CALL:
|
|
|
199 return false;
|
|
|
200
|
|
|
201 case REG:
|
|
|
202 return true;
|
|
|
203
|
|
|
204 case MEM:
|
|
|
205 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
|
|
|
206 It should not be hard, and might be faster than "elsewhere". */
|
|
|
207
|
|
|
208 /* Just handle the most trivial case where we load from an unchanging
|
|
|
209 location (most importantly, pic tables). */
|
|
|
210 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
|
|
|
211 break;
|
|
|
212
|
|
|
213 return false;
|
|
|
214
|
|
|
215 case ASM_OPERANDS:
|
|
|
216 /* Don't mess with insns declared volatile. */
|
|
|
217 if (MEM_VOLATILE_P (x))
|
|
|
218 return false;
|
|
|
219 break;
|
|
|
220
|
|
|
221 default:
|
|
|
222 break;
|
|
|
223 }
|
|
|
224
|
|
|
225 fmt = GET_RTX_FORMAT (code);
|
|
|
226 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
|
|
|
227 {
|
|
|
228 if (fmt[i] == 'e')
|
|
|
229 {
|
|
|
230 if (!check_maybe_invariant (XEXP (x, i)))
|
|
|
231 return false;
|
|
|
232 }
|
|
|
233 else if (fmt[i] == 'E')
|
|
|
234 {
|
|
|
235 for (j = 0; j < XVECLEN (x, i); j++)
|
|
|
236 if (!check_maybe_invariant (XVECEXP (x, i, j)))
|
|
|
237 return false;
|
|
|
238 }
|
|
|
239 }
|
|
|
240
|
|
|
241 return true;
|
|
|
242 }
|
|
|
243
|
|
|
244 /* Returns the invariant definition for USE, or NULL if USE is not
|
|
|
245 invariant. */
|
|
|
246
|
|
|
247 static struct invariant *
|
|
|
248 invariant_for_use (df_ref use)
|
|
|
249 {
|
|
|
250 struct df_link *defs;
|
|
|
251 df_ref def;
|
|
|
252 basic_block bb = DF_REF_BB (use), def_bb;
|
|
|
253
|
|
|
254 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
|
|
|
255 return NULL;
|
|
|
256
|
|
|
257 defs = DF_REF_CHAIN (use);
|
|
|
258 if (!defs || defs->next)
|
|
|
259 return NULL;
|
|
|
260 def = defs->ref;
|
|
|
261 check_invariant_table_size ();
|
|
|
262 if (!invariant_table[DF_REF_ID(def)])
|
|
|
263 return NULL;
|
|
|
264
|
|
|
265 def_bb = DF_REF_BB (def);
|
|
|
266 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
|
|
|
267 return NULL;
|
|
|
268 return invariant_table[DF_REF_ID(def)];
|
|
|
269 }
|
|
|
270
|
|
|
271 /* Computes hash value for invariant expression X in INSN. */
|
|
|
272
|
|
|
273 static hashval_t
|
|
|
274 hash_invariant_expr_1 (rtx insn, rtx x)
|
|
|
275 {
|
|
|
276 enum rtx_code code = GET_CODE (x);
|
|
|
277 int i, j;
|
|
|
278 const char *fmt;
|
|
|
279 hashval_t val = code;
|
|
|
280 int do_not_record_p;
|
|
|
281 df_ref use;
|
|
|
282 struct invariant *inv;
|
|
|
283
|
|
|
284 switch (code)
|
|
|
285 {
|
|
|
286 case CONST_INT:
|
|
|
287 case CONST_DOUBLE:
|
|
|
288 case CONST_FIXED:
|
|
|
289 case SYMBOL_REF:
|
|
|
290 case CONST:
|
|
|
291 case LABEL_REF:
|
|
|
292 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
|
|
|
293
|
|
|
294 case REG:
|
|
|
295 use = df_find_use (insn, x);
|
|
|
296 if (!use)
|
|
|
297 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
|
|
|
298 inv = invariant_for_use (use);
|
|
|
299 if (!inv)
|
|
|
300 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
|
|
|
301
|
|
|
302 gcc_assert (inv->eqto != ~0u);
|
|
|
303 return inv->eqto;
|
|
|
304
|
|
|
305 default:
|
|
|
306 break;
|
|
|
307 }
|
|
|
308
|
|
|
309 fmt = GET_RTX_FORMAT (code);
|
|
|
310 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
|
|
|
311 {
|
|
|
312 if (fmt[i] == 'e')
|
|
|
313 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
|
|
|
314 else if (fmt[i] == 'E')
|
|
|
315 {
|
|
|
316 for (j = 0; j < XVECLEN (x, i); j++)
|
|
|
317 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
|
|
|
318 }
|
|
|
319 else if (fmt[i] == 'i' || fmt[i] == 'n')
|
|
|
320 val ^= XINT (x, i);
|
|
|
321 }
|
|
|
322
|
|
|
323 return val;
|
|
|
324 }
|
|
|
325
|
|
|
326 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
|
|
|
327 and INSN2 have always the same value. */
|
|
|
328
|
|
|
329 static bool
|
|
|
330 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
|
|
|
331 {
|
|
|
332 enum rtx_code code = GET_CODE (e1);
|
|
|
333 int i, j;
|
|
|
334 const char *fmt;
|
|
|
335 df_ref use1, use2;
|
|
|
336 struct invariant *inv1 = NULL, *inv2 = NULL;
|
|
|
337 rtx sub1, sub2;
|
|
|
338
|
|
|
339 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
|
|
|
340 the other one. If both are VOIDmode, we rely on the caller of this
|
|
|
341 function to verify that their modes are the same. */
|
|
|
342 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
|
|
|
343 return false;
|
|
|
344
|
|
|
345 switch (code)
|
|
|
346 {
|
|
|
347 case CONST_INT:
|
|
|
348 case CONST_DOUBLE:
|
|
|
349 case CONST_FIXED:
|
|
|
350 case SYMBOL_REF:
|
|
|
351 case CONST:
|
|
|
352 case LABEL_REF:
|
|
|
353 return rtx_equal_p (e1, e2);
|
|
|
354
|
|
|
355 case REG:
|
|
|
356 use1 = df_find_use (insn1, e1);
|
|
|
357 use2 = df_find_use (insn2, e2);
|
|
|
358 if (use1)
|
|
|
359 inv1 = invariant_for_use (use1);
|
|
|
360 if (use2)
|
|
|
361 inv2 = invariant_for_use (use2);
|
|
|
362
|
|
|
363 if (!inv1 && !inv2)
|
|
|
364 return rtx_equal_p (e1, e2);
|
|
|
365
|
|
|
366 if (!inv1 || !inv2)
|
|
|
367 return false;
|
|
|
368
|
|
|
369 gcc_assert (inv1->eqto != ~0u);
|
|
|
370 gcc_assert (inv2->eqto != ~0u);
|
|
|
371 return inv1->eqto == inv2->eqto;
|
|
|
372
|
|
|
373 default:
|
|
|
374 break;
|
|
|
375 }
|
|
|
376
|
|
|
377 fmt = GET_RTX_FORMAT (code);
|
|
|
378 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
|
|
|
379 {
|
|
|
380 if (fmt[i] == 'e')
|
|
|
381 {
|
|
|
382 sub1 = XEXP (e1, i);
|
|
|
383 sub2 = XEXP (e2, i);
|
|
|
384
|
|
|
385 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
|
|
|
386 return false;
|
|
|
387 }
|
|
|
388
|
|
|
389 else if (fmt[i] == 'E')
|
|
|
390 {
|
|
|
391 if (XVECLEN (e1, i) != XVECLEN (e2, i))
|
|
|
392 return false;
|
|
|
393
|
|
|
394 for (j = 0; j < XVECLEN (e1, i); j++)
|
|
|
395 {
|
|
|
396 sub1 = XVECEXP (e1, i, j);
|
|
|
397 sub2 = XVECEXP (e2, i, j);
|
|
|
398
|
|
|
399 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
|
|
|
400 return false;
|
|
|
401 }
|
|
|
402 }
|
|
|
403 else if (fmt[i] == 'i' || fmt[i] == 'n')
|
|
|
404 {
|
|
|
405 if (XINT (e1, i) != XINT (e2, i))
|
|
|
406 return false;
|
|
|
407 }
|
|
|
408 /* Unhandled type of subexpression, we fail conservatively. */
|
|
|
409 else
|
|
|
410 return false;
|
|
|
411 }
|
|
|
412
|
|
|
413 return true;
|
|
|
414 }
|
|
|
415
|
|
|
416 /* Returns hash value for invariant expression entry E. */
|
|
|
417
|
|
|
418 static hashval_t
|
|
|
419 hash_invariant_expr (const void *e)
|
|
|
420 {
|
|
|
421 const struct invariant_expr_entry *const entry =
|
|
|
422 (const struct invariant_expr_entry *) e;
|
|
|
423
|
|
|
424 return entry->hash;
|
|
|
425 }
|
|
|
426
|
|
|
427 /* Compares invariant expression entries E1 and E2. */
|
|
|
428
|
|
|
429 static int
|
|
|
430 eq_invariant_expr (const void *e1, const void *e2)
|
|
|
431 {
|
|
|
432 const struct invariant_expr_entry *const entry1 =
|
|
|
433 (const struct invariant_expr_entry *) e1;
|
|
|
434 const struct invariant_expr_entry *const entry2 =
|
|
|
435 (const struct invariant_expr_entry *) e2;
|
|
|
436
|
|
|
437 if (entry1->mode != entry2->mode)
|
|
|
438 return 0;
|
|
|
439
|
|
|
440 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
|
|
|
441 entry2->inv->insn, entry2->expr);
|
|
|
442 }
|
|
|
443
|
|
|
444 /* Checks whether invariant with value EXPR in machine mode MODE is
|
|
|
445 recorded in EQ. If this is the case, return the invariant. Otherwise
|
|
|
446 insert INV to the table for this expression and return INV. */
|
|
|
447
|
|
|
448 static struct invariant *
|
|
|
449 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
|
|
|
450 struct invariant *inv)
|
|
|
451 {
|
|
|
452 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
|
|
|
453 struct invariant_expr_entry *entry;
|
|
|
454 struct invariant_expr_entry pentry;
|
|
|
455 PTR *slot;
|
|
|
456
|
|
|
457 pentry.expr = expr;
|
|
|
458 pentry.inv = inv;
|
|
|
459 pentry.mode = mode;
|
|
|
460 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
|
|
|
461 entry = (struct invariant_expr_entry *) *slot;
|
|
|
462
|
|
|
463 if (entry)
|
|
|
464 return entry->inv;
|
|
|
465
|
|
|
466 entry = XNEW (struct invariant_expr_entry);
|
|
|
467 entry->inv = inv;
|
|
|
468 entry->expr = expr;
|
|
|
469 entry->mode = mode;
|
|
|
470 entry->hash = hash;
|
|
|
471 *slot = entry;
|
|
|
472
|
|
|
473 return inv;
|
|
|
474 }
|
|
|
475
|
|
|
476 /* Finds invariants identical to INV and records the equivalence. EQ is the
|
|
|
477 hash table of the invariants. */
|
|
|
478
|
|
|
479 static void
|
|
|
480 find_identical_invariants (htab_t eq, struct invariant *inv)
|
|
|
481 {
|
|
|
482 unsigned depno;
|
|
|
483 bitmap_iterator bi;
|
|
|
484 struct invariant *dep;
|
|
|
485 rtx expr, set;
|
|
|
486 enum machine_mode mode;
|
|
|
487
|
|
|
488 if (inv->eqto != ~0u)
|
|
|
489 return;
|
|
|
490
|
|
|
491 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
|
|
|
492 {
|
|
|
493 dep = VEC_index (invariant_p, invariants, depno);
|
|
|
494 find_identical_invariants (eq, dep);
|
|
|
495 }
|
|
|
496
|
|
|
497 set = single_set (inv->insn);
|
|
|
498 expr = SET_SRC (set);
|
|
|
499 mode = GET_MODE (expr);
|
|
|
500 if (mode == VOIDmode)
|
|
|
501 mode = GET_MODE (SET_DEST (set));
|
|
|
502 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
|
|
|
503
|
|
|
504 if (dump_file && inv->eqto != inv->invno)
|
|
|
505 fprintf (dump_file,
|
|
|
506 "Invariant %d is equivalent to invariant %d.\n",
|
|
|
507 inv->invno, inv->eqto);
|
|
|
508 }
|
|
|
509
|
|
|
510 /* Find invariants with the same value and record the equivalences. */
|
|
|
511
|
|
|
512 static void
|
|
|
513 merge_identical_invariants (void)
|
|
|
514 {
|
|
|
515 unsigned i;
|
|
|
516 struct invariant *inv;
|
|
|
517 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
|
|
|
518 hash_invariant_expr, eq_invariant_expr, free);
|
|
|
519
|
|
|
520 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
|
|
|
521 find_identical_invariants (eq, inv);
|
|
|
522
|
|
|
523 htab_delete (eq);
|
|
|
524 }
|
|
|
525
|
|
|
526 /* Determines the basic blocks inside LOOP that are always executed and
|
|
|
527 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
|
|
|
528 basic blocks that may either exit the loop, or contain the call that
|
|
|
529 does not have to return. BODY is body of the loop obtained by
|
|
|
530 get_loop_body_in_dom_order. */
|
|
|
531
|
|
|
532 static void
|
|
|
533 compute_always_reached (struct loop *loop, basic_block *body,
|
|
|
534 bitmap may_exit, bitmap always_reached)
|
|
|
535 {
|
|
|
536 unsigned i;
|
|
|
537
|
|
|
538 for (i = 0; i < loop->num_nodes; i++)
|
|
|
539 {
|
|
|
540 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
|
|
|
541 bitmap_set_bit (always_reached, i);
|
|
|
542
|
|
|
543 if (bitmap_bit_p (may_exit, i))
|
|
|
544 return;
|
|
|
545 }
|
|
|
546 }
|
|
|
547
|
|
|
548 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
|
|
|
549 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
|
|
|
550 additionally mark blocks that may exit due to a call. */
|
|
|
551
|
|
|
552 static void
|
|
|
553 find_exits (struct loop *loop, basic_block *body,
|
|
|
554 bitmap may_exit, bitmap has_exit)
|
|
|
555 {
|
|
|
556 unsigned i;
|
|
|
557 edge_iterator ei;
|
|
|
558 edge e;
|
|
|
559 struct loop *outermost_exit = loop, *aexit;
|
|
|
560 bool has_call = false;
|
|
|
561 rtx insn;
|
|
|
562
|
|
|
563 for (i = 0; i < loop->num_nodes; i++)
|
|
|
564 {
|
|
|
565 if (body[i]->loop_father == loop)
|
|
|
566 {
|
|
|
567 FOR_BB_INSNS (body[i], insn)
|
|
|
568 {
|
|
|
569 if (CALL_P (insn)
|
|
|
570 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
|
|
|
571 || !RTL_CONST_OR_PURE_CALL_P (insn)))
|
|
|
572 {
|
|
|
573 has_call = true;
|
|
|
574 bitmap_set_bit (may_exit, i);
|
|
|
575 break;
|
|
|
576 }
|
|
|
577 }
|
|
|
578
|
|
|
579 FOR_EACH_EDGE (e, ei, body[i]->succs)
|
|
|
580 {
|
|
|
581 if (flow_bb_inside_loop_p (loop, e->dest))
|
|
|
582 continue;
|
|
|
583
|
|
|
584 bitmap_set_bit (may_exit, i);
|
|
|
585 bitmap_set_bit (has_exit, i);
|
|
|
586 outermost_exit = find_common_loop (outermost_exit,
|
|
|
587 e->dest->loop_father);
|
|
|
588 }
|
|
|
589 continue;
|
|
|
590 }
|
|
|
591
|
|
|
592 /* Use the data stored for the subloop to decide whether we may exit
|
|
|
593 through it. It is sufficient to do this for header of the loop,
|
|
|
594 as other basic blocks inside it must be dominated by it. */
|
|
|
595 if (body[i]->loop_father->header != body[i])
|
|
|
596 continue;
|
|
|
597
|
|
|
598 if (LOOP_DATA (body[i]->loop_father)->has_call)
|
|
|
599 {
|
|
|
600 has_call = true;
|
|
|
601 bitmap_set_bit (may_exit, i);
|
|
|
602 }
|
|
|
603 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
|
|
|
604 if (aexit != loop)
|
|
|
605 {
|
|
|
606 bitmap_set_bit (may_exit, i);
|
|
|
607 bitmap_set_bit (has_exit, i);
|
|
|
608
|
|
|
609 if (flow_loop_nested_p (aexit, outermost_exit))
|
|
|
610 outermost_exit = aexit;
|
|
|
611 }
|
|
|
612 }
|
|
|
613
|
|
|
614 loop->aux = xcalloc (1, sizeof (struct loop_data));
|
|
|
615 LOOP_DATA (loop)->outermost_exit = outermost_exit;
|
|
|
616 LOOP_DATA (loop)->has_call = has_call;
|
|
|
617 }
|
|
|
618
|
|
|
619 /* Check whether we may assign a value to X from a register. */
|
|
|
620
|
|
|
621 static bool
|
|
|
622 may_assign_reg_p (rtx x)
|
|
|
623 {
|
|
|
624 return (GET_MODE (x) != VOIDmode
|
|
|
625 && GET_MODE (x) != BLKmode
|
|
|
626 && can_copy_p (GET_MODE (x))
|
|
|
627 && (!REG_P (x)
|
|
|
628 || !HARD_REGISTER_P (x)
|
|
|
629 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
|
|
|
630 }
|
|
|
631
|
|
|
632 /* Finds definitions that may correspond to invariants in LOOP with body
|
|
|
633 BODY. */
|
|
|
634
|
|
|
635 static void
|
|
|
636 find_defs (struct loop *loop, basic_block *body)
|
|
|
637 {
|
|
|
638 unsigned i;
|
|
|
639 bitmap blocks = BITMAP_ALLOC (NULL);
|
|
|
640
|
|
|
641 for (i = 0; i < loop->num_nodes; i++)
|
|
|
642 bitmap_set_bit (blocks, body[i]->index);
|
|
|
643
|
|
|
644 df_remove_problem (df_chain);
|
|
|
645 df_process_deferred_rescans ();
|
|
|
646 df_chain_add_problem (DF_UD_CHAIN);
|
|
|
647 df_set_blocks (blocks);
|
|
|
648 df_analyze ();
|
|
|
649
|
|
|
650 if (dump_file)
|
|
|
651 {
|
|
|
652 df_dump_region (dump_file);
|
|
|
653 fprintf (dump_file, "*****starting processing of loop ******\n");
|
|
|
654 print_rtl_with_bb (dump_file, get_insns ());
|
|
|
655 fprintf (dump_file, "*****ending processing of loop ******\n");
|
|
|
656 }
|
|
|
657 check_invariant_table_size ();
|
|
|
658
|
|
|
659 BITMAP_FREE (blocks);
|
|
|
660 }
|
|
|
661
|
|
|
662 /* Creates a new invariant for definition DEF in INSN, depending on invariants
|
|
|
663 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
|
|
|
664 unless the program ends due to a function call. The newly created invariant
|
|
|
665 is returned. */
|
|
|
666
|
|
|
667 static struct invariant *
|
|
|
668 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
|
|
|
669 bool always_executed)
|
|
|
670 {
|
|
|
671 struct invariant *inv = XNEW (struct invariant);
|
|
|
672 rtx set = single_set (insn);
|
|
|
673 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
|
|
|
674
|
|
|
675 inv->def = def;
|
|
|
676 inv->always_executed = always_executed;
|
|
|
677 inv->depends_on = depends_on;
|
|
|
678
|
|
|
679 /* If the set is simple, usually by moving it we move the whole store out of
|
|
|
680 the loop. Otherwise we save only cost of the computation. */
|
|
|
681 if (def)
|
|
|
682 inv->cost = rtx_cost (set, SET, speed);
|
|
|
683 else
|
|
|
684 inv->cost = rtx_cost (SET_SRC (set), SET, speed);
|
|
|
685
|
|
|
686 inv->move = false;
|
|
|
687 inv->reg = NULL_RTX;
|
|
|
688 inv->stamp = 0;
|
|
|
689 inv->insn = insn;
|
|
|
690
|
|
|
691 inv->invno = VEC_length (invariant_p, invariants);
|
|
|
692 inv->eqto = ~0u;
|
|
|
693 if (def)
|
|
|
694 def->invno = inv->invno;
|
|
|
695 VEC_safe_push (invariant_p, heap, invariants, inv);
|
|
|
696
|
|
|
697 if (dump_file)
|
|
|
698 {
|
|
|
699 fprintf (dump_file,
|
|
|
700 "Set in insn %d is invariant (%d), cost %d, depends on ",
|
|
|
701 INSN_UID (insn), inv->invno, inv->cost);
|
|
|
702 dump_bitmap (dump_file, inv->depends_on);
|
|
|
703 }
|
|
|
704
|
|
|
705 return inv;
|
|
|
706 }
|
|
|
707
|
|
|
708 /* Record USE at DEF. */
|
|
|
709
|
|
|
710 static void
|
|
|
711 record_use (struct def *def, rtx *use, rtx insn)
|
|
|
712 {
|
|
|
713 struct use *u = XNEW (struct use);
|
|
|
714
|
|
|
715 gcc_assert (REG_P (*use));
|
|
|
716
|
|
|
717 u->pos = use;
|
|
|
718 u->insn = insn;
|
|
|
719 u->next = def->uses;
|
|
|
720 def->uses = u;
|
|
|
721 def->n_uses++;
|
|
|
722 }
|
|
|
723
|
|
|
724 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
|
|
|
725 bitmap. Returns true if all dependencies of USE are known to be
|
|
|
726 loop invariants, false otherwise. */
|
|
|
727
|
|
|
728 static bool
|
|
|
729 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
|
|
|
730 {
|
|
|
731 df_ref def;
|
|
|
732 basic_block def_bb;
|
|
|
733 struct df_link *defs;
|
|
|
734 struct def *def_data;
|
|
|
735 struct invariant *inv;
|
|
|
736
|
|
|
737 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
|
|
|
738 return false;
|
|
|
739
|
|
|
740 defs = DF_REF_CHAIN (use);
|
|
|
741 if (!defs)
|
|
|
742 return true;
|
|
|
743
|
|
|
744 if (defs->next)
|
|
|
745 return false;
|
|
|
746
|
|
|
747 def = defs->ref;
|
|
|
748 check_invariant_table_size ();
|
|
|
749 inv = invariant_table[DF_REF_ID(def)];
|
|
|
750 if (!inv)
|
|
|
751 return false;
|
|
|
752
|
|
|
753 def_data = inv->def;
|
|
|
754 gcc_assert (def_data != NULL);
|
|
|
755
|
|
|
756 def_bb = DF_REF_BB (def);
|
|
|
757 /* Note that in case bb == def_bb, we know that the definition
|
|
|
758 dominates insn, because def has invariant_table[DF_REF_ID(def)]
|
|
|
759 defined and we process the insns in the basic block bb
|
|
|
760 sequentially. */
|
|
|
761 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
|
|
|
762 return false;
|
|
|
763
|
|
|
764 bitmap_set_bit (depends_on, def_data->invno);
|
|
|
765 return true;
|
|
|
766 }
|
|
|
767
|
|
|
768
|
|
|
769 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
|
|
|
770 bitmap. Returns true if all dependencies of INSN are known to be
|
|
|
771 loop invariants, false otherwise. */
|
|
|
772
|
|
|
773 static bool
|
|
|
774 check_dependencies (rtx insn, bitmap depends_on)
|
|
|
775 {
|
|
|
776 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
|
|
|
777 df_ref *use_rec;
|
|
|
778 basic_block bb = BLOCK_FOR_INSN (insn);
|
|
|
779
|
|
|
780 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
|
|
|
781 if (!check_dependency (bb, *use_rec, depends_on))
|
|
|
782 return false;
|
|
|
783 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
|
|
|
784 if (!check_dependency (bb, *use_rec, depends_on))
|
|
|
785 return false;
|
|
|
786
|
|
|
787 return true;
|
|
|
788 }
|
|
|
789
|
|
|
790 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
|
|
|
791 executed. ALWAYS_EXECUTED is true if the insn is always executed,
|
|
|
792 unless the program ends due to a function call. */
|
|
|
793
|
|
|
794 static void
|
|
|
795 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
|
|
|
796 {
|
|
|
797 df_ref ref;
|
|
|
798 struct def *def;
|
|
|
799 bitmap depends_on;
|
|
|
800 rtx set, dest;
|
|
|
801 bool simple = true;
|
|
|
802 struct invariant *inv;
|
|
|
803
|
|
|
804 #ifdef HAVE_cc0
|
|
|
805 /* We can't move a CC0 setter without the user. */
|
|
|
806 if (sets_cc0_p (insn))
|
|
|
807 return;
|
|
|
808 #endif
|
|
|
809
|
|
|
810 set = single_set (insn);
|
|
|
811 if (!set)
|
|
|
812 return;
|
|
|
813 dest = SET_DEST (set);
|
|
|
814
|
|
|
815 if (!REG_P (dest)
|
|
|
816 || HARD_REGISTER_P (dest))
|
|
|
817 simple = false;
|
|
|
818
|
|
|
819 if (!may_assign_reg_p (SET_DEST (set))
|
|
|
820 || !check_maybe_invariant (SET_SRC (set)))
|
|
|
821 return;
|
|
|
822
|
|
|
823 /* If the insn can throw exception, we cannot move it at all without changing
|
|
|
824 cfg. */
|
|
|
825 if (can_throw_internal (insn))
|
|
|
826 return;
|
|
|
827
|
|
|
828 /* We cannot make trapping insn executed, unless it was executed before. */
|
|
|
829 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
|
|
|
830 return;
|
|
|
831
|
|
|
832 depends_on = BITMAP_ALLOC (NULL);
|
|
|
833 if (!check_dependencies (insn, depends_on))
|
|
|
834 {
|
|
|
835 BITMAP_FREE (depends_on);
|
|
|
836 return;
|
|
|
837 }
|
|
|
838
|
|
|
839 if (simple)
|
|
|
840 def = XCNEW (struct def);
|
|
|
841 else
|
|
|
842 def = NULL;
|
|
|
843
|
|
|
844 inv = create_new_invariant (def, insn, depends_on, always_executed);
|
|
|
845
|
|
|
846 if (simple)
|
|
|
847 {
|
|
|
848 ref = df_find_def (insn, dest);
|
|
|
849 check_invariant_table_size ();
|
|
|
850 invariant_table[DF_REF_ID(ref)] = inv;
|
|
|
851 }
|
|
|
852 }
|
|
|
853
|
|
|
854 /* Record registers used in INSN that have a unique invariant definition. */
|
|
|
855
|
|
|
856 static void
|
|
|
857 record_uses (rtx insn)
|
|
|
858 {
|
|
|
859 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
|
|
|
860 df_ref *use_rec;
|
|
|
861 struct invariant *inv;
|
|
|
862
|
|
|
863 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
|
|
|
864 {
|
|
|
865 df_ref use = *use_rec;
|
|
|
866 inv = invariant_for_use (use);
|
|
|
867 if (inv)
|
|
|
868 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
|
|
|
869 }
|
|
|
870 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
|
|
|
871 {
|
|
|
872 df_ref use = *use_rec;
|
|
|
873 inv = invariant_for_use (use);
|
|
|
874 if (inv)
|
|
|
875 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
|
|
|
876 }
|
|
|
877 }
|
|
|
878
|
|
|
879 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
|
|
|
880 executed. ALWAYS_EXECUTED is true if the insn is always executed,
|
|
|
881 unless the program ends due to a function call. */
|
|
|
882
|
|
|
883 static void
|
|
|
884 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
|
|
|
885 {
|
|
|
886 find_invariant_insn (insn, always_reached, always_executed);
|
|
|
887 record_uses (insn);
|
|
|
888 }
|
|
|
889
|
|
|
890 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
|
|
|
891 basic block is always executed. ALWAYS_EXECUTED is true if the basic
|
|
|
892 block is always executed, unless the program ends due to a function
|
|
|
893 call. */
|
|
|
894
|
|
|
895 static void
|
|
|
896 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
|
|
|
897 {
|
|
|
898 rtx insn;
|
|
|
899
|
|
|
900 FOR_BB_INSNS (bb, insn)
|
|
|
901 {
|
|
|
902 if (!INSN_P (insn))
|
|
|
903 continue;
|
|
|
904
|
|
|
905 find_invariants_insn (insn, always_reached, always_executed);
|
|
|
906
|
|
|
907 if (always_reached
|
|
|
908 && CALL_P (insn)
|
|
|
909 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
|
|
|
910 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
|
|
|
911 always_reached = false;
|
|
|
912 }
|
|
|
913 }
|
|
|
914
|
|
|
915 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
|
|
|
916 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
|
|
|
917 bitmap of basic blocks in BODY that are always executed unless the program
|
|
|
918 ends due to a function call. */
|
|
|
919
|
|
|
920 static void
|
|
|
921 find_invariants_body (struct loop *loop, basic_block *body,
|
|
|
922 bitmap always_reached, bitmap always_executed)
|
|
|
923 {
|
|
|
924 unsigned i;
|
|
|
925
|
|
|
926 for (i = 0; i < loop->num_nodes; i++)
|
|
|
927 find_invariants_bb (body[i],
|
|
|
928 bitmap_bit_p (always_reached, i),
|
|
|
929 bitmap_bit_p (always_executed, i));
|
|
|
930 }
|
|
|
931
|
|
|
932 /* Finds invariants in LOOP. */
|
|
|
933
|
|
|
934 static void
|
|
|
935 find_invariants (struct loop *loop)
|
|
|
936 {
|
|
|
937 bitmap may_exit = BITMAP_ALLOC (NULL);
|
|
|
938 bitmap always_reached = BITMAP_ALLOC (NULL);
|
|
|
939 bitmap has_exit = BITMAP_ALLOC (NULL);
|
|
|
940 bitmap always_executed = BITMAP_ALLOC (NULL);
|
|
|
941 basic_block *body = get_loop_body_in_dom_order (loop);
|
|
|
942
|
|
|
943 find_exits (loop, body, may_exit, has_exit);
|
|
|
944 compute_always_reached (loop, body, may_exit, always_reached);
|
|
|
945 compute_always_reached (loop, body, has_exit, always_executed);
|
|
|
946
|
|
|
947 find_defs (loop, body);
|
|
|
948 find_invariants_body (loop, body, always_reached, always_executed);
|
|
|
949 merge_identical_invariants ();
|
|
|
950
|
|
|
951 BITMAP_FREE (always_reached);
|
|
|
952 BITMAP_FREE (always_executed);
|
|
|
953 BITMAP_FREE (may_exit);
|
|
|
954 BITMAP_FREE (has_exit);
|
|
|
955 free (body);
|
|
|
956 }
|
|
|
957
|
|
|
958 /* Frees a list of uses USE. */
|
|
|
959
|
|
|
960 static void
|
|
|
961 free_use_list (struct use *use)
|
|
|
962 {
|
|
|
963 struct use *next;
|
|
|
964
|
|
|
965 for (; use; use = next)
|
|
|
966 {
|
|
|
967 next = use->next;
|
|
|
968 free (use);
|
|
|
969 }
|
|
|
970 }
|
|
|
971
|
|
|
972 /* Calculates cost and number of registers needed for moving invariant INV
|
|
|
973 out of the loop and stores them to *COST and *REGS_NEEDED. */
|
|
|
974
|
|
|
975 static void
|
|
|
976 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
|
|
|
977 {
|
|
|
978 int acomp_cost;
|
|
|
979 unsigned aregs_needed;
|
|
|
980 unsigned depno;
|
|
|
981 struct invariant *dep;
|
|
|
982 bitmap_iterator bi;
|
|
|
983
|
|
|
984 /* Find the representative of the class of the equivalent invariants. */
|
|
|
985 inv = VEC_index (invariant_p, invariants, inv->eqto);
|
|
|
986
|
|
|
987 *comp_cost = 0;
|
|
|
988 *regs_needed = 0;
|
|
|
989 if (inv->move
|
|
|
990 || inv->stamp == actual_stamp)
|
|
|
991 return;
|
|
|
992 inv->stamp = actual_stamp;
|
|
|
993
|
|
|
994 (*regs_needed)++;
|
|
|
995 (*comp_cost) += inv->cost;
|
|
|
996
|
|
|
997 #ifdef STACK_REGS
|
|
|
998 {
|
|
|
999 /* Hoisting constant pool constants into stack regs may cost more than
|
|
|
1000 just single register. On x87, the balance is affected both by the
|
|
|
1001 small number of FP registers, and by its register stack organization,
|
|
|
1002 that forces us to add compensation code in and around the loop to
|
|
|
1003 shuffle the operands to the top of stack before use, and pop them
|
|
|
1004 from the stack after the loop finishes.
|
|
|
1005
|
|
|
1006 To model this effect, we increase the number of registers needed for
|
|
|
1007 stack registers by two: one register push, and one register pop.
|
|
|
1008 This usually has the effect that FP constant loads from the constant
|
|
|
1009 pool are not moved out of the loop.
|
|
|
1010
|
|
|
1011 Note that this also means that dependent invariants can not be moved.
|
|
|
1012 However, the primary purpose of this pass is to move loop invariant
|
|
|
1013 address arithmetic out of loops, and address arithmetic that depends
|
|
|
1014 on floating point constants is unlikely to ever occur. */
|
|
|
1015 rtx set = single_set (inv->insn);
|
|
|
1016 if (set
|
|
|
1017 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
|
|
|
1018 && constant_pool_constant_p (SET_SRC (set)))
|
|
|
1019 (*regs_needed) += 2;
|
|
|
1020 }
|
|
|
1021 #endif
|
|
|
1022
|
|
|
1023 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
|
|
|
1024 {
|
|
|
1025 dep = VEC_index (invariant_p, invariants, depno);
|
|
|
1026
|
|
|
1027 get_inv_cost (dep, &acomp_cost, &aregs_needed);
|
|
|
1028
|
|
|
1029 if (aregs_needed
|
|
|
1030 /* We need to check always_executed, since if the original value of
|
|
|
1031 the invariant may be preserved, we may need to keep it in a
|
|
|
1032 separate register. TODO check whether the register has an
|
|
|
1033 use outside of the loop. */
|
|
|
1034 && dep->always_executed
|
|
|
1035 && !dep->def->uses->next)
|
|
|
1036 {
|
|
|
1037 /* If this is a single use, after moving the dependency we will not
|
|
|
1038 need a new register. */
|
|
|
1039 aregs_needed--;
|
|
|
1040 }
|
|
|
1041
|
|
|
1042 (*regs_needed) += aregs_needed;
|
|
|
1043 (*comp_cost) += acomp_cost;
|
|
|
1044 }
|
|
|
1045 }
|
|
|
1046
|
|
|
1047 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
|
|
|
1048 of registers used in the loop, NEW_REGS is the number of new variables
|
|
|
1049 already added due to the invariant motion. The number of registers needed
|
|
|
1050 for it is stored in *REGS_NEEDED. */
|
|
|
1051
|
|
|
1052 static int
|
|
|
1053 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
|
|
|
1054 unsigned new_regs, unsigned regs_used, bool speed)
|
|
|
1055 {
|
|
|
1056 int comp_cost, size_cost;
|
|
|
1057
|
|
|
1058 get_inv_cost (inv, &comp_cost, regs_needed);
|
|
|
1059 actual_stamp++;
|
|
|
1060
|
|
|
1061 size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used, speed)
|
|
|
1062 - estimate_reg_pressure_cost (new_regs, regs_used, speed));
|
|
|
1063
|
|
|
1064 return comp_cost - size_cost;
|
|
|
1065 }
|
|
|
1066
|
|
|
1067 /* Finds invariant with best gain for moving. Returns the gain, stores
|
|
|
1068 the invariant in *BEST and number of registers needed for it to
|
|
|
1069 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
|
|
|
1070 NEW_REGS is the number of new variables already added due to invariant
|
|
|
1071 motion. */
|
|
|
1072
|
|
|
1073 static int
|
|
|
1074 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
|
|
|
1075 unsigned new_regs, unsigned regs_used, bool speed)
|
|
|
1076 {
|
|
|
1077 struct invariant *inv;
|
|
|
1078 int gain = 0, again;
|
|
|
1079 unsigned aregs_needed, invno;
|
|
|
1080
|
|
|
1081 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
|
|
|
1082 {
|
|
|
1083 if (inv->move)
|
|
|
1084 continue;
|
|
|
1085
|
|
|
1086 /* Only consider the "representatives" of equivalent invariants. */
|
|
|
1087 if (inv->eqto != inv->invno)
|
|
|
1088 continue;
|
|
|
1089
|
|
|
1090 again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used,
|
|
|
1091 speed);
|
|
|
1092 if (again > gain)
|
|
|
1093 {
|
|
|
1094 gain = again;
|
|
|
1095 *best = inv;
|
|
|
1096 *regs_needed = aregs_needed;
|
|
|
1097 }
|
|
|
1098 }
|
|
|
1099
|
|
|
1100 return gain;
|
|
|
1101 }
|
|
|
1102
|
|
|
1103 /* Marks invariant INVNO and all its dependencies for moving. */
|
|
|
1104
|
|
|
1105 static void
|
|
|
1106 set_move_mark (unsigned invno)
|
|
|
1107 {
|
|
|
1108 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
|
|
|
1109 bitmap_iterator bi;
|
|
|
1110
|
|
|
1111 /* Find the representative of the class of the equivalent invariants. */
|
|
|
1112 inv = VEC_index (invariant_p, invariants, inv->eqto);
|
|
|
1113
|
|
|
1114 if (inv->move)
|
|
|
1115 return;
|
|
|
1116 inv->move = true;
|
|
|
1117
|
|
|
1118 if (dump_file)
|
|
|
1119 fprintf (dump_file, "Decided to move invariant %d\n", invno);
|
|
|
1120
|
|
|
1121 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
|
|
|
1122 {
|
|
|
1123 set_move_mark (invno);
|
|
|
1124 }
|
|
|
1125 }
|
|
|
1126
|
|
|
1127 /* Determines which invariants to move. */
|
|
|
1128
|
|
|
1129 static void
|
|
|
1130 find_invariants_to_move (bool speed)
|
|
|
1131 {
|
|
|
1132 unsigned i, regs_used, regs_needed = 0, new_regs;
|
|
|
1133 struct invariant *inv = NULL;
|
|
|
1134 unsigned int n_regs = DF_REG_SIZE (df);
|
|
|
1135
|
|
|
1136 if (!VEC_length (invariant_p, invariants))
|
|
|
1137 return;
|
|
|
1138
|
|
|
1139 /* We do not really do a good job in estimating number of registers used;
|
|
|
1140 we put some initial bound here to stand for induction variables etc.
|
|
|
1141 that we do not detect. */
|
|
|
1142 regs_used = 2;
|
|
|
1143
|
|
|
1144 for (i = 0; i < n_regs; i++)
|
|
|
1145 {
|
|
|
1146 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
|
|
|
1147 {
|
|
|
1148 /* This is a value that is used but not changed inside loop. */
|
|
|
1149 regs_used++;
|
|
|
1150 }
|
|
|
1151 }
|
|
|
1152
|
|
|
1153 new_regs = 0;
|
|
|
1154 while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used, speed) > 0)
|
|
|
1155 {
|
|
|
1156 set_move_mark (inv->invno);
|
|
|
1157 new_regs += regs_needed;
|
|
|
1158 }
|
|
|
1159 }
|
|
|
1160
|
|
|
1161 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
|
|
|
1162 otherwise. */
|
|
|
1163
|
|
|
1164 static bool
|
|
|
1165 move_invariant_reg (struct loop *loop, unsigned invno)
|
|
|
1166 {
|
|
|
1167 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
|
|
|
1168 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
|
|
|
1169 unsigned i;
|
|
|
1170 basic_block preheader = loop_preheader_edge (loop)->src;
|
|
|
1171 rtx reg, set, dest, note;
|
|
|
1172 struct use *use;
|
|
|
1173 bitmap_iterator bi;
|
|
|
1174
|
|
|
1175 if (inv->reg)
|
|
|
1176 return true;
|
|
|
1177 if (!repr->move)
|
|
|
1178 return false;
|
|
|
1179 /* If this is a representative of the class of equivalent invariants,
|
|
|
1180 really move the invariant. Otherwise just replace its use with
|
|
|
1181 the register used for the representative. */
|
|
|
1182 if (inv == repr)
|
|
|
1183 {
|
|
|
1184 if (inv->depends_on)
|
|
|
1185 {
|
|
|
1186 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
|
|
|
1187 {
|
|
|
1188 if (!move_invariant_reg (loop, i))
|
|
|
1189 goto fail;
|
|
|
1190 }
|
|
|
1191 }
|
|
|
1192
|
|
|
1193 /* Move the set out of the loop. If the set is always executed (we could
|
|
|
1194 omit this condition if we know that the register is unused outside of the
|
|
|
1195 loop, but it does not seem worth finding out) and it has no uses that
|
|
|
1196 would not be dominated by it, we may just move it (TODO). Otherwise we
|
|
|
1197 need to create a temporary register. */
|
|
|
1198 set = single_set (inv->insn);
|
|
|
1199 dest = SET_DEST (set);
|
|
|
1200 reg = gen_reg_rtx_and_attrs (dest);
|
|
|
1201
|
|
|
1202 /* Try replacing the destination by a new pseudoregister. */
|
|
|
1203 if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
|
|
|
1204 goto fail;
|
|
|
1205 df_insn_rescan (inv->insn);
|
|
|
1206
|
|
|
1207 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
|
|
|
1208 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
|
|
|
1209
|
|
|
1210 /* If there is a REG_EQUAL note on the insn we just moved, and
|
|
|
1211 insn is in a basic block that is not always executed, the note
|
|
|
1212 may no longer be valid after we move the insn.
|
|
|
1213 Note that uses in REG_EQUAL notes are taken into account in
|
|
|
1214 the computation of invariants. Hence it is safe to retain the
|
|
|
1215 note even if the note contains register references. */
|
|
|
1216 if (! inv->always_executed
|
|
|
1217 && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
|
|
|
1218 remove_note (inv->insn, note);
|
|
|
1219 }
|
|
|
1220 else
|
|
|
1221 {
|
|
|
1222 if (!move_invariant_reg (loop, repr->invno))
|
|
|
1223 goto fail;
|
|
|
1224 reg = repr->reg;
|
|
|
1225 set = single_set (inv->insn);
|
|
|
1226 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
|
|
|
1227 delete_insn (inv->insn);
|
|
|
1228 }
|
|
|
1229
|
|
|
1230
|
|
|
1231 inv->reg = reg;
|
|
|
1232
|
|
|
1233 /* Replace the uses we know to be dominated. It saves work for copy
|
|
|
1234 propagation, and also it is necessary so that dependent invariants
|
|
|
1235 are computed right. */
|
|
|
1236 if (inv->def)
|
|
|
1237 {
|
|
|
1238 for (use = inv->def->uses; use; use = use->next)
|
|
|
1239 {
|
|
|
1240 *use->pos = reg;
|
|
|
1241 df_insn_rescan (use->insn);
|
|
|
1242 }
|
|
|
1243 }
|
|
|
1244
|
|
|
1245 return true;
|
|
|
1246
|
|
|
1247 fail:
|
|
|
1248 /* If we failed, clear move flag, so that we do not try to move inv
|
|
|
1249 again. */
|
|
|
1250 if (dump_file)
|
|
|
1251 fprintf (dump_file, "Failed to move invariant %d\n", invno);
|
|
|
1252 inv->move = false;
|
|
|
1253 inv->reg = NULL_RTX;
|
|
|
1254
|
|
|
1255 return false;
|
|
|
1256 }
|
|
|
1257
|
|
|
1258 /* Move selected invariant out of the LOOP. Newly created regs are marked
|
|
|
1259 in TEMPORARY_REGS. */
|
|
|
1260
|
|
|
1261 static void
|
|
|
1262 move_invariants (struct loop *loop)
|
|
|
1263 {
|
|
|
1264 struct invariant *inv;
|
|
|
1265 unsigned i;
|
|
|
1266
|
|
|
1267 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
|
|
|
1268 move_invariant_reg (loop, i);
|
|
|
1269 }
|
|
|
1270
|
|
|
1271 /* Initializes invariant motion data. */
|
|
|
1272
|
|
|
1273 static void
|
|
|
1274 init_inv_motion_data (void)
|
|
|
1275 {
|
|
|
1276 actual_stamp = 1;
|
|
|
1277
|
|
|
1278 invariants = VEC_alloc (invariant_p, heap, 100);
|
|
|
1279 }
|
|
|
1280
|
|
|
1281 /* Frees the data allocated by invariant motion. */
|
|
|
1282
|
|
|
1283 static void
|
|
|
1284 free_inv_motion_data (void)
|
|
|
1285 {
|
|
|
1286 unsigned i;
|
|
|
1287 struct def *def;
|
|
|
1288 struct invariant *inv;
|
|
|
1289
|
|
|
1290 check_invariant_table_size ();
|
|
|
1291 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
|
|
|
1292 {
|
|
|
1293 inv = invariant_table[i];
|
|
|
1294 if (inv)
|
|
|
1295 {
|
|
|
1296 def = inv->def;
|
|
|
1297 gcc_assert (def != NULL);
|
|
|
1298
|
|
|
1299 free_use_list (def->uses);
|
|
|
1300 free (def);
|
|
|
1301 invariant_table[i] = NULL;
|
|
|
1302 }
|
|
|
1303 }
|
|
|
1304
|
|
|
1305 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
|
|
|
1306 {
|
|
|
1307 BITMAP_FREE (inv->depends_on);
|
|
|
1308 free (inv);
|
|
|
1309 }
|
|
|
1310 VEC_free (invariant_p, heap, invariants);
|
|
|
1311 }
|
|
|
1312
|
|
|
1313 /* Move the invariants out of the LOOP. */
|
|
|
1314
|
|
|
1315 static void
|
|
|
1316 move_single_loop_invariants (struct loop *loop)
|
|
|
1317 {
|
|
|
1318 init_inv_motion_data ();
|
|
|
1319
|
|
|
1320 find_invariants (loop);
|
|
|
1321 find_invariants_to_move (optimize_loop_for_speed_p (loop));
|
|
|
1322 move_invariants (loop);
|
|
|
1323
|
|
|
1324 free_inv_motion_data ();
|
|
|
1325 }
|
|
|
1326
|
|
|
1327 /* Releases the auxiliary data for LOOP. */
|
|
|
1328
|
|
|
1329 static void
|
|
|
1330 free_loop_data (struct loop *loop)
|
|
|
1331 {
|
|
|
1332 struct loop_data *data = LOOP_DATA (loop);
|
|
|
1333
|
|
|
1334 free (data);
|
|
|
1335 loop->aux = NULL;
|
|
|
1336 }
|
|
|
1337
|
|
|
1338 /* Move the invariants out of the loops. */
|
|
|
1339
|
|
|
1340 void
|
|
|
1341 move_loop_invariants (void)
|
|
|
1342 {
|
|
|
1343 struct loop *loop;
|
|
|
1344 loop_iterator li;
|
|
|
1345
|
|
|
1346 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
|
|
|
1347 /* Process the loops, innermost first. */
|
|
|
1348 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
|
|
|
1349 {
|
|
|
1350 /* move_single_loop_invariants for very large loops
|
|
|
1351 is time consuming and might need a lot of memory. */
|
|
|
1352 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
|
|
|
1353 move_single_loop_invariants (loop);
|
|
|
1354 }
|
|
|
1355
|
|
|
1356 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1357 {
|
|
|
1358 free_loop_data (loop);
|
|
|
1359 }
|
|
|
1360
|
|
|
1361 free (invariant_table);
|
|
|
1362 invariant_table = NULL;
|
|
|
1363 invariant_table_size = 0;
|
|
|
1364
|
|
|
1365 #ifdef ENABLE_CHECKING
|
|
|
1366 verify_flow_info ();
|
|
|
1367 #endif
|
|
|
1368 }
|
