1 /* GIMPLE store merging pass.
2 Copyright (C) 2016 Free Software Foundation, Inc.
3 Contributed by ARM Ltd.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
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/>. */
21 /* The purpose of this pass is to combine multiple memory stores of
22 constant values to consecutive memory locations into fewer wider stores.
23 For example, if we have a sequence peforming four byte stores to
24 consecutive memory locations:
29 we can transform this into a single 4-byte store if the target supports it:
30 [p] := imm1:imm2:imm3:imm4 //concatenated immediates according to endianness.
32 The algorithm is applied to each basic block in three phases:
34 1) Scan through the basic block recording constant assignments to
35 destinations that can be expressed as a store to memory of a certain size
36 at a certain bit offset. Record store chains to different bases in a
37 hash_map (m_stores) and make sure to terminate such chains when appropriate
38 (for example when when the stored values get used subsequently).
39 These stores can be a result of structure element initializers, array stores
40 etc. A store_immediate_info object is recorded for every such store.
41 Record as many such assignments to a single base as possible until a
42 statement that interferes with the store sequence is encountered.
44 2) Analyze the chain of stores recorded in phase 1) (i.e. the vector of
45 store_immediate_info objects) and coalesce contiguous stores into
46 merged_store_group objects.
48 For example, given the stores:
55 This phase would produce two merged_store_group objects, one recording the
56 two bytes stored in the memory region [p : p + 1] and another
57 recording the four bytes stored in the memory region [p + 3 : p + 6].
59 3) The merged_store_group objects produced in phase 2) are processed
60 to generate the sequence of wider stores that set the contiguous memory
61 regions to the sequence of bytes that correspond to it. This may emit
62 multiple stores per store group to handle contiguous stores that are not
63 of a size that is a power of 2. For example it can try to emit a 40-bit
64 store as a 32-bit store followed by an 8-bit store.
65 We try to emit as wide stores as we can while respecting STRICT_ALIGNMENT or
66 SLOW_UNALIGNED_ACCESS rules.
68 Note on endianness and example:
69 Consider 2 contiguous 16-bit stores followed by 2 contiguous 8-bit stores:
75 The memory layout for little-endian (LE) and big-endian (BE) must be:
85 To merge these into a single 48-bit merged value 'val' in phase 2)
86 on little-endian we insert stores to higher (consecutive) bitpositions
87 into the most significant bits of the merged value.
88 The final merged value would be: 0xcdab56781234
90 For big-endian we insert stores to higher bitpositions into the least
91 significant bits of the merged value.
92 The final merged value would be: 0x12345678abcd
94 Then, in phase 3), we want to emit this 48-bit value as a 32-bit store
95 followed by a 16-bit store. Again, we must consider endianness when
96 breaking down the 48-bit value 'val' computed above.
97 For little endian we emit:
98 [p] (32-bit) := 0x56781234; // val & 0x0000ffffffff;
99 [p + 4B] (16-bit) := 0xcdab; // (val & 0xffff00000000) >> 32;
101 Whereas for big-endian we emit:
102 [p] (32-bit) := 0x12345678; // (val & 0xffffffff0000) >> 16;
103 [p + 4B] (16-bit) := 0xabcd; // val & 0x00000000ffff; */
107 #include "coretypes.h"
111 #include "builtins.h"
112 #include "fold-const.h"
113 #include "tree-pass.h"
115 #include "gimple-pretty-print.h"
117 #include "fold-const.h"
119 #include "print-tree.h"
120 #include "tree-hash-traits.h"
121 #include "gimple-iterator.h"
122 #include "gimplify.h"
123 #include "stor-layout.h"
125 #include "tree-cfg.h"
129 /* The maximum size (in bits) of the stores this pass should generate. */
130 #define MAX_STORE_BITSIZE (BITS_PER_WORD)
131 #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
135 /* Struct recording the information about a single store of an immediate
136 to memory. These are created in the first phase and coalesced into
137 merged_store_group objects in the second phase. */
139 struct store_immediate_info
141 unsigned HOST_WIDE_INT bitsize
;
142 unsigned HOST_WIDE_INT bitpos
;
145 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
146 gimple
*, unsigned int);
149 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
150 unsigned HOST_WIDE_INT bp
,
153 : bitsize (bs
), bitpos (bp
), stmt (st
), order (ord
)
157 /* Struct representing a group of stores to contiguous memory locations.
158 These are produced by the second phase (coalescing) and consumed in the
159 third phase that outputs the widened stores. */
161 struct merged_store_group
163 unsigned HOST_WIDE_INT start
;
164 unsigned HOST_WIDE_INT width
;
165 /* The size of the allocated memory for val. */
166 unsigned HOST_WIDE_INT buf_size
;
169 unsigned int first_order
;
170 unsigned int last_order
;
172 auto_vec
<struct store_immediate_info
*> stores
;
173 /* We record the first and last original statements in the sequence because
174 we'll need their vuse/vdef and replacement position. It's easier to keep
175 track of them separately as 'stores' is reordered by apply_stores. */
180 merged_store_group (store_immediate_info
*);
181 ~merged_store_group ();
182 void merge_into (store_immediate_info
*);
183 void merge_overlapping (store_immediate_info
*);
184 bool apply_stores ();
187 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
190 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
195 for (unsigned int i
= 0; i
< len
; i
++)
196 fprintf (fd
, "%x ", ptr
[i
]);
200 /* Fill a byte array PTR of SZ elements with zeroes. This is to be used by
201 encode_tree_to_bitpos to zero-initialize most likely small arrays but
202 with a non-compile-time-constant size. */
205 zero_char_buf (unsigned char *ptr
, unsigned int sz
)
207 for (unsigned int i
= 0; i
< sz
; i
++)
211 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
212 bits between adjacent elements. AMNT should be within
215 00011111|11100000 << 2 = 01111111|10000000
216 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
219 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
224 unsigned char carry_over
= 0U;
225 unsigned char carry_mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- amnt
));
226 unsigned char clear_mask
= (~0U) << amnt
;
228 for (unsigned int i
= 0; i
< sz
; i
++)
230 unsigned prev_carry_over
= carry_over
;
232 = (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
237 ptr
[i
] &= clear_mask
;
238 ptr
[i
] |= prev_carry_over
;
243 /* Like shift_bytes_in_array but for big-endian.
244 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
245 bits between adjacent elements. AMNT should be within
248 00011111|11100000 >> 2 = 00000111|11111000
249 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
252 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
258 unsigned char carry_over
= 0U;
259 unsigned char carry_mask
= ~(~0U << amnt
);
261 for (unsigned int i
= 0; i
< sz
; i
++)
263 unsigned prev_carry_over
= carry_over
;
265 = (ptr
[i
] & carry_mask
);
267 carry_over
<<= ((unsigned char)BITS_PER_UNIT
- amnt
);
269 ptr
[i
] |= prev_carry_over
;
273 /* Clear out LEN bits starting from bit START in the byte array
274 PTR. This clears the bits to the *right* from START.
275 START must be within [0, BITS_PER_UNIT) and counts starting from
276 the least significant bit. */
279 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
284 /* Clear len bits to the right of start. */
285 else if (len
<= start
+ 1)
287 unsigned char mask
= (~(~0U << len
));
288 mask
= mask
<< (start
+ 1U - len
);
291 else if (start
!= BITS_PER_UNIT
- 1)
293 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
294 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
295 len
- (start
% BITS_PER_UNIT
) - 1);
297 else if (start
== BITS_PER_UNIT
- 1
298 && len
> BITS_PER_UNIT
)
300 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
301 for (unsigned int i
= 0; i
< nbytes
; i
++)
303 if (len
% BITS_PER_UNIT
!= 0)
304 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
305 len
% BITS_PER_UNIT
);
311 /* In the byte array PTR clear the bit region starting at bit
312 START and is LEN bits wide.
313 For regions spanning multiple bytes do this recursively until we reach
314 zero LEN or a region contained within a single byte. */
317 clear_bit_region (unsigned char *ptr
, unsigned int start
,
320 /* Degenerate base case. */
323 else if (start
>= BITS_PER_UNIT
)
324 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
325 /* Second base case. */
326 else if ((start
+ len
) <= BITS_PER_UNIT
)
328 unsigned char mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- len
));
329 mask
>>= BITS_PER_UNIT
- (start
+ len
);
335 /* Clear most significant bits in a byte and proceed with the next byte. */
338 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
339 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
) + 1);
341 /* Whole bytes need to be cleared. */
342 else if (start
== 0 && len
> BITS_PER_UNIT
)
344 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
345 /* We could recurse on each byte but do the loop here to avoid
346 recursing too deep. */
347 for (unsigned int i
= 0; i
< nbytes
; i
++)
349 /* Clear the remaining sub-byte region if there is one. */
350 if (len
% BITS_PER_UNIT
!= 0)
351 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
357 /* Write BITLEN bits of EXPR to the byte array PTR at
358 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
359 Return true if the operation succeeded. */
362 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
363 unsigned int total_bytes
)
365 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
367 bool sub_byte_op_p
= (bitlen
% BITS_PER_UNIT
) || (bitpos
% BITS_PER_UNIT
)
368 || mode_for_size (bitlen
, MODE_INT
, 0) == BLKmode
;
371 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
, 0)
375 We are writing a non byte-sized quantity or at a position that is not
377 |--------|--------|--------| ptr + first_byte
379 xxx xxxxxxxx xxx< bp>
382 First native_encode_expr EPXR into a temporary buffer and shift each
383 byte in the buffer by 'bp' (carrying the bits over as necessary).
384 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
385 <------bitlen---->< bp>
386 Then we clear the destination bits:
387 |---00000|00000000|000-----| ptr + first_byte
388 <-------bitlen--->< bp>
390 Finally we ORR the bytes of the shifted EXPR into the cleared region:
391 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
394 We are writing a non byte-sized quantity or at a position that is not
396 ptr + first_byte |--------|--------|--------|
398 <bp >xxx xxxxxxxx xxx
401 First native_encode_expr EPXR into a temporary buffer and shift each
402 byte in the buffer to the right by (carrying the bits over as necessary).
403 We shift by as much as needed to align the most significant bit of EXPR
405 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
406 <---bitlen----> <bp ><-----bitlen----->
407 Then we clear the destination bits:
408 ptr + first_byte |-----000||00000000||00000---|
409 <bp ><-------bitlen----->
411 Finally we ORR the bytes of the shifted EXPR into the cleared region:
412 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
413 The awkwardness comes from the fact that bitpos is counted from the
414 most significant bit of a byte. */
416 /* Allocate an extra byte so that we have space to shift into. */
417 unsigned int byte_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (expr
))) + 1;
418 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
419 zero_char_buf (tmpbuf
, byte_size
);
420 /* The store detection code should only have allowed constants that are
421 accepted by native_encode_expr. */
422 if (native_encode_expr (expr
, tmpbuf
, byte_size
, 0) == 0)
425 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
426 bytes to write. This means it can write more than
427 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
428 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
429 bitlen and zero out the bits that are not relevant as well (that may
430 contain a sign bit due to sign-extension). */
432 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
435 /* On big-endian the padding is at the 'front' so just skip the initial
437 if (BYTES_BIG_ENDIAN
)
440 byte_size
-= padding
;
441 if (bitlen
% BITS_PER_UNIT
!= 0)
443 if (BYTES_BIG_ENDIAN
)
444 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
445 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
447 clear_bit_region (tmpbuf
, bitlen
,
448 byte_size
* BITS_PER_UNIT
- bitlen
);
452 /* Clear the bit region in PTR where the bits from TMPBUF will be
454 if (BYTES_BIG_ENDIAN
)
455 clear_bit_region_be (ptr
+ first_byte
,
456 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
458 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
461 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
462 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
464 bool skip_byte
= false;
465 if (BYTES_BIG_ENDIAN
)
467 /* BITPOS and BITLEN are exactly aligned and no shifting
469 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
470 || (bitpos_mod
== 0 && bitlen_mod
== 0))
474 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
475 of the value until it aligns with 'bp' in the next byte over. */
476 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
478 shift_amnt
= bitlen_mod
+ bitpos_mod
;
479 skip_byte
= bitlen_mod
!= 0;
484 Shift the value right within the same byte so it aligns with 'bp'. */
486 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
489 shift_amnt
= bitpos
% BITS_PER_UNIT
;
491 /* Create the shifted version of EXPR. */
492 if (!BYTES_BIG_ENDIAN
)
493 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
496 gcc_assert (BYTES_BIG_ENDIAN
);
497 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
498 /* If shifting right forced us to move into the next byte skip the now
507 /* Insert the bits from TMPBUF. */
508 for (unsigned int i
= 0; i
< byte_size
; i
++)
509 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
514 /* Sorting function for store_immediate_info objects.
515 Sorts them by bitposition. */
518 sort_by_bitpos (const void *x
, const void *y
)
520 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
521 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
523 if ((*tmp
)->bitpos
<= (*tmp2
)->bitpos
)
525 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
531 /* Sorting function for store_immediate_info objects.
532 Sorts them by the order field. */
535 sort_by_order (const void *x
, const void *y
)
537 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
538 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
540 if ((*tmp
)->order
< (*tmp2
)->order
)
542 else if ((*tmp
)->order
> (*tmp2
)->order
)
548 /* Initialize a merged_store_group object from a store_immediate_info
551 merged_store_group::merged_store_group (store_immediate_info
*info
)
553 start
= info
->bitpos
;
554 width
= info
->bitsize
;
555 /* VAL has memory allocated for it in apply_stores once the group
556 width has been finalized. */
558 align
= get_object_alignment (gimple_assign_lhs (info
->stmt
));
560 stores
.safe_push (info
);
561 last_stmt
= info
->stmt
;
562 last_order
= info
->order
;
563 first_stmt
= last_stmt
;
564 first_order
= last_order
;
568 merged_store_group::~merged_store_group ()
574 /* Merge a store recorded by INFO into this merged store.
575 The store is not overlapping with the existing recorded
579 merged_store_group::merge_into (store_immediate_info
*info
)
581 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
582 /* Make sure we're inserting in the position we think we're inserting. */
583 gcc_assert (info
->bitpos
== start
+ width
);
586 gimple
*stmt
= info
->stmt
;
587 stores
.safe_push (info
);
588 if (info
->order
> last_order
)
590 last_order
= info
->order
;
593 else if (info
->order
< first_order
)
595 first_order
= info
->order
;
600 /* Merge a store described by INFO into this merged store.
601 INFO overlaps in some way with the current store (i.e. it's not contiguous
602 which is handled by merged_store_group::merge_into). */
605 merged_store_group::merge_overlapping (store_immediate_info
*info
)
607 gimple
*stmt
= info
->stmt
;
608 stores
.safe_push (info
);
610 /* If the store extends the size of the group, extend the width. */
611 if ((info
->bitpos
+ info
->bitsize
) > (start
+ width
))
612 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
614 if (info
->order
> last_order
)
616 last_order
= info
->order
;
619 else if (info
->order
< first_order
)
621 first_order
= info
->order
;
626 /* Go through all the recorded stores in this group in program order and
627 apply their values to the VAL byte array to create the final merged
628 value. Return true if the operation succeeded. */
631 merged_store_group::apply_stores ()
633 /* The total width of the stores must add up to a whole number of bytes
634 and start at a byte boundary. We don't support emitting bitfield
635 references for now. Also, make sure we have more than one store
636 in the group, otherwise we cannot merge anything. */
637 if (width
% BITS_PER_UNIT
!= 0
638 || start
% BITS_PER_UNIT
!= 0
639 || stores
.length () == 1)
642 stores
.qsort (sort_by_order
);
643 struct store_immediate_info
*info
;
645 /* Create a buffer of a size that is 2 times the number of bytes we're
646 storing. That way native_encode_expr can write power-of-2-sized
647 chunks without overrunning. */
649 = 2 * (ROUND_UP (width
, BITS_PER_UNIT
) / BITS_PER_UNIT
);
650 val
= XCNEWVEC (unsigned char, buf_size
);
652 FOR_EACH_VEC_ELT (stores
, i
, info
)
654 unsigned int pos_in_buffer
= info
->bitpos
- start
;
655 bool ret
= encode_tree_to_bitpos (gimple_assign_rhs1 (info
->stmt
),
657 pos_in_buffer
, buf_size
);
658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
662 fprintf (dump_file
, "After writing ");
663 print_generic_expr (dump_file
,
664 gimple_assign_rhs1 (info
->stmt
), 0);
665 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
666 " at position %d the merged region contains:\n",
667 info
->bitsize
, pos_in_buffer
);
668 dump_char_array (dump_file
, val
, buf_size
);
671 fprintf (dump_file
, "Failed to merge stores\n");
679 /* Structure describing the store chain. */
681 struct imm_store_chain_info
684 auto_vec
<struct store_immediate_info
*> m_store_info
;
685 auto_vec
<merged_store_group
*> m_merged_store_groups
;
687 imm_store_chain_info (tree b_a
) : base_addr (b_a
) {}
688 bool terminate_and_process_chain ();
689 bool coalesce_immediate_stores ();
690 bool output_merged_store (merged_store_group
*);
691 bool output_merged_stores ();
694 const pass_data pass_data_tree_store_merging
= {
695 GIMPLE_PASS
, /* type */
696 "store-merging", /* name */
697 OPTGROUP_NONE
, /* optinfo_flags */
698 TV_GIMPLE_STORE_MERGING
, /* tv_id */
699 PROP_ssa
, /* properties_required */
700 0, /* properties_provided */
701 0, /* properties_destroyed */
702 0, /* todo_flags_start */
703 TODO_update_ssa
, /* todo_flags_finish */
706 class pass_store_merging
: public gimple_opt_pass
709 pass_store_merging (gcc::context
*ctxt
)
710 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
)
714 /* Pass not supported for PDP-endianness. */
718 return flag_store_merging
&& (WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
);
721 virtual unsigned int execute (function
*);
724 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
726 bool terminate_and_process_all_chains ();
727 bool terminate_all_aliasing_chains (tree
, imm_store_chain_info
**,
729 bool terminate_and_release_chain (imm_store_chain_info
*);
730 }; // class pass_store_merging
732 /* Terminate and process all recorded chains. Return true if any changes
736 pass_store_merging::terminate_and_process_all_chains ()
738 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
741 for (; iter
!= m_stores
.end (); ++iter
)
742 ret
|= terminate_and_release_chain ((*iter
).second
);
747 /* Terminate all chains that are affected by the assignment to DEST, appearing
748 in statement STMT and ultimately points to the object BASE. Return true if
749 at least one aliasing chain was terminated. BASE and DEST are allowed to
750 be NULL_TREE. In that case the aliasing checks are performed on the whole
751 statement rather than a particular operand in it. VAR_OFFSET_P signifies
752 whether STMT represents a store to BASE offset by a variable amount.
753 If that is the case we have to terminate any chain anchored at BASE. */
756 pass_store_merging::terminate_all_aliasing_chains (tree dest
,
764 /* If the statement doesn't touch memory it can't alias. */
765 if (!gimple_vuse (stmt
))
768 /* Check if the assignment destination (BASE) is part of a store chain.
769 This is to catch non-constant stores to destinations that may be part
773 /* We have a chain at BASE and we're writing to [BASE + <variable>].
774 This can interfere with any of the stores so terminate
778 terminate_and_release_chain (*chain_info
);
781 /* Otherwise go through every store in the chain to see if it
782 aliases with any of them. */
785 struct store_immediate_info
*info
;
787 FOR_EACH_VEC_ELT ((*chain_info
)->m_store_info
, i
, info
)
789 if (stmt_may_clobber_ref_p (info
->stmt
, dest
))
791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
794 "stmt causes chain termination:\n");
795 print_gimple_stmt (dump_file
, stmt
, 0, 0);
797 terminate_and_release_chain (*chain_info
);
805 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
808 /* Check for aliasing with all other store chains. */
809 for (; iter
!= m_stores
.end (); ++iter
)
811 /* We already checked all the stores in chain_info and terminated the
812 chain if necessary. Skip it here. */
813 if (chain_info
&& (*chain_info
) == (*iter
).second
)
816 /* We can't use the base object here as that does not reliably exist.
817 Build a ao_ref from the base object address (if we know the
818 minimum and maximum offset and the maximum size we could improve
821 ao_ref_init_from_ptr_and_size (&chain_ref
, (*iter
).first
, NULL_TREE
);
822 if (ref_maybe_used_by_stmt_p (stmt
, &chain_ref
)
823 || stmt_may_clobber_ref_p_1 (stmt
, &chain_ref
))
825 terminate_and_release_chain ((*iter
).second
);
833 /* Helper function. Terminate the recorded chain storing to base object
834 BASE. Return true if the merging and output was successful. The m_stores
835 entry is removed after the processing in any case. */
838 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
840 bool ret
= chain_info
->terminate_and_process_chain ();
841 m_stores
.remove (chain_info
->base_addr
);
846 /* Go through the candidate stores recorded in m_store_info and merge them
847 into merged_store_group objects recorded into m_merged_store_groups
848 representing the widened stores. Return true if coalescing was successful
849 and the number of widened stores is fewer than the original number
853 imm_store_chain_info::coalesce_immediate_stores ()
855 /* Anything less can't be processed. */
856 if (m_store_info
.length () < 2)
859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
860 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
861 m_store_info
.length ());
863 store_immediate_info
*info
;
866 /* Order the stores by the bitposition they write to. */
867 m_store_info
.qsort (sort_by_bitpos
);
869 info
= m_store_info
[0];
870 merged_store_group
*merged_store
= new merged_store_group (info
);
872 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
874 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
877 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
878 i
, info
->bitsize
, info
->bitpos
);
879 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
), 0);
880 fprintf (dump_file
, "\n------------\n");
888 Overlapping stores. */
889 unsigned HOST_WIDE_INT start
= info
->bitpos
;
890 if (IN_RANGE (start
, merged_store
->start
,
891 merged_store
->start
+ merged_store
->width
- 1))
893 merged_store
->merge_overlapping (info
);
897 /* |---store 1---| <gap> |---store 2---|.
898 Gap between stores. Start a new group. */
899 if (start
!= merged_store
->start
+ merged_store
->width
)
901 /* Try to apply all the stores recorded for the group to determine
902 the bitpattern they write and discard it if that fails.
903 This will also reject single-store groups. */
904 if (!merged_store
->apply_stores ())
907 m_merged_store_groups
.safe_push (merged_store
);
909 merged_store
= new merged_store_group (info
);
914 /* |---store 1---||---store 2---|
915 This store is consecutive to the previous one.
916 Merge it into the current store group. */
917 merged_store
->merge_into (info
);
920 /* Record or discard the last store group. */
921 if (!merged_store
->apply_stores ())
924 m_merged_store_groups
.safe_push (merged_store
);
926 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
928 = !m_merged_store_groups
.is_empty ()
929 && m_merged_store_groups
.length () < m_store_info
.length ();
931 if (success
&& dump_file
)
932 fprintf (dump_file
, "Coalescing successful!\n"
933 "Merged into %u stores\n",
934 m_merged_store_groups
.length ());
939 /* Return the type to use for the merged stores described by STMTS.
940 This is needed to get the alias sets right. */
943 get_alias_type_for_stmts (auto_vec
<gimple
*> &stmts
)
947 tree lhs
= gimple_assign_lhs (stmts
[0]);
948 tree type
= reference_alias_ptr_type (lhs
);
950 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
955 lhs
= gimple_assign_lhs (stmt
);
956 tree type1
= reference_alias_ptr_type (lhs
);
957 if (!alias_ptr_types_compatible_p (type
, type1
))
958 return ptr_type_node
;
963 /* Return the location_t information we can find among the statements
967 get_location_for_stmts (auto_vec
<gimple
*> &stmts
)
972 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
973 if (gimple_has_location (stmt
))
974 return gimple_location (stmt
);
976 return UNKNOWN_LOCATION
;
979 /* Used to decribe a store resulting from splitting a wide store in smaller
980 regularly-sized stores in split_group. */
984 unsigned HOST_WIDE_INT bytepos
;
985 unsigned HOST_WIDE_INT size
;
986 unsigned HOST_WIDE_INT align
;
987 auto_vec
<gimple
*> orig_stmts
;
988 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
989 unsigned HOST_WIDE_INT
);
992 /* Simple constructor. */
994 split_store::split_store (unsigned HOST_WIDE_INT bp
,
995 unsigned HOST_WIDE_INT sz
,
996 unsigned HOST_WIDE_INT al
)
997 : bytepos (bp
), size (sz
), align (al
)
999 orig_stmts
.create (0);
1002 /* Record all statements corresponding to stores in GROUP that write to
1003 the region starting at BITPOS and is of size BITSIZE. Record such
1004 statements in STMTS. The stores in GROUP must be sorted by
1008 find_constituent_stmts (struct merged_store_group
*group
,
1009 auto_vec
<gimple
*> &stmts
,
1010 unsigned HOST_WIDE_INT bitpos
,
1011 unsigned HOST_WIDE_INT bitsize
)
1013 struct store_immediate_info
*info
;
1015 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1016 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
1018 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1019 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1020 if (stmt_end
< bitpos
)
1022 /* The stores in GROUP are ordered by bitposition so if we're past
1023 the region for this group return early. */
1024 if (stmt_start
> end
)
1027 if (IN_RANGE (stmt_start
, bitpos
, bitpos
+ bitsize
)
1028 || IN_RANGE (stmt_end
, bitpos
, end
)
1029 /* The statement writes a region that completely encloses the region
1030 that this group writes. Unlikely to occur but let's
1032 || IN_RANGE (bitpos
, stmt_start
, stmt_end
))
1033 stmts
.safe_push (info
->stmt
);
1037 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1038 vector with split_store structs describing the byte offset (from the base),
1039 the bit size and alignment of each store as well as the original statements
1040 involved in each such split group.
1041 This is to separate the splitting strategy from the statement
1042 building/emission/linking done in output_merged_store.
1043 At the moment just start with the widest possible size and keep emitting
1044 the widest we can until we have emitted all the bytes, halving the size
1045 when appropriate. */
1048 split_group (merged_store_group
*group
,
1049 auto_vec
<struct split_store
*> &split_stores
)
1051 unsigned HOST_WIDE_INT pos
= group
->start
;
1052 unsigned HOST_WIDE_INT size
= group
->width
;
1053 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1054 unsigned HOST_WIDE_INT align
= group
->align
;
1056 /* We don't handle partial bitfields for now. We shouldn't have
1057 reached this far. */
1058 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1060 bool allow_unaligned
1061 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1063 unsigned int try_size
= MAX_STORE_BITSIZE
;
1064 while (try_size
> size
1065 || (!allow_unaligned
1066 && try_size
> align
))
1069 if (try_size
< BITS_PER_UNIT
)
1073 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1074 group
->stores
.qsort (sort_by_bitpos
);
1078 struct split_store
*store
= new split_store (try_pos
, try_size
, align
);
1079 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1080 find_constituent_stmts (group
, store
->orig_stmts
, try_bitpos
, try_size
);
1081 split_stores
.safe_push (store
);
1083 try_pos
+= try_size
/ BITS_PER_UNIT
;
1087 while (size
< try_size
)
1093 /* Given a merged store group GROUP output the widened version of it.
1094 The store chain is against the base object BASE.
1095 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1096 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1097 Make sure that the number of statements output is less than the number of
1098 original statements. If a better sequence is possible emit it and
1102 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1104 unsigned HOST_WIDE_INT start_byte_pos
= group
->start
/ BITS_PER_UNIT
;
1106 unsigned int orig_num_stmts
= group
->stores
.length ();
1107 if (orig_num_stmts
< 2)
1110 auto_vec
<struct split_store
*> split_stores
;
1111 split_stores
.create (0);
1112 if (!split_group (group
, split_stores
))
1115 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1116 gimple_seq seq
= NULL
;
1117 unsigned int num_stmts
= 0;
1118 tree last_vdef
, new_vuse
;
1119 last_vdef
= gimple_vdef (group
->last_stmt
);
1120 new_vuse
= gimple_vuse (group
->last_stmt
);
1122 gimple
*stmt
= NULL
;
1123 /* The new SSA names created. Keep track of them so that we can free them
1124 if we decide to not use the new sequence. */
1125 auto_vec
<tree
> new_ssa_names
;
1126 split_store
*split_store
;
1130 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1132 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1133 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1134 unsigned HOST_WIDE_INT align
= split_store
->align
;
1135 tree offset_type
= get_alias_type_for_stmts (split_store
->orig_stmts
);
1136 location_t loc
= get_location_for_stmts (split_store
->orig_stmts
);
1138 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1139 int_type
= build_aligned_type (int_type
, align
);
1140 tree dest
= fold_build2 (MEM_REF
, int_type
, base_addr
,
1141 build_int_cst (offset_type
, try_pos
));
1143 tree src
= native_interpret_expr (int_type
,
1144 group
->val
+ try_pos
- start_byte_pos
,
1147 stmt
= gimple_build_assign (dest
, src
);
1148 gimple_set_location (stmt
, loc
);
1149 gimple_set_vuse (stmt
, new_vuse
);
1150 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1152 /* We didn't manage to reduce the number of statements. Bail out. */
1153 if (++num_stmts
== orig_num_stmts
)
1155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1157 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1158 " Not profitable to emit new sequence.\n",
1161 unsigned int ssa_count
;
1163 /* Don't forget to cleanup the temporary SSA names. */
1164 FOR_EACH_VEC_ELT (new_ssa_names
, ssa_count
, ssa_name
)
1165 release_ssa_name (ssa_name
);
1172 if (i
< split_stores
.length () - 1)
1174 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
1175 new_ssa_names
.safe_push (new_vdef
);
1178 new_vdef
= last_vdef
;
1180 gimple_set_vdef (stmt
, new_vdef
);
1181 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
1182 new_vuse
= new_vdef
;
1185 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1195 "New sequence of %u stmts to replace old one of %u stmts\n",
1196 num_stmts
, orig_num_stmts
);
1197 if (dump_flags
& TDF_DETAILS
)
1198 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1200 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
1205 /* Process the merged_store_group objects created in the coalescing phase.
1206 The stores are all against the base object BASE.
1207 Try to output the widened stores and delete the original statements if
1208 successful. Return true iff any changes were made. */
1211 imm_store_chain_info::output_merged_stores ()
1214 merged_store_group
*merged_store
;
1216 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
1218 if (output_merged_store (merged_store
))
1221 store_immediate_info
*store
;
1222 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
1224 gimple
*stmt
= store
->stmt
;
1225 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1226 gsi_remove (&gsi
, true);
1227 if (stmt
!= merged_store
->last_stmt
)
1229 unlink_stmt_vdef (stmt
);
1230 release_defs (stmt
);
1236 if (ret
&& dump_file
)
1237 fprintf (dump_file
, "Merging successful!\n");
1242 /* Coalesce the store_immediate_info objects recorded against the base object
1243 BASE in the first phase and output them.
1244 Delete the allocated structures.
1245 Return true if any changes were made. */
1248 imm_store_chain_info::terminate_and_process_chain ()
1250 /* Process store chain. */
1252 if (m_store_info
.length () > 1)
1254 ret
= coalesce_immediate_stores ();
1256 ret
= output_merged_stores ();
1259 /* Delete all the entries we allocated ourselves. */
1260 store_immediate_info
*info
;
1262 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1265 merged_store_group
*merged_info
;
1266 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
1272 /* Return true iff LHS is a destination potentially interesting for
1273 store merging. In practice these are the codes that get_inner_reference
1277 lhs_valid_for_store_merging_p (tree lhs
)
1279 tree_code code
= TREE_CODE (lhs
);
1281 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
1282 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
1288 /* Return true if the tree RHS is a constant we want to consider
1289 during store merging. In practice accept all codes that
1290 native_encode_expr accepts. */
1293 rhs_valid_for_store_merging_p (tree rhs
)
1295 tree type
= TREE_TYPE (rhs
);
1296 if (TREE_CODE_CLASS (TREE_CODE (rhs
)) != tcc_constant
1297 || !can_native_encode_type_p (type
))
1303 /* Entry point for the pass. Go over each basic block recording chains of
1304 immediate stores. Upon encountering a terminating statement (as defined
1305 by stmt_terminates_chain_p) process the recorded stores and emit the widened
1309 pass_store_merging::execute (function
*fun
)
1312 hash_set
<gimple
*> orig_stmts
;
1314 FOR_EACH_BB_FN (bb
, fun
)
1316 gimple_stmt_iterator gsi
;
1317 unsigned HOST_WIDE_INT num_statements
= 0;
1318 /* Record the original statements so that we can keep track of
1319 statements emitted in this pass and not re-process new
1321 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1323 if (is_gimple_debug (gsi_stmt (gsi
)))
1326 if (++num_statements
> 2)
1330 if (num_statements
< 2)
1333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1334 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
1336 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1338 gimple
*stmt
= gsi_stmt (gsi
);
1340 if (gimple_has_volatile_ops (stmt
))
1342 /* Terminate all chains. */
1343 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1344 fprintf (dump_file
, "Volatile access terminates "
1346 terminate_and_process_all_chains ();
1350 if (is_gimple_debug (stmt
))
1353 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
1354 && !stmt_can_throw_internal (stmt
)
1355 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
1357 tree lhs
= gimple_assign_lhs (stmt
);
1358 tree rhs
= gimple_assign_rhs1 (stmt
);
1360 HOST_WIDE_INT bitsize
, bitpos
;
1362 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
1363 tree offset
, base_addr
;
1365 = get_inner_reference (lhs
, &bitsize
, &bitpos
, &offset
, &mode
,
1366 &unsignedp
, &reversep
, &volatilep
);
1367 /* As a future enhancement we could handle stores with the same
1369 bool invalid
= offset
|| reversep
|| bitpos
< 0
1370 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
1371 && (TREE_CODE (rhs
) != INTEGER_CST
))
1372 || !rhs_valid_for_store_merging_p (rhs
)
1373 /* An access may not be volatile itself but base_addr may be
1374 a volatile decl i.e. MEM[&volatile-decl]. The hashing for
1375 tree_operand_hash won't consider such stores equal to each
1376 other so we can't track chains on them. */
1377 || TREE_THIS_VOLATILE (base_addr
);
1379 /* We do not want to rewrite TARGET_MEM_REFs. */
1380 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
1382 /* In some cases get_inner_reference may return a
1383 MEM_REF [ptr + byteoffset]. For the purposes of this pass
1384 canonicalize the base_addr to MEM_REF [ptr] and take
1385 byteoffset into account in the bitpos. This occurs in
1386 PR 23684 and this way we can catch more chains. */
1387 else if (TREE_CODE (base_addr
) == MEM_REF
)
1389 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
1390 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
1392 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
1393 bitpos
= bit_off
.to_shwi ();
1396 base_addr
= TREE_OPERAND (base_addr
, 0);
1398 /* get_inner_reference returns the base object, get at its
1401 base_addr
= build_fold_addr_expr (base_addr
);
1403 struct imm_store_chain_info
**chain_info
1404 = m_stores
.get (base_addr
);
1408 store_immediate_info
*info
;
1411 info
= new store_immediate_info (
1412 bitsize
, bitpos
, stmt
,
1413 (*chain_info
)->m_store_info
.length ());
1414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1417 "Recording immediate store from stmt:\n");
1418 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1420 (*chain_info
)->m_store_info
.safe_push (info
);
1421 /* If we reach the limit of stores to merge in a chain
1422 terminate and process the chain now. */
1423 if ((*chain_info
)->m_store_info
.length ()
1425 PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
1427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1429 "Reached maximum number of statements"
1431 terminate_and_release_chain (*chain_info
);
1436 /* Store aliases any existing chain? */
1437 terminate_all_aliasing_chains (lhs
, chain_info
, false, stmt
);
1438 /* Start a new chain. */
1439 struct imm_store_chain_info
*new_chain
1440 = new imm_store_chain_info (base_addr
);
1441 info
= new store_immediate_info (bitsize
, bitpos
,
1443 new_chain
->m_store_info
.safe_push (info
);
1444 m_stores
.put (base_addr
, new_chain
);
1445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1448 "Starting new chain with statement:\n");
1449 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1450 fprintf (dump_file
, "The base object is:\n");
1451 print_generic_expr (dump_file
, base_addr
, 0);
1452 fprintf (dump_file
, "\n");
1456 terminate_all_aliasing_chains (lhs
, chain_info
,
1457 offset
!= NULL_TREE
, stmt
);
1462 terminate_all_aliasing_chains (NULL_TREE
, NULL
, false, stmt
);
1464 terminate_and_process_all_chains ();
1471 /* Construct and return a store merging pass object. */
1474 make_pass_store_merging (gcc::context
*ctxt
)
1476 return new pass_store_merging (ctxt
);