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