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