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