1 /* GIMPLE store merging and byte swapping passes.
2 Copyright (C) 2009-2018 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 the store merging pass is to combine multiple memory stores
22 of constant values, values loaded from memory, bitwise operations on those,
23 or bit-field values, to consecutive locations, into fewer wider stores.
25 For example, if we have a sequence peforming four byte stores to
26 consecutive memory locations:
31 we can transform this into a single 4-byte store if the target supports it:
32 [p] := imm1:imm2:imm3:imm4 concatenated according to endianness.
39 if there is no overlap can be transformed into a single 4-byte
40 load followed by single 4-byte store.
44 [p + 1B] := [q + 1B] ^ imm2;
45 [p + 2B] := [q + 2B] ^ imm3;
46 [p + 3B] := [q + 3B] ^ imm4;
47 if there is no overlap can be transformed into a single 4-byte
48 load, xored with imm1:imm2:imm3:imm4 and stored using a single 4-byte store.
52 [p:31] := val & 0x7FFFFFFF;
53 we can transform this into a single 4-byte store if the target supports it:
54 [p] := imm:(val & 0x7FFFFFFF) concatenated according to endianness.
56 The algorithm is applied to each basic block in three phases:
58 1) Scan through the basic block and record assignments to destinations
59 that can be expressed as a store to memory of a certain size at a certain
60 bit offset from base expressions we can handle. For bit-fields we also
61 record the surrounding bit region, i.e. bits that could be stored in
62 a read-modify-write operation when storing the bit-field. Record store
63 chains to different bases in a hash_map (m_stores) and make sure to
64 terminate such chains when appropriate (for example when when the stored
65 values get used subsequently).
66 These stores can be a result of structure element initializers, array stores
67 etc. A store_immediate_info object is recorded for every such store.
68 Record as many such assignments to a single base as possible until a
69 statement that interferes with the store sequence is encountered.
70 Each store has up to 2 operands, which can be a either constant, a memory
71 load or an SSA name, from which the value to be stored can be computed.
72 At most one of the operands can be a constant. The operands are recorded
73 in store_operand_info struct.
75 2) Analyze the chains of stores recorded in phase 1) (i.e. the vector of
76 store_immediate_info objects) and coalesce contiguous stores into
77 merged_store_group objects. For bit-field stores, we don't need to
78 require the stores to be contiguous, just their surrounding bit regions
79 have to be contiguous. If the expression being stored is different
80 between adjacent stores, such as one store storing a constant and
81 following storing a value loaded from memory, or if the loaded memory
82 objects are not adjacent, a new merged_store_group is created as well.
84 For example, given the stores:
91 This phase would produce two merged_store_group objects, one recording the
92 two bytes stored in the memory region [p : p + 1] and another
93 recording the four bytes stored in the memory region [p + 3 : p + 6].
95 3) The merged_store_group objects produced in phase 2) are processed
96 to generate the sequence of wider stores that set the contiguous memory
97 regions to the sequence of bytes that correspond to it. This may emit
98 multiple stores per store group to handle contiguous stores that are not
99 of a size that is a power of 2. For example it can try to emit a 40-bit
100 store as a 32-bit store followed by an 8-bit store.
101 We try to emit as wide stores as we can while respecting STRICT_ALIGNMENT
102 or TARGET_SLOW_UNALIGNED_ACCESS settings.
104 Note on endianness and example:
105 Consider 2 contiguous 16-bit stores followed by 2 contiguous 8-bit stores:
111 The memory layout for little-endian (LE) and big-endian (BE) must be:
121 To merge these into a single 48-bit merged value 'val' in phase 2)
122 on little-endian we insert stores to higher (consecutive) bitpositions
123 into the most significant bits of the merged value.
124 The final merged value would be: 0xcdab56781234
126 For big-endian we insert stores to higher bitpositions into the least
127 significant bits of the merged value.
128 The final merged value would be: 0x12345678abcd
130 Then, in phase 3), we want to emit this 48-bit value as a 32-bit store
131 followed by a 16-bit store. Again, we must consider endianness when
132 breaking down the 48-bit value 'val' computed above.
133 For little endian we emit:
134 [p] (32-bit) := 0x56781234; // val & 0x0000ffffffff;
135 [p + 4B] (16-bit) := 0xcdab; // (val & 0xffff00000000) >> 32;
137 Whereas for big-endian we emit:
138 [p] (32-bit) := 0x12345678; // (val & 0xffffffff0000) >> 16;
139 [p + 4B] (16-bit) := 0xabcd; // val & 0x00000000ffff; */
143 #include "coretypes.h"
147 #include "builtins.h"
148 #include "fold-const.h"
149 #include "tree-pass.h"
151 #include "gimple-pretty-print.h"
153 #include "fold-const.h"
155 #include "print-tree.h"
156 #include "tree-hash-traits.h"
157 #include "gimple-iterator.h"
158 #include "gimplify.h"
159 #include "gimple-fold.h"
160 #include "stor-layout.h"
162 #include "tree-cfg.h"
165 #include "gimplify-me.h"
167 #include "expr.h" /* For get_bit_range. */
168 #include "optabs-tree.h"
169 #include "selftest.h"
171 /* The maximum size (in bits) of the stores this pass should generate. */
172 #define MAX_STORE_BITSIZE (BITS_PER_WORD)
173 #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
175 /* Limit to bound the number of aliasing checks for loads with the same
176 vuse as the corresponding store. */
177 #define MAX_STORE_ALIAS_CHECKS 64
183 /* Number of hand-written 16-bit nop / bswaps found. */
186 /* Number of hand-written 32-bit nop / bswaps found. */
189 /* Number of hand-written 64-bit nop / bswaps found. */
191 } nop_stats
, bswap_stats
;
193 /* A symbolic number structure is used to detect byte permutation and selection
194 patterns of a source. To achieve that, its field N contains an artificial
195 number consisting of BITS_PER_MARKER sized markers tracking where does each
196 byte come from in the source:
198 0 - target byte has the value 0
199 FF - target byte has an unknown value (eg. due to sign extension)
200 1..size - marker value is the byte index in the source (0 for lsb).
202 To detect permutations on memory sources (arrays and structures), a symbolic
203 number is also associated:
204 - a base address BASE_ADDR and an OFFSET giving the address of the source;
205 - a range which gives the difference between the highest and lowest accessed
206 memory location to make such a symbolic number;
207 - the address SRC of the source element of lowest address as a convenience
208 to easily get BASE_ADDR + offset + lowest bytepos;
209 - number of expressions N_OPS bitwise ored together to represent
210 approximate cost of the computation.
212 Note 1: the range is different from size as size reflects the size of the
213 type of the current expression. For instance, for an array char a[],
214 (short) a[0] | (short) a[3] would have a size of 2 but a range of 4 while
215 (short) a[0] | ((short) a[0] << 1) would still have a size of 2 but this
218 Note 2: for non-memory sources, range holds the same value as size.
220 Note 3: SRC points to the SSA_NAME in case of non-memory source. */
222 struct symbolic_number
{
227 poly_int64_pod bytepos
;
231 unsigned HOST_WIDE_INT range
;
235 #define BITS_PER_MARKER 8
236 #define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
237 #define MARKER_BYTE_UNKNOWN MARKER_MASK
238 #define HEAD_MARKER(n, size) \
239 ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
241 /* The number which the find_bswap_or_nop_1 result should match in
242 order to have a nop. The number is masked according to the size of
243 the symbolic number before using it. */
244 #define CMPNOP (sizeof (int64_t) < 8 ? 0 : \
245 (uint64_t)0x08070605 << 32 | 0x04030201)
247 /* The number which the find_bswap_or_nop_1 result should match in
248 order to have a byte swap. The number is masked according to the
249 size of the symbolic number before using it. */
250 #define CMPXCHG (sizeof (int64_t) < 8 ? 0 : \
251 (uint64_t)0x01020304 << 32 | 0x05060708)
253 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
254 number N. Return false if the requested operation is not permitted
255 on a symbolic number. */
258 do_shift_rotate (enum tree_code code
,
259 struct symbolic_number
*n
,
262 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
263 unsigned head_marker
;
265 if (count
% BITS_PER_UNIT
!= 0)
267 count
= (count
/ BITS_PER_UNIT
) * BITS_PER_MARKER
;
269 /* Zero out the extra bits of N in order to avoid them being shifted
270 into the significant bits. */
271 if (size
< 64 / BITS_PER_MARKER
)
272 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
280 head_marker
= HEAD_MARKER (n
->n
, size
);
282 /* Arithmetic shift of signed type: result is dependent on the value. */
283 if (!TYPE_UNSIGNED (n
->type
) && head_marker
)
284 for (i
= 0; i
< count
/ BITS_PER_MARKER
; i
++)
285 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
286 << ((size
- 1 - i
) * BITS_PER_MARKER
);
289 n
->n
= (n
->n
<< count
) | (n
->n
>> ((size
* BITS_PER_MARKER
) - count
));
292 n
->n
= (n
->n
>> count
) | (n
->n
<< ((size
* BITS_PER_MARKER
) - count
));
297 /* Zero unused bits for size. */
298 if (size
< 64 / BITS_PER_MARKER
)
299 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
303 /* Perform sanity checking for the symbolic number N and the gimple
307 verify_symbolic_number_p (struct symbolic_number
*n
, gimple
*stmt
)
311 lhs_type
= gimple_expr_type (stmt
);
313 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
316 if (TYPE_PRECISION (lhs_type
) != TYPE_PRECISION (n
->type
))
322 /* Initialize the symbolic number N for the bswap pass from the base element
323 SRC manipulated by the bitwise OR expression. */
326 init_symbolic_number (struct symbolic_number
*n
, tree src
)
330 if (! INTEGRAL_TYPE_P (TREE_TYPE (src
)))
333 n
->base_addr
= n
->offset
= n
->alias_set
= n
->vuse
= NULL_TREE
;
336 /* Set up the symbolic number N by setting each byte to a value between 1 and
337 the byte size of rhs1. The highest order byte is set to n->size and the
338 lowest order byte to 1. */
339 n
->type
= TREE_TYPE (src
);
340 size
= TYPE_PRECISION (n
->type
);
341 if (size
% BITS_PER_UNIT
!= 0)
343 size
/= BITS_PER_UNIT
;
344 if (size
> 64 / BITS_PER_MARKER
)
350 if (size
< 64 / BITS_PER_MARKER
)
351 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
356 /* Check if STMT might be a byte swap or a nop from a memory source and returns
357 the answer. If so, REF is that memory source and the base of the memory area
358 accessed and the offset of the access from that base are recorded in N. */
361 find_bswap_or_nop_load (gimple
*stmt
, tree ref
, struct symbolic_number
*n
)
363 /* Leaf node is an array or component ref. Memorize its base and
364 offset from base to compare to other such leaf node. */
365 poly_int64 bitsize
, bitpos
, bytepos
;
367 int unsignedp
, reversep
, volatilep
;
368 tree offset
, base_addr
;
370 /* Not prepared to handle PDP endian. */
371 if (BYTES_BIG_ENDIAN
!= WORDS_BIG_ENDIAN
)
374 if (!gimple_assign_load_p (stmt
) || gimple_has_volatile_ops (stmt
))
377 base_addr
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
378 &unsignedp
, &reversep
, &volatilep
);
380 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
381 /* Do not rewrite TARGET_MEM_REF. */
383 else if (TREE_CODE (base_addr
) == MEM_REF
)
385 poly_offset_int bit_offset
= 0;
386 tree off
= TREE_OPERAND (base_addr
, 1);
388 if (!integer_zerop (off
))
390 poly_offset_int boff
= mem_ref_offset (base_addr
);
391 boff
<<= LOG2_BITS_PER_UNIT
;
395 base_addr
= TREE_OPERAND (base_addr
, 0);
397 /* Avoid returning a negative bitpos as this may wreak havoc later. */
398 if (maybe_lt (bit_offset
, 0))
400 tree byte_offset
= wide_int_to_tree
401 (sizetype
, bits_to_bytes_round_down (bit_offset
));
402 bit_offset
= num_trailing_bits (bit_offset
);
404 offset
= size_binop (PLUS_EXPR
, offset
, byte_offset
);
406 offset
= byte_offset
;
409 bitpos
+= bit_offset
.force_shwi ();
412 base_addr
= build_fold_addr_expr (base_addr
);
414 if (!multiple_p (bitpos
, BITS_PER_UNIT
, &bytepos
))
416 if (!multiple_p (bitsize
, BITS_PER_UNIT
))
421 if (!init_symbolic_number (n
, ref
))
423 n
->base_addr
= base_addr
;
425 n
->bytepos
= bytepos
;
426 n
->alias_set
= reference_alias_ptr_type (ref
);
427 n
->vuse
= gimple_vuse (stmt
);
431 /* Compute the symbolic number N representing the result of a bitwise OR on 2
432 symbolic number N1 and N2 whose source statements are respectively
433 SOURCE_STMT1 and SOURCE_STMT2. */
436 perform_symbolic_merge (gimple
*source_stmt1
, struct symbolic_number
*n1
,
437 gimple
*source_stmt2
, struct symbolic_number
*n2
,
438 struct symbolic_number
*n
)
443 struct symbolic_number
*n_start
;
445 tree rhs1
= gimple_assign_rhs1 (source_stmt1
);
446 if (TREE_CODE (rhs1
) == BIT_FIELD_REF
447 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
448 rhs1
= TREE_OPERAND (rhs1
, 0);
449 tree rhs2
= gimple_assign_rhs1 (source_stmt2
);
450 if (TREE_CODE (rhs2
) == BIT_FIELD_REF
451 && TREE_CODE (TREE_OPERAND (rhs2
, 0)) == SSA_NAME
)
452 rhs2
= TREE_OPERAND (rhs2
, 0);
454 /* Sources are different, cancel bswap if they are not memory location with
455 the same base (array, structure, ...). */
459 HOST_WIDE_INT start1
, start2
, start_sub
, end_sub
, end1
, end2
, end
;
460 struct symbolic_number
*toinc_n_ptr
, *n_end
;
461 basic_block bb1
, bb2
;
463 if (!n1
->base_addr
|| !n2
->base_addr
464 || !operand_equal_p (n1
->base_addr
, n2
->base_addr
, 0))
467 if (!n1
->offset
!= !n2
->offset
468 || (n1
->offset
&& !operand_equal_p (n1
->offset
, n2
->offset
, 0)))
472 if (!(n2
->bytepos
- n1
->bytepos
).is_constant (&start2
))
478 start_sub
= start2
- start1
;
483 start_sub
= start1
- start2
;
486 bb1
= gimple_bb (source_stmt1
);
487 bb2
= gimple_bb (source_stmt2
);
488 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
489 source_stmt
= source_stmt1
;
491 source_stmt
= source_stmt2
;
493 /* Find the highest address at which a load is performed and
494 compute related info. */
495 end1
= start1
+ (n1
->range
- 1);
496 end2
= start2
+ (n2
->range
- 1);
500 end_sub
= end2
- end1
;
505 end_sub
= end1
- end2
;
507 n_end
= (end2
> end1
) ? n2
: n1
;
509 /* Find symbolic number whose lsb is the most significant. */
510 if (BYTES_BIG_ENDIAN
)
511 toinc_n_ptr
= (n_end
== n1
) ? n2
: n1
;
513 toinc_n_ptr
= (n_start
== n1
) ? n2
: n1
;
515 n
->range
= end
- MIN (start1
, start2
) + 1;
517 /* Check that the range of memory covered can be represented by
518 a symbolic number. */
519 if (n
->range
> 64 / BITS_PER_MARKER
)
522 /* Reinterpret byte marks in symbolic number holding the value of
523 bigger weight according to target endianness. */
524 inc
= BYTES_BIG_ENDIAN
? end_sub
: start_sub
;
525 size
= TYPE_PRECISION (n1
->type
) / BITS_PER_UNIT
;
526 for (i
= 0; i
< size
; i
++, inc
<<= BITS_PER_MARKER
)
529 = (toinc_n_ptr
->n
>> (i
* BITS_PER_MARKER
)) & MARKER_MASK
;
530 if (marker
&& marker
!= MARKER_BYTE_UNKNOWN
)
531 toinc_n_ptr
->n
+= inc
;
536 n
->range
= n1
->range
;
538 source_stmt
= source_stmt1
;
542 || alias_ptr_types_compatible_p (n1
->alias_set
, n2
->alias_set
))
543 n
->alias_set
= n1
->alias_set
;
545 n
->alias_set
= ptr_type_node
;
546 n
->vuse
= n_start
->vuse
;
547 n
->base_addr
= n_start
->base_addr
;
548 n
->offset
= n_start
->offset
;
549 n
->src
= n_start
->src
;
550 n
->bytepos
= n_start
->bytepos
;
551 n
->type
= n_start
->type
;
552 size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
554 for (i
= 0, mask
= MARKER_MASK
; i
< size
; i
++, mask
<<= BITS_PER_MARKER
)
556 uint64_t masked1
, masked2
;
558 masked1
= n1
->n
& mask
;
559 masked2
= n2
->n
& mask
;
560 if (masked1
&& masked2
&& masked1
!= masked2
)
563 n
->n
= n1
->n
| n2
->n
;
564 n
->n_ops
= n1
->n_ops
+ n2
->n_ops
;
569 /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
570 the operation given by the rhs of STMT on the result. If the operation
571 could successfully be executed the function returns a gimple stmt whose
572 rhs's first tree is the expression of the source operand and NULL
576 find_bswap_or_nop_1 (gimple
*stmt
, struct symbolic_number
*n
, int limit
)
579 tree rhs1
, rhs2
= NULL
;
580 gimple
*rhs1_stmt
, *rhs2_stmt
, *source_stmt1
;
581 enum gimple_rhs_class rhs_class
;
583 if (!limit
|| !is_gimple_assign (stmt
))
586 rhs1
= gimple_assign_rhs1 (stmt
);
588 if (find_bswap_or_nop_load (stmt
, rhs1
, n
))
591 /* Handle BIT_FIELD_REF. */
592 if (TREE_CODE (rhs1
) == BIT_FIELD_REF
593 && TREE_CODE (TREE_OPERAND (rhs1
, 0)) == SSA_NAME
)
595 unsigned HOST_WIDE_INT bitsize
= tree_to_uhwi (TREE_OPERAND (rhs1
, 1));
596 unsigned HOST_WIDE_INT bitpos
= tree_to_uhwi (TREE_OPERAND (rhs1
, 2));
597 if (bitpos
% BITS_PER_UNIT
== 0
598 && bitsize
% BITS_PER_UNIT
== 0
599 && init_symbolic_number (n
, TREE_OPERAND (rhs1
, 0)))
601 /* Handle big-endian bit numbering in BIT_FIELD_REF. */
602 if (BYTES_BIG_ENDIAN
)
603 bitpos
= TYPE_PRECISION (n
->type
) - bitpos
- bitsize
;
606 if (!do_shift_rotate (RSHIFT_EXPR
, n
, bitpos
))
611 uint64_t tmp
= (1 << BITS_PER_UNIT
) - 1;
612 for (unsigned i
= 0; i
< bitsize
/ BITS_PER_UNIT
;
613 i
++, tmp
<<= BITS_PER_UNIT
)
614 mask
|= (uint64_t) MARKER_MASK
<< (i
* BITS_PER_MARKER
);
618 n
->type
= TREE_TYPE (rhs1
);
620 n
->range
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
622 return verify_symbolic_number_p (n
, stmt
) ? stmt
: NULL
;
628 if (TREE_CODE (rhs1
) != SSA_NAME
)
631 code
= gimple_assign_rhs_code (stmt
);
632 rhs_class
= gimple_assign_rhs_class (stmt
);
633 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
635 if (rhs_class
== GIMPLE_BINARY_RHS
)
636 rhs2
= gimple_assign_rhs2 (stmt
);
638 /* Handle unary rhs and binary rhs with integer constants as second
641 if (rhs_class
== GIMPLE_UNARY_RHS
642 || (rhs_class
== GIMPLE_BINARY_RHS
643 && TREE_CODE (rhs2
) == INTEGER_CST
))
645 if (code
!= BIT_AND_EXPR
646 && code
!= LSHIFT_EXPR
647 && code
!= RSHIFT_EXPR
648 && code
!= LROTATE_EXPR
649 && code
!= RROTATE_EXPR
650 && !CONVERT_EXPR_CODE_P (code
))
653 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, n
, limit
- 1);
655 /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
656 we have to initialize the symbolic number. */
659 if (gimple_assign_load_p (stmt
)
660 || !init_symbolic_number (n
, rhs1
))
669 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
670 uint64_t val
= int_cst_value (rhs2
), mask
= 0;
671 uint64_t tmp
= (1 << BITS_PER_UNIT
) - 1;
673 /* Only constants masking full bytes are allowed. */
674 for (i
= 0; i
< size
; i
++, tmp
<<= BITS_PER_UNIT
)
675 if ((val
& tmp
) != 0 && (val
& tmp
) != tmp
)
678 mask
|= (uint64_t) MARKER_MASK
<< (i
* BITS_PER_MARKER
);
687 if (!do_shift_rotate (code
, n
, (int) TREE_INT_CST_LOW (rhs2
)))
692 int i
, type_size
, old_type_size
;
695 type
= gimple_expr_type (stmt
);
696 type_size
= TYPE_PRECISION (type
);
697 if (type_size
% BITS_PER_UNIT
!= 0)
699 type_size
/= BITS_PER_UNIT
;
700 if (type_size
> 64 / BITS_PER_MARKER
)
703 /* Sign extension: result is dependent on the value. */
704 old_type_size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
705 if (!TYPE_UNSIGNED (n
->type
) && type_size
> old_type_size
706 && HEAD_MARKER (n
->n
, old_type_size
))
707 for (i
= 0; i
< type_size
- old_type_size
; i
++)
708 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
709 << ((type_size
- 1 - i
) * BITS_PER_MARKER
);
711 if (type_size
< 64 / BITS_PER_MARKER
)
713 /* If STMT casts to a smaller type mask out the bits not
714 belonging to the target type. */
715 n
->n
&= ((uint64_t) 1 << (type_size
* BITS_PER_MARKER
)) - 1;
719 n
->range
= type_size
;
725 return verify_symbolic_number_p (n
, stmt
) ? source_stmt1
: NULL
;
728 /* Handle binary rhs. */
730 if (rhs_class
== GIMPLE_BINARY_RHS
)
732 struct symbolic_number n1
, n2
;
733 gimple
*source_stmt
, *source_stmt2
;
735 if (code
!= BIT_IOR_EXPR
)
738 if (TREE_CODE (rhs2
) != SSA_NAME
)
741 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
746 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, &n1
, limit
- 1);
751 source_stmt2
= find_bswap_or_nop_1 (rhs2_stmt
, &n2
, limit
- 1);
756 if (TYPE_PRECISION (n1
.type
) != TYPE_PRECISION (n2
.type
))
759 if (n1
.vuse
!= n2
.vuse
)
763 = perform_symbolic_merge (source_stmt1
, &n1
, source_stmt2
, &n2
, n
);
768 if (!verify_symbolic_number_p (n
, stmt
))
780 /* Helper for find_bswap_or_nop and try_coalesce_bswap to compute
781 *CMPXCHG, *CMPNOP and adjust *N. */
784 find_bswap_or_nop_finalize (struct symbolic_number
*n
, uint64_t *cmpxchg
,
790 /* The number which the find_bswap_or_nop_1 result should match in order
791 to have a full byte swap. The number is shifted to the right
792 according to the size of the symbolic number before using it. */
796 /* Find real size of result (highest non-zero byte). */
798 for (tmpn
= n
->n
, rsize
= 0; tmpn
; tmpn
>>= BITS_PER_MARKER
, rsize
++);
802 /* Zero out the bits corresponding to untouched bytes in original gimple
804 if (n
->range
< (int) sizeof (int64_t))
806 mask
= ((uint64_t) 1 << (n
->range
* BITS_PER_MARKER
)) - 1;
807 *cmpxchg
>>= (64 / BITS_PER_MARKER
- n
->range
) * BITS_PER_MARKER
;
811 /* Zero out the bits corresponding to unused bytes in the result of the
812 gimple expression. */
813 if (rsize
< n
->range
)
815 if (BYTES_BIG_ENDIAN
)
817 mask
= ((uint64_t) 1 << (rsize
* BITS_PER_MARKER
)) - 1;
819 *cmpnop
>>= (n
->range
- rsize
) * BITS_PER_MARKER
;
823 mask
= ((uint64_t) 1 << (rsize
* BITS_PER_MARKER
)) - 1;
824 *cmpxchg
>>= (n
->range
- rsize
) * BITS_PER_MARKER
;
830 n
->range
*= BITS_PER_UNIT
;
833 /* Check if STMT completes a bswap implementation or a read in a given
834 endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
835 accordingly. It also sets N to represent the kind of operations
836 performed: size of the resulting expression and whether it works on
837 a memory source, and if so alias-set and vuse. At last, the
838 function returns a stmt whose rhs's first tree is the source
842 find_bswap_or_nop (gimple
*stmt
, struct symbolic_number
*n
, bool *bswap
)
844 /* The last parameter determines the depth search limit. It usually
845 correlates directly to the number n of bytes to be touched. We
846 increase that number by log2(n) + 1 here in order to also
847 cover signed -> unsigned conversions of the src operand as can be seen
848 in libgcc, and for initial shift/and operation of the src operand. */
849 int limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
850 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
851 gimple
*ins_stmt
= find_bswap_or_nop_1 (stmt
, n
, limit
);
856 uint64_t cmpxchg
, cmpnop
;
857 find_bswap_or_nop_finalize (n
, &cmpxchg
, &cmpnop
);
859 /* A complete byte swap should make the symbolic number to start with
860 the largest digit in the highest order byte. Unchanged symbolic
861 number indicates a read with same endianness as target architecture. */
864 else if (n
->n
== cmpxchg
)
869 /* Useless bit manipulation performed by code. */
870 if (!n
->base_addr
&& n
->n
== cmpnop
&& n
->n_ops
== 1)
876 const pass_data pass_data_optimize_bswap
=
878 GIMPLE_PASS
, /* type */
880 OPTGROUP_NONE
, /* optinfo_flags */
882 PROP_ssa
, /* properties_required */
883 0, /* properties_provided */
884 0, /* properties_destroyed */
885 0, /* todo_flags_start */
886 0, /* todo_flags_finish */
889 class pass_optimize_bswap
: public gimple_opt_pass
892 pass_optimize_bswap (gcc::context
*ctxt
)
893 : gimple_opt_pass (pass_data_optimize_bswap
, ctxt
)
896 /* opt_pass methods: */
897 virtual bool gate (function
*)
899 return flag_expensive_optimizations
&& optimize
&& BITS_PER_UNIT
== 8;
902 virtual unsigned int execute (function
*);
904 }; // class pass_optimize_bswap
906 /* Perform the bswap optimization: replace the expression computed in the rhs
907 of gsi_stmt (GSI) (or if NULL add instead of replace) by an equivalent
908 bswap, load or load + bswap expression.
909 Which of these alternatives replace the rhs is given by N->base_addr (non
910 null if a load is needed) and BSWAP. The type, VUSE and set-alias of the
911 load to perform are also given in N while the builtin bswap invoke is given
912 in FNDEL. Finally, if a load is involved, INS_STMT refers to one of the
913 load statements involved to construct the rhs in gsi_stmt (GSI) and
914 N->range gives the size of the rhs expression for maintaining some
917 Note that if the replacement involve a load and if gsi_stmt (GSI) is
918 non-NULL, that stmt is moved just after INS_STMT to do the load with the
919 same VUSE which can lead to gsi_stmt (GSI) changing of basic block. */
922 bswap_replace (gimple_stmt_iterator gsi
, gimple
*ins_stmt
, tree fndecl
,
923 tree bswap_type
, tree load_type
, struct symbolic_number
*n
,
926 tree src
, tmp
, tgt
= NULL_TREE
;
929 gimple
*cur_stmt
= gsi_stmt (gsi
);
932 tgt
= gimple_assign_lhs (cur_stmt
);
934 /* Need to load the value from memory first. */
937 gimple_stmt_iterator gsi_ins
= gsi
;
939 gsi_ins
= gsi_for_stmt (ins_stmt
);
940 tree addr_expr
, addr_tmp
, val_expr
, val_tmp
;
941 tree load_offset_ptr
, aligned_load_type
;
943 unsigned align
= get_object_alignment (src
);
944 poly_int64 load_offset
= 0;
948 basic_block ins_bb
= gimple_bb (ins_stmt
);
949 basic_block cur_bb
= gimple_bb (cur_stmt
);
950 if (!dominated_by_p (CDI_DOMINATORS
, cur_bb
, ins_bb
))
953 /* Move cur_stmt just before one of the load of the original
954 to ensure it has the same VUSE. See PR61517 for what could
956 if (gimple_bb (cur_stmt
) != gimple_bb (ins_stmt
))
957 reset_flow_sensitive_info (gimple_assign_lhs (cur_stmt
));
958 gsi_move_before (&gsi
, &gsi_ins
);
959 gsi
= gsi_for_stmt (cur_stmt
);
964 /* Compute address to load from and cast according to the size
966 addr_expr
= build_fold_addr_expr (src
);
967 if (is_gimple_mem_ref_addr (addr_expr
))
968 addr_tmp
= unshare_expr (addr_expr
);
971 addr_tmp
= unshare_expr (n
->base_addr
);
972 if (!is_gimple_mem_ref_addr (addr_tmp
))
973 addr_tmp
= force_gimple_operand_gsi_1 (&gsi
, addr_tmp
,
974 is_gimple_mem_ref_addr
,
977 load_offset
= n
->bytepos
;
981 = force_gimple_operand_gsi (&gsi
, unshare_expr (n
->offset
),
982 true, NULL_TREE
, true,
985 = gimple_build_assign (make_ssa_name (TREE_TYPE (addr_tmp
)),
986 POINTER_PLUS_EXPR
, addr_tmp
, off
);
987 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
988 addr_tmp
= gimple_assign_lhs (stmt
);
992 /* Perform the load. */
993 aligned_load_type
= load_type
;
994 if (align
< TYPE_ALIGN (load_type
))
995 aligned_load_type
= build_aligned_type (load_type
, align
);
996 load_offset_ptr
= build_int_cst (n
->alias_set
, load_offset
);
997 val_expr
= fold_build2 (MEM_REF
, aligned_load_type
, addr_tmp
,
1003 nop_stats
.found_16bit
++;
1004 else if (n
->range
== 32)
1005 nop_stats
.found_32bit
++;
1008 gcc_assert (n
->range
== 64);
1009 nop_stats
.found_64bit
++;
1012 /* Convert the result of load if necessary. */
1013 if (tgt
&& !useless_type_conversion_p (TREE_TYPE (tgt
), load_type
))
1015 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
,
1017 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
1018 gimple_set_vuse (load_stmt
, n
->vuse
);
1019 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1020 gimple_assign_set_rhs_with_ops (&gsi
, NOP_EXPR
, val_tmp
);
1021 update_stmt (cur_stmt
);
1025 gimple_assign_set_rhs_with_ops (&gsi
, MEM_REF
, val_expr
);
1026 gimple_set_vuse (cur_stmt
, n
->vuse
);
1027 update_stmt (cur_stmt
);
1031 tgt
= make_ssa_name (load_type
);
1032 cur_stmt
= gimple_build_assign (tgt
, MEM_REF
, val_expr
);
1033 gimple_set_vuse (cur_stmt
, n
->vuse
);
1034 gsi_insert_before (&gsi
, cur_stmt
, GSI_SAME_STMT
);
1040 "%d bit load in target endianness found at: ",
1042 print_gimple_stmt (dump_file
, cur_stmt
, 0);
1048 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
, "load_dst");
1049 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
1050 gimple_set_vuse (load_stmt
, n
->vuse
);
1051 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1058 if (tgt
&& !useless_type_conversion_p (TREE_TYPE (tgt
), TREE_TYPE (src
)))
1060 if (!is_gimple_val (src
))
1062 g
= gimple_build_assign (tgt
, NOP_EXPR
, src
);
1065 g
= gimple_build_assign (tgt
, src
);
1069 nop_stats
.found_16bit
++;
1070 else if (n
->range
== 32)
1071 nop_stats
.found_32bit
++;
1074 gcc_assert (n
->range
== 64);
1075 nop_stats
.found_64bit
++;
1080 "%d bit reshuffle in target endianness found at: ",
1083 print_gimple_stmt (dump_file
, cur_stmt
, 0);
1086 print_generic_expr (dump_file
, tgt
, TDF_NONE
);
1087 fprintf (dump_file
, "\n");
1091 gsi_replace (&gsi
, g
, true);
1094 else if (TREE_CODE (src
) == BIT_FIELD_REF
)
1095 src
= TREE_OPERAND (src
, 0);
1098 bswap_stats
.found_16bit
++;
1099 else if (n
->range
== 32)
1100 bswap_stats
.found_32bit
++;
1103 gcc_assert (n
->range
== 64);
1104 bswap_stats
.found_64bit
++;
1109 /* Convert the src expression if necessary. */
1110 if (!useless_type_conversion_p (TREE_TYPE (tmp
), bswap_type
))
1112 gimple
*convert_stmt
;
1114 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
1115 convert_stmt
= gimple_build_assign (tmp
, NOP_EXPR
, src
);
1116 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1119 /* Canonical form for 16 bit bswap is a rotate expression. Only 16bit values
1120 are considered as rotation of 2N bit values by N bits is generally not
1121 equivalent to a bswap. Consider for instance 0x01020304 r>> 16 which
1122 gives 0x03040102 while a bswap for that value is 0x04030201. */
1123 if (bswap
&& n
->range
== 16)
1125 tree count
= build_int_cst (NULL
, BITS_PER_UNIT
);
1126 src
= fold_build2 (LROTATE_EXPR
, bswap_type
, tmp
, count
);
1127 bswap_stmt
= gimple_build_assign (NULL
, src
);
1130 bswap_stmt
= gimple_build_call (fndecl
, 1, tmp
);
1132 if (tgt
== NULL_TREE
)
1133 tgt
= make_ssa_name (bswap_type
);
1136 /* Convert the result if necessary. */
1137 if (!useless_type_conversion_p (TREE_TYPE (tgt
), bswap_type
))
1139 gimple
*convert_stmt
;
1141 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapdst");
1142 convert_stmt
= gimple_build_assign (tgt
, NOP_EXPR
, tmp
);
1143 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1146 gimple_set_lhs (bswap_stmt
, tmp
);
1150 fprintf (dump_file
, "%d bit bswap implementation found at: ",
1153 print_gimple_stmt (dump_file
, cur_stmt
, 0);
1156 print_generic_expr (dump_file
, tgt
, TDF_NONE
);
1157 fprintf (dump_file
, "\n");
1163 gsi_insert_after (&gsi
, bswap_stmt
, GSI_SAME_STMT
);
1164 gsi_remove (&gsi
, true);
1167 gsi_insert_before (&gsi
, bswap_stmt
, GSI_SAME_STMT
);
1171 /* Find manual byte swap implementations as well as load in a given
1172 endianness. Byte swaps are turned into a bswap builtin invokation
1173 while endian loads are converted to bswap builtin invokation or
1174 simple load according to the target endianness. */
1177 pass_optimize_bswap::execute (function
*fun
)
1180 bool bswap32_p
, bswap64_p
;
1181 bool changed
= false;
1182 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
1184 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
1185 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
1186 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
1187 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
1188 || (bswap32_p
&& word_mode
== SImode
)));
1190 /* Determine the argument type of the builtins. The code later on
1191 assumes that the return and argument type are the same. */
1194 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1195 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1200 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1201 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1204 memset (&nop_stats
, 0, sizeof (nop_stats
));
1205 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
1206 calculate_dominance_info (CDI_DOMINATORS
);
1208 FOR_EACH_BB_FN (bb
, fun
)
1210 gimple_stmt_iterator gsi
;
1212 /* We do a reverse scan for bswap patterns to make sure we get the
1213 widest match. As bswap pattern matching doesn't handle previously
1214 inserted smaller bswap replacements as sub-patterns, the wider
1215 variant wouldn't be detected. */
1216 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
1218 gimple
*ins_stmt
, *cur_stmt
= gsi_stmt (gsi
);
1219 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
, load_type
;
1220 enum tree_code code
;
1221 struct symbolic_number n
;
1224 /* This gsi_prev (&gsi) is not part of the for loop because cur_stmt
1225 might be moved to a different basic block by bswap_replace and gsi
1226 must not points to it if that's the case. Moving the gsi_prev
1227 there make sure that gsi points to the statement previous to
1228 cur_stmt while still making sure that all statements are
1229 considered in this basic block. */
1232 if (!is_gimple_assign (cur_stmt
))
1235 code
= gimple_assign_rhs_code (cur_stmt
);
1240 if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt
))
1241 || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt
))
1251 ins_stmt
= find_bswap_or_nop (cur_stmt
, &n
, &bswap
);
1259 /* Already in canonical form, nothing to do. */
1260 if (code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
1262 load_type
= bswap_type
= uint16_type_node
;
1265 load_type
= uint32_type_node
;
1268 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1269 bswap_type
= bswap32_type
;
1273 load_type
= uint64_type_node
;
1276 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1277 bswap_type
= bswap64_type
;
1284 if (bswap
&& !fndecl
&& n
.range
!= 16)
1287 if (bswap_replace (gsi_for_stmt (cur_stmt
), ins_stmt
, fndecl
,
1288 bswap_type
, load_type
, &n
, bswap
))
1293 statistics_counter_event (fun
, "16-bit nop implementations found",
1294 nop_stats
.found_16bit
);
1295 statistics_counter_event (fun
, "32-bit nop implementations found",
1296 nop_stats
.found_32bit
);
1297 statistics_counter_event (fun
, "64-bit nop implementations found",
1298 nop_stats
.found_64bit
);
1299 statistics_counter_event (fun
, "16-bit bswap implementations found",
1300 bswap_stats
.found_16bit
);
1301 statistics_counter_event (fun
, "32-bit bswap implementations found",
1302 bswap_stats
.found_32bit
);
1303 statistics_counter_event (fun
, "64-bit bswap implementations found",
1304 bswap_stats
.found_64bit
);
1306 return (changed
? TODO_update_ssa
: 0);
1312 make_pass_optimize_bswap (gcc::context
*ctxt
)
1314 return new pass_optimize_bswap (ctxt
);
1319 /* Struct recording one operand for the store, which is either a constant,
1320 then VAL represents the constant and all the other fields are zero, or
1321 a memory load, then VAL represents the reference, BASE_ADDR is non-NULL
1322 and the other fields also reflect the memory load, or an SSA name, then
1323 VAL represents the SSA name and all the other fields are zero, */
1325 struct store_operand_info
1329 poly_uint64 bitsize
;
1331 poly_uint64 bitregion_start
;
1332 poly_uint64 bitregion_end
;
1335 store_operand_info ();
1338 store_operand_info::store_operand_info ()
1339 : val (NULL_TREE
), base_addr (NULL_TREE
), bitsize (0), bitpos (0),
1340 bitregion_start (0), bitregion_end (0), stmt (NULL
), bit_not_p (false)
1344 /* Struct recording the information about a single store of an immediate
1345 to memory. These are created in the first phase and coalesced into
1346 merged_store_group objects in the second phase. */
1348 struct store_immediate_info
1350 unsigned HOST_WIDE_INT bitsize
;
1351 unsigned HOST_WIDE_INT bitpos
;
1352 unsigned HOST_WIDE_INT bitregion_start
;
1353 /* This is one past the last bit of the bit region. */
1354 unsigned HOST_WIDE_INT bitregion_end
;
1357 /* INTEGER_CST for constant stores, MEM_REF for memory copy,
1358 BIT_*_EXPR for logical bitwise operation, BIT_INSERT_EXPR
1360 LROTATE_EXPR if it can be only bswap optimized and
1361 ops are not really meaningful.
1362 NOP_EXPR if bswap optimization detected identity, ops
1363 are not meaningful. */
1364 enum tree_code rhs_code
;
1365 /* Two fields for bswap optimization purposes. */
1366 struct symbolic_number n
;
1368 /* True if BIT_{AND,IOR,XOR}_EXPR result is inverted before storing. */
1370 /* True if ops have been swapped and thus ops[1] represents
1371 rhs1 of BIT_{AND,IOR,XOR}_EXPR and ops[0] represents rhs2. */
1373 /* Operands. For BIT_*_EXPR rhs_code both operands are used, otherwise
1374 just the first one. */
1375 store_operand_info ops
[2];
1376 store_immediate_info (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
1377 unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
1378 gimple
*, unsigned int, enum tree_code
,
1379 struct symbolic_number
&, gimple
*, bool,
1380 const store_operand_info
&,
1381 const store_operand_info
&);
1384 store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs
,
1385 unsigned HOST_WIDE_INT bp
,
1386 unsigned HOST_WIDE_INT brs
,
1387 unsigned HOST_WIDE_INT bre
,
1390 enum tree_code rhscode
,
1391 struct symbolic_number
&nr
,
1394 const store_operand_info
&op0r
,
1395 const store_operand_info
&op1r
)
1396 : bitsize (bs
), bitpos (bp
), bitregion_start (brs
), bitregion_end (bre
),
1397 stmt (st
), order (ord
), rhs_code (rhscode
), n (nr
),
1398 ins_stmt (ins_stmtp
), bit_not_p (bitnotp
), ops_swapped_p (false)
1399 #if __cplusplus >= 201103L
1400 , ops
{ op0r
, op1r
}
1410 /* Struct representing a group of stores to contiguous memory locations.
1411 These are produced by the second phase (coalescing) and consumed in the
1412 third phase that outputs the widened stores. */
1414 struct merged_store_group
1416 unsigned HOST_WIDE_INT start
;
1417 unsigned HOST_WIDE_INT width
;
1418 unsigned HOST_WIDE_INT bitregion_start
;
1419 unsigned HOST_WIDE_INT bitregion_end
;
1420 /* The size of the allocated memory for val and mask. */
1421 unsigned HOST_WIDE_INT buf_size
;
1422 unsigned HOST_WIDE_INT align_base
;
1423 poly_uint64 load_align_base
[2];
1426 unsigned int load_align
[2];
1427 unsigned int first_order
;
1428 unsigned int last_order
;
1431 auto_vec
<store_immediate_info
*> stores
;
1432 /* We record the first and last original statements in the sequence because
1433 we'll need their vuse/vdef and replacement position. It's easier to keep
1434 track of them separately as 'stores' is reordered by apply_stores. */
1438 unsigned char *mask
;
1440 merged_store_group (store_immediate_info
*);
1441 ~merged_store_group ();
1442 bool can_be_merged_into (store_immediate_info
*);
1443 void merge_into (store_immediate_info
*);
1444 void merge_overlapping (store_immediate_info
*);
1445 bool apply_stores ();
1447 void do_merge (store_immediate_info
*);
1450 /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
1453 dump_char_array (FILE *fd
, unsigned char *ptr
, unsigned int len
)
1458 for (unsigned int i
= 0; i
< len
; i
++)
1459 fprintf (fd
, "%02x ", ptr
[i
]);
1463 /* Shift left the bytes in PTR of SZ elements by AMNT bits, carrying over the
1464 bits between adjacent elements. AMNT should be within
1467 00011111|11100000 << 2 = 01111111|10000000
1468 PTR[1] | PTR[0] PTR[1] | PTR[0]. */
1471 shift_bytes_in_array (unsigned char *ptr
, unsigned int sz
, unsigned int amnt
)
1476 unsigned char carry_over
= 0U;
1477 unsigned char carry_mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- amnt
);
1478 unsigned char clear_mask
= (~0U) << amnt
;
1480 for (unsigned int i
= 0; i
< sz
; i
++)
1482 unsigned prev_carry_over
= carry_over
;
1483 carry_over
= (ptr
[i
] & carry_mask
) >> (BITS_PER_UNIT
- amnt
);
1488 ptr
[i
] &= clear_mask
;
1489 ptr
[i
] |= prev_carry_over
;
1494 /* Like shift_bytes_in_array but for big-endian.
1495 Shift right the bytes in PTR of SZ elements by AMNT bits, carrying over the
1496 bits between adjacent elements. AMNT should be within
1499 00011111|11100000 >> 2 = 00000111|11111000
1500 PTR[0] | PTR[1] PTR[0] | PTR[1]. */
1503 shift_bytes_in_array_right (unsigned char *ptr
, unsigned int sz
,
1509 unsigned char carry_over
= 0U;
1510 unsigned char carry_mask
= ~(~0U << amnt
);
1512 for (unsigned int i
= 0; i
< sz
; i
++)
1514 unsigned prev_carry_over
= carry_over
;
1515 carry_over
= ptr
[i
] & carry_mask
;
1517 carry_over
<<= (unsigned char) BITS_PER_UNIT
- amnt
;
1519 ptr
[i
] |= prev_carry_over
;
1523 /* Clear out LEN bits starting from bit START in the byte array
1524 PTR. This clears the bits to the *right* from START.
1525 START must be within [0, BITS_PER_UNIT) and counts starting from
1526 the least significant bit. */
1529 clear_bit_region_be (unsigned char *ptr
, unsigned int start
,
1534 /* Clear len bits to the right of start. */
1535 else if (len
<= start
+ 1)
1537 unsigned char mask
= (~(~0U << len
));
1538 mask
= mask
<< (start
+ 1U - len
);
1541 else if (start
!= BITS_PER_UNIT
- 1)
1543 clear_bit_region_be (ptr
, start
, (start
% BITS_PER_UNIT
) + 1);
1544 clear_bit_region_be (ptr
+ 1, BITS_PER_UNIT
- 1,
1545 len
- (start
% BITS_PER_UNIT
) - 1);
1547 else if (start
== BITS_PER_UNIT
- 1
1548 && len
> BITS_PER_UNIT
)
1550 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
1551 memset (ptr
, 0, nbytes
);
1552 if (len
% BITS_PER_UNIT
!= 0)
1553 clear_bit_region_be (ptr
+ nbytes
, BITS_PER_UNIT
- 1,
1554 len
% BITS_PER_UNIT
);
1560 /* In the byte array PTR clear the bit region starting at bit
1561 START and is LEN bits wide.
1562 For regions spanning multiple bytes do this recursively until we reach
1563 zero LEN or a region contained within a single byte. */
1566 clear_bit_region (unsigned char *ptr
, unsigned int start
,
1569 /* Degenerate base case. */
1572 else if (start
>= BITS_PER_UNIT
)
1573 clear_bit_region (ptr
+ 1, start
- BITS_PER_UNIT
, len
);
1574 /* Second base case. */
1575 else if ((start
+ len
) <= BITS_PER_UNIT
)
1577 unsigned char mask
= (~0U) << (unsigned char) (BITS_PER_UNIT
- len
);
1578 mask
>>= BITS_PER_UNIT
- (start
+ len
);
1584 /* Clear most significant bits in a byte and proceed with the next byte. */
1585 else if (start
!= 0)
1587 clear_bit_region (ptr
, start
, BITS_PER_UNIT
- start
);
1588 clear_bit_region (ptr
+ 1, 0, len
- (BITS_PER_UNIT
- start
));
1590 /* Whole bytes need to be cleared. */
1591 else if (start
== 0 && len
> BITS_PER_UNIT
)
1593 unsigned int nbytes
= len
/ BITS_PER_UNIT
;
1594 /* We could recurse on each byte but we clear whole bytes, so a simple
1596 memset (ptr
, '\0', nbytes
);
1597 /* Clear the remaining sub-byte region if there is one. */
1598 if (len
% BITS_PER_UNIT
!= 0)
1599 clear_bit_region (ptr
+ nbytes
, 0, len
% BITS_PER_UNIT
);
1605 /* Write BITLEN bits of EXPR to the byte array PTR at
1606 bit position BITPOS. PTR should contain TOTAL_BYTES elements.
1607 Return true if the operation succeeded. */
1610 encode_tree_to_bitpos (tree expr
, unsigned char *ptr
, int bitlen
, int bitpos
,
1611 unsigned int total_bytes
)
1613 unsigned int first_byte
= bitpos
/ BITS_PER_UNIT
;
1614 tree tmp_int
= expr
;
1615 bool sub_byte_op_p
= ((bitlen
% BITS_PER_UNIT
)
1616 || (bitpos
% BITS_PER_UNIT
)
1617 || !int_mode_for_size (bitlen
, 0).exists ());
1620 return native_encode_expr (tmp_int
, ptr
+ first_byte
, total_bytes
) != 0;
1623 We are writing a non byte-sized quantity or at a position that is not
1625 |--------|--------|--------| ptr + first_byte
1627 xxx xxxxxxxx xxx< bp>
1630 First native_encode_expr EXPR into a temporary buffer and shift each
1631 byte in the buffer by 'bp' (carrying the bits over as necessary).
1632 |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
1633 <------bitlen---->< bp>
1634 Then we clear the destination bits:
1635 |---00000|00000000|000-----| ptr + first_byte
1636 <-------bitlen--->< bp>
1638 Finally we ORR the bytes of the shifted EXPR into the cleared region:
1639 |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
1642 We are writing a non byte-sized quantity or at a position that is not
1644 ptr + first_byte |--------|--------|--------|
1646 <bp >xxx xxxxxxxx xxx
1649 First native_encode_expr EXPR into a temporary buffer and shift each
1650 byte in the buffer to the right by (carrying the bits over as necessary).
1651 We shift by as much as needed to align the most significant bit of EXPR
1653 |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
1654 <---bitlen----> <bp ><-----bitlen----->
1655 Then we clear the destination bits:
1656 ptr + first_byte |-----000||00000000||00000---|
1657 <bp ><-------bitlen----->
1659 Finally we ORR the bytes of the shifted EXPR into the cleared region:
1660 ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
1661 The awkwardness comes from the fact that bitpos is counted from the
1662 most significant bit of a byte. */
1664 /* We must be dealing with fixed-size data at this point, since the
1665 total size is also fixed. */
1666 fixed_size_mode mode
= as_a
<fixed_size_mode
> (TYPE_MODE (TREE_TYPE (expr
)));
1667 /* Allocate an extra byte so that we have space to shift into. */
1668 unsigned int byte_size
= GET_MODE_SIZE (mode
) + 1;
1669 unsigned char *tmpbuf
= XALLOCAVEC (unsigned char, byte_size
);
1670 memset (tmpbuf
, '\0', byte_size
);
1671 /* The store detection code should only have allowed constants that are
1672 accepted by native_encode_expr. */
1673 if (native_encode_expr (expr
, tmpbuf
, byte_size
- 1) == 0)
1676 /* The native_encode_expr machinery uses TYPE_MODE to determine how many
1677 bytes to write. This means it can write more than
1678 ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
1679 write 8 bytes for a bitlen of 40). Skip the bytes that are not within
1680 bitlen and zero out the bits that are not relevant as well (that may
1681 contain a sign bit due to sign-extension). */
1682 unsigned int padding
1683 = byte_size
- ROUND_UP (bitlen
, BITS_PER_UNIT
) / BITS_PER_UNIT
- 1;
1684 /* On big-endian the padding is at the 'front' so just skip the initial
1686 if (BYTES_BIG_ENDIAN
)
1689 byte_size
-= padding
;
1691 if (bitlen
% BITS_PER_UNIT
!= 0)
1693 if (BYTES_BIG_ENDIAN
)
1694 clear_bit_region_be (tmpbuf
, BITS_PER_UNIT
- 1,
1695 BITS_PER_UNIT
- (bitlen
% BITS_PER_UNIT
));
1697 clear_bit_region (tmpbuf
, bitlen
,
1698 byte_size
* BITS_PER_UNIT
- bitlen
);
1700 /* Left shifting relies on the last byte being clear if bitlen is
1701 a multiple of BITS_PER_UNIT, which might not be clear if
1702 there are padding bytes. */
1703 else if (!BYTES_BIG_ENDIAN
)
1704 tmpbuf
[byte_size
- 1] = '\0';
1706 /* Clear the bit region in PTR where the bits from TMPBUF will be
1708 if (BYTES_BIG_ENDIAN
)
1709 clear_bit_region_be (ptr
+ first_byte
,
1710 BITS_PER_UNIT
- 1 - (bitpos
% BITS_PER_UNIT
), bitlen
);
1712 clear_bit_region (ptr
+ first_byte
, bitpos
% BITS_PER_UNIT
, bitlen
);
1715 int bitlen_mod
= bitlen
% BITS_PER_UNIT
;
1716 int bitpos_mod
= bitpos
% BITS_PER_UNIT
;
1718 bool skip_byte
= false;
1719 if (BYTES_BIG_ENDIAN
)
1721 /* BITPOS and BITLEN are exactly aligned and no shifting
1723 if (bitpos_mod
+ bitlen_mod
== BITS_PER_UNIT
1724 || (bitpos_mod
== 0 && bitlen_mod
== 0))
1726 /* |. . . . . . . .|
1728 We always shift right for BYTES_BIG_ENDIAN so shift the beginning
1729 of the value until it aligns with 'bp' in the next byte over. */
1730 else if (bitpos_mod
+ bitlen_mod
< BITS_PER_UNIT
)
1732 shift_amnt
= bitlen_mod
+ bitpos_mod
;
1733 skip_byte
= bitlen_mod
!= 0;
1735 /* |. . . . . . . .|
1738 Shift the value right within the same byte so it aligns with 'bp'. */
1740 shift_amnt
= bitlen_mod
+ bitpos_mod
- BITS_PER_UNIT
;
1743 shift_amnt
= bitpos
% BITS_PER_UNIT
;
1745 /* Create the shifted version of EXPR. */
1746 if (!BYTES_BIG_ENDIAN
)
1748 shift_bytes_in_array (tmpbuf
, byte_size
, shift_amnt
);
1749 if (shift_amnt
== 0)
1754 gcc_assert (BYTES_BIG_ENDIAN
);
1755 shift_bytes_in_array_right (tmpbuf
, byte_size
, shift_amnt
);
1756 /* If shifting right forced us to move into the next byte skip the now
1765 /* Insert the bits from TMPBUF. */
1766 for (unsigned int i
= 0; i
< byte_size
; i
++)
1767 ptr
[first_byte
+ i
] |= tmpbuf
[i
];
1772 /* Sorting function for store_immediate_info objects.
1773 Sorts them by bitposition. */
1776 sort_by_bitpos (const void *x
, const void *y
)
1778 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
1779 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
1781 if ((*tmp
)->bitpos
< (*tmp2
)->bitpos
)
1783 else if ((*tmp
)->bitpos
> (*tmp2
)->bitpos
)
1786 /* If they are the same let's use the order which is guaranteed to
1788 return (*tmp
)->order
- (*tmp2
)->order
;
1791 /* Sorting function for store_immediate_info objects.
1792 Sorts them by the order field. */
1795 sort_by_order (const void *x
, const void *y
)
1797 store_immediate_info
*const *tmp
= (store_immediate_info
* const *) x
;
1798 store_immediate_info
*const *tmp2
= (store_immediate_info
* const *) y
;
1800 if ((*tmp
)->order
< (*tmp2
)->order
)
1802 else if ((*tmp
)->order
> (*tmp2
)->order
)
1808 /* Initialize a merged_store_group object from a store_immediate_info
1811 merged_store_group::merged_store_group (store_immediate_info
*info
)
1813 start
= info
->bitpos
;
1814 width
= info
->bitsize
;
1815 bitregion_start
= info
->bitregion_start
;
1816 bitregion_end
= info
->bitregion_end
;
1817 /* VAL has memory allocated for it in apply_stores once the group
1818 width has been finalized. */
1821 bit_insertion
= false;
1822 unsigned HOST_WIDE_INT align_bitpos
= 0;
1823 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
1824 &align
, &align_bitpos
);
1825 align_base
= start
- align_bitpos
;
1826 for (int i
= 0; i
< 2; ++i
)
1828 store_operand_info
&op
= info
->ops
[i
];
1829 if (op
.base_addr
== NULL_TREE
)
1832 load_align_base
[i
] = 0;
1836 get_object_alignment_1 (op
.val
, &load_align
[i
], &align_bitpos
);
1837 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
1841 stores
.safe_push (info
);
1842 last_stmt
= info
->stmt
;
1843 last_order
= info
->order
;
1844 first_stmt
= last_stmt
;
1845 first_order
= last_order
;
1849 merged_store_group::~merged_store_group ()
1855 /* Return true if the store described by INFO can be merged into the group. */
1858 merged_store_group::can_be_merged_into (store_immediate_info
*info
)
1860 /* Do not merge bswap patterns. */
1861 if (info
->rhs_code
== LROTATE_EXPR
)
1864 /* The canonical case. */
1865 if (info
->rhs_code
== stores
[0]->rhs_code
)
1868 /* BIT_INSERT_EXPR is compatible with INTEGER_CST. */
1869 if (info
->rhs_code
== BIT_INSERT_EXPR
&& stores
[0]->rhs_code
== INTEGER_CST
)
1872 if (stores
[0]->rhs_code
== BIT_INSERT_EXPR
&& info
->rhs_code
== INTEGER_CST
)
1875 /* We can turn MEM_REF into BIT_INSERT_EXPR for bit-field stores. */
1876 if (info
->rhs_code
== MEM_REF
1877 && (stores
[0]->rhs_code
== INTEGER_CST
1878 || stores
[0]->rhs_code
== BIT_INSERT_EXPR
)
1879 && info
->bitregion_start
== stores
[0]->bitregion_start
1880 && info
->bitregion_end
== stores
[0]->bitregion_end
)
1883 if (stores
[0]->rhs_code
== MEM_REF
1884 && (info
->rhs_code
== INTEGER_CST
1885 || info
->rhs_code
== BIT_INSERT_EXPR
)
1886 && info
->bitregion_start
== stores
[0]->bitregion_start
1887 && info
->bitregion_end
== stores
[0]->bitregion_end
)
1893 /* Helper method for merge_into and merge_overlapping to do
1897 merged_store_group::do_merge (store_immediate_info
*info
)
1899 bitregion_start
= MIN (bitregion_start
, info
->bitregion_start
);
1900 bitregion_end
= MAX (bitregion_end
, info
->bitregion_end
);
1902 unsigned int this_align
;
1903 unsigned HOST_WIDE_INT align_bitpos
= 0;
1904 get_object_alignment_1 (gimple_assign_lhs (info
->stmt
),
1905 &this_align
, &align_bitpos
);
1906 if (this_align
> align
)
1909 align_base
= info
->bitpos
- align_bitpos
;
1911 for (int i
= 0; i
< 2; ++i
)
1913 store_operand_info
&op
= info
->ops
[i
];
1917 get_object_alignment_1 (op
.val
, &this_align
, &align_bitpos
);
1918 if (this_align
> load_align
[i
])
1920 load_align
[i
] = this_align
;
1921 load_align_base
[i
] = op
.bitpos
- align_bitpos
;
1925 gimple
*stmt
= info
->stmt
;
1926 stores
.safe_push (info
);
1927 if (info
->order
> last_order
)
1929 last_order
= info
->order
;
1932 else if (info
->order
< first_order
)
1934 first_order
= info
->order
;
1939 /* Merge a store recorded by INFO into this merged store.
1940 The store is not overlapping with the existing recorded
1944 merged_store_group::merge_into (store_immediate_info
*info
)
1946 /* Make sure we're inserting in the position we think we're inserting. */
1947 gcc_assert (info
->bitpos
>= start
+ width
1948 && info
->bitregion_start
<= bitregion_end
);
1950 width
= info
->bitpos
+ info
->bitsize
- start
;
1954 /* Merge a store described by INFO into this merged store.
1955 INFO overlaps in some way with the current store (i.e. it's not contiguous
1956 which is handled by merged_store_group::merge_into). */
1959 merged_store_group::merge_overlapping (store_immediate_info
*info
)
1961 /* If the store extends the size of the group, extend the width. */
1962 if (info
->bitpos
+ info
->bitsize
> start
+ width
)
1963 width
= info
->bitpos
+ info
->bitsize
- start
;
1968 /* Go through all the recorded stores in this group in program order and
1969 apply their values to the VAL byte array to create the final merged
1970 value. Return true if the operation succeeded. */
1973 merged_store_group::apply_stores ()
1975 /* Make sure we have more than one store in the group, otherwise we cannot
1977 if (bitregion_start
% BITS_PER_UNIT
!= 0
1978 || bitregion_end
% BITS_PER_UNIT
!= 0
1979 || stores
.length () == 1)
1982 stores
.qsort (sort_by_order
);
1983 store_immediate_info
*info
;
1985 /* Create a power-of-2-sized buffer for native_encode_expr. */
1986 buf_size
= 1 << ceil_log2 ((bitregion_end
- bitregion_start
) / BITS_PER_UNIT
);
1987 val
= XNEWVEC (unsigned char, 2 * buf_size
);
1988 mask
= val
+ buf_size
;
1989 memset (val
, 0, buf_size
);
1990 memset (mask
, ~0U, buf_size
);
1992 FOR_EACH_VEC_ELT (stores
, i
, info
)
1994 unsigned int pos_in_buffer
= info
->bitpos
- bitregion_start
;
1996 if (info
->ops
[0].val
&& info
->ops
[0].base_addr
== NULL_TREE
)
1997 cst
= info
->ops
[0].val
;
1998 else if (info
->ops
[1].val
&& info
->ops
[1].base_addr
== NULL_TREE
)
1999 cst
= info
->ops
[1].val
;
2005 if (info
->rhs_code
== BIT_INSERT_EXPR
)
2006 bit_insertion
= true;
2008 ret
= encode_tree_to_bitpos (cst
, val
, info
->bitsize
,
2009 pos_in_buffer
, buf_size
);
2011 unsigned char *m
= mask
+ (pos_in_buffer
/ BITS_PER_UNIT
);
2012 if (BYTES_BIG_ENDIAN
)
2013 clear_bit_region_be (m
, (BITS_PER_UNIT
- 1
2014 - (pos_in_buffer
% BITS_PER_UNIT
)),
2017 clear_bit_region (m
, pos_in_buffer
% BITS_PER_UNIT
, info
->bitsize
);
2018 if (cst
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
2022 fputs ("After writing ", dump_file
);
2023 print_generic_expr (dump_file
, cst
, TDF_NONE
);
2024 fprintf (dump_file
, " of size " HOST_WIDE_INT_PRINT_DEC
2025 " at position %d\n", info
->bitsize
, pos_in_buffer
);
2026 fputs (" the merged value contains ", dump_file
);
2027 dump_char_array (dump_file
, val
, buf_size
);
2028 fputs (" the merged mask contains ", dump_file
);
2029 dump_char_array (dump_file
, mask
, buf_size
);
2031 fputs (" bit insertion is required\n", dump_file
);
2034 fprintf (dump_file
, "Failed to merge stores\n");
2039 stores
.qsort (sort_by_bitpos
);
2043 /* Structure describing the store chain. */
2045 struct imm_store_chain_info
2047 /* Doubly-linked list that imposes an order on chain processing.
2048 PNXP (prev's next pointer) points to the head of a list, or to
2049 the next field in the previous chain in the list.
2050 See pass_store_merging::m_stores_head for more rationale. */
2051 imm_store_chain_info
*next
, **pnxp
;
2053 auto_vec
<store_immediate_info
*> m_store_info
;
2054 auto_vec
<merged_store_group
*> m_merged_store_groups
;
2056 imm_store_chain_info (imm_store_chain_info
*&inspt
, tree b_a
)
2057 : next (inspt
), pnxp (&inspt
), base_addr (b_a
)
2062 gcc_checking_assert (pnxp
== next
->pnxp
);
2066 ~imm_store_chain_info ()
2071 gcc_checking_assert (&next
== next
->pnxp
);
2075 bool terminate_and_process_chain ();
2076 bool try_coalesce_bswap (merged_store_group
*, unsigned int, unsigned int);
2077 bool coalesce_immediate_stores ();
2078 bool output_merged_store (merged_store_group
*);
2079 bool output_merged_stores ();
2082 const pass_data pass_data_tree_store_merging
= {
2083 GIMPLE_PASS
, /* type */
2084 "store-merging", /* name */
2085 OPTGROUP_NONE
, /* optinfo_flags */
2086 TV_GIMPLE_STORE_MERGING
, /* tv_id */
2087 PROP_ssa
, /* properties_required */
2088 0, /* properties_provided */
2089 0, /* properties_destroyed */
2090 0, /* todo_flags_start */
2091 TODO_update_ssa
, /* todo_flags_finish */
2094 class pass_store_merging
: public gimple_opt_pass
2097 pass_store_merging (gcc::context
*ctxt
)
2098 : gimple_opt_pass (pass_data_tree_store_merging
, ctxt
), m_stores_head ()
2102 /* Pass not supported for PDP-endian, nor for insane hosts or
2103 target character sizes where native_{encode,interpret}_expr
2104 doesn't work properly. */
2108 return flag_store_merging
2109 && BYTES_BIG_ENDIAN
== WORDS_BIG_ENDIAN
2111 && BITS_PER_UNIT
== 8;
2114 virtual unsigned int execute (function
*);
2117 hash_map
<tree_operand_hash
, struct imm_store_chain_info
*> m_stores
;
2119 /* Form a doubly-linked stack of the elements of m_stores, so that
2120 we can iterate over them in a predictable way. Using this order
2121 avoids extraneous differences in the compiler output just because
2122 of tree pointer variations (e.g. different chains end up in
2123 different positions of m_stores, so they are handled in different
2124 orders, so they allocate or release SSA names in different
2125 orders, and when they get reused, subsequent passes end up
2126 getting different SSA names, which may ultimately change
2127 decisions when going out of SSA). */
2128 imm_store_chain_info
*m_stores_head
;
2130 void process_store (gimple
*);
2131 bool terminate_and_process_all_chains ();
2132 bool terminate_all_aliasing_chains (imm_store_chain_info
**, gimple
*);
2133 bool terminate_and_release_chain (imm_store_chain_info
*);
2134 }; // class pass_store_merging
2136 /* Terminate and process all recorded chains. Return true if any changes
2140 pass_store_merging::terminate_and_process_all_chains ()
2143 while (m_stores_head
)
2144 ret
|= terminate_and_release_chain (m_stores_head
);
2145 gcc_assert (m_stores
.elements () == 0);
2146 gcc_assert (m_stores_head
== NULL
);
2151 /* Terminate all chains that are affected by the statement STMT.
2152 CHAIN_INFO is the chain we should ignore from the checks if
2156 pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
2162 /* If the statement doesn't touch memory it can't alias. */
2163 if (!gimple_vuse (stmt
))
2166 tree store_lhs
= gimple_store_p (stmt
) ? gimple_get_lhs (stmt
) : NULL_TREE
;
2167 for (imm_store_chain_info
*next
= m_stores_head
, *cur
= next
; cur
; cur
= next
)
2171 /* We already checked all the stores in chain_info and terminated the
2172 chain if necessary. Skip it here. */
2173 if (chain_info
&& *chain_info
== cur
)
2176 store_immediate_info
*info
;
2178 FOR_EACH_VEC_ELT (cur
->m_store_info
, i
, info
)
2180 tree lhs
= gimple_assign_lhs (info
->stmt
);
2181 if (ref_maybe_used_by_stmt_p (stmt
, lhs
)
2182 || stmt_may_clobber_ref_p (stmt
, lhs
)
2183 || (store_lhs
&& refs_output_dependent_p (store_lhs
, lhs
)))
2185 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2187 fprintf (dump_file
, "stmt causes chain termination:\n");
2188 print_gimple_stmt (dump_file
, stmt
, 0);
2190 terminate_and_release_chain (cur
);
2200 /* Helper function. Terminate the recorded chain storing to base object
2201 BASE. Return true if the merging and output was successful. The m_stores
2202 entry is removed after the processing in any case. */
2205 pass_store_merging::terminate_and_release_chain (imm_store_chain_info
*chain_info
)
2207 bool ret
= chain_info
->terminate_and_process_chain ();
2208 m_stores
.remove (chain_info
->base_addr
);
2213 /* Return true if stmts in between FIRST (inclusive) and LAST (exclusive)
2214 may clobber REF. FIRST and LAST must be in the same basic block and
2215 have non-NULL vdef. We want to be able to sink load of REF across
2216 stores between FIRST and LAST, up to right before LAST. */
2219 stmts_may_clobber_ref_p (gimple
*first
, gimple
*last
, tree ref
)
2222 ao_ref_init (&r
, ref
);
2223 unsigned int count
= 0;
2224 tree vop
= gimple_vdef (last
);
2227 gcc_checking_assert (gimple_bb (first
) == gimple_bb (last
));
2230 stmt
= SSA_NAME_DEF_STMT (vop
);
2231 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
2233 if (gimple_store_p (stmt
)
2234 && refs_anti_dependent_p (ref
, gimple_get_lhs (stmt
)))
2236 /* Avoid quadratic compile time by bounding the number of checks
2238 if (++count
> MAX_STORE_ALIAS_CHECKS
)
2240 vop
= gimple_vuse (stmt
);
2242 while (stmt
!= first
);
2246 /* Return true if INFO->ops[IDX] is mergeable with the
2247 corresponding loads already in MERGED_STORE group.
2248 BASE_ADDR is the base address of the whole store group. */
2251 compatible_load_p (merged_store_group
*merged_store
,
2252 store_immediate_info
*info
,
2253 tree base_addr
, int idx
)
2255 store_immediate_info
*infof
= merged_store
->stores
[0];
2256 if (!info
->ops
[idx
].base_addr
2257 || maybe_ne (info
->ops
[idx
].bitpos
- infof
->ops
[idx
].bitpos
,
2258 info
->bitpos
- infof
->bitpos
)
2259 || !operand_equal_p (info
->ops
[idx
].base_addr
,
2260 infof
->ops
[idx
].base_addr
, 0))
2263 store_immediate_info
*infol
= merged_store
->stores
.last ();
2264 tree load_vuse
= gimple_vuse (info
->ops
[idx
].stmt
);
2265 /* In this case all vuses should be the same, e.g.
2266 _1 = s.a; _2 = s.b; _3 = _1 | 1; t.a = _3; _4 = _2 | 2; t.b = _4;
2268 _1 = s.a; _2 = s.b; t.a = _1; t.b = _2;
2269 and we can emit the coalesced load next to any of those loads. */
2270 if (gimple_vuse (infof
->ops
[idx
].stmt
) == load_vuse
2271 && gimple_vuse (infol
->ops
[idx
].stmt
) == load_vuse
)
2274 /* Otherwise, at least for now require that the load has the same
2275 vuse as the store. See following examples. */
2276 if (gimple_vuse (info
->stmt
) != load_vuse
)
2279 if (gimple_vuse (infof
->stmt
) != gimple_vuse (infof
->ops
[idx
].stmt
)
2281 && gimple_vuse (infol
->stmt
) != gimple_vuse (infol
->ops
[idx
].stmt
)))
2284 /* If the load is from the same location as the store, already
2285 the construction of the immediate chain info guarantees no intervening
2286 stores, so no further checks are needed. Example:
2287 _1 = s.a; _2 = _1 & -7; s.a = _2; _3 = s.b; _4 = _3 & -7; s.b = _4; */
2288 if (known_eq (info
->ops
[idx
].bitpos
, info
->bitpos
)
2289 && operand_equal_p (info
->ops
[idx
].base_addr
, base_addr
, 0))
2292 /* Otherwise, we need to punt if any of the loads can be clobbered by any
2293 of the stores in the group, or any other stores in between those.
2294 Previous calls to compatible_load_p ensured that for all the
2295 merged_store->stores IDX loads, no stmts starting with
2296 merged_store->first_stmt and ending right before merged_store->last_stmt
2297 clobbers those loads. */
2298 gimple
*first
= merged_store
->first_stmt
;
2299 gimple
*last
= merged_store
->last_stmt
;
2301 store_immediate_info
*infoc
;
2302 /* The stores are sorted by increasing store bitpos, so if info->stmt store
2303 comes before the so far first load, we'll be changing
2304 merged_store->first_stmt. In that case we need to give up if
2305 any of the earlier processed loads clobber with the stmts in the new
2307 if (info
->order
< merged_store
->first_order
)
2309 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
2310 if (stmts_may_clobber_ref_p (info
->stmt
, first
, infoc
->ops
[idx
].val
))
2314 /* Similarly, we could change merged_store->last_stmt, so ensure
2315 in that case no stmts in the new range clobber any of the earlier
2317 else if (info
->order
> merged_store
->last_order
)
2319 FOR_EACH_VEC_ELT (merged_store
->stores
, i
, infoc
)
2320 if (stmts_may_clobber_ref_p (last
, info
->stmt
, infoc
->ops
[idx
].val
))
2324 /* And finally, we'd be adding a new load to the set, ensure it isn't
2325 clobbered in the new range. */
2326 if (stmts_may_clobber_ref_p (first
, last
, info
->ops
[idx
].val
))
2329 /* Otherwise, we are looking for:
2330 _1 = s.a; _2 = _1 ^ 15; t.a = _2; _3 = s.b; _4 = _3 ^ 15; t.b = _4;
2332 _1 = s.a; t.a = _1; _2 = s.b; t.b = _2; */
2336 /* Add all refs loaded to compute VAL to REFS vector. */
2339 gather_bswap_load_refs (vec
<tree
> *refs
, tree val
)
2341 if (TREE_CODE (val
) != SSA_NAME
)
2344 gimple
*stmt
= SSA_NAME_DEF_STMT (val
);
2345 if (!is_gimple_assign (stmt
))
2348 if (gimple_assign_load_p (stmt
))
2350 refs
->safe_push (gimple_assign_rhs1 (stmt
));
2354 switch (gimple_assign_rhs_class (stmt
))
2356 case GIMPLE_BINARY_RHS
:
2357 gather_bswap_load_refs (refs
, gimple_assign_rhs2 (stmt
));
2359 case GIMPLE_UNARY_RHS
:
2360 gather_bswap_load_refs (refs
, gimple_assign_rhs1 (stmt
));
2367 /* Check if there are any stores in M_STORE_INFO after index I
2368 (where M_STORE_INFO must be sorted by sort_by_bitpos) that overlap
2369 a potential group ending with END that have their order
2370 smaller than LAST_ORDER. RHS_CODE is the kind of store in the
2371 group. Return true if there are no such stores.
2373 MEM[(long long int *)p_28] = 0;
2374 MEM[(long long int *)p_28 + 8B] = 0;
2375 MEM[(long long int *)p_28 + 16B] = 0;
2376 MEM[(long long int *)p_28 + 24B] = 0;
2378 MEM[(int *)p_28 + 8B] = _129;
2379 MEM[(int *)p_28].a = -1;
2381 MEM[(long long int *)p_28] = 0;
2382 MEM[(int *)p_28].a = -1;
2383 stmts in the current group and need to consider if it is safe to
2384 add MEM[(long long int *)p_28 + 8B] = 0; store into the same group.
2385 There is an overlap between that store and the MEM[(int *)p_28 + 8B] = _129;
2386 store though, so if we add the MEM[(long long int *)p_28 + 8B] = 0;
2387 into the group and merging of those 3 stores is successful, merged
2388 stmts will be emitted at the latest store from that group, i.e.
2389 LAST_ORDER, which is the MEM[(int *)p_28].a = -1; store.
2390 The MEM[(int *)p_28 + 8B] = _129; store that originally follows
2391 the MEM[(long long int *)p_28 + 8B] = 0; would now be before it,
2392 so we need to refuse merging MEM[(long long int *)p_28 + 8B] = 0;
2393 into the group. That way it will be its own store group and will
2394 not be touched. If RHS_CODE is INTEGER_CST and there are overlapping
2395 INTEGER_CST stores, those are mergeable using merge_overlapping,
2396 so don't return false for those. */
2399 check_no_overlap (vec
<store_immediate_info
*> m_store_info
, unsigned int i
,
2400 enum tree_code rhs_code
, unsigned int last_order
,
2401 unsigned HOST_WIDE_INT end
)
2403 unsigned int len
= m_store_info
.length ();
2404 for (++i
; i
< len
; ++i
)
2406 store_immediate_info
*info
= m_store_info
[i
];
2407 if (info
->bitpos
>= end
)
2409 if (info
->order
< last_order
2410 && (rhs_code
!= INTEGER_CST
|| info
->rhs_code
!= INTEGER_CST
))
2416 /* Return true if m_store_info[first] and at least one following store
2417 form a group which store try_size bitsize value which is byte swapped
2418 from a memory load or some value, or identity from some value.
2419 This uses the bswap pass APIs. */
2422 imm_store_chain_info::try_coalesce_bswap (merged_store_group
*merged_store
,
2424 unsigned int try_size
)
2426 unsigned int len
= m_store_info
.length (), last
= first
;
2427 unsigned HOST_WIDE_INT width
= m_store_info
[first
]->bitsize
;
2428 if (width
>= try_size
)
2430 for (unsigned int i
= first
+ 1; i
< len
; ++i
)
2432 if (m_store_info
[i
]->bitpos
!= m_store_info
[first
]->bitpos
+ width
2433 || m_store_info
[i
]->ins_stmt
== NULL
)
2435 width
+= m_store_info
[i
]->bitsize
;
2436 if (width
>= try_size
)
2442 if (width
!= try_size
)
2445 bool allow_unaligned
2446 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
2447 /* Punt if the combined store would not be aligned and we need alignment. */
2448 if (!allow_unaligned
)
2450 unsigned int align
= merged_store
->align
;
2451 unsigned HOST_WIDE_INT align_base
= merged_store
->align_base
;
2452 for (unsigned int i
= first
+ 1; i
<= last
; ++i
)
2454 unsigned int this_align
;
2455 unsigned HOST_WIDE_INT align_bitpos
= 0;
2456 get_object_alignment_1 (gimple_assign_lhs (m_store_info
[i
]->stmt
),
2457 &this_align
, &align_bitpos
);
2458 if (this_align
> align
)
2461 align_base
= m_store_info
[i
]->bitpos
- align_bitpos
;
2464 unsigned HOST_WIDE_INT align_bitpos
2465 = (m_store_info
[first
]->bitpos
- align_base
) & (align
- 1);
2467 align
= least_bit_hwi (align_bitpos
);
2468 if (align
< try_size
)
2475 case 16: type
= uint16_type_node
; break;
2476 case 32: type
= uint32_type_node
; break;
2477 case 64: type
= uint64_type_node
; break;
2478 default: gcc_unreachable ();
2480 struct symbolic_number n
;
2481 gimple
*ins_stmt
= NULL
;
2482 int vuse_store
= -1;
2483 unsigned int first_order
= merged_store
->first_order
;
2484 unsigned int last_order
= merged_store
->last_order
;
2485 gimple
*first_stmt
= merged_store
->first_stmt
;
2486 gimple
*last_stmt
= merged_store
->last_stmt
;
2487 unsigned HOST_WIDE_INT end
= merged_store
->start
+ merged_store
->width
;
2488 store_immediate_info
*infof
= m_store_info
[first
];
2490 for (unsigned int i
= first
; i
<= last
; ++i
)
2492 store_immediate_info
*info
= m_store_info
[i
];
2493 struct symbolic_number this_n
= info
->n
;
2495 if (!this_n
.base_addr
)
2496 this_n
.range
= try_size
/ BITS_PER_UNIT
;
2498 /* Update vuse in case it has changed by output_merged_stores. */
2499 this_n
.vuse
= gimple_vuse (info
->ins_stmt
);
2500 unsigned int bitpos
= info
->bitpos
- infof
->bitpos
;
2501 if (!do_shift_rotate (LSHIFT_EXPR
, &this_n
,
2503 ? try_size
- info
->bitsize
- bitpos
2506 if (this_n
.base_addr
&& vuse_store
)
2509 for (j
= first
; j
<= last
; ++j
)
2510 if (this_n
.vuse
== gimple_vuse (m_store_info
[j
]->stmt
))
2514 if (vuse_store
== 1)
2522 ins_stmt
= info
->ins_stmt
;
2526 if (n
.base_addr
&& n
.vuse
!= this_n
.vuse
)
2528 if (vuse_store
== 0)
2532 if (info
->order
> last_order
)
2534 last_order
= info
->order
;
2535 last_stmt
= info
->stmt
;
2537 else if (info
->order
< first_order
)
2539 first_order
= info
->order
;
2540 first_stmt
= info
->stmt
;
2542 end
= MAX (end
, info
->bitpos
+ info
->bitsize
);
2544 ins_stmt
= perform_symbolic_merge (ins_stmt
, &n
, info
->ins_stmt
,
2546 if (ins_stmt
== NULL
)
2551 uint64_t cmpxchg
, cmpnop
;
2552 find_bswap_or_nop_finalize (&n
, &cmpxchg
, &cmpnop
);
2554 /* A complete byte swap should make the symbolic number to start with
2555 the largest digit in the highest order byte. Unchanged symbolic
2556 number indicates a read with same endianness as target architecture. */
2557 if (n
.n
!= cmpnop
&& n
.n
!= cmpxchg
)
2560 if (n
.base_addr
== NULL_TREE
&& !is_gimple_val (n
.src
))
2563 if (!check_no_overlap (m_store_info
, last
, LROTATE_EXPR
, last_order
, end
))
2566 /* Don't handle memory copy this way if normal non-bswap processing
2567 would handle it too. */
2568 if (n
.n
== cmpnop
&& (unsigned) n
.n_ops
== last
- first
+ 1)
2571 for (i
= first
; i
<= last
; ++i
)
2572 if (m_store_info
[i
]->rhs_code
!= MEM_REF
)
2582 /* Will emit LROTATE_EXPR. */
2585 if (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
2586 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
)
2590 if (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
2591 && optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
)
2598 if (!allow_unaligned
&& n
.base_addr
)
2600 unsigned int align
= get_object_alignment (n
.src
);
2601 if (align
< try_size
)
2605 /* If each load has vuse of the corresponding store, need to verify
2606 the loads can be sunk right before the last store. */
2607 if (vuse_store
== 1)
2609 auto_vec
<tree
, 64> refs
;
2610 for (unsigned int i
= first
; i
<= last
; ++i
)
2611 gather_bswap_load_refs (&refs
,
2612 gimple_assign_rhs1 (m_store_info
[i
]->stmt
));
2616 FOR_EACH_VEC_ELT (refs
, i
, ref
)
2617 if (stmts_may_clobber_ref_p (first_stmt
, last_stmt
, ref
))
2623 infof
->ins_stmt
= ins_stmt
;
2624 for (unsigned int i
= first
; i
<= last
; ++i
)
2626 m_store_info
[i
]->rhs_code
= n
.n
== cmpxchg
? LROTATE_EXPR
: NOP_EXPR
;
2627 m_store_info
[i
]->ops
[0].base_addr
= NULL_TREE
;
2628 m_store_info
[i
]->ops
[1].base_addr
= NULL_TREE
;
2630 merged_store
->merge_into (m_store_info
[i
]);
2636 /* Go through the candidate stores recorded in m_store_info and merge them
2637 into merged_store_group objects recorded into m_merged_store_groups
2638 representing the widened stores. Return true if coalescing was successful
2639 and the number of widened stores is fewer than the original number
2643 imm_store_chain_info::coalesce_immediate_stores ()
2645 /* Anything less can't be processed. */
2646 if (m_store_info
.length () < 2)
2649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2650 fprintf (dump_file
, "Attempting to coalesce %u stores in chain\n",
2651 m_store_info
.length ());
2653 store_immediate_info
*info
;
2654 unsigned int i
, ignore
= 0;
2656 /* Order the stores by the bitposition they write to. */
2657 m_store_info
.qsort (sort_by_bitpos
);
2659 info
= m_store_info
[0];
2660 merged_store_group
*merged_store
= new merged_store_group (info
);
2661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2662 fputs ("New store group\n", dump_file
);
2664 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
2669 /* First try to handle group of stores like:
2674 using the bswap framework. */
2675 if (info
->bitpos
== merged_store
->start
+ merged_store
->width
2676 && merged_store
->stores
.length () == 1
2677 && merged_store
->stores
[0]->ins_stmt
!= NULL
2678 && info
->ins_stmt
!= NULL
)
2680 unsigned int try_size
;
2681 for (try_size
= 64; try_size
>= 16; try_size
>>= 1)
2682 if (try_coalesce_bswap (merged_store
, i
- 1, try_size
))
2687 ignore
= i
+ merged_store
->stores
.length () - 1;
2688 m_merged_store_groups
.safe_push (merged_store
);
2689 if (ignore
< m_store_info
.length ())
2690 merged_store
= new merged_store_group (m_store_info
[ignore
]);
2692 merged_store
= NULL
;
2699 Overlapping stores. */
2700 if (IN_RANGE (info
->bitpos
, merged_store
->start
,
2701 merged_store
->start
+ merged_store
->width
- 1))
2703 /* Only allow overlapping stores of constants. */
2704 if (info
->rhs_code
== INTEGER_CST
2705 && merged_store
->stores
[0]->rhs_code
== INTEGER_CST
)
2707 unsigned int last_order
2708 = MAX (merged_store
->last_order
, info
->order
);
2709 unsigned HOST_WIDE_INT end
2710 = MAX (merged_store
->start
+ merged_store
->width
,
2711 info
->bitpos
+ info
->bitsize
);
2712 if (check_no_overlap (m_store_info
, i
, INTEGER_CST
,
2715 /* check_no_overlap call above made sure there are no
2716 overlapping stores with non-INTEGER_CST rhs_code
2717 in between the first and last of the stores we've
2718 just merged. If there are any INTEGER_CST rhs_code
2719 stores in between, we need to merge_overlapping them
2720 even if in the sort_by_bitpos order there are other
2721 overlapping stores in between. Keep those stores as is.
2723 MEM[(int *)p_28] = 0;
2724 MEM[(char *)p_28 + 3B] = 1;
2725 MEM[(char *)p_28 + 1B] = 2;
2726 MEM[(char *)p_28 + 2B] = MEM[(char *)p_28 + 6B];
2727 We can't merge the zero store with the store of two and
2728 not merge anything else, because the store of one is
2729 in the original order in between those two, but in
2730 store_by_bitpos order it comes after the last store that
2731 we can't merge with them. We can merge the first 3 stores
2732 and keep the last store as is though. */
2733 unsigned int len
= m_store_info
.length (), k
= i
;
2734 for (unsigned int j
= i
+ 1; j
< len
; ++j
)
2736 store_immediate_info
*info2
= m_store_info
[j
];
2737 if (info2
->bitpos
>= end
)
2739 if (info2
->order
< last_order
)
2741 if (info2
->rhs_code
!= INTEGER_CST
)
2743 /* Normally check_no_overlap makes sure this
2744 doesn't happen, but if end grows below, then
2745 we need to process more stores than
2746 check_no_overlap verified. Example:
2747 MEM[(int *)p_5] = 0;
2748 MEM[(short *)p_5 + 3B] = 1;
2749 MEM[(char *)p_5 + 4B] = _9;
2750 MEM[(char *)p_5 + 2B] = 2; */
2755 end
= MAX (end
, info2
->bitpos
+ info2
->bitsize
);
2761 merged_store
->merge_overlapping (info
);
2763 for (unsigned int j
= i
+ 1; j
<= k
; j
++)
2765 store_immediate_info
*info2
= m_store_info
[j
];
2766 gcc_assert (info2
->bitpos
< end
);
2767 if (info2
->order
< last_order
)
2769 gcc_assert (info2
->rhs_code
== INTEGER_CST
);
2770 merged_store
->merge_overlapping (info2
);
2772 /* Other stores are kept and not merged in any
2781 /* |---store 1---||---store 2---|
2782 This store is consecutive to the previous one.
2783 Merge it into the current store group. There can be gaps in between
2784 the stores, but there can't be gaps in between bitregions. */
2785 else if (info
->bitregion_start
<= merged_store
->bitregion_end
2786 && merged_store
->can_be_merged_into (info
))
2788 store_immediate_info
*infof
= merged_store
->stores
[0];
2790 /* All the rhs_code ops that take 2 operands are commutative,
2791 swap the operands if it could make the operands compatible. */
2792 if (infof
->ops
[0].base_addr
2793 && infof
->ops
[1].base_addr
2794 && info
->ops
[0].base_addr
2795 && info
->ops
[1].base_addr
2796 && known_eq (info
->ops
[1].bitpos
- infof
->ops
[0].bitpos
,
2797 info
->bitpos
- infof
->bitpos
)
2798 && operand_equal_p (info
->ops
[1].base_addr
,
2799 infof
->ops
[0].base_addr
, 0))
2801 std::swap (info
->ops
[0], info
->ops
[1]);
2802 info
->ops_swapped_p
= true;
2804 if (check_no_overlap (m_store_info
, i
, info
->rhs_code
,
2805 MAX (merged_store
->last_order
, info
->order
),
2806 MAX (merged_store
->start
+ merged_store
->width
,
2807 info
->bitpos
+ info
->bitsize
)))
2809 /* Turn MEM_REF into BIT_INSERT_EXPR for bit-field stores. */
2810 if (info
->rhs_code
== MEM_REF
&& infof
->rhs_code
!= MEM_REF
)
2812 info
->rhs_code
= BIT_INSERT_EXPR
;
2813 info
->ops
[0].val
= gimple_assign_rhs1 (info
->stmt
);
2814 info
->ops
[0].base_addr
= NULL_TREE
;
2816 else if (infof
->rhs_code
== MEM_REF
&& info
->rhs_code
!= MEM_REF
)
2818 store_immediate_info
*infoj
;
2820 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, infoj
)
2822 infoj
->rhs_code
= BIT_INSERT_EXPR
;
2823 infoj
->ops
[0].val
= gimple_assign_rhs1 (infoj
->stmt
);
2824 infoj
->ops
[0].base_addr
= NULL_TREE
;
2827 if ((infof
->ops
[0].base_addr
2828 ? compatible_load_p (merged_store
, info
, base_addr
, 0)
2829 : !info
->ops
[0].base_addr
)
2830 && (infof
->ops
[1].base_addr
2831 ? compatible_load_p (merged_store
, info
, base_addr
, 1)
2832 : !info
->ops
[1].base_addr
))
2834 merged_store
->merge_into (info
);
2840 /* |---store 1---| <gap> |---store 2---|.
2841 Gap between stores or the rhs not compatible. Start a new group. */
2843 /* Try to apply all the stores recorded for the group to determine
2844 the bitpattern they write and discard it if that fails.
2845 This will also reject single-store groups. */
2846 if (merged_store
->apply_stores ())
2847 m_merged_store_groups
.safe_push (merged_store
);
2849 delete merged_store
;
2851 merged_store
= new merged_store_group (info
);
2852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2853 fputs ("New store group\n", dump_file
);
2856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2858 fprintf (dump_file
, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
2859 " bitpos:" HOST_WIDE_INT_PRINT_DEC
" val:",
2860 i
, info
->bitsize
, info
->bitpos
);
2861 print_generic_expr (dump_file
, gimple_assign_rhs1 (info
->stmt
));
2862 fputc ('\n', dump_file
);
2866 /* Record or discard the last store group. */
2869 if (merged_store
->apply_stores ())
2870 m_merged_store_groups
.safe_push (merged_store
);
2872 delete merged_store
;
2875 gcc_assert (m_merged_store_groups
.length () <= m_store_info
.length ());
2878 = !m_merged_store_groups
.is_empty ()
2879 && m_merged_store_groups
.length () < m_store_info
.length ();
2881 if (success
&& dump_file
)
2882 fprintf (dump_file
, "Coalescing successful!\nMerged into %u stores\n",
2883 m_merged_store_groups
.length ());
2888 /* Return the type to use for the merged stores or loads described by STMTS.
2889 This is needed to get the alias sets right. If IS_LOAD, look for rhs,
2890 otherwise lhs. Additionally set *CLIQUEP and *BASEP to MR_DEPENDENCE_*
2891 of the MEM_REFs if any. */
2894 get_alias_type_for_stmts (vec
<gimple
*> &stmts
, bool is_load
,
2895 unsigned short *cliquep
, unsigned short *basep
)
2899 tree type
= NULL_TREE
;
2900 tree ret
= NULL_TREE
;
2904 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
2906 tree ref
= is_load
? gimple_assign_rhs1 (stmt
)
2907 : gimple_assign_lhs (stmt
);
2908 tree type1
= reference_alias_ptr_type (ref
);
2909 tree base
= get_base_address (ref
);
2913 if (TREE_CODE (base
) == MEM_REF
)
2915 *cliquep
= MR_DEPENDENCE_CLIQUE (base
);
2916 *basep
= MR_DEPENDENCE_BASE (base
);
2921 if (!alias_ptr_types_compatible_p (type
, type1
))
2922 ret
= ptr_type_node
;
2923 if (TREE_CODE (base
) != MEM_REF
2924 || *cliquep
!= MR_DEPENDENCE_CLIQUE (base
)
2925 || *basep
!= MR_DEPENDENCE_BASE (base
))
2934 /* Return the location_t information we can find among the statements
2938 get_location_for_stmts (vec
<gimple
*> &stmts
)
2943 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
2944 if (gimple_has_location (stmt
))
2945 return gimple_location (stmt
);
2947 return UNKNOWN_LOCATION
;
2950 /* Used to decribe a store resulting from splitting a wide store in smaller
2951 regularly-sized stores in split_group. */
2955 unsigned HOST_WIDE_INT bytepos
;
2956 unsigned HOST_WIDE_INT size
;
2957 unsigned HOST_WIDE_INT align
;
2958 auto_vec
<store_immediate_info
*> orig_stores
;
2959 /* True if there is a single orig stmt covering the whole split store. */
2961 split_store (unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
2962 unsigned HOST_WIDE_INT
);
2965 /* Simple constructor. */
2967 split_store::split_store (unsigned HOST_WIDE_INT bp
,
2968 unsigned HOST_WIDE_INT sz
,
2969 unsigned HOST_WIDE_INT al
)
2970 : bytepos (bp
), size (sz
), align (al
), orig (false)
2972 orig_stores
.create (0);
2975 /* Record all stores in GROUP that write to the region starting at BITPOS and
2976 is of size BITSIZE. Record infos for such statements in STORES if
2977 non-NULL. The stores in GROUP must be sorted by bitposition. Return INFO
2978 if there is exactly one original store in the range. */
2980 static store_immediate_info
*
2981 find_constituent_stores (struct merged_store_group
*group
,
2982 vec
<store_immediate_info
*> *stores
,
2983 unsigned int *first
,
2984 unsigned HOST_WIDE_INT bitpos
,
2985 unsigned HOST_WIDE_INT bitsize
)
2987 store_immediate_info
*info
, *ret
= NULL
;
2989 bool second
= false;
2990 bool update_first
= true;
2991 unsigned HOST_WIDE_INT end
= bitpos
+ bitsize
;
2992 for (i
= *first
; group
->stores
.iterate (i
, &info
); ++i
)
2994 unsigned HOST_WIDE_INT stmt_start
= info
->bitpos
;
2995 unsigned HOST_WIDE_INT stmt_end
= stmt_start
+ info
->bitsize
;
2996 if (stmt_end
<= bitpos
)
2998 /* BITPOS passed to this function never decreases from within the
2999 same split_group call, so optimize and don't scan info records
3000 which are known to end before or at BITPOS next time.
3001 Only do it if all stores before this one also pass this. */
3007 update_first
= false;
3009 /* The stores in GROUP are ordered by bitposition so if we're past
3010 the region for this group return early. */
3011 if (stmt_start
>= end
)
3016 stores
->safe_push (info
);
3031 /* Return how many SSA_NAMEs used to compute value to store in the INFO
3032 store have multiple uses. If any SSA_NAME has multiple uses, also
3033 count statements needed to compute it. */
3036 count_multiple_uses (store_immediate_info
*info
)
3038 gimple
*stmt
= info
->stmt
;
3040 switch (info
->rhs_code
)
3047 if (info
->bit_not_p
)
3049 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
3050 ret
= 1; /* Fall through below to return
3051 the BIT_NOT_EXPR stmt and then
3052 BIT_{AND,IOR,XOR}_EXPR and anything it
3055 /* stmt is after this the BIT_NOT_EXPR. */
3056 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
3058 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
3060 ret
+= 1 + info
->ops
[0].bit_not_p
;
3061 if (info
->ops
[1].base_addr
)
3062 ret
+= 1 + info
->ops
[1].bit_not_p
;
3065 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
3066 /* stmt is now the BIT_*_EXPR. */
3067 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
3068 ret
+= 1 + info
->ops
[info
->ops_swapped_p
].bit_not_p
;
3069 else if (info
->ops
[info
->ops_swapped_p
].bit_not_p
)
3071 gimple
*stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
3072 if (!has_single_use (gimple_assign_rhs1 (stmt2
)))
3075 if (info
->ops
[1].base_addr
== NULL_TREE
)
3077 gcc_checking_assert (!info
->ops_swapped_p
);
3080 if (!has_single_use (gimple_assign_rhs2 (stmt
)))
3081 ret
+= 1 + info
->ops
[1 - info
->ops_swapped_p
].bit_not_p
;
3082 else if (info
->ops
[1 - info
->ops_swapped_p
].bit_not_p
)
3084 gimple
*stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
3085 if (!has_single_use (gimple_assign_rhs1 (stmt2
)))
3090 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
3091 return 1 + info
->ops
[0].bit_not_p
;
3092 else if (info
->ops
[0].bit_not_p
)
3094 stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
3095 if (!has_single_use (gimple_assign_rhs1 (stmt
)))
3099 case BIT_INSERT_EXPR
:
3100 return has_single_use (gimple_assign_rhs1 (stmt
)) ? 0 : 1;
3106 /* Split a merged store described by GROUP by populating the SPLIT_STORES
3107 vector (if non-NULL) with split_store structs describing the byte offset
3108 (from the base), the bit size and alignment of each store as well as the
3109 original statements involved in each such split group.
3110 This is to separate the splitting strategy from the statement
3111 building/emission/linking done in output_merged_store.
3112 Return number of new stores.
3113 If ALLOW_UNALIGNED_STORE is false, then all stores must be aligned.
3114 If ALLOW_UNALIGNED_LOAD is false, then all loads must be aligned.
3115 If SPLIT_STORES is NULL, it is just a dry run to count number of
3119 split_group (merged_store_group
*group
, bool allow_unaligned_store
,
3120 bool allow_unaligned_load
,
3121 vec
<struct split_store
*> *split_stores
,
3122 unsigned *total_orig
,
3123 unsigned *total_new
)
3125 unsigned HOST_WIDE_INT pos
= group
->bitregion_start
;
3126 unsigned HOST_WIDE_INT size
= group
->bitregion_end
- pos
;
3127 unsigned HOST_WIDE_INT bytepos
= pos
/ BITS_PER_UNIT
;
3128 unsigned HOST_WIDE_INT group_align
= group
->align
;
3129 unsigned HOST_WIDE_INT align_base
= group
->align_base
;
3130 unsigned HOST_WIDE_INT group_load_align
= group_align
;
3131 bool any_orig
= false;
3133 gcc_assert ((size
% BITS_PER_UNIT
== 0) && (pos
% BITS_PER_UNIT
== 0));
3135 if (group
->stores
[0]->rhs_code
== LROTATE_EXPR
3136 || group
->stores
[0]->rhs_code
== NOP_EXPR
)
3138 /* For bswap framework using sets of stores, all the checking
3139 has been done earlier in try_coalesce_bswap and needs to be
3140 emitted as a single store. */
3143 /* Avoid the old/new stmt count heuristics. It should be
3144 always beneficial. */
3151 unsigned HOST_WIDE_INT align_bitpos
3152 = (group
->start
- align_base
) & (group_align
- 1);
3153 unsigned HOST_WIDE_INT align
= group_align
;
3155 align
= least_bit_hwi (align_bitpos
);
3156 bytepos
= group
->start
/ BITS_PER_UNIT
;
3157 struct split_store
*store
3158 = new split_store (bytepos
, group
->width
, align
);
3159 unsigned int first
= 0;
3160 find_constituent_stores (group
, &store
->orig_stores
,
3161 &first
, group
->start
, group
->width
);
3162 split_stores
->safe_push (store
);
3168 unsigned int ret
= 0, first
= 0;
3169 unsigned HOST_WIDE_INT try_pos
= bytepos
;
3174 store_immediate_info
*info
= group
->stores
[0];
3177 total_orig
[0] = 1; /* The orig store. */
3178 info
= group
->stores
[0];
3179 if (info
->ops
[0].base_addr
)
3181 if (info
->ops
[1].base_addr
)
3183 switch (info
->rhs_code
)
3188 total_orig
[0]++; /* The orig BIT_*_EXPR stmt. */
3193 total_orig
[0] *= group
->stores
.length ();
3195 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
3197 total_new
[0] += count_multiple_uses (info
);
3198 total_orig
[0] += (info
->bit_not_p
3199 + info
->ops
[0].bit_not_p
3200 + info
->ops
[1].bit_not_p
);
3204 if (!allow_unaligned_load
)
3205 for (int i
= 0; i
< 2; ++i
)
3206 if (group
->load_align
[i
])
3207 group_load_align
= MIN (group_load_align
, group
->load_align
[i
]);
3211 if ((allow_unaligned_store
|| group_align
<= BITS_PER_UNIT
)
3212 && group
->mask
[try_pos
- bytepos
] == (unsigned char) ~0U)
3214 /* Skip padding bytes. */
3216 size
-= BITS_PER_UNIT
;
3220 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
3221 unsigned int try_size
= MAX_STORE_BITSIZE
, nonmasked
;
3222 unsigned HOST_WIDE_INT align_bitpos
3223 = (try_bitpos
- align_base
) & (group_align
- 1);
3224 unsigned HOST_WIDE_INT align
= group_align
;
3226 align
= least_bit_hwi (align_bitpos
);
3227 if (!allow_unaligned_store
)
3228 try_size
= MIN (try_size
, align
);
3229 if (!allow_unaligned_load
)
3231 /* If we can't do or don't want to do unaligned stores
3232 as well as loads, we need to take the loads into account
3234 unsigned HOST_WIDE_INT load_align
= group_load_align
;
3235 align_bitpos
= (try_bitpos
- align_base
) & (load_align
- 1);
3237 load_align
= least_bit_hwi (align_bitpos
);
3238 for (int i
= 0; i
< 2; ++i
)
3239 if (group
->load_align
[i
])
3242 = known_alignment (try_bitpos
3243 - group
->stores
[0]->bitpos
3244 + group
->stores
[0]->ops
[i
].bitpos
3245 - group
->load_align_base
[i
]);
3246 if (align_bitpos
& (group_load_align
- 1))
3248 unsigned HOST_WIDE_INT a
= least_bit_hwi (align_bitpos
);
3249 load_align
= MIN (load_align
, a
);
3252 try_size
= MIN (try_size
, load_align
);
3254 store_immediate_info
*info
3255 = find_constituent_stores (group
, NULL
, &first
, try_bitpos
, try_size
);
3258 /* If there is just one original statement for the range, see if
3259 we can just reuse the original store which could be even larger
3261 unsigned HOST_WIDE_INT stmt_end
3262 = ROUND_UP (info
->bitpos
+ info
->bitsize
, BITS_PER_UNIT
);
3263 info
= find_constituent_stores (group
, NULL
, &first
, try_bitpos
,
3264 stmt_end
- try_bitpos
);
3265 if (info
&& info
->bitpos
>= try_bitpos
)
3267 try_size
= stmt_end
- try_bitpos
;
3272 /* Approximate store bitsize for the case when there are no padding
3274 while (try_size
> size
)
3276 /* Now look for whole padding bytes at the end of that bitsize. */
3277 for (nonmasked
= try_size
/ BITS_PER_UNIT
; nonmasked
> 0; --nonmasked
)
3278 if (group
->mask
[try_pos
- bytepos
+ nonmasked
- 1]
3279 != (unsigned char) ~0U)
3283 /* If entire try_size range is padding, skip it. */
3284 try_pos
+= try_size
/ BITS_PER_UNIT
;
3288 /* Otherwise try to decrease try_size if second half, last 3 quarters
3289 etc. are padding. */
3290 nonmasked
*= BITS_PER_UNIT
;
3291 while (nonmasked
<= try_size
/ 2)
3293 if (!allow_unaligned_store
&& group_align
> BITS_PER_UNIT
)
3295 /* Now look for whole padding bytes at the start of that bitsize. */
3296 unsigned int try_bytesize
= try_size
/ BITS_PER_UNIT
, masked
;
3297 for (masked
= 0; masked
< try_bytesize
; ++masked
)
3298 if (group
->mask
[try_pos
- bytepos
+ masked
] != (unsigned char) ~0U)
3300 masked
*= BITS_PER_UNIT
;
3301 gcc_assert (masked
< try_size
);
3302 if (masked
>= try_size
/ 2)
3304 while (masked
>= try_size
/ 2)
3307 try_pos
+= try_size
/ BITS_PER_UNIT
;
3311 /* Need to recompute the alignment, so just retry at the new
3322 struct split_store
*store
3323 = new split_store (try_pos
, try_size
, align
);
3324 info
= find_constituent_stores (group
, &store
->orig_stores
,
3325 &first
, try_bitpos
, try_size
);
3327 && info
->bitpos
>= try_bitpos
3328 && info
->bitpos
+ info
->bitsize
<= try_bitpos
+ try_size
)
3333 split_stores
->safe_push (store
);
3336 try_pos
+= try_size
/ BITS_PER_UNIT
;
3343 struct split_store
*store
;
3344 /* If we are reusing some original stores and any of the
3345 original SSA_NAMEs had multiple uses, we need to subtract
3346 those now before we add the new ones. */
3347 if (total_new
[0] && any_orig
)
3349 FOR_EACH_VEC_ELT (*split_stores
, i
, store
)
3351 total_new
[0] -= count_multiple_uses (store
->orig_stores
[0]);
3353 total_new
[0] += ret
; /* The new store. */
3354 store_immediate_info
*info
= group
->stores
[0];
3355 if (info
->ops
[0].base_addr
)
3356 total_new
[0] += ret
;
3357 if (info
->ops
[1].base_addr
)
3358 total_new
[0] += ret
;
3359 switch (info
->rhs_code
)
3364 total_new
[0] += ret
; /* The new BIT_*_EXPR stmt. */
3369 FOR_EACH_VEC_ELT (*split_stores
, i
, store
)
3372 bool bit_not_p
[3] = { false, false, false };
3373 /* If all orig_stores have certain bit_not_p set, then
3374 we'd use a BIT_NOT_EXPR stmt and need to account for it.
3375 If some orig_stores have certain bit_not_p set, then
3376 we'd use a BIT_XOR_EXPR with a mask and need to account for
3378 FOR_EACH_VEC_ELT (store
->orig_stores
, j
, info
)
3380 if (info
->ops
[0].bit_not_p
)
3381 bit_not_p
[0] = true;
3382 if (info
->ops
[1].bit_not_p
)
3383 bit_not_p
[1] = true;
3384 if (info
->bit_not_p
)
3385 bit_not_p
[2] = true;
3387 total_new
[0] += bit_not_p
[0] + bit_not_p
[1] + bit_not_p
[2];
3395 /* Return the operation through which the operand IDX (if < 2) or
3396 result (IDX == 2) should be inverted. If NOP_EXPR, no inversion
3397 is done, if BIT_NOT_EXPR, all bits are inverted, if BIT_XOR_EXPR,
3398 the bits should be xored with mask. */
3400 static enum tree_code
3401 invert_op (split_store
*split_store
, int idx
, tree int_type
, tree
&mask
)
3404 store_immediate_info
*info
;
3405 unsigned int cnt
= 0;
3406 bool any_paddings
= false;
3407 FOR_EACH_VEC_ELT (split_store
->orig_stores
, i
, info
)
3409 bool bit_not_p
= idx
< 2 ? info
->ops
[idx
].bit_not_p
: info
->bit_not_p
;
3413 tree lhs
= gimple_assign_lhs (info
->stmt
);
3414 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
3415 && TYPE_PRECISION (TREE_TYPE (lhs
)) < info
->bitsize
)
3416 any_paddings
= true;
3422 if (cnt
== split_store
->orig_stores
.length () && !any_paddings
)
3423 return BIT_NOT_EXPR
;
3425 unsigned HOST_WIDE_INT try_bitpos
= split_store
->bytepos
* BITS_PER_UNIT
;
3426 unsigned buf_size
= split_store
->size
/ BITS_PER_UNIT
;
3428 = XALLOCAVEC (unsigned char, buf_size
);
3429 memset (buf
, ~0U, buf_size
);
3430 FOR_EACH_VEC_ELT (split_store
->orig_stores
, i
, info
)
3432 bool bit_not_p
= idx
< 2 ? info
->ops
[idx
].bit_not_p
: info
->bit_not_p
;
3435 /* Clear regions with bit_not_p and invert afterwards, rather than
3436 clear regions with !bit_not_p, so that gaps in between stores aren't
3438 unsigned HOST_WIDE_INT bitsize
= info
->bitsize
;
3439 unsigned HOST_WIDE_INT prec
= bitsize
;
3440 unsigned int pos_in_buffer
= 0;
3443 tree lhs
= gimple_assign_lhs (info
->stmt
);
3444 if (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
3445 && TYPE_PRECISION (TREE_TYPE (lhs
)) < bitsize
)
3446 prec
= TYPE_PRECISION (TREE_TYPE (lhs
));
3448 if (info
->bitpos
< try_bitpos
)
3450 gcc_assert (info
->bitpos
+ bitsize
> try_bitpos
);
3451 if (!BYTES_BIG_ENDIAN
)
3453 if (prec
<= try_bitpos
- info
->bitpos
)
3455 prec
-= try_bitpos
- info
->bitpos
;
3457 bitsize
-= try_bitpos
- info
->bitpos
;
3458 if (BYTES_BIG_ENDIAN
&& prec
> bitsize
)
3462 pos_in_buffer
= info
->bitpos
- try_bitpos
;
3465 /* If this is a bool inversion, invert just the least significant
3466 prec bits rather than all bits of it. */
3467 if (BYTES_BIG_ENDIAN
)
3469 pos_in_buffer
+= bitsize
- prec
;
3470 if (pos_in_buffer
>= split_store
->size
)
3475 if (pos_in_buffer
+ bitsize
> split_store
->size
)
3476 bitsize
= split_store
->size
- pos_in_buffer
;
3477 unsigned char *p
= buf
+ (pos_in_buffer
/ BITS_PER_UNIT
);
3478 if (BYTES_BIG_ENDIAN
)
3479 clear_bit_region_be (p
, (BITS_PER_UNIT
- 1
3480 - (pos_in_buffer
% BITS_PER_UNIT
)), bitsize
);
3482 clear_bit_region (p
, pos_in_buffer
% BITS_PER_UNIT
, bitsize
);
3484 for (unsigned int i
= 0; i
< buf_size
; ++i
)
3486 mask
= native_interpret_expr (int_type
, buf
, buf_size
);
3487 return BIT_XOR_EXPR
;
3490 /* Given a merged store group GROUP output the widened version of it.
3491 The store chain is against the base object BASE.
3492 Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
3493 unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
3494 Make sure that the number of statements output is less than the number of
3495 original statements. If a better sequence is possible emit it and
3499 imm_store_chain_info::output_merged_store (merged_store_group
*group
)
3501 split_store
*split_store
;
3503 unsigned HOST_WIDE_INT start_byte_pos
3504 = group
->bitregion_start
/ BITS_PER_UNIT
;
3506 unsigned int orig_num_stmts
= group
->stores
.length ();
3507 if (orig_num_stmts
< 2)
3510 auto_vec
<struct split_store
*, 32> split_stores
;
3511 bool allow_unaligned_store
3512 = !STRICT_ALIGNMENT
&& PARAM_VALUE (PARAM_STORE_MERGING_ALLOW_UNALIGNED
);
3513 bool allow_unaligned_load
= allow_unaligned_store
;
3514 if (allow_unaligned_store
)
3516 /* If unaligned stores are allowed, see how many stores we'd emit
3517 for unaligned and how many stores we'd emit for aligned stores.
3518 Only use unaligned stores if it allows fewer stores than aligned. */
3519 unsigned aligned_cnt
3520 = split_group (group
, false, allow_unaligned_load
, NULL
, NULL
, NULL
);
3521 unsigned unaligned_cnt
3522 = split_group (group
, true, allow_unaligned_load
, NULL
, NULL
, NULL
);
3523 if (aligned_cnt
<= unaligned_cnt
)
3524 allow_unaligned_store
= false;
3526 unsigned total_orig
, total_new
;
3527 split_group (group
, allow_unaligned_store
, allow_unaligned_load
,
3528 &split_stores
, &total_orig
, &total_new
);
3530 if (split_stores
.length () >= orig_num_stmts
)
3532 /* We didn't manage to reduce the number of statements. Bail out. */
3533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3534 fprintf (dump_file
, "Exceeded original number of stmts (%u)."
3535 " Not profitable to emit new sequence.\n",
3537 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
3541 if (total_orig
<= total_new
)
3543 /* If number of estimated new statements is above estimated original
3544 statements, bail out too. */
3545 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3546 fprintf (dump_file
, "Estimated number of original stmts (%u)"
3547 " not larger than estimated number of new"
3549 total_orig
, total_new
);
3550 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
3555 gimple_stmt_iterator last_gsi
= gsi_for_stmt (group
->last_stmt
);
3556 gimple_seq seq
= NULL
;
3557 tree last_vdef
, new_vuse
;
3558 last_vdef
= gimple_vdef (group
->last_stmt
);
3559 new_vuse
= gimple_vuse (group
->last_stmt
);
3560 tree bswap_res
= NULL_TREE
;
3562 if (group
->stores
[0]->rhs_code
== LROTATE_EXPR
3563 || group
->stores
[0]->rhs_code
== NOP_EXPR
)
3565 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
, load_type
;
3566 gimple
*ins_stmt
= group
->stores
[0]->ins_stmt
;
3567 struct symbolic_number
*n
= &group
->stores
[0]->n
;
3568 bool bswap
= group
->stores
[0]->rhs_code
== LROTATE_EXPR
;
3573 load_type
= bswap_type
= uint16_type_node
;
3576 load_type
= uint32_type_node
;
3579 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
3580 bswap_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
3584 load_type
= uint64_type_node
;
3587 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
3588 bswap_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
3595 /* If the loads have each vuse of the corresponding store,
3596 we've checked the aliasing already in try_coalesce_bswap and
3597 we want to sink the need load into seq. So need to use new_vuse
3601 if (n
->vuse
== NULL
)
3607 /* Update vuse in case it has changed by output_merged_stores. */
3608 n
->vuse
= gimple_vuse (ins_stmt
);
3610 bswap_res
= bswap_replace (gsi_start (seq
), ins_stmt
, fndecl
,
3611 bswap_type
, load_type
, n
, bswap
);
3612 gcc_assert (bswap_res
);
3615 gimple
*stmt
= NULL
;
3616 auto_vec
<gimple
*, 32> orig_stmts
;
3617 gimple_seq this_seq
;
3618 tree addr
= force_gimple_operand_1 (unshare_expr (base_addr
), &this_seq
,
3619 is_gimple_mem_ref_addr
, NULL_TREE
);
3620 gimple_seq_add_seq_without_update (&seq
, this_seq
);
3622 tree load_addr
[2] = { NULL_TREE
, NULL_TREE
};
3623 gimple_seq load_seq
[2] = { NULL
, NULL
};
3624 gimple_stmt_iterator load_gsi
[2] = { gsi_none (), gsi_none () };
3625 for (int j
= 0; j
< 2; ++j
)
3627 store_operand_info
&op
= group
->stores
[0]->ops
[j
];
3628 if (op
.base_addr
== NULL_TREE
)
3631 store_immediate_info
*infol
= group
->stores
.last ();
3632 if (gimple_vuse (op
.stmt
) == gimple_vuse (infol
->ops
[j
].stmt
))
3634 /* We can't pick the location randomly; while we've verified
3635 all the loads have the same vuse, they can be still in different
3636 basic blocks and we need to pick the one from the last bb:
3642 otherwise if we put the wider load at the q[0] load, we might
3643 segfault if q[1] is not mapped. */
3644 basic_block bb
= gimple_bb (op
.stmt
);
3645 gimple
*ostmt
= op
.stmt
;
3646 store_immediate_info
*info
;
3647 FOR_EACH_VEC_ELT (group
->stores
, i
, info
)
3649 gimple
*tstmt
= info
->ops
[j
].stmt
;
3650 basic_block tbb
= gimple_bb (tstmt
);
3651 if (dominated_by_p (CDI_DOMINATORS
, tbb
, bb
))
3657 load_gsi
[j
] = gsi_for_stmt (ostmt
);
3659 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
3660 &load_seq
[j
], is_gimple_mem_ref_addr
,
3663 else if (operand_equal_p (base_addr
, op
.base_addr
, 0))
3664 load_addr
[j
] = addr
;
3668 = force_gimple_operand_1 (unshare_expr (op
.base_addr
),
3669 &this_seq
, is_gimple_mem_ref_addr
,
3671 gimple_seq_add_seq_without_update (&seq
, this_seq
);
3675 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
3677 unsigned HOST_WIDE_INT try_size
= split_store
->size
;
3678 unsigned HOST_WIDE_INT try_pos
= split_store
->bytepos
;
3679 unsigned HOST_WIDE_INT try_bitpos
= try_pos
* BITS_PER_UNIT
;
3680 unsigned HOST_WIDE_INT align
= split_store
->align
;
3683 if (split_store
->orig
)
3685 /* If there is just a single constituent store which covers
3686 the whole area, just reuse the lhs and rhs. */
3687 gimple
*orig_stmt
= split_store
->orig_stores
[0]->stmt
;
3688 dest
= gimple_assign_lhs (orig_stmt
);
3689 src
= gimple_assign_rhs1 (orig_stmt
);
3690 loc
= gimple_location (orig_stmt
);
3694 store_immediate_info
*info
;
3695 unsigned short clique
, base
;
3697 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
3698 orig_stmts
.safe_push (info
->stmt
);
3700 = get_alias_type_for_stmts (orig_stmts
, false, &clique
, &base
);
3701 loc
= get_location_for_stmts (orig_stmts
);
3702 orig_stmts
.truncate (0);
3704 tree int_type
= build_nonstandard_integer_type (try_size
, UNSIGNED
);
3705 int_type
= build_aligned_type (int_type
, align
);
3706 dest
= fold_build2 (MEM_REF
, int_type
, addr
,
3707 build_int_cst (offset_type
, try_pos
));
3708 if (TREE_CODE (dest
) == MEM_REF
)
3710 MR_DEPENDENCE_CLIQUE (dest
) = clique
;
3711 MR_DEPENDENCE_BASE (dest
) = base
;
3716 mask
= integer_zero_node
;
3718 mask
= native_interpret_expr (int_type
,
3719 group
->mask
+ try_pos
3725 j
< 1 + (split_store
->orig_stores
[0]->ops
[1].val
!= NULL_TREE
);
3728 store_operand_info
&op
= split_store
->orig_stores
[0]->ops
[j
];
3731 else if (op
.base_addr
)
3733 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
3734 orig_stmts
.safe_push (info
->ops
[j
].stmt
);
3736 offset_type
= get_alias_type_for_stmts (orig_stmts
, true,
3738 location_t load_loc
= get_location_for_stmts (orig_stmts
);
3739 orig_stmts
.truncate (0);
3741 unsigned HOST_WIDE_INT load_align
= group
->load_align
[j
];
3742 unsigned HOST_WIDE_INT align_bitpos
3743 = known_alignment (try_bitpos
3744 - split_store
->orig_stores
[0]->bitpos
3746 if (align_bitpos
& (load_align
- 1))
3747 load_align
= least_bit_hwi (align_bitpos
);
3750 = build_nonstandard_integer_type (try_size
, UNSIGNED
);
3752 = build_aligned_type (load_int_type
, load_align
);
3754 poly_uint64 load_pos
3755 = exact_div (try_bitpos
3756 - split_store
->orig_stores
[0]->bitpos
3759 ops
[j
] = fold_build2 (MEM_REF
, load_int_type
, load_addr
[j
],
3760 build_int_cst (offset_type
, load_pos
));
3761 if (TREE_CODE (ops
[j
]) == MEM_REF
)
3763 MR_DEPENDENCE_CLIQUE (ops
[j
]) = clique
;
3764 MR_DEPENDENCE_BASE (ops
[j
]) = base
;
3766 if (!integer_zerop (mask
))
3767 /* The load might load some bits (that will be masked off
3768 later on) uninitialized, avoid -W*uninitialized
3769 warnings in that case. */
3770 TREE_NO_WARNING (ops
[j
]) = 1;
3772 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3774 gimple_set_location (stmt
, load_loc
);
3775 if (gsi_bb (load_gsi
[j
]))
3777 gimple_set_vuse (stmt
, gimple_vuse (op
.stmt
));
3778 gimple_seq_add_stmt_without_update (&load_seq
[j
], stmt
);
3782 gimple_set_vuse (stmt
, new_vuse
);
3783 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3785 ops
[j
] = gimple_assign_lhs (stmt
);
3787 enum tree_code inv_op
3788 = invert_op (split_store
, j
, int_type
, xor_mask
);
3789 if (inv_op
!= NOP_EXPR
)
3791 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3792 inv_op
, ops
[j
], xor_mask
);
3793 gimple_set_location (stmt
, load_loc
);
3794 ops
[j
] = gimple_assign_lhs (stmt
);
3796 if (gsi_bb (load_gsi
[j
]))
3797 gimple_seq_add_stmt_without_update (&load_seq
[j
],
3800 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3804 ops
[j
] = native_interpret_expr (int_type
,
3805 group
->val
+ try_pos
3810 switch (split_store
->orig_stores
[0]->rhs_code
)
3815 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
3817 tree rhs1
= gimple_assign_rhs1 (info
->stmt
);
3818 orig_stmts
.safe_push (SSA_NAME_DEF_STMT (rhs1
));
3821 bit_loc
= get_location_for_stmts (orig_stmts
);
3822 orig_stmts
.truncate (0);
3825 = gimple_build_assign (make_ssa_name (int_type
),
3826 split_store
->orig_stores
[0]->rhs_code
,
3828 gimple_set_location (stmt
, bit_loc
);
3829 /* If there is just one load and there is a separate
3830 load_seq[0], emit the bitwise op right after it. */
3831 if (load_addr
[1] == NULL_TREE
&& gsi_bb (load_gsi
[0]))
3832 gimple_seq_add_stmt_without_update (&load_seq
[0], stmt
);
3833 /* Otherwise, if at least one load is in seq, we need to
3834 emit the bitwise op right before the store. If there
3835 are two loads and are emitted somewhere else, it would
3836 be better to emit the bitwise op as early as possible;
3837 we don't track where that would be possible right now
3840 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3841 src
= gimple_assign_lhs (stmt
);
3843 enum tree_code inv_op
;
3844 inv_op
= invert_op (split_store
, 2, int_type
, xor_mask
);
3845 if (inv_op
!= NOP_EXPR
)
3847 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3848 inv_op
, src
, xor_mask
);
3849 gimple_set_location (stmt
, bit_loc
);
3850 if (load_addr
[1] == NULL_TREE
&& gsi_bb (load_gsi
[0]))
3851 gimple_seq_add_stmt_without_update (&load_seq
[0], stmt
);
3853 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3854 src
= gimple_assign_lhs (stmt
);
3860 if (!is_gimple_val (src
))
3862 stmt
= gimple_build_assign (make_ssa_name (TREE_TYPE (src
)),
3864 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3865 src
= gimple_assign_lhs (stmt
);
3867 if (!useless_type_conversion_p (int_type
, TREE_TYPE (src
)))
3869 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3871 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3872 src
= gimple_assign_lhs (stmt
);
3874 inv_op
= invert_op (split_store
, 2, int_type
, xor_mask
);
3875 if (inv_op
!= NOP_EXPR
)
3877 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3878 inv_op
, src
, xor_mask
);
3879 gimple_set_location (stmt
, loc
);
3880 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3881 src
= gimple_assign_lhs (stmt
);
3889 /* If bit insertion is required, we use the source as an accumulator
3890 into which the successive bit-field values are manually inserted.
3891 FIXME: perhaps use BIT_INSERT_EXPR instead in some cases? */
3892 if (group
->bit_insertion
)
3893 FOR_EACH_VEC_ELT (split_store
->orig_stores
, k
, info
)
3894 if (info
->rhs_code
== BIT_INSERT_EXPR
3895 && info
->bitpos
< try_bitpos
+ try_size
3896 && info
->bitpos
+ info
->bitsize
> try_bitpos
)
3898 /* Mask, truncate, convert to final type, shift and ior into
3899 the accumulator. Note that every step can be a no-op. */
3900 const HOST_WIDE_INT start_gap
= info
->bitpos
- try_bitpos
;
3901 const HOST_WIDE_INT end_gap
3902 = (try_bitpos
+ try_size
) - (info
->bitpos
+ info
->bitsize
);
3903 tree tem
= info
->ops
[0].val
;
3904 if (TYPE_PRECISION (TREE_TYPE (tem
)) <= info
->bitsize
)
3907 = build_nonstandard_integer_type (info
->bitsize
,
3909 tem
= gimple_convert (&seq
, loc
, bitfield_type
, tem
);
3911 else if ((BYTES_BIG_ENDIAN
? start_gap
: end_gap
) > 0)
3913 const unsigned HOST_WIDE_INT imask
3914 = (HOST_WIDE_INT_1U
<< info
->bitsize
) - 1;
3915 tem
= gimple_build (&seq
, loc
,
3916 BIT_AND_EXPR
, TREE_TYPE (tem
), tem
,
3917 build_int_cst (TREE_TYPE (tem
),
3920 const HOST_WIDE_INT shift
3921 = (BYTES_BIG_ENDIAN
? end_gap
: start_gap
);
3923 tem
= gimple_build (&seq
, loc
,
3924 RSHIFT_EXPR
, TREE_TYPE (tem
), tem
,
3925 build_int_cst (NULL_TREE
, -shift
));
3926 tem
= gimple_convert (&seq
, loc
, int_type
, tem
);
3928 tem
= gimple_build (&seq
, loc
,
3929 LSHIFT_EXPR
, int_type
, tem
,
3930 build_int_cst (NULL_TREE
, shift
));
3931 src
= gimple_build (&seq
, loc
,
3932 BIT_IOR_EXPR
, int_type
, tem
, src
);
3935 if (!integer_zerop (mask
))
3937 tree tem
= make_ssa_name (int_type
);
3938 tree load_src
= unshare_expr (dest
);
3939 /* The load might load some or all bits uninitialized,
3940 avoid -W*uninitialized warnings in that case.
3941 As optimization, it would be nice if all the bits are
3942 provably uninitialized (no stores at all yet or previous
3943 store a CLOBBER) we'd optimize away the load and replace
3945 TREE_NO_WARNING (load_src
) = 1;
3946 stmt
= gimple_build_assign (tem
, load_src
);
3947 gimple_set_location (stmt
, loc
);
3948 gimple_set_vuse (stmt
, new_vuse
);
3949 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3951 /* FIXME: If there is a single chunk of zero bits in mask,
3952 perhaps use BIT_INSERT_EXPR instead? */
3953 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3954 BIT_AND_EXPR
, tem
, mask
);
3955 gimple_set_location (stmt
, loc
);
3956 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3957 tem
= gimple_assign_lhs (stmt
);
3959 if (TREE_CODE (src
) == INTEGER_CST
)
3960 src
= wide_int_to_tree (int_type
,
3961 wi::bit_and_not (wi::to_wide (src
),
3962 wi::to_wide (mask
)));
3966 = wide_int_to_tree (int_type
,
3967 wi::bit_not (wi::to_wide (mask
)));
3968 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3969 BIT_AND_EXPR
, src
, nmask
);
3970 gimple_set_location (stmt
, loc
);
3971 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3972 src
= gimple_assign_lhs (stmt
);
3974 stmt
= gimple_build_assign (make_ssa_name (int_type
),
3975 BIT_IOR_EXPR
, tem
, src
);
3976 gimple_set_location (stmt
, loc
);
3977 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3978 src
= gimple_assign_lhs (stmt
);
3982 stmt
= gimple_build_assign (dest
, src
);
3983 gimple_set_location (stmt
, loc
);
3984 gimple_set_vuse (stmt
, new_vuse
);
3985 gimple_seq_add_stmt_without_update (&seq
, stmt
);
3988 if (i
< split_stores
.length () - 1)
3989 new_vdef
= make_ssa_name (gimple_vop (cfun
), stmt
);
3991 new_vdef
= last_vdef
;
3993 gimple_set_vdef (stmt
, new_vdef
);
3994 SSA_NAME_DEF_STMT (new_vdef
) = stmt
;
3995 new_vuse
= new_vdef
;
3998 FOR_EACH_VEC_ELT (split_stores
, i
, split_store
)
4005 "New sequence of %u stores to replace old one of %u stores\n",
4006 split_stores
.length (), orig_num_stmts
);
4007 if (dump_flags
& TDF_DETAILS
)
4008 print_gimple_seq (dump_file
, seq
, 0, TDF_VOPS
| TDF_MEMSYMS
);
4010 gsi_insert_seq_after (&last_gsi
, seq
, GSI_SAME_STMT
);
4011 for (int j
= 0; j
< 2; ++j
)
4013 gsi_insert_seq_after (&load_gsi
[j
], load_seq
[j
], GSI_SAME_STMT
);
4018 /* Process the merged_store_group objects created in the coalescing phase.
4019 The stores are all against the base object BASE.
4020 Try to output the widened stores and delete the original statements if
4021 successful. Return true iff any changes were made. */
4024 imm_store_chain_info::output_merged_stores ()
4027 merged_store_group
*merged_store
;
4029 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_store
)
4031 if (output_merged_store (merged_store
))
4034 store_immediate_info
*store
;
4035 FOR_EACH_VEC_ELT (merged_store
->stores
, j
, store
)
4037 gimple
*stmt
= store
->stmt
;
4038 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
4039 gsi_remove (&gsi
, true);
4040 if (stmt
!= merged_store
->last_stmt
)
4042 unlink_stmt_vdef (stmt
);
4043 release_defs (stmt
);
4049 if (ret
&& dump_file
)
4050 fprintf (dump_file
, "Merging successful!\n");
4055 /* Coalesce the store_immediate_info objects recorded against the base object
4056 BASE in the first phase and output them.
4057 Delete the allocated structures.
4058 Return true if any changes were made. */
4061 imm_store_chain_info::terminate_and_process_chain ()
4063 /* Process store chain. */
4065 if (m_store_info
.length () > 1)
4067 ret
= coalesce_immediate_stores ();
4069 ret
= output_merged_stores ();
4072 /* Delete all the entries we allocated ourselves. */
4073 store_immediate_info
*info
;
4075 FOR_EACH_VEC_ELT (m_store_info
, i
, info
)
4078 merged_store_group
*merged_info
;
4079 FOR_EACH_VEC_ELT (m_merged_store_groups
, i
, merged_info
)
4085 /* Return true iff LHS is a destination potentially interesting for
4086 store merging. In practice these are the codes that get_inner_reference
4090 lhs_valid_for_store_merging_p (tree lhs
)
4092 tree_code code
= TREE_CODE (lhs
);
4094 if (code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
|| code
== MEM_REF
4095 || code
== COMPONENT_REF
|| code
== BIT_FIELD_REF
)
4101 /* Return true if the tree RHS is a constant we want to consider
4102 during store merging. In practice accept all codes that
4103 native_encode_expr accepts. */
4106 rhs_valid_for_store_merging_p (tree rhs
)
4108 unsigned HOST_WIDE_INT size
;
4109 return (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (rhs
))).is_constant (&size
)
4110 && native_encode_expr (rhs
, NULL
, size
) != 0);
4113 /* If MEM is a memory reference usable for store merging (either as
4114 store destination or for loads), return the non-NULL base_addr
4115 and set *PBITSIZE, *PBITPOS, *PBITREGION_START and *PBITREGION_END.
4116 Otherwise return NULL, *PBITPOS should be still valid even for that
4120 mem_valid_for_store_merging (tree mem
, poly_uint64
*pbitsize
,
4121 poly_uint64
*pbitpos
,
4122 poly_uint64
*pbitregion_start
,
4123 poly_uint64
*pbitregion_end
)
4125 poly_int64 bitsize
, bitpos
;
4126 poly_uint64 bitregion_start
= 0, bitregion_end
= 0;
4128 int unsignedp
= 0, reversep
= 0, volatilep
= 0;
4130 tree base_addr
= get_inner_reference (mem
, &bitsize
, &bitpos
, &offset
, &mode
,
4131 &unsignedp
, &reversep
, &volatilep
);
4132 *pbitsize
= bitsize
;
4133 if (known_eq (bitsize
, 0))
4136 if (TREE_CODE (mem
) == COMPONENT_REF
4137 && DECL_BIT_FIELD_TYPE (TREE_OPERAND (mem
, 1)))
4139 get_bit_range (&bitregion_start
, &bitregion_end
, mem
, &bitpos
, &offset
);
4140 if (maybe_ne (bitregion_end
, 0U))
4147 /* We do not want to rewrite TARGET_MEM_REFs. */
4148 if (TREE_CODE (base_addr
) == TARGET_MEM_REF
)
4150 /* In some cases get_inner_reference may return a
4151 MEM_REF [ptr + byteoffset]. For the purposes of this pass
4152 canonicalize the base_addr to MEM_REF [ptr] and take
4153 byteoffset into account in the bitpos. This occurs in
4154 PR 23684 and this way we can catch more chains. */
4155 else if (TREE_CODE (base_addr
) == MEM_REF
)
4157 poly_offset_int byte_off
= mem_ref_offset (base_addr
);
4158 poly_offset_int bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
4160 if (known_ge (bit_off
, 0) && bit_off
.to_shwi (&bitpos
))
4162 if (maybe_ne (bitregion_end
, 0U))
4164 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
4165 bit_off
+= bitregion_start
;
4166 if (bit_off
.to_uhwi (&bitregion_start
))
4168 bit_off
= byte_off
<< LOG2_BITS_PER_UNIT
;
4169 bit_off
+= bitregion_end
;
4170 if (!bit_off
.to_uhwi (&bitregion_end
))
4179 base_addr
= TREE_OPERAND (base_addr
, 0);
4181 /* get_inner_reference returns the base object, get at its
4185 if (maybe_lt (bitpos
, 0))
4187 base_addr
= build_fold_addr_expr (base_addr
);
4190 if (known_eq (bitregion_end
, 0U))
4192 bitregion_start
= round_down_to_byte_boundary (bitpos
);
4193 bitregion_end
= bitpos
;
4194 bitregion_end
= round_up_to_byte_boundary (bitregion_end
+ bitsize
);
4197 if (offset
!= NULL_TREE
)
4199 /* If the access is variable offset then a base decl has to be
4200 address-taken to be able to emit pointer-based stores to it.
4201 ??? We might be able to get away with re-using the original
4202 base up to the first variable part and then wrapping that inside
4204 tree base
= get_base_address (base_addr
);
4206 || (DECL_P (base
) && ! TREE_ADDRESSABLE (base
)))
4209 base_addr
= build2 (POINTER_PLUS_EXPR
, TREE_TYPE (base_addr
),
4213 *pbitsize
= bitsize
;
4215 *pbitregion_start
= bitregion_start
;
4216 *pbitregion_end
= bitregion_end
;
4220 /* Return true if STMT is a load that can be used for store merging.
4221 In that case fill in *OP. BITSIZE, BITPOS, BITREGION_START and
4222 BITREGION_END are properties of the corresponding store. */
4225 handled_load (gimple
*stmt
, store_operand_info
*op
,
4226 poly_uint64 bitsize
, poly_uint64 bitpos
,
4227 poly_uint64 bitregion_start
, poly_uint64 bitregion_end
)
4229 if (!is_gimple_assign (stmt
))
4231 if (gimple_assign_rhs_code (stmt
) == BIT_NOT_EXPR
)
4233 tree rhs1
= gimple_assign_rhs1 (stmt
);
4234 if (TREE_CODE (rhs1
) == SSA_NAME
4235 && handled_load (SSA_NAME_DEF_STMT (rhs1
), op
, bitsize
, bitpos
,
4236 bitregion_start
, bitregion_end
))
4238 /* Don't allow _1 = load; _2 = ~1; _3 = ~_2; which should have
4239 been optimized earlier, but if allowed here, would confuse the
4240 multiple uses counting. */
4243 op
->bit_not_p
= !op
->bit_not_p
;
4248 if (gimple_vuse (stmt
)
4249 && gimple_assign_load_p (stmt
)
4250 && !stmt_can_throw_internal (stmt
)
4251 && !gimple_has_volatile_ops (stmt
))
4253 tree mem
= gimple_assign_rhs1 (stmt
);
4255 = mem_valid_for_store_merging (mem
, &op
->bitsize
, &op
->bitpos
,
4256 &op
->bitregion_start
,
4257 &op
->bitregion_end
);
4258 if (op
->base_addr
!= NULL_TREE
4259 && known_eq (op
->bitsize
, bitsize
)
4260 && multiple_p (op
->bitpos
- bitpos
, BITS_PER_UNIT
)
4261 && known_ge (op
->bitpos
- op
->bitregion_start
,
4262 bitpos
- bitregion_start
)
4263 && known_ge (op
->bitregion_end
- op
->bitpos
,
4264 bitregion_end
- bitpos
))
4268 op
->bit_not_p
= false;
4275 /* Record the store STMT for store merging optimization if it can be
4279 pass_store_merging::process_store (gimple
*stmt
)
4281 tree lhs
= gimple_assign_lhs (stmt
);
4282 tree rhs
= gimple_assign_rhs1 (stmt
);
4283 poly_uint64 bitsize
, bitpos
;
4284 poly_uint64 bitregion_start
, bitregion_end
;
4286 = mem_valid_for_store_merging (lhs
, &bitsize
, &bitpos
,
4287 &bitregion_start
, &bitregion_end
);
4288 if (known_eq (bitsize
, 0U))
4291 bool invalid
= (base_addr
== NULL_TREE
4292 || (maybe_gt (bitsize
,
4293 (unsigned int) MAX_BITSIZE_MODE_ANY_INT
)
4294 && (TREE_CODE (rhs
) != INTEGER_CST
)));
4295 enum tree_code rhs_code
= ERROR_MARK
;
4296 bool bit_not_p
= false;
4297 struct symbolic_number n
;
4298 gimple
*ins_stmt
= NULL
;
4299 store_operand_info ops
[2];
4302 else if (rhs_valid_for_store_merging_p (rhs
))
4304 rhs_code
= INTEGER_CST
;
4307 else if (TREE_CODE (rhs
) != SSA_NAME
)
4311 gimple
*def_stmt
= SSA_NAME_DEF_STMT (rhs
), *def_stmt1
, *def_stmt2
;
4312 if (!is_gimple_assign (def_stmt
))
4314 else if (handled_load (def_stmt
, &ops
[0], bitsize
, bitpos
,
4315 bitregion_start
, bitregion_end
))
4317 else if (gimple_assign_rhs_code (def_stmt
) == BIT_NOT_EXPR
)
4319 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
4320 if (TREE_CODE (rhs1
) == SSA_NAME
4321 && is_gimple_assign (SSA_NAME_DEF_STMT (rhs1
)))
4324 def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
4328 if (rhs_code
== ERROR_MARK
&& !invalid
)
4329 switch ((rhs_code
= gimple_assign_rhs_code (def_stmt
)))
4335 rhs1
= gimple_assign_rhs1 (def_stmt
);
4336 rhs2
= gimple_assign_rhs2 (def_stmt
);
4338 if (TREE_CODE (rhs1
) != SSA_NAME
)
4340 def_stmt1
= SSA_NAME_DEF_STMT (rhs1
);
4341 if (!is_gimple_assign (def_stmt1
)
4342 || !handled_load (def_stmt1
, &ops
[0], bitsize
, bitpos
,
4343 bitregion_start
, bitregion_end
))
4345 if (rhs_valid_for_store_merging_p (rhs2
))
4347 else if (TREE_CODE (rhs2
) != SSA_NAME
)
4351 def_stmt2
= SSA_NAME_DEF_STMT (rhs2
);
4352 if (!is_gimple_assign (def_stmt2
))
4354 else if (!handled_load (def_stmt2
, &ops
[1], bitsize
, bitpos
,
4355 bitregion_start
, bitregion_end
))
4365 unsigned HOST_WIDE_INT const_bitsize
;
4366 if (bitsize
.is_constant (&const_bitsize
)
4367 && (const_bitsize
% BITS_PER_UNIT
) == 0
4368 && const_bitsize
<= 64
4369 && multiple_p (bitpos
, BITS_PER_UNIT
))
4371 ins_stmt
= find_bswap_or_nop_1 (def_stmt
, &n
, 12);
4375 for (unsigned HOST_WIDE_INT i
= 0;
4377 i
+= BITS_PER_UNIT
, nn
>>= BITS_PER_MARKER
)
4378 if ((nn
& MARKER_MASK
) == 0
4379 || (nn
& MARKER_MASK
) == MARKER_BYTE_UNKNOWN
)
4388 rhs_code
= LROTATE_EXPR
;
4389 ops
[0].base_addr
= NULL_TREE
;
4390 ops
[1].base_addr
= NULL_TREE
;
4398 && bitsize
.is_constant (&const_bitsize
)
4399 && ((const_bitsize
% BITS_PER_UNIT
) != 0
4400 || !multiple_p (bitpos
, BITS_PER_UNIT
))
4401 && const_bitsize
<= 64)
4403 /* Bypass a conversion to the bit-field type. */
4405 && is_gimple_assign (def_stmt
)
4406 && CONVERT_EXPR_CODE_P (rhs_code
))
4408 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
4409 if (TREE_CODE (rhs1
) == SSA_NAME
4410 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1
)))
4413 rhs_code
= BIT_INSERT_EXPR
;
4416 ops
[0].base_addr
= NULL_TREE
;
4417 ops
[1].base_addr
= NULL_TREE
;
4422 unsigned HOST_WIDE_INT const_bitsize
, const_bitpos
;
4423 unsigned HOST_WIDE_INT const_bitregion_start
, const_bitregion_end
;
4425 || !bitsize
.is_constant (&const_bitsize
)
4426 || !bitpos
.is_constant (&const_bitpos
)
4427 || !bitregion_start
.is_constant (&const_bitregion_start
)
4428 || !bitregion_end
.is_constant (&const_bitregion_end
))
4430 terminate_all_aliasing_chains (NULL
, stmt
);
4435 memset (&n
, 0, sizeof (n
));
4437 struct imm_store_chain_info
**chain_info
= NULL
;
4439 chain_info
= m_stores
.get (base_addr
);
4441 store_immediate_info
*info
;
4444 unsigned int ord
= (*chain_info
)->m_store_info
.length ();
4445 info
= new store_immediate_info (const_bitsize
, const_bitpos
,
4446 const_bitregion_start
,
4447 const_bitregion_end
,
4448 stmt
, ord
, rhs_code
, n
, ins_stmt
,
4449 bit_not_p
, ops
[0], ops
[1]);
4450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4452 fprintf (dump_file
, "Recording immediate store from stmt:\n");
4453 print_gimple_stmt (dump_file
, stmt
, 0);
4455 (*chain_info
)->m_store_info
.safe_push (info
);
4456 terminate_all_aliasing_chains (chain_info
, stmt
);
4457 /* If we reach the limit of stores to merge in a chain terminate and
4458 process the chain now. */
4459 if ((*chain_info
)->m_store_info
.length ()
4460 == (unsigned int) PARAM_VALUE (PARAM_MAX_STORES_TO_MERGE
))
4462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4464 "Reached maximum number of statements to merge:\n");
4465 terminate_and_release_chain (*chain_info
);
4470 /* Store aliases any existing chain? */
4471 terminate_all_aliasing_chains (NULL
, stmt
);
4472 /* Start a new chain. */
4473 struct imm_store_chain_info
*new_chain
4474 = new imm_store_chain_info (m_stores_head
, base_addr
);
4475 info
= new store_immediate_info (const_bitsize
, const_bitpos
,
4476 const_bitregion_start
,
4477 const_bitregion_end
,
4478 stmt
, 0, rhs_code
, n
, ins_stmt
,
4479 bit_not_p
, ops
[0], ops
[1]);
4480 new_chain
->m_store_info
.safe_push (info
);
4481 m_stores
.put (base_addr
, new_chain
);
4482 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4484 fprintf (dump_file
, "Starting new chain with statement:\n");
4485 print_gimple_stmt (dump_file
, stmt
, 0);
4486 fprintf (dump_file
, "The base object is:\n");
4487 print_generic_expr (dump_file
, base_addr
);
4488 fprintf (dump_file
, "\n");
4492 /* Entry point for the pass. Go over each basic block recording chains of
4493 immediate stores. Upon encountering a terminating statement (as defined
4494 by stmt_terminates_chain_p) process the recorded stores and emit the widened
4498 pass_store_merging::execute (function
*fun
)
4501 hash_set
<gimple
*> orig_stmts
;
4503 calculate_dominance_info (CDI_DOMINATORS
);
4505 FOR_EACH_BB_FN (bb
, fun
)
4507 gimple_stmt_iterator gsi
;
4508 unsigned HOST_WIDE_INT num_statements
= 0;
4509 /* Record the original statements so that we can keep track of
4510 statements emitted in this pass and not re-process new
4512 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4514 if (is_gimple_debug (gsi_stmt (gsi
)))
4517 if (++num_statements
>= 2)
4521 if (num_statements
< 2)
4524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4525 fprintf (dump_file
, "Processing basic block <%d>:\n", bb
->index
);
4527 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4529 gimple
*stmt
= gsi_stmt (gsi
);
4531 if (is_gimple_debug (stmt
))
4534 if (gimple_has_volatile_ops (stmt
))
4536 /* Terminate all chains. */
4537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4538 fprintf (dump_file
, "Volatile access terminates "
4540 terminate_and_process_all_chains ();
4544 if (gimple_assign_single_p (stmt
) && gimple_vdef (stmt
)
4545 && !stmt_can_throw_internal (stmt
)
4546 && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt
)))
4547 process_store (stmt
);
4549 terminate_all_aliasing_chains (NULL
, stmt
);
4551 terminate_and_process_all_chains ();
4558 /* Construct and return a store merging pass object. */
4561 make_pass_store_merging (gcc::context
*ctxt
)
4563 return new pass_store_merging (ctxt
);
4568 namespace selftest
{
4570 /* Selftests for store merging helpers. */
4572 /* Assert that all elements of the byte arrays X and Y, both of length N
4576 verify_array_eq (unsigned char *x
, unsigned char *y
, unsigned int n
)
4578 for (unsigned int i
= 0; i
< n
; i
++)
4582 fprintf (stderr
, "Arrays do not match. X:\n");
4583 dump_char_array (stderr
, x
, n
);
4584 fprintf (stderr
, "Y:\n");
4585 dump_char_array (stderr
, y
, n
);
4587 ASSERT_EQ (x
[i
], y
[i
]);
4591 /* Test shift_bytes_in_array and that it carries bits across between
4595 verify_shift_bytes_in_array (void)
4598 00011111 | 11100000. */
4599 unsigned char orig
[2] = { 0xe0, 0x1f };
4600 unsigned char in
[2];
4601 memcpy (in
, orig
, sizeof orig
);
4603 unsigned char expected
[2] = { 0x80, 0x7f };
4604 shift_bytes_in_array (in
, sizeof (in
), 2);
4605 verify_array_eq (in
, expected
, sizeof (in
));
4607 memcpy (in
, orig
, sizeof orig
);
4608 memcpy (expected
, orig
, sizeof orig
);
4609 /* Check that shifting by zero doesn't change anything. */
4610 shift_bytes_in_array (in
, sizeof (in
), 0);
4611 verify_array_eq (in
, expected
, sizeof (in
));
4615 /* Test shift_bytes_in_array_right and that it carries bits across between
4619 verify_shift_bytes_in_array_right (void)
4622 00011111 | 11100000. */
4623 unsigned char orig
[2] = { 0x1f, 0xe0};
4624 unsigned char in
[2];
4625 memcpy (in
, orig
, sizeof orig
);
4626 unsigned char expected
[2] = { 0x07, 0xf8};
4627 shift_bytes_in_array_right (in
, sizeof (in
), 2);
4628 verify_array_eq (in
, expected
, sizeof (in
));
4630 memcpy (in
, orig
, sizeof orig
);
4631 memcpy (expected
, orig
, sizeof orig
);
4632 /* Check that shifting by zero doesn't change anything. */
4633 shift_bytes_in_array_right (in
, sizeof (in
), 0);
4634 verify_array_eq (in
, expected
, sizeof (in
));
4637 /* Test clear_bit_region that it clears exactly the bits asked and
4641 verify_clear_bit_region (void)
4643 /* Start with all bits set and test clearing various patterns in them. */
4644 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
4645 unsigned char in
[3];
4646 unsigned char expected
[3];
4647 memcpy (in
, orig
, sizeof in
);
4649 /* Check zeroing out all the bits. */
4650 clear_bit_region (in
, 0, 3 * BITS_PER_UNIT
);
4651 expected
[0] = expected
[1] = expected
[2] = 0;
4652 verify_array_eq (in
, expected
, sizeof in
);
4654 memcpy (in
, orig
, sizeof in
);
4655 /* Leave the first and last bits intact. */
4656 clear_bit_region (in
, 1, 3 * BITS_PER_UNIT
- 2);
4660 verify_array_eq (in
, expected
, sizeof in
);
4663 /* Test verify_clear_bit_region_be that it clears exactly the bits asked and
4667 verify_clear_bit_region_be (void)
4669 /* Start with all bits set and test clearing various patterns in them. */
4670 unsigned char orig
[3] = { 0xff, 0xff, 0xff};
4671 unsigned char in
[3];
4672 unsigned char expected
[3];
4673 memcpy (in
, orig
, sizeof in
);
4675 /* Check zeroing out all the bits. */
4676 clear_bit_region_be (in
, BITS_PER_UNIT
- 1, 3 * BITS_PER_UNIT
);
4677 expected
[0] = expected
[1] = expected
[2] = 0;
4678 verify_array_eq (in
, expected
, sizeof in
);
4680 memcpy (in
, orig
, sizeof in
);
4681 /* Leave the first and last bits intact. */
4682 clear_bit_region_be (in
, BITS_PER_UNIT
- 2, 3 * BITS_PER_UNIT
- 2);
4686 verify_array_eq (in
, expected
, sizeof in
);
4690 /* Run all of the selftests within this file. */
4693 store_merging_c_tests (void)
4695 verify_shift_bytes_in_array ();
4696 verify_shift_bytes_in_array_right ();
4697 verify_clear_bit_region ();
4698 verify_clear_bit_region_be ();
4701 } // namespace selftest
4702 #endif /* CHECKING_P. */