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