Daily bump.
[gcc.git] / gcc / store-motion.c
1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "diagnostic-core.h"
26 #include "toplev.h"
27
28 #include "rtl.h"
29 #include "tree.h"
30 #include "tm_p.h"
31 #include "regs.h"
32 #include "hard-reg-set.h"
33 #include "flags.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "basic-block.h"
37 #include "function.h"
38 #include "expr.h"
39 #include "except.h"
40 #include "ggc.h"
41 #include "intl.h"
42 #include "tree-pass.h"
43 #include "hashtab.h"
44 #include "df.h"
45 #include "dbgcnt.h"
46
47 /* This pass implements downward store motion.
48 As of May 1, 2009, the pass is not enabled by default on any target,
49 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
50
51 /* TODO:
52 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
53 a compile time hog that needs a rewrite (maybe cache st_exprs to
54 invalidate REG_EQUAL/REG_EQUIV notes for?).
55 - pattern_regs in st_expr should be a regset (on its own obstack).
56 - antic_stores and avail_stores should be VECs instead of lists.
57 - store_motion_mems should be a vec instead of a list.
58 - there should be an alloc pool for struct st_expr objects.
59 - investigate whether it is helpful to make the address of an st_expr
60 a cselib VALUE.
61 - when GIMPLE alias information is exported, the effectiveness of this
62 pass should be re-evaluated.
63 */
64
65 /* This is a list of store expressions (MEMs). The structure is used
66 as an expression table to track stores which look interesting, and
67 might be moveable towards the exit block. */
68
69 struct st_expr
70 {
71 /* Pattern of this mem. */
72 rtx pattern;
73 /* List of registers mentioned by the mem. */
74 rtx pattern_regs;
75 /* INSN list of stores that are locally anticipatable. */
76 rtx antic_stores;
77 /* INSN list of stores that are locally available. */
78 rtx avail_stores;
79 /* Next in the list. */
80 struct st_expr * next;
81 /* Store ID in the dataflow bitmaps. */
82 int index;
83 /* Hash value for the hash table. */
84 unsigned int hash_index;
85 /* Register holding the stored expression when a store is moved.
86 This field is also used as a cache in find_moveable_store, see
87 LAST_AVAIL_CHECK_FAILURE below. */
88 rtx reaching_reg;
89 };
90
91 /* Head of the list of load/store memory refs. */
92 static struct st_expr * store_motion_mems = NULL;
93
94 /* Hashtable for the load/store memory refs. */
95 static htab_t store_motion_mems_table = NULL;
96
97 /* These bitmaps will hold the local dataflow properties per basic block. */
98 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
99
100 /* Nonzero for expressions which should be inserted on a specific edge. */
101 static sbitmap *st_insert_map;
102
103 /* Nonzero for expressions which should be deleted in a specific block. */
104 static sbitmap *st_delete_map;
105
106 /* Global holding the number of store expressions we are dealing with. */
107 static int num_stores;
108
109 /* Contains the edge_list returned by pre_edge_lcm. */
110 static struct edge_list *edge_list;
111
112 static hashval_t
113 pre_st_expr_hash (const void *p)
114 {
115 int do_not_record_p = 0;
116 const struct st_expr *const x = (const struct st_expr *) p;
117 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
118 }
119
120 static int
121 pre_st_expr_eq (const void *p1, const void *p2)
122 {
123 const struct st_expr *const ptr1 = (const struct st_expr *) p1,
124 *const ptr2 = (const struct st_expr *) p2;
125 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
126 }
127
128 /* This will search the st_expr list for a matching expression. If it
129 doesn't find one, we create one and initialize it. */
130
131 static struct st_expr *
132 st_expr_entry (rtx x)
133 {
134 int do_not_record_p = 0;
135 struct st_expr * ptr;
136 unsigned int hash;
137 void **slot;
138 struct st_expr e;
139
140 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
141 NULL, /*have_reg_qty=*/false);
142
143 e.pattern = x;
144 slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT);
145 if (*slot)
146 return (struct st_expr *)*slot;
147
148 ptr = XNEW (struct st_expr);
149
150 ptr->next = store_motion_mems;
151 ptr->pattern = x;
152 ptr->pattern_regs = NULL_RTX;
153 ptr->antic_stores = NULL_RTX;
154 ptr->avail_stores = NULL_RTX;
155 ptr->reaching_reg = NULL_RTX;
156 ptr->index = 0;
157 ptr->hash_index = hash;
158 store_motion_mems = ptr;
159 *slot = ptr;
160
161 return ptr;
162 }
163
164 /* Free up an individual st_expr entry. */
165
166 static void
167 free_st_expr_entry (struct st_expr * ptr)
168 {
169 free_INSN_LIST_list (& ptr->antic_stores);
170 free_INSN_LIST_list (& ptr->avail_stores);
171
172 free (ptr);
173 }
174
175 /* Free up all memory associated with the st_expr list. */
176
177 static void
178 free_store_motion_mems (void)
179 {
180 if (store_motion_mems_table)
181 htab_delete (store_motion_mems_table);
182 store_motion_mems_table = NULL;
183
184 while (store_motion_mems)
185 {
186 struct st_expr * tmp = store_motion_mems;
187 store_motion_mems = store_motion_mems->next;
188 free_st_expr_entry (tmp);
189 }
190 store_motion_mems = NULL;
191 }
192
193 /* Assign each element of the list of mems a monotonically increasing value. */
194
195 static int
196 enumerate_store_motion_mems (void)
197 {
198 struct st_expr * ptr;
199 int n = 0;
200
201 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
202 ptr->index = n++;
203
204 return n;
205 }
206
207 /* Return first item in the list. */
208
209 static inline struct st_expr *
210 first_st_expr (void)
211 {
212 return store_motion_mems;
213 }
214
215 /* Return the next item in the list after the specified one. */
216
217 static inline struct st_expr *
218 next_st_expr (struct st_expr * ptr)
219 {
220 return ptr->next;
221 }
222
223 /* Dump debugging info about the store_motion_mems list. */
224
225 static void
226 print_store_motion_mems (FILE * file)
227 {
228 struct st_expr * ptr;
229
230 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
231
232 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
233 {
234 fprintf (file, " Pattern (%3d): ", ptr->index);
235
236 print_rtl (file, ptr->pattern);
237
238 fprintf (file, "\n ANTIC stores : ");
239
240 if (ptr->antic_stores)
241 print_rtl (file, ptr->antic_stores);
242 else
243 fprintf (file, "(nil)");
244
245 fprintf (file, "\n AVAIL stores : ");
246
247 if (ptr->avail_stores)
248 print_rtl (file, ptr->avail_stores);
249 else
250 fprintf (file, "(nil)");
251
252 fprintf (file, "\n\n");
253 }
254
255 fprintf (file, "\n");
256 }
257 \f
258 /* Return zero if some of the registers in list X are killed
259 due to set of registers in bitmap REGS_SET. */
260
261 static bool
262 store_ops_ok (const_rtx x, int *regs_set)
263 {
264 const_rtx reg;
265
266 for (; x; x = XEXP (x, 1))
267 {
268 reg = XEXP (x, 0);
269 if (regs_set[REGNO(reg)])
270 return false;
271 }
272
273 return true;
274 }
275
276 /* Helper for extract_mentioned_regs. */
277
278 static int
279 extract_mentioned_regs_1 (rtx *loc, void *data)
280 {
281 rtx *mentioned_regs_p = (rtx *) data;
282
283 if (REG_P (*loc))
284 *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
285
286 return 0;
287 }
288
289 /* Returns a list of registers mentioned in X.
290 FIXME: A regset would be prettier and less expensive. */
291
292 static rtx
293 extract_mentioned_regs (rtx x)
294 {
295 rtx mentioned_regs = NULL;
296 for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
297 return mentioned_regs;
298 }
299
300 /* Check to see if the load X is aliased with STORE_PATTERN.
301 AFTER is true if we are checking the case when STORE_PATTERN occurs
302 after the X. */
303
304 static bool
305 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
306 {
307 if (after)
308 return anti_dependence (x, store_pattern);
309 else
310 return true_dependence (store_pattern, GET_MODE (store_pattern), x);
311 }
312
313 /* Go through the entire rtx X, looking for any loads which might alias
314 STORE_PATTERN. Return true if found.
315 AFTER is true if we are checking the case when STORE_PATTERN occurs
316 after the insn X. */
317
318 static bool
319 find_loads (const_rtx x, const_rtx store_pattern, int after)
320 {
321 const char * fmt;
322 int i, j;
323 int ret = false;
324
325 if (!x)
326 return false;
327
328 if (GET_CODE (x) == SET)
329 x = SET_SRC (x);
330
331 if (MEM_P (x))
332 {
333 if (load_kills_store (x, store_pattern, after))
334 return true;
335 }
336
337 /* Recursively process the insn. */
338 fmt = GET_RTX_FORMAT (GET_CODE (x));
339
340 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
341 {
342 if (fmt[i] == 'e')
343 ret |= find_loads (XEXP (x, i), store_pattern, after);
344 else if (fmt[i] == 'E')
345 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
346 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
347 }
348 return ret;
349 }
350
351 /* Go through pattern PAT looking for any loads which might kill the
352 store in X. Return true if found.
353 AFTER is true if we are checking the case when loads kill X occurs
354 after the insn for PAT. */
355
356 static inline bool
357 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
358 {
359 if (GET_CODE (pat) == SET)
360 {
361 rtx dest = SET_DEST (pat);
362
363 if (GET_CODE (dest) == ZERO_EXTRACT)
364 dest = XEXP (dest, 0);
365
366 /* Check for memory stores to aliased objects. */
367 if (MEM_P (dest)
368 && !exp_equiv_p (dest, x, 0, true))
369 {
370 if (after)
371 {
372 if (output_dependence (dest, x))
373 return true;
374 }
375 else
376 {
377 if (output_dependence (x, dest))
378 return true;
379 }
380 }
381 }
382
383 if (find_loads (pat, x, after))
384 return true;
385
386 return false;
387 }
388
389 /* Check if INSN kills the store pattern X (is aliased with it).
390 AFTER is true if we are checking the case when store X occurs
391 after the insn. Return true if it does. */
392
393 static bool
394 store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
395 {
396 const_rtx reg, note, pat;
397
398 if (! NONDEBUG_INSN_P (insn))
399 return false;
400
401 if (CALL_P (insn))
402 {
403 /* A normal or pure call might read from pattern,
404 but a const call will not. */
405 if (!RTL_CONST_CALL_P (insn))
406 return true;
407
408 /* But even a const call reads its parameters. Check whether the
409 base of some of registers used in mem is stack pointer. */
410 for (reg = x_regs; reg; reg = XEXP (reg, 1))
411 if (may_be_sp_based_p (XEXP (reg, 0)))
412 return true;
413
414 return false;
415 }
416
417 pat = PATTERN (insn);
418 if (GET_CODE (pat) == SET)
419 {
420 if (store_killed_in_pat (x, pat, after))
421 return true;
422 }
423 else if (GET_CODE (pat) == PARALLEL)
424 {
425 int i;
426
427 for (i = 0; i < XVECLEN (pat, 0); i++)
428 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
429 return true;
430 }
431 else if (find_loads (PATTERN (insn), x, after))
432 return true;
433
434 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
435 location aliased with X, then this insn kills X. */
436 note = find_reg_equal_equiv_note (insn);
437 if (! note)
438 return false;
439 note = XEXP (note, 0);
440
441 /* However, if the note represents a must alias rather than a may
442 alias relationship, then it does not kill X. */
443 if (exp_equiv_p (note, x, 0, true))
444 return false;
445
446 /* See if there are any aliased loads in the note. */
447 return find_loads (note, x, after);
448 }
449
450 /* Returns true if the expression X is loaded or clobbered on or after INSN
451 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
452 or after the insn. X_REGS is list of registers mentioned in X. If the store
453 is killed, return the last insn in that it occurs in FAIL_INSN. */
454
455 static bool
456 store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
457 int *regs_set_after, rtx *fail_insn)
458 {
459 rtx last = BB_END (bb), act;
460
461 if (!store_ops_ok (x_regs, regs_set_after))
462 {
463 /* We do not know where it will happen. */
464 if (fail_insn)
465 *fail_insn = NULL_RTX;
466 return true;
467 }
468
469 /* Scan from the end, so that fail_insn is determined correctly. */
470 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
471 if (store_killed_in_insn (x, x_regs, act, false))
472 {
473 if (fail_insn)
474 *fail_insn = act;
475 return true;
476 }
477
478 return false;
479 }
480
481 /* Returns true if the expression X is loaded or clobbered on or before INSN
482 within basic block BB. X_REGS is list of registers mentioned in X.
483 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
484 static bool
485 store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
486 int *regs_set_before)
487 {
488 rtx first = BB_HEAD (bb);
489
490 if (!store_ops_ok (x_regs, regs_set_before))
491 return true;
492
493 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
494 if (store_killed_in_insn (x, x_regs, insn, true))
495 return true;
496
497 return false;
498 }
499
500 /* The last insn in the basic block that compute_store_table is processing,
501 where store_killed_after is true for X.
502 Since we go through the basic block from BB_END to BB_HEAD, this is
503 also the available store at the end of the basic block. Therefore
504 this is in effect a cache, to avoid calling store_killed_after for
505 equivalent aliasing store expressions.
506 This value is only meaningful during the computation of the store
507 table. We hi-jack the REACHING_REG field of struct st_expr to save
508 a bit of memory. */
509 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
510
511 /* Determine whether INSN is MEM store pattern that we will consider moving.
512 REGS_SET_BEFORE is bitmap of registers set before (and including) the
513 current insn, REGS_SET_AFTER is bitmap of registers set after (and
514 including) the insn in this basic block. We must be passing through BB from
515 head to end, as we are using this fact to speed things up.
516
517 The results are stored this way:
518
519 -- the first anticipatable expression is added into ANTIC_STORES
520 -- if the processed expression is not anticipatable, NULL_RTX is added
521 there instead, so that we can use it as indicator that no further
522 expression of this type may be anticipatable
523 -- if the expression is available, it is added as head of AVAIL_STORES;
524 consequently, all of them but this head are dead and may be deleted.
525 -- if the expression is not available, the insn due to that it fails to be
526 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
527
528 The things are complicated a bit by fact that there already may be stores
529 to the same MEM from other blocks; also caller must take care of the
530 necessary cleanup of the temporary markers after end of the basic block.
531 */
532
533 static void
534 find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
535 {
536 struct st_expr * ptr;
537 rtx dest, set, tmp;
538 int check_anticipatable, check_available;
539 basic_block bb = BLOCK_FOR_INSN (insn);
540
541 set = single_set (insn);
542 if (!set)
543 return;
544
545 dest = SET_DEST (set);
546
547 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
548 || GET_MODE (dest) == BLKmode)
549 return;
550
551 if (side_effects_p (dest))
552 return;
553
554 /* If we are handling exceptions, we must be careful with memory references
555 that may trap. If we are not, the behavior is undefined, so we may just
556 continue. */
557 if (cfun->can_throw_non_call_exceptions && may_trap_p (dest))
558 return;
559
560 /* Even if the destination cannot trap, the source may. In this case we'd
561 need to handle updating the REG_EH_REGION note. */
562 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
563 return;
564
565 /* Make sure that the SET_SRC of this store insns can be assigned to
566 a register, or we will fail later on in replace_store_insn, which
567 assumes that we can do this. But sometimes the target machine has
568 oddities like MEM read-modify-write instruction. See for example
569 PR24257. */
570 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
571 return;
572
573 ptr = st_expr_entry (dest);
574 if (!ptr->pattern_regs)
575 ptr->pattern_regs = extract_mentioned_regs (dest);
576
577 /* Do not check for anticipatability if we either found one anticipatable
578 store already, or tested for one and found out that it was killed. */
579 check_anticipatable = 0;
580 if (!ptr->antic_stores)
581 check_anticipatable = 1;
582 else
583 {
584 tmp = XEXP (ptr->antic_stores, 0);
585 if (tmp != NULL_RTX
586 && BLOCK_FOR_INSN (tmp) != bb)
587 check_anticipatable = 1;
588 }
589 if (check_anticipatable)
590 {
591 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
592 tmp = NULL_RTX;
593 else
594 tmp = insn;
595 ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
596 }
597
598 /* It is not necessary to check whether store is available if we did
599 it successfully before; if we failed before, do not bother to check
600 until we reach the insn that caused us to fail. */
601 check_available = 0;
602 if (!ptr->avail_stores)
603 check_available = 1;
604 else
605 {
606 tmp = XEXP (ptr->avail_stores, 0);
607 if (BLOCK_FOR_INSN (tmp) != bb)
608 check_available = 1;
609 }
610 if (check_available)
611 {
612 /* Check that we have already reached the insn at that the check
613 failed last time. */
614 if (LAST_AVAIL_CHECK_FAILURE (ptr))
615 {
616 for (tmp = BB_END (bb);
617 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
618 tmp = PREV_INSN (tmp))
619 continue;
620 if (tmp == insn)
621 check_available = 0;
622 }
623 else
624 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
625 bb, regs_set_after,
626 &LAST_AVAIL_CHECK_FAILURE (ptr));
627 }
628 if (!check_available)
629 ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
630 }
631
632 /* Find available and anticipatable stores. */
633
634 static int
635 compute_store_table (void)
636 {
637 int ret;
638 basic_block bb;
639 #ifdef ENABLE_CHECKING
640 unsigned regno;
641 #endif
642 rtx insn, tmp;
643 df_ref *def_rec;
644 int *last_set_in, *already_set;
645 struct st_expr * ptr, **prev_next_ptr_ptr;
646 unsigned int max_gcse_regno = max_reg_num ();
647
648 store_motion_mems = NULL;
649 store_motion_mems_table = htab_create (13, pre_st_expr_hash,
650 pre_st_expr_eq, NULL);
651 last_set_in = XCNEWVEC (int, max_gcse_regno);
652 already_set = XNEWVEC (int, max_gcse_regno);
653
654 /* Find all the stores we care about. */
655 FOR_EACH_BB (bb)
656 {
657 /* First compute the registers set in this block. */
658 FOR_BB_INSNS (bb, insn)
659 {
660
661 if (! NONDEBUG_INSN_P (insn))
662 continue;
663
664 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
665 last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
666 }
667
668 /* Now find the stores. */
669 memset (already_set, 0, sizeof (int) * max_gcse_regno);
670 FOR_BB_INSNS (bb, insn)
671 {
672 if (! NONDEBUG_INSN_P (insn))
673 continue;
674
675 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
676 already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
677
678 /* Now that we've marked regs, look for stores. */
679 find_moveable_store (insn, already_set, last_set_in);
680
681 /* Unmark regs that are no longer set. */
682 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
683 if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn))
684 last_set_in[DF_REF_REGNO (*def_rec)] = 0;
685 }
686
687 #ifdef ENABLE_CHECKING
688 /* last_set_in should now be all-zero. */
689 for (regno = 0; regno < max_gcse_regno; regno++)
690 gcc_assert (!last_set_in[regno]);
691 #endif
692
693 /* Clear temporary marks. */
694 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
695 {
696 LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
697 if (ptr->antic_stores
698 && (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX)
699 ptr->antic_stores = XEXP (ptr->antic_stores, 1);
700 }
701 }
702
703 /* Remove the stores that are not available anywhere, as there will
704 be no opportunity to optimize them. */
705 for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
706 ptr != NULL;
707 ptr = *prev_next_ptr_ptr)
708 {
709 if (! ptr->avail_stores)
710 {
711 *prev_next_ptr_ptr = ptr->next;
712 htab_remove_elt_with_hash (store_motion_mems_table,
713 ptr, ptr->hash_index);
714 free_st_expr_entry (ptr);
715 }
716 else
717 prev_next_ptr_ptr = &ptr->next;
718 }
719
720 ret = enumerate_store_motion_mems ();
721
722 if (dump_file)
723 print_store_motion_mems (dump_file);
724
725 free (last_set_in);
726 free (already_set);
727 return ret;
728 }
729
730 /* In all code following after this, REACHING_REG has its original
731 meaning again. Avoid confusion, and undef the accessor macro for
732 the temporary marks usage in compute_store_table. */
733 #undef LAST_AVAIL_CHECK_FAILURE
734
735 /* Insert an instruction at the beginning of a basic block, and update
736 the BB_HEAD if needed. */
737
738 static void
739 insert_insn_start_basic_block (rtx insn, basic_block bb)
740 {
741 /* Insert at start of successor block. */
742 rtx prev = PREV_INSN (BB_HEAD (bb));
743 rtx before = BB_HEAD (bb);
744 while (before != 0)
745 {
746 if (! LABEL_P (before)
747 && !NOTE_INSN_BASIC_BLOCK_P (before))
748 break;
749 prev = before;
750 if (prev == BB_END (bb))
751 break;
752 before = NEXT_INSN (before);
753 }
754
755 insn = emit_insn_after_noloc (insn, prev, bb);
756
757 if (dump_file)
758 {
759 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
760 bb->index);
761 print_inline_rtx (dump_file, insn, 6);
762 fprintf (dump_file, "\n");
763 }
764 }
765
766 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
767 the memory reference, and E is the edge to insert it on. Returns nonzero
768 if an edge insertion was performed. */
769
770 static int
771 insert_store (struct st_expr * expr, edge e)
772 {
773 rtx reg, insn;
774 basic_block bb;
775 edge tmp;
776 edge_iterator ei;
777
778 /* We did all the deleted before this insert, so if we didn't delete a
779 store, then we haven't set the reaching reg yet either. */
780 if (expr->reaching_reg == NULL_RTX)
781 return 0;
782
783 if (e->flags & EDGE_FAKE)
784 return 0;
785
786 reg = expr->reaching_reg;
787 insn = gen_move_insn (copy_rtx (expr->pattern), reg);
788
789 /* If we are inserting this expression on ALL predecessor edges of a BB,
790 insert it at the start of the BB, and reset the insert bits on the other
791 edges so we don't try to insert it on the other edges. */
792 bb = e->dest;
793 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
794 if (!(tmp->flags & EDGE_FAKE))
795 {
796 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
797
798 gcc_assert (index != EDGE_INDEX_NO_EDGE);
799 if (! bitmap_bit_p (st_insert_map[index], expr->index))
800 break;
801 }
802
803 /* If tmp is NULL, we found an insertion on every edge, blank the
804 insertion vector for these edges, and insert at the start of the BB. */
805 if (!tmp && bb != EXIT_BLOCK_PTR)
806 {
807 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
808 {
809 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
810 bitmap_clear_bit (st_insert_map[index], expr->index);
811 }
812 insert_insn_start_basic_block (insn, bb);
813 return 0;
814 }
815
816 /* We can't put stores in the front of blocks pointed to by abnormal
817 edges since that may put a store where one didn't used to be. */
818 gcc_assert (!(e->flags & EDGE_ABNORMAL));
819
820 insert_insn_on_edge (insn, e);
821
822 if (dump_file)
823 {
824 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
825 e->src->index, e->dest->index);
826 print_inline_rtx (dump_file, insn, 6);
827 fprintf (dump_file, "\n");
828 }
829
830 return 1;
831 }
832
833 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
834 memory location in SMEXPR set in basic block BB.
835
836 This could be rather expensive. */
837
838 static void
839 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
840 {
841 edge_iterator *stack, ei;
842 int sp;
843 edge act;
844 sbitmap visited = sbitmap_alloc (last_basic_block);
845 rtx last, insn, note;
846 rtx mem = smexpr->pattern;
847
848 stack = XNEWVEC (edge_iterator, n_basic_blocks);
849 sp = 0;
850 ei = ei_start (bb->succs);
851
852 bitmap_clear (visited);
853
854 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
855 while (1)
856 {
857 if (!act)
858 {
859 if (!sp)
860 {
861 free (stack);
862 sbitmap_free (visited);
863 return;
864 }
865 act = ei_edge (stack[--sp]);
866 }
867 bb = act->dest;
868
869 if (bb == EXIT_BLOCK_PTR
870 || bitmap_bit_p (visited, bb->index))
871 {
872 if (!ei_end_p (ei))
873 ei_next (&ei);
874 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
875 continue;
876 }
877 bitmap_set_bit (visited, bb->index);
878
879 if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
880 {
881 for (last = smexpr->antic_stores;
882 BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
883 last = XEXP (last, 1))
884 continue;
885 last = XEXP (last, 0);
886 }
887 else
888 last = NEXT_INSN (BB_END (bb));
889
890 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
891 if (NONDEBUG_INSN_P (insn))
892 {
893 note = find_reg_equal_equiv_note (insn);
894 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
895 continue;
896
897 if (dump_file)
898 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
899 INSN_UID (insn));
900 remove_note (insn, note);
901 }
902
903 if (!ei_end_p (ei))
904 ei_next (&ei);
905 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
906
907 if (EDGE_COUNT (bb->succs) > 0)
908 {
909 if (act)
910 stack[sp++] = ei;
911 ei = ei_start (bb->succs);
912 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
913 }
914 }
915 }
916
917 /* This routine will replace a store with a SET to a specified register. */
918
919 static void
920 replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
921 {
922 rtx insn, mem, note, set, ptr;
923
924 mem = smexpr->pattern;
925 insn = gen_move_insn (reg, SET_SRC (single_set (del)));
926
927 for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
928 if (XEXP (ptr, 0) == del)
929 {
930 XEXP (ptr, 0) = insn;
931 break;
932 }
933
934 /* Move the notes from the deleted insn to its replacement. */
935 REG_NOTES (insn) = REG_NOTES (del);
936
937 /* Emit the insn AFTER all the notes are transferred.
938 This is cheaper since we avoid df rescanning for the note change. */
939 insn = emit_insn_after (insn, del);
940
941 if (dump_file)
942 {
943 fprintf (dump_file,
944 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
945 print_inline_rtx (dump_file, del, 6);
946 fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
947 print_inline_rtx (dump_file, insn, 6);
948 fprintf (dump_file, "\n");
949 }
950
951 delete_insn (del);
952
953 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
954 they are no longer accurate provided that they are reached by this
955 definition, so drop them. */
956 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
957 if (NONDEBUG_INSN_P (insn))
958 {
959 set = single_set (insn);
960 if (!set)
961 continue;
962 if (exp_equiv_p (SET_DEST (set), mem, 0, true))
963 return;
964 note = find_reg_equal_equiv_note (insn);
965 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
966 continue;
967
968 if (dump_file)
969 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
970 INSN_UID (insn));
971 remove_note (insn, note);
972 }
973 remove_reachable_equiv_notes (bb, smexpr);
974 }
975
976
977 /* Delete a store, but copy the value that would have been stored into
978 the reaching_reg for later storing. */
979
980 static void
981 delete_store (struct st_expr * expr, basic_block bb)
982 {
983 rtx reg, i, del;
984
985 if (expr->reaching_reg == NULL_RTX)
986 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
987
988 reg = expr->reaching_reg;
989
990 for (i = expr->avail_stores; i; i = XEXP (i, 1))
991 {
992 del = XEXP (i, 0);
993 if (BLOCK_FOR_INSN (del) == bb)
994 {
995 /* We know there is only one since we deleted redundant
996 ones during the available computation. */
997 replace_store_insn (reg, del, bb, expr);
998 break;
999 }
1000 }
1001 }
1002
1003 /* Fill in available, anticipatable, transparent and kill vectors in
1004 STORE_DATA, based on lists of available and anticipatable stores. */
1005 static void
1006 build_store_vectors (void)
1007 {
1008 basic_block bb;
1009 int *regs_set_in_block;
1010 rtx insn, st;
1011 struct st_expr * ptr;
1012 unsigned int max_gcse_regno = max_reg_num ();
1013
1014 /* Build the gen_vector. This is any store in the table which is not killed
1015 by aliasing later in its block. */
1016 st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1017 bitmap_vector_clear (st_avloc, last_basic_block);
1018
1019 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1020 bitmap_vector_clear (st_antloc, last_basic_block);
1021
1022 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1023 {
1024 for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
1025 {
1026 insn = XEXP (st, 0);
1027 bb = BLOCK_FOR_INSN (insn);
1028
1029 /* If we've already seen an available expression in this block,
1030 we can delete this one (It occurs earlier in the block). We'll
1031 copy the SRC expression to an unused register in case there
1032 are any side effects. */
1033 if (bitmap_bit_p (st_avloc[bb->index], ptr->index))
1034 {
1035 rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1036 if (dump_file)
1037 fprintf (dump_file, "Removing redundant store:\n");
1038 replace_store_insn (r, XEXP (st, 0), bb, ptr);
1039 continue;
1040 }
1041 bitmap_set_bit (st_avloc[bb->index], ptr->index);
1042 }
1043
1044 for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
1045 {
1046 insn = XEXP (st, 0);
1047 bb = BLOCK_FOR_INSN (insn);
1048 bitmap_set_bit (st_antloc[bb->index], ptr->index);
1049 }
1050 }
1051
1052 st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
1053 bitmap_vector_clear (st_kill, last_basic_block);
1054
1055 st_transp = sbitmap_vector_alloc (last_basic_block, num_stores);
1056 bitmap_vector_clear (st_transp, last_basic_block);
1057 regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1058
1059 FOR_EACH_BB (bb)
1060 {
1061 memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
1062
1063 FOR_BB_INSNS (bb, insn)
1064 if (NONDEBUG_INSN_P (insn))
1065 {
1066 df_ref *def_rec;
1067 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1068 {
1069 unsigned int ref_regno = DF_REF_REGNO (*def_rec);
1070 if (ref_regno < max_gcse_regno)
1071 regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
1072 }
1073 }
1074
1075 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1076 {
1077 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1078 bb, regs_set_in_block, NULL))
1079 {
1080 /* It should not be necessary to consider the expression
1081 killed if it is both anticipatable and available. */
1082 if (!bitmap_bit_p (st_antloc[bb->index], ptr->index)
1083 || !bitmap_bit_p (st_avloc[bb->index], ptr->index))
1084 bitmap_set_bit (st_kill[bb->index], ptr->index);
1085 }
1086 else
1087 bitmap_set_bit (st_transp[bb->index], ptr->index);
1088 }
1089 }
1090
1091 free (regs_set_in_block);
1092
1093 if (dump_file)
1094 {
1095 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
1096 dump_bitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
1097 dump_bitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
1098 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
1099 }
1100 }
1101
1102 /* Free memory used by store motion. */
1103
1104 static void
1105 free_store_memory (void)
1106 {
1107 free_store_motion_mems ();
1108
1109 if (st_avloc)
1110 sbitmap_vector_free (st_avloc);
1111 if (st_kill)
1112 sbitmap_vector_free (st_kill);
1113 if (st_transp)
1114 sbitmap_vector_free (st_transp);
1115 if (st_antloc)
1116 sbitmap_vector_free (st_antloc);
1117 if (st_insert_map)
1118 sbitmap_vector_free (st_insert_map);
1119 if (st_delete_map)
1120 sbitmap_vector_free (st_delete_map);
1121
1122 st_avloc = st_kill = st_transp = st_antloc = NULL;
1123 st_insert_map = st_delete_map = NULL;
1124 }
1125
1126 /* Perform store motion. Much like gcse, except we move expressions the
1127 other way by looking at the flowgraph in reverse.
1128 Return non-zero if transformations are performed by the pass. */
1129
1130 static int
1131 one_store_motion_pass (void)
1132 {
1133 basic_block bb;
1134 int x;
1135 struct st_expr * ptr;
1136 int did_edge_inserts = 0;
1137 int n_stores_deleted = 0;
1138 int n_stores_created = 0;
1139
1140 init_alias_analysis ();
1141
1142 /* Find all the available and anticipatable stores. */
1143 num_stores = compute_store_table ();
1144 if (num_stores == 0)
1145 {
1146 htab_delete (store_motion_mems_table);
1147 store_motion_mems_table = NULL;
1148 end_alias_analysis ();
1149 return 0;
1150 }
1151
1152 /* Now compute kill & transp vectors. */
1153 build_store_vectors ();
1154 add_noreturn_fake_exit_edges ();
1155 connect_infinite_loops_to_exit ();
1156
1157 edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1158 st_antloc, st_kill, &st_insert_map,
1159 &st_delete_map);
1160
1161 /* Now we want to insert the new stores which are going to be needed. */
1162 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1163 {
1164 /* If any of the edges we have above are abnormal, we can't move this
1165 store. */
1166 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1167 if (bitmap_bit_p (st_insert_map[x], ptr->index)
1168 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1169 break;
1170
1171 if (x >= 0)
1172 {
1173 if (dump_file != NULL)
1174 fprintf (dump_file,
1175 "Can't replace store %d: abnormal edge from %d to %d\n",
1176 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1177 INDEX_EDGE (edge_list, x)->dest->index);
1178 continue;
1179 }
1180
1181 /* Now we want to insert the new stores which are going to be needed. */
1182
1183 FOR_EACH_BB (bb)
1184 if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
1185 {
1186 delete_store (ptr, bb);
1187 n_stores_deleted++;
1188 }
1189
1190 for (x = 0; x < NUM_EDGES (edge_list); x++)
1191 if (bitmap_bit_p (st_insert_map[x], ptr->index))
1192 {
1193 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1194 n_stores_created++;
1195 }
1196 }
1197
1198 if (did_edge_inserts)
1199 commit_edge_insertions ();
1200
1201 free_store_memory ();
1202 free_edge_list (edge_list);
1203 remove_fake_exit_edges ();
1204 end_alias_analysis ();
1205
1206 if (dump_file)
1207 {
1208 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1209 current_function_name (), n_basic_blocks);
1210 fprintf (dump_file, "%d insns deleted, %d insns created\n",
1211 n_stores_deleted, n_stores_created);
1212 }
1213
1214 return (n_stores_deleted > 0 || n_stores_created > 0);
1215 }
1216
1217 \f
1218 static bool
1219 gate_rtl_store_motion (void)
1220 {
1221 return optimize > 0 && flag_gcse_sm
1222 && !cfun->calls_setjmp
1223 && optimize_function_for_speed_p (cfun)
1224 && dbg_cnt (store_motion);
1225 }
1226
1227 static unsigned int
1228 execute_rtl_store_motion (void)
1229 {
1230 delete_unreachable_blocks ();
1231 df_analyze ();
1232 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1233 return 0;
1234 }
1235
1236 struct rtl_opt_pass pass_rtl_store_motion =
1237 {
1238 {
1239 RTL_PASS,
1240 "store_motion", /* name */
1241 OPTGROUP_NONE, /* optinfo_flags */
1242 gate_rtl_store_motion, /* gate */
1243 execute_rtl_store_motion, /* execute */
1244 NULL, /* sub */
1245 NULL, /* next */
1246 0, /* static_pass_number */
1247 TV_LSM, /* tv_id */
1248 PROP_cfglayout, /* properties_required */
1249 0, /* properties_provided */
1250 0, /* properties_destroyed */
1251 0, /* todo_flags_start */
1252 TODO_df_finish | TODO_verify_rtl_sharing |
1253 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
1254 }
1255 };