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 /* Fill a byte array PTR of SZ elements with zeroes. This is to be used by
203 encode_tree_to_bitpos to zero-initialize most likely small arrays but
204 with a non-compile-time-constant size. */
207 zero_char_buf (unsigned char *ptr
, unsigned int sz
)
209 for (unsigned int i
= 0; i
< sz
; i
++)
213 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
214 bits between adjacent elements. AMNT should be within
217 00011111|11100000 << 2 = 01111111|10000000
218 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
221 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
226 unsigned char carry_over
= 0U;
227 unsigned char carry_mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- amnt
));
228 unsigned char clear_mask
= (~0U) << amnt
;
230 for (unsigned int i
= 0; i
< sz
; i
++)
232 unsigned prev_carry_over
= carry_over
;
234 = (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
239 ptr
[i
] &= clear_mask
;
240 ptr
[i
] |= prev_carry_over
;
245 /* Like shift_bytes_in_array but for big-endian.
246 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
247 bits between adjacent elements. AMNT should be within
250 00011111|11100000 >> 2 = 00000111|11111000
251 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
254 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
260 unsigned char carry_over
= 0U;
261 unsigned char carry_mask
= ~(~0U << amnt
);
263 for (unsigned int i
= 0; i
< sz
; i
++)
265 unsigned prev_carry_over
= carry_over
;
267 = (ptr
[i
] & carry_mask
);
269 carry_over
<<= ((unsigned char)BITS_PER_UNIT
- amnt
);
271 ptr
[i
] |= prev_carry_over
;
275 /* Clear out LEN bits starting from bit START in the byte array
276 PTR. This clears the bits to the *right* from START.
277 START must be within [0, BITS_PER_UNIT) and counts starting from
278 the least significant bit. */
281 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
286 /* Clear len bits to the right of start. */
287 else if (len
<= start
+ 1)
289 unsigned char mask
= (~(~0U << len
));
290 mask
= mask
<< (start
+ 1U - len
);
293 else if (start
!= BITS_PER_UNIT
- 1)
295 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
296 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
297 len
- (start
% BITS_PER_UNIT
) - 1);
299 else if (start
== BITS_PER_UNIT
- 1
300 && len
> BITS_PER_UNIT
)
302 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
303 for (unsigned int i
= 0; i
< nbytes
; i
++)
305 if (len
% BITS_PER_UNIT
!= 0)
306 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
307 len
% BITS_PER_UNIT
);
313 /* In the byte array PTR clear the bit region starting at bit
314 START and is LEN bits wide.
315 For regions spanning multiple bytes do this recursively until we reach
316 zero LEN or a region contained within a single byte. */
319 clear_bit_region (unsigned char *ptr
, unsigned int start
,
322 /* Degenerate base case. */
325 else if (start
>= BITS_PER_UNIT
)
326 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
327 /* Second base case. */
328 else if ((start
+ len
) <= BITS_PER_UNIT
)
330 unsigned char mask
= (~0U) << ((unsigned char)(BITS_PER_UNIT
- len
));
331 mask
>>= BITS_PER_UNIT
- (start
+ len
);
337 /* Clear most significant bits in a byte and proceed with the next byte. */
340 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
341 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
));
343 /* Whole bytes need to be cleared. */
344 else if (start
== 0 && len
> BITS_PER_UNIT
)
346 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
347 /* We could recurse on each byte but do the loop here to avoid
348 recursing too deep. */
349 for (unsigned int i
= 0; i
< nbytes
; i
++)
351 /* Clear the remaining sub-byte region if there is one. */
352 if (len
% BITS_PER_UNIT
!= 0)
353 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
359 /* Write BITLEN bits of EXPR to the byte array PTR at
360 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
361 Return true if the operation succeeded. */
364 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
365 unsigned int total_bytes
)
367 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
369 bool sub_byte_op_p
= (bitlen
% BITS_PER_UNIT
) || (bitpos
% BITS_PER_UNIT
)
370 || mode_for_size (bitlen
, MODE_INT
, 0) == BLKmode
;
373 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
, 0)
377 We are writing a non byte-sized quantity or at a position that is not
379 |--------|--------|--------| ptr + first_byte
381 xxx xxxxxxxx xxx< bp>
384 First native_encode_expr EPXR into a temporary buffer and shift each
385 byte in the buffer by 'bp' (carrying the bits over as necessary).
386 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
387 <------bitlen---->< bp>
388 Then we clear the destination bits:
389 |---00000|00000000|000-----| ptr + first_byte
390 <-------bitlen--->< bp>
392 Finally we ORR the bytes of the shifted EXPR into the cleared region:
393 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
396 We are writing a non byte-sized quantity or at a position that is not
398 ptr + first_byte |--------|--------|--------|
400 <bp >xxx xxxxxxxx xxx
403 First native_encode_expr EPXR into a temporary buffer and shift each
404 byte in the buffer to the right by (carrying the bits over as necessary).
405 We shift by as much as needed to align the most significant bit of EXPR
407 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
408 <---bitlen----> <bp ><-----bitlen----->
409 Then we clear the destination bits:
410 ptr + first_byte |-----000||00000000||00000---|
411 <bp ><-------bitlen----->
413 Finally we ORR the bytes of the shifted EXPR into the cleared region:
414 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
415 The awkwardness comes from the fact that bitpos is counted from the
416 most significant bit of a byte. */
418 /* Allocate an extra byte so that we have space to shift into. */
419 unsigned int byte_size
= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (expr
))) + 1;
420 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
421 zero_char_buf (tmpbuf
, byte_size
);
422 /* The store detection code should only have allowed constants that are
423 accepted by native_encode_expr. */
424 if (native_encode_expr (expr
, tmpbuf
, byte_size
, 0) == 0)
427 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
428 bytes to write. This means it can write more than
429 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
430 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
431 bitlen and zero out the bits that are not relevant as well (that may
432 contain a sign bit due to sign-extension). */
434 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
436 || bitlen
% BITS_PER_UNIT
!= 0)
438 /* On big-endian the padding is at the 'front' so just skip the initial
440 if (BYTES_BIG_ENDIAN
)
443 byte_size
-= padding
;
444 if (bitlen
% BITS_PER_UNIT
!= 0)
446 if (BYTES_BIG_ENDIAN
)
447 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
448 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
450 clear_bit_region (tmpbuf
, bitlen
,
451 byte_size
* BITS_PER_UNIT
- bitlen
);
455 /* Clear the bit region in PTR where the bits from TMPBUF will be
457 if (BYTES_BIG_ENDIAN
)
458 clear_bit_region_be (ptr
+ first_byte
,
459 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
461 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
464 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
465 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
467 bool skip_byte
= false;
468 if (BYTES_BIG_ENDIAN
)
470 /* BITPOS and BITLEN are exactly aligned and no shifting
472 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
473 || (bitpos_mod
== 0 && bitlen_mod
== 0))
477 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
478 of the value until it aligns with 'bp' in the next byte over. */
479 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
481 shift_amnt
= bitlen_mod
+ bitpos_mod
;
482 skip_byte
= bitlen_mod
!= 0;
487 Shift the value right within the same byte so it aligns with 'bp'. */
489 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
492 shift_amnt
= bitpos
% BITS_PER_UNIT
;
494 /* Create the shifted version of EXPR. */
495 if (!BYTES_BIG_ENDIAN
)
496 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
499 gcc_assert (BYTES_BIG_ENDIAN
);
500 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
501 /* If shifting right forced us to move into the next byte skip the now
510 /* Insert the bits from TMPBUF. */
511 for (unsigned int i
= 0; i
< byte_size
; i
++)
512 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
517 /* Sorting function for store_immediate_info objects.
518 Sorts them by bitposition. */
521 sort_by_bitpos (const void *x
, const void *y
)
523 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
524 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
526 if ((*tmp
)->bitpos
<= (*tmp2
)->bitpos
)
528 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
534 /* Sorting function for store_immediate_info objects.
535 Sorts them by the order field. */
538 sort_by_order (const void *x
, const void *y
)
540 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
541 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
543 if ((*tmp
)->order
< (*tmp2
)->order
)
545 else if ((*tmp
)->order
> (*tmp2
)->order
)
551 /* Initialize a merged_store_group object from a store_immediate_info
554 merged_store_group::merged_store_group (store_immediate_info
*info
)
556 start
= info
->bitpos
;
557 width
= info
->bitsize
;
558 /* VAL has memory allocated for it in apply_stores once the group
559 width has been finalized. */
561 align
= get_object_alignment (gimple_assign_lhs (info
->stmt
));
563 stores
.safe_push (info
);
564 last_stmt
= info
->stmt
;
565 last_order
= info
->order
;
566 first_stmt
= last_stmt
;
567 first_order
= last_order
;
571 merged_store_group::~merged_store_group ()
577 /* Merge a store recorded by INFO into this merged store.
578 The store is not overlapping with the existing recorded
582 merged_store_group::merge_into (store_immediate_info
*info
)
584 unsigned HOST_WIDE_INT wid
= info
->bitsize
;
585 /* Make sure we're inserting in the position we think we're inserting. */
586 gcc_assert (info
->bitpos
== start
+ width
);
589 gimple
*stmt
= info
->stmt
;
590 stores
.safe_push (info
);
591 if (info
->order
> last_order
)
593 last_order
= info
->order
;
596 else if (info
->order
< first_order
)
598 first_order
= info
->order
;
603 /* Merge a store described by INFO into this merged store.
604 INFO overlaps in some way with the current store (i.e. it's not contiguous
605 which is handled by merged_store_group::merge_into). */
608 merged_store_group::merge_overlapping (store_immediate_info
*info
)
610 gimple
*stmt
= info
->stmt
;
611 stores
.safe_push (info
);
613 /* If the store extends the size of the group, extend the width. */
614 if ((info
->bitpos
+ info
->bitsize
) > (start
+ width
))
615 width
+= info
->bitpos
+ info
->bitsize
- (start
+ width
);
617 if (info
->order
> last_order
)
619 last_order
= info
->order
;
622 else if (info
->order
< first_order
)
624 first_order
= info
->order
;
629 /* Go through all the recorded stores in this group in program order and
630 apply their values to the VAL byte array to create the final merged
631 value. Return true if the operation succeeded. */
634 merged_store_group::apply_stores ()
636 /* The total width of the stores must add up to a whole number of bytes
637 and start at a byte boundary. We don't support emitting bitfield
638 references for now. Also, make sure we have more than one store
639 in the group, otherwise we cannot merge anything. */
640 if (width
% BITS_PER_UNIT
!= 0
641 || start
% BITS_PER_UNIT
!= 0
642 || stores
.length () == 1)
645 stores
.qsort (sort_by_order
);
646 struct store_immediate_info
*info
;
648 /* Create a buffer of a size that is 2 times the number of bytes we're
649 storing. That way native_encode_expr can write power-of-2-sized
650 chunks without overrunning. */
652 = 2 * (ROUND_UP (width
, BITS_PER_UNIT
) / BITS_PER_UNIT
);
653 val
= XCNEWVEC (unsigned char, buf_size
);
655 FOR_EACH_VEC_ELT (stores
, i
, info
)
657 unsigned int pos_in_buffer
= info
->bitpos
- start
;
658 bool ret
= encode_tree_to_bitpos (gimple_assign_rhs1 (info
->stmt
),
660 pos_in_buffer
, buf_size
);
661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
665 fprintf (dump_file
, "After writing ");
666 print_generic_expr (dump_file
,
667 gimple_assign_rhs1 (info
->stmt
), 0);
668 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
669 " at position %d the merged region contains:\n",
670 info
->bitsize
, pos_in_buffer
);
671 dump_char_array (dump_file
, val
, buf_size
);
674 fprintf (dump_file
, "Failed to merge stores\n");
682 /* Structure describing the store chain. */
684 struct imm_store_chain_info
687 auto_vec
<struct store_immediate_info
*> m_store_info
;
688 auto_vec
<merged_store_group
*> m_merged_store_groups
;
690 imm_store_chain_info (tree b_a
) : base_addr (b_a
) {}
691 bool terminate_and_process_chain ();
692 bool coalesce_immediate_stores ();
693 bool output_merged_store (merged_store_group
*);
694 bool output_merged_stores ();
697 const pass_data pass_data_tree_store_merging
= {
698 GIMPLE_PASS
, /* type */
699 "store-merging", /* name */
700 OPTGROUP_NONE
, /* optinfo_flags */
701 TV_GIMPLE_STORE_MERGING
, /* tv_id */
702 PROP_ssa
, /* properties_required */
703 0, /* properties_provided */
704 0, /* properties_destroyed */
705 0, /* todo_flags_start */
706 TODO_update_ssa
, /* todo_flags_finish */
709 class pass_store_merging
: public gimple_opt_pass
712 pass_store_merging (gcc::context
*ctxt
)
713 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
)
717 /* Pass not supported for PDP-endianness. */
721 return flag_store_merging
&& (WORDS_BIG_ENDIAN
== BYTES_BIG_ENDIAN
);
724 virtual unsigned int execute (function
*);
727 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
729 bool terminate_and_process_all_chains ();
730 bool terminate_all_aliasing_chains (imm_store_chain_info
**,
732 bool terminate_and_release_chain (imm_store_chain_info
*);
733 }; // class pass_store_merging
735 /* Terminate and process all recorded chains. Return true if any changes
739 pass_store_merging::terminate_and_process_all_chains ()
741 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
744 for (; iter
!= m_stores
.end (); ++iter
)
745 ret
|= terminate_and_release_chain ((*iter
).second
);
750 /* Terminate all chains that are affected by the assignment to DEST, appearing
751 in statement STMT and ultimately points to the object BASE. Return true if
752 at least one aliasing chain was terminated. BASE and DEST are allowed to
753 be NULL_TREE. In that case the aliasing checks are performed on the whole
754 statement rather than a particular operand in it. VAR_OFFSET_P signifies
755 whether STMT represents a store to BASE offset by a variable amount.
756 If that is the case we have to terminate any chain anchored at BASE. */
759 pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
766 /* If the statement doesn't touch memory it can't alias. */
767 if (!gimple_vuse (stmt
))
770 /* Check if the assignment destination (BASE) is part of a store chain.
771 This is to catch non-constant stores to destinations that may be part
775 /* We have a chain at BASE and we're writing to [BASE + <variable>].
776 This can interfere with any of the stores so terminate
780 terminate_and_release_chain (*chain_info
);
783 /* Otherwise go through every store in the chain to see if it
784 aliases with any of them. */
787 struct store_immediate_info
*info
;
789 FOR_EACH_VEC_ELT ((*chain_info
)->m_store_info
, i
, info
)
791 if (ref_maybe_used_by_stmt_p (stmt
,
792 gimple_assign_lhs (info
->stmt
))
793 || stmt_may_clobber_ref_p (stmt
,
794 gimple_assign_lhs (info
->stmt
)))
796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
799 "stmt causes chain termination:\n");
800 print_gimple_stmt (dump_file
, stmt
, 0, 0);
802 terminate_and_release_chain (*chain_info
);
810 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*>::iterator iter
813 /* Check for aliasing with all other store chains. */
814 for (; iter
!= m_stores
.end (); ++iter
)
816 /* We already checked all the stores in chain_info and terminated the
817 chain if necessary. Skip it here. */
818 if (chain_info
&& (*chain_info
) == (*iter
).second
)
821 /* We can't use the base object here as that does not reliably exist.
822 Build a ao_ref from the base object address (if we know the
823 minimum and maximum offset and the maximum size we could improve
826 ao_ref_init_from_ptr_and_size (&chain_ref
, (*iter
).first
, NULL_TREE
);
827 if (ref_maybe_used_by_stmt_p (stmt
, &chain_ref
)
828 || stmt_may_clobber_ref_p_1 (stmt
, &chain_ref
))
830 terminate_and_release_chain ((*iter
).second
);
838 /* Helper function. Terminate the recorded chain storing to base object
839 BASE. Return true if the merging and output was successful. The m_stores
840 entry is removed after the processing in any case. */
843 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
845 bool ret
= chain_info
->terminate_and_process_chain ();
846 m_stores
.remove (chain_info
->base_addr
);
851 /* Go through the candidate stores recorded in m_store_info and merge them
852 into merged_store_group objects recorded into m_merged_store_groups
853 representing the widened stores. Return true if coalescing was successful
854 and the number of widened stores is fewer than the original number
858 imm_store_chain_info::coalesce_immediate_stores ()
860 /* Anything less can't be processed. */
861 if (m_store_info
.length () < 2)
864 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 fprintf (dump_file
, "Attempting to coalesce %u stores in chain.\n",
866 m_store_info
.length ());
868 store_immediate_info
*info
;
871 /* Order the stores by the bitposition they write to. */
872 m_store_info
.qsort (sort_by_bitpos
);
874 info
= m_store_info
[0];
875 merged_store_group
*merged_store
= new merged_store_group (info
);
877 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
881 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
882 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:\n",
883 i
, info
->bitsize
, info
->bitpos
);
884 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
), 0);
885 fprintf (dump_file
, "\n------------\n");
893 Overlapping stores. */
894 unsigned HOST_WIDE_INT start
= info
->bitpos
;
895 if (IN_RANGE (start
, merged_store
->start
,
896 merged_store
->start
+ merged_store
->width
- 1))
898 merged_store
->merge_overlapping (info
);
902 /* |---store 1---| <gap> |---store 2---|.
903 Gap between stores. Start a new group. */
904 if (start
!= merged_store
->start
+ merged_store
->width
)
906 /* Try to apply all the stores recorded for the group to determine
907 the bitpattern they write and discard it if that fails.
908 This will also reject single-store groups. */
909 if (!merged_store
->apply_stores ())
912 m_merged_store_groups
.safe_push (merged_store
);
914 merged_store
= new merged_store_group (info
);
919 /* |---store 1---||---store 2---|
920 This store is consecutive to the previous one.
921 Merge it into the current store group. */
922 merged_store
->merge_into (info
);
925 /* Record or discard the last store group. */
926 if (!merged_store
->apply_stores ())
929 m_merged_store_groups
.safe_push (merged_store
);
931 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
933 = !m_merged_store_groups
.is_empty ()
934 && m_merged_store_groups
.length () < m_store_info
.length ();
936 if (success
&& dump_file
)
937 fprintf (dump_file
, "Coalescing successful!\n"
938 "Merged into %u stores\n",
939 m_merged_store_groups
.length ());
944 /* Return the type to use for the merged stores described by STMTS.
945 This is needed to get the alias sets right. */
948 get_alias_type_for_stmts (auto_vec
<gimple
*> &stmts
)
952 tree lhs
= gimple_assign_lhs (stmts
[0]);
953 tree type
= reference_alias_ptr_type (lhs
);
955 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
960 lhs
= gimple_assign_lhs (stmt
);
961 tree type1
= reference_alias_ptr_type (lhs
);
962 if (!alias_ptr_types_compatible_p (type
, type1
))
963 return ptr_type_node
;
968 /* Return the location_t information we can find among the statements
972 get_location_for_stmts (auto_vec
<gimple
*> &stmts
)
977 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
978 if (gimple_has_location (stmt
))
979 return gimple_location (stmt
);
981 return UNKNOWN_LOCATION
;
984 /* Used to decribe a store resulting from splitting a wide store in smaller
985 regularly-sized stores in split_group. */
989 unsigned HOST_WIDE_INT bytepos
;
990 unsigned HOST_WIDE_INT size
;
991 unsigned HOST_WIDE_INT align
;
992 auto_vec
<gimple
*> orig_stmts
;
993 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
994 unsigned HOST_WIDE_INT
);
997 /* Simple constructor. */
999 split_store::split_store (unsigned HOST_WIDE_INT bp
,
1000 unsigned HOST_WIDE_INT sz
,
1001 unsigned HOST_WIDE_INT al
)
1002 : bytepos (bp
), size (sz
), align (al
)
1004 orig_stmts
.create (0);
1007 /* Record all statements corresponding to stores in GROUP that write to
1008 the region starting at BITPOS and is of size BITSIZE. Record such
1009 statements in STMTS. The stores in GROUP must be sorted by
1013 find_constituent_stmts (struct merged_store_group
*group
,
1014 auto_vec
<gimple
*> &stmts
,
1015 unsigned HOST_WIDE_INT bitpos
,
1016 unsigned HOST_WIDE_INT bitsize
)
1018 struct store_immediate_info
*info
;
1020 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
1021 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
1023 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
1024 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
1025 if (stmt_end
< bitpos
)
1027 /* The stores in GROUP are ordered by bitposition so if we're past
1028 the region for this group return early. */
1029 if (stmt_start
> end
)
1032 if (IN_RANGE (stmt_start
, bitpos
, bitpos
+ bitsize
)
1033 || IN_RANGE (stmt_end
, bitpos
, end
)
1034 /* The statement writes a region that completely encloses the region
1035 that this group writes. Unlikely to occur but let's
1037 || IN_RANGE (bitpos
, stmt_start
, stmt_end
))
1038 stmts
.safe_push (info
->stmt
);
1042 /* Split a merged store described by GROUP by populating the SPLIT_STORES
1043 vector with split_store structs describing the byte offset (from the base),
1044 the bit size and alignment of each store as well as the original statements
1045 involved in each such split group.
1046 This is to separate the splitting strategy from the statement
1047 building/emission/linking done in output_merged_store.
1048 At the moment just start with the widest possible size and keep emitting
1049 the widest we can until we have emitted all the bytes, halving the size
1050 when appropriate. */
1053 split_group (merged_store_group
*group
,
1054 auto_vec
<struct split_store
*> &split_stores
)
1056 unsigned HOST_WIDE_INT pos
= group
->start
;
1057 unsigned HOST_WIDE_INT size
= group
->width
;
1058 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
1059 unsigned HOST_WIDE_INT align
= group
->align
;
1061 /* We don't handle partial bitfields for now. We shouldn't have
1062 reached this far. */
1063 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
1065 bool allow_unaligned
1066 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
1068 unsigned int try_size
= MAX_STORE_BITSIZE
;
1069 while (try_size
> size
1070 || (!allow_unaligned
1071 && try_size
> align
))
1074 if (try_size
< BITS_PER_UNIT
)
1078 unsigned HOST_WIDE_INT try_pos
= bytepos
;
1079 group
->stores
.qsort (sort_by_bitpos
);
1083 struct split_store
*store
= new split_store (try_pos
, try_size
, align
);
1084 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
1085 find_constituent_stmts (group
, store
->orig_stmts
, try_bitpos
, try_size
);
1086 split_stores
.safe_push (store
);
1088 try_pos
+= try_size
/ BITS_PER_UNIT
;
1092 while (size
< try_size
)
1098 /* Given a merged store group GROUP output the widened version of it.
1099 The store chain is against the base object BASE.
1100 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
1101 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
1102 Make sure that the number of statements output is less than the number of
1103 original statements. If a better sequence is possible emit it and
1107 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
1109 unsigned HOST_WIDE_INT start_byte_pos
= group
->start
/ BITS_PER_UNIT
;
1111 unsigned int orig_num_stmts
= group
->stores
.length ();
1112 if (orig_num_stmts
< 2)
1115 auto_vec
<struct split_store
*> split_stores
;
1116 split_stores
.create (0);
1117 if (!split_group (group
, split_stores
))
1120 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
1121 gimple_seq seq
= NULL
;
1122 unsigned int num_stmts
= 0;
1123 tree last_vdef
, new_vuse
;
1124 last_vdef
= gimple_vdef (group
->last_stmt
);
1125 new_vuse
= gimple_vuse (group
->last_stmt
);
1127 gimple
*stmt
= NULL
;
1128 /* The new SSA names created. Keep track of them so that we can free them
1129 if we decide to not use the new sequence. */
1130 auto_vec
<tree
> new_ssa_names
;
1131 split_store
*split_store
;
1135 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &seq
,
1136 is_gimple_mem_ref_addr
, NULL_TREE
);
1137 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1139 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
1140 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
1141 unsigned HOST_WIDE_INT align
= split_store
->align
;
1142 tree offset_type
= get_alias_type_for_stmts (split_store
->orig_stmts
);
1143 location_t loc
= get_location_for_stmts (split_store
->orig_stmts
);
1145 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
1146 int_type
= build_aligned_type (int_type
, align
);
1147 tree dest
= fold_build2 (MEM_REF
, int_type
, addr
,
1148 build_int_cst (offset_type
, try_pos
));
1150 tree src
= native_interpret_expr (int_type
,
1151 group
->val
+ try_pos
- start_byte_pos
,
1154 stmt
= gimple_build_assign (dest
, src
);
1155 gimple_set_location (stmt
, loc
);
1156 gimple_set_vuse (stmt
, new_vuse
);
1157 gimple_seq_add_stmt_without_update (&seq
, stmt
);
1159 /* We didn't manage to reduce the number of statements. Bail out. */
1160 if (++num_stmts
== orig_num_stmts
)
1162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1164 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
1165 " Not profitable to emit new sequence.\n",
1168 unsigned int ssa_count
;
1170 /* Don't forget to cleanup the temporary SSA names. */
1171 FOR_EACH_VEC_ELT (new_ssa_names
, ssa_count
, ssa_name
)
1172 release_ssa_name (ssa_name
);
1179 if (i
< split_stores
.length () - 1)
1181 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
1182 new_ssa_names
.safe_push (new_vdef
);
1185 new_vdef
= last_vdef
;
1187 gimple_set_vdef (stmt
, new_vdef
);
1188 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
1189 new_vuse
= new_vdef
;
1192 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
1202 "New sequence of %u stmts to replace old one of %u stmts\n",
1203 num_stmts
, orig_num_stmts
);
1204 if (dump_flags
& TDF_DETAILS
)
1205 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1207 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
1212 /* Process the merged_store_group objects created in the coalescing phase.
1213 The stores are all against the base object BASE.
1214 Try to output the widened stores and delete the original statements if
1215 successful. Return true iff any changes were made. */
1218 imm_store_chain_info::output_merged_stores ()
1221 merged_store_group
*merged_store
;
1223 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
1225 if (output_merged_store (merged_store
))
1228 store_immediate_info
*store
;
1229 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
1231 gimple
*stmt
= store
->stmt
;
1232 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1233 gsi_remove (&gsi
, true);
1234 if (stmt
!= merged_store
->last_stmt
)
1236 unlink_stmt_vdef (stmt
);
1237 release_defs (stmt
);
1243 if (ret
&& dump_file
)
1244 fprintf (dump_file
, "Merging successful!\n");
1249 /* Coalesce the store_immediate_info objects recorded against the base object
1250 BASE in the first phase and output them.
1251 Delete the allocated structures.
1252 Return true if any changes were made. */
1255 imm_store_chain_info::terminate_and_process_chain ()
1257 /* Process store chain. */
1259 if (m_store_info
.length () > 1)
1261 ret
= coalesce_immediate_stores ();
1263 ret
= output_merged_stores ();
1266 /* Delete all the entries we allocated ourselves. */
1267 store_immediate_info
*info
;
1269 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
1272 merged_store_group
*merged_info
;
1273 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
1279 /* Return true iff LHS is a destination potentially interesting for
1280 store merging. In practice these are the codes that get_inner_reference
1284 lhs_valid_for_store_merging_p (tree lhs
)
1286 tree_code code
= TREE_CODE (lhs
);
1288 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
1289 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
1295 /* Return true if the tree RHS is a constant we want to consider
1296 during store merging. In practice accept all codes that
1297 native_encode_expr accepts. */
1300 rhs_valid_for_store_merging_p (tree rhs
)
1302 tree type
= TREE_TYPE (rhs
);
1303 if (TREE_CODE_CLASS (TREE_CODE (rhs
)) != tcc_constant
1304 || !can_native_encode_type_p (type
))
1310 /* Entry point for the pass. Go over each basic block recording chains of
1311 immediate stores. Upon encountering a terminating statement (as defined
1312 by stmt_terminates_chain_p) process the recorded stores and emit the widened
1316 pass_store_merging::execute (function
*fun
)
1319 hash_set
<gimple
*> orig_stmts
;
1321 FOR_EACH_BB_FN (bb
, fun
)
1323 gimple_stmt_iterator gsi
;
1324 unsigned HOST_WIDE_INT num_statements
= 0;
1325 /* Record the original statements so that we can keep track of
1326 statements emitted in this pass and not re-process new
1328 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1330 if (is_gimple_debug (gsi_stmt (gsi
)))
1333 if (++num_statements
> 2)
1337 if (num_statements
< 2)
1340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1341 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
1343 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1345 gimple
*stmt
= gsi_stmt (gsi
);
1347 if (gimple_has_volatile_ops (stmt
))
1349 /* Terminate all chains. */
1350 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1351 fprintf (dump_file
, "Volatile access terminates "
1353 terminate_and_process_all_chains ();
1357 if (is_gimple_debug (stmt
))
1360 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
1361 && !stmt_can_throw_internal (stmt
)
1362 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
1364 tree lhs
= gimple_assign_lhs (stmt
);
1365 tree rhs
= gimple_assign_rhs1 (stmt
);
1367 HOST_WIDE_INT bitsize
, bitpos
;
1369 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
1370 tree offset
, base_addr
;
1372 = get_inner_reference (lhs
, &bitsize
, &bitpos
, &offset
, &mode
,
1373 &unsignedp
, &reversep
, &volatilep
);
1374 /* As a future enhancement we could handle stores with the same
1376 bool invalid
= reversep
1377 || ((bitsize
> MAX_BITSIZE_MODE_ANY_INT
)
1378 && (TREE_CODE (rhs
) != INTEGER_CST
))
1379 || !rhs_valid_for_store_merging_p (rhs
);
1381 /* We do not want to rewrite TARGET_MEM_REFs. */
1382 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
1384 /* In some cases get_inner_reference may return a
1385 MEM_REF [ptr + byteoffset]. For the purposes of this pass
1386 canonicalize the base_addr to MEM_REF [ptr] and take
1387 byteoffset into account in the bitpos. This occurs in
1388 PR 23684 and this way we can catch more chains. */
1389 else if (TREE_CODE (base_addr
) == MEM_REF
)
1391 offset_int bit_off
, byte_off
= mem_ref_offset (base_addr
);
1392 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
1394 if (!wi::neg_p (bit_off
) && wi::fits_shwi_p (bit_off
))
1395 bitpos
= bit_off
.to_shwi ();
1398 base_addr
= TREE_OPERAND (base_addr
, 0);
1400 /* get_inner_reference returns the base object, get at its
1406 base_addr
= build_fold_addr_expr (base_addr
);
1410 && offset
!= NULL_TREE
)
1412 /* If the access is variable offset then a base
1413 decl has to be address-taken to be able to
1414 emit pointer-based stores to it.
1415 ??? We might be able to get away with
1416 re-using the original base up to the first
1417 variable part and then wrapping that inside
1419 tree base
= get_base_address (base_addr
);
1422 && ! TREE_ADDRESSABLE (base
)))
1425 base_addr
= build2 (POINTER_PLUS_EXPR
,
1426 TREE_TYPE (base_addr
),
1430 struct imm_store_chain_info
**chain_info
1431 = m_stores
.get (base_addr
);
1435 store_immediate_info
*info
;
1438 info
= new store_immediate_info (
1439 bitsize
, bitpos
, stmt
,
1440 (*chain_info
)->m_store_info
.length ());
1441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1444 "Recording immediate store from stmt:\n");
1445 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1447 (*chain_info
)->m_store_info
.safe_push (info
);
1448 /* If we reach the limit of stores to merge in a chain
1449 terminate and process the chain now. */
1450 if ((*chain_info
)->m_store_info
.length ()
1452 PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
1454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1456 "Reached maximum number of statements"
1458 terminate_and_release_chain (*chain_info
);
1463 /* Store aliases any existing chain? */
1464 terminate_all_aliasing_chains (chain_info
, false, stmt
);
1465 /* Start a new chain. */
1466 struct imm_store_chain_info
*new_chain
1467 = new imm_store_chain_info (base_addr
);
1468 info
= new store_immediate_info (bitsize
, bitpos
,
1470 new_chain
->m_store_info
.safe_push (info
);
1471 m_stores
.put (base_addr
, new_chain
);
1472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1475 "Starting new chain with statement:\n");
1476 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1477 fprintf (dump_file
, "The base object is:\n");
1478 print_generic_expr (dump_file
, base_addr
, 0);
1479 fprintf (dump_file
, "\n");
1483 terminate_all_aliasing_chains (chain_info
,
1484 offset
!= NULL_TREE
, stmt
);
1489 terminate_all_aliasing_chains (NULL
, false, stmt
);
1491 terminate_and_process_all_chains ();
1498 /* Construct and return a store merging pass object. */
1501 make_pass_store_merging (gcc::context
*ctxt
)
1503 return new pass_store_merging (ctxt
);
1508 namespace selftest
{
1510 /* Selftests for store merging helpers. */
1512 /* Assert that all elements of the byte arrays X and Y, both of length N
1516 verify_array_eq (unsigned char *x
, unsigned char *y
, unsigned int n
)
1518 for (unsigned int i
= 0; i
< n
; i
++)
1522 fprintf (stderr
, "Arrays do not match. X:\n");
1523 dump_char_array (stderr
, x
, n
);
1524 fprintf (stderr
, "Y:\n");
1525 dump_char_array (stderr
, y
, n
);
1527 ASSERT_EQ (x
[i
], y
[i
]);
1531 /* Test shift_bytes_in_array and that it carries bits across between
1535 verify_shift_bytes_in_array (void)
1538 00011111 | 11100000. */
1539 unsigned char orig
[2] = { 0xe0, 0x1f };
1540 unsigned char in
[2];
1541 memcpy (in
, orig
, sizeof orig
);
1543 unsigned char expected
[2] = { 0x80, 0x7f };
1544 shift_bytes_in_array (in
, sizeof (in
), 2);
1545 verify_array_eq (in
, expected
, sizeof (in
));
1547 memcpy (in
, orig
, sizeof orig
);
1548 memcpy (expected
, orig
, sizeof orig
);
1549 /* Check that shifting by zero doesn't change anything. */
1550 shift_bytes_in_array (in
, sizeof (in
), 0);
1551 verify_array_eq (in
, expected
, sizeof (in
));
1555 /* Test shift_bytes_in_array_right and that it carries bits across between
1559 verify_shift_bytes_in_array_right (void)
1562 00011111 | 11100000. */
1563 unsigned char orig
[2] = { 0x1f, 0xe0};
1564 unsigned char in
[2];
1565 memcpy (in
, orig
, sizeof orig
);
1566 unsigned char expected
[2] = { 0x07, 0xf8};
1567 shift_bytes_in_array_right (in
, sizeof (in
), 2);
1568 verify_array_eq (in
, expected
, sizeof (in
));
1570 memcpy (in
, orig
, sizeof orig
);
1571 memcpy (expected
, orig
, sizeof orig
);
1572 /* Check that shifting by zero doesn't change anything. */
1573 shift_bytes_in_array_right (in
, sizeof (in
), 0);
1574 verify_array_eq (in
, expected
, sizeof (in
));
1577 /* Test clear_bit_region that it clears exactly the bits asked and
1581 verify_clear_bit_region (void)
1583 /* Start with all bits set and test clearing various patterns in them. */
1584 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
1585 unsigned char in
[3];
1586 unsigned char expected
[3];
1587 memcpy (in
, orig
, sizeof in
);
1589 /* Check zeroing out all the bits. */
1590 clear_bit_region (in
, 0, 3 * BITS_PER_UNIT
);
1591 expected
[0] = expected
[1] = expected
[2] = 0;
1592 verify_array_eq (in
, expected
, sizeof in
);
1594 memcpy (in
, orig
, sizeof in
);
1595 /* Leave the first and last bits intact. */
1596 clear_bit_region (in
, 1, 3 * BITS_PER_UNIT
- 2);
1600 verify_array_eq (in
, expected
, sizeof in
);
1603 /* Test verify_clear_bit_region_be that it clears exactly the bits asked and
1607 verify_clear_bit_region_be (void)
1609 /* Start with all bits set and test clearing various patterns in them. */
1610 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
1611 unsigned char in
[3];
1612 unsigned char expected
[3];
1613 memcpy (in
, orig
, sizeof in
);
1615 /* Check zeroing out all the bits. */
1616 clear_bit_region_be (in
, BITS_PER_UNIT
- 1, 3 * BITS_PER_UNIT
);
1617 expected
[0] = expected
[1] = expected
[2] = 0;
1618 verify_array_eq (in
, expected
, sizeof in
);
1620 memcpy (in
, orig
, sizeof in
);
1621 /* Leave the first and last bits intact. */
1622 clear_bit_region_be (in
, BITS_PER_UNIT
- 2, 3 * BITS_PER_UNIT
- 2);
1626 verify_array_eq (in
, expected
, sizeof in
);
1630 /* Run all of the selftests within this file. */
1633 store_merging_c_tests (void)
1635 verify_shift_bytes_in_array ();
1636 verify_shift_bytes_in_array_right ();
1637 verify_clear_bit_region ();
1638 verify_clear_bit_region_be ();
1641 } // namespace selftest
1642 #endif /* CHECKING_P. */