1 /* GIMPLE store merging pass.
2 Copyright (C) 2016-2017 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, values loaded from memory or bitwise operations
23 on those to consecutive memory locations into fewer wider stores.
24 For example, if we have a sequence peforming four byte stores to
25 consecutive memory locations:
30 we can transform this into a single 4-byte store if the target supports it:
31 [p] := imm1:imm2:imm3:imm4 //concatenated immediates according to endianness.
38 if there is no overlap can be transformed into a single 4-byte
39 load followed by single 4-byte store.
43 [p + 1B] := [q + 1B] ^ imm2;
44 [p + 2B] := [q + 2B] ^ imm3;
45 [p + 3B] := [q + 3B] ^ imm4;
46 if there is no overlap can be transformed into a single 4-byte
47 load, xored with imm1:imm2:imm3:imm4 and stored using a single 4-byte store.
49 The algorithm is applied to each basic block in three phases:
51 1) Scan through the basic block recording assignments to
52 destinations that can be expressed as a store to memory of a certain size
53 at a certain bit offset from expressions we can handle. For bit-fields
54 we also note the surrounding bit region, bits that could be stored in
55 a read-modify-write operation when storing the bit-field. Record store
56 chains to different bases in a hash_map (m_stores) and make sure to
57 terminate such chains when appropriate (for example when when the stored
58 values get used subsequently).
59 These stores can be a result of structure element initializers, array stores
60 etc. A store_immediate_info object is recorded for every such store.
61 Record as many such assignments to a single base as possible until a
62 statement that interferes with the store sequence is encountered.
63 Each store has up to 2 operands, which can be an immediate constant
64 or a memory load, from which the value to be stored can be computed.
65 At most one of the operands can be a constant. The operands are recorded
66 in store_operand_info struct.
68 2) Analyze the chain of stores recorded in phase 1) (i.e. the vector of
69 store_immediate_info objects) and coalesce contiguous stores into
70 merged_store_group objects. For bit-fields stores, we don't need to
71 require the stores to be contiguous, just their surrounding bit regions
72 have to be contiguous. If the expression being stored is different
73 between adjacent stores, such as one store storing a constant and
74 following storing a value loaded from memory, or if the loaded memory
75 objects are not adjacent, a new merged_store_group is created as well.
77 For example, given the stores:
84 This phase would produce two merged_store_group objects, one recording the
85 two bytes stored in the memory region [p : p + 1] and another
86 recording the four bytes stored in the memory region [p + 3 : p + 6].
88 3) The merged_store_group objects produced in phase 2) are processed
89 to generate the sequence of wider stores that set the contiguous memory
90 regions to the sequence of bytes that correspond to it. This may emit
91 multiple stores per store group to handle contiguous stores that are not
92 of a size that is a power of 2. For example it can try to emit a 40-bit
93 store as a 32-bit store followed by an 8-bit store.
94 We try to emit as wide stores as we can while respecting STRICT_ALIGNMENT or
95 TARGET_SLOW_UNALIGNED_ACCESS rules.
97 Note on endianness and example:
98 Consider 2 contiguous 16-bit stores followed by 2 contiguous 8-bit stores:
104 The memory layout for little-endian (LE) and big-endian (BE) must be:
114 To merge these into a single 48-bit merged value 'val' in phase 2)
115 on little-endian we insert stores to higher (consecutive) bitpositions
116 into the most significant bits of the merged value.
117 The final merged value would be: 0xcdab56781234
119 For big-endian we insert stores to higher bitpositions into the least
120 significant bits of the merged value.
121 The final merged value would be: 0x12345678abcd
123 Then, in phase 3), we want to emit this 48-bit value as a 32-bit store
124 followed by a 16-bit store. Again, we must consider endianness when
125 breaking down the 48-bit value 'val' computed above.
126 For little endian we emit:
127 [p] (32-bit) := 0x56781234; // val & 0x0000ffffffff;
128 [p + 4B] (16-bit) := 0xcdab; // (val & 0xffff00000000) >> 32;
130 Whereas for big-endian we emit:
131 [p] (32-bit) := 0x12345678; // (val & 0xffffffff0000) >> 16;
132 [p + 4B] (16-bit) := 0xabcd; // val & 0x00000000ffff; */
136 #include "coretypes.h"
140 #include "builtins.h"
141 #include "fold-const.h"
142 #include "tree-pass.h"
144 #include "gimple-pretty-print.h"
146 #include "fold-const.h"
148 #include "print-tree.h"
149 #include "tree-hash-traits.h"
150 #include "gimple-iterator.h"
151 #include "gimplify.h"
152 #include "stor-layout.h"
154 #include "tree-cfg.h"
157 #include "gimplify-me.h"
159 #include "expr.h" /* For get_bit_range. */
160 #include "selftest.h"
162 /* The maximum size (in bits) of the stores this pass should generate. */
163 #define MAX_STORE_BITSIZE (BITS_PER_WORD)
164 #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
166 /* Limit to bound the number of aliasing checks for loads with the same
167 vuse as the corresponding store. */
168 #define MAX_STORE_ALIAS_CHECKS 64
172 /* Struct recording one operand for the store, which is either a constant,
173 then VAL represents the constant and all the other fields are zero,
174 or a memory load, then VAL represents the reference, BASE_ADDR is non-NULL
175 and the other fields also reflect the memory load. */
177 struct store_operand_info
181 unsigned HOST_WIDE_INT bitsize
;
182 unsigned HOST_WIDE_INT bitpos
;
183 unsigned HOST_WIDE_INT bitregion_start
;
184 unsigned HOST_WIDE_INT bitregion_end
;
186 store_operand_info ();
189 store_operand_info::store_operand_info ()
190 : val (NULL_TREE
), base_addr (NULL_TREE
), bitsize (0), bitpos (0),
191 bitregion_start (0), bitregion_end (0), stmt (NULL
)
195 /* Struct recording the information about a single store of an immediate
196 to memory. These are created in the first phase and coalesced into
197 merged_store_group objects in the second phase. */
199 struct store_immediate_info
201 unsigned HOST_WIDE_INT bitsize
;
202 unsigned HOST_WIDE_INT bitpos
;
203 unsigned HOST_WIDE_INT bitregion_start
;
204 /* This is one past the last bit of the bit region. */
205 unsigned HOST_WIDE_INT bitregion_end
;
208 /* INTEGER_CST for constant stores, MEM_REF for memory copy or
209 BIT_*_EXPR for logical bitwise operation. */
210 enum tree_code rhs_code
;
211 /* Operands. For BIT_*_EXPR rhs_code both operands are used, otherwise
212 just the first one. */
213 store_operand_info ops
[2];
214 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
215 unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
216 gimple
*, unsigned int, enum tree_code
,
217 const store_operand_info
&,
218 const store_operand_info
&);
221 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
222 unsigned HOST_WIDE_INT bp
,
223 unsigned HOST_WIDE_INT brs
,
224 unsigned HOST_WIDE_INT bre
,
227 enum tree_code rhscode
,
228 const store_operand_info
&op0r
,
229 const store_operand_info
&op1r
)
230 : bitsize (bs
), bitpos (bp
), bitregion_start (brs
), bitregion_end (bre
),
231 stmt (st
), order (ord
), rhs_code (rhscode
)
232 #if __cplusplus >= 201103L
243 /* Struct representing a group of stores to contiguous memory locations.
244 These are produced by the second phase (coalescing) and consumed in the
245 third phase that outputs the widened stores. */
247 struct merged_store_group
249 unsigned HOST_WIDE_INT start
;
250 unsigned HOST_WIDE_INT width
;
251 unsigned HOST_WIDE_INT bitregion_start
;
252 unsigned HOST_WIDE_INT bitregion_end
;
253 /* The size of the allocated memory for val and mask. */
254 unsigned HOST_WIDE_INT buf_size
;
255 unsigned HOST_WIDE_INT align_base
;
256 unsigned HOST_WIDE_INT load_align_base
[2];
259 unsigned int load_align
[2];
260 unsigned int first_order
;
261 unsigned int last_order
;
263 auto_vec
<store_immediate_info
*> stores
;
264 /* We record the first and last original statements in the sequence because
265 we'll need their vuse/vdef and replacement position. It's easier to keep
266 track of them separately as 'stores' is reordered by apply_stores. */
272 merged_store_group (store_immediate_info
*);
273 ~merged_store_group ();
274 void merge_into (store_immediate_info
*);
275 void merge_overlapping (store_immediate_info
*);
276 bool apply_stores ();
278 void do_merge (store_immediate_info
*);
281 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
284 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
289 for (unsigned int i
= 0; i
< len
; i
++)
290 fprintf (fd
, "%x ", ptr
[i
]);
294 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
295 bits between adjacent elements. AMNT should be within
298 00011111|11100000 << 2 = 01111111|10000000
299 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
302 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
307 unsigned char carry_over
= 0U;
308 unsigned char carry_mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- amnt
);
309 unsigned char clear_mask
= (~0U) << amnt
;
311 for (unsigned int i
= 0; i
< sz
; i
++)
313 unsigned prev_carry_over
= carry_over
;
314 carry_over
= (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
319 ptr
[i
] &= clear_mask
;
320 ptr
[i
] |= prev_carry_over
;
325 /* Like shift_bytes_in_array but for big-endian.
326 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
327 bits between adjacent elements. AMNT should be within
330 00011111|11100000 >> 2 = 00000111|11111000
331 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
334 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
340 unsigned char carry_over
= 0U;
341 unsigned char carry_mask
= ~(~0U << amnt
);
343 for (unsigned int i
= 0; i
< sz
; i
++)
345 unsigned prev_carry_over
= carry_over
;
346 carry_over
= ptr
[i
] & carry_mask
;
348 carry_over
<<= (unsigned char) BITS_PER_UNIT
- amnt
;
350 ptr
[i
] |= prev_carry_over
;
354 /* Clear out LEN bits starting from bit START in the byte array
355 PTR. This clears the bits to the *right* from START.
356 START must be within [0, BITS_PER_UNIT) and counts starting from
357 the least significant bit. */
360 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
365 /* Clear len bits to the right of start. */
366 else if (len
<= start
+ 1)
368 unsigned char mask
= (~(~0U << len
));
369 mask
= mask
<< (start
+ 1U - len
);
372 else if (start
!= BITS_PER_UNIT
- 1)
374 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
375 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
376 len
- (start
% BITS_PER_UNIT
) - 1);
378 else if (start
== BITS_PER_UNIT
- 1
379 && len
> BITS_PER_UNIT
)
381 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
382 memset (ptr
, 0, nbytes
);
383 if (len
% BITS_PER_UNIT
!= 0)
384 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
385 len
% BITS_PER_UNIT
);
391 /* In the byte array PTR clear the bit region starting at bit
392 START and is LEN bits wide.
393 For regions spanning multiple bytes do this recursively until we reach
394 zero LEN or a region contained within a single byte. */
397 clear_bit_region (unsigned char *ptr
, unsigned int start
,
400 /* Degenerate base case. */
403 else if (start
>= BITS_PER_UNIT
)
404 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
405 /* Second base case. */
406 else if ((start
+ len
) <= BITS_PER_UNIT
)
408 unsigned char mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- len
);
409 mask
>>= BITS_PER_UNIT
- (start
+ len
);
415 /* Clear most significant bits in a byte and proceed with the next byte. */
418 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
419 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
));
421 /* Whole bytes need to be cleared. */
422 else if (start
== 0 && len
> BITS_PER_UNIT
)
424 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
425 /* We could recurse on each byte but we clear whole bytes, so a simple
427 memset (ptr
, '\0', nbytes
);
428 /* Clear the remaining sub-byte region if there is one. */
429 if (len
% BITS_PER_UNIT
!= 0)
430 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
436 /* Write BITLEN bits of EXPR to the byte array PTR at
437 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
438 Return true if the operation succeeded. */
441 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
442 unsigned int total_bytes
)
444 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
446 bool sub_byte_op_p
= ((bitlen
% BITS_PER_UNIT
)
447 || (bitpos
% BITS_PER_UNIT
)
448 || !int_mode_for_size (bitlen
, 0).exists ());
451 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
) != 0;
454 We are writing a non byte-sized quantity or at a position that is not
456 |--------|--------|--------| ptr + first_byte
458 xxx xxxxxxxx xxx< bp>
461 First native_encode_expr EXPR into a temporary buffer and shift each
462 byte in the buffer by 'bp' (carrying the bits over as necessary).
463 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
464 <------bitlen---->< bp>
465 Then we clear the destination bits:
466 |---00000|00000000|000-----| ptr + first_byte
467 <-------bitlen--->< bp>
469 Finally we ORR the bytes of the shifted EXPR into the cleared region:
470 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
473 We are writing a non byte-sized quantity or at a position that is not
475 ptr + first_byte |--------|--------|--------|
477 <bp >xxx xxxxxxxx xxx
480 First native_encode_expr EXPR into a temporary buffer and shift each
481 byte in the buffer to the right by (carrying the bits over as necessary).
482 We shift by as much as needed to align the most significant bit of EXPR
484 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
485 <---bitlen----> <bp ><-----bitlen----->
486 Then we clear the destination bits:
487 ptr + first_byte |-----000||00000000||00000---|
488 <bp ><-------bitlen----->
490 Finally we ORR the bytes of the shifted EXPR into the cleared region:
491 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
492 The awkwardness comes from the fact that bitpos is counted from the
493 most significant bit of a byte. */
495 /* We must be dealing with fixed-size data at this point, since the
496 total size is also fixed. */
497 fixed_size_mode mode
= as_a
<fixed_size_mode
> (TYPE_MODE (TREE_TYPE (expr
)));
498 /* Allocate an extra byte so that we have space to shift into. */
499 unsigned int byte_size
= GET_MODE_SIZE (mode
) + 1;
500 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
501 memset (tmpbuf
, '\0', byte_size
);
502 /* The store detection code should only have allowed constants that are
503 accepted by native_encode_expr. */
504 if (native_encode_expr (expr
, tmpbuf
, byte_size
- 1) == 0)
507 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
508 bytes to write. This means it can write more than
509 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
510 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
511 bitlen and zero out the bits that are not relevant as well (that may
512 contain a sign bit due to sign-extension). */
514 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
515 /* On big-endian the padding is at the 'front' so just skip the initial
517 if (BYTES_BIG_ENDIAN
)
520 byte_size
-= padding
;
522 if (bitlen
% BITS_PER_UNIT
!= 0)
524 if (BYTES_BIG_ENDIAN
)
525 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
526 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
528 clear_bit_region (tmpbuf
, bitlen
,
529 byte_size
* BITS_PER_UNIT
- bitlen
);
531 /* Left shifting relies on the last byte being clear if bitlen is
532 a multiple of BITS_PER_UNIT, which might not be clear if
533 there are padding bytes. */
534 else if (!BYTES_BIG_ENDIAN
)
535 tmpbuf
[byte_size
- 1] = '\0';
537 /* Clear the bit region in PTR where the bits from TMPBUF will be
539 if (BYTES_BIG_ENDIAN
)
540 clear_bit_region_be (ptr
+ first_byte
,
541 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
543 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
546 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
547 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
549 bool skip_byte
= false;
550 if (BYTES_BIG_ENDIAN
)
552 /* BITPOS and BITLEN are exactly aligned and no shifting
554 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
555 || (bitpos_mod
== 0 && bitlen_mod
== 0))
559 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
560 of the value until it aligns with 'bp' in the next byte over. */
561 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
563 shift_amnt
= bitlen_mod
+ bitpos_mod
;
564 skip_byte
= bitlen_mod
!= 0;
569 Shift the value right within the same byte so it aligns with 'bp'. */
571 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
574 shift_amnt
= bitpos
% BITS_PER_UNIT
;
576 /* Create the shifted version of EXPR. */
577 if (!BYTES_BIG_ENDIAN
)
579 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
585 gcc_assert (BYTES_BIG_ENDIAN
);
586 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
587 /* If shifting right forced us to move into the next byte skip the now
596 /* Insert the bits from TMPBUF. */
597 for (unsigned int i
= 0; i
< byte_size
; i
++)
598 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
603 /* Sorting function for store_immediate_info objects.
604 Sorts them by bitposition. */
607 sort_by_bitpos (const void *x
, const void *y
)
609 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
610 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
612 if ((*tmp
)->bitpos
< (*tmp2
)->bitpos
)
614 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
617 /* If they are the same let's use the order which is guaranteed to
619 return (*tmp
)->order
- (*tmp2
)->order
;
622 /* Sorting function for store_immediate_info objects.
623 Sorts them by the order field. */
626 sort_by_order (const void *x
, const void *y
)
628 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
629 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
631 if ((*tmp
)->order
< (*tmp2
)->order
)
633 else if ((*tmp
)->order
> (*tmp2
)->order
)
639 /* Initialize a merged_store_group object from a store_immediate_info
642 merged_store_group::merged_store_group (store_immediate_info
*info
)
644 start
= info
->bitpos
;
645 width
= info
->bitsize
;
646 bitregion_start
= info
->bitregion_start
;
647 bitregion_end
= info
->bitregion_end
;
648 /* VAL has memory allocated for it in apply_stores once the group
649 width has been finalized. */
652 unsigned HOST_WIDE_INT align_bitpos
= 0;
653 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
654 &align
, &align_bitpos
);
655 align_base
= start
- align_bitpos
;
656 for (int i
= 0; i
< 2; ++i
)
658 store_operand_info
&op
= info
->ops
[i
];
659 if (op
.base_addr
== NULL_TREE
)
662 load_align_base
[i
] = 0;
666 get_object_alignment_1 (op
.val
, &load_align
[i
], &align_bitpos
);
667 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
671 stores
.safe_push (info
);
672 last_stmt
= info
->stmt
;
673 last_order
= info
->order
;
674 first_stmt
= last_stmt
;
675 first_order
= last_order
;
679 merged_store_group::~merged_store_group ()
685 /* Helper method for merge_into and merge_overlapping to do
688 merged_store_group::do_merge (store_immediate_info
*info
)
690 bitregion_start
= MIN (bitregion_start
, info
->bitregion_start
);
691 bitregion_end
= MAX (bitregion_end
, info
->bitregion_end
);
693 unsigned int this_align
;
694 unsigned HOST_WIDE_INT align_bitpos
= 0;
695 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
696 &this_align
, &align_bitpos
);
697 if (this_align
> align
)
700 align_base
= info
->bitpos
- align_bitpos
;
702 for (int i
= 0; i
< 2; ++i
)
704 store_operand_info
&op
= info
->ops
[i
];
708 get_object_alignment_1 (op
.val
, &this_align
, &align_bitpos
);
709 if (this_align
> load_align
[i
])
711 load_align
[i
] = this_align
;
712 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
716 gimple
*stmt
= info
->stmt
;
717 stores
.safe_push (info
);
718 if (info
->order
> last_order
)
720 last_order
= info
->order
;
723 else if (info
->order
< first_order
)
725 first_order
= info
->order
;
730 /* Merge a store recorded by INFO into this merged store.
731 The store is not overlapping with the existing recorded
735 merged_store_group::merge_into (store_immediate_info
*info
)
737 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
738 /* Make sure we're inserting in the position we think we're inserting. */
739 gcc_assert (info
->bitpos
>= start
+ width
740 && info
->bitregion_start
<= bitregion_end
);
746 /* Merge a store described by INFO into this merged store.
747 INFO overlaps in some way with the current store (i.e. it's not contiguous
748 which is handled by merged_store_group::merge_into). */
751 merged_store_group::merge_overlapping (store_immediate_info
*info
)
753 /* If the store extends the size of the group, extend the width. */
754 if (info
->bitpos
+ info
->bitsize
> start
+ width
)
755 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
760 /* Go through all the recorded stores in this group in program order and
761 apply their values to the VAL byte array to create the final merged
762 value. Return true if the operation succeeded. */
765 merged_store_group::apply_stores ()
767 /* Make sure we have more than one store in the group, otherwise we cannot
769 if (bitregion_start
% BITS_PER_UNIT
!= 0
770 || bitregion_end
% BITS_PER_UNIT
!= 0
771 || stores
.length () == 1)
774 stores
.qsort (sort_by_order
);
775 store_immediate_info
*info
;
777 /* Create a buffer of a size that is 2 times the number of bytes we're
778 storing. That way native_encode_expr can write power-of-2-sized
779 chunks without overrunning. */
780 buf_size
= 2 * ((bitregion_end
- bitregion_start
) / BITS_PER_UNIT
);
781 val
= XNEWVEC (unsigned char, 2 * buf_size
);
782 mask
= val
+ buf_size
;
783 memset (val
, 0, buf_size
);
784 memset (mask
, ~0U, buf_size
);
786 FOR_EACH_VEC_ELT (stores
, i
, info
)
788 unsigned int pos_in_buffer
= info
->bitpos
- bitregion_start
;
789 tree cst
= NULL_TREE
;
790 if (info
->ops
[0].val
&& info
->ops
[0].base_addr
== NULL_TREE
)
791 cst
= info
->ops
[0].val
;
792 else if (info
->ops
[1].val
&& info
->ops
[1].base_addr
== NULL_TREE
)
793 cst
= info
->ops
[1].val
;
796 ret
= encode_tree_to_bitpos (cst
, val
, info
->bitsize
,
797 pos_in_buffer
, buf_size
);
798 if (cst
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "After writing ");
803 print_generic_expr (dump_file
, cst
, 0);
804 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
805 " at position %d the merged region contains:\n",
806 info
->bitsize
, pos_in_buffer
);
807 dump_char_array (dump_file
, val
, buf_size
);
810 fprintf (dump_file
, "Failed to merge stores\n");
814 unsigned char *m
= mask
+ (pos_in_buffer
/ BITS_PER_UNIT
);
815 if (BYTES_BIG_ENDIAN
)
816 clear_bit_region_be (m
, (BITS_PER_UNIT
- 1
817 - (pos_in_buffer
% BITS_PER_UNIT
)),
820 clear_bit_region (m
, pos_in_buffer
% BITS_PER_UNIT
, info
->bitsize
);
825 /* Structure describing the store chain. */
827 struct imm_store_chain_info
829 /* Doubly-linked list that imposes an order on chain processing.
830 PNXP (prev's next pointer) points to the head of a list, or to
831 the next field in the previous chain in the list.
832 See pass_store_merging::m_stores_head for more rationale. */
833 imm_store_chain_info
*next
, **pnxp
;
835 auto_vec
<store_immediate_info
*> m_store_info
;
836 auto_vec
<merged_store_group
*> m_merged_store_groups
;
838 imm_store_chain_info (imm_store_chain_info
*&inspt
, tree b_a
)
839 : next (inspt
), pnxp (&inspt
), base_addr (b_a
)
844 gcc_checking_assert (pnxp
== next
->pnxp
);
848 ~imm_store_chain_info ()
853 gcc_checking_assert (&next
== next
->pnxp
);
857 bool terminate_and_process_chain ();
858 bool coalesce_immediate_stores ();
859 bool output_merged_store (merged_store_group
*);
860 bool output_merged_stores ();
863 const pass_data pass_data_tree_store_merging
= {
864 GIMPLE_PASS
, /* type */
865 "store-merging", /* name */
866 OPTGROUP_NONE
, /* optinfo_flags */
867 TV_GIMPLE_STORE_MERGING
, /* tv_id */
868 PROP_ssa
, /* properties_required */
869 0, /* properties_provided */
870 0, /* properties_destroyed */
871 0, /* todo_flags_start */
872 TODO_update_ssa
, /* todo_flags_finish */
875 class pass_store_merging
: public gimple_opt_pass
878 pass_store_merging (gcc::context
*ctxt
)
879 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
), m_stores_head ()
883 /* Pass not supported for PDP-endianness, nor for insane hosts
884 or target character sizes where native_{encode,interpret}_expr
885 doesn't work properly. */
889 return flag_store_merging
890 && WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
892 && BITS_PER_UNIT
== 8;
895 virtual unsigned int execute (function
*);
898 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
900 /* Form a doubly-linked stack of the elements of m_stores, so that
901 we can iterate over them in a predictable way. Using this order
902 avoids extraneous differences in the compiler output just because
903 of tree pointer variations (e.g. different chains end up in
904 different positions of m_stores, so they are handled in different
905 orders, so they allocate or release SSA names in different
906 orders, and when they get reused, subsequent passes end up
907 getting different SSA names, which may ultimately change
908 decisions when going out of SSA). */
909 imm_store_chain_info
*m_stores_head
;
911 void process_store (gimple
*);
912 bool terminate_and_process_all_chains ();
913 bool terminate_all_aliasing_chains (imm_store_chain_info
**,
915 bool terminate_and_release_chain (imm_store_chain_info
*);
916 }; // class pass_store_merging
918 /* Terminate and process all recorded chains. Return true if any changes
922 pass_store_merging::terminate_and_process_all_chains ()
925 while (m_stores_head
)
926 ret
|= terminate_and_release_chain (m_stores_head
);
927 gcc_assert (m_stores
.elements () == 0);
928 gcc_assert (m_stores_head
== NULL
);
933 /* Terminate all chains that are affected by the assignment to DEST, appearing
934 in statement STMT and ultimately points to the object BASE. Return true if
935 at least one aliasing chain was terminated. BASE and DEST are allowed to
936 be NULL_TREE. In that case the aliasing checks are performed on the whole
937 statement rather than a particular operand in it. VAR_OFFSET_P signifies
938 whether STMT represents a store to BASE offset by a variable amount.
939 If that is the case we have to terminate any chain anchored at BASE. */
942 pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
948 /* If the statement doesn't touch memory it can't alias. */
949 if (!gimple_vuse (stmt
))
952 /* Check if the assignment destination (BASE) is part of a store chain.
953 This is to catch non-constant stores to destinations that may be part
957 store_immediate_info
*info
;
959 FOR_EACH_VEC_ELT ((*chain_info
)->m_store_info
, i
, info
)
961 if (ref_maybe_used_by_stmt_p (stmt
, gimple_assign_lhs (info
->stmt
))
962 || stmt_may_clobber_ref_p (stmt
, gimple_assign_lhs (info
->stmt
)))
964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "stmt causes chain termination:\n");
967 print_gimple_stmt (dump_file
, stmt
, 0);
969 terminate_and_release_chain (*chain_info
);
976 /* Check for aliasing with all other store chains. */
977 for (imm_store_chain_info
*next
= m_stores_head
, *cur
= next
; cur
; cur
= next
)
981 /* We already checked all the stores in chain_info and terminated the
982 chain if necessary. Skip it here. */
983 if (chain_info
&& (*chain_info
) == cur
)
986 /* We can't use the base object here as that does not reliably exist.
987 Build a ao_ref from the base object address (if we know the
988 minimum and maximum offset and the maximum size we could improve
991 ao_ref_init_from_ptr_and_size (&chain_ref
, cur
->base_addr
, NULL_TREE
);
992 if (ref_maybe_used_by_stmt_p (stmt
, &chain_ref
)
993 || stmt_may_clobber_ref_p_1 (stmt
, &chain_ref
))
995 terminate_and_release_chain (cur
);
1003 /* Helper function. Terminate the recorded chain storing to base object
1004 BASE. Return true if the merging and output was successful. The m_stores
1005 entry is removed after the processing in any case. */
1008 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
1010 bool ret
= chain_info
->terminate_and_process_chain ();
1011 m_stores
.remove (chain_info
->base_addr
);
1016 /* Return true if stmts in between FIRST (inclusive) and LAST (exclusive)
1017 may clobber REF. FIRST and LAST must be in the same basic block and
1018 have non-NULL vdef. */
1021 stmts_may_clobber_ref_p (gimple
*first
, gimple
*last
, tree ref
)
1024 ao_ref_init (&r
, ref
);
1025 unsigned int count
= 0;
1026 tree vop
= gimple_vdef (last
);
1029 gcc_checking_assert (gimple_bb (first
) == gimple_bb (last
));
1032 stmt
= SSA_NAME_DEF_STMT (vop
);
1033 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
1035 /* Avoid quadratic compile time by bounding the number of checks
1037 if (++count
> MAX_STORE_ALIAS_CHECKS
)
1039 vop
= gimple_vuse (stmt
);
1041 while (stmt
!= first
);
1045 /* Return true if INFO->ops[IDX] is mergeable with the
1046 corresponding loads already in MERGED_STORE group.
1047 BASE_ADDR is the base address of the whole store group. */
1050 compatible_load_p (merged_store_group
*merged_store
,
1051 store_immediate_info
*info
,
1052 tree base_addr
, int idx
)
1054 store_immediate_info
*infof
= merged_store
->stores
[0];
1055 if (!info
->ops
[idx
].base_addr
1056 || (info
->ops
[idx
].bitpos
- infof
->ops
[idx
].bitpos
1057 != info
->bitpos
- infof
->bitpos
)
1058 || !operand_equal_p (info
->ops
[idx
].base_addr
,
1059 infof
->ops
[idx
].base_addr
, 0))
1062 store_immediate_info
*infol
= merged_store
->stores
.last ();
1063 tree load_vuse
= gimple_vuse (info
->ops
[idx
].stmt
);
1064 /* In this case all vuses should be the same, e.g.
1065 _1 = s.a; _2 = s.b; _3 = _1 | 1; t.a = _3; _4 = _2 | 2; t.b = _4;
1067 _1 = s.a; _2 = s.b; t.a = _1; t.b = _2;
1068 and we can emit the coalesced load next to any of those loads. */
1069 if (gimple_vuse (infof
->ops
[idx
].stmt
) == load_vuse
1070 && gimple_vuse (infol
->ops
[idx
].stmt
) == load_vuse
)
1073 /* Otherwise, at least for now require that the load has the same
1074 vuse as the store. See following examples. */
1075 if (gimple_vuse (info
->stmt
) != load_vuse
)
1078 if (gimple_vuse (infof
->stmt
) != gimple_vuse (infof
->ops
[idx
].stmt
)
1080 && gimple_vuse (infol
->stmt
) != gimple_vuse (infol
->ops
[idx
].stmt
)))
1083 /* If the load is from the same location as the store, already
1084 the construction of the immediate chain info guarantees no intervening
1085 stores, so no further checks are needed. Example:
1086 _1 = s.a; _2 = _1 & -7; s.a = _2; _3 = s.b; _4 = _3 & -7; s.b = _4; */
1087 if (info
->ops
[idx
].bitpos
== info
->bitpos
1088 && operand_equal_p (info
->ops
[idx
].base_addr
, base_addr
, 0))
1091 /* Otherwise, we need to punt if any of the loads can be clobbered by any
1092 of the stores in the group, or any other stores in between those.
1093 Previous calls to compatible_load_p ensured that for all the
1094 merged_store->stores IDX loads, no stmts starting with
1095 merged_store->first_stmt and ending right before merged_store->last_stmt
1096 clobbers those loads. */
1097 gimple
*first
= merged_store
->first_stmt
;
1098 gimple
*last
= merged_store
->last_stmt
;
1100 store_immediate_info
*infoc
;
1101 /* The stores are sorted by increasing store bitpos, so if info->stmt store
1102 comes before the so far first load, we'll be changing
1103 merged_store->first_stmt. In that case we need to give up if
1104 any of the earlier processed loads clobber with the stmts in the new
1106 if (info
->order
< merged_store
->first_order
)
1108 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
1109 if (stmts_may_clobber_ref_p (info
->stmt
, first
, infoc
->ops
[idx
].val
))
1113 /* Similarly, we could change merged_store->last_stmt, so ensure
1114 in that case no stmts in the new range clobber any of the earlier
1116 else if (info
->order
> merged_store
->last_order
)
1118 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
1119 if (stmts_may_clobber_ref_p (last
, info
->stmt
, infoc
->ops
[idx
].val
))
1123 /* And finally, we'd be adding a new load to the set, ensure it isn't
1124 clobbered in the new range. */
1125 if (stmts_may_clobber_ref_p (first
, last
, info
->ops
[idx
].val
))
1128 /* Otherwise, we are looking for:
1129 _1 = s.a; _2 = _1 ^ 15; t.a = _2; _3 = s.b; _4 = _3 ^ 15; t.b = _4;
1131 _1 = s.a; t.a = _1; _2 = s.b; t.b = _2; */
1135 /* Go through the candidate stores recorded in m_store_info and merge them
1136 into merged_store_group objects recorded into m_merged_store_groups
1137 representing the widened stores. Return true if coalescing was successful
1138 and the number of widened stores is fewer than the original number
1142 imm_store_chain_info::coalesce_immediate_stores ()
1144 /* Anything less can't be processed. */
1145 if (m_store_info
.length () < 2)
1148 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1149 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
1150 m_store_info
.length ());
1152 store_immediate_info
*info
;
1155 /* Order the stores by the bitposition they write to. */
1156 m_store_info
.qsort (sort_by_bitpos
);
1158 info
= m_store_info
[0];
1159 merged_store_group
*merged_store
= new merged_store_group (info
);
1161 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1165 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
1166 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
1167 i
, info
->bitsize
, info
->bitpos
);
1168 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
));
1169 fprintf (dump_file
, "\n------------\n");
1177 Overlapping stores. */
1178 unsigned HOST_WIDE_INT start
= info
->bitpos
;
1179 if (IN_RANGE (start
, merged_store
->start
,
1180 merged_store
->start
+ merged_store
->width
- 1))
1182 /* Only allow overlapping stores of constants. */
1183 if (info
->rhs_code
== INTEGER_CST
1184 && merged_store
->stores
[0]->rhs_code
== INTEGER_CST
)
1186 merged_store
->merge_overlapping (info
);
1190 /* |---store 1---||---store 2---|
1191 This store is consecutive to the previous one.
1192 Merge it into the current store group. There can be gaps in between
1193 the stores, but there can't be gaps in between bitregions. */
1194 else if (info
->bitregion_start
<= merged_store
->bitregion_end
1195 && info
->rhs_code
== merged_store
->stores
[0]->rhs_code
)
1197 store_immediate_info
*infof
= merged_store
->stores
[0];
1199 /* All the rhs_code ops that take 2 operands are commutative,
1200 swap the operands if it could make the operands compatible. */
1201 if (infof
->ops
[0].base_addr
1202 && infof
->ops
[1].base_addr
1203 && info
->ops
[0].base_addr
1204 && info
->ops
[1].base_addr
1205 && (info
->ops
[1].bitpos
- infof
->ops
[0].bitpos
1206 == info
->bitpos
- infof
->bitpos
)
1207 && operand_equal_p (info
->ops
[1].base_addr
,
1208 infof
->ops
[0].base_addr
, 0))
1209 std::swap (info
->ops
[0], info
->ops
[1]);
1210 if ((!infof
->ops
[0].base_addr
1211 || compatible_load_p (merged_store
, info
, base_addr
, 0))
1212 && (!infof
->ops
[1].base_addr
1213 || compatible_load_p (merged_store
, info
, base_addr
, 1)))
1215 merged_store
->merge_into (info
);
1220 /* |---store 1---| <gap> |---store 2---|.
1221 Gap between stores or the rhs not compatible. Start a new group. */
1223 /* Try to apply all the stores recorded for the group to determine
1224 the bitpattern they write and discard it if that fails.
1225 This will also reject single-store groups. */
1226 if (!merged_store
->apply_stores ())
1227 delete merged_store
;
1229 m_merged_store_groups
.safe_push (merged_store
);
1231 merged_store
= new merged_store_group (info
);
1234 /* Record or discard the last store group. */
1235 if (!merged_store
->apply_stores ())
1236 delete merged_store
;
1238 m_merged_store_groups
.safe_push (merged_store
);
1240 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
1242 = !m_merged_store_groups
.is_empty ()
1243 && m_merged_store_groups
.length () < m_store_info
.length ();
1245 if (success
&& dump_file
)
1246 fprintf (dump_file
, "Coalescing successful!\n"
1247 "Merged into %u stores\n",
1248 m_merged_store_groups
.length ());
1253 /* Return the type to use for the merged stores or loads described by STMTS.
1254 This is needed to get the alias sets right. If IS_LOAD, look for rhs,
1255 otherwise lhs. Additionally set *CLIQUEP and *BASEP to MR_DEPENDENCE_*
1256 of the MEM_REFs if any. */
1259 get_alias_type_for_stmts (vec
<gimple
*> &stmts
, bool is_load
,
1260 unsigned short *cliquep
, unsigned short *basep
)
1264 tree type
= NULL_TREE
;
1265 tree ret
= NULL_TREE
;
1269 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1271 tree ref
= is_load
? gimple_assign_rhs1 (stmt
)
1272 : gimple_assign_lhs (stmt
);
1273 tree type1
= reference_alias_ptr_type (ref
);
1274 tree base
= get_base_address (ref
);
1278 if (TREE_CODE (base
) == MEM_REF
)
1280 *cliquep
= MR_DEPENDENCE_CLIQUE (base
);
1281 *basep
= MR_DEPENDENCE_BASE (base
);
1286 if (!alias_ptr_types_compatible_p (type
, type1
))
1287 ret
= ptr_type_node
;
1288 if (TREE_CODE (base
) != MEM_REF
1289 || *cliquep
!= MR_DEPENDENCE_CLIQUE (base
)
1290 || *basep
!= MR_DEPENDENCE_BASE (base
))
1299 /* Return the location_t information we can find among the statements
1303 get_location_for_stmts (vec
<gimple
*> &stmts
)
1308 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1309 if (gimple_has_location (stmt
))
1310 return gimple_location (stmt
);
1312 return UNKNOWN_LOCATION
;
1315 /* Used to decribe a store resulting from splitting a wide store in smaller
1316 regularly-sized stores in split_group. */
1320 unsigned HOST_WIDE_INT bytepos
;
1321 unsigned HOST_WIDE_INT size
;
1322 unsigned HOST_WIDE_INT align
;
1323 auto_vec
<store_immediate_info
*> orig_stores
;
1324 /* True if there is a single orig stmt covering the whole split store. */
1326 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
1327 unsigned HOST_WIDE_INT
);
1330 /* Simple constructor. */
1332 split_store::split_store (unsigned HOST_WIDE_INT bp
,
1333 unsigned HOST_WIDE_INT sz
,
1334 unsigned HOST_WIDE_INT al
)
1335 : bytepos (bp
), size (sz
), align (al
), orig (false)
1337 orig_stores
.create (0);
1340 /* Record all stores in GROUP that write to the region starting at BITPOS and
1341 is of size BITSIZE. Record infos for such statements in STORES if
1342 non-NULL. The stores in GROUP must be sorted by bitposition. Return INFO
1343 if there is exactly one original store in the range. */
1345 static store_immediate_info
*
1346 find_constituent_stores (struct merged_store_group
*group
,
1347 vec
<store_immediate_info
*> *stores
,
1348 unsigned int *first
,
1349 unsigned HOST_WIDE_INT bitpos
,
1350 unsigned HOST_WIDE_INT bitsize
)
1352 store_immediate_info
*info
, *ret
= NULL
;
1354 bool second
= false;
1355 bool update_first
= true;
1356 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1357 for (i
= *first
; group
->stores
.iterate (i
, &info
); ++i
)
1359 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1360 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1361 if (stmt_end
<= bitpos
)
1363 /* BITPOS passed to this function never decreases from within the
1364 same split_group call, so optimize and don't scan info records
1365 which are known to end before or at BITPOS next time.
1366 Only do it if all stores before this one also pass this. */
1372 update_first
= false;
1374 /* The stores in GROUP are ordered by bitposition so if we're past
1375 the region for this group return early. */
1376 if (stmt_start
>= end
)
1381 stores
->safe_push (info
);
1396 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1397 vector (if non-NULL) with split_store structs describing the byte offset
1398 (from the base), the bit size and alignment of each store as well as the
1399 original statements involved in each such split group.
1400 This is to separate the splitting strategy from the statement
1401 building/emission/linking done in output_merged_store.
1402 Return number of new stores.
1403 If ALLOW_UNALIGNED_STORE is false, then all stores must be aligned.
1404 If ALLOW_UNALIGNED_LOAD is false, then all loads must be aligned.
1405 If SPLIT_STORES is NULL, it is just a dry run to count number of
1409 split_group (merged_store_group
*group
, bool allow_unaligned_store
,
1410 bool allow_unaligned_load
,
1411 vec
<struct split_store
*> *split_stores
)
1413 unsigned HOST_WIDE_INT pos
= group
->bitregion_start
;
1414 unsigned HOST_WIDE_INT size
= group
->bitregion_end
- pos
;
1415 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1416 unsigned HOST_WIDE_INT group_align
= group
->align
;
1417 unsigned HOST_WIDE_INT align_base
= group
->align_base
;
1418 unsigned HOST_WIDE_INT group_load_align
= group_align
;
1420 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1422 unsigned int ret
= 0, first
= 0;
1423 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1424 group
->stores
.qsort (sort_by_bitpos
);
1426 if (!allow_unaligned_load
)
1427 for (int i
= 0; i
< 2; ++i
)
1428 if (group
->load_align
[i
])
1429 group_load_align
= MIN (group_load_align
, group
->load_align
[i
]);
1433 if ((allow_unaligned_store
|| group_align
<= BITS_PER_UNIT
)
1434 && group
->mask
[try_pos
- bytepos
] == (unsigned char) ~0U)
1436 /* Skip padding bytes. */
1438 size
-= BITS_PER_UNIT
;
1442 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1443 unsigned int try_size
= MAX_STORE_BITSIZE
, nonmasked
;
1444 unsigned HOST_WIDE_INT align_bitpos
1445 = (try_bitpos
- align_base
) & (group_align
- 1);
1446 unsigned HOST_WIDE_INT align
= group_align
;
1448 align
= least_bit_hwi (align_bitpos
);
1449 if (!allow_unaligned_store
)
1450 try_size
= MIN (try_size
, align
);
1451 if (!allow_unaligned_load
)
1453 /* If we can't do or don't want to do unaligned stores
1454 as well as loads, we need to take the loads into account
1456 unsigned HOST_WIDE_INT load_align
= group_load_align
;
1457 align_bitpos
= (try_bitpos
- align_base
) & (load_align
- 1);
1459 load_align
= least_bit_hwi (align_bitpos
);
1460 for (int i
= 0; i
< 2; ++i
)
1461 if (group
->load_align
[i
])
1463 align_bitpos
= try_bitpos
- group
->stores
[0]->bitpos
;
1464 align_bitpos
+= group
->stores
[0]->ops
[i
].bitpos
;
1465 align_bitpos
-= group
->load_align_base
[i
];
1466 align_bitpos
&= (group_load_align
- 1);
1469 unsigned HOST_WIDE_INT a
= least_bit_hwi (align_bitpos
);
1470 load_align
= MIN (load_align
, a
);
1473 try_size
= MIN (try_size
, load_align
);
1475 store_immediate_info
*info
1476 = find_constituent_stores (group
, NULL
, &first
, try_bitpos
, try_size
);
1479 /* If there is just one original statement for the range, see if
1480 we can just reuse the original store which could be even larger
1482 unsigned HOST_WIDE_INT stmt_end
1483 = ROUND_UP (info
->bitpos
+ info
->bitsize
, BITS_PER_UNIT
);
1484 info
= find_constituent_stores (group
, NULL
, &first
, try_bitpos
,
1485 stmt_end
- try_bitpos
);
1486 if (info
&& info
->bitpos
>= try_bitpos
)
1488 try_size
= stmt_end
- try_bitpos
;
1493 /* Approximate store bitsize for the case when there are no padding
1495 while (try_size
> size
)
1497 /* Now look for whole padding bytes at the end of that bitsize. */
1498 for (nonmasked
= try_size
/ BITS_PER_UNIT
; nonmasked
> 0; --nonmasked
)
1499 if (group
->mask
[try_pos
- bytepos
+ nonmasked
- 1]
1500 != (unsigned char) ~0U)
1504 /* If entire try_size range is padding, skip it. */
1505 try_pos
+= try_size
/ BITS_PER_UNIT
;
1509 /* Otherwise try to decrease try_size if second half, last 3 quarters
1510 etc. are padding. */
1511 nonmasked
*= BITS_PER_UNIT
;
1512 while (nonmasked
<= try_size
/ 2)
1514 if (!allow_unaligned_store
&& group_align
> BITS_PER_UNIT
)
1516 /* Now look for whole padding bytes at the start of that bitsize. */
1517 unsigned int try_bytesize
= try_size
/ BITS_PER_UNIT
, masked
;
1518 for (masked
= 0; masked
< try_bytesize
; ++masked
)
1519 if (group
->mask
[try_pos
- bytepos
+ masked
] != (unsigned char) ~0U)
1521 masked
*= BITS_PER_UNIT
;
1522 gcc_assert (masked
< try_size
);
1523 if (masked
>= try_size
/ 2)
1525 while (masked
>= try_size
/ 2)
1528 try_pos
+= try_size
/ BITS_PER_UNIT
;
1532 /* Need to recompute the alignment, so just retry at the new
1543 struct split_store
*store
1544 = new split_store (try_pos
, try_size
, align
);
1545 info
= find_constituent_stores (group
, &store
->orig_stores
,
1546 &first
, try_bitpos
, try_size
);
1548 && info
->bitpos
>= try_bitpos
1549 && info
->bitpos
+ info
->bitsize
<= try_bitpos
+ try_size
)
1551 split_stores
->safe_push (store
);
1554 try_pos
+= try_size
/ BITS_PER_UNIT
;
1561 /* Given a merged store group GROUP output the widened version of it.
1562 The store chain is against the base object BASE.
1563 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1564 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1565 Make sure that the number of statements output is less than the number of
1566 original statements. If a better sequence is possible emit it and
1570 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1572 unsigned HOST_WIDE_INT start_byte_pos
1573 = group
->bitregion_start
/ BITS_PER_UNIT
;
1575 unsigned int orig_num_stmts
= group
->stores
.length ();
1576 if (orig_num_stmts
< 2)
1579 auto_vec
<struct split_store
*, 32> split_stores
;
1580 split_stores
.create (0);
1581 bool allow_unaligned_store
1582 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1583 bool allow_unaligned_load
= allow_unaligned_store
;
1584 if (allow_unaligned_store
)
1586 /* If unaligned stores are allowed, see how many stores we'd emit
1587 for unaligned and how many stores we'd emit for aligned stores.
1588 Only use unaligned stores if it allows fewer stores than aligned. */
1589 unsigned aligned_cnt
1590 = split_group (group
, false, allow_unaligned_load
, NULL
);
1591 unsigned unaligned_cnt
1592 = split_group (group
, true, allow_unaligned_load
, NULL
);
1593 if (aligned_cnt
<= unaligned_cnt
)
1594 allow_unaligned_store
= false;
1596 split_group (group
, allow_unaligned_store
, allow_unaligned_load
,
1599 if (split_stores
.length () >= orig_num_stmts
)
1601 /* We didn't manage to reduce the number of statements. Bail out. */
1602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1604 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1605 " Not profitable to emit new sequence.\n",
1611 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1612 gimple_seq seq
= NULL
;
1613 tree last_vdef
, new_vuse
;
1614 last_vdef
= gimple_vdef (group
->last_stmt
);
1615 new_vuse
= gimple_vuse (group
->last_stmt
);
1617 gimple
*stmt
= NULL
;
1618 split_store
*split_store
;
1620 auto_vec
<gimple
*, 32> orig_stmts
;
1621 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &seq
,
1622 is_gimple_mem_ref_addr
, NULL_TREE
);
1624 tree load_addr
[2] = { NULL_TREE
, NULL_TREE
};
1625 gimple_seq load_seq
[2] = { NULL
, NULL
};
1626 gimple_stmt_iterator load_gsi
[2] = { gsi_none (), gsi_none () };
1627 for (int j
= 0; j
< 2; ++j
)
1629 store_operand_info
&op
= group
->stores
[0]->ops
[j
];
1630 if (op
.base_addr
== NULL_TREE
)
1633 store_immediate_info
*infol
= group
->stores
.last ();
1634 if (gimple_vuse (op
.stmt
) == gimple_vuse (infol
->ops
[j
].stmt
))
1636 load_gsi
[j
] = gsi_for_stmt (op
.stmt
);
1638 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
1639 &load_seq
[j
], is_gimple_mem_ref_addr
,
1642 else if (operand_equal_p (base_addr
, op
.base_addr
, 0))
1643 load_addr
[j
] = addr
;
1646 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
1647 &seq
, is_gimple_mem_ref_addr
,
1651 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1653 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1654 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1655 unsigned HOST_WIDE_INT align
= split_store
->align
;
1658 if (split_store
->orig
)
1660 /* If there is just a single constituent store which covers
1661 the whole area, just reuse the lhs and rhs. */
1662 gimple
*orig_stmt
= split_store
->orig_stores
[0]->stmt
;
1663 dest
= gimple_assign_lhs (orig_stmt
);
1664 src
= gimple_assign_rhs1 (orig_stmt
);
1665 loc
= gimple_location (orig_stmt
);
1669 store_immediate_info
*info
;
1670 unsigned short clique
, base
;
1672 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1673 orig_stmts
.safe_push (info
->stmt
);
1675 = get_alias_type_for_stmts (orig_stmts
, false, &clique
, &base
);
1676 loc
= get_location_for_stmts (orig_stmts
);
1677 orig_stmts
.truncate (0);
1679 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1680 int_type
= build_aligned_type (int_type
, align
);
1681 dest
= fold_build2 (MEM_REF
, int_type
, addr
,
1682 build_int_cst (offset_type
, try_pos
));
1683 if (TREE_CODE (dest
) == MEM_REF
)
1685 MR_DEPENDENCE_CLIQUE (dest
) = clique
;
1686 MR_DEPENDENCE_BASE (dest
) = base
;
1690 = native_interpret_expr (int_type
,
1691 group
->mask
+ try_pos
- start_byte_pos
,
1696 j
< 1 + (split_store
->orig_stores
[0]->ops
[1].val
!= NULL_TREE
);
1699 store_operand_info
&op
= split_store
->orig_stores
[0]->ops
[j
];
1702 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1703 orig_stmts
.safe_push (info
->ops
[j
].stmt
);
1705 offset_type
= get_alias_type_for_stmts (orig_stmts
, true,
1707 location_t load_loc
= get_location_for_stmts (orig_stmts
);
1708 orig_stmts
.truncate (0);
1710 unsigned HOST_WIDE_INT load_align
= group
->load_align
[j
];
1711 unsigned HOST_WIDE_INT align_bitpos
1712 = (try_pos
* BITS_PER_UNIT
1713 - split_store
->orig_stores
[0]->bitpos
1714 + op
.bitpos
) & (load_align
- 1);
1716 load_align
= least_bit_hwi (align_bitpos
);
1719 = build_nonstandard_integer_type (try_size
, UNSIGNED
);
1721 = build_aligned_type (load_int_type
, load_align
);
1723 unsigned HOST_WIDE_INT load_pos
1724 = (try_pos
* BITS_PER_UNIT
1725 - split_store
->orig_stores
[0]->bitpos
1726 + op
.bitpos
) / BITS_PER_UNIT
;
1727 ops
[j
] = fold_build2 (MEM_REF
, load_int_type
, load_addr
[j
],
1728 build_int_cst (offset_type
, load_pos
));
1729 if (TREE_CODE (ops
[j
]) == MEM_REF
)
1731 MR_DEPENDENCE_CLIQUE (ops
[j
]) = clique
;
1732 MR_DEPENDENCE_BASE (ops
[j
]) = base
;
1734 if (!integer_zerop (mask
))
1735 /* The load might load some bits (that will be masked off
1736 later on) uninitialized, avoid -W*uninitialized
1737 warnings in that case. */
1738 TREE_NO_WARNING (ops
[j
]) = 1;
1740 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1742 gimple_set_location (stmt
, load_loc
);
1743 if (gsi_bb (load_gsi
[j
]))
1745 gimple_set_vuse (stmt
, gimple_vuse (op
.stmt
));
1746 gimple_seq_add_stmt_without_update (&load_seq
[j
], stmt
);
1750 gimple_set_vuse (stmt
, new_vuse
);
1751 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1753 ops
[j
] = gimple_assign_lhs (stmt
);
1756 ops
[j
] = native_interpret_expr (int_type
,
1757 group
->val
+ try_pos
1762 switch (split_store
->orig_stores
[0]->rhs_code
)
1767 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1769 tree rhs1
= gimple_assign_rhs1 (info
->stmt
);
1770 orig_stmts
.safe_push (SSA_NAME_DEF_STMT (rhs1
));
1773 bit_loc
= get_location_for_stmts (orig_stmts
);
1774 orig_stmts
.truncate (0);
1777 = gimple_build_assign (make_ssa_name (int_type
),
1778 split_store
->orig_stores
[0]->rhs_code
,
1780 gimple_set_location (stmt
, bit_loc
);
1781 /* If there is just one load and there is a separate
1782 load_seq[0], emit the bitwise op right after it. */
1783 if (load_addr
[1] == NULL_TREE
&& gsi_bb (load_gsi
[0]))
1784 gimple_seq_add_stmt_without_update (&load_seq
[0], stmt
);
1785 /* Otherwise, if at least one load is in seq, we need to
1786 emit the bitwise op right before the store. If there
1787 are two loads and are emitted somewhere else, it would
1788 be better to emit the bitwise op as early as possible;
1789 we don't track where that would be possible right now
1792 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1793 src
= gimple_assign_lhs (stmt
);
1800 if (!integer_zerop (mask
))
1802 tree tem
= make_ssa_name (int_type
);
1803 tree load_src
= unshare_expr (dest
);
1804 /* The load might load some or all bits uninitialized,
1805 avoid -W*uninitialized warnings in that case.
1806 As optimization, it would be nice if all the bits are
1807 provably uninitialized (no stores at all yet or previous
1808 store a CLOBBER) we'd optimize away the load and replace
1810 TREE_NO_WARNING (load_src
) = 1;
1811 stmt
= gimple_build_assign (tem
, load_src
);
1812 gimple_set_location (stmt
, loc
);
1813 gimple_set_vuse (stmt
, new_vuse
);
1814 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1816 /* FIXME: If there is a single chunk of zero bits in mask,
1817 perhaps use BIT_INSERT_EXPR instead? */
1818 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1819 BIT_AND_EXPR
, tem
, mask
);
1820 gimple_set_location (stmt
, loc
);
1821 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1822 tem
= gimple_assign_lhs (stmt
);
1824 if (TREE_CODE (src
) == INTEGER_CST
)
1825 src
= wide_int_to_tree (int_type
,
1826 wi::bit_and_not (wi::to_wide (src
),
1827 wi::to_wide (mask
)));
1831 = wide_int_to_tree (int_type
,
1832 wi::bit_not (wi::to_wide (mask
)));
1833 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1834 BIT_AND_EXPR
, src
, nmask
);
1835 gimple_set_location (stmt
, loc
);
1836 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1837 src
= gimple_assign_lhs (stmt
);
1839 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1840 BIT_IOR_EXPR
, tem
, src
);
1841 gimple_set_location (stmt
, loc
);
1842 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1843 src
= gimple_assign_lhs (stmt
);
1847 stmt
= gimple_build_assign (dest
, src
);
1848 gimple_set_location (stmt
, loc
);
1849 gimple_set_vuse (stmt
, new_vuse
);
1850 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1853 if (i
< split_stores
.length () - 1)
1854 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
1856 new_vdef
= last_vdef
;
1858 gimple_set_vdef (stmt
, new_vdef
);
1859 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
1860 new_vuse
= new_vdef
;
1863 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1870 "New sequence of %u stmts to replace old one of %u stmts\n",
1871 split_stores
.length (), orig_num_stmts
);
1872 if (dump_flags
& TDF_DETAILS
)
1873 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1875 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
1876 for (int j
= 0; j
< 2; ++j
)
1878 gsi_insert_seq_after (&load_gsi
[j
], load_seq
[j
], GSI_SAME_STMT
);
1883 /* Process the merged_store_group objects created in the coalescing phase.
1884 The stores are all against the base object BASE.
1885 Try to output the widened stores and delete the original statements if
1886 successful. Return true iff any changes were made. */
1889 imm_store_chain_info::output_merged_stores ()
1892 merged_store_group
*merged_store
;
1894 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
1896 if (output_merged_store (merged_store
))
1899 store_immediate_info
*store
;
1900 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
1902 gimple
*stmt
= store
->stmt
;
1903 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1904 gsi_remove (&gsi
, true);
1905 if (stmt
!= merged_store
->last_stmt
)
1907 unlink_stmt_vdef (stmt
);
1908 release_defs (stmt
);
1914 if (ret
&& dump_file
)
1915 fprintf (dump_file
, "Merging successful!\n");
1920 /* Coalesce the store_immediate_info objects recorded against the base object
1921 BASE in the first phase and output them.
1922 Delete the allocated structures.
1923 Return true if any changes were made. */
1926 imm_store_chain_info::terminate_and_process_chain ()
1928 /* Process store chain. */
1930 if (m_store_info
.length () > 1)
1932 ret
= coalesce_immediate_stores ();
1934 ret
= output_merged_stores ();
1937 /* Delete all the entries we allocated ourselves. */
1938 store_immediate_info
*info
;
1940 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1943 merged_store_group
*merged_info
;
1944 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
1950 /* Return true iff LHS is a destination potentially interesting for
1951 store merging. In practice these are the codes that get_inner_reference
1955 lhs_valid_for_store_merging_p (tree lhs
)
1957 tree_code code
= TREE_CODE (lhs
);
1959 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
1960 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
1966 /* Return true if the tree RHS is a constant we want to consider
1967 during store merging. In practice accept all codes that
1968 native_encode_expr accepts. */
1971 rhs_valid_for_store_merging_p (tree rhs
)
1973 return native_encode_expr (rhs
, NULL
,
1974 GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (rhs
)))) != 0;
1977 /* If MEM is a memory reference usable for store merging (either as
1978 store destination or for loads), return the non-NULL base_addr
1979 and set *PBITSIZE, *PBITPOS, *PBITREGION_START and *PBITREGION_END.
1980 Otherwise return NULL, *PBITPOS should be still valid even for that
1984 mem_valid_for_store_merging (tree mem
, unsigned HOST_WIDE_INT
*pbitsize
,
1985 unsigned HOST_WIDE_INT
*pbitpos
,
1986 unsigned HOST_WIDE_INT
*pbitregion_start
,
1987 unsigned HOST_WIDE_INT
*pbitregion_end
)
1989 HOST_WIDE_INT bitsize
;
1990 HOST_WIDE_INT bitpos
;
1991 unsigned HOST_WIDE_INT bitregion_start
= 0;
1992 unsigned HOST_WIDE_INT bitregion_end
= 0;
1994 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
1996 tree base_addr
= get_inner_reference (mem
, &bitsize
, &bitpos
, &offset
, &mode
,
1997 &unsignedp
, &reversep
, &volatilep
);
1998 *pbitsize
= bitsize
;
2002 if (TREE_CODE (mem
) == COMPONENT_REF
2003 && DECL_BIT_FIELD_TYPE (TREE_OPERAND (mem
, 1)))
2005 get_bit_range (&bitregion_start
, &bitregion_end
, mem
, &bitpos
, &offset
);
2013 /* We do not want to rewrite TARGET_MEM_REFs. */
2014 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
2016 /* In some cases get_inner_reference may return a
2017 MEM_REF [ptr + byteoffset]. For the purposes of this pass
2018 canonicalize the base_addr to MEM_REF [ptr] and take
2019 byteoffset into account in the bitpos. This occurs in
2020 PR 23684 and this way we can catch more chains. */
2021 else if (TREE_CODE (base_addr
) == MEM_REF
)
2023 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
2024 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2026 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
2028 bitpos
= bit_off
.to_shwi ();
2031 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2032 bit_off
+= bitregion_start
;
2033 if (wi::fits_uhwi_p (bit_off
))
2035 bitregion_start
= bit_off
.to_uhwi ();
2036 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2037 bit_off
+= bitregion_end
;
2038 if (wi::fits_uhwi_p (bit_off
))
2039 bitregion_end
= bit_off
.to_uhwi ();
2049 base_addr
= TREE_OPERAND (base_addr
, 0);
2051 /* get_inner_reference returns the base object, get at its
2057 base_addr
= build_fold_addr_expr (base_addr
);
2062 bitregion_start
= ROUND_DOWN (bitpos
, BITS_PER_UNIT
);
2063 bitregion_end
= ROUND_UP (bitpos
+ bitsize
, BITS_PER_UNIT
);
2066 if (offset
!= NULL_TREE
)
2068 /* If the access is variable offset then a base decl has to be
2069 address-taken to be able to emit pointer-based stores to it.
2070 ??? We might be able to get away with re-using the original
2071 base up to the first variable part and then wrapping that inside
2073 tree base
= get_base_address (base_addr
);
2075 || (DECL_P (base
) && ! TREE_ADDRESSABLE (base
)))
2078 base_addr
= build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base_addr
),
2082 *pbitsize
= bitsize
;
2084 *pbitregion_start
= bitregion_start
;
2085 *pbitregion_end
= bitregion_end
;
2089 /* Return true if STMT is a load that can be used for store merging.
2090 In that case fill in *OP. BITSIZE, BITPOS, BITREGION_START and
2091 BITREGION_END are properties of the corresponding store. */
2094 handled_load (gimple
*stmt
, store_operand_info
*op
,
2095 unsigned HOST_WIDE_INT bitsize
, unsigned HOST_WIDE_INT bitpos
,
2096 unsigned HOST_WIDE_INT bitregion_start
,
2097 unsigned HOST_WIDE_INT bitregion_end
)
2099 if (!is_gimple_assign (stmt
) || !gimple_vuse (stmt
))
2101 if (gimple_assign_load_p (stmt
)
2102 && !stmt_can_throw_internal (stmt
)
2103 && !gimple_has_volatile_ops (stmt
))
2105 tree mem
= gimple_assign_rhs1 (stmt
);
2107 = mem_valid_for_store_merging (mem
, &op
->bitsize
, &op
->bitpos
,
2108 &op
->bitregion_start
,
2109 &op
->bitregion_end
);
2110 if (op
->base_addr
!= NULL_TREE
2111 && op
->bitsize
== bitsize
2112 && ((op
->bitpos
- bitpos
) % BITS_PER_UNIT
) == 0
2113 && op
->bitpos
- op
->bitregion_start
>= bitpos
- bitregion_start
2114 && op
->bitregion_end
- op
->bitpos
>= bitregion_end
- bitpos
)
2124 /* Record the store STMT for store merging optimization if it can be
2128 pass_store_merging::process_store (gimple
*stmt
)
2130 tree lhs
= gimple_assign_lhs (stmt
);
2131 tree rhs
= gimple_assign_rhs1 (stmt
);
2132 unsigned HOST_WIDE_INT bitsize
, bitpos
;
2133 unsigned HOST_WIDE_INT bitregion_start
;
2134 unsigned HOST_WIDE_INT bitregion_end
;
2136 = mem_valid_for_store_merging (lhs
, &bitsize
, &bitpos
,
2137 &bitregion_start
, &bitregion_end
);
2141 bool invalid
= (base_addr
== NULL_TREE
2142 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
2143 && (TREE_CODE (rhs
) != INTEGER_CST
)));
2144 enum tree_code rhs_code
= ERROR_MARK
;
2145 store_operand_info ops
[2];
2148 else if (rhs_valid_for_store_merging_p (rhs
))
2150 rhs_code
= INTEGER_CST
;
2153 else if (TREE_CODE (rhs
) != SSA_NAME
|| !has_single_use (rhs
))
2157 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
), *def_stmt1
, *def_stmt2
;
2158 if (!is_gimple_assign (def_stmt
))
2160 else if (handled_load (def_stmt
, &ops
[0], bitsize
, bitpos
,
2161 bitregion_start
, bitregion_end
))
2164 switch ((rhs_code
= gimple_assign_rhs_code (def_stmt
)))
2170 rhs1
= gimple_assign_rhs1 (def_stmt
);
2171 rhs2
= gimple_assign_rhs2 (def_stmt
);
2173 if (TREE_CODE (rhs1
) != SSA_NAME
|| !has_single_use (rhs1
))
2175 def_stmt1
= SSA_NAME_DEF_STMT (rhs1
);
2176 if (!is_gimple_assign (def_stmt1
)
2177 || !handled_load (def_stmt1
, &ops
[0], bitsize
, bitpos
,
2178 bitregion_start
, bitregion_end
))
2180 if (rhs_valid_for_store_merging_p (rhs2
))
2182 else if (TREE_CODE (rhs2
) != SSA_NAME
|| !has_single_use (rhs2
))
2186 def_stmt2
= SSA_NAME_DEF_STMT (rhs2
);
2187 if (!is_gimple_assign (def_stmt2
))
2189 else if (!handled_load (def_stmt2
, &ops
[1], bitsize
, bitpos
,
2190 bitregion_start
, bitregion_end
))
2201 struct imm_store_chain_info
**chain_info
= NULL
;
2203 chain_info
= m_stores
.get (base_addr
);
2207 terminate_all_aliasing_chains (chain_info
, stmt
);
2211 store_immediate_info
*info
;
2214 unsigned int ord
= (*chain_info
)->m_store_info
.length ();
2215 info
= new store_immediate_info (bitsize
, bitpos
, bitregion_start
,
2216 bitregion_end
, stmt
, ord
, rhs_code
,
2218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 fprintf (dump_file
, "Recording immediate store from stmt:\n");
2221 print_gimple_stmt (dump_file
, stmt
, 0);
2223 (*chain_info
)->m_store_info
.safe_push (info
);
2224 /* If we reach the limit of stores to merge in a chain terminate and
2225 process the chain now. */
2226 if ((*chain_info
)->m_store_info
.length ()
2227 == (unsigned int) PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
2229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2231 "Reached maximum number of statements to merge:\n");
2232 terminate_and_release_chain (*chain_info
);
2237 /* Store aliases any existing chain? */
2238 terminate_all_aliasing_chains (chain_info
, stmt
);
2239 /* Start a new chain. */
2240 struct imm_store_chain_info
*new_chain
2241 = new imm_store_chain_info (m_stores_head
, base_addr
);
2242 info
= new store_immediate_info (bitsize
, bitpos
, bitregion_start
,
2243 bitregion_end
, stmt
, 0, rhs_code
,
2245 new_chain
->m_store_info
.safe_push (info
);
2246 m_stores
.put (base_addr
, new_chain
);
2247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2249 fprintf (dump_file
, "Starting new chain with statement:\n");
2250 print_gimple_stmt (dump_file
, stmt
, 0);
2251 fprintf (dump_file
, "The base object is:\n");
2252 print_generic_expr (dump_file
, base_addr
);
2253 fprintf (dump_file
, "\n");
2257 /* Entry point for the pass. Go over each basic block recording chains of
2258 immediate stores. Upon encountering a terminating statement (as defined
2259 by stmt_terminates_chain_p) process the recorded stores and emit the widened
2263 pass_store_merging::execute (function
*fun
)
2266 hash_set
<gimple
*> orig_stmts
;
2268 FOR_EACH_BB_FN (bb
, fun
)
2270 gimple_stmt_iterator gsi
;
2271 unsigned HOST_WIDE_INT num_statements
= 0;
2272 /* Record the original statements so that we can keep track of
2273 statements emitted in this pass and not re-process new
2275 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2277 if (is_gimple_debug (gsi_stmt (gsi
)))
2280 if (++num_statements
>= 2)
2284 if (num_statements
< 2)
2287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2288 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
2290 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2292 gimple
*stmt
= gsi_stmt (gsi
);
2294 if (is_gimple_debug (stmt
))
2297 if (gimple_has_volatile_ops (stmt
))
2299 /* Terminate all chains. */
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2301 fprintf (dump_file
, "Volatile access terminates "
2303 terminate_and_process_all_chains ();
2307 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
2308 && !stmt_can_throw_internal (stmt
)
2309 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
2310 process_store (stmt
);
2312 terminate_all_aliasing_chains (NULL
, stmt
);
2314 terminate_and_process_all_chains ();
2321 /* Construct and return a store merging pass object. */
2324 make_pass_store_merging (gcc::context
*ctxt
)
2326 return new pass_store_merging (ctxt
);
2331 namespace selftest
{
2333 /* Selftests for store merging helpers. */
2335 /* Assert that all elements of the byte arrays X and Y, both of length N
2339 verify_array_eq (unsigned char *x
, unsigned char *y
, unsigned int n
)
2341 for (unsigned int i
= 0; i
< n
; i
++)
2345 fprintf (stderr
, "Arrays do not match. X:\n");
2346 dump_char_array (stderr
, x
, n
);
2347 fprintf (stderr
, "Y:\n");
2348 dump_char_array (stderr
, y
, n
);
2350 ASSERT_EQ (x
[i
], y
[i
]);
2354 /* Test shift_bytes_in_array and that it carries bits across between
2358 verify_shift_bytes_in_array (void)
2361 00011111 | 11100000. */
2362 unsigned char orig
[2] = { 0xe0, 0x1f };
2363 unsigned char in
[2];
2364 memcpy (in
, orig
, sizeof orig
);
2366 unsigned char expected
[2] = { 0x80, 0x7f };
2367 shift_bytes_in_array (in
, sizeof (in
), 2);
2368 verify_array_eq (in
, expected
, sizeof (in
));
2370 memcpy (in
, orig
, sizeof orig
);
2371 memcpy (expected
, orig
, sizeof orig
);
2372 /* Check that shifting by zero doesn't change anything. */
2373 shift_bytes_in_array (in
, sizeof (in
), 0);
2374 verify_array_eq (in
, expected
, sizeof (in
));
2378 /* Test shift_bytes_in_array_right and that it carries bits across between
2382 verify_shift_bytes_in_array_right (void)
2385 00011111 | 11100000. */
2386 unsigned char orig
[2] = { 0x1f, 0xe0};
2387 unsigned char in
[2];
2388 memcpy (in
, orig
, sizeof orig
);
2389 unsigned char expected
[2] = { 0x07, 0xf8};
2390 shift_bytes_in_array_right (in
, sizeof (in
), 2);
2391 verify_array_eq (in
, expected
, sizeof (in
));
2393 memcpy (in
, orig
, sizeof orig
);
2394 memcpy (expected
, orig
, sizeof orig
);
2395 /* Check that shifting by zero doesn't change anything. */
2396 shift_bytes_in_array_right (in
, sizeof (in
), 0);
2397 verify_array_eq (in
, expected
, sizeof (in
));
2400 /* Test clear_bit_region that it clears exactly the bits asked and
2404 verify_clear_bit_region (void)
2406 /* Start with all bits set and test clearing various patterns in them. */
2407 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
2408 unsigned char in
[3];
2409 unsigned char expected
[3];
2410 memcpy (in
, orig
, sizeof in
);
2412 /* Check zeroing out all the bits. */
2413 clear_bit_region (in
, 0, 3 * BITS_PER_UNIT
);
2414 expected
[0] = expected
[1] = expected
[2] = 0;
2415 verify_array_eq (in
, expected
, sizeof in
);
2417 memcpy (in
, orig
, sizeof in
);
2418 /* Leave the first and last bits intact. */
2419 clear_bit_region (in
, 1, 3 * BITS_PER_UNIT
- 2);
2423 verify_array_eq (in
, expected
, sizeof in
);
2426 /* Test verify_clear_bit_region_be that it clears exactly the bits asked and
2430 verify_clear_bit_region_be (void)
2432 /* Start with all bits set and test clearing various patterns in them. */
2433 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
2434 unsigned char in
[3];
2435 unsigned char expected
[3];
2436 memcpy (in
, orig
, sizeof in
);
2438 /* Check zeroing out all the bits. */
2439 clear_bit_region_be (in
, BITS_PER_UNIT
- 1, 3 * BITS_PER_UNIT
);
2440 expected
[0] = expected
[1] = expected
[2] = 0;
2441 verify_array_eq (in
, expected
, sizeof in
);
2443 memcpy (in
, orig
, sizeof in
);
2444 /* Leave the first and last bits intact. */
2445 clear_bit_region_be (in
, BITS_PER_UNIT
- 2, 3 * BITS_PER_UNIT
- 2);
2449 verify_array_eq (in
, expected
, sizeof in
);
2453 /* Run all of the selftests within this file. */
2456 store_merging_c_tests (void)
2458 verify_shift_bytes_in_array ();
2459 verify_shift_bytes_in_array_right ();
2460 verify_clear_bit_region ();
2461 verify_clear_bit_region_be ();
2464 } // namespace selftest
2465 #endif /* CHECKING_P. */