1 /* GIMPLE store merging pass.
2 Copyright (C) 2016 Free Software Foundation, Inc.
3 Contributed by ARM Ltd.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The purpose of this pass is to combine multiple memory stores of
22 constant values to consecutive memory locations into fewer wider stores.
23 For example, if we have a sequence peforming four byte stores to
24 consecutive memory locations:
29 we can transform this into a single 4-byte store if the target supports it:
30 [p] := imm1:imm2:imm3:imm4 //concatenated immediates according to endianness.
32 The algorithm is applied to each basic block in three phases:
34 1) Scan through the basic block recording constant assignments to
35 destinations that can be expressed as a store to memory of a certain size
36 at a certain bit offset. Record store chains to different bases in a
37 hash_map (m_stores) and make sure to terminate such chains when appropriate
38 (for example when when the stored values get used subsequently).
39 These stores can be a result of structure element initializers, array stores
40 etc. A store_immediate_info object is recorded for every such store.
41 Record as many such assignments to a single base as possible until a
42 statement that interferes with the store sequence is encountered.
44 2) Analyze the chain of stores recorded in phase 1) (i.e. the vector of
45 store_immediate_info objects) and coalesce contiguous stores into
46 merged_store_group objects.
48 For example, given the stores:
55 This phase would produce two merged_store_group objects, one recording the
56 two bytes stored in the memory region [p : p + 1] and another
57 recording the four bytes stored in the memory region [p + 3 : p + 6].
59 3) The merged_store_group objects produced in phase 2) are processed
60 to generate the sequence of wider stores that set the contiguous memory
61 regions to the sequence of bytes that correspond to it. This may emit
62 multiple stores per store group to handle contiguous stores that are not
63 of a size that is a power of 2. For example it can try to emit a 40-bit
64 store as a 32-bit store followed by an 8-bit store.
65 We try to emit as wide stores as we can while respecting STRICT_ALIGNMENT or
66 SLOW_UNALIGNED_ACCESS rules.
68 Note on endianness and example:
69 Consider 2 contiguous 16-bit stores followed by 2 contiguous 8-bit stores:
75 The memory layout for little-endian (LE) and big-endian (BE) must be:
85 To merge these into a single 48-bit merged value 'val' in phase 2)
86 on little-endian we insert stores to higher (consecutive) bitpositions
87 into the most significant bits of the merged value.
88 The final merged value would be: 0xcdab56781234
90 For big-endian we insert stores to higher bitpositions into the least
91 significant bits of the merged value.
92 The final merged value would be: 0x12345678abcd
94 Then, in phase 3), we want to emit this 48-bit value as a 32-bit store
95 followed by a 16-bit store. Again, we must consider endianness when
96 breaking down the 48-bit value 'val' computed above.
97 For little endian we emit:
98 [p] (32-bit) := 0x56781234; // val & 0x0000ffffffff;
99 [p + 4B] (16-bit) := 0xcdab; // (val & 0xffff00000000) >> 32;
101 Whereas for big-endian we emit:
102 [p] (32-bit) := 0x12345678; // (val & 0xffffffff0000) >> 16;
103 [p + 4B] (16-bit) := 0xabcd; // val & 0x00000000ffff; */
107 #include "coretypes.h"
111 #include "builtins.h"
112 #include "fold-const.h"
113 #include "tree-pass.h"
115 #include "gimple-pretty-print.h"
117 #include "fold-const.h"
119 #include "print-tree.h"
120 #include "tree-hash-traits.h"
121 #include "gimple-iterator.h"
122 #include "gimplify.h"
123 #include "stor-layout.h"
125 #include "tree-cfg.h"
128 #include "gimplify-me.h"
129 #include "selftest.h"
131 /* The maximum size (in bits) of the stores this pass should generate. */
132 #define MAX_STORE_BITSIZE (BITS_PER_WORD)
133 #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
137 /* Struct recording the information about a single store of an immediate
138 to memory. These are created in the first phase and coalesced into
139 merged_store_group objects in the second phase. */
141 struct store_immediate_info
143 unsigned HOST_WIDE_INT bitsize
;
144 unsigned HOST_WIDE_INT bitpos
;
147 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
148 gimple
*, unsigned int);
151 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
152 unsigned HOST_WIDE_INT bp
,
155 : bitsize (bs
), bitpos (bp
), stmt (st
), order (ord
)
159 /* Struct representing a group of stores to contiguous memory locations.
160 These are produced by the second phase (coalescing) and consumed in the
161 third phase that outputs the widened stores. */
163 struct merged_store_group
165 unsigned HOST_WIDE_INT start
;
166 unsigned HOST_WIDE_INT width
;
167 /* The size of the allocated memory for val. */
168 unsigned HOST_WIDE_INT buf_size
;
171 unsigned int first_order
;
172 unsigned int last_order
;
174 auto_vec
<struct store_immediate_info
*> stores
;
175 /* We record the first and last original statements in the sequence because
176 we'll need their vuse/vdef and replacement position. It's easier to keep
177 track of them separately as 'stores' is reordered by apply_stores. */
182 merged_store_group (store_immediate_info
*);
183 ~merged_store_group ();
184 void merge_into (store_immediate_info
*);
185 void merge_overlapping (store_immediate_info
*);
186 bool apply_stores ();
189 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
192 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
197 for (unsigned int i
= 0; i
< len
; i
++)
198 fprintf (fd
, "%x ", ptr
[i
]);
202 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
203 bits between adjacent elements. AMNT should be within
206 00011111|11100000 << 2 = 01111111|10000000
207 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
210 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
215 unsigned char carry_over
= 0U;
216 unsigned char carry_mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- amnt
);
217 unsigned char clear_mask
= (~0U) << amnt
;
219 for (unsigned int i
= 0; i
< sz
; i
++)
221 unsigned prev_carry_over
= carry_over
;
222 carry_over
= (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
227 ptr
[i
] &= clear_mask
;
228 ptr
[i
] |= prev_carry_over
;
233 /* Like shift_bytes_in_array but for big-endian.
234 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
235 bits between adjacent elements. AMNT should be within
238 00011111|11100000 >> 2 = 00000111|11111000
239 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
242 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
248 unsigned char carry_over
= 0U;
249 unsigned char carry_mask
= ~(~0U << amnt
);
251 for (unsigned int i
= 0; i
< sz
; i
++)
253 unsigned prev_carry_over
= carry_over
;
254 carry_over
= ptr
[i
] & carry_mask
;
256 carry_over
<<= (unsigned char) BITS_PER_UNIT
- amnt
;
258 ptr
[i
] |= prev_carry_over
;
262 /* Clear out LEN bits starting from bit START in the byte array
263 PTR. This clears the bits to the *right* from START.
264 START must be within [0, BITS_PER_UNIT) and counts starting from
265 the least significant bit. */
268 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
273 /* Clear len bits to the right of start. */
274 else if (len
<= start
+ 1)
276 unsigned char mask
= (~(~0U << len
));
277 mask
= mask
<< (start
+ 1U - len
);
280 else if (start
!= BITS_PER_UNIT
- 1)
282 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
283 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
284 len
- (start
% BITS_PER_UNIT
) - 1);
286 else if (start
== BITS_PER_UNIT
- 1
287 && len
> BITS_PER_UNIT
)
289 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
290 for (unsigned int i
= 0; i
< nbytes
; i
++)
292 if (len
% BITS_PER_UNIT
!= 0)
293 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
294 len
% BITS_PER_UNIT
);
300 /* In the byte array PTR clear the bit region starting at bit
301 START and is LEN bits wide.
302 For regions spanning multiple bytes do this recursively until we reach
303 zero LEN or a region contained within a single byte. */
306 clear_bit_region (unsigned char *ptr
, unsigned int start
,
309 /* Degenerate base case. */
312 else if (start
>= BITS_PER_UNIT
)
313 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
314 /* Second base case. */
315 else if ((start
+ len
) <= BITS_PER_UNIT
)
317 unsigned char mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- len
);
318 mask
>>= BITS_PER_UNIT
- (start
+ len
);
324 /* Clear most significant bits in a byte and proceed with the next byte. */
327 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
328 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
));
330 /* Whole bytes need to be cleared. */
331 else if (start
== 0 && len
> BITS_PER_UNIT
)
333 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
334 /* We could recurse on each byte but do the loop here to avoid
335 recursing too deep. */
336 memset (ptr
, '\0', nbytes
);
337 /* Clear the remaining sub-byte region if there is one. */
338 if (len
% BITS_PER_UNIT
!= 0)
339 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
345 /* Write BITLEN bits of EXPR to the byte array PTR at
346 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
347 Return true if the operation succeeded. */
350 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
351 unsigned int total_bytes
)
353 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
355 bool sub_byte_op_p
= (bitlen
% BITS_PER_UNIT
) || (bitpos
% BITS_PER_UNIT
)
356 || mode_for_size (bitlen
, MODE_INT
, 0) == BLKmode
;
359 return (native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
, 0)
363 We are writing a non byte-sized quantity or at a position that is not
365 |--------|--------|--------| ptr + first_byte
367 xxx xxxxxxxx xxx< bp>
370 First native_encode_expr EXPR into a temporary buffer and shift each
371 byte in the buffer by 'bp' (carrying the bits over as necessary).
372 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
373 <------bitlen---->< bp>
374 Then we clear the destination bits:
375 |---00000|00000000|000-----| ptr + first_byte
376 <-------bitlen--->< bp>
378 Finally we ORR the bytes of the shifted EXPR into the cleared region:
379 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
382 We are writing a non byte-sized quantity or at a position that is not
384 ptr + first_byte |--------|--------|--------|
386 <bp >xxx xxxxxxxx xxx
389 First native_encode_expr EXPR into a temporary buffer and shift each
390 byte in the buffer to the right by (carrying the bits over as necessary).
391 We shift by as much as needed to align the most significant bit of EXPR
393 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
394 <---bitlen----> <bp ><-----bitlen----->
395 Then we clear the destination bits:
396 ptr + first_byte |-----000||00000000||00000---|
397 <bp ><-------bitlen----->
399 Finally we ORR the bytes of the shifted EXPR into the cleared region:
400 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
401 The awkwardness comes from the fact that bitpos is counted from the
402 most significant bit of a byte. */
404 /* Allocate an extra byte so that we have space to shift into. */
405 unsigned int byte_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (expr
))) + 1;
406 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
407 memset (tmpbuf
, '\0', byte_size
);
408 /* The store detection code should only have allowed constants that are
409 accepted by native_encode_expr. */
410 if (native_encode_expr (expr
, tmpbuf
, byte_size
, 0) == 0)
413 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
414 bytes to write. This means it can write more than
415 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
416 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
417 bitlen and zero out the bits that are not relevant as well (that may
418 contain a sign bit due to sign-extension). */
420 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
422 || bitlen
% BITS_PER_UNIT
!= 0)
424 /* On big-endian the padding is at the 'front' so just skip the initial
426 if (BYTES_BIG_ENDIAN
)
429 byte_size
-= padding
;
430 if (bitlen
% BITS_PER_UNIT
!= 0)
432 if (BYTES_BIG_ENDIAN
)
433 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
434 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
436 clear_bit_region (tmpbuf
, bitlen
,
437 byte_size
* BITS_PER_UNIT
- bitlen
);
441 /* Clear the bit region in PTR where the bits from TMPBUF will be
443 if (BYTES_BIG_ENDIAN
)
444 clear_bit_region_be (ptr
+ first_byte
,
445 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
447 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
450 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
451 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
453 bool skip_byte
= false;
454 if (BYTES_BIG_ENDIAN
)
456 /* BITPOS and BITLEN are exactly aligned and no shifting
458 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
459 || (bitpos_mod
== 0 && bitlen_mod
== 0))
463 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
464 of the value until it aligns with 'bp' in the next byte over. */
465 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
467 shift_amnt
= bitlen_mod
+ bitpos_mod
;
468 skip_byte
= bitlen_mod
!= 0;
473 Shift the value right within the same byte so it aligns with 'bp'. */
475 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
478 shift_amnt
= bitpos
% BITS_PER_UNIT
;
480 /* Create the shifted version of EXPR. */
481 if (!BYTES_BIG_ENDIAN
)
483 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
489 gcc_assert (BYTES_BIG_ENDIAN
);
490 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
491 /* If shifting right forced us to move into the next byte skip the now
500 /* Insert the bits from TMPBUF. */
501 for (unsigned int i
= 0; i
< byte_size
; i
++)
502 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
507 /* Sorting function for store_immediate_info objects.
508 Sorts them by bitposition. */
511 sort_by_bitpos (const void *x
, const void *y
)
513 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
514 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
516 if ((*tmp
)->bitpos
<= (*tmp2
)->bitpos
)
518 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
524 /* Sorting function for store_immediate_info objects.
525 Sorts them by the order field. */
528 sort_by_order (const void *x
, const void *y
)
530 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
531 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
533 if ((*tmp
)->order
< (*tmp2
)->order
)
535 else if ((*tmp
)->order
> (*tmp2
)->order
)
541 /* Initialize a merged_store_group object from a store_immediate_info
544 merged_store_group::merged_store_group (store_immediate_info
*info
)
546 start
= info
->bitpos
;
547 width
= info
->bitsize
;
548 /* VAL has memory allocated for it in apply_stores once the group
549 width has been finalized. */
551 align
= get_object_alignment (gimple_assign_lhs (info
->stmt
));
553 stores
.safe_push (info
);
554 last_stmt
= info
->stmt
;
555 last_order
= info
->order
;
556 first_stmt
= last_stmt
;
557 first_order
= last_order
;
561 merged_store_group::~merged_store_group ()
567 /* Merge a store recorded by INFO into this merged store.
568 The store is not overlapping with the existing recorded
572 merged_store_group::merge_into (store_immediate_info
*info
)
574 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
575 /* Make sure we're inserting in the position we think we're inserting. */
576 gcc_assert (info
->bitpos
== start
+ width
);
579 gimple
*stmt
= info
->stmt
;
580 stores
.safe_push (info
);
581 if (info
->order
> last_order
)
583 last_order
= info
->order
;
586 else if (info
->order
< first_order
)
588 first_order
= info
->order
;
593 /* Merge a store described by INFO into this merged store.
594 INFO overlaps in some way with the current store (i.e. it's not contiguous
595 which is handled by merged_store_group::merge_into). */
598 merged_store_group::merge_overlapping (store_immediate_info
*info
)
600 gimple
*stmt
= info
->stmt
;
601 stores
.safe_push (info
);
603 /* If the store extends the size of the group, extend the width. */
604 if ((info
->bitpos
+ info
->bitsize
) > (start
+ width
))
605 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
607 if (info
->order
> last_order
)
609 last_order
= info
->order
;
612 else if (info
->order
< first_order
)
614 first_order
= info
->order
;
619 /* Go through all the recorded stores in this group in program order and
620 apply their values to the VAL byte array to create the final merged
621 value. Return true if the operation succeeded. */
624 merged_store_group::apply_stores ()
626 /* The total width of the stores must add up to a whole number of bytes
627 and start at a byte boundary. We don't support emitting bitfield
628 references for now. Also, make sure we have more than one store
629 in the group, otherwise we cannot merge anything. */
630 if (width
% BITS_PER_UNIT
!= 0
631 || start
% BITS_PER_UNIT
!= 0
632 || stores
.length () == 1)
635 stores
.qsort (sort_by_order
);
636 struct store_immediate_info
*info
;
638 /* Create a buffer of a size that is 2 times the number of bytes we're
639 storing. That way native_encode_expr can write power-of-2-sized
640 chunks without overrunning. */
641 buf_size
= 2 * (ROUND_UP (width
, BITS_PER_UNIT
) / BITS_PER_UNIT
);
642 val
= XCNEWVEC (unsigned char, buf_size
);
644 FOR_EACH_VEC_ELT (stores
, i
, info
)
646 unsigned int pos_in_buffer
= info
->bitpos
- start
;
647 bool ret
= encode_tree_to_bitpos (gimple_assign_rhs1 (info
->stmt
),
649 pos_in_buffer
, buf_size
);
650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
654 fprintf (dump_file
, "After writing ");
655 print_generic_expr (dump_file
,
656 gimple_assign_rhs1 (info
->stmt
), 0);
657 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
658 " at position %d the merged region contains:\n",
659 info
->bitsize
, pos_in_buffer
);
660 dump_char_array (dump_file
, val
, buf_size
);
663 fprintf (dump_file
, "Failed to merge stores\n");
671 /* Structure describing the store chain. */
673 struct imm_store_chain_info
676 auto_vec
<struct store_immediate_info
*> m_store_info
;
677 auto_vec
<merged_store_group
*> m_merged_store_groups
;
679 imm_store_chain_info (tree b_a
) : base_addr (b_a
) {}
680 bool terminate_and_process_chain ();
681 bool coalesce_immediate_stores ();
682 bool output_merged_store (merged_store_group
*);
683 bool output_merged_stores ();
686 const pass_data pass_data_tree_store_merging
= {
687 GIMPLE_PASS
, /* type */
688 "store-merging", /* name */
689 OPTGROUP_NONE
, /* optinfo_flags */
690 TV_GIMPLE_STORE_MERGING
, /* tv_id */
691 PROP_ssa
, /* properties_required */
692 0, /* properties_provided */
693 0, /* properties_destroyed */
694 0, /* todo_flags_start */
695 TODO_update_ssa
, /* todo_flags_finish */
698 class pass_store_merging
: public gimple_opt_pass
701 pass_store_merging (gcc::context
*ctxt
)
702 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
)
706 /* Pass not supported for PDP-endianness. */
710 return flag_store_merging
&& (WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
);
713 virtual unsigned int execute (function
*);
716 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
718 bool terminate_and_process_all_chains ();
719 bool terminate_all_aliasing_chains (imm_store_chain_info
**,
721 bool terminate_and_release_chain (imm_store_chain_info
*);
722 }; // class pass_store_merging
724 /* Terminate and process all recorded chains. Return true if any changes
728 pass_store_merging::terminate_and_process_all_chains ()
730 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
733 for (; iter
!= m_stores
.end (); ++iter
)
734 ret
|= terminate_and_release_chain ((*iter
).second
);
739 /* Terminate all chains that are affected by the assignment to DEST, appearing
740 in statement STMT and ultimately points to the object BASE. Return true if
741 at least one aliasing chain was terminated. BASE and DEST are allowed to
742 be NULL_TREE. In that case the aliasing checks are performed on the whole
743 statement rather than a particular operand in it. VAR_OFFSET_P signifies
744 whether STMT represents a store to BASE offset by a variable amount.
745 If that is the case we have to terminate any chain anchored at BASE. */
748 pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
755 /* If the statement doesn't touch memory it can't alias. */
756 if (!gimple_vuse (stmt
))
759 /* Check if the assignment destination (BASE) is part of a store chain.
760 This is to catch non-constant stores to destinations that may be part
764 /* We have a chain at BASE and we're writing to [BASE + <variable>].
765 This can interfere with any of the stores so terminate
769 terminate_and_release_chain (*chain_info
);
772 /* Otherwise go through every store in the chain to see if it
773 aliases with any of them. */
776 struct store_immediate_info
*info
;
778 FOR_EACH_VEC_ELT ((*chain_info
)->m_store_info
, i
, info
)
780 if (ref_maybe_used_by_stmt_p (stmt
,
781 gimple_assign_lhs (info
->stmt
))
782 || stmt_may_clobber_ref_p (stmt
,
783 gimple_assign_lhs (info
->stmt
)))
785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
788 "stmt causes chain termination:\n");
789 print_gimple_stmt (dump_file
, stmt
, 0, 0);
791 terminate_and_release_chain (*chain_info
);
799 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
802 /* Check for aliasing with all other store chains. */
803 for (; iter
!= m_stores
.end (); ++iter
)
805 /* We already checked all the stores in chain_info and terminated the
806 chain if necessary. Skip it here. */
807 if (chain_info
&& (*chain_info
) == (*iter
).second
)
810 /* We can't use the base object here as that does not reliably exist.
811 Build a ao_ref from the base object address (if we know the
812 minimum and maximum offset and the maximum size we could improve
815 ao_ref_init_from_ptr_and_size (&chain_ref
, (*iter
).first
, NULL_TREE
);
816 if (ref_maybe_used_by_stmt_p (stmt
, &chain_ref
)
817 || stmt_may_clobber_ref_p_1 (stmt
, &chain_ref
))
819 terminate_and_release_chain ((*iter
).second
);
827 /* Helper function. Terminate the recorded chain storing to base object
828 BASE. Return true if the merging and output was successful. The m_stores
829 entry is removed after the processing in any case. */
832 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
834 bool ret
= chain_info
->terminate_and_process_chain ();
835 m_stores
.remove (chain_info
->base_addr
);
840 /* Go through the candidate stores recorded in m_store_info and merge them
841 into merged_store_group objects recorded into m_merged_store_groups
842 representing the widened stores. Return true if coalescing was successful
843 and the number of widened stores is fewer than the original number
847 imm_store_chain_info::coalesce_immediate_stores ()
849 /* Anything less can't be processed. */
850 if (m_store_info
.length () < 2)
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
855 m_store_info
.length ());
857 store_immediate_info
*info
;
860 /* Order the stores by the bitposition they write to. */
861 m_store_info
.qsort (sort_by_bitpos
);
863 info
= m_store_info
[0];
864 merged_store_group
*merged_store
= new merged_store_group (info
);
866 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
870 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
871 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
872 i
, info
->bitsize
, info
->bitpos
);
873 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
), 0);
874 fprintf (dump_file
, "\n------------\n");
882 Overlapping stores. */
883 unsigned HOST_WIDE_INT start
= info
->bitpos
;
884 if (IN_RANGE (start
, merged_store
->start
,
885 merged_store
->start
+ merged_store
->width
- 1))
887 merged_store
->merge_overlapping (info
);
891 /* |---store 1---| <gap> |---store 2---|.
892 Gap between stores. Start a new group. */
893 if (start
!= merged_store
->start
+ merged_store
->width
)
895 /* Try to apply all the stores recorded for the group to determine
896 the bitpattern they write and discard it if that fails.
897 This will also reject single-store groups. */
898 if (!merged_store
->apply_stores ())
901 m_merged_store_groups
.safe_push (merged_store
);
903 merged_store
= new merged_store_group (info
);
908 /* |---store 1---||---store 2---|
909 This store is consecutive to the previous one.
910 Merge it into the current store group. */
911 merged_store
->merge_into (info
);
914 /* Record or discard the last store group. */
915 if (!merged_store
->apply_stores ())
918 m_merged_store_groups
.safe_push (merged_store
);
920 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
922 = !m_merged_store_groups
.is_empty ()
923 && m_merged_store_groups
.length () < m_store_info
.length ();
925 if (success
&& dump_file
)
926 fprintf (dump_file
, "Coalescing successful!\n"
927 "Merged into %u stores\n",
928 m_merged_store_groups
.length ());
933 /* Return the type to use for the merged stores described by STMTS.
934 This is needed to get the alias sets right. */
937 get_alias_type_for_stmts (auto_vec
<gimple
*> &stmts
)
941 tree lhs
= gimple_assign_lhs (stmts
[0]);
942 tree type
= reference_alias_ptr_type (lhs
);
944 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
949 lhs
= gimple_assign_lhs (stmt
);
950 tree type1
= reference_alias_ptr_type (lhs
);
951 if (!alias_ptr_types_compatible_p (type
, type1
))
952 return ptr_type_node
;
957 /* Return the location_t information we can find among the statements
961 get_location_for_stmts (auto_vec
<gimple
*> &stmts
)
966 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
967 if (gimple_has_location (stmt
))
968 return gimple_location (stmt
);
970 return UNKNOWN_LOCATION
;
973 /* Used to decribe a store resulting from splitting a wide store in smaller
974 regularly-sized stores in split_group. */
978 unsigned HOST_WIDE_INT bytepos
;
979 unsigned HOST_WIDE_INT size
;
980 unsigned HOST_WIDE_INT align
;
981 auto_vec
<gimple
*> orig_stmts
;
982 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
983 unsigned HOST_WIDE_INT
);
986 /* Simple constructor. */
988 split_store::split_store (unsigned HOST_WIDE_INT bp
,
989 unsigned HOST_WIDE_INT sz
,
990 unsigned HOST_WIDE_INT al
)
991 : bytepos (bp
), size (sz
), align (al
)
993 orig_stmts
.create (0);
996 /* Record all statements corresponding to stores in GROUP that write to
997 the region starting at BITPOS and is of size BITSIZE. Record such
998 statements in STMTS. The stores in GROUP must be sorted by
1002 find_constituent_stmts (struct merged_store_group
*group
,
1003 auto_vec
<gimple
*> &stmts
,
1004 unsigned HOST_WIDE_INT bitpos
,
1005 unsigned HOST_WIDE_INT bitsize
)
1007 struct store_immediate_info
*info
;
1009 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1010 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
1012 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1013 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1014 if (stmt_end
< bitpos
)
1016 /* The stores in GROUP are ordered by bitposition so if we're past
1017 the region for this group return early. */
1018 if (stmt_start
> end
)
1021 if (IN_RANGE (stmt_start
, bitpos
, bitpos
+ bitsize
)
1022 || IN_RANGE (stmt_end
, bitpos
, end
)
1023 /* The statement writes a region that completely encloses the region
1024 that this group writes. Unlikely to occur but let's
1026 || IN_RANGE (bitpos
, stmt_start
, stmt_end
))
1027 stmts
.safe_push (info
->stmt
);
1031 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1032 vector with split_store structs describing the byte offset (from the base),
1033 the bit size and alignment of each store as well as the original statements
1034 involved in each such split group.
1035 This is to separate the splitting strategy from the statement
1036 building/emission/linking done in output_merged_store.
1037 At the moment just start with the widest possible size and keep emitting
1038 the widest we can until we have emitted all the bytes, halving the size
1039 when appropriate. */
1042 split_group (merged_store_group
*group
,
1043 auto_vec
<struct split_store
*> &split_stores
)
1045 unsigned HOST_WIDE_INT pos
= group
->start
;
1046 unsigned HOST_WIDE_INT size
= group
->width
;
1047 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1048 unsigned HOST_WIDE_INT align
= group
->align
;
1050 /* We don't handle partial bitfields for now. We shouldn't have
1051 reached this far. */
1052 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1054 bool allow_unaligned
1055 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1057 unsigned int try_size
= MAX_STORE_BITSIZE
;
1058 while (try_size
> size
1059 || (!allow_unaligned
1060 && try_size
> align
))
1063 if (try_size
< BITS_PER_UNIT
)
1067 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1068 group
->stores
.qsort (sort_by_bitpos
);
1072 struct split_store
*store
= new split_store (try_pos
, try_size
, align
);
1073 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1074 find_constituent_stmts (group
, store
->orig_stmts
, try_bitpos
, try_size
);
1075 split_stores
.safe_push (store
);
1077 try_pos
+= try_size
/ BITS_PER_UNIT
;
1081 while (size
< try_size
)
1087 /* Given a merged store group GROUP output the widened version of it.
1088 The store chain is against the base object BASE.
1089 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1090 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1091 Make sure that the number of statements output is less than the number of
1092 original statements. If a better sequence is possible emit it and
1096 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1098 unsigned HOST_WIDE_INT start_byte_pos
= group
->start
/ BITS_PER_UNIT
;
1100 unsigned int orig_num_stmts
= group
->stores
.length ();
1101 if (orig_num_stmts
< 2)
1104 auto_vec
<struct split_store
*> split_stores
;
1105 split_stores
.create (0);
1106 if (!split_group (group
, split_stores
))
1109 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1110 gimple_seq seq
= NULL
;
1111 unsigned int num_stmts
= 0;
1112 tree last_vdef
, new_vuse
;
1113 last_vdef
= gimple_vdef (group
->last_stmt
);
1114 new_vuse
= gimple_vuse (group
->last_stmt
);
1116 gimple
*stmt
= NULL
;
1117 /* The new SSA names created. Keep track of them so that we can free them
1118 if we decide to not use the new sequence. */
1119 auto_vec
<tree
> new_ssa_names
;
1120 split_store
*split_store
;
1124 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &seq
,
1125 is_gimple_mem_ref_addr
, NULL_TREE
);
1126 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1128 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1129 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1130 unsigned HOST_WIDE_INT align
= split_store
->align
;
1131 tree offset_type
= get_alias_type_for_stmts (split_store
->orig_stmts
);
1132 location_t loc
= get_location_for_stmts (split_store
->orig_stmts
);
1134 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1135 int_type
= build_aligned_type (int_type
, align
);
1136 tree dest
= fold_build2 (MEM_REF
, int_type
, addr
,
1137 build_int_cst (offset_type
, try_pos
));
1139 tree src
= native_interpret_expr (int_type
,
1140 group
->val
+ try_pos
- start_byte_pos
,
1143 stmt
= gimple_build_assign (dest
, src
);
1144 gimple_set_location (stmt
, loc
);
1145 gimple_set_vuse (stmt
, new_vuse
);
1146 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1148 /* We didn't manage to reduce the number of statements. Bail out. */
1149 if (++num_stmts
== orig_num_stmts
)
1151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1153 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1154 " Not profitable to emit new sequence.\n",
1157 unsigned int ssa_count
;
1159 /* Don't forget to cleanup the temporary SSA names. */
1160 FOR_EACH_VEC_ELT (new_ssa_names
, ssa_count
, ssa_name
)
1161 release_ssa_name (ssa_name
);
1168 if (i
< split_stores
.length () - 1)
1170 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
1171 new_ssa_names
.safe_push (new_vdef
);
1174 new_vdef
= last_vdef
;
1176 gimple_set_vdef (stmt
, new_vdef
);
1177 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
1178 new_vuse
= new_vdef
;
1181 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1191 "New sequence of %u stmts to replace old one of %u stmts\n",
1192 num_stmts
, orig_num_stmts
);
1193 if (dump_flags
& TDF_DETAILS
)
1194 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1196 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
1201 /* Process the merged_store_group objects created in the coalescing phase.
1202 The stores are all against the base object BASE.
1203 Try to output the widened stores and delete the original statements if
1204 successful. Return true iff any changes were made. */
1207 imm_store_chain_info::output_merged_stores ()
1210 merged_store_group
*merged_store
;
1212 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
1214 if (output_merged_store (merged_store
))
1217 store_immediate_info
*store
;
1218 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
1220 gimple
*stmt
= store
->stmt
;
1221 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1222 gsi_remove (&gsi
, true);
1223 if (stmt
!= merged_store
->last_stmt
)
1225 unlink_stmt_vdef (stmt
);
1226 release_defs (stmt
);
1232 if (ret
&& dump_file
)
1233 fprintf (dump_file
, "Merging successful!\n");
1238 /* Coalesce the store_immediate_info objects recorded against the base object
1239 BASE in the first phase and output them.
1240 Delete the allocated structures.
1241 Return true if any changes were made. */
1244 imm_store_chain_info::terminate_and_process_chain ()
1246 /* Process store chain. */
1248 if (m_store_info
.length () > 1)
1250 ret
= coalesce_immediate_stores ();
1252 ret
= output_merged_stores ();
1255 /* Delete all the entries we allocated ourselves. */
1256 store_immediate_info
*info
;
1258 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1261 merged_store_group
*merged_info
;
1262 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
1268 /* Return true iff LHS is a destination potentially interesting for
1269 store merging. In practice these are the codes that get_inner_reference
1273 lhs_valid_for_store_merging_p (tree lhs
)
1275 tree_code code
= TREE_CODE (lhs
);
1277 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
1278 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
1284 /* Return true if the tree RHS is a constant we want to consider
1285 during store merging. In practice accept all codes that
1286 native_encode_expr accepts. */
1289 rhs_valid_for_store_merging_p (tree rhs
)
1291 tree type
= TREE_TYPE (rhs
);
1292 if (TREE_CODE_CLASS (TREE_CODE (rhs
)) != tcc_constant
1293 || !can_native_encode_type_p (type
))
1299 /* Entry point for the pass. Go over each basic block recording chains of
1300 immediate stores. Upon encountering a terminating statement (as defined
1301 by stmt_terminates_chain_p) process the recorded stores and emit the widened
1305 pass_store_merging::execute (function
*fun
)
1308 hash_set
<gimple
*> orig_stmts
;
1310 FOR_EACH_BB_FN (bb
, fun
)
1312 gimple_stmt_iterator gsi
;
1313 unsigned HOST_WIDE_INT num_statements
= 0;
1314 /* Record the original statements so that we can keep track of
1315 statements emitted in this pass and not re-process new
1317 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1319 if (is_gimple_debug (gsi_stmt (gsi
)))
1322 if (++num_statements
> 2)
1326 if (num_statements
< 2)
1329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1330 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
1332 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1334 gimple
*stmt
= gsi_stmt (gsi
);
1336 if (gimple_has_volatile_ops (stmt
))
1338 /* Terminate all chains. */
1339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1340 fprintf (dump_file
, "Volatile access terminates "
1342 terminate_and_process_all_chains ();
1346 if (is_gimple_debug (stmt
))
1349 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
1350 && !stmt_can_throw_internal (stmt
)
1351 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
1353 tree lhs
= gimple_assign_lhs (stmt
);
1354 tree rhs
= gimple_assign_rhs1 (stmt
);
1356 HOST_WIDE_INT bitsize
, bitpos
;
1358 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
1359 tree offset
, base_addr
;
1361 = get_inner_reference (lhs
, &bitsize
, &bitpos
, &offset
, &mode
,
1362 &unsignedp
, &reversep
, &volatilep
);
1363 /* As a future enhancement we could handle stores with the same
1365 bool invalid
= reversep
1366 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
1367 && (TREE_CODE (rhs
) != INTEGER_CST
))
1368 || !rhs_valid_for_store_merging_p (rhs
);
1370 /* We do not want to rewrite TARGET_MEM_REFs. */
1371 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
1373 /* In some cases get_inner_reference may return a
1374 MEM_REF [ptr + byteoffset]. For the purposes of this pass
1375 canonicalize the base_addr to MEM_REF [ptr] and take
1376 byteoffset into account in the bitpos. This occurs in
1377 PR 23684 and this way we can catch more chains. */
1378 else if (TREE_CODE (base_addr
) == MEM_REF
)
1380 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
1381 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
1383 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
1384 bitpos
= bit_off
.to_shwi ();
1387 base_addr
= TREE_OPERAND (base_addr
, 0);
1389 /* get_inner_reference returns the base object, get at its
1395 base_addr
= build_fold_addr_expr (base_addr
);
1399 && offset
!= NULL_TREE
)
1401 /* If the access is variable offset then a base
1402 decl has to be address-taken to be able to
1403 emit pointer-based stores to it.
1404 ??? We might be able to get away with
1405 re-using the original base up to the first
1406 variable part and then wrapping that inside
1408 tree base
= get_base_address (base_addr
);
1411 && ! TREE_ADDRESSABLE (base
)))
1414 base_addr
= build2 (POINTER_PLUS_EXPR
,
1415 TREE_TYPE (base_addr
),
1419 struct imm_store_chain_info
**chain_info
1420 = m_stores
.get (base_addr
);
1424 store_immediate_info
*info
;
1427 info
= new store_immediate_info (
1428 bitsize
, bitpos
, stmt
,
1429 (*chain_info
)->m_store_info
.length ());
1430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1433 "Recording immediate store from stmt:\n");
1434 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1436 (*chain_info
)->m_store_info
.safe_push (info
);
1437 /* If we reach the limit of stores to merge in a chain
1438 terminate and process the chain now. */
1439 if ((*chain_info
)->m_store_info
.length ()
1441 PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
1443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1445 "Reached maximum number of statements"
1447 terminate_and_release_chain (*chain_info
);
1452 /* Store aliases any existing chain? */
1453 terminate_all_aliasing_chains (chain_info
, false, stmt
);
1454 /* Start a new chain. */
1455 struct imm_store_chain_info
*new_chain
1456 = new imm_store_chain_info (base_addr
);
1457 info
= new store_immediate_info (bitsize
, bitpos
,
1459 new_chain
->m_store_info
.safe_push (info
);
1460 m_stores
.put (base_addr
, new_chain
);
1461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1464 "Starting new chain with statement:\n");
1465 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1466 fprintf (dump_file
, "The base object is:\n");
1467 print_generic_expr (dump_file
, base_addr
, 0);
1468 fprintf (dump_file
, "\n");
1472 terminate_all_aliasing_chains (chain_info
,
1473 offset
!= NULL_TREE
, stmt
);
1478 terminate_all_aliasing_chains (NULL
, false, stmt
);
1480 terminate_and_process_all_chains ();
1487 /* Construct and return a store merging pass object. */
1490 make_pass_store_merging (gcc::context
*ctxt
)
1492 return new pass_store_merging (ctxt
);
1497 namespace selftest
{
1499 /* Selftests for store merging helpers. */
1501 /* Assert that all elements of the byte arrays X and Y, both of length N
1505 verify_array_eq (unsigned char *x
, unsigned char *y
, unsigned int n
)
1507 for (unsigned int i
= 0; i
< n
; i
++)
1511 fprintf (stderr
, "Arrays do not match. X:\n");
1512 dump_char_array (stderr
, x
, n
);
1513 fprintf (stderr
, "Y:\n");
1514 dump_char_array (stderr
, y
, n
);
1516 ASSERT_EQ (x
[i
], y
[i
]);
1520 /* Test shift_bytes_in_array and that it carries bits across between
1524 verify_shift_bytes_in_array (void)
1527 00011111 | 11100000. */
1528 unsigned char orig
[2] = { 0xe0, 0x1f };
1529 unsigned char in
[2];
1530 memcpy (in
, orig
, sizeof orig
);
1532 unsigned char expected
[2] = { 0x80, 0x7f };
1533 shift_bytes_in_array (in
, sizeof (in
), 2);
1534 verify_array_eq (in
, expected
, sizeof (in
));
1536 memcpy (in
, orig
, sizeof orig
);
1537 memcpy (expected
, orig
, sizeof orig
);
1538 /* Check that shifting by zero doesn't change anything. */
1539 shift_bytes_in_array (in
, sizeof (in
), 0);
1540 verify_array_eq (in
, expected
, sizeof (in
));
1544 /* Test shift_bytes_in_array_right and that it carries bits across between
1548 verify_shift_bytes_in_array_right (void)
1551 00011111 | 11100000. */
1552 unsigned char orig
[2] = { 0x1f, 0xe0};
1553 unsigned char in
[2];
1554 memcpy (in
, orig
, sizeof orig
);
1555 unsigned char expected
[2] = { 0x07, 0xf8};
1556 shift_bytes_in_array_right (in
, sizeof (in
), 2);
1557 verify_array_eq (in
, expected
, sizeof (in
));
1559 memcpy (in
, orig
, sizeof orig
);
1560 memcpy (expected
, orig
, sizeof orig
);
1561 /* Check that shifting by zero doesn't change anything. */
1562 shift_bytes_in_array_right (in
, sizeof (in
), 0);
1563 verify_array_eq (in
, expected
, sizeof (in
));
1566 /* Test clear_bit_region that it clears exactly the bits asked and
1570 verify_clear_bit_region (void)
1572 /* Start with all bits set and test clearing various patterns in them. */
1573 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
1574 unsigned char in
[3];
1575 unsigned char expected
[3];
1576 memcpy (in
, orig
, sizeof in
);
1578 /* Check zeroing out all the bits. */
1579 clear_bit_region (in
, 0, 3 * BITS_PER_UNIT
);
1580 expected
[0] = expected
[1] = expected
[2] = 0;
1581 verify_array_eq (in
, expected
, sizeof in
);
1583 memcpy (in
, orig
, sizeof in
);
1584 /* Leave the first and last bits intact. */
1585 clear_bit_region (in
, 1, 3 * BITS_PER_UNIT
- 2);
1589 verify_array_eq (in
, expected
, sizeof in
);
1592 /* Test verify_clear_bit_region_be that it clears exactly the bits asked and
1596 verify_clear_bit_region_be (void)
1598 /* Start with all bits set and test clearing various patterns in them. */
1599 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
1600 unsigned char in
[3];
1601 unsigned char expected
[3];
1602 memcpy (in
, orig
, sizeof in
);
1604 /* Check zeroing out all the bits. */
1605 clear_bit_region_be (in
, BITS_PER_UNIT
- 1, 3 * BITS_PER_UNIT
);
1606 expected
[0] = expected
[1] = expected
[2] = 0;
1607 verify_array_eq (in
, expected
, sizeof in
);
1609 memcpy (in
, orig
, sizeof in
);
1610 /* Leave the first and last bits intact. */
1611 clear_bit_region_be (in
, BITS_PER_UNIT
- 2, 3 * BITS_PER_UNIT
- 2);
1615 verify_array_eq (in
, expected
, sizeof in
);
1619 /* Run all of the selftests within this file. */
1622 store_merging_c_tests (void)
1624 verify_shift_bytes_in_array ();
1625 verify_shift_bytes_in_array_right ();
1626 verify_clear_bit_region ();
1627 verify_clear_bit_region_be ();
1630 } // namespace selftest
1631 #endif /* CHECKING_P. */