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
;
187 store_operand_info ();
190 store_operand_info::store_operand_info ()
191 : val (NULL_TREE
), base_addr (NULL_TREE
), bitsize (0), bitpos (0),
192 bitregion_start (0), bitregion_end (0), stmt (NULL
), bit_not_p (false)
196 /* Struct recording the information about a single store of an immediate
197 to memory. These are created in the first phase and coalesced into
198 merged_store_group objects in the second phase. */
200 struct store_immediate_info
202 unsigned HOST_WIDE_INT bitsize
;
203 unsigned HOST_WIDE_INT bitpos
;
204 unsigned HOST_WIDE_INT bitregion_start
;
205 /* This is one past the last bit of the bit region. */
206 unsigned HOST_WIDE_INT bitregion_end
;
209 /* INTEGER_CST for constant stores, MEM_REF for memory copy or
210 BIT_*_EXPR for logical bitwise operation. */
211 enum tree_code rhs_code
;
213 /* Operands. For BIT_*_EXPR rhs_code both operands are used, otherwise
214 just the first one. */
215 store_operand_info ops
[2];
216 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
217 unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
218 gimple
*, unsigned int, enum tree_code
, bool,
219 const store_operand_info
&,
220 const store_operand_info
&);
223 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
224 unsigned HOST_WIDE_INT bp
,
225 unsigned HOST_WIDE_INT brs
,
226 unsigned HOST_WIDE_INT bre
,
229 enum tree_code rhscode
,
231 const store_operand_info
&op0r
,
232 const store_operand_info
&op1r
)
233 : bitsize (bs
), bitpos (bp
), bitregion_start (brs
), bitregion_end (bre
),
234 stmt (st
), order (ord
), rhs_code (rhscode
), bit_not_p (bitnotp
)
235 #if __cplusplus >= 201103L
246 /* Struct representing a group of stores to contiguous memory locations.
247 These are produced by the second phase (coalescing) and consumed in the
248 third phase that outputs the widened stores. */
250 struct merged_store_group
252 unsigned HOST_WIDE_INT start
;
253 unsigned HOST_WIDE_INT width
;
254 unsigned HOST_WIDE_INT bitregion_start
;
255 unsigned HOST_WIDE_INT bitregion_end
;
256 /* The size of the allocated memory for val and mask. */
257 unsigned HOST_WIDE_INT buf_size
;
258 unsigned HOST_WIDE_INT align_base
;
259 unsigned HOST_WIDE_INT load_align_base
[2];
262 unsigned int load_align
[2];
263 unsigned int first_order
;
264 unsigned int last_order
;
266 auto_vec
<store_immediate_info
*> stores
;
267 /* We record the first and last original statements in the sequence because
268 we'll need their vuse/vdef and replacement position. It's easier to keep
269 track of them separately as 'stores' is reordered by apply_stores. */
275 merged_store_group (store_immediate_info
*);
276 ~merged_store_group ();
277 void merge_into (store_immediate_info
*);
278 void merge_overlapping (store_immediate_info
*);
279 bool apply_stores ();
281 void do_merge (store_immediate_info
*);
284 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
287 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
292 for (unsigned int i
= 0; i
< len
; i
++)
293 fprintf (fd
, "%x ", ptr
[i
]);
297 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
298 bits between adjacent elements. AMNT should be within
301 00011111|11100000 << 2 = 01111111|10000000
302 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
305 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
310 unsigned char carry_over
= 0U;
311 unsigned char carry_mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- amnt
);
312 unsigned char clear_mask
= (~0U) << amnt
;
314 for (unsigned int i
= 0; i
< sz
; i
++)
316 unsigned prev_carry_over
= carry_over
;
317 carry_over
= (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
322 ptr
[i
] &= clear_mask
;
323 ptr
[i
] |= prev_carry_over
;
328 /* Like shift_bytes_in_array but for big-endian.
329 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
330 bits between adjacent elements. AMNT should be within
333 00011111|11100000 >> 2 = 00000111|11111000
334 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
337 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
343 unsigned char carry_over
= 0U;
344 unsigned char carry_mask
= ~(~0U << amnt
);
346 for (unsigned int i
= 0; i
< sz
; i
++)
348 unsigned prev_carry_over
= carry_over
;
349 carry_over
= ptr
[i
] & carry_mask
;
351 carry_over
<<= (unsigned char) BITS_PER_UNIT
- amnt
;
353 ptr
[i
] |= prev_carry_over
;
357 /* Clear out LEN bits starting from bit START in the byte array
358 PTR. This clears the bits to the *right* from START.
359 START must be within [0, BITS_PER_UNIT) and counts starting from
360 the least significant bit. */
363 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
368 /* Clear len bits to the right of start. */
369 else if (len
<= start
+ 1)
371 unsigned char mask
= (~(~0U << len
));
372 mask
= mask
<< (start
+ 1U - len
);
375 else if (start
!= BITS_PER_UNIT
- 1)
377 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
378 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
379 len
- (start
% BITS_PER_UNIT
) - 1);
381 else if (start
== BITS_PER_UNIT
- 1
382 && len
> BITS_PER_UNIT
)
384 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
385 memset (ptr
, 0, nbytes
);
386 if (len
% BITS_PER_UNIT
!= 0)
387 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
388 len
% BITS_PER_UNIT
);
394 /* In the byte array PTR clear the bit region starting at bit
395 START and is LEN bits wide.
396 For regions spanning multiple bytes do this recursively until we reach
397 zero LEN or a region contained within a single byte. */
400 clear_bit_region (unsigned char *ptr
, unsigned int start
,
403 /* Degenerate base case. */
406 else if (start
>= BITS_PER_UNIT
)
407 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
408 /* Second base case. */
409 else if ((start
+ len
) <= BITS_PER_UNIT
)
411 unsigned char mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- len
);
412 mask
>>= BITS_PER_UNIT
- (start
+ len
);
418 /* Clear most significant bits in a byte and proceed with the next byte. */
421 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
422 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
));
424 /* Whole bytes need to be cleared. */
425 else if (start
== 0 && len
> BITS_PER_UNIT
)
427 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
428 /* We could recurse on each byte but we clear whole bytes, so a simple
430 memset (ptr
, '\0', nbytes
);
431 /* Clear the remaining sub-byte region if there is one. */
432 if (len
% BITS_PER_UNIT
!= 0)
433 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
439 /* Write BITLEN bits of EXPR to the byte array PTR at
440 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
441 Return true if the operation succeeded. */
444 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
445 unsigned int total_bytes
)
447 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
449 bool sub_byte_op_p
= ((bitlen
% BITS_PER_UNIT
)
450 || (bitpos
% BITS_PER_UNIT
)
451 || !int_mode_for_size (bitlen
, 0).exists ());
454 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
) != 0;
457 We are writing a non byte-sized quantity or at a position that is not
459 |--------|--------|--------| ptr + first_byte
461 xxx xxxxxxxx xxx< bp>
464 First native_encode_expr EXPR into a temporary buffer and shift each
465 byte in the buffer by 'bp' (carrying the bits over as necessary).
466 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
467 <------bitlen---->< bp>
468 Then we clear the destination bits:
469 |---00000|00000000|000-----| ptr + first_byte
470 <-------bitlen--->< bp>
472 Finally we ORR the bytes of the shifted EXPR into the cleared region:
473 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
476 We are writing a non byte-sized quantity or at a position that is not
478 ptr + first_byte |--------|--------|--------|
480 <bp >xxx xxxxxxxx xxx
483 First native_encode_expr EXPR into a temporary buffer and shift each
484 byte in the buffer to the right by (carrying the bits over as necessary).
485 We shift by as much as needed to align the most significant bit of EXPR
487 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
488 <---bitlen----> <bp ><-----bitlen----->
489 Then we clear the destination bits:
490 ptr + first_byte |-----000||00000000||00000---|
491 <bp ><-------bitlen----->
493 Finally we ORR the bytes of the shifted EXPR into the cleared region:
494 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
495 The awkwardness comes from the fact that bitpos is counted from the
496 most significant bit of a byte. */
498 /* We must be dealing with fixed-size data at this point, since the
499 total size is also fixed. */
500 fixed_size_mode mode
= as_a
<fixed_size_mode
> (TYPE_MODE (TREE_TYPE (expr
)));
501 /* Allocate an extra byte so that we have space to shift into. */
502 unsigned int byte_size
= GET_MODE_SIZE (mode
) + 1;
503 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
504 memset (tmpbuf
, '\0', byte_size
);
505 /* The store detection code should only have allowed constants that are
506 accepted by native_encode_expr. */
507 if (native_encode_expr (expr
, tmpbuf
, byte_size
- 1) == 0)
510 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
511 bytes to write. This means it can write more than
512 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
513 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
514 bitlen and zero out the bits that are not relevant as well (that may
515 contain a sign bit due to sign-extension). */
517 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
518 /* On big-endian the padding is at the 'front' so just skip the initial
520 if (BYTES_BIG_ENDIAN
)
523 byte_size
-= padding
;
525 if (bitlen
% BITS_PER_UNIT
!= 0)
527 if (BYTES_BIG_ENDIAN
)
528 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
529 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
531 clear_bit_region (tmpbuf
, bitlen
,
532 byte_size
* BITS_PER_UNIT
- bitlen
);
534 /* Left shifting relies on the last byte being clear if bitlen is
535 a multiple of BITS_PER_UNIT, which might not be clear if
536 there are padding bytes. */
537 else if (!BYTES_BIG_ENDIAN
)
538 tmpbuf
[byte_size
- 1] = '\0';
540 /* Clear the bit region in PTR where the bits from TMPBUF will be
542 if (BYTES_BIG_ENDIAN
)
543 clear_bit_region_be (ptr
+ first_byte
,
544 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
546 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
549 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
550 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
552 bool skip_byte
= false;
553 if (BYTES_BIG_ENDIAN
)
555 /* BITPOS and BITLEN are exactly aligned and no shifting
557 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
558 || (bitpos_mod
== 0 && bitlen_mod
== 0))
562 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
563 of the value until it aligns with 'bp' in the next byte over. */
564 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
566 shift_amnt
= bitlen_mod
+ bitpos_mod
;
567 skip_byte
= bitlen_mod
!= 0;
572 Shift the value right within the same byte so it aligns with 'bp'. */
574 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
577 shift_amnt
= bitpos
% BITS_PER_UNIT
;
579 /* Create the shifted version of EXPR. */
580 if (!BYTES_BIG_ENDIAN
)
582 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
588 gcc_assert (BYTES_BIG_ENDIAN
);
589 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
590 /* If shifting right forced us to move into the next byte skip the now
599 /* Insert the bits from TMPBUF. */
600 for (unsigned int i
= 0; i
< byte_size
; i
++)
601 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
606 /* Sorting function for store_immediate_info objects.
607 Sorts them by bitposition. */
610 sort_by_bitpos (const void *x
, const void *y
)
612 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
613 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
615 if ((*tmp
)->bitpos
< (*tmp2
)->bitpos
)
617 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
620 /* If they are the same let's use the order which is guaranteed to
622 return (*tmp
)->order
- (*tmp2
)->order
;
625 /* Sorting function for store_immediate_info objects.
626 Sorts them by the order field. */
629 sort_by_order (const void *x
, const void *y
)
631 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
632 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
634 if ((*tmp
)->order
< (*tmp2
)->order
)
636 else if ((*tmp
)->order
> (*tmp2
)->order
)
642 /* Initialize a merged_store_group object from a store_immediate_info
645 merged_store_group::merged_store_group (store_immediate_info
*info
)
647 start
= info
->bitpos
;
648 width
= info
->bitsize
;
649 bitregion_start
= info
->bitregion_start
;
650 bitregion_end
= info
->bitregion_end
;
651 /* VAL has memory allocated for it in apply_stores once the group
652 width has been finalized. */
655 unsigned HOST_WIDE_INT align_bitpos
= 0;
656 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
657 &align
, &align_bitpos
);
658 align_base
= start
- align_bitpos
;
659 for (int i
= 0; i
< 2; ++i
)
661 store_operand_info
&op
= info
->ops
[i
];
662 if (op
.base_addr
== NULL_TREE
)
665 load_align_base
[i
] = 0;
669 get_object_alignment_1 (op
.val
, &load_align
[i
], &align_bitpos
);
670 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
674 stores
.safe_push (info
);
675 last_stmt
= info
->stmt
;
676 last_order
= info
->order
;
677 first_stmt
= last_stmt
;
678 first_order
= last_order
;
682 merged_store_group::~merged_store_group ()
688 /* Helper method for merge_into and merge_overlapping to do
691 merged_store_group::do_merge (store_immediate_info
*info
)
693 bitregion_start
= MIN (bitregion_start
, info
->bitregion_start
);
694 bitregion_end
= MAX (bitregion_end
, info
->bitregion_end
);
696 unsigned int this_align
;
697 unsigned HOST_WIDE_INT align_bitpos
= 0;
698 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
699 &this_align
, &align_bitpos
);
700 if (this_align
> align
)
703 align_base
= info
->bitpos
- align_bitpos
;
705 for (int i
= 0; i
< 2; ++i
)
707 store_operand_info
&op
= info
->ops
[i
];
711 get_object_alignment_1 (op
.val
, &this_align
, &align_bitpos
);
712 if (this_align
> load_align
[i
])
714 load_align
[i
] = this_align
;
715 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
719 gimple
*stmt
= info
->stmt
;
720 stores
.safe_push (info
);
721 if (info
->order
> last_order
)
723 last_order
= info
->order
;
726 else if (info
->order
< first_order
)
728 first_order
= info
->order
;
733 /* Merge a store recorded by INFO into this merged store.
734 The store is not overlapping with the existing recorded
738 merged_store_group::merge_into (store_immediate_info
*info
)
740 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
741 /* Make sure we're inserting in the position we think we're inserting. */
742 gcc_assert (info
->bitpos
>= start
+ width
743 && info
->bitregion_start
<= bitregion_end
);
749 /* Merge a store described by INFO into this merged store.
750 INFO overlaps in some way with the current store (i.e. it's not contiguous
751 which is handled by merged_store_group::merge_into). */
754 merged_store_group::merge_overlapping (store_immediate_info
*info
)
756 /* If the store extends the size of the group, extend the width. */
757 if (info
->bitpos
+ info
->bitsize
> start
+ width
)
758 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
763 /* Go through all the recorded stores in this group in program order and
764 apply their values to the VAL byte array to create the final merged
765 value. Return true if the operation succeeded. */
768 merged_store_group::apply_stores ()
770 /* Make sure we have more than one store in the group, otherwise we cannot
772 if (bitregion_start
% BITS_PER_UNIT
!= 0
773 || bitregion_end
% BITS_PER_UNIT
!= 0
774 || stores
.length () == 1)
777 stores
.qsort (sort_by_order
);
778 store_immediate_info
*info
;
780 /* Create a buffer of a size that is 2 times the number of bytes we're
781 storing. That way native_encode_expr can write power-of-2-sized
782 chunks without overrunning. */
783 buf_size
= 2 * ((bitregion_end
- bitregion_start
) / BITS_PER_UNIT
);
784 val
= XNEWVEC (unsigned char, 2 * buf_size
);
785 mask
= val
+ buf_size
;
786 memset (val
, 0, buf_size
);
787 memset (mask
, ~0U, buf_size
);
789 FOR_EACH_VEC_ELT (stores
, i
, info
)
791 unsigned int pos_in_buffer
= info
->bitpos
- bitregion_start
;
792 tree cst
= NULL_TREE
;
793 if (info
->ops
[0].val
&& info
->ops
[0].base_addr
== NULL_TREE
)
794 cst
= info
->ops
[0].val
;
795 else if (info
->ops
[1].val
&& info
->ops
[1].base_addr
== NULL_TREE
)
796 cst
= info
->ops
[1].val
;
799 ret
= encode_tree_to_bitpos (cst
, val
, info
->bitsize
,
800 pos_in_buffer
, buf_size
);
801 if (cst
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
805 fprintf (dump_file
, "After writing ");
806 print_generic_expr (dump_file
, cst
, 0);
807 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
808 " at position %d the merged region contains:\n",
809 info
->bitsize
, pos_in_buffer
);
810 dump_char_array (dump_file
, val
, buf_size
);
813 fprintf (dump_file
, "Failed to merge stores\n");
817 unsigned char *m
= mask
+ (pos_in_buffer
/ BITS_PER_UNIT
);
818 if (BYTES_BIG_ENDIAN
)
819 clear_bit_region_be (m
, (BITS_PER_UNIT
- 1
820 - (pos_in_buffer
% BITS_PER_UNIT
)),
823 clear_bit_region (m
, pos_in_buffer
% BITS_PER_UNIT
, info
->bitsize
);
828 /* Structure describing the store chain. */
830 struct imm_store_chain_info
832 /* Doubly-linked list that imposes an order on chain processing.
833 PNXP (prev's next pointer) points to the head of a list, or to
834 the next field in the previous chain in the list.
835 See pass_store_merging::m_stores_head for more rationale. */
836 imm_store_chain_info
*next
, **pnxp
;
838 auto_vec
<store_immediate_info
*> m_store_info
;
839 auto_vec
<merged_store_group
*> m_merged_store_groups
;
841 imm_store_chain_info (imm_store_chain_info
*&inspt
, tree b_a
)
842 : next (inspt
), pnxp (&inspt
), base_addr (b_a
)
847 gcc_checking_assert (pnxp
== next
->pnxp
);
851 ~imm_store_chain_info ()
856 gcc_checking_assert (&next
== next
->pnxp
);
860 bool terminate_and_process_chain ();
861 bool coalesce_immediate_stores ();
862 bool output_merged_store (merged_store_group
*);
863 bool output_merged_stores ();
866 const pass_data pass_data_tree_store_merging
= {
867 GIMPLE_PASS
, /* type */
868 "store-merging", /* name */
869 OPTGROUP_NONE
, /* optinfo_flags */
870 TV_GIMPLE_STORE_MERGING
, /* tv_id */
871 PROP_ssa
, /* properties_required */
872 0, /* properties_provided */
873 0, /* properties_destroyed */
874 0, /* todo_flags_start */
875 TODO_update_ssa
, /* todo_flags_finish */
878 class pass_store_merging
: public gimple_opt_pass
881 pass_store_merging (gcc::context
*ctxt
)
882 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
), m_stores_head ()
886 /* Pass not supported for PDP-endianness, nor for insane hosts
887 or target character sizes where native_{encode,interpret}_expr
888 doesn't work properly. */
892 return flag_store_merging
893 && WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
895 && BITS_PER_UNIT
== 8;
898 virtual unsigned int execute (function
*);
901 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
903 /* Form a doubly-linked stack of the elements of m_stores, so that
904 we can iterate over them in a predictable way. Using this order
905 avoids extraneous differences in the compiler output just because
906 of tree pointer variations (e.g. different chains end up in
907 different positions of m_stores, so they are handled in different
908 orders, so they allocate or release SSA names in different
909 orders, and when they get reused, subsequent passes end up
910 getting different SSA names, which may ultimately change
911 decisions when going out of SSA). */
912 imm_store_chain_info
*m_stores_head
;
914 void process_store (gimple
*);
915 bool terminate_and_process_all_chains ();
916 bool terminate_all_aliasing_chains (imm_store_chain_info
**, gimple
*);
917 bool terminate_and_release_chain (imm_store_chain_info
*);
918 }; // class pass_store_merging
920 /* Terminate and process all recorded chains. Return true if any changes
924 pass_store_merging::terminate_and_process_all_chains ()
927 while (m_stores_head
)
928 ret
|= terminate_and_release_chain (m_stores_head
);
929 gcc_assert (m_stores
.elements () == 0);
930 gcc_assert (m_stores_head
== NULL
);
935 /* Terminate all chains that are affected by the statement STMT.
936 CHAIN_INFO is the chain we should ignore from the checks if
940 pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
946 /* If the statement doesn't touch memory it can't alias. */
947 if (!gimple_vuse (stmt
))
950 tree store_lhs
= gimple_store_p (stmt
) ? gimple_get_lhs (stmt
) : NULL_TREE
;
951 for (imm_store_chain_info
*next
= m_stores_head
, *cur
= next
; cur
; cur
= next
)
955 /* We already checked all the stores in chain_info and terminated the
956 chain if necessary. Skip it here. */
957 if (chain_info
&& *chain_info
== cur
)
960 store_immediate_info
*info
;
962 FOR_EACH_VEC_ELT (cur
->m_store_info
, i
, info
)
964 tree lhs
= gimple_assign_lhs (info
->stmt
);
965 if (ref_maybe_used_by_stmt_p (stmt
, lhs
)
966 || stmt_may_clobber_ref_p (stmt
, lhs
)
967 || (store_lhs
&& refs_output_dependent_p (store_lhs
, lhs
)))
969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
971 fprintf (dump_file
, "stmt causes chain termination:\n");
972 print_gimple_stmt (dump_file
, stmt
, 0);
974 terminate_and_release_chain (cur
);
984 /* Helper function. Terminate the recorded chain storing to base object
985 BASE. Return true if the merging and output was successful. The m_stores
986 entry is removed after the processing in any case. */
989 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
991 bool ret
= chain_info
->terminate_and_process_chain ();
992 m_stores
.remove (chain_info
->base_addr
);
997 /* Return true if stmts in between FIRST (inclusive) and LAST (exclusive)
998 may clobber REF. FIRST and LAST must be in the same basic block and
999 have non-NULL vdef. */
1002 stmts_may_clobber_ref_p (gimple
*first
, gimple
*last
, tree ref
)
1005 ao_ref_init (&r
, ref
);
1006 unsigned int count
= 0;
1007 tree vop
= gimple_vdef (last
);
1010 gcc_checking_assert (gimple_bb (first
) == gimple_bb (last
));
1013 stmt
= SSA_NAME_DEF_STMT (vop
);
1014 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
1016 /* Avoid quadratic compile time by bounding the number of checks
1018 if (++count
> MAX_STORE_ALIAS_CHECKS
)
1020 vop
= gimple_vuse (stmt
);
1022 while (stmt
!= first
);
1026 /* Return true if INFO->ops[IDX] is mergeable with the
1027 corresponding loads already in MERGED_STORE group.
1028 BASE_ADDR is the base address of the whole store group. */
1031 compatible_load_p (merged_store_group
*merged_store
,
1032 store_immediate_info
*info
,
1033 tree base_addr
, int idx
)
1035 store_immediate_info
*infof
= merged_store
->stores
[0];
1036 if (!info
->ops
[idx
].base_addr
1037 || info
->ops
[idx
].bit_not_p
!= infof
->ops
[idx
].bit_not_p
1038 || (info
->ops
[idx
].bitpos
- infof
->ops
[idx
].bitpos
1039 != info
->bitpos
- infof
->bitpos
)
1040 || !operand_equal_p (info
->ops
[idx
].base_addr
,
1041 infof
->ops
[idx
].base_addr
, 0))
1044 store_immediate_info
*infol
= merged_store
->stores
.last ();
1045 tree load_vuse
= gimple_vuse (info
->ops
[idx
].stmt
);
1046 /* In this case all vuses should be the same, e.g.
1047 _1 = s.a; _2 = s.b; _3 = _1 | 1; t.a = _3; _4 = _2 | 2; t.b = _4;
1049 _1 = s.a; _2 = s.b; t.a = _1; t.b = _2;
1050 and we can emit the coalesced load next to any of those loads. */
1051 if (gimple_vuse (infof
->ops
[idx
].stmt
) == load_vuse
1052 && gimple_vuse (infol
->ops
[idx
].stmt
) == load_vuse
)
1055 /* Otherwise, at least for now require that the load has the same
1056 vuse as the store. See following examples. */
1057 if (gimple_vuse (info
->stmt
) != load_vuse
)
1060 if (gimple_vuse (infof
->stmt
) != gimple_vuse (infof
->ops
[idx
].stmt
)
1062 && gimple_vuse (infol
->stmt
) != gimple_vuse (infol
->ops
[idx
].stmt
)))
1065 /* If the load is from the same location as the store, already
1066 the construction of the immediate chain info guarantees no intervening
1067 stores, so no further checks are needed. Example:
1068 _1 = s.a; _2 = _1 & -7; s.a = _2; _3 = s.b; _4 = _3 & -7; s.b = _4; */
1069 if (info
->ops
[idx
].bitpos
== info
->bitpos
1070 && operand_equal_p (info
->ops
[idx
].base_addr
, base_addr
, 0))
1073 /* Otherwise, we need to punt if any of the loads can be clobbered by any
1074 of the stores in the group, or any other stores in between those.
1075 Previous calls to compatible_load_p ensured that for all the
1076 merged_store->stores IDX loads, no stmts starting with
1077 merged_store->first_stmt and ending right before merged_store->last_stmt
1078 clobbers those loads. */
1079 gimple
*first
= merged_store
->first_stmt
;
1080 gimple
*last
= merged_store
->last_stmt
;
1082 store_immediate_info
*infoc
;
1083 /* The stores are sorted by increasing store bitpos, so if info->stmt store
1084 comes before the so far first load, we'll be changing
1085 merged_store->first_stmt. In that case we need to give up if
1086 any of the earlier processed loads clobber with the stmts in the new
1088 if (info
->order
< merged_store
->first_order
)
1090 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
1091 if (stmts_may_clobber_ref_p (info
->stmt
, first
, infoc
->ops
[idx
].val
))
1095 /* Similarly, we could change merged_store->last_stmt, so ensure
1096 in that case no stmts in the new range clobber any of the earlier
1098 else if (info
->order
> merged_store
->last_order
)
1100 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
1101 if (stmts_may_clobber_ref_p (last
, info
->stmt
, infoc
->ops
[idx
].val
))
1105 /* And finally, we'd be adding a new load to the set, ensure it isn't
1106 clobbered in the new range. */
1107 if (stmts_may_clobber_ref_p (first
, last
, info
->ops
[idx
].val
))
1110 /* Otherwise, we are looking for:
1111 _1 = s.a; _2 = _1 ^ 15; t.a = _2; _3 = s.b; _4 = _3 ^ 15; t.b = _4;
1113 _1 = s.a; t.a = _1; _2 = s.b; t.b = _2; */
1117 /* Go through the candidate stores recorded in m_store_info and merge them
1118 into merged_store_group objects recorded into m_merged_store_groups
1119 representing the widened stores. Return true if coalescing was successful
1120 and the number of widened stores is fewer than the original number
1124 imm_store_chain_info::coalesce_immediate_stores ()
1126 /* Anything less can't be processed. */
1127 if (m_store_info
.length () < 2)
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
1132 m_store_info
.length ());
1134 store_immediate_info
*info
;
1137 /* Order the stores by the bitposition they write to. */
1138 m_store_info
.qsort (sort_by_bitpos
);
1140 info
= m_store_info
[0];
1141 merged_store_group
*merged_store
= new merged_store_group (info
);
1143 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1147 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
1148 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
1149 i
, info
->bitsize
, info
->bitpos
);
1150 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
));
1151 fprintf (dump_file
, "\n------------\n");
1159 Overlapping stores. */
1160 unsigned HOST_WIDE_INT start
= info
->bitpos
;
1161 if (IN_RANGE (start
, merged_store
->start
,
1162 merged_store
->start
+ merged_store
->width
- 1))
1164 /* Only allow overlapping stores of constants. */
1165 if (info
->rhs_code
== INTEGER_CST
1166 && merged_store
->stores
[0]->rhs_code
== INTEGER_CST
)
1168 merged_store
->merge_overlapping (info
);
1172 /* |---store 1---||---store 2---|
1173 This store is consecutive to the previous one.
1174 Merge it into the current store group. There can be gaps in between
1175 the stores, but there can't be gaps in between bitregions. */
1176 else if (info
->bitregion_start
<= merged_store
->bitregion_end
1177 && info
->rhs_code
== merged_store
->stores
[0]->rhs_code
1178 && info
->bit_not_p
== merged_store
->stores
[0]->bit_not_p
)
1180 store_immediate_info
*infof
= merged_store
->stores
[0];
1182 /* All the rhs_code ops that take 2 operands are commutative,
1183 swap the operands if it could make the operands compatible. */
1184 if (infof
->ops
[0].base_addr
1185 && infof
->ops
[1].base_addr
1186 && info
->ops
[0].base_addr
1187 && info
->ops
[1].base_addr
1188 && (info
->ops
[1].bitpos
- infof
->ops
[0].bitpos
1189 == info
->bitpos
- infof
->bitpos
)
1190 && operand_equal_p (info
->ops
[1].base_addr
,
1191 infof
->ops
[0].base_addr
, 0))
1192 std::swap (info
->ops
[0], info
->ops
[1]);
1193 if ((!infof
->ops
[0].base_addr
1194 || compatible_load_p (merged_store
, info
, base_addr
, 0))
1195 && (!infof
->ops
[1].base_addr
1196 || compatible_load_p (merged_store
, info
, base_addr
, 1)))
1198 merged_store
->merge_into (info
);
1203 /* |---store 1---| <gap> |---store 2---|.
1204 Gap between stores or the rhs not compatible. Start a new group. */
1206 /* Try to apply all the stores recorded for the group to determine
1207 the bitpattern they write and discard it if that fails.
1208 This will also reject single-store groups. */
1209 if (!merged_store
->apply_stores ())
1210 delete merged_store
;
1212 m_merged_store_groups
.safe_push (merged_store
);
1214 merged_store
= new merged_store_group (info
);
1217 /* Record or discard the last store group. */
1218 if (!merged_store
->apply_stores ())
1219 delete merged_store
;
1221 m_merged_store_groups
.safe_push (merged_store
);
1223 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
1225 = !m_merged_store_groups
.is_empty ()
1226 && m_merged_store_groups
.length () < m_store_info
.length ();
1228 if (success
&& dump_file
)
1229 fprintf (dump_file
, "Coalescing successful!\n"
1230 "Merged into %u stores\n",
1231 m_merged_store_groups
.length ());
1236 /* Return the type to use for the merged stores or loads described by STMTS.
1237 This is needed to get the alias sets right. If IS_LOAD, look for rhs,
1238 otherwise lhs. Additionally set *CLIQUEP and *BASEP to MR_DEPENDENCE_*
1239 of the MEM_REFs if any. */
1242 get_alias_type_for_stmts (vec
<gimple
*> &stmts
, bool is_load
,
1243 unsigned short *cliquep
, unsigned short *basep
)
1247 tree type
= NULL_TREE
;
1248 tree ret
= NULL_TREE
;
1252 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1254 tree ref
= is_load
? gimple_assign_rhs1 (stmt
)
1255 : gimple_assign_lhs (stmt
);
1256 tree type1
= reference_alias_ptr_type (ref
);
1257 tree base
= get_base_address (ref
);
1261 if (TREE_CODE (base
) == MEM_REF
)
1263 *cliquep
= MR_DEPENDENCE_CLIQUE (base
);
1264 *basep
= MR_DEPENDENCE_BASE (base
);
1269 if (!alias_ptr_types_compatible_p (type
, type1
))
1270 ret
= ptr_type_node
;
1271 if (TREE_CODE (base
) != MEM_REF
1272 || *cliquep
!= MR_DEPENDENCE_CLIQUE (base
)
1273 || *basep
!= MR_DEPENDENCE_BASE (base
))
1282 /* Return the location_t information we can find among the statements
1286 get_location_for_stmts (vec
<gimple
*> &stmts
)
1291 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1292 if (gimple_has_location (stmt
))
1293 return gimple_location (stmt
);
1295 return UNKNOWN_LOCATION
;
1298 /* Used to decribe a store resulting from splitting a wide store in smaller
1299 regularly-sized stores in split_group. */
1303 unsigned HOST_WIDE_INT bytepos
;
1304 unsigned HOST_WIDE_INT size
;
1305 unsigned HOST_WIDE_INT align
;
1306 auto_vec
<store_immediate_info
*> orig_stores
;
1307 /* True if there is a single orig stmt covering the whole split store. */
1309 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
1310 unsigned HOST_WIDE_INT
);
1313 /* Simple constructor. */
1315 split_store::split_store (unsigned HOST_WIDE_INT bp
,
1316 unsigned HOST_WIDE_INT sz
,
1317 unsigned HOST_WIDE_INT al
)
1318 : bytepos (bp
), size (sz
), align (al
), orig (false)
1320 orig_stores
.create (0);
1323 /* Record all stores in GROUP that write to the region starting at BITPOS and
1324 is of size BITSIZE. Record infos for such statements in STORES if
1325 non-NULL. The stores in GROUP must be sorted by bitposition. Return INFO
1326 if there is exactly one original store in the range. */
1328 static store_immediate_info
*
1329 find_constituent_stores (struct merged_store_group
*group
,
1330 vec
<store_immediate_info
*> *stores
,
1331 unsigned int *first
,
1332 unsigned HOST_WIDE_INT bitpos
,
1333 unsigned HOST_WIDE_INT bitsize
)
1335 store_immediate_info
*info
, *ret
= NULL
;
1337 bool second
= false;
1338 bool update_first
= true;
1339 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1340 for (i
= *first
; group
->stores
.iterate (i
, &info
); ++i
)
1342 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1343 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1344 if (stmt_end
<= bitpos
)
1346 /* BITPOS passed to this function never decreases from within the
1347 same split_group call, so optimize and don't scan info records
1348 which are known to end before or at BITPOS next time.
1349 Only do it if all stores before this one also pass this. */
1355 update_first
= false;
1357 /* The stores in GROUP are ordered by bitposition so if we're past
1358 the region for this group return early. */
1359 if (stmt_start
>= end
)
1364 stores
->safe_push (info
);
1379 /* Return how many SSA_NAMEs used to compute value to store in the INFO
1380 store have multiple uses. If any SSA_NAME has multiple uses, also
1381 count statements needed to compute it. */
1384 count_multiple_uses (store_immediate_info
*info
)
1386 gimple
*stmt
= info
->stmt
;
1388 switch (info
->rhs_code
)
1395 if (info
->bit_not_p
)
1397 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
1398 ret
= 1; /* Fall through below to return
1399 the BIT_NOT_EXPR stmt and then
1400 BIT_{AND,IOR,XOR}_EXPR and anything it
1403 /* stmt is after this the BIT_NOT_EXPR. */
1404 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
1406 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
1408 ret
+= 1 + info
->ops
[0].bit_not_p
;
1409 if (info
->ops
[1].base_addr
)
1410 ret
+= 1 + info
->ops
[1].bit_not_p
;
1413 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
1414 /* stmt is now the BIT_*_EXPR. */
1415 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
1416 ret
+= 1 + info
->ops
[0].bit_not_p
;
1417 else if (info
->ops
[0].bit_not_p
)
1419 gimple
*stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
1420 if (!has_single_use (gimple_assign_rhs1 (stmt2
)))
1423 if (info
->ops
[1].base_addr
== NULL_TREE
)
1425 if (!has_single_use (gimple_assign_rhs2 (stmt
)))
1426 ret
+= 1 + info
->ops
[1].bit_not_p
;
1427 else if (info
->ops
[1].bit_not_p
)
1429 gimple
*stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
1430 if (!has_single_use (gimple_assign_rhs1 (stmt2
)))
1435 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
1436 return 1 + info
->ops
[0].bit_not_p
;
1437 else if (info
->ops
[0].bit_not_p
)
1439 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
1440 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
1449 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1450 vector (if non-NULL) with split_store structs describing the byte offset
1451 (from the base), the bit size and alignment of each store as well as the
1452 original statements involved in each such split group.
1453 This is to separate the splitting strategy from the statement
1454 building/emission/linking done in output_merged_store.
1455 Return number of new stores.
1456 If ALLOW_UNALIGNED_STORE is false, then all stores must be aligned.
1457 If ALLOW_UNALIGNED_LOAD is false, then all loads must be aligned.
1458 If SPLIT_STORES is NULL, it is just a dry run to count number of
1462 split_group (merged_store_group
*group
, bool allow_unaligned_store
,
1463 bool allow_unaligned_load
,
1464 vec
<struct split_store
*> *split_stores
,
1465 unsigned *total_orig
,
1466 unsigned *total_new
)
1468 unsigned HOST_WIDE_INT pos
= group
->bitregion_start
;
1469 unsigned HOST_WIDE_INT size
= group
->bitregion_end
- pos
;
1470 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1471 unsigned HOST_WIDE_INT group_align
= group
->align
;
1472 unsigned HOST_WIDE_INT align_base
= group
->align_base
;
1473 unsigned HOST_WIDE_INT group_load_align
= group_align
;
1474 bool any_orig
= false;
1476 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1478 unsigned int ret
= 0, first
= 0;
1479 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1480 group
->stores
.qsort (sort_by_bitpos
);
1485 store_immediate_info
*info
= group
->stores
[0];
1488 total_orig
[0] = 1; /* The orig store. */
1489 info
= group
->stores
[0];
1490 if (info
->ops
[0].base_addr
)
1491 total_orig
[0] += 1 + info
->ops
[0].bit_not_p
;
1492 if (info
->ops
[1].base_addr
)
1493 total_orig
[0] += 1 + info
->ops
[1].bit_not_p
;
1494 switch (info
->rhs_code
)
1499 if (info
->bit_not_p
)
1500 total_orig
[0]++; /* The orig BIT_NOT_EXPR stmt. */
1501 total_orig
[0]++; /* The orig BIT_*_EXPR stmt. */
1506 total_orig
[0] *= group
->stores
.length ();
1508 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
1509 total_new
[0] += count_multiple_uses (info
);
1512 if (!allow_unaligned_load
)
1513 for (int i
= 0; i
< 2; ++i
)
1514 if (group
->load_align
[i
])
1515 group_load_align
= MIN (group_load_align
, group
->load_align
[i
]);
1519 if ((allow_unaligned_store
|| group_align
<= BITS_PER_UNIT
)
1520 && group
->mask
[try_pos
- bytepos
] == (unsigned char) ~0U)
1522 /* Skip padding bytes. */
1524 size
-= BITS_PER_UNIT
;
1528 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1529 unsigned int try_size
= MAX_STORE_BITSIZE
, nonmasked
;
1530 unsigned HOST_WIDE_INT align_bitpos
1531 = (try_bitpos
- align_base
) & (group_align
- 1);
1532 unsigned HOST_WIDE_INT align
= group_align
;
1534 align
= least_bit_hwi (align_bitpos
);
1535 if (!allow_unaligned_store
)
1536 try_size
= MIN (try_size
, align
);
1537 if (!allow_unaligned_load
)
1539 /* If we can't do or don't want to do unaligned stores
1540 as well as loads, we need to take the loads into account
1542 unsigned HOST_WIDE_INT load_align
= group_load_align
;
1543 align_bitpos
= (try_bitpos
- align_base
) & (load_align
- 1);
1545 load_align
= least_bit_hwi (align_bitpos
);
1546 for (int i
= 0; i
< 2; ++i
)
1547 if (group
->load_align
[i
])
1549 align_bitpos
= try_bitpos
- group
->stores
[0]->bitpos
;
1550 align_bitpos
+= group
->stores
[0]->ops
[i
].bitpos
;
1551 align_bitpos
-= group
->load_align_base
[i
];
1552 align_bitpos
&= (group_load_align
- 1);
1555 unsigned HOST_WIDE_INT a
= least_bit_hwi (align_bitpos
);
1556 load_align
= MIN (load_align
, a
);
1559 try_size
= MIN (try_size
, load_align
);
1561 store_immediate_info
*info
1562 = find_constituent_stores (group
, NULL
, &first
, try_bitpos
, try_size
);
1565 /* If there is just one original statement for the range, see if
1566 we can just reuse the original store which could be even larger
1568 unsigned HOST_WIDE_INT stmt_end
1569 = ROUND_UP (info
->bitpos
+ info
->bitsize
, BITS_PER_UNIT
);
1570 info
= find_constituent_stores (group
, NULL
, &first
, try_bitpos
,
1571 stmt_end
- try_bitpos
);
1572 if (info
&& info
->bitpos
>= try_bitpos
)
1574 try_size
= stmt_end
- try_bitpos
;
1579 /* Approximate store bitsize for the case when there are no padding
1581 while (try_size
> size
)
1583 /* Now look for whole padding bytes at the end of that bitsize. */
1584 for (nonmasked
= try_size
/ BITS_PER_UNIT
; nonmasked
> 0; --nonmasked
)
1585 if (group
->mask
[try_pos
- bytepos
+ nonmasked
- 1]
1586 != (unsigned char) ~0U)
1590 /* If entire try_size range is padding, skip it. */
1591 try_pos
+= try_size
/ BITS_PER_UNIT
;
1595 /* Otherwise try to decrease try_size if second half, last 3 quarters
1596 etc. are padding. */
1597 nonmasked
*= BITS_PER_UNIT
;
1598 while (nonmasked
<= try_size
/ 2)
1600 if (!allow_unaligned_store
&& group_align
> BITS_PER_UNIT
)
1602 /* Now look for whole padding bytes at the start of that bitsize. */
1603 unsigned int try_bytesize
= try_size
/ BITS_PER_UNIT
, masked
;
1604 for (masked
= 0; masked
< try_bytesize
; ++masked
)
1605 if (group
->mask
[try_pos
- bytepos
+ masked
] != (unsigned char) ~0U)
1607 masked
*= BITS_PER_UNIT
;
1608 gcc_assert (masked
< try_size
);
1609 if (masked
>= try_size
/ 2)
1611 while (masked
>= try_size
/ 2)
1614 try_pos
+= try_size
/ BITS_PER_UNIT
;
1618 /* Need to recompute the alignment, so just retry at the new
1629 struct split_store
*store
1630 = new split_store (try_pos
, try_size
, align
);
1631 info
= find_constituent_stores (group
, &store
->orig_stores
,
1632 &first
, try_bitpos
, try_size
);
1634 && info
->bitpos
>= try_bitpos
1635 && info
->bitpos
+ info
->bitsize
<= try_bitpos
+ try_size
)
1640 split_stores
->safe_push (store
);
1643 try_pos
+= try_size
/ BITS_PER_UNIT
;
1649 /* If we are reusing some original stores and any of the
1650 original SSA_NAMEs had multiple uses, we need to subtract
1651 those now before we add the new ones. */
1652 if (total_new
[0] && any_orig
)
1655 struct split_store
*store
;
1656 FOR_EACH_VEC_ELT (*split_stores
, i
, store
)
1658 total_new
[0] -= count_multiple_uses (store
->orig_stores
[0]);
1660 total_new
[0] += ret
; /* The new store. */
1661 store_immediate_info
*info
= group
->stores
[0];
1662 if (info
->ops
[0].base_addr
)
1663 total_new
[0] += ret
* (1 + info
->ops
[0].bit_not_p
);
1664 if (info
->ops
[1].base_addr
)
1665 total_new
[0] += ret
* (1 + info
->ops
[1].bit_not_p
);
1666 switch (info
->rhs_code
)
1671 if (info
->bit_not_p
)
1672 total_new
[0] += ret
; /* The new BIT_NOT_EXPR stmt. */
1673 total_new
[0] += ret
; /* The new BIT_*_EXPR stmt. */
1683 /* Given a merged store group GROUP output the widened version of it.
1684 The store chain is against the base object BASE.
1685 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1686 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1687 Make sure that the number of statements output is less than the number of
1688 original statements. If a better sequence is possible emit it and
1692 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1694 unsigned HOST_WIDE_INT start_byte_pos
1695 = group
->bitregion_start
/ BITS_PER_UNIT
;
1697 unsigned int orig_num_stmts
= group
->stores
.length ();
1698 if (orig_num_stmts
< 2)
1701 auto_vec
<struct split_store
*, 32> split_stores
;
1702 split_stores
.create (0);
1703 bool allow_unaligned_store
1704 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1705 bool allow_unaligned_load
= allow_unaligned_store
;
1706 if (allow_unaligned_store
)
1708 /* If unaligned stores are allowed, see how many stores we'd emit
1709 for unaligned and how many stores we'd emit for aligned stores.
1710 Only use unaligned stores if it allows fewer stores than aligned. */
1711 unsigned aligned_cnt
1712 = split_group (group
, false, allow_unaligned_load
, NULL
, NULL
, NULL
);
1713 unsigned unaligned_cnt
1714 = split_group (group
, true, allow_unaligned_load
, NULL
, NULL
, NULL
);
1715 if (aligned_cnt
<= unaligned_cnt
)
1716 allow_unaligned_store
= false;
1718 unsigned total_orig
, total_new
;
1719 split_group (group
, allow_unaligned_store
, allow_unaligned_load
,
1720 &split_stores
, &total_orig
, &total_new
);
1722 if (split_stores
.length () >= orig_num_stmts
)
1724 /* We didn't manage to reduce the number of statements. Bail out. */
1725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1726 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1727 " Not profitable to emit new sequence.\n",
1731 if (total_orig
<= total_new
)
1733 /* If number of estimated new statements is above estimated original
1734 statements, bail out too. */
1735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1736 fprintf (dump_file
, "Estimated number of original stmts (%u)"
1737 " not larger than estimated number of new"
1739 total_orig
, total_new
);
1742 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1743 gimple_seq seq
= NULL
;
1744 tree last_vdef
, new_vuse
;
1745 last_vdef
= gimple_vdef (group
->last_stmt
);
1746 new_vuse
= gimple_vuse (group
->last_stmt
);
1748 gimple
*stmt
= NULL
;
1749 split_store
*split_store
;
1751 auto_vec
<gimple
*, 32> orig_stmts
;
1752 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &seq
,
1753 is_gimple_mem_ref_addr
, NULL_TREE
);
1755 tree load_addr
[2] = { NULL_TREE
, NULL_TREE
};
1756 gimple_seq load_seq
[2] = { NULL
, NULL
};
1757 gimple_stmt_iterator load_gsi
[2] = { gsi_none (), gsi_none () };
1758 for (int j
= 0; j
< 2; ++j
)
1760 store_operand_info
&op
= group
->stores
[0]->ops
[j
];
1761 if (op
.base_addr
== NULL_TREE
)
1764 store_immediate_info
*infol
= group
->stores
.last ();
1765 if (gimple_vuse (op
.stmt
) == gimple_vuse (infol
->ops
[j
].stmt
))
1767 load_gsi
[j
] = gsi_for_stmt (op
.stmt
);
1769 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
1770 &load_seq
[j
], is_gimple_mem_ref_addr
,
1773 else if (operand_equal_p (base_addr
, op
.base_addr
, 0))
1774 load_addr
[j
] = addr
;
1777 gimple_seq this_seq
;
1779 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
1780 &this_seq
, is_gimple_mem_ref_addr
,
1782 gimple_seq_add_seq_without_update (&seq
, this_seq
);
1786 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1788 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1789 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1790 unsigned HOST_WIDE_INT align
= split_store
->align
;
1793 if (split_store
->orig
)
1795 /* If there is just a single constituent store which covers
1796 the whole area, just reuse the lhs and rhs. */
1797 gimple
*orig_stmt
= split_store
->orig_stores
[0]->stmt
;
1798 dest
= gimple_assign_lhs (orig_stmt
);
1799 src
= gimple_assign_rhs1 (orig_stmt
);
1800 loc
= gimple_location (orig_stmt
);
1804 store_immediate_info
*info
;
1805 unsigned short clique
, base
;
1807 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1808 orig_stmts
.safe_push (info
->stmt
);
1810 = get_alias_type_for_stmts (orig_stmts
, false, &clique
, &base
);
1811 loc
= get_location_for_stmts (orig_stmts
);
1812 orig_stmts
.truncate (0);
1814 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1815 int_type
= build_aligned_type (int_type
, align
);
1816 dest
= fold_build2 (MEM_REF
, int_type
, addr
,
1817 build_int_cst (offset_type
, try_pos
));
1818 if (TREE_CODE (dest
) == MEM_REF
)
1820 MR_DEPENDENCE_CLIQUE (dest
) = clique
;
1821 MR_DEPENDENCE_BASE (dest
) = base
;
1825 = native_interpret_expr (int_type
,
1826 group
->mask
+ try_pos
- start_byte_pos
,
1831 j
< 1 + (split_store
->orig_stores
[0]->ops
[1].val
!= NULL_TREE
);
1834 store_operand_info
&op
= split_store
->orig_stores
[0]->ops
[j
];
1837 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1838 orig_stmts
.safe_push (info
->ops
[j
].stmt
);
1840 offset_type
= get_alias_type_for_stmts (orig_stmts
, true,
1842 location_t load_loc
= get_location_for_stmts (orig_stmts
);
1843 orig_stmts
.truncate (0);
1845 unsigned HOST_WIDE_INT load_align
= group
->load_align
[j
];
1846 unsigned HOST_WIDE_INT align_bitpos
1847 = (try_pos
* BITS_PER_UNIT
1848 - split_store
->orig_stores
[0]->bitpos
1849 + op
.bitpos
) & (load_align
- 1);
1851 load_align
= least_bit_hwi (align_bitpos
);
1854 = build_nonstandard_integer_type (try_size
, UNSIGNED
);
1856 = build_aligned_type (load_int_type
, load_align
);
1858 unsigned HOST_WIDE_INT load_pos
1859 = (try_pos
* BITS_PER_UNIT
1860 - split_store
->orig_stores
[0]->bitpos
1861 + op
.bitpos
) / BITS_PER_UNIT
;
1862 ops
[j
] = fold_build2 (MEM_REF
, load_int_type
, load_addr
[j
],
1863 build_int_cst (offset_type
, load_pos
));
1864 if (TREE_CODE (ops
[j
]) == MEM_REF
)
1866 MR_DEPENDENCE_CLIQUE (ops
[j
]) = clique
;
1867 MR_DEPENDENCE_BASE (ops
[j
]) = base
;
1869 if (!integer_zerop (mask
))
1870 /* The load might load some bits (that will be masked off
1871 later on) uninitialized, avoid -W*uninitialized
1872 warnings in that case. */
1873 TREE_NO_WARNING (ops
[j
]) = 1;
1875 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1877 gimple_set_location (stmt
, load_loc
);
1878 if (gsi_bb (load_gsi
[j
]))
1880 gimple_set_vuse (stmt
, gimple_vuse (op
.stmt
));
1881 gimple_seq_add_stmt_without_update (&load_seq
[j
], stmt
);
1885 gimple_set_vuse (stmt
, new_vuse
);
1886 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1888 ops
[j
] = gimple_assign_lhs (stmt
);
1891 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1892 BIT_NOT_EXPR
, ops
[j
]);
1893 gimple_set_location (stmt
, load_loc
);
1894 ops
[j
] = gimple_assign_lhs (stmt
);
1896 if (gsi_bb (load_gsi
[j
]))
1897 gimple_seq_add_stmt_without_update (&load_seq
[j
],
1900 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1904 ops
[j
] = native_interpret_expr (int_type
,
1905 group
->val
+ try_pos
1910 switch (split_store
->orig_stores
[0]->rhs_code
)
1915 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
1917 tree rhs1
= gimple_assign_rhs1 (info
->stmt
);
1918 orig_stmts
.safe_push (SSA_NAME_DEF_STMT (rhs1
));
1921 bit_loc
= get_location_for_stmts (orig_stmts
);
1922 orig_stmts
.truncate (0);
1925 = gimple_build_assign (make_ssa_name (int_type
),
1926 split_store
->orig_stores
[0]->rhs_code
,
1928 gimple_set_location (stmt
, bit_loc
);
1929 /* If there is just one load and there is a separate
1930 load_seq[0], emit the bitwise op right after it. */
1931 if (load_addr
[1] == NULL_TREE
&& gsi_bb (load_gsi
[0]))
1932 gimple_seq_add_stmt_without_update (&load_seq
[0], stmt
);
1933 /* Otherwise, if at least one load is in seq, we need to
1934 emit the bitwise op right before the store. If there
1935 are two loads and are emitted somewhere else, it would
1936 be better to emit the bitwise op as early as possible;
1937 we don't track where that would be possible right now
1940 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1941 src
= gimple_assign_lhs (stmt
);
1942 if (split_store
->orig_stores
[0]->bit_not_p
)
1944 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1946 gimple_set_location (stmt
, bit_loc
);
1947 if (load_addr
[1] == NULL_TREE
&& gsi_bb (load_gsi
[0]))
1948 gimple_seq_add_stmt_without_update (&load_seq
[0], stmt
);
1950 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1951 src
= gimple_assign_lhs (stmt
);
1959 if (!integer_zerop (mask
))
1961 tree tem
= make_ssa_name (int_type
);
1962 tree load_src
= unshare_expr (dest
);
1963 /* The load might load some or all bits uninitialized,
1964 avoid -W*uninitialized warnings in that case.
1965 As optimization, it would be nice if all the bits are
1966 provably uninitialized (no stores at all yet or previous
1967 store a CLOBBER) we'd optimize away the load and replace
1969 TREE_NO_WARNING (load_src
) = 1;
1970 stmt
= gimple_build_assign (tem
, load_src
);
1971 gimple_set_location (stmt
, loc
);
1972 gimple_set_vuse (stmt
, new_vuse
);
1973 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1975 /* FIXME: If there is a single chunk of zero bits in mask,
1976 perhaps use BIT_INSERT_EXPR instead? */
1977 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1978 BIT_AND_EXPR
, tem
, mask
);
1979 gimple_set_location (stmt
, loc
);
1980 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1981 tem
= gimple_assign_lhs (stmt
);
1983 if (TREE_CODE (src
) == INTEGER_CST
)
1984 src
= wide_int_to_tree (int_type
,
1985 wi::bit_and_not (wi::to_wide (src
),
1986 wi::to_wide (mask
)));
1990 = wide_int_to_tree (int_type
,
1991 wi::bit_not (wi::to_wide (mask
)));
1992 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1993 BIT_AND_EXPR
, src
, nmask
);
1994 gimple_set_location (stmt
, loc
);
1995 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1996 src
= gimple_assign_lhs (stmt
);
1998 stmt
= gimple_build_assign (make_ssa_name (int_type
),
1999 BIT_IOR_EXPR
, tem
, src
);
2000 gimple_set_location (stmt
, loc
);
2001 gimple_seq_add_stmt_without_update (&seq
, stmt
);
2002 src
= gimple_assign_lhs (stmt
);
2006 stmt
= gimple_build_assign (dest
, src
);
2007 gimple_set_location (stmt
, loc
);
2008 gimple_set_vuse (stmt
, new_vuse
);
2009 gimple_seq_add_stmt_without_update (&seq
, stmt
);
2012 if (i
< split_stores
.length () - 1)
2013 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
2015 new_vdef
= last_vdef
;
2017 gimple_set_vdef (stmt
, new_vdef
);
2018 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
2019 new_vuse
= new_vdef
;
2022 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
2029 "New sequence of %u stmts to replace old one of %u stmts\n",
2030 split_stores
.length (), orig_num_stmts
);
2031 if (dump_flags
& TDF_DETAILS
)
2032 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
2034 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
2035 for (int j
= 0; j
< 2; ++j
)
2037 gsi_insert_seq_after (&load_gsi
[j
], load_seq
[j
], GSI_SAME_STMT
);
2042 /* Process the merged_store_group objects created in the coalescing phase.
2043 The stores are all against the base object BASE.
2044 Try to output the widened stores and delete the original statements if
2045 successful. Return true iff any changes were made. */
2048 imm_store_chain_info::output_merged_stores ()
2051 merged_store_group
*merged_store
;
2053 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
2055 if (output_merged_store (merged_store
))
2058 store_immediate_info
*store
;
2059 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
2061 gimple
*stmt
= store
->stmt
;
2062 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
2063 gsi_remove (&gsi
, true);
2064 if (stmt
!= merged_store
->last_stmt
)
2066 unlink_stmt_vdef (stmt
);
2067 release_defs (stmt
);
2073 if (ret
&& dump_file
)
2074 fprintf (dump_file
, "Merging successful!\n");
2079 /* Coalesce the store_immediate_info objects recorded against the base object
2080 BASE in the first phase and output them.
2081 Delete the allocated structures.
2082 Return true if any changes were made. */
2085 imm_store_chain_info::terminate_and_process_chain ()
2087 /* Process store chain. */
2089 if (m_store_info
.length () > 1)
2091 ret
= coalesce_immediate_stores ();
2093 ret
= output_merged_stores ();
2096 /* Delete all the entries we allocated ourselves. */
2097 store_immediate_info
*info
;
2099 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
2102 merged_store_group
*merged_info
;
2103 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
2109 /* Return true iff LHS is a destination potentially interesting for
2110 store merging. In practice these are the codes that get_inner_reference
2114 lhs_valid_for_store_merging_p (tree lhs
)
2116 tree_code code
= TREE_CODE (lhs
);
2118 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
2119 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
2125 /* Return true if the tree RHS is a constant we want to consider
2126 during store merging. In practice accept all codes that
2127 native_encode_expr accepts. */
2130 rhs_valid_for_store_merging_p (tree rhs
)
2132 return native_encode_expr (rhs
, NULL
,
2133 GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (rhs
)))) != 0;
2136 /* If MEM is a memory reference usable for store merging (either as
2137 store destination or for loads), return the non-NULL base_addr
2138 and set *PBITSIZE, *PBITPOS, *PBITREGION_START and *PBITREGION_END.
2139 Otherwise return NULL, *PBITPOS should be still valid even for that
2143 mem_valid_for_store_merging (tree mem
, unsigned HOST_WIDE_INT
*pbitsize
,
2144 unsigned HOST_WIDE_INT
*pbitpos
,
2145 unsigned HOST_WIDE_INT
*pbitregion_start
,
2146 unsigned HOST_WIDE_INT
*pbitregion_end
)
2148 HOST_WIDE_INT bitsize
;
2149 HOST_WIDE_INT bitpos
;
2150 unsigned HOST_WIDE_INT bitregion_start
= 0;
2151 unsigned HOST_WIDE_INT bitregion_end
= 0;
2153 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
2155 tree base_addr
= get_inner_reference (mem
, &bitsize
, &bitpos
, &offset
, &mode
,
2156 &unsignedp
, &reversep
, &volatilep
);
2157 *pbitsize
= bitsize
;
2161 if (TREE_CODE (mem
) == COMPONENT_REF
2162 && DECL_BIT_FIELD_TYPE (TREE_OPERAND (mem
, 1)))
2164 get_bit_range (&bitregion_start
, &bitregion_end
, mem
, &bitpos
, &offset
);
2172 /* We do not want to rewrite TARGET_MEM_REFs. */
2173 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
2175 /* In some cases get_inner_reference may return a
2176 MEM_REF [ptr + byteoffset]. For the purposes of this pass
2177 canonicalize the base_addr to MEM_REF [ptr] and take
2178 byteoffset into account in the bitpos. This occurs in
2179 PR 23684 and this way we can catch more chains. */
2180 else if (TREE_CODE (base_addr
) == MEM_REF
)
2182 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
2183 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2185 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
2187 bitpos
= bit_off
.to_shwi ();
2190 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2191 bit_off
+= bitregion_start
;
2192 if (wi::fits_uhwi_p (bit_off
))
2194 bitregion_start
= bit_off
.to_uhwi ();
2195 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
2196 bit_off
+= bitregion_end
;
2197 if (wi::fits_uhwi_p (bit_off
))
2198 bitregion_end
= bit_off
.to_uhwi ();
2208 base_addr
= TREE_OPERAND (base_addr
, 0);
2210 /* get_inner_reference returns the base object, get at its
2216 base_addr
= build_fold_addr_expr (base_addr
);
2221 bitregion_start
= ROUND_DOWN (bitpos
, BITS_PER_UNIT
);
2222 bitregion_end
= ROUND_UP (bitpos
+ bitsize
, BITS_PER_UNIT
);
2225 if (offset
!= NULL_TREE
)
2227 /* If the access is variable offset then a base decl has to be
2228 address-taken to be able to emit pointer-based stores to it.
2229 ??? We might be able to get away with re-using the original
2230 base up to the first variable part and then wrapping that inside
2232 tree base
= get_base_address (base_addr
);
2234 || (DECL_P (base
) && ! TREE_ADDRESSABLE (base
)))
2237 base_addr
= build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base_addr
),
2241 *pbitsize
= bitsize
;
2243 *pbitregion_start
= bitregion_start
;
2244 *pbitregion_end
= bitregion_end
;
2248 /* Return true if STMT is a load that can be used for store merging.
2249 In that case fill in *OP. BITSIZE, BITPOS, BITREGION_START and
2250 BITREGION_END are properties of the corresponding store. */
2253 handled_load (gimple
*stmt
, store_operand_info
*op
,
2254 unsigned HOST_WIDE_INT bitsize
, unsigned HOST_WIDE_INT bitpos
,
2255 unsigned HOST_WIDE_INT bitregion_start
,
2256 unsigned HOST_WIDE_INT bitregion_end
)
2258 if (!is_gimple_assign (stmt
))
2260 if (gimple_assign_rhs_code (stmt
) == BIT_NOT_EXPR
)
2262 tree rhs1
= gimple_assign_rhs1 (stmt
);
2263 if (TREE_CODE (rhs1
) == SSA_NAME
2264 && handled_load (SSA_NAME_DEF_STMT (rhs1
), op
, bitsize
, bitpos
,
2265 bitregion_start
, bitregion_end
))
2267 /* Don't allow _1 = load; _2 = ~1; _3 = ~_2; which should have
2268 been optimized earlier, but if allowed here, would confuse the
2269 multiple uses counting. */
2272 op
->bit_not_p
= !op
->bit_not_p
;
2277 if (gimple_vuse (stmt
)
2278 && gimple_assign_load_p (stmt
)
2279 && !stmt_can_throw_internal (stmt
)
2280 && !gimple_has_volatile_ops (stmt
))
2282 tree mem
= gimple_assign_rhs1 (stmt
);
2284 = mem_valid_for_store_merging (mem
, &op
->bitsize
, &op
->bitpos
,
2285 &op
->bitregion_start
,
2286 &op
->bitregion_end
);
2287 if (op
->base_addr
!= NULL_TREE
2288 && op
->bitsize
== bitsize
2289 && ((op
->bitpos
- bitpos
) % BITS_PER_UNIT
) == 0
2290 && op
->bitpos
- op
->bitregion_start
>= bitpos
- bitregion_start
2291 && op
->bitregion_end
- op
->bitpos
>= bitregion_end
- bitpos
)
2295 op
->bit_not_p
= false;
2302 /* Record the store STMT for store merging optimization if it can be
2306 pass_store_merging::process_store (gimple
*stmt
)
2308 tree lhs
= gimple_assign_lhs (stmt
);
2309 tree rhs
= gimple_assign_rhs1 (stmt
);
2310 unsigned HOST_WIDE_INT bitsize
, bitpos
;
2311 unsigned HOST_WIDE_INT bitregion_start
;
2312 unsigned HOST_WIDE_INT bitregion_end
;
2314 = mem_valid_for_store_merging (lhs
, &bitsize
, &bitpos
,
2315 &bitregion_start
, &bitregion_end
);
2319 bool invalid
= (base_addr
== NULL_TREE
2320 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
2321 && (TREE_CODE (rhs
) != INTEGER_CST
)));
2322 enum tree_code rhs_code
= ERROR_MARK
;
2323 bool bit_not_p
= false;
2324 store_operand_info ops
[2];
2327 else if (rhs_valid_for_store_merging_p (rhs
))
2329 rhs_code
= INTEGER_CST
;
2332 else if (TREE_CODE (rhs
) != SSA_NAME
)
2336 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
), *def_stmt1
, *def_stmt2
;
2337 if (!is_gimple_assign (def_stmt
))
2339 else if (handled_load (def_stmt
, &ops
[0], bitsize
, bitpos
,
2340 bitregion_start
, bitregion_end
))
2342 else if (gimple_assign_rhs_code (def_stmt
) == BIT_NOT_EXPR
)
2344 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
2345 if (TREE_CODE (rhs1
) == SSA_NAME
2346 && is_gimple_assign (SSA_NAME_DEF_STMT (rhs1
)))
2349 def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2352 if (rhs_code
== ERROR_MARK
&& !invalid
)
2353 switch ((rhs_code
= gimple_assign_rhs_code (def_stmt
)))
2359 rhs1
= gimple_assign_rhs1 (def_stmt
);
2360 rhs2
= gimple_assign_rhs2 (def_stmt
);
2362 if (TREE_CODE (rhs1
) != SSA_NAME
)
2364 def_stmt1
= SSA_NAME_DEF_STMT (rhs1
);
2365 if (!is_gimple_assign (def_stmt1
)
2366 || !handled_load (def_stmt1
, &ops
[0], bitsize
, bitpos
,
2367 bitregion_start
, bitregion_end
))
2369 if (rhs_valid_for_store_merging_p (rhs2
))
2371 else if (TREE_CODE (rhs2
) != SSA_NAME
)
2375 def_stmt2
= SSA_NAME_DEF_STMT (rhs2
);
2376 if (!is_gimple_assign (def_stmt2
))
2378 else if (!handled_load (def_stmt2
, &ops
[1], bitsize
, bitpos
,
2379 bitregion_start
, bitregion_end
))
2392 terminate_all_aliasing_chains (NULL
, stmt
);
2396 struct imm_store_chain_info
**chain_info
= NULL
;
2398 chain_info
= m_stores
.get (base_addr
);
2400 store_immediate_info
*info
;
2403 unsigned int ord
= (*chain_info
)->m_store_info
.length ();
2404 info
= new store_immediate_info (bitsize
, bitpos
, bitregion_start
,
2405 bitregion_end
, stmt
, ord
, rhs_code
,
2406 bit_not_p
, ops
[0], ops
[1]);
2407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2409 fprintf (dump_file
, "Recording immediate store from stmt:\n");
2410 print_gimple_stmt (dump_file
, stmt
, 0);
2412 (*chain_info
)->m_store_info
.safe_push (info
);
2413 terminate_all_aliasing_chains (chain_info
, stmt
);
2414 /* If we reach the limit of stores to merge in a chain terminate and
2415 process the chain now. */
2416 if ((*chain_info
)->m_store_info
.length ()
2417 == (unsigned int) PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
2419 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2421 "Reached maximum number of statements to merge:\n");
2422 terminate_and_release_chain (*chain_info
);
2427 /* Store aliases any existing chain? */
2428 terminate_all_aliasing_chains (NULL
, stmt
);
2429 /* Start a new chain. */
2430 struct imm_store_chain_info
*new_chain
2431 = new imm_store_chain_info (m_stores_head
, base_addr
);
2432 info
= new store_immediate_info (bitsize
, bitpos
, bitregion_start
,
2433 bitregion_end
, stmt
, 0, rhs_code
,
2434 bit_not_p
, ops
[0], ops
[1]);
2435 new_chain
->m_store_info
.safe_push (info
);
2436 m_stores
.put (base_addr
, new_chain
);
2437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2439 fprintf (dump_file
, "Starting new chain with statement:\n");
2440 print_gimple_stmt (dump_file
, stmt
, 0);
2441 fprintf (dump_file
, "The base object is:\n");
2442 print_generic_expr (dump_file
, base_addr
);
2443 fprintf (dump_file
, "\n");
2447 /* Entry point for the pass. Go over each basic block recording chains of
2448 immediate stores. Upon encountering a terminating statement (as defined
2449 by stmt_terminates_chain_p) process the recorded stores and emit the widened
2453 pass_store_merging::execute (function
*fun
)
2456 hash_set
<gimple
*> orig_stmts
;
2458 FOR_EACH_BB_FN (bb
, fun
)
2460 gimple_stmt_iterator gsi
;
2461 unsigned HOST_WIDE_INT num_statements
= 0;
2462 /* Record the original statements so that we can keep track of
2463 statements emitted in this pass and not re-process new
2465 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2467 if (is_gimple_debug (gsi_stmt (gsi
)))
2470 if (++num_statements
>= 2)
2474 if (num_statements
< 2)
2477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2478 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
2480 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2482 gimple
*stmt
= gsi_stmt (gsi
);
2484 if (is_gimple_debug (stmt
))
2487 if (gimple_has_volatile_ops (stmt
))
2489 /* Terminate all chains. */
2490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2491 fprintf (dump_file
, "Volatile access terminates "
2493 terminate_and_process_all_chains ();
2497 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
2498 && !stmt_can_throw_internal (stmt
)
2499 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
2500 process_store (stmt
);
2502 terminate_all_aliasing_chains (NULL
, stmt
);
2504 terminate_and_process_all_chains ();
2511 /* Construct and return a store merging pass object. */
2514 make_pass_store_merging (gcc::context
*ctxt
)
2516 return new pass_store_merging (ctxt
);
2521 namespace selftest
{
2523 /* Selftests for store merging helpers. */
2525 /* Assert that all elements of the byte arrays X and Y, both of length N
2529 verify_array_eq (unsigned char *x
, unsigned char *y
, unsigned int n
)
2531 for (unsigned int i
= 0; i
< n
; i
++)
2535 fprintf (stderr
, "Arrays do not match. X:\n");
2536 dump_char_array (stderr
, x
, n
);
2537 fprintf (stderr
, "Y:\n");
2538 dump_char_array (stderr
, y
, n
);
2540 ASSERT_EQ (x
[i
], y
[i
]);
2544 /* Test shift_bytes_in_array and that it carries bits across between
2548 verify_shift_bytes_in_array (void)
2551 00011111 | 11100000. */
2552 unsigned char orig
[2] = { 0xe0, 0x1f };
2553 unsigned char in
[2];
2554 memcpy (in
, orig
, sizeof orig
);
2556 unsigned char expected
[2] = { 0x80, 0x7f };
2557 shift_bytes_in_array (in
, sizeof (in
), 2);
2558 verify_array_eq (in
, expected
, sizeof (in
));
2560 memcpy (in
, orig
, sizeof orig
);
2561 memcpy (expected
, orig
, sizeof orig
);
2562 /* Check that shifting by zero doesn't change anything. */
2563 shift_bytes_in_array (in
, sizeof (in
), 0);
2564 verify_array_eq (in
, expected
, sizeof (in
));
2568 /* Test shift_bytes_in_array_right and that it carries bits across between
2572 verify_shift_bytes_in_array_right (void)
2575 00011111 | 11100000. */
2576 unsigned char orig
[2] = { 0x1f, 0xe0};
2577 unsigned char in
[2];
2578 memcpy (in
, orig
, sizeof orig
);
2579 unsigned char expected
[2] = { 0x07, 0xf8};
2580 shift_bytes_in_array_right (in
, sizeof (in
), 2);
2581 verify_array_eq (in
, expected
, sizeof (in
));
2583 memcpy (in
, orig
, sizeof orig
);
2584 memcpy (expected
, orig
, sizeof orig
);
2585 /* Check that shifting by zero doesn't change anything. */
2586 shift_bytes_in_array_right (in
, sizeof (in
), 0);
2587 verify_array_eq (in
, expected
, sizeof (in
));
2590 /* Test clear_bit_region that it clears exactly the bits asked and
2594 verify_clear_bit_region (void)
2596 /* Start with all bits set and test clearing various patterns in them. */
2597 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
2598 unsigned char in
[3];
2599 unsigned char expected
[3];
2600 memcpy (in
, orig
, sizeof in
);
2602 /* Check zeroing out all the bits. */
2603 clear_bit_region (in
, 0, 3 * BITS_PER_UNIT
);
2604 expected
[0] = expected
[1] = expected
[2] = 0;
2605 verify_array_eq (in
, expected
, sizeof in
);
2607 memcpy (in
, orig
, sizeof in
);
2608 /* Leave the first and last bits intact. */
2609 clear_bit_region (in
, 1, 3 * BITS_PER_UNIT
- 2);
2613 verify_array_eq (in
, expected
, sizeof in
);
2616 /* Test verify_clear_bit_region_be that it clears exactly the bits asked and
2620 verify_clear_bit_region_be (void)
2622 /* Start with all bits set and test clearing various patterns in them. */
2623 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
2624 unsigned char in
[3];
2625 unsigned char expected
[3];
2626 memcpy (in
, orig
, sizeof in
);
2628 /* Check zeroing out all the bits. */
2629 clear_bit_region_be (in
, BITS_PER_UNIT
- 1, 3 * BITS_PER_UNIT
);
2630 expected
[0] = expected
[1] = expected
[2] = 0;
2631 verify_array_eq (in
, expected
, sizeof in
);
2633 memcpy (in
, orig
, sizeof in
);
2634 /* Leave the first and last bits intact. */
2635 clear_bit_region_be (in
, BITS_PER_UNIT
- 2, 3 * BITS_PER_UNIT
- 2);
2639 verify_array_eq (in
, expected
, sizeof in
);
2643 /* Run all of the selftests within this file. */
2646 store_merging_c_tests (void)
2648 verify_shift_bytes_in_array ();
2649 verify_shift_bytes_in_array_right ();
2650 verify_clear_bit_region ();
2651 verify_clear_bit_region_be ();
2654 } // namespace selftest
2655 #endif /* CHECKING_P. */