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"
128 #include "gimplify-me.h"
130 /* The maximum size (in bits) of the stores this pass should generate. */
131 #define MAX_STORE_BITSIZE (BITS_PER_WORD)
132 #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
136 /* Struct recording the information about a single store of an immediate
137 to memory. These are created in the first phase and coalesced into
138 merged_store_group objects in the second phase. */
140 struct store_immediate_info
142 unsigned HOST_WIDE_INT bitsize
;
143 unsigned HOST_WIDE_INT bitpos
;
146 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
147 gimple
*, unsigned int);
150 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
151 unsigned HOST_WIDE_INT bp
,
154 : bitsize (bs
), bitpos (bp
), stmt (st
), order (ord
)
158 /* Struct representing a group of stores to contiguous memory locations.
159 These are produced by the second phase (coalescing) and consumed in the
160 third phase that outputs the widened stores. */
162 struct merged_store_group
164 unsigned HOST_WIDE_INT start
;
165 unsigned HOST_WIDE_INT width
;
166 /* The size of the allocated memory for val. */
167 unsigned HOST_WIDE_INT buf_size
;
170 unsigned int first_order
;
171 unsigned int last_order
;
173 auto_vec
<struct store_immediate_info
*> stores
;
174 /* We record the first and last original statements in the sequence because
175 we'll need their vuse/vdef and replacement position. It's easier to keep
176 track of them separately as 'stores' is reordered by apply_stores. */
181 merged_store_group (store_immediate_info
*);
182 ~merged_store_group ();
183 void merge_into (store_immediate_info
*);
184 void merge_overlapping (store_immediate_info
*);
185 bool apply_stores ();
188 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
191 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
196 for (unsigned int i
= 0; i
< len
; i
++)
197 fprintf (fd
, "%x ", ptr
[i
]);
201 /* Fill a byte array PTR of SZ elements with zeroes. This is to be used by
202 encode_tree_to_bitpos to zero-initialize most likely small arrays but
203 with a non-compile-time-constant size. */
206 zero_char_buf (unsigned char *ptr
, unsigned int sz
)
208 for (unsigned int i
= 0; i
< sz
; i
++)
212 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
213 bits between adjacent elements. AMNT should be within
216 00011111|11100000 << 2 = 01111111|10000000
217 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
220 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
225 unsigned char carry_over
= 0U;
226 unsigned char carry_mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- amnt
));
227 unsigned char clear_mask
= (~0U) << amnt
;
229 for (unsigned int i
= 0; i
< sz
; i
++)
231 unsigned prev_carry_over
= carry_over
;
233 = (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
238 ptr
[i
] &= clear_mask
;
239 ptr
[i
] |= prev_carry_over
;
244 /* Like shift_bytes_in_array but for big-endian.
245 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
246 bits between adjacent elements. AMNT should be within
249 00011111|11100000 >> 2 = 00000111|11111000
250 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
253 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
259 unsigned char carry_over
= 0U;
260 unsigned char carry_mask
= ~(~0U << amnt
);
262 for (unsigned int i
= 0; i
< sz
; i
++)
264 unsigned prev_carry_over
= carry_over
;
266 = (ptr
[i
] & carry_mask
);
268 carry_over
<<= ((unsigned char)BITS_PER_UNIT
- amnt
);
270 ptr
[i
] |= prev_carry_over
;
274 /* Clear out LEN bits starting from bit START in the byte array
275 PTR. This clears the bits to the *right* from START.
276 START must be within [0, BITS_PER_UNIT) and counts starting from
277 the least significant bit. */
280 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
285 /* Clear len bits to the right of start. */
286 else if (len
<= start
+ 1)
288 unsigned char mask
= (~(~0U << len
));
289 mask
= mask
<< (start
+ 1U - len
);
292 else if (start
!= BITS_PER_UNIT
- 1)
294 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
295 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
296 len
- (start
% BITS_PER_UNIT
) - 1);
298 else if (start
== BITS_PER_UNIT
- 1
299 && len
> BITS_PER_UNIT
)
301 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
302 for (unsigned int i
= 0; i
< nbytes
; i
++)
304 if (len
% BITS_PER_UNIT
!= 0)
305 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
306 len
% BITS_PER_UNIT
);
312 /* In the byte array PTR clear the bit region starting at bit
313 START and is LEN bits wide.
314 For regions spanning multiple bytes do this recursively until we reach
315 zero LEN or a region contained within a single byte. */
318 clear_bit_region (unsigned char *ptr
, unsigned int start
,
321 /* Degenerate base case. */
324 else if (start
>= BITS_PER_UNIT
)
325 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
326 /* Second base case. */
327 else if ((start
+ len
) <= BITS_PER_UNIT
)
329 unsigned char mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- len
));
330 mask
>>= BITS_PER_UNIT
- (start
+ len
);
336 /* Clear most significant bits in a byte and proceed with the next byte. */
339 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
340 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
) + 1);
342 /* Whole bytes need to be cleared. */
343 else if (start
== 0 && len
> BITS_PER_UNIT
)
345 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
346 /* We could recurse on each byte but do the loop here to avoid
347 recursing too deep. */
348 for (unsigned int i
= 0; i
< nbytes
; i
++)
350 /* Clear the remaining sub-byte region if there is one. */
351 if (len
% BITS_PER_UNIT
!= 0)
352 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
358 /* Write BITLEN bits of EXPR to the byte array PTR at
359 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
360 Return true if the operation succeeded. */
363 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
364 unsigned int total_bytes
)
366 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
368 bool sub_byte_op_p
= (bitlen
% BITS_PER_UNIT
) || (bitpos
% BITS_PER_UNIT
)
369 || mode_for_size (bitlen
, MODE_INT
, 0) == BLKmode
;
372 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
, 0)
376 We are writing a non byte-sized quantity or at a position that is not
378 |--------|--------|--------| ptr + first_byte
380 xxx xxxxxxxx xxx< bp>
383 First native_encode_expr EPXR into a temporary buffer and shift each
384 byte in the buffer by 'bp' (carrying the bits over as necessary).
385 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
386 <------bitlen---->< bp>
387 Then we clear the destination bits:
388 |---00000|00000000|000-----| ptr + first_byte
389 <-------bitlen--->< bp>
391 Finally we ORR the bytes of the shifted EXPR into the cleared region:
392 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
395 We are writing a non byte-sized quantity or at a position that is not
397 ptr + first_byte |--------|--------|--------|
399 <bp >xxx xxxxxxxx xxx
402 First native_encode_expr EPXR into a temporary buffer and shift each
403 byte in the buffer to the right by (carrying the bits over as necessary).
404 We shift by as much as needed to align the most significant bit of EXPR
406 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
407 <---bitlen----> <bp ><-----bitlen----->
408 Then we clear the destination bits:
409 ptr + first_byte |-----000||00000000||00000---|
410 <bp ><-------bitlen----->
412 Finally we ORR the bytes of the shifted EXPR into the cleared region:
413 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
414 The awkwardness comes from the fact that bitpos is counted from the
415 most significant bit of a byte. */
417 /* Allocate an extra byte so that we have space to shift into. */
418 unsigned int byte_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (expr
))) + 1;
419 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
420 zero_char_buf (tmpbuf
, byte_size
);
421 /* The store detection code should only have allowed constants that are
422 accepted by native_encode_expr. */
423 if (native_encode_expr (expr
, tmpbuf
, byte_size
, 0) == 0)
426 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
427 bytes to write. This means it can write more than
428 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
429 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
430 bitlen and zero out the bits that are not relevant as well (that may
431 contain a sign bit due to sign-extension). */
433 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
435 || bitlen
% BITS_PER_UNIT
!= 0)
437 /* On big-endian the padding is at the 'front' so just skip the initial
439 if (BYTES_BIG_ENDIAN
)
442 byte_size
-= padding
;
443 if (bitlen
% BITS_PER_UNIT
!= 0)
445 if (BYTES_BIG_ENDIAN
)
446 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
447 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
449 clear_bit_region (tmpbuf
, bitlen
,
450 byte_size
* BITS_PER_UNIT
- bitlen
);
454 /* Clear the bit region in PTR where the bits from TMPBUF will be
456 if (BYTES_BIG_ENDIAN
)
457 clear_bit_region_be (ptr
+ first_byte
,
458 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
460 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
463 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
464 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
466 bool skip_byte
= false;
467 if (BYTES_BIG_ENDIAN
)
469 /* BITPOS and BITLEN are exactly aligned and no shifting
471 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
472 || (bitpos_mod
== 0 && bitlen_mod
== 0))
476 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
477 of the value until it aligns with 'bp' in the next byte over. */
478 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
480 shift_amnt
= bitlen_mod
+ bitpos_mod
;
481 skip_byte
= bitlen_mod
!= 0;
486 Shift the value right within the same byte so it aligns with 'bp'. */
488 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
491 shift_amnt
= bitpos
% BITS_PER_UNIT
;
493 /* Create the shifted version of EXPR. */
494 if (!BYTES_BIG_ENDIAN
)
495 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
498 gcc_assert (BYTES_BIG_ENDIAN
);
499 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
500 /* If shifting right forced us to move into the next byte skip the now
509 /* Insert the bits from TMPBUF. */
510 for (unsigned int i
= 0; i
< byte_size
; i
++)
511 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
516 /* Sorting function for store_immediate_info objects.
517 Sorts them by bitposition. */
520 sort_by_bitpos (const void *x
, const void *y
)
522 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
523 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
525 if ((*tmp
)->bitpos
<= (*tmp2
)->bitpos
)
527 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
533 /* Sorting function for store_immediate_info objects.
534 Sorts them by the order field. */
537 sort_by_order (const void *x
, const void *y
)
539 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
540 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
542 if ((*tmp
)->order
< (*tmp2
)->order
)
544 else if ((*tmp
)->order
> (*tmp2
)->order
)
550 /* Initialize a merged_store_group object from a store_immediate_info
553 merged_store_group::merged_store_group (store_immediate_info
*info
)
555 start
= info
->bitpos
;
556 width
= info
->bitsize
;
557 /* VAL has memory allocated for it in apply_stores once the group
558 width has been finalized. */
560 align
= get_object_alignment (gimple_assign_lhs (info
->stmt
));
562 stores
.safe_push (info
);
563 last_stmt
= info
->stmt
;
564 last_order
= info
->order
;
565 first_stmt
= last_stmt
;
566 first_order
= last_order
;
570 merged_store_group::~merged_store_group ()
576 /* Merge a store recorded by INFO into this merged store.
577 The store is not overlapping with the existing recorded
581 merged_store_group::merge_into (store_immediate_info
*info
)
583 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
584 /* Make sure we're inserting in the position we think we're inserting. */
585 gcc_assert (info
->bitpos
== start
+ width
);
588 gimple
*stmt
= info
->stmt
;
589 stores
.safe_push (info
);
590 if (info
->order
> last_order
)
592 last_order
= info
->order
;
595 else if (info
->order
< first_order
)
597 first_order
= info
->order
;
602 /* Merge a store described by INFO into this merged store.
603 INFO overlaps in some way with the current store (i.e. it's not contiguous
604 which is handled by merged_store_group::merge_into). */
607 merged_store_group::merge_overlapping (store_immediate_info
*info
)
609 gimple
*stmt
= info
->stmt
;
610 stores
.safe_push (info
);
612 /* If the store extends the size of the group, extend the width. */
613 if ((info
->bitpos
+ info
->bitsize
) > (start
+ width
))
614 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
616 if (info
->order
> last_order
)
618 last_order
= info
->order
;
621 else if (info
->order
< first_order
)
623 first_order
= info
->order
;
628 /* Go through all the recorded stores in this group in program order and
629 apply their values to the VAL byte array to create the final merged
630 value. Return true if the operation succeeded. */
633 merged_store_group::apply_stores ()
635 /* The total width of the stores must add up to a whole number of bytes
636 and start at a byte boundary. We don't support emitting bitfield
637 references for now. Also, make sure we have more than one store
638 in the group, otherwise we cannot merge anything. */
639 if (width
% BITS_PER_UNIT
!= 0
640 || start
% BITS_PER_UNIT
!= 0
641 || stores
.length () == 1)
644 stores
.qsort (sort_by_order
);
645 struct store_immediate_info
*info
;
647 /* Create a buffer of a size that is 2 times the number of bytes we're
648 storing. That way native_encode_expr can write power-of-2-sized
649 chunks without overrunning. */
651 = 2 * (ROUND_UP (width
, BITS_PER_UNIT
) / BITS_PER_UNIT
);
652 val
= XCNEWVEC (unsigned char, buf_size
);
654 FOR_EACH_VEC_ELT (stores
, i
, info
)
656 unsigned int pos_in_buffer
= info
->bitpos
- start
;
657 bool ret
= encode_tree_to_bitpos (gimple_assign_rhs1 (info
->stmt
),
659 pos_in_buffer
, buf_size
);
660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
664 fprintf (dump_file
, "After writing ");
665 print_generic_expr (dump_file
,
666 gimple_assign_rhs1 (info
->stmt
), 0);
667 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
668 " at position %d the merged region contains:\n",
669 info
->bitsize
, pos_in_buffer
);
670 dump_char_array (dump_file
, val
, buf_size
);
673 fprintf (dump_file
, "Failed to merge stores\n");
681 /* Structure describing the store chain. */
683 struct imm_store_chain_info
686 auto_vec
<struct store_immediate_info
*> m_store_info
;
687 auto_vec
<merged_store_group
*> m_merged_store_groups
;
689 imm_store_chain_info (tree b_a
) : base_addr (b_a
) {}
690 bool terminate_and_process_chain ();
691 bool coalesce_immediate_stores ();
692 bool output_merged_store (merged_store_group
*);
693 bool output_merged_stores ();
696 const pass_data pass_data_tree_store_merging
= {
697 GIMPLE_PASS
, /* type */
698 "store-merging", /* name */
699 OPTGROUP_NONE
, /* optinfo_flags */
700 TV_GIMPLE_STORE_MERGING
, /* tv_id */
701 PROP_ssa
, /* properties_required */
702 0, /* properties_provided */
703 0, /* properties_destroyed */
704 0, /* todo_flags_start */
705 TODO_update_ssa
, /* todo_flags_finish */
708 class pass_store_merging
: public gimple_opt_pass
711 pass_store_merging (gcc::context
*ctxt
)
712 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
)
716 /* Pass not supported for PDP-endianness. */
720 return flag_store_merging
&& (WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
);
723 virtual unsigned int execute (function
*);
726 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
728 bool terminate_and_process_all_chains ();
729 bool terminate_all_aliasing_chains (tree
, imm_store_chain_info
**,
731 bool terminate_and_release_chain (imm_store_chain_info
*);
732 }; // class pass_store_merging
734 /* Terminate and process all recorded chains. Return true if any changes
738 pass_store_merging::terminate_and_process_all_chains ()
740 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
743 for (; iter
!= m_stores
.end (); ++iter
)
744 ret
|= terminate_and_release_chain ((*iter
).second
);
749 /* Terminate all chains that are affected by the assignment to DEST, appearing
750 in statement STMT and ultimately points to the object BASE. Return true if
751 at least one aliasing chain was terminated. BASE and DEST are allowed to
752 be NULL_TREE. In that case the aliasing checks are performed on the whole
753 statement rather than a particular operand in it. VAR_OFFSET_P signifies
754 whether STMT represents a store to BASE offset by a variable amount.
755 If that is the case we have to terminate any chain anchored at BASE. */
758 pass_store_merging::terminate_all_aliasing_chains (tree dest
,
766 /* If the statement doesn't touch memory it can't alias. */
767 if (!gimple_vuse (stmt
))
770 /* Check if the assignment destination (BASE) is part of a store chain.
771 This is to catch non-constant stores to destinations that may be part
775 /* We have a chain at BASE and we're writing to [BASE + <variable>].
776 This can interfere with any of the stores so terminate
780 terminate_and_release_chain (*chain_info
);
783 /* Otherwise go through every store in the chain to see if it
784 aliases with any of them. */
787 struct store_immediate_info
*info
;
789 FOR_EACH_VEC_ELT ((*chain_info
)->m_store_info
, i
, info
)
791 if (stmt_may_clobber_ref_p (info
->stmt
, dest
))
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
796 "stmt causes chain termination:\n");
797 print_gimple_stmt (dump_file
, stmt
, 0, 0);
799 terminate_and_release_chain (*chain_info
);
807 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
810 /* Check for aliasing with all other store chains. */
811 for (; iter
!= m_stores
.end (); ++iter
)
813 /* We already checked all the stores in chain_info and terminated the
814 chain if necessary. Skip it here. */
815 if (chain_info
&& (*chain_info
) == (*iter
).second
)
818 /* We can't use the base object here as that does not reliably exist.
819 Build a ao_ref from the base object address (if we know the
820 minimum and maximum offset and the maximum size we could improve
823 ao_ref_init_from_ptr_and_size (&chain_ref
, (*iter
).first
, NULL_TREE
);
824 if (ref_maybe_used_by_stmt_p (stmt
, &chain_ref
)
825 || stmt_may_clobber_ref_p_1 (stmt
, &chain_ref
))
827 terminate_and_release_chain ((*iter
).second
);
835 /* Helper function. Terminate the recorded chain storing to base object
836 BASE. Return true if the merging and output was successful. The m_stores
837 entry is removed after the processing in any case. */
840 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
842 bool ret
= chain_info
->terminate_and_process_chain ();
843 m_stores
.remove (chain_info
->base_addr
);
848 /* Go through the candidate stores recorded in m_store_info and merge them
849 into merged_store_group objects recorded into m_merged_store_groups
850 representing the widened stores. Return true if coalescing was successful
851 and the number of widened stores is fewer than the original number
855 imm_store_chain_info::coalesce_immediate_stores ()
857 /* Anything less can't be processed. */
858 if (m_store_info
.length () < 2)
861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
862 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
863 m_store_info
.length ());
865 store_immediate_info
*info
;
868 /* Order the stores by the bitposition they write to. */
869 m_store_info
.qsort (sort_by_bitpos
);
871 info
= m_store_info
[0];
872 merged_store_group
*merged_store
= new merged_store_group (info
);
874 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
878 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
879 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
880 i
, info
->bitsize
, info
->bitpos
);
881 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
), 0);
882 fprintf (dump_file
, "\n------------\n");
890 Overlapping stores. */
891 unsigned HOST_WIDE_INT start
= info
->bitpos
;
892 if (IN_RANGE (start
, merged_store
->start
,
893 merged_store
->start
+ merged_store
->width
- 1))
895 merged_store
->merge_overlapping (info
);
899 /* |---store 1---| <gap> |---store 2---|.
900 Gap between stores. Start a new group. */
901 if (start
!= merged_store
->start
+ merged_store
->width
)
903 /* Try to apply all the stores recorded for the group to determine
904 the bitpattern they write and discard it if that fails.
905 This will also reject single-store groups. */
906 if (!merged_store
->apply_stores ())
909 m_merged_store_groups
.safe_push (merged_store
);
911 merged_store
= new merged_store_group (info
);
916 /* |---store 1---||---store 2---|
917 This store is consecutive to the previous one.
918 Merge it into the current store group. */
919 merged_store
->merge_into (info
);
922 /* Record or discard the last store group. */
923 if (!merged_store
->apply_stores ())
926 m_merged_store_groups
.safe_push (merged_store
);
928 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
930 = !m_merged_store_groups
.is_empty ()
931 && m_merged_store_groups
.length () < m_store_info
.length ();
933 if (success
&& dump_file
)
934 fprintf (dump_file
, "Coalescing successful!\n"
935 "Merged into %u stores\n",
936 m_merged_store_groups
.length ());
941 /* Return the type to use for the merged stores described by STMTS.
942 This is needed to get the alias sets right. */
945 get_alias_type_for_stmts (auto_vec
<gimple
*> &stmts
)
949 tree lhs
= gimple_assign_lhs (stmts
[0]);
950 tree type
= reference_alias_ptr_type (lhs
);
952 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
957 lhs
= gimple_assign_lhs (stmt
);
958 tree type1
= reference_alias_ptr_type (lhs
);
959 if (!alias_ptr_types_compatible_p (type
, type1
))
960 return ptr_type_node
;
965 /* Return the location_t information we can find among the statements
969 get_location_for_stmts (auto_vec
<gimple
*> &stmts
)
974 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
975 if (gimple_has_location (stmt
))
976 return gimple_location (stmt
);
978 return UNKNOWN_LOCATION
;
981 /* Used to decribe a store resulting from splitting a wide store in smaller
982 regularly-sized stores in split_group. */
986 unsigned HOST_WIDE_INT bytepos
;
987 unsigned HOST_WIDE_INT size
;
988 unsigned HOST_WIDE_INT align
;
989 auto_vec
<gimple
*> orig_stmts
;
990 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
991 unsigned HOST_WIDE_INT
);
994 /* Simple constructor. */
996 split_store::split_store (unsigned HOST_WIDE_INT bp
,
997 unsigned HOST_WIDE_INT sz
,
998 unsigned HOST_WIDE_INT al
)
999 : bytepos (bp
), size (sz
), align (al
)
1001 orig_stmts
.create (0);
1004 /* Record all statements corresponding to stores in GROUP that write to
1005 the region starting at BITPOS and is of size BITSIZE. Record such
1006 statements in STMTS. The stores in GROUP must be sorted by
1010 find_constituent_stmts (struct merged_store_group
*group
,
1011 auto_vec
<gimple
*> &stmts
,
1012 unsigned HOST_WIDE_INT bitpos
,
1013 unsigned HOST_WIDE_INT bitsize
)
1015 struct store_immediate_info
*info
;
1017 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1018 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
1020 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1021 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1022 if (stmt_end
< bitpos
)
1024 /* The stores in GROUP are ordered by bitposition so if we're past
1025 the region for this group return early. */
1026 if (stmt_start
> end
)
1029 if (IN_RANGE (stmt_start
, bitpos
, bitpos
+ bitsize
)
1030 || IN_RANGE (stmt_end
, bitpos
, end
)
1031 /* The statement writes a region that completely encloses the region
1032 that this group writes. Unlikely to occur but let's
1034 || IN_RANGE (bitpos
, stmt_start
, stmt_end
))
1035 stmts
.safe_push (info
->stmt
);
1039 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1040 vector with split_store structs describing the byte offset (from the base),
1041 the bit size and alignment of each store as well as the original statements
1042 involved in each such split group.
1043 This is to separate the splitting strategy from the statement
1044 building/emission/linking done in output_merged_store.
1045 At the moment just start with the widest possible size and keep emitting
1046 the widest we can until we have emitted all the bytes, halving the size
1047 when appropriate. */
1050 split_group (merged_store_group
*group
,
1051 auto_vec
<struct split_store
*> &split_stores
)
1053 unsigned HOST_WIDE_INT pos
= group
->start
;
1054 unsigned HOST_WIDE_INT size
= group
->width
;
1055 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1056 unsigned HOST_WIDE_INT align
= group
->align
;
1058 /* We don't handle partial bitfields for now. We shouldn't have
1059 reached this far. */
1060 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1062 bool allow_unaligned
1063 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1065 unsigned int try_size
= MAX_STORE_BITSIZE
;
1066 while (try_size
> size
1067 || (!allow_unaligned
1068 && try_size
> align
))
1071 if (try_size
< BITS_PER_UNIT
)
1075 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1076 group
->stores
.qsort (sort_by_bitpos
);
1080 struct split_store
*store
= new split_store (try_pos
, try_size
, align
);
1081 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1082 find_constituent_stmts (group
, store
->orig_stmts
, try_bitpos
, try_size
);
1083 split_stores
.safe_push (store
);
1085 try_pos
+= try_size
/ BITS_PER_UNIT
;
1089 while (size
< try_size
)
1095 /* Given a merged store group GROUP output the widened version of it.
1096 The store chain is against the base object BASE.
1097 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1098 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1099 Make sure that the number of statements output is less than the number of
1100 original statements. If a better sequence is possible emit it and
1104 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1106 unsigned HOST_WIDE_INT start_byte_pos
= group
->start
/ BITS_PER_UNIT
;
1108 unsigned int orig_num_stmts
= group
->stores
.length ();
1109 if (orig_num_stmts
< 2)
1112 auto_vec
<struct split_store
*> split_stores
;
1113 split_stores
.create (0);
1114 if (!split_group (group
, split_stores
))
1117 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1118 gimple_seq seq
= NULL
;
1119 unsigned int num_stmts
= 0;
1120 tree last_vdef
, new_vuse
;
1121 last_vdef
= gimple_vdef (group
->last_stmt
);
1122 new_vuse
= gimple_vuse (group
->last_stmt
);
1124 gimple
*stmt
= NULL
;
1125 /* The new SSA names created. Keep track of them so that we can free them
1126 if we decide to not use the new sequence. */
1127 auto_vec
<tree
> new_ssa_names
;
1128 split_store
*split_store
;
1132 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &seq
,
1133 is_gimple_mem_ref_addr
, NULL_TREE
);
1134 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1136 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1137 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1138 unsigned HOST_WIDE_INT align
= split_store
->align
;
1139 tree offset_type
= get_alias_type_for_stmts (split_store
->orig_stmts
);
1140 location_t loc
= get_location_for_stmts (split_store
->orig_stmts
);
1142 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1143 int_type
= build_aligned_type (int_type
, align
);
1144 tree dest
= fold_build2 (MEM_REF
, int_type
, addr
,
1145 build_int_cst (offset_type
, try_pos
));
1147 tree src
= native_interpret_expr (int_type
,
1148 group
->val
+ try_pos
- start_byte_pos
,
1151 stmt
= gimple_build_assign (dest
, src
);
1152 gimple_set_location (stmt
, loc
);
1153 gimple_set_vuse (stmt
, new_vuse
);
1154 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1156 /* We didn't manage to reduce the number of statements. Bail out. */
1157 if (++num_stmts
== orig_num_stmts
)
1159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1161 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1162 " Not profitable to emit new sequence.\n",
1165 unsigned int ssa_count
;
1167 /* Don't forget to cleanup the temporary SSA names. */
1168 FOR_EACH_VEC_ELT (new_ssa_names
, ssa_count
, ssa_name
)
1169 release_ssa_name (ssa_name
);
1176 if (i
< split_stores
.length () - 1)
1178 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
1179 new_ssa_names
.safe_push (new_vdef
);
1182 new_vdef
= last_vdef
;
1184 gimple_set_vdef (stmt
, new_vdef
);
1185 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
1186 new_vuse
= new_vdef
;
1189 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1199 "New sequence of %u stmts to replace old one of %u stmts\n",
1200 num_stmts
, orig_num_stmts
);
1201 if (dump_flags
& TDF_DETAILS
)
1202 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1204 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
1209 /* Process the merged_store_group objects created in the coalescing phase.
1210 The stores are all against the base object BASE.
1211 Try to output the widened stores and delete the original statements if
1212 successful. Return true iff any changes were made. */
1215 imm_store_chain_info::output_merged_stores ()
1218 merged_store_group
*merged_store
;
1220 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
1222 if (output_merged_store (merged_store
))
1225 store_immediate_info
*store
;
1226 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
1228 gimple
*stmt
= store
->stmt
;
1229 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1230 gsi_remove (&gsi
, true);
1231 if (stmt
!= merged_store
->last_stmt
)
1233 unlink_stmt_vdef (stmt
);
1234 release_defs (stmt
);
1240 if (ret
&& dump_file
)
1241 fprintf (dump_file
, "Merging successful!\n");
1246 /* Coalesce the store_immediate_info objects recorded against the base object
1247 BASE in the first phase and output them.
1248 Delete the allocated structures.
1249 Return true if any changes were made. */
1252 imm_store_chain_info::terminate_and_process_chain ()
1254 /* Process store chain. */
1256 if (m_store_info
.length () > 1)
1258 ret
= coalesce_immediate_stores ();
1260 ret
= output_merged_stores ();
1263 /* Delete all the entries we allocated ourselves. */
1264 store_immediate_info
*info
;
1266 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1269 merged_store_group
*merged_info
;
1270 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
1276 /* Return true iff LHS is a destination potentially interesting for
1277 store merging. In practice these are the codes that get_inner_reference
1281 lhs_valid_for_store_merging_p (tree lhs
)
1283 tree_code code
= TREE_CODE (lhs
);
1285 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
1286 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
1292 /* Return true if the tree RHS is a constant we want to consider
1293 during store merging. In practice accept all codes that
1294 native_encode_expr accepts. */
1297 rhs_valid_for_store_merging_p (tree rhs
)
1299 tree type
= TREE_TYPE (rhs
);
1300 if (TREE_CODE_CLASS (TREE_CODE (rhs
)) != tcc_constant
1301 || !can_native_encode_type_p (type
))
1307 /* Entry point for the pass. Go over each basic block recording chains of
1308 immediate stores. Upon encountering a terminating statement (as defined
1309 by stmt_terminates_chain_p) process the recorded stores and emit the widened
1313 pass_store_merging::execute (function
*fun
)
1316 hash_set
<gimple
*> orig_stmts
;
1318 FOR_EACH_BB_FN (bb
, fun
)
1320 gimple_stmt_iterator gsi
;
1321 unsigned HOST_WIDE_INT num_statements
= 0;
1322 /* Record the original statements so that we can keep track of
1323 statements emitted in this pass and not re-process new
1325 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1327 if (is_gimple_debug (gsi_stmt (gsi
)))
1330 if (++num_statements
> 2)
1334 if (num_statements
< 2)
1337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1338 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
1340 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1342 gimple
*stmt
= gsi_stmt (gsi
);
1344 if (gimple_has_volatile_ops (stmt
))
1346 /* Terminate all chains. */
1347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1348 fprintf (dump_file
, "Volatile access terminates "
1350 terminate_and_process_all_chains ();
1354 if (is_gimple_debug (stmt
))
1357 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
1358 && !stmt_can_throw_internal (stmt
)
1359 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
1361 tree lhs
= gimple_assign_lhs (stmt
);
1362 tree rhs
= gimple_assign_rhs1 (stmt
);
1364 HOST_WIDE_INT bitsize
, bitpos
;
1366 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
1367 tree offset
, base_addr
;
1369 = get_inner_reference (lhs
, &bitsize
, &bitpos
, &offset
, &mode
,
1370 &unsignedp
, &reversep
, &volatilep
);
1371 /* As a future enhancement we could handle stores with the same
1373 bool invalid
= reversep
1374 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
1375 && (TREE_CODE (rhs
) != INTEGER_CST
))
1376 || !rhs_valid_for_store_merging_p (rhs
);
1378 /* We do not want to rewrite TARGET_MEM_REFs. */
1379 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
1381 /* In some cases get_inner_reference may return a
1382 MEM_REF [ptr + byteoffset]. For the purposes of this pass
1383 canonicalize the base_addr to MEM_REF [ptr] and take
1384 byteoffset into account in the bitpos. This occurs in
1385 PR 23684 and this way we can catch more chains. */
1386 else if (TREE_CODE (base_addr
) == MEM_REF
)
1388 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
1389 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
1391 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
1392 bitpos
= bit_off
.to_shwi ();
1395 base_addr
= TREE_OPERAND (base_addr
, 0);
1397 /* get_inner_reference returns the base object, get at its
1403 base_addr
= build_fold_addr_expr (base_addr
);
1407 && offset
!= NULL_TREE
)
1409 /* If the access is variable offset then a base
1410 decl has to be address-taken to be able to
1411 emit pointer-based stores to it.
1412 ??? We might be able to get away with
1413 re-using the original base up to the first
1414 variable part and then wrapping that inside
1416 tree base
= get_base_address (base_addr
);
1419 && ! TREE_ADDRESSABLE (base
)))
1422 base_addr
= build2 (POINTER_PLUS_EXPR
,
1423 TREE_TYPE (base_addr
),
1427 struct imm_store_chain_info
**chain_info
1428 = m_stores
.get (base_addr
);
1432 store_immediate_info
*info
;
1435 info
= new store_immediate_info (
1436 bitsize
, bitpos
, stmt
,
1437 (*chain_info
)->m_store_info
.length ());
1438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1441 "Recording immediate store from stmt:\n");
1442 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1444 (*chain_info
)->m_store_info
.safe_push (info
);
1445 /* If we reach the limit of stores to merge in a chain
1446 terminate and process the chain now. */
1447 if ((*chain_info
)->m_store_info
.length ()
1449 PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
1451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1453 "Reached maximum number of statements"
1455 terminate_and_release_chain (*chain_info
);
1460 /* Store aliases any existing chain? */
1461 terminate_all_aliasing_chains (lhs
, chain_info
, false, stmt
);
1462 /* Start a new chain. */
1463 struct imm_store_chain_info
*new_chain
1464 = new imm_store_chain_info (base_addr
);
1465 info
= new store_immediate_info (bitsize
, bitpos
,
1467 new_chain
->m_store_info
.safe_push (info
);
1468 m_stores
.put (base_addr
, new_chain
);
1469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1472 "Starting new chain with statement:\n");
1473 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1474 fprintf (dump_file
, "The base object is:\n");
1475 print_generic_expr (dump_file
, base_addr
, 0);
1476 fprintf (dump_file
, "\n");
1480 terminate_all_aliasing_chains (lhs
, chain_info
,
1481 offset
!= NULL_TREE
, stmt
);
1486 terminate_all_aliasing_chains (NULL_TREE
, NULL
, false, stmt
);
1488 terminate_and_process_all_chains ();
1495 /* Construct and return a store merging pass object. */
1498 make_pass_store_merging (gcc::context
*ctxt
)
1500 return new pass_store_merging (ctxt
);