Branch data Line data Source code
1 : : /* GIMPLE store merging and byte swapping passes.
2 : : Copyright (C) 2009-2024 Free Software Foundation, Inc.
3 : : Contributed by ARM Ltd.
4 : :
5 : : This file is part of GCC.
6 : :
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)
10 : : any later version.
11 : :
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.
16 : :
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/>. */
20 : :
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.
24 : :
25 : : For example, if we have a sequence peforming four byte stores to
26 : : consecutive memory locations:
27 : : [p ] := imm1;
28 : : [p + 1B] := imm2;
29 : : [p + 2B] := imm3;
30 : : [p + 3B] := imm4;
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.
33 : :
34 : : Or:
35 : : [p ] := [q ];
36 : : [p + 1B] := [q + 1B];
37 : : [p + 2B] := [q + 2B];
38 : : [p + 3B] := [q + 3B];
39 : : if there is no overlap can be transformed into a single 4-byte
40 : : load followed by single 4-byte store.
41 : :
42 : : Or:
43 : : [p ] := [q ] ^ imm1;
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.
49 : :
50 : : Or:
51 : : [p:1 ] := imm;
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.
55 : :
56 : : The algorithm is applied to each basic block in three phases:
57 : :
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 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.
74 : :
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.
83 : :
84 : : For example, given the stores:
85 : : [p ] := 0;
86 : : [p + 1B] := 1;
87 : : [p + 3B] := 0;
88 : : [p + 4B] := 1;
89 : : [p + 5B] := 0;
90 : : [p + 6B] := 0;
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].
94 : :
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.
103 : :
104 : : Note on endianness and example:
105 : : Consider 2 contiguous 16-bit stores followed by 2 contiguous 8-bit stores:
106 : : [p ] := 0x1234;
107 : : [p + 2B] := 0x5678;
108 : : [p + 4B] := 0xab;
109 : : [p + 5B] := 0xcd;
110 : :
111 : : The memory layout for little-endian (LE) and big-endian (BE) must be:
112 : : p |LE|BE|
113 : : ---------
114 : : 0 |34|12|
115 : : 1 |12|34|
116 : : 2 |78|56|
117 : : 3 |56|78|
118 : : 4 |ab|ab|
119 : : 5 |cd|cd|
120 : :
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
125 : :
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
129 : :
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;
136 : :
137 : : Whereas for big-endian we emit:
138 : : [p] (32-bit) := 0x12345678; // (val & 0xffffffff0000) >> 16;
139 : : [p + 4B] (16-bit) := 0xabcd; // val & 0x00000000ffff; */
140 : :
141 : : #include "config.h"
142 : : #include "system.h"
143 : : #include "coretypes.h"
144 : : #include "backend.h"
145 : : #include "tree.h"
146 : : #include "gimple.h"
147 : : #include "builtins.h"
148 : : #include "fold-const.h"
149 : : #include "tree-pass.h"
150 : : #include "ssa.h"
151 : : #include "gimple-pretty-print.h"
152 : : #include "alias.h"
153 : : #include "fold-const.h"
154 : : #include "print-tree.h"
155 : : #include "tree-hash-traits.h"
156 : : #include "gimple-iterator.h"
157 : : #include "gimplify.h"
158 : : #include "gimple-fold.h"
159 : : #include "stor-layout.h"
160 : : #include "timevar.h"
161 : : #include "cfganal.h"
162 : : #include "cfgcleanup.h"
163 : : #include "tree-cfg.h"
164 : : #include "except.h"
165 : : #include "tree-eh.h"
166 : : #include "target.h"
167 : : #include "gimplify-me.h"
168 : : #include "rtl.h"
169 : : #include "expr.h" /* For get_bit_range. */
170 : : #include "optabs-tree.h"
171 : : #include "dbgcnt.h"
172 : : #include "selftest.h"
173 : :
174 : : /* The maximum size (in bits) of the stores this pass should generate. */
175 : : #define MAX_STORE_BITSIZE (BITS_PER_WORD)
176 : : #define MAX_STORE_BYTES (MAX_STORE_BITSIZE / BITS_PER_UNIT)
177 : :
178 : : /* Limit to bound the number of aliasing checks for loads with the same
179 : : vuse as the corresponding store. */
180 : : #define MAX_STORE_ALIAS_CHECKS 64
181 : :
182 : : namespace {
183 : :
184 : : struct bswap_stat
185 : : {
186 : : /* Number of hand-written 16-bit nop / bswaps found. */
187 : : int found_16bit;
188 : :
189 : : /* Number of hand-written 32-bit nop / bswaps found. */
190 : : int found_32bit;
191 : :
192 : : /* Number of hand-written 64-bit nop / bswaps found. */
193 : : int found_64bit;
194 : : } nop_stats, bswap_stats;
195 : :
196 : : /* A symbolic number structure is used to detect byte permutation and selection
197 : : patterns of a source. To achieve that, its field N contains an artificial
198 : : number consisting of BITS_PER_MARKER sized markers tracking where does each
199 : : byte come from in the source:
200 : :
201 : : 0 - target byte has the value 0
202 : : FF - target byte has an unknown value (eg. due to sign extension)
203 : : 1..size - marker value is the byte index in the source (0 for lsb).
204 : :
205 : : To detect permutations on memory sources (arrays and structures), a symbolic
206 : : number is also associated:
207 : : - a base address BASE_ADDR and an OFFSET giving the address of the source;
208 : : - a range which gives the difference between the highest and lowest accessed
209 : : memory location to make such a symbolic number;
210 : : - the address SRC of the source element of lowest address as a convenience
211 : : to easily get BASE_ADDR + offset + lowest bytepos;
212 : : - number of expressions N_OPS bitwise ored together to represent
213 : : approximate cost of the computation.
214 : :
215 : : Note 1: the range is different from size as size reflects the size of the
216 : : type of the current expression. For instance, for an array char a[],
217 : : (short) a[0] | (short) a[3] would have a size of 2 but a range of 4 while
218 : : (short) a[0] | ((short) a[0] << 1) would still have a size of 2 but this
219 : : time a range of 1.
220 : :
221 : : Note 2: for non-memory sources, range holds the same value as size.
222 : :
223 : : Note 3: SRC points to the SSA_NAME in case of non-memory source. */
224 : :
225 : : struct symbolic_number {
226 : : uint64_t n;
227 : : tree type;
228 : : tree base_addr;
229 : : tree offset;
230 : : poly_int64 bytepos;
231 : : tree src;
232 : : tree alias_set;
233 : : tree vuse;
234 : : unsigned HOST_WIDE_INT range;
235 : : int n_ops;
236 : : };
237 : :
238 : : #define BITS_PER_MARKER 8
239 : : #define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
240 : : #define MARKER_BYTE_UNKNOWN MARKER_MASK
241 : : #define HEAD_MARKER(n, size) \
242 : : ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
243 : :
244 : : /* The number which the find_bswap_or_nop_1 result should match in
245 : : order to have a nop. The number is masked according to the size of
246 : : the symbolic number before using it. */
247 : : #define CMPNOP (sizeof (int64_t) < 8 ? 0 : \
248 : : (uint64_t)0x08070605 << 32 | 0x04030201)
249 : :
250 : : /* The number which the find_bswap_or_nop_1 result should match in
251 : : order to have a byte swap. The number is masked according to the
252 : : size of the symbolic number before using it. */
253 : : #define CMPXCHG (sizeof (int64_t) < 8 ? 0 : \
254 : : (uint64_t)0x01020304 << 32 | 0x05060708)
255 : :
256 : : /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
257 : : number N. Return false if the requested operation is not permitted
258 : : on a symbolic number. */
259 : :
260 : : inline bool
261 : 189549 : do_shift_rotate (enum tree_code code,
262 : : struct symbolic_number *n,
263 : : int count)
264 : : {
265 : 189549 : int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
266 : 189549 : uint64_t head_marker;
267 : :
268 : 189549 : if (count < 0
269 : 189549 : || count >= TYPE_PRECISION (n->type)
270 : 379098 : || count % BITS_PER_UNIT != 0)
271 : : return false;
272 : 147816 : count = (count / BITS_PER_UNIT) * BITS_PER_MARKER;
273 : :
274 : : /* Zero out the extra bits of N in order to avoid them being shifted
275 : : into the significant bits. */
276 : 147816 : if (size < 64 / BITS_PER_MARKER)
277 : 40973 : n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
278 : :
279 : 147816 : switch (code)
280 : : {
281 : 116668 : case LSHIFT_EXPR:
282 : 116668 : n->n <<= count;
283 : 116668 : break;
284 : 28867 : case RSHIFT_EXPR:
285 : 28867 : head_marker = HEAD_MARKER (n->n, size);
286 : 28867 : n->n >>= count;
287 : : /* Arithmetic shift of signed type: result is dependent on the value. */
288 : 28867 : if (!TYPE_UNSIGNED (n->type) && head_marker)
289 : 2276 : for (i = 0; i < count / BITS_PER_MARKER; i++)
290 : 1536 : n->n |= (uint64_t) MARKER_BYTE_UNKNOWN
291 : 1536 : << ((size - 1 - i) * BITS_PER_MARKER);
292 : : break;
293 : 25 : case LROTATE_EXPR:
294 : 25 : n->n = (n->n << count) | (n->n >> ((size * BITS_PER_MARKER) - count));
295 : 25 : break;
296 : 2256 : case RROTATE_EXPR:
297 : 2256 : n->n = (n->n >> count) | (n->n << ((size * BITS_PER_MARKER) - count));
298 : 2256 : break;
299 : : default:
300 : : return false;
301 : : }
302 : : /* Zero unused bits for size. */
303 : 147816 : if (size < 64 / BITS_PER_MARKER)
304 : 40973 : n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
305 : : return true;
306 : : }
307 : :
308 : : /* Perform sanity checking for the symbolic number N and the gimple
309 : : statement STMT. */
310 : :
311 : : inline bool
312 : 333495 : verify_symbolic_number_p (struct symbolic_number *n, gimple *stmt)
313 : : {
314 : 333495 : tree lhs_type;
315 : :
316 : 333495 : lhs_type = TREE_TYPE (gimple_get_lhs (stmt));
317 : :
318 : 333495 : if (TREE_CODE (lhs_type) != INTEGER_TYPE
319 : 333495 : && TREE_CODE (lhs_type) != ENUMERAL_TYPE)
320 : : return false;
321 : :
322 : 323256 : if (TYPE_PRECISION (lhs_type) != TYPE_PRECISION (n->type))
323 : 0 : return false;
324 : :
325 : : return true;
326 : : }
327 : :
328 : : /* Initialize the symbolic number N for the bswap pass from the base element
329 : : SRC manipulated by the bitwise OR expression. */
330 : :
331 : : bool
332 : 1077359 : init_symbolic_number (struct symbolic_number *n, tree src)
333 : : {
334 : 1077359 : int size;
335 : :
336 : 1077359 : if (!INTEGRAL_TYPE_P (TREE_TYPE (src)) && !POINTER_TYPE_P (TREE_TYPE (src)))
337 : : return false;
338 : :
339 : 927784 : n->base_addr = n->offset = n->alias_set = n->vuse = NULL_TREE;
340 : 927784 : n->src = src;
341 : :
342 : : /* Set up the symbolic number N by setting each byte to a value between 1 and
343 : : the byte size of rhs1. The highest order byte is set to n->size and the
344 : : lowest order byte to 1. */
345 : 927784 : n->type = TREE_TYPE (src);
346 : 927784 : size = TYPE_PRECISION (n->type);
347 : 927784 : if (size % BITS_PER_UNIT != 0)
348 : : return false;
349 : 912144 : size /= BITS_PER_UNIT;
350 : 912144 : if (size > 64 / BITS_PER_MARKER)
351 : : return false;
352 : 911233 : n->range = size;
353 : 911233 : n->n = CMPNOP;
354 : 911233 : n->n_ops = 1;
355 : :
356 : 911233 : if (size < 64 / BITS_PER_MARKER)
357 : 438897 : n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
358 : :
359 : : return true;
360 : : }
361 : :
362 : : /* Check if STMT might be a byte swap or a nop from a memory source and returns
363 : : the answer. If so, REF is that memory source and the base of the memory area
364 : : accessed and the offset of the access from that base are recorded in N. */
365 : :
366 : : bool
367 : 4871538 : find_bswap_or_nop_load (gimple *stmt, tree ref, struct symbolic_number *n)
368 : : {
369 : : /* Leaf node is an array or component ref. Memorize its base and
370 : : offset from base to compare to other such leaf node. */
371 : 4871538 : poly_int64 bitsize, bitpos, bytepos;
372 : 4871538 : machine_mode mode;
373 : 4871538 : int unsignedp, reversep, volatilep;
374 : 4871538 : tree offset, base_addr;
375 : :
376 : : /* Not prepared to handle PDP endian. */
377 : 4871538 : if (BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN)
378 : : return false;
379 : :
380 : 5731076 : if (!gimple_assign_load_p (stmt) || gimple_has_volatile_ops (stmt))
381 : : return false;
382 : :
383 : 854393 : base_addr = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
384 : : &unsignedp, &reversep, &volatilep);
385 : :
386 : 854393 : if (TREE_CODE (base_addr) == TARGET_MEM_REF)
387 : : /* Do not rewrite TARGET_MEM_REF. */
388 : : return false;
389 : 818029 : else if (TREE_CODE (base_addr) == MEM_REF)
390 : : {
391 : 428616 : poly_offset_int bit_offset = 0;
392 : 428616 : tree off = TREE_OPERAND (base_addr, 1);
393 : :
394 : 428616 : if (!integer_zerop (off))
395 : : {
396 : 78394 : poly_offset_int boff = mem_ref_offset (base_addr);
397 : 78394 : boff <<= LOG2_BITS_PER_UNIT;
398 : 78394 : bit_offset += boff;
399 : : }
400 : :
401 : 428616 : base_addr = TREE_OPERAND (base_addr, 0);
402 : :
403 : : /* Avoid returning a negative bitpos as this may wreak havoc later. */
404 : 428616 : if (maybe_lt (bit_offset, 0))
405 : : {
406 : 3081 : tree byte_offset = wide_int_to_tree
407 : 3081 : (sizetype, bits_to_bytes_round_down (bit_offset));
408 : 3081 : bit_offset = num_trailing_bits (bit_offset);
409 : 3081 : if (offset)
410 : 0 : offset = size_binop (PLUS_EXPR, offset, byte_offset);
411 : : else
412 : 3081 : offset = byte_offset;
413 : : }
414 : :
415 : 428616 : bitpos += bit_offset.force_shwi ();
416 : : }
417 : : else
418 : 389413 : base_addr = build_fold_addr_expr (base_addr);
419 : :
420 : 5009222 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
421 : : return false;
422 : 817068 : if (!multiple_p (bitsize, BITS_PER_UNIT))
423 : : return false;
424 : 815970 : if (reversep)
425 : : return false;
426 : :
427 : 815961 : if (!init_symbolic_number (n, ref))
428 : : return false;
429 : 679384 : n->base_addr = base_addr;
430 : 679384 : n->offset = offset;
431 : 679384 : n->bytepos = bytepos;
432 : 679384 : n->alias_set = reference_alias_ptr_type (ref);
433 : 679384 : n->vuse = gimple_vuse (stmt);
434 : 679384 : return true;
435 : : }
436 : :
437 : : /* Compute the symbolic number N representing the result of a bitwise OR,
438 : : bitwise XOR or plus on 2 symbolic number N1 and N2 whose source statements
439 : : are respectively SOURCE_STMT1 and SOURCE_STMT2. CODE is the operation. */
440 : :
441 : : gimple *
442 : 158655 : perform_symbolic_merge (gimple *source_stmt1, struct symbolic_number *n1,
443 : : gimple *source_stmt2, struct symbolic_number *n2,
444 : : struct symbolic_number *n, enum tree_code code)
445 : : {
446 : 158655 : int i, size;
447 : 158655 : uint64_t mask;
448 : 158655 : gimple *source_stmt;
449 : 158655 : struct symbolic_number *n_start;
450 : :
451 : 158655 : tree rhs1 = gimple_assign_rhs1 (source_stmt1);
452 : 158655 : if (TREE_CODE (rhs1) == BIT_FIELD_REF
453 : 158655 : && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
454 : 328 : rhs1 = TREE_OPERAND (rhs1, 0);
455 : 158655 : tree rhs2 = gimple_assign_rhs1 (source_stmt2);
456 : 158655 : if (TREE_CODE (rhs2) == BIT_FIELD_REF
457 : 158655 : && TREE_CODE (TREE_OPERAND (rhs2, 0)) == SSA_NAME)
458 : 321 : rhs2 = TREE_OPERAND (rhs2, 0);
459 : :
460 : : /* Sources are different, cancel bswap if they are not memory location with
461 : : the same base (array, structure, ...). */
462 : 158655 : if (rhs1 != rhs2)
463 : : {
464 : 150619 : uint64_t inc;
465 : 150619 : HOST_WIDE_INT start1, start2, start_sub, end_sub, end1, end2, end;
466 : 150619 : struct symbolic_number *toinc_n_ptr, *n_end;
467 : 150619 : basic_block bb1, bb2;
468 : :
469 : 120793 : if (!n1->base_addr || !n2->base_addr
470 : 271405 : || !operand_equal_p (n1->base_addr, n2->base_addr, 0))
471 : 87028 : return NULL;
472 : :
473 : 63591 : if (!n1->offset != !n2->offset
474 : 63591 : || (n1->offset && !operand_equal_p (n1->offset, n2->offset, 0)))
475 : 3208 : return NULL;
476 : :
477 : 60383 : start1 = 0;
478 : 60383 : if (!(n2->bytepos - n1->bytepos).is_constant (&start2))
479 : : return NULL;
480 : :
481 : 60383 : if (start1 < start2)
482 : : {
483 : : n_start = n1;
484 : : start_sub = start2 - start1;
485 : : }
486 : : else
487 : : {
488 : 13711 : n_start = n2;
489 : 13711 : start_sub = start1 - start2;
490 : : }
491 : :
492 : 60383 : bb1 = gimple_bb (source_stmt1);
493 : 60383 : bb2 = gimple_bb (source_stmt2);
494 : 60383 : if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
495 : : source_stmt = source_stmt1;
496 : : else
497 : 5532 : source_stmt = source_stmt2;
498 : :
499 : : /* Find the highest address at which a load is performed and
500 : : compute related info. */
501 : 60383 : end1 = start1 + (n1->range - 1);
502 : 60383 : end2 = start2 + (n2->range - 1);
503 : 60383 : if (end1 < end2)
504 : : {
505 : : end = end2;
506 : : end_sub = end2 - end1;
507 : : }
508 : : else
509 : : {
510 : : end = end1;
511 : : end_sub = end1 - end2;
512 : : }
513 : 60383 : n_end = (end2 > end1) ? n2 : n1;
514 : :
515 : : /* Find symbolic number whose lsb is the most significant. */
516 : 60383 : if (BYTES_BIG_ENDIAN)
517 : : toinc_n_ptr = (n_end == n1) ? n2 : n1;
518 : : else
519 : 60383 : toinc_n_ptr = (n_start == n1) ? n2 : n1;
520 : :
521 : 60383 : n->range = end - MIN (start1, start2) + 1;
522 : :
523 : : /* Check that the range of memory covered can be represented by
524 : : a symbolic number. */
525 : 60383 : if (n->range > 64 / BITS_PER_MARKER)
526 : : return NULL;
527 : :
528 : : /* Reinterpret byte marks in symbolic number holding the value of
529 : : bigger weight according to target endianness. */
530 : 46424 : inc = BYTES_BIG_ENDIAN ? end_sub : start_sub;
531 : 46424 : size = TYPE_PRECISION (n1->type) / BITS_PER_UNIT;
532 : 367374 : for (i = 0; i < size; i++, inc <<= BITS_PER_MARKER)
533 : : {
534 : 320950 : unsigned marker
535 : 320950 : = (toinc_n_ptr->n >> (i * BITS_PER_MARKER)) & MARKER_MASK;
536 : 320950 : if (marker && marker != MARKER_BYTE_UNKNOWN)
537 : 123830 : toinc_n_ptr->n += inc;
538 : : }
539 : : }
540 : : else
541 : : {
542 : 8036 : n->range = n1->range;
543 : 8036 : n_start = n1;
544 : 8036 : source_stmt = source_stmt1;
545 : : }
546 : :
547 : 54460 : if (!n1->alias_set
548 : 54460 : || alias_ptr_types_compatible_p (n1->alias_set, n2->alias_set))
549 : 39474 : n->alias_set = n1->alias_set;
550 : : else
551 : 14986 : n->alias_set = ptr_type_node;
552 : 54460 : n->vuse = n_start->vuse;
553 : 54460 : n->base_addr = n_start->base_addr;
554 : 54460 : n->offset = n_start->offset;
555 : 54460 : n->src = n_start->src;
556 : 54460 : n->bytepos = n_start->bytepos;
557 : 54460 : n->type = n_start->type;
558 : 54460 : size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
559 : 54460 : uint64_t res_n = n1->n | n2->n;
560 : :
561 : 424785 : for (i = 0, mask = MARKER_MASK; i < size; i++, mask <<= BITS_PER_MARKER)
562 : : {
563 : 371529 : uint64_t masked1, masked2;
564 : :
565 : 371529 : masked1 = n1->n & mask;
566 : 371529 : masked2 = n2->n & mask;
567 : : /* If at least one byte is 0, all of 0 | x == 0 ^ x == 0 + x == x. */
568 : 371529 : if (masked1 && masked2)
569 : : {
570 : : /* + can carry into upper bits, just punt. */
571 : 8744 : if (code == PLUS_EXPR)
572 : : return NULL;
573 : : /* x | x is still x. */
574 : 7540 : if (code == BIT_IOR_EXPR && masked1 == masked2)
575 : 209 : continue;
576 : 7331 : if (code == BIT_XOR_EXPR)
577 : : {
578 : : /* x ^ x is 0, but MARKER_BYTE_UNKNOWN stands for
579 : : unknown values and unknown ^ unknown is unknown. */
580 : 1618 : if (masked1 == masked2
581 : 208 : && masked1 != ((uint64_t) MARKER_BYTE_UNKNOWN
582 : 146 : << i * BITS_PER_MARKER))
583 : : {
584 : 62 : res_n &= ~mask;
585 : 62 : continue;
586 : : }
587 : : }
588 : : /* Otherwise set the byte to unknown, it might still be
589 : : later masked off. */
590 : 7269 : res_n |= mask;
591 : : }
592 : : }
593 : 53256 : n->n = res_n;
594 : 53256 : n->n_ops = n1->n_ops + n2->n_ops;
595 : :
596 : 53256 : return source_stmt;
597 : : }
598 : :
599 : : /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
600 : : the operation given by the rhs of STMT on the result. If the operation
601 : : could successfully be executed the function returns a gimple stmt whose
602 : : rhs's first tree is the expression of the source operand and NULL
603 : : otherwise. */
604 : :
605 : : gimple *
606 : 5735087 : find_bswap_or_nop_1 (gimple *stmt, struct symbolic_number *n, int limit)
607 : : {
608 : 5735087 : enum tree_code code;
609 : 5735087 : tree rhs1, rhs2 = NULL;
610 : 5735087 : gimple *rhs1_stmt, *rhs2_stmt, *source_stmt1;
611 : 5735087 : enum gimple_rhs_class rhs_class;
612 : :
613 : 5735087 : if (!limit || !is_gimple_assign (stmt))
614 : : return NULL;
615 : :
616 : 4871538 : rhs1 = gimple_assign_rhs1 (stmt);
617 : :
618 : 4871538 : if (find_bswap_or_nop_load (stmt, rhs1, n))
619 : : return stmt;
620 : :
621 : : /* Handle BIT_FIELD_REF. */
622 : 4192154 : if (TREE_CODE (rhs1) == BIT_FIELD_REF
623 : 4192154 : && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
624 : : {
625 : 11460 : if (!tree_fits_uhwi_p (TREE_OPERAND (rhs1, 1))
626 : 11460 : || !tree_fits_uhwi_p (TREE_OPERAND (rhs1, 2)))
627 : : return NULL;
628 : :
629 : 11460 : unsigned HOST_WIDE_INT bitsize = tree_to_uhwi (TREE_OPERAND (rhs1, 1));
630 : 11460 : unsigned HOST_WIDE_INT bitpos = tree_to_uhwi (TREE_OPERAND (rhs1, 2));
631 : 11460 : if (bitpos % BITS_PER_UNIT == 0
632 : 11460 : && bitsize % BITS_PER_UNIT == 0
633 : 22920 : && init_symbolic_number (n, TREE_OPERAND (rhs1, 0)))
634 : : {
635 : : /* Handle big-endian bit numbering in BIT_FIELD_REF. */
636 : 482 : if (BYTES_BIG_ENDIAN)
637 : : bitpos = TYPE_PRECISION (n->type) - bitpos - bitsize;
638 : :
639 : : /* Shift. */
640 : 482 : if (!do_shift_rotate (RSHIFT_EXPR, n, bitpos))
641 : : return NULL;
642 : :
643 : : /* Mask. */
644 : : uint64_t mask = 0;
645 : : uint64_t tmp = (1 << BITS_PER_UNIT) - 1;
646 : 1239 : for (unsigned i = 0; i < bitsize / BITS_PER_UNIT;
647 : 757 : i++, tmp <<= BITS_PER_UNIT)
648 : 757 : mask |= (uint64_t) MARKER_MASK << (i * BITS_PER_MARKER);
649 : 482 : n->n &= mask;
650 : :
651 : : /* Convert. */
652 : 482 : n->type = TREE_TYPE (rhs1);
653 : 482 : if (!verify_symbolic_number_p (n, stmt))
654 : : return NULL;
655 : :
656 : 469 : if (!n->base_addr)
657 : 469 : n->range = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
658 : :
659 : 469 : return stmt;
660 : : }
661 : :
662 : 10978 : return NULL;
663 : : }
664 : :
665 : 4180694 : if (TREE_CODE (rhs1) != SSA_NAME)
666 : : return NULL;
667 : :
668 : 3847795 : code = gimple_assign_rhs_code (stmt);
669 : 3847795 : rhs_class = gimple_assign_rhs_class (stmt);
670 : 3847795 : rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
671 : :
672 : 3847795 : if (rhs_class == GIMPLE_BINARY_RHS)
673 : 3546519 : rhs2 = gimple_assign_rhs2 (stmt);
674 : :
675 : : /* Handle unary rhs and binary rhs with integer constants as second
676 : : operand. */
677 : :
678 : 3847795 : if (rhs_class == GIMPLE_UNARY_RHS
679 : 3548876 : || (rhs_class == GIMPLE_BINARY_RHS
680 : 3546519 : && TREE_CODE (rhs2) == INTEGER_CST))
681 : : {
682 : 1720597 : if (code != BIT_AND_EXPR
683 : 1720597 : && code != LSHIFT_EXPR
684 : : && code != RSHIFT_EXPR
685 : 1653424 : && code != LROTATE_EXPR
686 : 1594307 : && code != RROTATE_EXPR
687 : 1589563 : && !CONVERT_EXPR_CODE_P (code))
688 : : return NULL;
689 : :
690 : 395688 : source_stmt1 = find_bswap_or_nop_1 (rhs1_stmt, n, limit - 1);
691 : :
692 : : /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
693 : : we have to initialize the symbolic number. */
694 : 395688 : if (!source_stmt1)
695 : : {
696 : 249938 : if (gimple_assign_load_p (stmt)
697 : 249938 : || !init_symbolic_number (n, rhs1))
698 : 18571 : return NULL;
699 : : source_stmt1 = stmt;
700 : : }
701 : :
702 : 377117 : switch (code)
703 : : {
704 : 30977 : case BIT_AND_EXPR:
705 : 30977 : {
706 : 30977 : int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
707 : 30977 : uint64_t val = int_cst_value (rhs2), mask = 0;
708 : 30977 : uint64_t tmp = (1 << BITS_PER_UNIT) - 1;
709 : :
710 : : /* Only constants masking full bytes are allowed. */
711 : 154081 : for (i = 0; i < size; i++, tmp <<= BITS_PER_UNIT)
712 : 141332 : if ((val & tmp) != 0 && (val & tmp) != tmp)
713 : : return NULL;
714 : 123104 : else if (val & tmp)
715 : 63614 : mask |= (uint64_t) MARKER_MASK << (i * BITS_PER_MARKER);
716 : :
717 : 12749 : n->n &= mask;
718 : : }
719 : 12749 : break;
720 : 99754 : case LSHIFT_EXPR:
721 : 99754 : case RSHIFT_EXPR:
722 : 99754 : case LROTATE_EXPR:
723 : 99754 : case RROTATE_EXPR:
724 : 99754 : if (!do_shift_rotate (code, n, (int) TREE_INT_CST_LOW (rhs2)))
725 : : return NULL;
726 : : break;
727 : 246386 : CASE_CONVERT:
728 : 246386 : {
729 : 246386 : int i, type_size, old_type_size;
730 : 246386 : tree type;
731 : :
732 : 246386 : type = TREE_TYPE (gimple_assign_lhs (stmt));
733 : 246386 : type_size = TYPE_PRECISION (type);
734 : 246386 : if (type_size % BITS_PER_UNIT != 0)
735 : : return NULL;
736 : 243908 : type_size /= BITS_PER_UNIT;
737 : 243908 : if (type_size > 64 / BITS_PER_MARKER)
738 : : return NULL;
739 : :
740 : : /* Sign extension: result is dependent on the value. */
741 : 243388 : old_type_size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
742 : 331446 : if (!TYPE_UNSIGNED (n->type) && type_size > old_type_size
743 : 278283 : && HEAD_MARKER (n->n, old_type_size))
744 : 168124 : for (i = 0; i < type_size - old_type_size; i++)
745 : 133244 : n->n |= (uint64_t) MARKER_BYTE_UNKNOWN
746 : 133244 : << ((type_size - 1 - i) * BITS_PER_MARKER);
747 : :
748 : 243388 : if (type_size < 64 / BITS_PER_MARKER)
749 : : {
750 : : /* If STMT casts to a smaller type mask out the bits not
751 : : belonging to the target type. */
752 : 136175 : n->n &= ((uint64_t) 1 << (type_size * BITS_PER_MARKER)) - 1;
753 : : }
754 : 243388 : n->type = type;
755 : 243388 : if (!n->base_addr)
756 : 150696 : n->range = type_size;
757 : : }
758 : : break;
759 : : default:
760 : : return NULL;
761 : 314158 : };
762 : 314158 : return verify_symbolic_number_p (n, stmt) ? source_stmt1 : NULL;
763 : : }
764 : :
765 : : /* Handle binary rhs. */
766 : :
767 : 2124841 : if (rhs_class == GIMPLE_BINARY_RHS)
768 : : {
769 : 2124841 : struct symbolic_number n1, n2;
770 : 2124841 : gimple *source_stmt, *source_stmt2;
771 : :
772 : 2124841 : if (!rhs2 || TREE_CODE (rhs2) != SSA_NAME)
773 : : return NULL;
774 : :
775 : 2067742 : rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
776 : :
777 : 2067742 : switch (code)
778 : : {
779 : 1864296 : case BIT_IOR_EXPR:
780 : 1864296 : case BIT_XOR_EXPR:
781 : 1864296 : case PLUS_EXPR:
782 : 1864296 : source_stmt1 = find_bswap_or_nop_1 (rhs1_stmt, &n1, limit - 1);
783 : :
784 : 1864296 : if (!source_stmt1)
785 : : return NULL;
786 : :
787 : 244072 : source_stmt2 = find_bswap_or_nop_1 (rhs2_stmt, &n2, limit - 1);
788 : :
789 : 244072 : if (!source_stmt2)
790 : : return NULL;
791 : :
792 : 131932 : if (TYPE_PRECISION (n1.type) != TYPE_PRECISION (n2.type))
793 : : return NULL;
794 : :
795 : 131932 : if (n1.vuse != n2.vuse)
796 : : return NULL;
797 : :
798 : 108306 : source_stmt
799 : 108306 : = perform_symbolic_merge (source_stmt1, &n1, source_stmt2, &n2, n,
800 : : code);
801 : :
802 : 108306 : if (!source_stmt)
803 : : return NULL;
804 : :
805 : 18855 : if (!verify_symbolic_number_p (n, stmt))
806 : : return NULL;
807 : :
808 : : break;
809 : : default:
810 : : return NULL;
811 : : }
812 : : return source_stmt;
813 : : }
814 : : return NULL;
815 : : }
816 : :
817 : : /* Helper for find_bswap_or_nop and try_coalesce_bswap to compute
818 : : *CMPXCHG, *CMPNOP and adjust *N. */
819 : :
820 : : void
821 : 34890 : find_bswap_or_nop_finalize (struct symbolic_number *n, uint64_t *cmpxchg,
822 : : uint64_t *cmpnop, bool *cast64_to_32)
823 : : {
824 : 34890 : unsigned rsize;
825 : 34890 : uint64_t tmpn, mask;
826 : :
827 : : /* The number which the find_bswap_or_nop_1 result should match in order
828 : : to have a full byte swap. The number is shifted to the right
829 : : according to the size of the symbolic number before using it. */
830 : 34890 : *cmpxchg = CMPXCHG;
831 : 34890 : *cmpnop = CMPNOP;
832 : 34890 : *cast64_to_32 = false;
833 : :
834 : : /* Find real size of result (highest non-zero byte). */
835 : 34890 : if (n->base_addr)
836 : 249616 : for (tmpn = n->n, rsize = 0; tmpn; tmpn >>= BITS_PER_MARKER, rsize++);
837 : : else
838 : 1939 : rsize = n->range;
839 : :
840 : : /* Zero out the bits corresponding to untouched bytes in original gimple
841 : : expression. */
842 : 34890 : if (n->range < (int) sizeof (int64_t))
843 : : {
844 : 11046 : mask = ((uint64_t) 1 << (n->range * BITS_PER_MARKER)) - 1;
845 : 11046 : if (n->base_addr == NULL
846 : 988 : && n->range == 4
847 : 11752 : && int_size_in_bytes (TREE_TYPE (n->src)) == 8)
848 : : {
849 : : /* If all bytes in n->n are either 0 or in [5..8] range, this
850 : : might be a candidate for (unsigned) __builtin_bswap64 (src).
851 : : It is not worth it for (unsigned short) __builtin_bswap64 (src)
852 : : or (unsigned short) __builtin_bswap32 (src). */
853 : 135 : *cast64_to_32 = true;
854 : 309 : for (tmpn = n->n; tmpn; tmpn >>= BITS_PER_MARKER)
855 : 268 : if ((tmpn & MARKER_MASK)
856 : 268 : && ((tmpn & MARKER_MASK) <= 4 || (tmpn & MARKER_MASK) > 8))
857 : : {
858 : 94 : *cast64_to_32 = false;
859 : 94 : break;
860 : : }
861 : : }
862 : 11046 : if (*cast64_to_32)
863 : 41 : *cmpxchg &= mask;
864 : : else
865 : 11005 : *cmpxchg >>= (64 / BITS_PER_MARKER - n->range) * BITS_PER_MARKER;
866 : 11046 : *cmpnop &= mask;
867 : : }
868 : :
869 : : /* Zero out the bits corresponding to unused bytes in the result of the
870 : : gimple expression. */
871 : 34890 : if (rsize < n->range)
872 : : {
873 : 2427 : if (BYTES_BIG_ENDIAN)
874 : : {
875 : : mask = ((uint64_t) 1 << (rsize * BITS_PER_MARKER)) - 1;
876 : : *cmpxchg &= mask;
877 : : if (n->range - rsize == sizeof (int64_t))
878 : : *cmpnop = 0;
879 : : else
880 : : *cmpnop >>= (n->range - rsize) * BITS_PER_MARKER;
881 : : }
882 : : else
883 : : {
884 : 2427 : mask = ((uint64_t) 1 << (rsize * BITS_PER_MARKER)) - 1;
885 : 2427 : if (n->range - rsize == sizeof (int64_t))
886 : 6 : *cmpxchg = 0;
887 : : else
888 : 2421 : *cmpxchg >>= (n->range - rsize) * BITS_PER_MARKER;
889 : 2427 : *cmpnop &= mask;
890 : : }
891 : 2427 : n->range = rsize;
892 : : }
893 : :
894 : 34890 : if (*cast64_to_32)
895 : 41 : n->range = 8;
896 : 34890 : n->range *= BITS_PER_UNIT;
897 : 34890 : }
898 : :
899 : : /* Helper function for find_bswap_or_nop,
900 : : Return true if N is a swap or nop with MASK. */
901 : : static bool
902 : 16970 : is_bswap_or_nop_p (uint64_t n, uint64_t cmpxchg,
903 : : uint64_t cmpnop, uint64_t* mask,
904 : : bool* bswap)
905 : : {
906 : 16970 : *mask = ~(uint64_t) 0;
907 : 16970 : if (n == cmpnop)
908 : 7744 : *bswap = false;
909 : 9226 : else if (n == cmpxchg)
910 : 1858 : *bswap = true;
911 : : else
912 : : {
913 : : int set = 0;
914 : 15987 : for (uint64_t msk = MARKER_MASK; msk; msk <<= BITS_PER_MARKER)
915 : 15548 : if ((n & msk) == 0)
916 : 5515 : *mask &= ~msk;
917 : 10033 : else if ((n & msk) == (cmpxchg & msk))
918 : 3104 : set++;
919 : : else
920 : : return false;
921 : :
922 : 439 : if (set < 2)
923 : : return false;
924 : 437 : *bswap = true;
925 : : }
926 : : return true;
927 : : }
928 : :
929 : :
930 : : /* Check if STMT completes a bswap implementation or a read in a given
931 : : endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
932 : : accordingly. It also sets N to represent the kind of operations
933 : : performed: size of the resulting expression and whether it works on
934 : : a memory source, and if so alias-set and vuse. At last, the
935 : : function returns a stmt whose rhs's first tree is the source
936 : : expression. */
937 : :
938 : : gimple *
939 : 1883422 : find_bswap_or_nop (gimple *stmt, struct symbolic_number *n, bool *bswap,
940 : : bool *cast64_to_32, uint64_t *mask, uint64_t* l_rotate)
941 : : {
942 : 1883422 : tree type_size = TYPE_SIZE_UNIT (TREE_TYPE (gimple_get_lhs (stmt)));
943 : 1883422 : if (!tree_fits_uhwi_p (type_size))
944 : : return NULL;
945 : :
946 : : /* The last parameter determines the depth search limit. It usually
947 : : correlates directly to the number n of bytes to be touched. We
948 : : increase that number by 2 * (log2(n) + 1) here in order to also
949 : : cover signed -> unsigned conversions of the src operand as can be seen
950 : : in libgcc, and for initial shift/and operation of the src operand. */
951 : 1883422 : int limit = tree_to_uhwi (type_size);
952 : 1883422 : limit += 2 * (1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT) limit));
953 : 1883422 : gimple *ins_stmt = find_bswap_or_nop_1 (stmt, n, limit);
954 : :
955 : 1883422 : if (!ins_stmt)
956 : : {
957 : 1875429 : if (gimple_assign_rhs_code (stmt) != CONSTRUCTOR
958 : : || BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN)
959 : 1883422 : return NULL;
960 : 47074 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (type_size) * BITS_PER_UNIT;
961 : 47074 : if (sz != 16 && sz != 32 && sz != 64)
962 : : return NULL;
963 : 43908 : tree rhs = gimple_assign_rhs1 (stmt);
964 : 1916832 : if (CONSTRUCTOR_NELTS (rhs) == 0)
965 : : return NULL;
966 : 43449 : tree eltype = TREE_TYPE (TREE_TYPE (rhs));
967 : 43449 : unsigned HOST_WIDE_INT eltsz
968 : 43449 : = int_size_in_bytes (eltype) * BITS_PER_UNIT;
969 : 43449 : if (TYPE_PRECISION (eltype) != eltsz)
970 : : return NULL;
971 : 43291 : constructor_elt *elt;
972 : 43291 : unsigned int i;
973 : 43291 : tree type = build_nonstandard_integer_type (sz, 1);
974 : 75906 : FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (rhs), i, elt)
975 : : {
976 : 68469 : if (TREE_CODE (elt->value) != SSA_NAME
977 : 68469 : || !INTEGRAL_TYPE_P (TREE_TYPE (elt->value)))
978 : 35854 : return NULL;
979 : 68041 : struct symbolic_number n1;
980 : 68041 : gimple *source_stmt
981 : 68041 : = find_bswap_or_nop_1 (SSA_NAME_DEF_STMT (elt->value), &n1,
982 : : limit - 1);
983 : :
984 : 68041 : if (!source_stmt)
985 : : return NULL;
986 : :
987 : 46839 : n1.type = type;
988 : 46839 : if (!n1.base_addr)
989 : 10017 : n1.range = sz / BITS_PER_UNIT;
990 : :
991 : 46839 : if (i == 0)
992 : : {
993 : 23065 : ins_stmt = source_stmt;
994 : 23065 : *n = n1;
995 : : }
996 : : else
997 : : {
998 : 23774 : if (n->vuse != n1.vuse)
999 : 14224 : return NULL;
1000 : :
1001 : 13422 : struct symbolic_number n0 = *n;
1002 : :
1003 : 13422 : if (!BYTES_BIG_ENDIAN)
1004 : : {
1005 : 13422 : if (!do_shift_rotate (LSHIFT_EXPR, &n1, i * eltsz))
1006 : : return NULL;
1007 : : }
1008 : : else if (!do_shift_rotate (LSHIFT_EXPR, &n0, eltsz))
1009 : : return NULL;
1010 : 13422 : ins_stmt
1011 : 13422 : = perform_symbolic_merge (ins_stmt, &n0, source_stmt, &n1, n,
1012 : : BIT_IOR_EXPR);
1013 : :
1014 : 13422 : if (!ins_stmt)
1015 : : return NULL;
1016 : : }
1017 : : }
1018 : : }
1019 : :
1020 : 15430 : uint64_t cmpxchg, cmpnop;
1021 : 15430 : uint64_t orig_range = n->range * BITS_PER_UNIT;
1022 : 15430 : find_bswap_or_nop_finalize (n, &cmpxchg, &cmpnop, cast64_to_32);
1023 : :
1024 : : /* A complete byte swap should make the symbolic number to start with
1025 : : the largest digit in the highest order byte. Unchanged symbolic
1026 : : number indicates a read with same endianness as target architecture. */
1027 : 15430 : *l_rotate = 0;
1028 : 15430 : uint64_t tmp_n = n->n;
1029 : 15430 : if (!is_bswap_or_nop_p (tmp_n, cmpxchg, cmpnop, mask, bswap))
1030 : : {
1031 : : /* Try bswap + lrotate. */
1032 : : /* TODO, handle cast64_to_32 and big/litte_endian memory
1033 : : source when rsize < range. */
1034 : 5487 : if (n->range == orig_range
1035 : : /* There're case like 0x300000200 for uint32->uint64 cast,
1036 : : Don't hanlde this. */
1037 : 4494 : && n->range == TYPE_PRECISION (n->type)
1038 : 1866 : && ((orig_range == 32
1039 : 511 : && optab_handler (rotl_optab, SImode) != CODE_FOR_nothing)
1040 : 1355 : || (orig_range == 64
1041 : 1325 : && optab_handler (rotl_optab, DImode) != CODE_FOR_nothing))
1042 : 7323 : && (tmp_n & MARKER_MASK) < orig_range / BITS_PER_UNIT)
1043 : : {
1044 : 1540 : uint64_t range = (orig_range / BITS_PER_UNIT) * BITS_PER_MARKER;
1045 : 1540 : uint64_t count = (tmp_n & MARKER_MASK) * BITS_PER_MARKER;
1046 : : /* .i.e. hanlde 0x203040506070800 when lower byte is zero. */
1047 : 1540 : if (!count)
1048 : : {
1049 : 66 : for (uint64_t i = 1; i != range / BITS_PER_MARKER; i++)
1050 : : {
1051 : 66 : count = (tmp_n >> i * BITS_PER_MARKER) & MARKER_MASK;
1052 : 66 : if (count)
1053 : : {
1054 : : /* Count should be meaningful not 0xff. */
1055 : 36 : if (count <= range / BITS_PER_MARKER)
1056 : : {
1057 : 36 : count = (count + i) * BITS_PER_MARKER % range;
1058 : 36 : break;
1059 : : }
1060 : : else
1061 : : return NULL;
1062 : : }
1063 : : }
1064 : : }
1065 : 1540 : tmp_n = tmp_n >> count | tmp_n << (range - count);
1066 : 1540 : if (orig_range == 32)
1067 : 324 : tmp_n &= (1ULL << 32) - 1;
1068 : 1540 : if (!is_bswap_or_nop_p (tmp_n, cmpxchg, cmpnop, mask, bswap))
1069 : : return NULL;
1070 : 96 : *l_rotate = count / BITS_PER_MARKER * BITS_PER_UNIT;
1071 : 96 : gcc_assert (*bswap);
1072 : : }
1073 : : else
1074 : 3947 : return NULL;
1075 : : }
1076 : :
1077 : : /* Useless bit manipulation performed by code. */
1078 : 10039 : if (!n->base_addr && n->n == cmpnop && n->n_ops == 1)
1079 : : return NULL;
1080 : :
1081 : : return ins_stmt;
1082 : : }
1083 : :
1084 : : const pass_data pass_data_optimize_bswap =
1085 : : {
1086 : : GIMPLE_PASS, /* type */
1087 : : "bswap", /* name */
1088 : : OPTGROUP_NONE, /* optinfo_flags */
1089 : : TV_NONE, /* tv_id */
1090 : : PROP_ssa, /* properties_required */
1091 : : 0, /* properties_provided */
1092 : : 0, /* properties_destroyed */
1093 : : 0, /* todo_flags_start */
1094 : : 0, /* todo_flags_finish */
1095 : : };
1096 : :
1097 : : class pass_optimize_bswap : public gimple_opt_pass
1098 : : {
1099 : : public:
1100 : 280455 : pass_optimize_bswap (gcc::context *ctxt)
1101 : 560910 : : gimple_opt_pass (pass_data_optimize_bswap, ctxt)
1102 : : {}
1103 : :
1104 : : /* opt_pass methods: */
1105 : 972089 : bool gate (function *) final override
1106 : : {
1107 : 972089 : return flag_expensive_optimizations && optimize && BITS_PER_UNIT == 8;
1108 : : }
1109 : :
1110 : : unsigned int execute (function *) final override;
1111 : :
1112 : : }; // class pass_optimize_bswap
1113 : :
1114 : : /* Helper function for bswap_replace. Build VIEW_CONVERT_EXPR from
1115 : : VAL to TYPE. If VAL has different type size, emit a NOP_EXPR cast
1116 : : first. */
1117 : :
1118 : : static tree
1119 : 5265 : bswap_view_convert (gimple_stmt_iterator *gsi, tree type, tree val,
1120 : : bool before)
1121 : : {
1122 : 5265 : gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (val))
1123 : : || POINTER_TYPE_P (TREE_TYPE (val)));
1124 : 5265 : if (TYPE_SIZE (type) != TYPE_SIZE (TREE_TYPE (val)))
1125 : : {
1126 : 26 : HOST_WIDE_INT prec = TREE_INT_CST_LOW (TYPE_SIZE (type));
1127 : 26 : if (POINTER_TYPE_P (TREE_TYPE (val)))
1128 : : {
1129 : 1 : gimple *g
1130 : 1 : = gimple_build_assign (make_ssa_name (pointer_sized_int_node),
1131 : : NOP_EXPR, val);
1132 : 1 : if (before)
1133 : 1 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1134 : : else
1135 : 0 : gsi_insert_after (gsi, g, GSI_NEW_STMT);
1136 : 1 : val = gimple_assign_lhs (g);
1137 : : }
1138 : 26 : tree itype = build_nonstandard_integer_type (prec, 1);
1139 : 26 : gimple *g = gimple_build_assign (make_ssa_name (itype), NOP_EXPR, val);
1140 : 26 : if (before)
1141 : 25 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1142 : : else
1143 : 1 : gsi_insert_after (gsi, g, GSI_NEW_STMT);
1144 : 26 : val = gimple_assign_lhs (g);
1145 : : }
1146 : 5265 : return build1 (VIEW_CONVERT_EXPR, type, val);
1147 : : }
1148 : :
1149 : : /* Perform the bswap optimization: replace the expression computed in the rhs
1150 : : of gsi_stmt (GSI) (or if NULL add instead of replace) by an equivalent
1151 : : bswap, load or load + bswap expression.
1152 : : Which of these alternatives replace the rhs is given by N->base_addr (non
1153 : : null if a load is needed) and BSWAP. The type, VUSE and set-alias of the
1154 : : load to perform are also given in N while the builtin bswap invoke is given
1155 : : in FNDEL. Finally, if a load is involved, INS_STMT refers to one of the
1156 : : load statements involved to construct the rhs in gsi_stmt (GSI) and
1157 : : N->range gives the size of the rhs expression for maintaining some
1158 : : statistics.
1159 : :
1160 : : Note that if the replacement involve a load and if gsi_stmt (GSI) is
1161 : : non-NULL, that stmt is moved just after INS_STMT to do the load with the
1162 : : same VUSE which can lead to gsi_stmt (GSI) changing of basic block. */
1163 : :
1164 : : tree
1165 : 8223 : bswap_replace (gimple_stmt_iterator gsi, gimple *ins_stmt, tree fndecl,
1166 : : tree bswap_type, tree load_type, struct symbolic_number *n,
1167 : : bool bswap, uint64_t mask, uint64_t l_rotate)
1168 : : {
1169 : 8223 : tree src, tmp, tgt = NULL_TREE;
1170 : 8223 : gimple *bswap_stmt, *mask_stmt = NULL, *rotl_stmt = NULL;
1171 : 8223 : tree_code conv_code = NOP_EXPR;
1172 : :
1173 : 8223 : gimple *cur_stmt = gsi_stmt (gsi);
1174 : 8223 : src = n->src;
1175 : 8223 : if (cur_stmt)
1176 : : {
1177 : 7702 : tgt = gimple_assign_lhs (cur_stmt);
1178 : 7702 : if (gimple_assign_rhs_code (cur_stmt) == CONSTRUCTOR
1179 : 5265 : && tgt
1180 : 12967 : && VECTOR_TYPE_P (TREE_TYPE (tgt)))
1181 : : conv_code = VIEW_CONVERT_EXPR;
1182 : : }
1183 : :
1184 : : /* Need to load the value from memory first. */
1185 : 8223 : if (n->base_addr)
1186 : : {
1187 : 7531 : gimple_stmt_iterator gsi_ins = gsi;
1188 : 7531 : if (ins_stmt)
1189 : 7507 : gsi_ins = gsi_for_stmt (ins_stmt);
1190 : 7531 : tree addr_expr, addr_tmp, val_expr, val_tmp;
1191 : 7531 : tree load_offset_ptr, aligned_load_type;
1192 : 7531 : gimple *load_stmt;
1193 : 7531 : unsigned align = get_object_alignment (src);
1194 : 7531 : poly_int64 load_offset = 0;
1195 : :
1196 : 7531 : if (cur_stmt)
1197 : : {
1198 : 7231 : basic_block ins_bb = gimple_bb (ins_stmt);
1199 : 7231 : basic_block cur_bb = gimple_bb (cur_stmt);
1200 : 7231 : if (!dominated_by_p (CDI_DOMINATORS, cur_bb, ins_bb))
1201 : 6162 : return NULL_TREE;
1202 : :
1203 : : /* Move cur_stmt just before one of the load of the original
1204 : : to ensure it has the same VUSE. See PR61517 for what could
1205 : : go wrong. */
1206 : 7231 : if (gimple_bb (cur_stmt) != gimple_bb (ins_stmt))
1207 : 1832 : reset_flow_sensitive_info (gimple_assign_lhs (cur_stmt));
1208 : 7231 : gsi_move_before (&gsi, &gsi_ins);
1209 : 7231 : gsi = gsi_for_stmt (cur_stmt);
1210 : : }
1211 : : else
1212 : 300 : gsi = gsi_ins;
1213 : :
1214 : : /* Compute address to load from and cast according to the size
1215 : : of the load. */
1216 : 7531 : addr_expr = build_fold_addr_expr (src);
1217 : 7531 : if (is_gimple_mem_ref_addr (addr_expr))
1218 : 416 : addr_tmp = unshare_expr (addr_expr);
1219 : : else
1220 : : {
1221 : 7115 : addr_tmp = unshare_expr (n->base_addr);
1222 : 7115 : if (!is_gimple_mem_ref_addr (addr_tmp))
1223 : 0 : addr_tmp = force_gimple_operand_gsi_1 (&gsi, addr_tmp,
1224 : : is_gimple_mem_ref_addr,
1225 : : NULL_TREE, true,
1226 : : GSI_SAME_STMT);
1227 : 7115 : load_offset = n->bytepos;
1228 : 7115 : if (n->offset)
1229 : : {
1230 : 0 : tree off
1231 : 0 : = force_gimple_operand_gsi (&gsi, unshare_expr (n->offset),
1232 : : true, NULL_TREE, true,
1233 : : GSI_SAME_STMT);
1234 : 0 : gimple *stmt
1235 : 0 : = gimple_build_assign (make_ssa_name (TREE_TYPE (addr_tmp)),
1236 : : POINTER_PLUS_EXPR, addr_tmp, off);
1237 : 0 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1238 : 0 : addr_tmp = gimple_assign_lhs (stmt);
1239 : : }
1240 : : }
1241 : :
1242 : : /* Perform the load. */
1243 : 7531 : aligned_load_type = load_type;
1244 : 7531 : if (align < TYPE_ALIGN (load_type))
1245 : 6724 : aligned_load_type = build_aligned_type (load_type, align);
1246 : 7531 : load_offset_ptr = build_int_cst (n->alias_set, load_offset);
1247 : 7531 : val_expr = fold_build2 (MEM_REF, aligned_load_type, addr_tmp,
1248 : : load_offset_ptr);
1249 : :
1250 : 7531 : if (!bswap)
1251 : : {
1252 : 6162 : if (n->range == 16)
1253 : 387 : nop_stats.found_16bit++;
1254 : 5775 : else if (n->range == 32)
1255 : 716 : nop_stats.found_32bit++;
1256 : : else
1257 : : {
1258 : 5059 : gcc_assert (n->range == 64);
1259 : 5059 : nop_stats.found_64bit++;
1260 : : }
1261 : :
1262 : : /* Convert the result of load if necessary. */
1263 : 6162 : if (tgt && !useless_type_conversion_p (TREE_TYPE (tgt), load_type))
1264 : : {
1265 : 5616 : val_tmp = make_temp_ssa_name (aligned_load_type, NULL,
1266 : : "load_dst");
1267 : 5616 : load_stmt = gimple_build_assign (val_tmp, val_expr);
1268 : 5616 : gimple_set_vuse (load_stmt, n->vuse);
1269 : 5616 : gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1270 : 5616 : if (conv_code == VIEW_CONVERT_EXPR)
1271 : 4885 : val_tmp = bswap_view_convert (&gsi, TREE_TYPE (tgt), val_tmp,
1272 : : true);
1273 : 5616 : gimple_assign_set_rhs_with_ops (&gsi, conv_code, val_tmp);
1274 : 5616 : update_stmt (cur_stmt);
1275 : : }
1276 : 546 : else if (cur_stmt)
1277 : : {
1278 : 445 : gimple_assign_set_rhs_with_ops (&gsi, MEM_REF, val_expr);
1279 : 445 : gimple_set_vuse (cur_stmt, n->vuse);
1280 : 445 : update_stmt (cur_stmt);
1281 : : }
1282 : : else
1283 : : {
1284 : 101 : tgt = make_ssa_name (load_type);
1285 : 101 : cur_stmt = gimple_build_assign (tgt, MEM_REF, val_expr);
1286 : 101 : gimple_set_vuse (cur_stmt, n->vuse);
1287 : 101 : gsi_insert_before (&gsi, cur_stmt, GSI_SAME_STMT);
1288 : : }
1289 : :
1290 : 6162 : if (dump_file)
1291 : : {
1292 : 26 : fprintf (dump_file,
1293 : : "%d bit load in target endianness found at: ",
1294 : 26 : (int) n->range);
1295 : 26 : print_gimple_stmt (dump_file, cur_stmt, 0);
1296 : : }
1297 : 6162 : return tgt;
1298 : : }
1299 : : else
1300 : : {
1301 : 1369 : val_tmp = make_temp_ssa_name (aligned_load_type, NULL, "load_dst");
1302 : 1369 : load_stmt = gimple_build_assign (val_tmp, val_expr);
1303 : 1369 : gimple_set_vuse (load_stmt, n->vuse);
1304 : 1369 : gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1305 : : }
1306 : 1369 : src = val_tmp;
1307 : : }
1308 : 692 : else if (!bswap)
1309 : : {
1310 : 250 : gimple *g = NULL;
1311 : 250 : if (tgt && !useless_type_conversion_p (TREE_TYPE (tgt), TREE_TYPE (src)))
1312 : : {
1313 : 118 : if (!is_gimple_val (src))
1314 : : return NULL_TREE;
1315 : 118 : if (conv_code == VIEW_CONVERT_EXPR)
1316 : 118 : src = bswap_view_convert (&gsi, TREE_TYPE (tgt), src, true);
1317 : 118 : g = gimple_build_assign (tgt, conv_code, src);
1318 : : }
1319 : 132 : else if (cur_stmt)
1320 : 7 : g = gimple_build_assign (tgt, src);
1321 : : else
1322 : : tgt = src;
1323 : 250 : if (n->range == 16)
1324 : 67 : nop_stats.found_16bit++;
1325 : 183 : else if (n->range == 32)
1326 : 104 : nop_stats.found_32bit++;
1327 : : else
1328 : : {
1329 : 79 : gcc_assert (n->range == 64);
1330 : 79 : nop_stats.found_64bit++;
1331 : : }
1332 : 250 : if (dump_file)
1333 : : {
1334 : 1 : fprintf (dump_file,
1335 : : "%d bit reshuffle in target endianness found at: ",
1336 : : (int) n->range);
1337 : 1 : if (cur_stmt)
1338 : 0 : print_gimple_stmt (dump_file, cur_stmt, 0);
1339 : : else
1340 : : {
1341 : 1 : print_generic_expr (dump_file, tgt, TDF_NONE);
1342 : 1 : fprintf (dump_file, "\n");
1343 : : }
1344 : : }
1345 : 250 : if (cur_stmt)
1346 : 125 : gsi_replace (&gsi, g, true);
1347 : 250 : return tgt;
1348 : : }
1349 : 442 : else if (TREE_CODE (src) == BIT_FIELD_REF)
1350 : 0 : src = TREE_OPERAND (src, 0);
1351 : :
1352 : 1811 : if (n->range == 16)
1353 : 662 : bswap_stats.found_16bit++;
1354 : 1149 : else if (n->range == 32)
1355 : 757 : bswap_stats.found_32bit++;
1356 : : else
1357 : : {
1358 : 392 : gcc_assert (n->range == 64);
1359 : 392 : bswap_stats.found_64bit++;
1360 : : }
1361 : :
1362 : 1811 : tmp = src;
1363 : :
1364 : : /* Convert the src expression if necessary. */
1365 : 1811 : if (!useless_type_conversion_p (TREE_TYPE (tmp), bswap_type))
1366 : : {
1367 : 151 : gimple *convert_stmt;
1368 : :
1369 : 151 : tmp = make_temp_ssa_name (bswap_type, NULL, "bswapsrc");
1370 : 151 : convert_stmt = gimple_build_assign (tmp, NOP_EXPR, src);
1371 : 151 : gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
1372 : : }
1373 : :
1374 : : /* Canonical form for 16 bit bswap is a rotate expression. Only 16bit values
1375 : : are considered as rotation of 2N bit values by N bits is generally not
1376 : : equivalent to a bswap. Consider for instance 0x01020304 r>> 16 which
1377 : : gives 0x03040102 while a bswap for that value is 0x04030201. */
1378 : 1811 : if (bswap && n->range == 16)
1379 : : {
1380 : 662 : tree count = build_int_cst (NULL, BITS_PER_UNIT);
1381 : 662 : src = fold_build2 (LROTATE_EXPR, bswap_type, tmp, count);
1382 : 662 : bswap_stmt = gimple_build_assign (NULL, src);
1383 : 662 : }
1384 : : else
1385 : 1149 : bswap_stmt = gimple_build_call (fndecl, 1, tmp);
1386 : :
1387 : 1811 : if (tgt == NULL_TREE)
1388 : 295 : tgt = make_ssa_name (bswap_type);
1389 : 1811 : tmp = tgt;
1390 : :
1391 : 1811 : if (mask != ~(uint64_t) 0)
1392 : : {
1393 : 437 : tree m = build_int_cst (bswap_type, mask);
1394 : 437 : tmp = make_temp_ssa_name (bswap_type, NULL, "bswapdst");
1395 : 437 : gimple_set_lhs (bswap_stmt, tmp);
1396 : 437 : mask_stmt = gimple_build_assign (tgt, BIT_AND_EXPR, tmp, m);
1397 : 437 : tmp = tgt;
1398 : : }
1399 : :
1400 : 1811 : if (l_rotate)
1401 : : {
1402 : 96 : tree m = build_int_cst (bswap_type, l_rotate);
1403 : 125 : tmp = make_temp_ssa_name (bswap_type, NULL,
1404 : : mask_stmt ? "bswapmaskdst" : "bswapdst");
1405 : 125 : gimple_set_lhs (mask_stmt ? mask_stmt : bswap_stmt, tmp);
1406 : 96 : rotl_stmt = gimple_build_assign (tgt, LROTATE_EXPR, tmp, m);
1407 : 96 : tmp = tgt;
1408 : : }
1409 : :
1410 : : /* Convert the result if necessary. */
1411 : 1811 : if (!useless_type_conversion_p (TREE_TYPE (tgt), bswap_type))
1412 : : {
1413 : 624 : tmp = make_temp_ssa_name (bswap_type, NULL, "bswapdst");
1414 : 624 : tree atmp = tmp;
1415 : 624 : gimple_stmt_iterator gsi2 = gsi;
1416 : 624 : if (conv_code == VIEW_CONVERT_EXPR)
1417 : 262 : atmp = bswap_view_convert (&gsi2, TREE_TYPE (tgt), tmp, false);
1418 : 624 : gimple *convert_stmt = gimple_build_assign (tgt, conv_code, atmp);
1419 : 624 : gsi_insert_after (&gsi2, convert_stmt, GSI_SAME_STMT);
1420 : : }
1421 : :
1422 : 3526 : gimple_set_lhs (rotl_stmt ? rotl_stmt
1423 : 1715 : : mask_stmt ? mask_stmt : bswap_stmt, tmp);
1424 : :
1425 : 1811 : if (dump_file)
1426 : : {
1427 : 30 : fprintf (dump_file, "%d bit bswap implementation found at: ",
1428 : 30 : (int) n->range);
1429 : 30 : if (cur_stmt)
1430 : 21 : print_gimple_stmt (dump_file, cur_stmt, 0);
1431 : : else
1432 : : {
1433 : 9 : print_generic_expr (dump_file, tgt, TDF_NONE);
1434 : 9 : fprintf (dump_file, "\n");
1435 : : }
1436 : : }
1437 : :
1438 : 1811 : if (cur_stmt)
1439 : : {
1440 : 1516 : if (rotl_stmt)
1441 : 96 : gsi_insert_after (&gsi, rotl_stmt, GSI_SAME_STMT);
1442 : 1516 : if (mask_stmt)
1443 : 437 : gsi_insert_after (&gsi, mask_stmt, GSI_SAME_STMT);
1444 : 1516 : gsi_insert_after (&gsi, bswap_stmt, GSI_SAME_STMT);
1445 : 1516 : gsi_remove (&gsi, true);
1446 : : }
1447 : : else
1448 : : {
1449 : 295 : gsi_insert_before (&gsi, bswap_stmt, GSI_SAME_STMT);
1450 : 295 : if (mask_stmt)
1451 : 0 : gsi_insert_before (&gsi, mask_stmt, GSI_SAME_STMT);
1452 : 295 : if (rotl_stmt)
1453 : 0 : gsi_insert_after (&gsi, rotl_stmt, GSI_SAME_STMT);
1454 : : }
1455 : : return tgt;
1456 : : }
1457 : :
1458 : : /* Try to optimize an assignment CUR_STMT with CONSTRUCTOR on the rhs
1459 : : using bswap optimizations. CDI_DOMINATORS need to be
1460 : : computed on entry. Return true if it has been optimized and
1461 : : TODO_update_ssa is needed. */
1462 : :
1463 : : static bool
1464 : 1132113 : maybe_optimize_vector_constructor (gimple *cur_stmt)
1465 : : {
1466 : 1132113 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
1467 : 1132113 : struct symbolic_number n;
1468 : 1132113 : bool bswap;
1469 : :
1470 : 1132113 : gcc_assert (is_gimple_assign (cur_stmt)
1471 : : && gimple_assign_rhs_code (cur_stmt) == CONSTRUCTOR);
1472 : :
1473 : 1132113 : tree rhs = gimple_assign_rhs1 (cur_stmt);
1474 : 1132113 : if (!VECTOR_TYPE_P (TREE_TYPE (rhs))
1475 : 112116 : || !INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs)))
1476 : 1241065 : || gimple_assign_lhs (cur_stmt) == NULL_TREE)
1477 : : return false;
1478 : :
1479 : 108952 : HOST_WIDE_INT sz = int_size_in_bytes (TREE_TYPE (rhs)) * BITS_PER_UNIT;
1480 : 108952 : switch (sz)
1481 : : {
1482 : 1058 : case 16:
1483 : 1058 : load_type = bswap_type = uint16_type_node;
1484 : 1058 : break;
1485 : 2017 : case 32:
1486 : 2017 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
1487 : 4010 : && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing)
1488 : : {
1489 : 1993 : load_type = uint32_type_node;
1490 : 1993 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
1491 : 1993 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1492 : : }
1493 : : else
1494 : 24 : return false;
1495 : 1993 : break;
1496 : 41109 : case 64:
1497 : 41109 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
1498 : 81373 : && (optab_handler (bswap_optab, DImode) != CODE_FOR_nothing
1499 : 36176 : || (word_mode == SImode
1500 : 36176 : && builtin_decl_explicit_p (BUILT_IN_BSWAP32)
1501 : 36176 : && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing)))
1502 : : {
1503 : 40264 : load_type = uint64_type_node;
1504 : 40264 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
1505 : 40264 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1506 : : }
1507 : : else
1508 : 845 : return false;
1509 : 40264 : break;
1510 : : default:
1511 : : return false;
1512 : : }
1513 : :
1514 : 43315 : bool cast64_to_32;
1515 : 43315 : uint64_t mask, l_rotate;
1516 : 43315 : gimple *ins_stmt = find_bswap_or_nop (cur_stmt, &n, &bswap,
1517 : : &cast64_to_32, &mask, &l_rotate);
1518 : 43315 : if (!ins_stmt
1519 : 5551 : || n.range != (unsigned HOST_WIDE_INT) sz
1520 : 5230 : || cast64_to_32
1521 : 5230 : || mask != ~(uint64_t) 0)
1522 : : return false;
1523 : :
1524 : 5230 : if (bswap && !fndecl && n.range != 16)
1525 : : return false;
1526 : :
1527 : 5230 : memset (&nop_stats, 0, sizeof (nop_stats));
1528 : 5230 : memset (&bswap_stats, 0, sizeof (bswap_stats));
1529 : 5230 : return bswap_replace (gsi_for_stmt (cur_stmt), ins_stmt, fndecl,
1530 : : bswap_type, load_type, &n, bswap, mask,
1531 : 5230 : l_rotate) != NULL_TREE;
1532 : : }
1533 : :
1534 : : /* Find manual byte swap implementations as well as load in a given
1535 : : endianness. Byte swaps are turned into a bswap builtin invokation
1536 : : while endian loads are converted to bswap builtin invokation or
1537 : : simple load according to the target endianness. */
1538 : :
1539 : : unsigned int
1540 : 901282 : pass_optimize_bswap::execute (function *fun)
1541 : : {
1542 : 901282 : basic_block bb;
1543 : 901282 : bool bswap32_p, bswap64_p;
1544 : 901282 : bool changed = false;
1545 : 901282 : tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1546 : :
1547 : 901282 : bswap32_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
1548 : 1717441 : && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing);
1549 : 901282 : bswap64_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
1550 : 1717441 : && (optab_handler (bswap_optab, DImode) != CODE_FOR_nothing
1551 : 119662 : || (bswap32_p && word_mode == SImode)));
1552 : :
1553 : : /* Determine the argument type of the builtins. The code later on
1554 : : assumes that the return and argument type are the same. */
1555 : 901282 : if (bswap32_p)
1556 : : {
1557 : 816159 : tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
1558 : 816159 : bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1559 : : }
1560 : :
1561 : 901282 : if (bswap64_p)
1562 : : {
1563 : 816159 : tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
1564 : 816159 : bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1565 : : }
1566 : :
1567 : 901282 : memset (&nop_stats, 0, sizeof (nop_stats));
1568 : 901282 : memset (&bswap_stats, 0, sizeof (bswap_stats));
1569 : 901282 : calculate_dominance_info (CDI_DOMINATORS);
1570 : :
1571 : 8752388 : FOR_EACH_BB_FN (bb, fun)
1572 : : {
1573 : 7851106 : gimple_stmt_iterator gsi;
1574 : :
1575 : : /* We do a reverse scan for bswap patterns to make sure we get the
1576 : : widest match. As bswap pattern matching doesn't handle previously
1577 : : inserted smaller bswap replacements as sub-patterns, the wider
1578 : : variant wouldn't be detected. */
1579 : 79568865 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1580 : : {
1581 : 63866653 : gimple *ins_stmt, *cur_stmt = gsi_stmt (gsi);
1582 : 63866653 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
1583 : 63866653 : enum tree_code code;
1584 : 63866653 : struct symbolic_number n;
1585 : 63866653 : bool bswap, cast64_to_32;
1586 : 63866653 : uint64_t mask, l_rotate;
1587 : :
1588 : : /* This gsi_prev (&gsi) is not part of the for loop because cur_stmt
1589 : : might be moved to a different basic block by bswap_replace and gsi
1590 : : must not points to it if that's the case. Moving the gsi_prev
1591 : : there make sure that gsi points to the statement previous to
1592 : : cur_stmt while still making sure that all statements are
1593 : : considered in this basic block. */
1594 : 63866653 : gsi_prev (&gsi);
1595 : :
1596 : 63866653 : if (!is_gimple_assign (cur_stmt))
1597 : 63864181 : continue;
1598 : :
1599 : 18644135 : code = gimple_assign_rhs_code (cur_stmt);
1600 : 18644135 : switch (code)
1601 : : {
1602 : 6603 : case LROTATE_EXPR:
1603 : 6603 : case RROTATE_EXPR:
1604 : 6603 : if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt))
1605 : 6603 : || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt))
1606 : 3754 : % BITS_PER_UNIT)
1607 : 5873 : continue;
1608 : : /* Fall through. */
1609 : : case BIT_IOR_EXPR:
1610 : : case BIT_XOR_EXPR:
1611 : : case PLUS_EXPR:
1612 : : break;
1613 : 1264368 : case CONSTRUCTOR:
1614 : 1264368 : {
1615 : 1264368 : tree rhs = gimple_assign_rhs1 (cur_stmt);
1616 : 1264368 : if (VECTOR_TYPE_P (TREE_TYPE (rhs))
1617 : 1264368 : && INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs))))
1618 : : break;
1619 : : }
1620 : 1260609 : continue;
1621 : 15537546 : default:
1622 : 15537546 : continue;
1623 : 16798155 : }
1624 : :
1625 : 1840107 : ins_stmt = find_bswap_or_nop (cur_stmt, &n, &bswap,
1626 : : &cast64_to_32, &mask, &l_rotate);
1627 : :
1628 : 1840107 : if (!ins_stmt)
1629 : 1835619 : continue;
1630 : :
1631 : 4488 : switch (n.range)
1632 : : {
1633 : 948 : case 16:
1634 : : /* Already in canonical form, nothing to do. */
1635 : 948 : if (code == LROTATE_EXPR || code == RROTATE_EXPR)
1636 : 333 : continue;
1637 : 615 : load_type = bswap_type = uint16_type_node;
1638 : 615 : break;
1639 : 1277 : case 32:
1640 : 1277 : load_type = uint32_type_node;
1641 : 1277 : if (bswap32_p)
1642 : : {
1643 : 1277 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
1644 : 1277 : bswap_type = bswap32_type;
1645 : : }
1646 : : break;
1647 : 580 : case 64:
1648 : 580 : load_type = uint64_type_node;
1649 : 580 : if (bswap64_p)
1650 : : {
1651 : 580 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
1652 : 580 : bswap_type = bswap64_type;
1653 : : }
1654 : : break;
1655 : 1683 : default:
1656 : 1683 : continue;
1657 : : }
1658 : :
1659 : 2472 : if (bswap && !fndecl && n.range != 16)
1660 : 0 : continue;
1661 : :
1662 : 2472 : if (bswap_replace (gsi_for_stmt (cur_stmt), ins_stmt, fndecl,
1663 : : bswap_type, load_type, &n, bswap, mask,
1664 : : l_rotate))
1665 : 2472 : changed = true;
1666 : : }
1667 : : }
1668 : :
1669 : 901282 : statistics_counter_event (fun, "16-bit nop implementations found",
1670 : : nop_stats.found_16bit);
1671 : 901282 : statistics_counter_event (fun, "32-bit nop implementations found",
1672 : : nop_stats.found_32bit);
1673 : 901282 : statistics_counter_event (fun, "64-bit nop implementations found",
1674 : : nop_stats.found_64bit);
1675 : 901282 : statistics_counter_event (fun, "16-bit bswap implementations found",
1676 : : bswap_stats.found_16bit);
1677 : 901282 : statistics_counter_event (fun, "32-bit bswap implementations found",
1678 : : bswap_stats.found_32bit);
1679 : 901282 : statistics_counter_event (fun, "64-bit bswap implementations found",
1680 : : bswap_stats.found_64bit);
1681 : :
1682 : 901282 : return (changed ? TODO_update_ssa : 0);
1683 : : }
1684 : :
1685 : : } // anon namespace
1686 : :
1687 : : gimple_opt_pass *
1688 : 280455 : make_pass_optimize_bswap (gcc::context *ctxt)
1689 : : {
1690 : 280455 : return new pass_optimize_bswap (ctxt);
1691 : : }
1692 : :
1693 : : namespace {
1694 : :
1695 : : /* Struct recording one operand for the store, which is either a constant,
1696 : : then VAL represents the constant and all the other fields are zero, or
1697 : : a memory load, then VAL represents the reference, BASE_ADDR is non-NULL
1698 : : and the other fields also reflect the memory load, or an SSA name, then
1699 : : VAL represents the SSA name and all the other fields are zero. */
1700 : :
1701 : : class store_operand_info
1702 : : {
1703 : : public:
1704 : : tree val;
1705 : : tree base_addr;
1706 : : poly_uint64 bitsize;
1707 : : poly_uint64 bitpos;
1708 : : poly_uint64 bitregion_start;
1709 : : poly_uint64 bitregion_end;
1710 : : gimple *stmt;
1711 : : bool bit_not_p;
1712 : : store_operand_info ();
1713 : : };
1714 : :
1715 : 9404908 : store_operand_info::store_operand_info ()
1716 : 9404908 : : val (NULL_TREE), base_addr (NULL_TREE), bitsize (0), bitpos (0),
1717 : 9404908 : bitregion_start (0), bitregion_end (0), stmt (NULL), bit_not_p (false)
1718 : : {
1719 : 0 : }
1720 : :
1721 : : /* Struct recording the information about a single store of an immediate
1722 : : to memory. These are created in the first phase and coalesced into
1723 : : merged_store_group objects in the second phase. */
1724 : :
1725 : : class store_immediate_info
1726 : : {
1727 : : public:
1728 : : unsigned HOST_WIDE_INT bitsize;
1729 : : unsigned HOST_WIDE_INT bitpos;
1730 : : unsigned HOST_WIDE_INT bitregion_start;
1731 : : /* This is one past the last bit of the bit region. */
1732 : : unsigned HOST_WIDE_INT bitregion_end;
1733 : : gimple *stmt;
1734 : : unsigned int order;
1735 : : /* INTEGER_CST for constant store, STRING_CST for string store,
1736 : : MEM_REF for memory copy, BIT_*_EXPR for logical bitwise operation,
1737 : : BIT_INSERT_EXPR for bit insertion.
1738 : : LROTATE_EXPR if it can be only bswap optimized and
1739 : : ops are not really meaningful.
1740 : : NOP_EXPR if bswap optimization detected identity, ops
1741 : : are not meaningful. */
1742 : : enum tree_code rhs_code;
1743 : : /* Two fields for bswap optimization purposes. */
1744 : : struct symbolic_number n;
1745 : : gimple *ins_stmt;
1746 : : /* True if BIT_{AND,IOR,XOR}_EXPR result is inverted before storing. */
1747 : : bool bit_not_p;
1748 : : /* True if ops have been swapped and thus ops[1] represents
1749 : : rhs1 of BIT_{AND,IOR,XOR}_EXPR and ops[0] represents rhs2. */
1750 : : bool ops_swapped_p;
1751 : : /* The index number of the landing pad, or 0 if there is none. */
1752 : : int lp_nr;
1753 : : /* Operands. For BIT_*_EXPR rhs_code both operands are used, otherwise
1754 : : just the first one. */
1755 : : store_operand_info ops[2];
1756 : : store_immediate_info (unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
1757 : : unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
1758 : : gimple *, unsigned int, enum tree_code,
1759 : : struct symbolic_number &, gimple *, bool, int,
1760 : : const store_operand_info &,
1761 : : const store_operand_info &);
1762 : : };
1763 : :
1764 : 2873574 : store_immediate_info::store_immediate_info (unsigned HOST_WIDE_INT bs,
1765 : : unsigned HOST_WIDE_INT bp,
1766 : : unsigned HOST_WIDE_INT brs,
1767 : : unsigned HOST_WIDE_INT bre,
1768 : : gimple *st,
1769 : : unsigned int ord,
1770 : : enum tree_code rhscode,
1771 : : struct symbolic_number &nr,
1772 : : gimple *ins_stmtp,
1773 : : bool bitnotp,
1774 : : int nr2,
1775 : : const store_operand_info &op0r,
1776 : 2873574 : const store_operand_info &op1r)
1777 : 2873574 : : bitsize (bs), bitpos (bp), bitregion_start (brs), bitregion_end (bre),
1778 : 2873574 : stmt (st), order (ord), rhs_code (rhscode), n (nr),
1779 : 2873574 : ins_stmt (ins_stmtp), bit_not_p (bitnotp), ops_swapped_p (false),
1780 : 2873574 : lp_nr (nr2), ops { op0r, op1r }
1781 : : {
1782 : 0 : }
1783 : :
1784 : : /* Struct representing a group of stores to contiguous memory locations.
1785 : : These are produced by the second phase (coalescing) and consumed in the
1786 : : third phase that outputs the widened stores. */
1787 : :
1788 : : class merged_store_group
1789 : : {
1790 : : public:
1791 : : unsigned HOST_WIDE_INT start;
1792 : : unsigned HOST_WIDE_INT width;
1793 : : unsigned HOST_WIDE_INT bitregion_start;
1794 : : unsigned HOST_WIDE_INT bitregion_end;
1795 : : /* The size of the allocated memory for val and mask. */
1796 : : unsigned HOST_WIDE_INT buf_size;
1797 : : unsigned HOST_WIDE_INT align_base;
1798 : : poly_uint64 load_align_base[2];
1799 : :
1800 : : unsigned int align;
1801 : : unsigned int load_align[2];
1802 : : unsigned int first_order;
1803 : : unsigned int last_order;
1804 : : bool bit_insertion;
1805 : : bool string_concatenation;
1806 : : bool only_constants;
1807 : : bool consecutive;
1808 : : unsigned int first_nonmergeable_order;
1809 : : int lp_nr;
1810 : :
1811 : : auto_vec<store_immediate_info *> stores;
1812 : : /* We record the first and last original statements in the sequence because
1813 : : we'll need their vuse/vdef and replacement position. It's easier to keep
1814 : : track of them separately as 'stores' is reordered by apply_stores. */
1815 : : gimple *last_stmt;
1816 : : gimple *first_stmt;
1817 : : unsigned char *val;
1818 : : unsigned char *mask;
1819 : :
1820 : : merged_store_group (store_immediate_info *);
1821 : : ~merged_store_group ();
1822 : : bool can_be_merged_into (store_immediate_info *);
1823 : : void merge_into (store_immediate_info *);
1824 : : void merge_overlapping (store_immediate_info *);
1825 : : bool apply_stores ();
1826 : : private:
1827 : : void do_merge (store_immediate_info *);
1828 : : };
1829 : :
1830 : : /* Debug helper. Dump LEN elements of byte array PTR to FD in hex. */
1831 : :
1832 : : static void
1833 : 460 : dump_char_array (FILE *fd, unsigned char *ptr, unsigned int len)
1834 : : {
1835 : 460 : if (!fd)
1836 : : return;
1837 : :
1838 : 23388 : for (unsigned int i = 0; i < len; i++)
1839 : 22928 : fprintf (fd, "%02x ", ptr[i]);
1840 : 460 : fprintf (fd, "\n");
1841 : : }
1842 : :
1843 : : /* Clear out LEN bits starting from bit START in the byte array
1844 : : PTR. This clears the bits to the *right* from START.
1845 : : START must be within [0, BITS_PER_UNIT) and counts starting from
1846 : : the least significant bit. */
1847 : :
1848 : : static void
1849 : 12 : clear_bit_region_be (unsigned char *ptr, unsigned int start,
1850 : : unsigned int len)
1851 : : {
1852 : 20 : if (len == 0)
1853 : : return;
1854 : : /* Clear len bits to the right of start. */
1855 : 20 : else if (len <= start + 1)
1856 : : {
1857 : 8 : unsigned char mask = (~(~0U << len));
1858 : 8 : mask = mask << (start + 1U - len);
1859 : 8 : ptr[0] &= ~mask;
1860 : : }
1861 : 12 : else if (start != BITS_PER_UNIT - 1)
1862 : : {
1863 : 4 : clear_bit_region_be (ptr, start, (start % BITS_PER_UNIT) + 1);
1864 : 4 : clear_bit_region_be (ptr + 1, BITS_PER_UNIT - 1,
1865 : 4 : len - (start % BITS_PER_UNIT) - 1);
1866 : : }
1867 : 8 : else if (start == BITS_PER_UNIT - 1
1868 : : && len > BITS_PER_UNIT)
1869 : : {
1870 : 8 : unsigned int nbytes = len / BITS_PER_UNIT;
1871 : 8 : memset (ptr, 0, nbytes);
1872 : 8 : if (len % BITS_PER_UNIT != 0)
1873 : 4 : clear_bit_region_be (ptr + nbytes, BITS_PER_UNIT - 1,
1874 : : len % BITS_PER_UNIT);
1875 : : }
1876 : : else
1877 : 0 : gcc_unreachable ();
1878 : : }
1879 : :
1880 : : /* In the byte array PTR clear the bit region starting at bit
1881 : : START and is LEN bits wide.
1882 : : For regions spanning multiple bytes do this recursively until we reach
1883 : : zero LEN or a region contained within a single byte. */
1884 : :
1885 : : static void
1886 : 1345358 : clear_bit_region (unsigned char *ptr, unsigned int start,
1887 : : unsigned int len)
1888 : : {
1889 : : /* Degenerate base case. */
1890 : 1404348 : if (len == 0)
1891 : : return;
1892 : 1404348 : else if (start >= BITS_PER_UNIT)
1893 : 27559 : clear_bit_region (ptr + 1, start - BITS_PER_UNIT, len);
1894 : : /* Second base case. */
1895 : 1376789 : else if ((start + len) <= BITS_PER_UNIT)
1896 : : {
1897 : 147642 : unsigned char mask = (~0U) << (unsigned char) (BITS_PER_UNIT - len);
1898 : 147642 : mask >>= BITS_PER_UNIT - (start + len);
1899 : :
1900 : 147642 : ptr[0] &= ~mask;
1901 : :
1902 : 147642 : return;
1903 : : }
1904 : : /* Clear most significant bits in a byte and proceed with the next byte. */
1905 : 1229147 : else if (start != 0)
1906 : : {
1907 : 28655 : clear_bit_region (ptr, start, BITS_PER_UNIT - start);
1908 : 28655 : clear_bit_region (ptr + 1, 0, len - (BITS_PER_UNIT - start));
1909 : : }
1910 : : /* Whole bytes need to be cleared. */
1911 : 1200492 : else if (start == 0 && len > BITS_PER_UNIT)
1912 : : {
1913 : 1200492 : unsigned int nbytes = len / BITS_PER_UNIT;
1914 : : /* We could recurse on each byte but we clear whole bytes, so a simple
1915 : : memset will do. */
1916 : 1200492 : memset (ptr, '\0', nbytes);
1917 : : /* Clear the remaining sub-byte region if there is one. */
1918 : 1200492 : if (len % BITS_PER_UNIT != 0)
1919 : 2776 : clear_bit_region (ptr + nbytes, 0, len % BITS_PER_UNIT);
1920 : : }
1921 : : else
1922 : 0 : gcc_unreachable ();
1923 : : }
1924 : :
1925 : : /* Write BITLEN bits of EXPR to the byte array PTR at
1926 : : bit position BITPOS. PTR should contain TOTAL_BYTES elements.
1927 : : Return true if the operation succeeded. */
1928 : :
1929 : : static bool
1930 : 1015615 : encode_tree_to_bitpos (tree expr, unsigned char *ptr, int bitlen, int bitpos,
1931 : : unsigned int total_bytes)
1932 : : {
1933 : 1015615 : unsigned int first_byte = bitpos / BITS_PER_UNIT;
1934 : 1015615 : bool sub_byte_op_p = ((bitlen % BITS_PER_UNIT)
1935 : 1000287 : || (bitpos % BITS_PER_UNIT)
1936 : 2015379 : || !int_mode_for_size (bitlen, 0).exists ());
1937 : 1015615 : bool empty_ctor_p
1938 : 1015615 : = (TREE_CODE (expr) == CONSTRUCTOR
1939 : 349080 : && CONSTRUCTOR_NELTS (expr) == 0
1940 : 349080 : && TYPE_SIZE_UNIT (TREE_TYPE (expr))
1941 : 1364695 : && tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (expr))));
1942 : :
1943 : 1015615 : if (!sub_byte_op_p)
1944 : : {
1945 : 892397 : if (first_byte >= total_bytes)
1946 : : return false;
1947 : 892397 : total_bytes -= first_byte;
1948 : 892397 : if (empty_ctor_p)
1949 : : {
1950 : 242055 : unsigned HOST_WIDE_INT rhs_bytes
1951 : 242055 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (expr)));
1952 : 242055 : if (rhs_bytes > total_bytes)
1953 : : return false;
1954 : 242055 : memset (ptr + first_byte, '\0', rhs_bytes);
1955 : 242055 : return true;
1956 : : }
1957 : 650342 : return native_encode_expr (expr, ptr + first_byte, total_bytes) != 0;
1958 : : }
1959 : :
1960 : : /* LITTLE-ENDIAN
1961 : : We are writing a non byte-sized quantity or at a position that is not
1962 : : at a byte boundary.
1963 : : |--------|--------|--------| ptr + first_byte
1964 : : ^ ^
1965 : : xxx xxxxxxxx xxx< bp>
1966 : : |______EXPR____|
1967 : :
1968 : : First native_encode_expr EXPR into a temporary buffer and shift each
1969 : : byte in the buffer by 'bp' (carrying the bits over as necessary).
1970 : : |00000000|00xxxxxx|xxxxxxxx| << bp = |000xxxxx|xxxxxxxx|xxx00000|
1971 : : <------bitlen---->< bp>
1972 : : Then we clear the destination bits:
1973 : : |---00000|00000000|000-----| ptr + first_byte
1974 : : <-------bitlen--->< bp>
1975 : :
1976 : : Finally we ORR the bytes of the shifted EXPR into the cleared region:
1977 : : |---xxxxx||xxxxxxxx||xxx-----| ptr + first_byte.
1978 : :
1979 : : BIG-ENDIAN
1980 : : We are writing a non byte-sized quantity or at a position that is not
1981 : : at a byte boundary.
1982 : : ptr + first_byte |--------|--------|--------|
1983 : : ^ ^
1984 : : <bp >xxx xxxxxxxx xxx
1985 : : |_____EXPR_____|
1986 : :
1987 : : First native_encode_expr EXPR into a temporary buffer and shift each
1988 : : byte in the buffer to the right by (carrying the bits over as necessary).
1989 : : We shift by as much as needed to align the most significant bit of EXPR
1990 : : with bitpos:
1991 : : |00xxxxxx|xxxxxxxx| >> 3 = |00000xxx|xxxxxxxx|xxxxx000|
1992 : : <---bitlen----> <bp ><-----bitlen----->
1993 : : Then we clear the destination bits:
1994 : : ptr + first_byte |-----000||00000000||00000---|
1995 : : <bp ><-------bitlen----->
1996 : :
1997 : : Finally we ORR the bytes of the shifted EXPR into the cleared region:
1998 : : ptr + first_byte |---xxxxx||xxxxxxxx||xxx-----|.
1999 : : The awkwardness comes from the fact that bitpos is counted from the
2000 : : most significant bit of a byte. */
2001 : :
2002 : : /* We must be dealing with fixed-size data at this point, since the
2003 : : total size is also fixed. */
2004 : 123218 : unsigned int byte_size;
2005 : 123218 : if (empty_ctor_p)
2006 : : {
2007 : 107025 : unsigned HOST_WIDE_INT rhs_bytes
2008 : 107025 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (expr)));
2009 : 107025 : if (rhs_bytes > total_bytes)
2010 : : return false;
2011 : 107025 : byte_size = rhs_bytes;
2012 : : }
2013 : : else
2014 : : {
2015 : 16193 : fixed_size_mode mode
2016 : 16193 : = as_a <fixed_size_mode> (TYPE_MODE (TREE_TYPE (expr)));
2017 : 16193 : byte_size
2018 : 16193 : = mode == BLKmode
2019 : 241 : ? tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (expr)))
2020 : 15952 : : GET_MODE_SIZE (mode);
2021 : : }
2022 : : /* Allocate an extra byte so that we have space to shift into. */
2023 : 123218 : byte_size++;
2024 : 123218 : unsigned char *tmpbuf = XALLOCAVEC (unsigned char, byte_size);
2025 : 123218 : memset (tmpbuf, '\0', byte_size);
2026 : : /* The store detection code should only have allowed constants that are
2027 : : accepted by native_encode_expr or empty ctors. */
2028 : 123218 : if (!empty_ctor_p
2029 : 123218 : && native_encode_expr (expr, tmpbuf, byte_size - 1) == 0)
2030 : 0 : gcc_unreachable ();
2031 : :
2032 : : /* The native_encode_expr machinery uses TYPE_MODE to determine how many
2033 : : bytes to write. This means it can write more than
2034 : : ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT bytes (for example
2035 : : write 8 bytes for a bitlen of 40). Skip the bytes that are not within
2036 : : bitlen and zero out the bits that are not relevant as well (that may
2037 : : contain a sign bit due to sign-extension). */
2038 : 123218 : unsigned int padding
2039 : 123218 : = byte_size - ROUND_UP (bitlen, BITS_PER_UNIT) / BITS_PER_UNIT - 1;
2040 : : /* On big-endian the padding is at the 'front' so just skip the initial
2041 : : bytes. */
2042 : 123218 : if (BYTES_BIG_ENDIAN)
2043 : : tmpbuf += padding;
2044 : :
2045 : 123218 : byte_size -= padding;
2046 : :
2047 : 123218 : if (bitlen % BITS_PER_UNIT != 0)
2048 : : {
2049 : 15328 : if (BYTES_BIG_ENDIAN)
2050 : : clear_bit_region_be (tmpbuf, BITS_PER_UNIT - 1,
2051 : : BITS_PER_UNIT - (bitlen % BITS_PER_UNIT));
2052 : : else
2053 : 15328 : clear_bit_region (tmpbuf, bitlen,
2054 : 15328 : byte_size * BITS_PER_UNIT - bitlen);
2055 : : }
2056 : : /* Left shifting relies on the last byte being clear if bitlen is
2057 : : a multiple of BITS_PER_UNIT, which might not be clear if
2058 : : there are padding bytes. */
2059 : 107890 : else if (!BYTES_BIG_ENDIAN)
2060 : 107890 : tmpbuf[byte_size - 1] = '\0';
2061 : :
2062 : : /* Clear the bit region in PTR where the bits from TMPBUF will be
2063 : : inserted into. */
2064 : 123218 : if (BYTES_BIG_ENDIAN)
2065 : : clear_bit_region_be (ptr + first_byte,
2066 : : BITS_PER_UNIT - 1 - (bitpos % BITS_PER_UNIT), bitlen);
2067 : : else
2068 : 123218 : clear_bit_region (ptr + first_byte, bitpos % BITS_PER_UNIT, bitlen);
2069 : :
2070 : 123218 : int shift_amnt;
2071 : 123218 : int bitlen_mod = bitlen % BITS_PER_UNIT;
2072 : 123218 : int bitpos_mod = bitpos % BITS_PER_UNIT;
2073 : :
2074 : 123218 : bool skip_byte = false;
2075 : 123218 : if (BYTES_BIG_ENDIAN)
2076 : : {
2077 : : /* BITPOS and BITLEN are exactly aligned and no shifting
2078 : : is necessary. */
2079 : : if (bitpos_mod + bitlen_mod == BITS_PER_UNIT
2080 : : || (bitpos_mod == 0 && bitlen_mod == 0))
2081 : : shift_amnt = 0;
2082 : : /* |. . . . . . . .|
2083 : : <bp > <blen >.
2084 : : We always shift right for BYTES_BIG_ENDIAN so shift the beginning
2085 : : of the value until it aligns with 'bp' in the next byte over. */
2086 : : else if (bitpos_mod + bitlen_mod < BITS_PER_UNIT)
2087 : : {
2088 : : shift_amnt = bitlen_mod + bitpos_mod;
2089 : : skip_byte = bitlen_mod != 0;
2090 : : }
2091 : : /* |. . . . . . . .|
2092 : : <----bp--->
2093 : : <---blen---->.
2094 : : Shift the value right within the same byte so it aligns with 'bp'. */
2095 : : else
2096 : : shift_amnt = bitlen_mod + bitpos_mod - BITS_PER_UNIT;
2097 : : }
2098 : : else
2099 : 123218 : shift_amnt = bitpos % BITS_PER_UNIT;
2100 : :
2101 : : /* Create the shifted version of EXPR. */
2102 : 123218 : if (!BYTES_BIG_ENDIAN)
2103 : : {
2104 : 123218 : shift_bytes_in_array_left (tmpbuf, byte_size, shift_amnt);
2105 : 123218 : if (shift_amnt == 0)
2106 : 114686 : byte_size--;
2107 : : }
2108 : : else
2109 : : {
2110 : : gcc_assert (BYTES_BIG_ENDIAN);
2111 : : shift_bytes_in_array_right (tmpbuf, byte_size, shift_amnt);
2112 : : /* If shifting right forced us to move into the next byte skip the now
2113 : : empty byte. */
2114 : : if (skip_byte)
2115 : : {
2116 : : tmpbuf++;
2117 : : byte_size--;
2118 : : }
2119 : : }
2120 : :
2121 : : /* Insert the bits from TMPBUF. */
2122 : 23918761 : for (unsigned int i = 0; i < byte_size; i++)
2123 : 23795543 : ptr[first_byte + i] |= tmpbuf[i];
2124 : :
2125 : : return true;
2126 : : }
2127 : :
2128 : : /* Sorting function for store_immediate_info objects.
2129 : : Sorts them by bitposition. */
2130 : :
2131 : : static int
2132 : 16079947 : sort_by_bitpos (const void *x, const void *y)
2133 : : {
2134 : 16079947 : store_immediate_info *const *tmp = (store_immediate_info * const *) x;
2135 : 16079947 : store_immediate_info *const *tmp2 = (store_immediate_info * const *) y;
2136 : :
2137 : 16079947 : if ((*tmp)->bitpos < (*tmp2)->bitpos)
2138 : : return -1;
2139 : 8750518 : else if ((*tmp)->bitpos > (*tmp2)->bitpos)
2140 : : return 1;
2141 : : else
2142 : : /* If they are the same let's use the order which is guaranteed to
2143 : : be different. */
2144 : 1553367 : return (*tmp)->order - (*tmp2)->order;
2145 : : }
2146 : :
2147 : : /* Sorting function for store_immediate_info objects.
2148 : : Sorts them by the order field. */
2149 : :
2150 : : static int
2151 : 6147360 : sort_by_order (const void *x, const void *y)
2152 : : {
2153 : 6147360 : store_immediate_info *const *tmp = (store_immediate_info * const *) x;
2154 : 6147360 : store_immediate_info *const *tmp2 = (store_immediate_info * const *) y;
2155 : :
2156 : 6147360 : if ((*tmp)->order < (*tmp2)->order)
2157 : : return -1;
2158 : 3020406 : else if ((*tmp)->order > (*tmp2)->order)
2159 : : return 1;
2160 : :
2161 : 0 : gcc_unreachable ();
2162 : : }
2163 : :
2164 : : /* Initialize a merged_store_group object from a store_immediate_info
2165 : : object. */
2166 : :
2167 : 796167 : merged_store_group::merged_store_group (store_immediate_info *info)
2168 : : {
2169 : 796167 : start = info->bitpos;
2170 : 796167 : width = info->bitsize;
2171 : 796167 : bitregion_start = info->bitregion_start;
2172 : 796167 : bitregion_end = info->bitregion_end;
2173 : : /* VAL has memory allocated for it in apply_stores once the group
2174 : : width has been finalized. */
2175 : 796167 : val = NULL;
2176 : 796167 : mask = NULL;
2177 : 796167 : bit_insertion = info->rhs_code == BIT_INSERT_EXPR;
2178 : 796167 : string_concatenation = info->rhs_code == STRING_CST;
2179 : 796167 : only_constants = info->rhs_code == INTEGER_CST;
2180 : 796167 : consecutive = true;
2181 : 796167 : first_nonmergeable_order = ~0U;
2182 : 796167 : lp_nr = info->lp_nr;
2183 : 796167 : unsigned HOST_WIDE_INT align_bitpos = 0;
2184 : 796167 : get_object_alignment_1 (gimple_assign_lhs (info->stmt),
2185 : : &align, &align_bitpos);
2186 : 796167 : align_base = start - align_bitpos;
2187 : 2388501 : for (int i = 0; i < 2; ++i)
2188 : : {
2189 : 1592334 : store_operand_info &op = info->ops[i];
2190 : 1592334 : if (op.base_addr == NULL_TREE)
2191 : : {
2192 : 1424052 : load_align[i] = 0;
2193 : 1424052 : load_align_base[i] = 0;
2194 : : }
2195 : : else
2196 : : {
2197 : 168282 : get_object_alignment_1 (op.val, &load_align[i], &align_bitpos);
2198 : 168282 : load_align_base[i] = op.bitpos - align_bitpos;
2199 : : }
2200 : : }
2201 : 796167 : stores.create (1);
2202 : 796167 : stores.safe_push (info);
2203 : 796167 : last_stmt = info->stmt;
2204 : 796167 : last_order = info->order;
2205 : 796167 : first_stmt = last_stmt;
2206 : 796167 : first_order = last_order;
2207 : 796167 : buf_size = 0;
2208 : 796167 : }
2209 : :
2210 : 796167 : merged_store_group::~merged_store_group ()
2211 : : {
2212 : 796167 : if (val)
2213 : 407529 : XDELETEVEC (val);
2214 : 796167 : }
2215 : :
2216 : : /* Return true if the store described by INFO can be merged into the group. */
2217 : :
2218 : : bool
2219 : 561195 : merged_store_group::can_be_merged_into (store_immediate_info *info)
2220 : : {
2221 : : /* Do not merge bswap patterns. */
2222 : 561195 : if (info->rhs_code == LROTATE_EXPR)
2223 : : return false;
2224 : :
2225 : 549048 : if (info->lp_nr != lp_nr)
2226 : : return false;
2227 : :
2228 : : /* The canonical case. */
2229 : 549020 : if (info->rhs_code == stores[0]->rhs_code)
2230 : : return true;
2231 : :
2232 : : /* BIT_INSERT_EXPR is compatible with INTEGER_CST if no STRING_CST. */
2233 : 41459 : if (info->rhs_code == BIT_INSERT_EXPR && stores[0]->rhs_code == INTEGER_CST)
2234 : 1816 : return !string_concatenation;
2235 : :
2236 : 39643 : if (stores[0]->rhs_code == BIT_INSERT_EXPR && info->rhs_code == INTEGER_CST)
2237 : 343 : return !string_concatenation;
2238 : :
2239 : : /* We can turn MEM_REF into BIT_INSERT_EXPR for bit-field stores, but do it
2240 : : only for small regions since this can generate a lot of instructions. */
2241 : 39300 : if (info->rhs_code == MEM_REF
2242 : 15327 : && (stores[0]->rhs_code == INTEGER_CST
2243 : 487 : || stores[0]->rhs_code == BIT_INSERT_EXPR)
2244 : 15147 : && info->bitregion_start == stores[0]->bitregion_start
2245 : 614 : && info->bitregion_end == stores[0]->bitregion_end
2246 : 40528 : && info->bitregion_end - info->bitregion_start <= MAX_FIXED_MODE_SIZE)
2247 : 612 : return !string_concatenation;
2248 : :
2249 : 38688 : if (stores[0]->rhs_code == MEM_REF
2250 : 18832 : && (info->rhs_code == INTEGER_CST
2251 : 18832 : || info->rhs_code == BIT_INSERT_EXPR)
2252 : 18613 : && info->bitregion_start == stores[0]->bitregion_start
2253 : 4 : && info->bitregion_end == stores[0]->bitregion_end
2254 : 38692 : && info->bitregion_end - info->bitregion_start <= MAX_FIXED_MODE_SIZE)
2255 : 2 : return !string_concatenation;
2256 : :
2257 : : /* STRING_CST is compatible with INTEGER_CST if no BIT_INSERT_EXPR. */
2258 : 38686 : if (info->rhs_code == STRING_CST
2259 : 129 : && stores[0]->rhs_code == INTEGER_CST
2260 : 38815 : && stores[0]->bitsize == CHAR_BIT)
2261 : 69 : return !bit_insertion;
2262 : :
2263 : 38617 : if (stores[0]->rhs_code == STRING_CST
2264 : 150 : && info->rhs_code == INTEGER_CST
2265 : 38767 : && info->bitsize == CHAR_BIT)
2266 : 14 : return !bit_insertion;
2267 : :
2268 : : return false;
2269 : : }
2270 : :
2271 : : /* Helper method for merge_into and merge_overlapping to do
2272 : : the common part. */
2273 : :
2274 : : void
2275 : 771832 : merged_store_group::do_merge (store_immediate_info *info)
2276 : : {
2277 : 771832 : bitregion_start = MIN (bitregion_start, info->bitregion_start);
2278 : 771832 : bitregion_end = MAX (bitregion_end, info->bitregion_end);
2279 : :
2280 : 771832 : unsigned int this_align;
2281 : 771832 : unsigned HOST_WIDE_INT align_bitpos = 0;
2282 : 771832 : get_object_alignment_1 (gimple_assign_lhs (info->stmt),
2283 : : &this_align, &align_bitpos);
2284 : 771832 : if (this_align > align)
2285 : : {
2286 : 429 : align = this_align;
2287 : 429 : align_base = info->bitpos - align_bitpos;
2288 : : }
2289 : 2315496 : for (int i = 0; i < 2; ++i)
2290 : : {
2291 : 1543664 : store_operand_info &op = info->ops[i];
2292 : 1543664 : if (!op.base_addr)
2293 : 1453176 : continue;
2294 : :
2295 : 90488 : get_object_alignment_1 (op.val, &this_align, &align_bitpos);
2296 : 90488 : if (this_align > load_align[i])
2297 : : {
2298 : 18 : load_align[i] = this_align;
2299 : 18 : load_align_base[i] = op.bitpos - align_bitpos;
2300 : : }
2301 : : }
2302 : :
2303 : 771832 : gimple *stmt = info->stmt;
2304 : 771832 : stores.safe_push (info);
2305 : 771832 : if (info->order > last_order)
2306 : : {
2307 : 579920 : last_order = info->order;
2308 : 579920 : last_stmt = stmt;
2309 : : }
2310 : 191912 : else if (info->order < first_order)
2311 : : {
2312 : 74814 : first_order = info->order;
2313 : 74814 : first_stmt = stmt;
2314 : : }
2315 : :
2316 : 771832 : if (info->bitpos != start + width)
2317 : 278691 : consecutive = false;
2318 : :
2319 : : /* We need to use extraction if there is any bit-field. */
2320 : 771832 : if (info->rhs_code == BIT_INSERT_EXPR)
2321 : : {
2322 : 3267 : bit_insertion = true;
2323 : 3267 : gcc_assert (!string_concatenation);
2324 : : }
2325 : :
2326 : : /* We want to use concatenation if there is any string. */
2327 : 771832 : if (info->rhs_code == STRING_CST)
2328 : : {
2329 : 520 : string_concatenation = true;
2330 : 520 : gcc_assert (!bit_insertion);
2331 : : }
2332 : :
2333 : : /* But we cannot use it if we don't have consecutive stores. */
2334 : 771832 : if (!consecutive)
2335 : 369381 : string_concatenation = false;
2336 : :
2337 : 771832 : if (info->rhs_code != INTEGER_CST)
2338 : 93893 : only_constants = false;
2339 : 771832 : }
2340 : :
2341 : : /* Merge a store recorded by INFO into this merged store.
2342 : : The store is not overlapping with the existing recorded
2343 : : stores. */
2344 : :
2345 : : void
2346 : 94460 : merged_store_group::merge_into (store_immediate_info *info)
2347 : : {
2348 : 94460 : do_merge (info);
2349 : :
2350 : : /* Make sure we're inserting in the position we think we're inserting. */
2351 : 94460 : gcc_assert (info->bitpos >= start + width
2352 : : && info->bitregion_start <= bitregion_end);
2353 : :
2354 : 94460 : width = info->bitpos + info->bitsize - start;
2355 : 94460 : }
2356 : :
2357 : : /* Merge a store described by INFO into this merged store.
2358 : : INFO overlaps in some way with the current store (i.e. it's not contiguous
2359 : : which is handled by merged_store_group::merge_into). */
2360 : :
2361 : : void
2362 : 677372 : merged_store_group::merge_overlapping (store_immediate_info *info)
2363 : : {
2364 : 677372 : do_merge (info);
2365 : :
2366 : : /* If the store extends the size of the group, extend the width. */
2367 : 677372 : if (info->bitpos + info->bitsize > start + width)
2368 : 400035 : width = info->bitpos + info->bitsize - start;
2369 : 677372 : }
2370 : :
2371 : : /* Go through all the recorded stores in this group in program order and
2372 : : apply their values to the VAL byte array to create the final merged
2373 : : value. Return true if the operation succeeded. */
2374 : :
2375 : : bool
2376 : 795646 : merged_store_group::apply_stores ()
2377 : : {
2378 : 795646 : store_immediate_info *info;
2379 : 795646 : unsigned int i;
2380 : :
2381 : : /* Make sure we have more than one store in the group, otherwise we cannot
2382 : : merge anything. */
2383 : 795646 : if (bitregion_start % BITS_PER_UNIT != 0
2384 : 795646 : || bitregion_end % BITS_PER_UNIT != 0
2385 : 1591292 : || stores.length () == 1)
2386 : : return false;
2387 : :
2388 : 407529 : buf_size = (bitregion_end - bitregion_start) / BITS_PER_UNIT;
2389 : :
2390 : : /* Really do string concatenation for large strings only. */
2391 : 407532 : if (buf_size <= MOVE_MAX)
2392 : 175718 : string_concatenation = false;
2393 : :
2394 : : /* String concatenation only works for byte aligned start and end. */
2395 : 407529 : if (start % BITS_PER_UNIT != 0 || width % BITS_PER_UNIT != 0)
2396 : 737 : string_concatenation = false;
2397 : :
2398 : : /* Create a power-of-2-sized buffer for native_encode_expr. */
2399 : 407529 : if (!string_concatenation)
2400 : 814918 : buf_size = 1 << ceil_log2 (buf_size);
2401 : :
2402 : 407529 : val = XNEWVEC (unsigned char, 2 * buf_size);
2403 : 407529 : mask = val + buf_size;
2404 : 407529 : memset (val, 0, buf_size);
2405 : 407529 : memset (mask, ~0U, buf_size);
2406 : :
2407 : 407529 : stores.qsort (sort_by_order);
2408 : :
2409 : 1585651 : FOR_EACH_VEC_ELT (stores, i, info)
2410 : : {
2411 : 1178122 : unsigned int pos_in_buffer = info->bitpos - bitregion_start;
2412 : 1178122 : tree cst;
2413 : 1178122 : if (info->ops[0].val && info->ops[0].base_addr == NULL_TREE)
2414 : : cst = info->ops[0].val;
2415 : 158713 : else if (info->ops[1].val && info->ops[1].base_addr == NULL_TREE)
2416 : : cst = info->ops[1].val;
2417 : : else
2418 : : cst = NULL_TREE;
2419 : 1019721 : bool ret = true;
2420 : 1019721 : if (cst && info->rhs_code != BIT_INSERT_EXPR)
2421 : 1015615 : ret = encode_tree_to_bitpos (cst, val, info->bitsize, pos_in_buffer,
2422 : 1015615 : buf_size);
2423 : 1178122 : unsigned char *m = mask + (pos_in_buffer / BITS_PER_UNIT);
2424 : 1178122 : if (BYTES_BIG_ENDIAN)
2425 : : clear_bit_region_be (m, (BITS_PER_UNIT - 1
2426 : : - (pos_in_buffer % BITS_PER_UNIT)),
2427 : : info->bitsize);
2428 : : else
2429 : 1178122 : clear_bit_region (m, pos_in_buffer % BITS_PER_UNIT, info->bitsize);
2430 : 1178122 : if (cst && dump_file && (dump_flags & TDF_DETAILS))
2431 : : {
2432 : 230 : if (ret)
2433 : : {
2434 : 230 : fputs ("After writing ", dump_file);
2435 : 230 : print_generic_expr (dump_file, cst, TDF_NONE);
2436 : 230 : fprintf (dump_file, " of size " HOST_WIDE_INT_PRINT_DEC
2437 : : " at position %d\n", info->bitsize, pos_in_buffer);
2438 : 230 : fputs (" the merged value contains ", dump_file);
2439 : 230 : dump_char_array (dump_file, val, buf_size);
2440 : 230 : fputs (" the merged mask contains ", dump_file);
2441 : 230 : dump_char_array (dump_file, mask, buf_size);
2442 : 230 : if (bit_insertion)
2443 : 0 : fputs (" bit insertion is required\n", dump_file);
2444 : 230 : if (string_concatenation)
2445 : 0 : fputs (" string concatenation is required\n", dump_file);
2446 : : }
2447 : : else
2448 : 0 : fprintf (dump_file, "Failed to merge stores\n");
2449 : : }
2450 : 1178122 : if (!ret)
2451 : : return false;
2452 : : }
2453 : 407529 : stores.qsort (sort_by_bitpos);
2454 : : return true;
2455 : : }
2456 : :
2457 : : /* Structure describing the store chain. */
2458 : :
2459 : : class imm_store_chain_info
2460 : : {
2461 : : public:
2462 : : /* Doubly-linked list that imposes an order on chain processing.
2463 : : PNXP (prev's next pointer) points to the head of a list, or to
2464 : : the next field in the previous chain in the list.
2465 : : See pass_store_merging::m_stores_head for more rationale. */
2466 : : imm_store_chain_info *next, **pnxp;
2467 : : tree base_addr;
2468 : : auto_vec<store_immediate_info *> m_store_info;
2469 : : auto_vec<merged_store_group *> m_merged_store_groups;
2470 : :
2471 : 1791458 : imm_store_chain_info (imm_store_chain_info *&inspt, tree b_a)
2472 : 1791458 : : next (inspt), pnxp (&inspt), base_addr (b_a)
2473 : : {
2474 : 1791458 : inspt = this;
2475 : 1791458 : if (next)
2476 : : {
2477 : 598737 : gcc_checking_assert (pnxp == next->pnxp);
2478 : 598737 : next->pnxp = &next;
2479 : : }
2480 : 1791458 : }
2481 : 1791458 : ~imm_store_chain_info ()
2482 : : {
2483 : 1791458 : *pnxp = next;
2484 : 1791458 : if (next)
2485 : : {
2486 : 574206 : gcc_checking_assert (&next == next->pnxp);
2487 : 574206 : next->pnxp = pnxp;
2488 : : }
2489 : 1791458 : }
2490 : : bool terminate_and_process_chain ();
2491 : : bool try_coalesce_bswap (merged_store_group *, unsigned int, unsigned int,
2492 : : unsigned int);
2493 : : bool coalesce_immediate_stores ();
2494 : : bool output_merged_store (merged_store_group *);
2495 : : bool output_merged_stores ();
2496 : : };
2497 : :
2498 : : const pass_data pass_data_tree_store_merging = {
2499 : : GIMPLE_PASS, /* type */
2500 : : "store-merging", /* name */
2501 : : OPTGROUP_NONE, /* optinfo_flags */
2502 : : TV_GIMPLE_STORE_MERGING, /* tv_id */
2503 : : PROP_ssa, /* properties_required */
2504 : : 0, /* properties_provided */
2505 : : 0, /* properties_destroyed */
2506 : : 0, /* todo_flags_start */
2507 : : TODO_update_ssa, /* todo_flags_finish */
2508 : : };
2509 : :
2510 : : class pass_store_merging : public gimple_opt_pass
2511 : : {
2512 : : public:
2513 : 280455 : pass_store_merging (gcc::context *ctxt)
2514 : 560910 : : gimple_opt_pass (pass_data_tree_store_merging, ctxt), m_stores_head (),
2515 : 280455 : m_n_chains (0), m_n_stores (0)
2516 : : {
2517 : 280455 : }
2518 : :
2519 : : /* Pass not supported for PDP-endian, nor for insane hosts or
2520 : : target character sizes where native_{encode,interpret}_expr
2521 : : doesn't work properly. */
2522 : : bool
2523 : 972089 : gate (function *) final override
2524 : : {
2525 : 972089 : return flag_store_merging
2526 : : && BYTES_BIG_ENDIAN == WORDS_BIG_ENDIAN
2527 : : && CHAR_BIT == 8
2528 : 972089 : && BITS_PER_UNIT == 8;
2529 : : }
2530 : :
2531 : : unsigned int execute (function *) final override;
2532 : :
2533 : : private:
2534 : : hash_map<tree_operand_hash, class imm_store_chain_info *> m_stores;
2535 : :
2536 : : /* Form a doubly-linked stack of the elements of m_stores, so that
2537 : : we can iterate over them in a predictable way. Using this order
2538 : : avoids extraneous differences in the compiler output just because
2539 : : of tree pointer variations (e.g. different chains end up in
2540 : : different positions of m_stores, so they are handled in different
2541 : : orders, so they allocate or release SSA names in different
2542 : : orders, and when they get reused, subsequent passes end up
2543 : : getting different SSA names, which may ultimately change
2544 : : decisions when going out of SSA). */
2545 : : imm_store_chain_info *m_stores_head;
2546 : :
2547 : : /* The number of store chains currently tracked. */
2548 : : unsigned m_n_chains;
2549 : : /* The number of stores currently tracked. */
2550 : : unsigned m_n_stores;
2551 : :
2552 : : bool process_store (gimple *);
2553 : : bool terminate_and_process_chain (imm_store_chain_info *);
2554 : : bool terminate_all_aliasing_chains (imm_store_chain_info **, gimple *);
2555 : : bool terminate_and_process_all_chains ();
2556 : : }; // class pass_store_merging
2557 : :
2558 : : /* Terminate and process all recorded chains. Return true if any changes
2559 : : were made. */
2560 : :
2561 : : bool
2562 : 1061615 : pass_store_merging::terminate_and_process_all_chains ()
2563 : : {
2564 : 1061615 : bool ret = false;
2565 : 1890960 : while (m_stores_head)
2566 : 829345 : ret |= terminate_and_process_chain (m_stores_head);
2567 : 1061615 : gcc_assert (m_stores.is_empty ());
2568 : 1061615 : return ret;
2569 : : }
2570 : :
2571 : : /* Terminate all chains that are affected by the statement STMT.
2572 : : CHAIN_INFO is the chain we should ignore from the checks if
2573 : : non-NULL. Return true if any changes were made. */
2574 : :
2575 : : bool
2576 : 9298475 : pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
2577 : : **chain_info,
2578 : : gimple *stmt)
2579 : : {
2580 : 9298475 : bool ret = false;
2581 : :
2582 : : /* If the statement doesn't touch memory it can't alias. */
2583 : 18166183 : if (!gimple_vuse (stmt))
2584 : : return false;
2585 : :
2586 : 7389336 : tree store_lhs = gimple_store_p (stmt) ? gimple_get_lhs (stmt) : NULL_TREE;
2587 : 7389336 : ao_ref store_lhs_ref;
2588 : 7389336 : ao_ref_init (&store_lhs_ref, store_lhs);
2589 : 7389336 : for (imm_store_chain_info *next = m_stores_head, *cur = next; cur; cur = next)
2590 : : {
2591 : 7697038 : next = cur->next;
2592 : :
2593 : : /* We already checked all the stores in chain_info and terminated the
2594 : : chain if necessary. Skip it here. */
2595 : 7697038 : if (chain_info && *chain_info == cur)
2596 : 1082116 : continue;
2597 : :
2598 : : store_immediate_info *info;
2599 : : unsigned int i;
2600 : 31106861 : FOR_EACH_VEC_ELT (cur->m_store_info, i, info)
2601 : : {
2602 : 10364689 : tree lhs = gimple_assign_lhs (info->stmt);
2603 : 10364689 : ao_ref lhs_ref;
2604 : 10364689 : ao_ref_init (&lhs_ref, lhs);
2605 : 10364689 : if (ref_maybe_used_by_stmt_p (stmt, &lhs_ref)
2606 : 9604948 : || stmt_may_clobber_ref_p_1 (stmt, &lhs_ref)
2607 : 19800487 : || (store_lhs && refs_may_alias_p_1 (&store_lhs_ref,
2608 : : &lhs_ref, false)))
2609 : : {
2610 : 959124 : if (dump_file && (dump_flags & TDF_DETAILS))
2611 : : {
2612 : 26 : fprintf (dump_file, "stmt causes chain termination:\n");
2613 : 26 : print_gimple_stmt (dump_file, stmt, 0);
2614 : : }
2615 : 959124 : ret |= terminate_and_process_chain (cur);
2616 : 959124 : break;
2617 : : }
2618 : : }
2619 : : }
2620 : :
2621 : : return ret;
2622 : : }
2623 : :
2624 : : /* Helper function. Terminate the recorded chain storing to base object
2625 : : BASE. Return true if the merging and output was successful. The m_stores
2626 : : entry is removed after the processing in any case. */
2627 : :
2628 : : bool
2629 : 1791458 : pass_store_merging::terminate_and_process_chain (imm_store_chain_info *chain_info)
2630 : : {
2631 : 1791458 : m_n_stores -= chain_info->m_store_info.length ();
2632 : 1791458 : m_n_chains--;
2633 : 1791458 : bool ret = chain_info->terminate_and_process_chain ();
2634 : 1791458 : m_stores.remove (chain_info->base_addr);
2635 : 1791458 : delete chain_info;
2636 : 1791458 : return ret;
2637 : : }
2638 : :
2639 : : /* Return true if stmts in between FIRST (inclusive) and LAST (exclusive)
2640 : : may clobber REF. FIRST and LAST must have non-NULL vdef. We want to
2641 : : be able to sink load of REF across stores between FIRST and LAST, up
2642 : : to right before LAST. */
2643 : :
2644 : : bool
2645 : 25853 : stmts_may_clobber_ref_p (gimple *first, gimple *last, tree ref)
2646 : : {
2647 : 25853 : ao_ref r;
2648 : 25853 : ao_ref_init (&r, ref);
2649 : 25853 : unsigned int count = 0;
2650 : 25853 : tree vop = gimple_vdef (last);
2651 : 25853 : gimple *stmt;
2652 : :
2653 : : /* Return true conservatively if the basic blocks are different. */
2654 : 25853 : if (gimple_bb (first) != gimple_bb (last))
2655 : : return true;
2656 : :
2657 : 64287 : do
2658 : : {
2659 : 64287 : stmt = SSA_NAME_DEF_STMT (vop);
2660 : 64287 : if (stmt_may_clobber_ref_p_1 (stmt, &r))
2661 : : return true;
2662 : 63828 : if (gimple_store_p (stmt)
2663 : 63828 : && refs_anti_dependent_p (ref, gimple_get_lhs (stmt)))
2664 : : return true;
2665 : : /* Avoid quadratic compile time by bounding the number of checks
2666 : : we perform. */
2667 : 63604 : if (++count > MAX_STORE_ALIAS_CHECKS)
2668 : : return true;
2669 : 63604 : vop = gimple_vuse (stmt);
2670 : : }
2671 : 63604 : while (stmt != first);
2672 : :
2673 : : return false;
2674 : : }
2675 : :
2676 : : /* Return true if INFO->ops[IDX] is mergeable with the
2677 : : corresponding loads already in MERGED_STORE group.
2678 : : BASE_ADDR is the base address of the whole store group. */
2679 : :
2680 : : bool
2681 : 108329 : compatible_load_p (merged_store_group *merged_store,
2682 : : store_immediate_info *info,
2683 : : tree base_addr, int idx)
2684 : : {
2685 : 108329 : store_immediate_info *infof = merged_store->stores[0];
2686 : 108329 : if (!info->ops[idx].base_addr
2687 : 108329 : || maybe_ne (info->ops[idx].bitpos - infof->ops[idx].bitpos,
2688 : 108329 : info->bitpos - infof->bitpos)
2689 : 202809 : || !operand_equal_p (info->ops[idx].base_addr,
2690 : 94480 : infof->ops[idx].base_addr, 0))
2691 : 14882 : return false;
2692 : :
2693 : 93447 : store_immediate_info *infol = merged_store->stores.last ();
2694 : 93447 : tree load_vuse = gimple_vuse (info->ops[idx].stmt);
2695 : : /* In this case all vuses should be the same, e.g.
2696 : : _1 = s.a; _2 = s.b; _3 = _1 | 1; t.a = _3; _4 = _2 | 2; t.b = _4;
2697 : : or
2698 : : _1 = s.a; _2 = s.b; t.a = _1; t.b = _2;
2699 : : and we can emit the coalesced load next to any of those loads. */
2700 : 93447 : if (gimple_vuse (infof->ops[idx].stmt) == load_vuse
2701 : 177248 : && gimple_vuse (infol->ops[idx].stmt) == load_vuse)
2702 : : return true;
2703 : :
2704 : : /* Otherwise, at least for now require that the load has the same
2705 : : vuse as the store. See following examples. */
2706 : 19292 : if (gimple_vuse (info->stmt) != load_vuse)
2707 : : return false;
2708 : :
2709 : 16222 : if (gimple_vuse (infof->stmt) != gimple_vuse (infof->ops[idx].stmt)
2710 : 8111 : || (infof != infol
2711 : 7344 : && gimple_vuse (infol->stmt) != gimple_vuse (infol->ops[idx].stmt)))
2712 : : return false;
2713 : :
2714 : : /* If the load is from the same location as the store, already
2715 : : the construction of the immediate chain info guarantees no intervening
2716 : : stores, so no further checks are needed. Example:
2717 : : _1 = s.a; _2 = _1 & -7; s.a = _2; _3 = s.b; _4 = _3 & -7; s.b = _4; */
2718 : 7415 : if (known_eq (info->ops[idx].bitpos, info->bitpos)
2719 : 7415 : && operand_equal_p (info->ops[idx].base_addr, base_addr, 0))
2720 : : return true;
2721 : :
2722 : : /* Otherwise, we need to punt if any of the loads can be clobbered by any
2723 : : of the stores in the group, or any other stores in between those.
2724 : : Previous calls to compatible_load_p ensured that for all the
2725 : : merged_store->stores IDX loads, no stmts starting with
2726 : : merged_store->first_stmt and ending right before merged_store->last_stmt
2727 : : clobbers those loads. */
2728 : 7312 : gimple *first = merged_store->first_stmt;
2729 : 7312 : gimple *last = merged_store->last_stmt;
2730 : : /* The stores are sorted by increasing store bitpos, so if info->stmt store
2731 : : comes before the so far first load, we'll be changing
2732 : : merged_store->first_stmt. In that case we need to give up if
2733 : : any of the earlier processed loads clobber with the stmts in the new
2734 : : range. */
2735 : 7312 : if (info->order < merged_store->first_order)
2736 : : {
2737 : 941 : for (store_immediate_info *infoc : merged_store->stores)
2738 : 272 : if (stmts_may_clobber_ref_p (info->stmt, first, infoc->ops[idx].val))
2739 : : return false;
2740 : 125 : first = info->stmt;
2741 : : }
2742 : : /* Similarly, we could change merged_store->last_stmt, so ensure
2743 : : in that case no stmts in the new range clobber any of the earlier
2744 : : processed loads. */
2745 : 7040 : else if (info->order > merged_store->last_order)
2746 : : {
2747 : 39479 : for (store_immediate_info *infoc : merged_store->stores)
2748 : 18930 : if (stmts_may_clobber_ref_p (last, info->stmt, infoc->ops[idx].val))
2749 : : return false;
2750 : 6469 : last = info->stmt;
2751 : : }
2752 : : /* And finally, we'd be adding a new load to the set, ensure it isn't
2753 : : clobbered in the new range. */
2754 : 6594 : if (stmts_may_clobber_ref_p (first, last, info->ops[idx].val))
2755 : : return false;
2756 : :
2757 : : /* Otherwise, we are looking for:
2758 : : _1 = s.a; _2 = _1 ^ 15; t.a = _2; _3 = s.b; _4 = _3 ^ 15; t.b = _4;
2759 : : or
2760 : : _1 = s.a; t.a = _1; _2 = s.b; t.b = _2; */
2761 : : return true;
2762 : : }
2763 : :
2764 : : /* Add all refs loaded to compute VAL to REFS vector. */
2765 : :
2766 : : void
2767 : 59 : gather_bswap_load_refs (vec<tree> *refs, tree val)
2768 : : {
2769 : 68 : if (TREE_CODE (val) != SSA_NAME)
2770 : : return;
2771 : :
2772 : 66 : gimple *stmt = SSA_NAME_DEF_STMT (val);
2773 : 66 : if (!is_gimple_assign (stmt))
2774 : : return;
2775 : :
2776 : 66 : if (gimple_assign_load_p (stmt))
2777 : : {
2778 : 57 : refs->safe_push (gimple_assign_rhs1 (stmt));
2779 : 57 : return;
2780 : : }
2781 : :
2782 : 9 : switch (gimple_assign_rhs_class (stmt))
2783 : : {
2784 : 2 : case GIMPLE_BINARY_RHS:
2785 : 2 : gather_bswap_load_refs (refs, gimple_assign_rhs2 (stmt));
2786 : : /* FALLTHRU */
2787 : 9 : case GIMPLE_UNARY_RHS:
2788 : 9 : gather_bswap_load_refs (refs, gimple_assign_rhs1 (stmt));
2789 : 9 : break;
2790 : 0 : default:
2791 : 0 : gcc_unreachable ();
2792 : : }
2793 : : }
2794 : :
2795 : : /* Check if there are any stores in M_STORE_INFO after index I
2796 : : (where M_STORE_INFO must be sorted by sort_by_bitpos) that overlap
2797 : : a potential group ending with END that have their order
2798 : : smaller than LAST_ORDER. ALL_INTEGER_CST_P is true if
2799 : : all the stores already merged and the one under consideration
2800 : : have rhs_code of INTEGER_CST. Return true if there are no such stores.
2801 : : Consider:
2802 : : MEM[(long long int *)p_28] = 0;
2803 : : MEM[(long long int *)p_28 + 8B] = 0;
2804 : : MEM[(long long int *)p_28 + 16B] = 0;
2805 : : MEM[(long long int *)p_28 + 24B] = 0;
2806 : : _129 = (int) _130;
2807 : : MEM[(int *)p_28 + 8B] = _129;
2808 : : MEM[(int *)p_28].a = -1;
2809 : : We already have
2810 : : MEM[(long long int *)p_28] = 0;
2811 : : MEM[(int *)p_28].a = -1;
2812 : : stmts in the current group and need to consider if it is safe to
2813 : : add MEM[(long long int *)p_28 + 8B] = 0; store into the same group.
2814 : : There is an overlap between that store and the MEM[(int *)p_28 + 8B] = _129;
2815 : : store though, so if we add the MEM[(long long int *)p_28 + 8B] = 0;
2816 : : into the group and merging of those 3 stores is successful, merged
2817 : : stmts will be emitted at the latest store from that group, i.e.
2818 : : LAST_ORDER, which is the MEM[(int *)p_28].a = -1; store.
2819 : : The MEM[(int *)p_28 + 8B] = _129; store that originally follows
2820 : : the MEM[(long long int *)p_28 + 8B] = 0; would now be before it,
2821 : : so we need to refuse merging MEM[(long long int *)p_28 + 8B] = 0;
2822 : : into the group. That way it will be its own store group and will
2823 : : not be touched. If ALL_INTEGER_CST_P and there are overlapping
2824 : : INTEGER_CST stores, those are mergeable using merge_overlapping,
2825 : : so don't return false for those.
2826 : :
2827 : : Similarly, check stores from FIRST_EARLIER (inclusive) to END_EARLIER
2828 : : (exclusive), whether they don't overlap the bitrange START to END
2829 : : and have order in between FIRST_ORDER and LAST_ORDER. This is to
2830 : : prevent merging in cases like:
2831 : : MEM <char[12]> [&b + 8B] = {};
2832 : : MEM[(short *) &b] = 5;
2833 : : _5 = *x_4(D);
2834 : : MEM <long long unsigned int> [&b + 2B] = _5;
2835 : : MEM[(char *)&b + 16B] = 88;
2836 : : MEM[(int *)&b + 20B] = 1;
2837 : : The = {} store comes in sort_by_bitpos before the = 88 store, and can't
2838 : : be merged with it, because the = _5 store overlaps these and is in between
2839 : : them in sort_by_order ordering. If it was merged, the merged store would
2840 : : go after the = _5 store and thus change behavior. */
2841 : :
2842 : : static bool
2843 : 755823 : check_no_overlap (const vec<store_immediate_info *> &m_store_info,
2844 : : unsigned int i,
2845 : : bool all_integer_cst_p, unsigned int first_order,
2846 : : unsigned int last_order, unsigned HOST_WIDE_INT start,
2847 : : unsigned HOST_WIDE_INT end, unsigned int first_earlier,
2848 : : unsigned end_earlier)
2849 : : {
2850 : 755823 : unsigned int len = m_store_info.length ();
2851 : 767985 : for (unsigned int j = first_earlier; j < end_earlier; j++)
2852 : : {
2853 : 12182 : store_immediate_info *info = m_store_info[j];
2854 : 12182 : if (info->order > first_order
2855 : 48 : && info->order < last_order
2856 : 27 : && info->bitpos + info->bitsize > start)
2857 : : return false;
2858 : : }
2859 : 887135 : for (++i; i < len; ++i)
2860 : : {
2861 : 433857 : store_immediate_info *info = m_store_info[i];
2862 : 433857 : if (info->bitpos >= end)
2863 : : break;
2864 : 131372 : if (info->order < last_order
2865 : 27785 : && (!all_integer_cst_p || info->rhs_code != INTEGER_CST))
2866 : : return false;
2867 : : }
2868 : : return true;
2869 : : }
2870 : :
2871 : : /* Return true if m_store_info[first] and at least one following store
2872 : : form a group which store try_size bitsize value which is byte swapped
2873 : : from a memory load or some value, or identity from some value.
2874 : : This uses the bswap pass APIs. */
2875 : :
2876 : : bool
2877 : 202542 : imm_store_chain_info::try_coalesce_bswap (merged_store_group *merged_store,
2878 : : unsigned int first,
2879 : : unsigned int try_size,
2880 : : unsigned int first_earlier)
2881 : : {
2882 : 202542 : unsigned int len = m_store_info.length (), last = first;
2883 : 202542 : unsigned HOST_WIDE_INT width = m_store_info[first]->bitsize;
2884 : 202542 : if (width >= try_size)
2885 : : return false;
2886 : 77158 : for (unsigned int i = first + 1; i < len; ++i)
2887 : : {
2888 : 70221 : if (m_store_info[i]->bitpos != m_store_info[first]->bitpos + width
2889 : 69771 : || m_store_info[i]->lp_nr != merged_store->lp_nr
2890 : 139992 : || m_store_info[i]->ins_stmt == NULL)
2891 : : return false;
2892 : 68434 : width += m_store_info[i]->bitsize;
2893 : 68434 : if (width >= try_size)
2894 : : {
2895 : : last = i;
2896 : : break;
2897 : : }
2898 : : }
2899 : 42396 : if (width != try_size)
2900 : : return false;
2901 : :
2902 : 35250 : bool allow_unaligned
2903 : 35250 : = !STRICT_ALIGNMENT && param_store_merging_allow_unaligned;
2904 : : /* Punt if the combined store would not be aligned and we need alignment. */
2905 : 35250 : if (!allow_unaligned)
2906 : : {
2907 : 0 : unsigned int align = merged_store->align;
2908 : 0 : unsigned HOST_WIDE_INT align_base = merged_store->align_base;
2909 : 0 : for (unsigned int i = first + 1; i <= last; ++i)
2910 : : {
2911 : 0 : unsigned int this_align;
2912 : 0 : unsigned HOST_WIDE_INT align_bitpos = 0;
2913 : 0 : get_object_alignment_1 (gimple_assign_lhs (m_store_info[i]->stmt),
2914 : : &this_align, &align_bitpos);
2915 : 0 : if (this_align > align)
2916 : : {
2917 : 0 : align = this_align;
2918 : 0 : align_base = m_store_info[i]->bitpos - align_bitpos;
2919 : : }
2920 : : }
2921 : 0 : unsigned HOST_WIDE_INT align_bitpos
2922 : 0 : = (m_store_info[first]->bitpos - align_base) & (align - 1);
2923 : 0 : if (align_bitpos)
2924 : 0 : align = least_bit_hwi (align_bitpos);
2925 : 0 : if (align < try_size)
2926 : : return false;
2927 : : }
2928 : :
2929 : 35250 : tree type;
2930 : 35250 : switch (try_size)
2931 : : {
2932 : 5862 : case 16: type = uint16_type_node; break;
2933 : 4796 : case 32: type = uint32_type_node; break;
2934 : 24592 : case 64: type = uint64_type_node; break;
2935 : 0 : default: gcc_unreachable ();
2936 : : }
2937 : 35250 : struct symbolic_number n;
2938 : 35250 : gimple *ins_stmt = NULL;
2939 : 35250 : int vuse_store = -1;
2940 : 35250 : unsigned int first_order = merged_store->first_order;
2941 : 35250 : unsigned int last_order = merged_store->last_order;
2942 : 35250 : gimple *first_stmt = merged_store->first_stmt;
2943 : 35250 : gimple *last_stmt = merged_store->last_stmt;
2944 : 35250 : unsigned HOST_WIDE_INT end = merged_store->start + merged_store->width;
2945 : 35250 : store_immediate_info *infof = m_store_info[first];
2946 : :
2947 : 95351 : for (unsigned int i = first; i <= last; ++i)
2948 : : {
2949 : 75891 : store_immediate_info *info = m_store_info[i];
2950 : 75891 : struct symbolic_number this_n = info->n;
2951 : 75891 : this_n.type = type;
2952 : 75891 : if (!this_n.base_addr)
2953 : 11675 : this_n.range = try_size / BITS_PER_UNIT;
2954 : : else
2955 : : /* Update vuse in case it has changed by output_merged_stores. */
2956 : 128432 : this_n.vuse = gimple_vuse (info->ins_stmt);
2957 : 75891 : unsigned int bitpos = info->bitpos - infof->bitpos;
2958 : 75891 : if (!do_shift_rotate (LSHIFT_EXPR, &this_n,
2959 : : BYTES_BIG_ENDIAN
2960 : : ? try_size - info->bitsize - bitpos
2961 : : : bitpos))
2962 : 15790 : return false;
2963 : 75891 : if (this_n.base_addr && vuse_store)
2964 : : {
2965 : : unsigned int j;
2966 : 99125 : for (j = first; j <= last; ++j)
2967 : 153786 : if (this_n.vuse == gimple_vuse (m_store_info[j]->stmt))
2968 : : break;
2969 : 38562 : if (j > last)
2970 : : {
2971 : 22232 : if (vuse_store == 1)
2972 : : return false;
2973 : : vuse_store = 0;
2974 : : }
2975 : : }
2976 : 75891 : if (i == first)
2977 : : {
2978 : 35250 : n = this_n;
2979 : 35250 : ins_stmt = info->ins_stmt;
2980 : : }
2981 : : else
2982 : : {
2983 : 40641 : if (n.base_addr && n.vuse != this_n.vuse)
2984 : : {
2985 : 4551 : if (vuse_store == 0)
2986 : : return false;
2987 : : vuse_store = 1;
2988 : : }
2989 : 36927 : if (info->order > last_order)
2990 : : {
2991 : 34726 : last_order = info->order;
2992 : 34726 : last_stmt = info->stmt;
2993 : : }
2994 : 2201 : else if (info->order < first_order)
2995 : : {
2996 : 2197 : first_order = info->order;
2997 : 2197 : first_stmt = info->stmt;
2998 : : }
2999 : 36927 : end = MAX (end, info->bitpos + info->bitsize);
3000 : :
3001 : 36927 : ins_stmt = perform_symbolic_merge (ins_stmt, &n, info->ins_stmt,
3002 : : &this_n, &n, BIT_IOR_EXPR);
3003 : 36927 : if (ins_stmt == NULL)
3004 : : return false;
3005 : : }
3006 : : }
3007 : :
3008 : 19460 : uint64_t cmpxchg, cmpnop;
3009 : 19460 : bool cast64_to_32;
3010 : 19460 : find_bswap_or_nop_finalize (&n, &cmpxchg, &cmpnop, &cast64_to_32);
3011 : :
3012 : : /* A complete byte swap should make the symbolic number to start with
3013 : : the largest digit in the highest order byte. Unchanged symbolic
3014 : : number indicates a read with same endianness as target architecture. */
3015 : 19460 : if (n.n != cmpnop && n.n != cmpxchg)
3016 : : return false;
3017 : :
3018 : : /* For now. */
3019 : 17339 : if (cast64_to_32)
3020 : : return false;
3021 : :
3022 : 17336 : if (n.base_addr == NULL_TREE && !is_gimple_val (n.src))
3023 : : return false;
3024 : :
3025 : 17336 : if (!check_no_overlap (m_store_info, last, false, first_order, last_order,
3026 : : merged_store->start, end, first_earlier, first))
3027 : : return false;
3028 : :
3029 : : /* Don't handle memory copy this way if normal non-bswap processing
3030 : : would handle it too. */
3031 : 17334 : if (n.n == cmpnop && (unsigned) n.n_ops == last - first + 1)
3032 : : {
3033 : : unsigned int i;
3034 : 51108 : for (i = first; i <= last; ++i)
3035 : 34317 : if (m_store_info[i]->rhs_code != MEM_REF)
3036 : : break;
3037 : 17017 : if (i == last + 1)
3038 : : return false;
3039 : : }
3040 : :
3041 : 543 : if (n.n == cmpxchg)
3042 : 317 : switch (try_size)
3043 : : {
3044 : : case 16:
3045 : : /* Will emit LROTATE_EXPR. */
3046 : : break;
3047 : 24 : case 32:
3048 : 24 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
3049 : 36 : && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing)
3050 : : break;
3051 : 12 : return false;
3052 : 47 : case 64:
3053 : 47 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
3054 : 84 : && (optab_handler (bswap_optab, DImode) != CODE_FOR_nothing
3055 : 27 : || (word_mode == SImode
3056 : 27 : && builtin_decl_explicit_p (BUILT_IN_BSWAP32)
3057 : 27 : && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing)))
3058 : : break;
3059 : 10 : return false;
3060 : 0 : default:
3061 : 0 : gcc_unreachable ();
3062 : : }
3063 : :
3064 : 521 : if (!allow_unaligned && n.base_addr)
3065 : : {
3066 : 0 : unsigned int align = get_object_alignment (n.src);
3067 : 0 : if (align < try_size)
3068 : : return false;
3069 : : }
3070 : :
3071 : : /* If each load has vuse of the corresponding store, need to verify
3072 : : the loads can be sunk right before the last store. */
3073 : 521 : if (vuse_store == 1)
3074 : : {
3075 : 24 : auto_vec<tree, 64> refs;
3076 : 81 : for (unsigned int i = first; i <= last; ++i)
3077 : 57 : gather_bswap_load_refs (&refs,
3078 : 57 : gimple_assign_rhs1 (m_store_info[i]->stmt));
3079 : :
3080 : 129 : for (tree ref : refs)
3081 : 57 : if (stmts_may_clobber_ref_p (first_stmt, last_stmt, ref))
3082 : 0 : return false;
3083 : 24 : n.vuse = NULL_TREE;
3084 : 24 : }
3085 : :
3086 : 521 : infof->n = n;
3087 : 521 : infof->ins_stmt = ins_stmt;
3088 : 2281 : for (unsigned int i = first; i <= last; ++i)
3089 : : {
3090 : 2686 : m_store_info[i]->rhs_code = n.n == cmpxchg ? LROTATE_EXPR : NOP_EXPR;
3091 : 1760 : m_store_info[i]->ops[0].base_addr = NULL_TREE;
3092 : 1760 : m_store_info[i]->ops[1].base_addr = NULL_TREE;
3093 : 1760 : if (i != first)
3094 : 1239 : merged_store->merge_into (m_store_info[i]);
3095 : : }
3096 : :
3097 : : return true;
3098 : : }
3099 : :
3100 : : /* Go through the candidate stores recorded in m_store_info and merge them
3101 : : into merged_store_group objects recorded into m_merged_store_groups
3102 : : representing the widened stores. Return true if coalescing was successful
3103 : : and the number of widened stores is fewer than the original number
3104 : : of stores. */
3105 : :
3106 : : bool
3107 : 491105 : imm_store_chain_info::coalesce_immediate_stores ()
3108 : : {
3109 : : /* Anything less can't be processed. */
3110 : 601122 : if (m_store_info.length () < 2)
3111 : : return false;
3112 : :
3113 : 491105 : if (dump_file && (dump_flags & TDF_DETAILS))
3114 : 27 : fprintf (dump_file, "Attempting to coalesce %u stores in chain\n",
3115 : : m_store_info.length ());
3116 : :
3117 : 491105 : store_immediate_info *info;
3118 : 491105 : unsigned int i, ignore = 0;
3119 : 491105 : unsigned int first_earlier = 0;
3120 : 491105 : unsigned int end_earlier = 0;
3121 : :
3122 : : /* Order the stores by the bitposition they write to. */
3123 : 491105 : m_store_info.qsort (sort_by_bitpos);
3124 : :
3125 : 491105 : info = m_store_info[0];
3126 : 491105 : merged_store_group *merged_store = new merged_store_group (info);
3127 : 491105 : if (dump_file && (dump_flags & TDF_DETAILS))
3128 : 27 : fputs ("New store group\n", dump_file);
3129 : :
3130 : 2064326 : FOR_EACH_VEC_ELT (m_store_info, i, info)
3131 : : {
3132 : 1573221 : unsigned HOST_WIDE_INT new_bitregion_start, new_bitregion_end;
3133 : :
3134 : 1573221 : if (i <= ignore)
3135 : 617859 : goto done;
3136 : :
3137 : : while (first_earlier < end_earlier
3138 : 1170619 : && (m_store_info[first_earlier]->bitpos
3139 : 223223 : + m_store_info[first_earlier]->bitsize
3140 : 223223 : <= merged_store->start))
3141 : 215257 : first_earlier++;
3142 : :
3143 : : /* First try to handle group of stores like:
3144 : : p[0] = data >> 24;
3145 : : p[1] = data >> 16;
3146 : : p[2] = data >> 8;
3147 : : p[3] = data;
3148 : : using the bswap framework. */
3149 : 955362 : if (info->bitpos == merged_store->start + merged_store->width
3150 : 561005 : && merged_store->stores.length () == 1
3151 : 310669 : && merged_store->stores[0]->ins_stmt != NULL
3152 : 103986 : && info->lp_nr == merged_store->lp_nr
3153 : 1059346 : && info->ins_stmt != NULL)
3154 : : {
3155 : : unsigned int try_size;
3156 : 269651 : for (try_size = 64; try_size >= 16; try_size >>= 1)
3157 : 202542 : if (try_coalesce_bswap (merged_store, i - 1, try_size,
3158 : : first_earlier))
3159 : : break;
3160 : :
3161 : 67630 : if (try_size >= 16)
3162 : : {
3163 : 521 : ignore = i + merged_store->stores.length () - 1;
3164 : 521 : m_merged_store_groups.safe_push (merged_store);
3165 : 1042 : if (ignore < m_store_info.length ())
3166 : : {
3167 : 195 : merged_store = new merged_store_group (m_store_info[ignore]);
3168 : 195 : end_earlier = ignore;
3169 : : }
3170 : : else
3171 : 326 : merged_store = NULL;
3172 : 521 : goto done;
3173 : : }
3174 : : }
3175 : :
3176 : 954841 : new_bitregion_start
3177 : 954841 : = MIN (merged_store->bitregion_start, info->bitregion_start);
3178 : 954841 : new_bitregion_end
3179 : 954841 : = MAX (merged_store->bitregion_end, info->bitregion_end);
3180 : :
3181 : 954841 : if (info->order >= merged_store->first_nonmergeable_order
3182 : 951009 : || (((new_bitregion_end - new_bitregion_start + 1) / BITS_PER_UNIT)
3183 : 951009 : > (unsigned) param_store_merging_max_size))
3184 : : ;
3185 : :
3186 : : /* |---store 1---|
3187 : : |---store 2---|
3188 : : Overlapping stores. */
3189 : 950913 : else if (IN_RANGE (info->bitpos, merged_store->start,
3190 : : merged_store->start + merged_store->width - 1)
3191 : : /* |---store 1---||---store 2---|
3192 : : Handle also the consecutive INTEGER_CST stores case here,
3193 : : as we have here the code to deal with overlaps. */
3194 : 950913 : || (info->bitregion_start <= merged_store->bitregion_end
3195 : 561182 : && info->rhs_code == INTEGER_CST
3196 : 423281 : && merged_store->only_constants
3197 : 399365 : && merged_store->can_be_merged_into (info)))
3198 : : {
3199 : : /* Only allow overlapping stores of constants. */
3200 : 569914 : if (info->rhs_code == INTEGER_CST
3201 : 557042 : && merged_store->only_constants
3202 : 556828 : && info->lp_nr == merged_store->lp_nr)
3203 : : {
3204 : 556811 : unsigned int first_order
3205 : 556811 : = MIN (merged_store->first_order, info->order);
3206 : 556811 : unsigned int last_order
3207 : 556811 : = MAX (merged_store->last_order, info->order);
3208 : 556811 : unsigned HOST_WIDE_INT end
3209 : 556811 : = MAX (merged_store->start + merged_store->width,
3210 : : info->bitpos + info->bitsize);
3211 : 556811 : if (check_no_overlap (m_store_info, i, true, first_order,
3212 : : last_order, merged_store->start, end,
3213 : : first_earlier, end_earlier))
3214 : : {
3215 : : /* check_no_overlap call above made sure there are no
3216 : : overlapping stores with non-INTEGER_CST rhs_code
3217 : : in between the first and last of the stores we've
3218 : : just merged. If there are any INTEGER_CST rhs_code
3219 : : stores in between, we need to merge_overlapping them
3220 : : even if in the sort_by_bitpos order there are other
3221 : : overlapping stores in between. Keep those stores as is.
3222 : : Example:
3223 : : MEM[(int *)p_28] = 0;
3224 : : MEM[(char *)p_28 + 3B] = 1;
3225 : : MEM[(char *)p_28 + 1B] = 2;
3226 : : MEM[(char *)p_28 + 2B] = MEM[(char *)p_28 + 6B];
3227 : : We can't merge the zero store with the store of two and
3228 : : not merge anything else, because the store of one is
3229 : : in the original order in between those two, but in
3230 : : store_by_bitpos order it comes after the last store that
3231 : : we can't merge with them. We can merge the first 3 stores
3232 : : and keep the last store as is though. */
3233 : 556756 : unsigned int len = m_store_info.length ();
3234 : 556756 : unsigned int try_order = last_order;
3235 : 556756 : unsigned int first_nonmergeable_order;
3236 : 556756 : unsigned int k;
3237 : 556756 : bool last_iter = false;
3238 : 556756 : int attempts = 0;
3239 : 605738 : do
3240 : : {
3241 : 605738 : unsigned int max_order = 0;
3242 : 605738 : unsigned int min_order = first_order;
3243 : 605738 : unsigned first_nonmergeable_int_order = ~0U;
3244 : 605738 : unsigned HOST_WIDE_INT this_end = end;
3245 : 605738 : k = i;
3246 : 605738 : first_nonmergeable_order = ~0U;
3247 : 839485 : for (unsigned int j = i + 1; j < len; ++j)
3248 : : {
3249 : 509767 : store_immediate_info *info2 = m_store_info[j];
3250 : 509767 : if (info2->bitpos >= this_end)
3251 : : break;
3252 : 233750 : if (info2->order < try_order)
3253 : : {
3254 : 121422 : if (info2->rhs_code != INTEGER_CST
3255 : 121419 : || info2->lp_nr != merged_store->lp_nr)
3256 : : {
3257 : : /* Normally check_no_overlap makes sure this
3258 : : doesn't happen, but if end grows below,
3259 : : then we need to process more stores than
3260 : : check_no_overlap verified. Example:
3261 : : MEM[(int *)p_5] = 0;
3262 : : MEM[(short *)p_5 + 3B] = 1;
3263 : : MEM[(char *)p_5 + 4B] = _9;
3264 : : MEM[(char *)p_5 + 2B] = 2; */
3265 : : k = 0;
3266 : : break;
3267 : : }
3268 : 121419 : k = j;
3269 : 121419 : min_order = MIN (min_order, info2->order);
3270 : 121419 : this_end = MAX (this_end,
3271 : : info2->bitpos + info2->bitsize);
3272 : : }
3273 : 112328 : else if (info2->rhs_code == INTEGER_CST
3274 : 95466 : && info2->lp_nr == merged_store->lp_nr
3275 : 95455 : && !last_iter)
3276 : : {
3277 : 95455 : max_order = MAX (max_order, info2->order + 1);
3278 : 95455 : first_nonmergeable_int_order
3279 : 95455 : = MIN (first_nonmergeable_int_order,
3280 : : info2->order);
3281 : : }
3282 : : else
3283 : 16873 : first_nonmergeable_order
3284 : 16873 : = MIN (first_nonmergeable_order, info2->order);
3285 : : }
3286 : 605738 : if (k > i
3287 : 605738 : && !check_no_overlap (m_store_info, len - 1, true,
3288 : : min_order, try_order,
3289 : : merged_store->start, this_end,
3290 : : first_earlier, end_earlier))
3291 : : k = 0;
3292 : 605738 : if (k == 0)
3293 : : {
3294 : 3 : if (last_order == try_order)
3295 : : break;
3296 : : /* If this failed, but only because we grew
3297 : : try_order, retry with the last working one,
3298 : : so that we merge at least something. */
3299 : 0 : try_order = last_order;
3300 : 0 : last_iter = true;
3301 : 0 : continue;
3302 : : }
3303 : 605735 : last_order = try_order;
3304 : : /* Retry with a larger try_order to see if we could
3305 : : merge some further INTEGER_CST stores. */
3306 : 605735 : if (max_order
3307 : 605735 : && (first_nonmergeable_int_order
3308 : 605735 : < first_nonmergeable_order))
3309 : : {
3310 : 48983 : try_order = MIN (max_order,
3311 : : first_nonmergeable_order);
3312 : 48983 : try_order
3313 : 48983 : = MIN (try_order,
3314 : : merged_store->first_nonmergeable_order);
3315 : 48983 : if (try_order > last_order && ++attempts < 16)
3316 : 48982 : continue;
3317 : : }
3318 : 556753 : first_nonmergeable_order
3319 : 556753 : = MIN (first_nonmergeable_order,
3320 : : first_nonmergeable_int_order);
3321 : : end = this_end;
3322 : : break;
3323 : : }
3324 : : while (1);
3325 : :
3326 : 556756 : if (k != 0)
3327 : : {
3328 : 556753 : merged_store->merge_overlapping (info);
3329 : :
3330 : 556753 : merged_store->first_nonmergeable_order
3331 : 556753 : = MIN (merged_store->first_nonmergeable_order,
3332 : : first_nonmergeable_order);
3333 : :
3334 : 682594 : for (unsigned int j = i + 1; j <= k; j++)
3335 : : {
3336 : 125841 : store_immediate_info *info2 = m_store_info[j];
3337 : 125841 : gcc_assert (info2->bitpos < end);
3338 : 125841 : if (info2->order < last_order)
3339 : : {
3340 : 120619 : gcc_assert (info2->rhs_code == INTEGER_CST);
3341 : 120619 : if (info != info2)
3342 : 120619 : merged_store->merge_overlapping (info2);
3343 : : }
3344 : : /* Other stores are kept and not merged in any
3345 : : way. */
3346 : : }
3347 : 556753 : ignore = k;
3348 : 556753 : goto done;
3349 : : }
3350 : : }
3351 : : }
3352 : : }
3353 : : /* |---store 1---||---store 2---|
3354 : : This store is consecutive to the previous one.
3355 : : Merge it into the current store group. There can be gaps in between
3356 : : the stores, but there can't be gaps in between bitregions. */
3357 : 380999 : else if (info->bitregion_start <= merged_store->bitregion_end
3358 : 380999 : && merged_store->can_be_merged_into (info))
3359 : : {
3360 : 111065 : store_immediate_info *infof = merged_store->stores[0];
3361 : :
3362 : : /* All the rhs_code ops that take 2 operands are commutative,
3363 : : swap the operands if it could make the operands compatible. */
3364 : 111065 : if (infof->ops[0].base_addr
3365 : 106713 : && infof->ops[1].base_addr
3366 : 1621 : && info->ops[0].base_addr
3367 : 1621 : && info->ops[1].base_addr
3368 : 1621 : && known_eq (info->ops[1].bitpos - infof->ops[0].bitpos,
3369 : : info->bitpos - infof->bitpos)
3370 : 111734 : && operand_equal_p (info->ops[1].base_addr,
3371 : : infof->ops[0].base_addr, 0))
3372 : : {
3373 : 494 : std::swap (info->ops[0], info->ops[1]);
3374 : 494 : info->ops_swapped_p = true;
3375 : : }
3376 : 111065 : if (check_no_overlap (m_store_info, i, false,
3377 : 111065 : MIN (merged_store->first_order, info->order),
3378 : 111065 : MAX (merged_store->last_order, info->order),
3379 : : merged_store->start,
3380 : 111065 : MAX (merged_store->start + merged_store->width,
3381 : : info->bitpos + info->bitsize),
3382 : : first_earlier, end_earlier))
3383 : : {
3384 : : /* Turn MEM_REF into BIT_INSERT_EXPR for bit-field stores. */
3385 : 111062 : if (info->rhs_code == MEM_REF && infof->rhs_code != MEM_REF)
3386 : : {
3387 : 612 : info->rhs_code = BIT_INSERT_EXPR;
3388 : 612 : info->ops[0].val = gimple_assign_rhs1 (info->stmt);
3389 : 612 : info->ops[0].base_addr = NULL_TREE;
3390 : : }
3391 : 110450 : else if (infof->rhs_code == MEM_REF && info->rhs_code != MEM_REF)
3392 : : {
3393 : 8 : for (store_immediate_info *infoj : merged_store->stores)
3394 : : {
3395 : 2 : infoj->rhs_code = BIT_INSERT_EXPR;
3396 : 2 : infoj->ops[0].val = gimple_assign_rhs1 (infoj->stmt);
3397 : 2 : infoj->ops[0].base_addr = NULL_TREE;
3398 : : }
3399 : 2 : merged_store->bit_insertion = true;
3400 : : }
3401 : 111062 : if ((infof->ops[0].base_addr
3402 : 106708 : ? compatible_load_p (merged_store, info, base_addr, 0)
3403 : 4354 : : !info->ops[0].base_addr)
3404 : 223745 : && (infof->ops[1].base_addr
3405 : 1621 : ? compatible_load_p (merged_store, info, base_addr, 1)
3406 : 91601 : : !info->ops[1].base_addr))
3407 : : {
3408 : 93221 : merged_store->merge_into (info);
3409 : 93221 : goto done;
3410 : : }
3411 : : }
3412 : : }
3413 : :
3414 : : /* |---store 1---| <gap> |---store 2---|.
3415 : : Gap between stores or the rhs not compatible. Start a new group. */
3416 : :
3417 : : /* Try to apply all the stores recorded for the group to determine
3418 : : the bitpattern they write and discard it if that fails.
3419 : : This will also reject single-store groups. */
3420 : 304867 : if (merged_store->apply_stores ())
3421 : 51441 : m_merged_store_groups.safe_push (merged_store);
3422 : : else
3423 : 253426 : delete merged_store;
3424 : :
3425 : 304867 : merged_store = new merged_store_group (info);
3426 : 304867 : end_earlier = i;
3427 : 304867 : if (dump_file && (dump_flags & TDF_DETAILS))
3428 : 1 : fputs ("New store group\n", dump_file);
3429 : :
3430 : 1573221 : done:
3431 : 1573221 : if (dump_file && (dump_flags & TDF_DETAILS))
3432 : : {
3433 : 235 : fprintf (dump_file, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
3434 : : " bitpos:" HOST_WIDE_INT_PRINT_DEC " val:",
3435 : : i, info->bitsize, info->bitpos);
3436 : 235 : print_generic_expr (dump_file, gimple_assign_rhs1 (info->stmt));
3437 : 235 : fputc ('\n', dump_file);
3438 : : }
3439 : : }
3440 : :
3441 : : /* Record or discard the last store group. */
3442 : 491105 : if (merged_store)
3443 : : {
3444 : 490779 : if (merged_store->apply_stores ())
3445 : 356088 : m_merged_store_groups.safe_push (merged_store);
3446 : : else
3447 : 134691 : delete merged_store;
3448 : : }
3449 : :
3450 : 1363298 : gcc_assert (m_merged_store_groups.length () <= m_store_info.length ());
3451 : :
3452 : 491105 : bool success
3453 : 491105 : = !m_merged_store_groups.is_empty ()
3454 : 381088 : && m_merged_store_groups.length () < m_store_info.length ();
3455 : :
3456 : 381088 : if (success && dump_file)
3457 : 100 : fprintf (dump_file, "Coalescing successful!\nMerged into %u stores\n",
3458 : : m_merged_store_groups.length ());
3459 : :
3460 : : return success;
3461 : : }
3462 : :
3463 : : /* Return the type to use for the merged stores or loads described by STMTS.
3464 : : This is needed to get the alias sets right. If IS_LOAD, look for rhs,
3465 : : otherwise lhs. Additionally set *CLIQUEP and *BASEP to MR_DEPENDENCE_*
3466 : : of the MEM_REFs if any. */
3467 : :
3468 : : static tree
3469 : 72846 : get_alias_type_for_stmts (vec<gimple *> &stmts, bool is_load,
3470 : : unsigned short *cliquep, unsigned short *basep)
3471 : : {
3472 : 72846 : gimple *stmt;
3473 : 72846 : unsigned int i;
3474 : 72846 : tree type = NULL_TREE;
3475 : 72846 : tree ret = NULL_TREE;
3476 : 72846 : *cliquep = 0;
3477 : 72846 : *basep = 0;
3478 : :
3479 : 249521 : FOR_EACH_VEC_ELT (stmts, i, stmt)
3480 : : {
3481 : 176675 : tree ref = is_load ? gimple_assign_rhs1 (stmt)
3482 : 173431 : : gimple_assign_lhs (stmt);
3483 : 176675 : tree type1 = reference_alias_ptr_type (ref);
3484 : 176675 : tree base = get_base_address (ref);
3485 : :
3486 : 176675 : if (i == 0)
3487 : : {
3488 : 72846 : if (TREE_CODE (base) == MEM_REF)
3489 : : {
3490 : 9839 : *cliquep = MR_DEPENDENCE_CLIQUE (base);
3491 : 9839 : *basep = MR_DEPENDENCE_BASE (base);
3492 : : }
3493 : 72846 : ret = type = type1;
3494 : 72846 : continue;
3495 : : }
3496 : 103829 : if (!alias_ptr_types_compatible_p (type, type1))
3497 : 73166 : ret = ptr_type_node;
3498 : 103829 : if (TREE_CODE (base) != MEM_REF
3499 : 18373 : || *cliquep != MR_DEPENDENCE_CLIQUE (base)
3500 : 114303 : || *basep != MR_DEPENDENCE_BASE (base))
3501 : : {
3502 : 93355 : *cliquep = 0;
3503 : 93355 : *basep = 0;
3504 : : }
3505 : : }
3506 : 72846 : return ret;
3507 : : }
3508 : :
3509 : : /* Return the location_t information we can find among the statements
3510 : : in STMTS. */
3511 : :
3512 : : static location_t
3513 : 72887 : get_location_for_stmts (vec<gimple *> &stmts)
3514 : : {
3515 : 224334 : for (gimple *stmt : stmts)
3516 : 75993 : if (gimple_has_location (stmt))
3517 : 70320 : return gimple_location (stmt);
3518 : :
3519 : : return UNKNOWN_LOCATION;
3520 : : }
3521 : :
3522 : : /* Used to decribe a store resulting from splitting a wide store in smaller
3523 : : regularly-sized stores in split_group. */
3524 : :
3525 : 795000 : class split_store
3526 : : {
3527 : : public:
3528 : : unsigned HOST_WIDE_INT bytepos;
3529 : : unsigned HOST_WIDE_INT size;
3530 : : unsigned HOST_WIDE_INT align;
3531 : : auto_vec<store_immediate_info *> orig_stores;
3532 : : /* True if there is a single orig stmt covering the whole split store. */
3533 : : bool orig;
3534 : : split_store (unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
3535 : : unsigned HOST_WIDE_INT);
3536 : : };
3537 : :
3538 : : /* Simple constructor. */
3539 : :
3540 : 795000 : split_store::split_store (unsigned HOST_WIDE_INT bp,
3541 : : unsigned HOST_WIDE_INT sz,
3542 : 795000 : unsigned HOST_WIDE_INT al)
3543 : 795000 : : bytepos (bp), size (sz), align (al), orig (false)
3544 : : {
3545 : 795000 : orig_stores.create (0);
3546 : 0 : }
3547 : :
3548 : : /* Record all stores in GROUP that write to the region starting at BITPOS and
3549 : : is of size BITSIZE. Record infos for such statements in STORES if
3550 : : non-NULL. The stores in GROUP must be sorted by bitposition. Return INFO
3551 : : if there is exactly one original store in the range (in that case ignore
3552 : : clobber stmts, unless there are only clobber stmts). */
3553 : :
3554 : : static store_immediate_info *
3555 : 7147296 : find_constituent_stores (class merged_store_group *group,
3556 : : vec<store_immediate_info *> *stores,
3557 : : unsigned int *first,
3558 : : unsigned HOST_WIDE_INT bitpos,
3559 : : unsigned HOST_WIDE_INT bitsize)
3560 : : {
3561 : 7147296 : store_immediate_info *info, *ret = NULL;
3562 : 7147296 : unsigned int i;
3563 : 7147296 : bool second = false;
3564 : 7147296 : bool update_first = true;
3565 : 7147296 : unsigned HOST_WIDE_INT end = bitpos + bitsize;
3566 : 20494075 : for (i = *first; group->stores.iterate (i, &info); ++i)
3567 : : {
3568 : 16963013 : unsigned HOST_WIDE_INT stmt_start = info->bitpos;
3569 : 16963013 : unsigned HOST_WIDE_INT stmt_end = stmt_start + info->bitsize;
3570 : 16963013 : if (stmt_end <= bitpos)
3571 : : {
3572 : : /* BITPOS passed to this function never decreases from within the
3573 : : same split_group call, so optimize and don't scan info records
3574 : : which are known to end before or at BITPOS next time.
3575 : : Only do it if all stores before this one also pass this. */
3576 : 5439377 : if (update_first)
3577 : 1745852 : *first = i + 1;
3578 : 5439377 : continue;
3579 : : }
3580 : : else
3581 : 11523636 : update_first = false;
3582 : :
3583 : : /* The stores in GROUP are ordered by bitposition so if we're past
3584 : : the region for this group return early. */
3585 : 11523636 : if (stmt_start >= end)
3586 : 3338071 : return ret;
3587 : :
3588 : 8185565 : if (gimple_clobber_p (info->stmt))
3589 : : {
3590 : 2216118 : if (stores)
3591 : 117243 : stores->safe_push (info);
3592 : 2216118 : if (ret == NULL)
3593 : 1805636 : ret = info;
3594 : 2216118 : continue;
3595 : : }
3596 : 5969447 : if (stores)
3597 : : {
3598 : 888499 : stores->safe_push (info);
3599 : 888499 : if (ret && !gimple_clobber_p (ret->stmt))
3600 : : {
3601 : : ret = NULL;
3602 : : second = true;
3603 : : }
3604 : : }
3605 : 5080948 : else if (ret && !gimple_clobber_p (ret->stmt))
3606 : : return NULL;
3607 : 5691284 : if (!second)
3608 : 5596349 : ret = info;
3609 : : }
3610 : : return ret;
3611 : : }
3612 : :
3613 : : /* Return how many SSA_NAMEs used to compute value to store in the INFO
3614 : : store have multiple uses. If any SSA_NAME has multiple uses, also
3615 : : count statements needed to compute it. */
3616 : :
3617 : : static unsigned
3618 : 1013233 : count_multiple_uses (store_immediate_info *info)
3619 : : {
3620 : 1013233 : gimple *stmt = info->stmt;
3621 : 1013233 : unsigned ret = 0;
3622 : 1013233 : switch (info->rhs_code)
3623 : : {
3624 : : case INTEGER_CST:
3625 : : case STRING_CST:
3626 : : return 0;
3627 : 6162 : case BIT_AND_EXPR:
3628 : 6162 : case BIT_IOR_EXPR:
3629 : 6162 : case BIT_XOR_EXPR:
3630 : 6162 : if (info->bit_not_p)
3631 : : {
3632 : 65 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3633 : : ret = 1; /* Fall through below to return
3634 : : the BIT_NOT_EXPR stmt and then
3635 : : BIT_{AND,IOR,XOR}_EXPR and anything it
3636 : : uses. */
3637 : : else
3638 : : /* stmt is after this the BIT_NOT_EXPR. */
3639 : 65 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3640 : : }
3641 : 6162 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3642 : : {
3643 : 10 : ret += 1 + info->ops[0].bit_not_p;
3644 : 10 : if (info->ops[1].base_addr)
3645 : 10 : ret += 1 + info->ops[1].bit_not_p;
3646 : 10 : return ret + 1;
3647 : : }
3648 : 6152 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3649 : : /* stmt is now the BIT_*_EXPR. */
3650 : 6152 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3651 : 4664 : ret += 1 + info->ops[info->ops_swapped_p].bit_not_p;
3652 : 1488 : else if (info->ops[info->ops_swapped_p].bit_not_p)
3653 : : {
3654 : 171 : gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3655 : 171 : if (!has_single_use (gimple_assign_rhs1 (stmt2)))
3656 : 0 : ++ret;
3657 : : }
3658 : 6152 : if (info->ops[1].base_addr == NULL_TREE)
3659 : : {
3660 : 316 : gcc_checking_assert (!info->ops_swapped_p);
3661 : : return ret;
3662 : : }
3663 : 5836 : if (!has_single_use (gimple_assign_rhs2 (stmt)))
3664 : 852 : ret += 1 + info->ops[1 - info->ops_swapped_p].bit_not_p;
3665 : 4984 : else if (info->ops[1 - info->ops_swapped_p].bit_not_p)
3666 : : {
3667 : 19 : gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
3668 : 19 : if (!has_single_use (gimple_assign_rhs1 (stmt2)))
3669 : 0 : ++ret;
3670 : : }
3671 : : return ret;
3672 : 217894 : case MEM_REF:
3673 : 217894 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3674 : 112345 : return 1 + info->ops[0].bit_not_p;
3675 : 105549 : else if (info->ops[0].bit_not_p)
3676 : : {
3677 : 90 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3678 : 90 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3679 : : return 1;
3680 : : }
3681 : : return 0;
3682 : 4106 : case BIT_INSERT_EXPR:
3683 : 4106 : return has_single_use (gimple_assign_rhs1 (stmt)) ? 0 : 1;
3684 : 0 : default:
3685 : 0 : gcc_unreachable ();
3686 : : }
3687 : : }
3688 : :
3689 : : /* Split a merged store described by GROUP by populating the SPLIT_STORES
3690 : : vector (if non-NULL) with split_store structs describing the byte offset
3691 : : (from the base), the bit size and alignment of each store as well as the
3692 : : original statements involved in each such split group.
3693 : : This is to separate the splitting strategy from the statement
3694 : : building/emission/linking done in output_merged_store.
3695 : : Return number of new stores.
3696 : : If ALLOW_UNALIGNED_STORE is false, then all stores must be aligned.
3697 : : If ALLOW_UNALIGNED_LOAD is false, then all loads must be aligned.
3698 : : BZERO_FIRST may be true only when the first store covers the whole group
3699 : : and clears it; if BZERO_FIRST is true, keep that first store in the set
3700 : : unmodified and emit further stores for the overrides only.
3701 : : If SPLIT_STORES is NULL, it is just a dry run to count number of
3702 : : new stores. */
3703 : :
3704 : : static unsigned int
3705 : 905478 : split_group (merged_store_group *group, bool allow_unaligned_store,
3706 : : bool allow_unaligned_load, bool bzero_first,
3707 : : vec<split_store *> *split_stores,
3708 : : unsigned *total_orig,
3709 : : unsigned *total_new)
3710 : : {
3711 : 905478 : unsigned HOST_WIDE_INT pos = group->bitregion_start;
3712 : 905478 : unsigned HOST_WIDE_INT size = group->bitregion_end - pos;
3713 : 905478 : unsigned HOST_WIDE_INT bytepos = pos / BITS_PER_UNIT;
3714 : 905478 : unsigned HOST_WIDE_INT group_align = group->align;
3715 : 905478 : unsigned HOST_WIDE_INT align_base = group->align_base;
3716 : 905478 : unsigned HOST_WIDE_INT group_load_align = group_align;
3717 : 905478 : bool any_orig = false;
3718 : :
3719 : 905478 : gcc_assert ((size % BITS_PER_UNIT == 0) && (pos % BITS_PER_UNIT == 0));
3720 : :
3721 : : /* For bswap framework using sets of stores, all the checking has been done
3722 : : earlier in try_coalesce_bswap and the result always needs to be emitted
3723 : : as a single store. Likewise for string concatenation. */
3724 : 905478 : if (group->stores[0]->rhs_code == LROTATE_EXPR
3725 : 904593 : || group->stores[0]->rhs_code == NOP_EXPR
3726 : 1809393 : || group->string_concatenation)
3727 : : {
3728 : 1773 : gcc_assert (!bzero_first);
3729 : 1773 : if (total_orig)
3730 : : {
3731 : : /* Avoid the old/new stmt count heuristics. It should be
3732 : : always beneficial. */
3733 : 591 : total_new[0] = 1;
3734 : 591 : total_orig[0] = 2;
3735 : : }
3736 : :
3737 : 1773 : if (split_stores)
3738 : : {
3739 : 591 : unsigned HOST_WIDE_INT align_bitpos
3740 : 591 : = (group->start - align_base) & (group_align - 1);
3741 : 591 : unsigned HOST_WIDE_INT align = group_align;
3742 : 591 : if (align_bitpos)
3743 : 64 : align = least_bit_hwi (align_bitpos);
3744 : 591 : bytepos = group->start / BITS_PER_UNIT;
3745 : 591 : split_store *store
3746 : 591 : = new split_store (bytepos, group->width, align);
3747 : 591 : unsigned int first = 0;
3748 : 591 : find_constituent_stores (group, &store->orig_stores,
3749 : : &first, group->start, group->width);
3750 : 591 : split_stores->safe_push (store);
3751 : : }
3752 : :
3753 : 1773 : return 1;
3754 : : }
3755 : :
3756 : 903705 : unsigned int ret = 0, first = 0;
3757 : 903705 : unsigned HOST_WIDE_INT try_pos = bytepos;
3758 : :
3759 : 903705 : if (total_orig)
3760 : : {
3761 : 296467 : unsigned int i;
3762 : 296467 : store_immediate_info *info = group->stores[0];
3763 : :
3764 : 296467 : total_new[0] = 0;
3765 : 296467 : total_orig[0] = 1; /* The orig store. */
3766 : 296467 : info = group->stores[0];
3767 : 296467 : if (info->ops[0].base_addr)
3768 : 69846 : total_orig[0]++;
3769 : 296467 : if (info->ops[1].base_addr)
3770 : 1463 : total_orig[0]++;
3771 : 296467 : switch (info->rhs_code)
3772 : : {
3773 : 1560 : case BIT_AND_EXPR:
3774 : 1560 : case BIT_IOR_EXPR:
3775 : 1560 : case BIT_XOR_EXPR:
3776 : 1560 : total_orig[0]++; /* The orig BIT_*_EXPR stmt. */
3777 : 1560 : break;
3778 : : default:
3779 : : break;
3780 : : }
3781 : 296467 : total_orig[0] *= group->stores.length ();
3782 : :
3783 : 1244215 : FOR_EACH_VEC_ELT (group->stores, i, info)
3784 : : {
3785 : 947748 : total_new[0] += count_multiple_uses (info);
3786 : 947748 : total_orig[0] += (info->bit_not_p
3787 : 947748 : + info->ops[0].bit_not_p
3788 : 947748 : + info->ops[1].bit_not_p);
3789 : : }
3790 : : }
3791 : :
3792 : 903705 : if (!allow_unaligned_load)
3793 : 0 : for (int i = 0; i < 2; ++i)
3794 : 0 : if (group->load_align[i])
3795 : 0 : group_load_align = MIN (group_load_align, group->load_align[i]);
3796 : :
3797 : 903705 : if (bzero_first)
3798 : : {
3799 : : store_immediate_info *gstore;
3800 : 15947 : FOR_EACH_VEC_ELT (group->stores, first, gstore)
3801 : 15947 : if (!gimple_clobber_p (gstore->stmt))
3802 : : break;
3803 : 15732 : ++first;
3804 : 15732 : ret = 1;
3805 : 15732 : if (split_stores)
3806 : : {
3807 : 1428 : split_store *store
3808 : 1428 : = new split_store (bytepos, gstore->bitsize, align_base);
3809 : 1428 : store->orig_stores.safe_push (gstore);
3810 : 1428 : store->orig = true;
3811 : 1428 : any_orig = true;
3812 : 1428 : split_stores->safe_push (store);
3813 : : }
3814 : : }
3815 : :
3816 : 5245147 : while (size > 0)
3817 : : {
3818 : 4341442 : if ((allow_unaligned_store || group_align <= BITS_PER_UNIT)
3819 : 1773022 : && (group->mask[try_pos - bytepos] == (unsigned char) ~0U
3820 : 1768406 : || (bzero_first && group->val[try_pos - bytepos] == 0)))
3821 : : {
3822 : : /* Skip padding bytes. */
3823 : 477811 : ++try_pos;
3824 : 477811 : size -= BITS_PER_UNIT;
3825 : 477811 : continue;
3826 : : }
3827 : :
3828 : 3863631 : unsigned HOST_WIDE_INT try_bitpos = try_pos * BITS_PER_UNIT;
3829 : 3863631 : unsigned int try_size = MAX_STORE_BITSIZE, nonmasked;
3830 : 3863631 : unsigned HOST_WIDE_INT align_bitpos
3831 : 3863631 : = (try_bitpos - align_base) & (group_align - 1);
3832 : 3863631 : unsigned HOST_WIDE_INT align = group_align;
3833 : 3863631 : bool found_orig = false;
3834 : 3863631 : if (align_bitpos)
3835 : 938087 : align = least_bit_hwi (align_bitpos);
3836 : 3863631 : if (!allow_unaligned_store)
3837 : 2598486 : try_size = MIN (try_size, align);
3838 : 3863631 : if (!allow_unaligned_load)
3839 : : {
3840 : : /* If we can't do or don't want to do unaligned stores
3841 : : as well as loads, we need to take the loads into account
3842 : : as well. */
3843 : 0 : unsigned HOST_WIDE_INT load_align = group_load_align;
3844 : 0 : align_bitpos = (try_bitpos - align_base) & (load_align - 1);
3845 : 0 : if (align_bitpos)
3846 : 0 : load_align = least_bit_hwi (align_bitpos);
3847 : 0 : for (int i = 0; i < 2; ++i)
3848 : 0 : if (group->load_align[i])
3849 : : {
3850 : 0 : align_bitpos
3851 : 0 : = known_alignment (try_bitpos
3852 : 0 : - group->stores[0]->bitpos
3853 : 0 : + group->stores[0]->ops[i].bitpos
3854 : 0 : - group->load_align_base[i]);
3855 : 0 : if (align_bitpos & (group_load_align - 1))
3856 : : {
3857 : 0 : unsigned HOST_WIDE_INT a = least_bit_hwi (align_bitpos);
3858 : 0 : load_align = MIN (load_align, a);
3859 : : }
3860 : : }
3861 : 0 : try_size = MIN (try_size, load_align);
3862 : : }
3863 : 3863631 : store_immediate_info *info
3864 : 3863631 : = find_constituent_stores (group, NULL, &first, try_bitpos, try_size);
3865 : 3863631 : if (info && !gimple_clobber_p (info->stmt))
3866 : : {
3867 : : /* If there is just one original statement for the range, see if
3868 : : we can just reuse the original store which could be even larger
3869 : : than try_size. */
3870 : 2275906 : unsigned HOST_WIDE_INT stmt_end
3871 : 2275906 : = ROUND_UP (info->bitpos + info->bitsize, BITS_PER_UNIT);
3872 : 2275906 : info = find_constituent_stores (group, NULL, &first, try_bitpos,
3873 : : stmt_end - try_bitpos);
3874 : 2275906 : if (info && info->bitpos >= try_bitpos)
3875 : : {
3876 : 2128313 : store_immediate_info *info2 = NULL;
3877 : 2128313 : unsigned int first_copy = first;
3878 : 2128313 : if (info->bitpos > try_bitpos
3879 : 5289 : && stmt_end - try_bitpos <= try_size)
3880 : : {
3881 : 5120 : info2 = find_constituent_stores (group, NULL, &first_copy,
3882 : : try_bitpos,
3883 : : info->bitpos - try_bitpos);
3884 : 5120 : gcc_assert (info2 == NULL || gimple_clobber_p (info2->stmt));
3885 : : }
3886 : 2127995 : if (info2 == NULL && stmt_end - try_bitpos < try_size)
3887 : : {
3888 : 418134 : info2 = find_constituent_stores (group, NULL, &first_copy,
3889 : : stmt_end,
3890 : 209067 : (try_bitpos + try_size)
3891 : : - stmt_end);
3892 : 209067 : gcc_assert (info2 == NULL || gimple_clobber_p (info2->stmt));
3893 : : }
3894 : : if (info2 == NULL)
3895 : : {
3896 : 2089622 : try_size = stmt_end - try_bitpos;
3897 : 2089622 : found_orig = true;
3898 : 2089622 : goto found;
3899 : : }
3900 : : }
3901 : : }
3902 : :
3903 : : /* Approximate store bitsize for the case when there are no padding
3904 : : bits. */
3905 : 1861301 : while (try_size > size)
3906 : 87292 : try_size /= 2;
3907 : : /* Now look for whole padding bytes at the end of that bitsize. */
3908 : 2613978 : for (nonmasked = try_size / BITS_PER_UNIT; nonmasked > 0; --nonmasked)
3909 : 2476912 : if (group->mask[try_pos - bytepos + nonmasked - 1]
3910 : : != (unsigned char) ~0U
3911 : 2466317 : && (!bzero_first
3912 : 832951 : || group->val[try_pos - bytepos + nonmasked - 1] != 0))
3913 : : break;
3914 : 1774009 : if (nonmasked == 0 || (info && gimple_clobber_p (info->stmt)))
3915 : : {
3916 : : /* If entire try_size range is padding, skip it. */
3917 : 1336753 : try_pos += try_size / BITS_PER_UNIT;
3918 : 1336753 : size -= try_size;
3919 : 1336753 : continue;
3920 : : }
3921 : : /* Otherwise try to decrease try_size if second half, last 3 quarters
3922 : : etc. are padding. */
3923 : 437256 : nonmasked *= BITS_PER_UNIT;
3924 : 440830 : while (nonmasked <= try_size / 2)
3925 : : try_size /= 2;
3926 : 437256 : if (!allow_unaligned_store && group_align > BITS_PER_UNIT)
3927 : : {
3928 : : /* Now look for whole padding bytes at the start of that bitsize. */
3929 : 259757 : unsigned int try_bytesize = try_size / BITS_PER_UNIT, masked;
3930 : 265127 : for (masked = 0; masked < try_bytesize; ++masked)
3931 : 265127 : if (group->mask[try_pos - bytepos + masked] != (unsigned char) ~0U
3932 : 263347 : && (!bzero_first
3933 : 5440 : || group->val[try_pos - bytepos + masked] != 0))
3934 : : break;
3935 : 259757 : masked *= BITS_PER_UNIT;
3936 : 259757 : gcc_assert (masked < try_size);
3937 : 259757 : if (masked >= try_size / 2)
3938 : : {
3939 : 3166 : while (masked >= try_size / 2)
3940 : : {
3941 : 1685 : try_size /= 2;
3942 : 1685 : try_pos += try_size / BITS_PER_UNIT;
3943 : 1685 : size -= try_size;
3944 : 1685 : masked -= try_size;
3945 : : }
3946 : : /* Need to recompute the alignment, so just retry at the new
3947 : : position. */
3948 : 1481 : continue;
3949 : : }
3950 : : }
3951 : :
3952 : 177499 : found:
3953 : 2525397 : ++ret;
3954 : :
3955 : 2525397 : if (split_stores)
3956 : : {
3957 : 792981 : split_store *store
3958 : 792981 : = new split_store (try_pos, try_size, align);
3959 : 792981 : info = find_constituent_stores (group, &store->orig_stores,
3960 : : &first, try_bitpos, try_size);
3961 : 792981 : if (info
3962 : 720005 : && !gimple_clobber_p (info->stmt)
3963 : 719985 : && info->bitpos >= try_bitpos
3964 : 712331 : && info->bitpos + info->bitsize <= try_bitpos + try_size
3965 : 1504344 : && (store->orig_stores.length () == 1
3966 : 78251 : || found_orig
3967 : 13236 : || (info->bitpos == try_bitpos
3968 : 13173 : && (info->bitpos + info->bitsize
3969 : : == try_bitpos + try_size))))
3970 : : {
3971 : 698573 : store->orig = true;
3972 : 698573 : any_orig = true;
3973 : : }
3974 : 792981 : split_stores->safe_push (store);
3975 : : }
3976 : :
3977 : 2525397 : try_pos += try_size / BITS_PER_UNIT;
3978 : 2525397 : size -= try_size;
3979 : : }
3980 : :
3981 : 903705 : if (total_orig)
3982 : : {
3983 : 296467 : unsigned int i;
3984 : 296467 : split_store *store;
3985 : : /* If we are reusing some original stores and any of the
3986 : : original SSA_NAMEs had multiple uses, we need to subtract
3987 : : those now before we add the new ones. */
3988 : 296467 : if (total_new[0] && any_orig)
3989 : : {
3990 : 96406 : FOR_EACH_VEC_ELT (*split_stores, i, store)
3991 : 65779 : if (store->orig)
3992 : 65485 : total_new[0] -= count_multiple_uses (store->orig_stores[0]);
3993 : : }
3994 : 296467 : total_new[0] += ret; /* The new store. */
3995 : 296467 : store_immediate_info *info = group->stores[0];
3996 : 296467 : if (info->ops[0].base_addr)
3997 : 69846 : total_new[0] += ret;
3998 : 296467 : if (info->ops[1].base_addr)
3999 : 1463 : total_new[0] += ret;
4000 : 296467 : switch (info->rhs_code)
4001 : : {
4002 : 1560 : case BIT_AND_EXPR:
4003 : 1560 : case BIT_IOR_EXPR:
4004 : 1560 : case BIT_XOR_EXPR:
4005 : 1560 : total_new[0] += ret; /* The new BIT_*_EXPR stmt. */
4006 : 1560 : break;
4007 : : default:
4008 : : break;
4009 : : }
4010 : 1090876 : FOR_EACH_VEC_ELT (*split_stores, i, store)
4011 : : {
4012 : 794409 : unsigned int j;
4013 : 794409 : bool bit_not_p[3] = { false, false, false };
4014 : : /* If all orig_stores have certain bit_not_p set, then
4015 : : we'd use a BIT_NOT_EXPR stmt and need to account for it.
4016 : : If some orig_stores have certain bit_not_p set, then
4017 : : we'd use a BIT_XOR_EXPR with a mask and need to account for
4018 : : it. */
4019 : 1799386 : FOR_EACH_VEC_ELT (store->orig_stores, j, info)
4020 : : {
4021 : 1004977 : if (info->ops[0].bit_not_p)
4022 : 263 : bit_not_p[0] = true;
4023 : 1004977 : if (info->ops[1].bit_not_p)
4024 : 17 : bit_not_p[1] = true;
4025 : 1004977 : if (info->bit_not_p)
4026 : 65 : bit_not_p[2] = true;
4027 : : }
4028 : 794409 : total_new[0] += bit_not_p[0] + bit_not_p[1] + bit_not_p[2];
4029 : : }
4030 : :
4031 : : }
4032 : :
4033 : : return ret;
4034 : : }
4035 : :
4036 : : /* Return the operation through which the operand IDX (if < 2) or
4037 : : result (IDX == 2) should be inverted. If NOP_EXPR, no inversion
4038 : : is done, if BIT_NOT_EXPR, all bits are inverted, if BIT_XOR_EXPR,
4039 : : the bits should be xored with mask. */
4040 : :
4041 : : static enum tree_code
4042 : 1754 : invert_op (split_store *split_store, int idx, tree int_type, tree &mask)
4043 : : {
4044 : 1754 : unsigned int i;
4045 : 1754 : store_immediate_info *info;
4046 : 1754 : unsigned int cnt = 0;
4047 : 1754 : bool any_paddings = false;
4048 : 6914 : FOR_EACH_VEC_ELT (split_store->orig_stores, i, info)
4049 : : {
4050 : 5160 : bool bit_not_p = idx < 2 ? info->ops[idx].bit_not_p : info->bit_not_p;
4051 : 5160 : if (bit_not_p)
4052 : : {
4053 : 67 : ++cnt;
4054 : 67 : tree lhs = gimple_assign_lhs (info->stmt);
4055 : 134 : if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4056 : 134 : && TYPE_PRECISION (TREE_TYPE (lhs)) < info->bitsize)
4057 : : any_paddings = true;
4058 : : }
4059 : : }
4060 : 1754 : mask = NULL_TREE;
4061 : 1754 : if (cnt == 0)
4062 : : return NOP_EXPR;
4063 : 50 : if (cnt == split_store->orig_stores.length () && !any_paddings)
4064 : : return BIT_NOT_EXPR;
4065 : :
4066 : 16 : unsigned HOST_WIDE_INT try_bitpos = split_store->bytepos * BITS_PER_UNIT;
4067 : 16 : unsigned buf_size = split_store->size / BITS_PER_UNIT;
4068 : 16 : unsigned char *buf
4069 : 16 : = XALLOCAVEC (unsigned char, buf_size);
4070 : 16 : memset (buf, ~0U, buf_size);
4071 : 68 : FOR_EACH_VEC_ELT (split_store->orig_stores, i, info)
4072 : : {
4073 : 52 : bool bit_not_p = idx < 2 ? info->ops[idx].bit_not_p : info->bit_not_p;
4074 : 52 : if (!bit_not_p)
4075 : 25 : continue;
4076 : : /* Clear regions with bit_not_p and invert afterwards, rather than
4077 : : clear regions with !bit_not_p, so that gaps in between stores aren't
4078 : : set in the mask. */
4079 : 27 : unsigned HOST_WIDE_INT bitsize = info->bitsize;
4080 : 27 : unsigned HOST_WIDE_INT prec = bitsize;
4081 : 27 : unsigned int pos_in_buffer = 0;
4082 : 27 : if (any_paddings)
4083 : : {
4084 : 8 : tree lhs = gimple_assign_lhs (info->stmt);
4085 : 16 : if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4086 : 16 : && TYPE_PRECISION (TREE_TYPE (lhs)) < bitsize)
4087 : 8 : prec = TYPE_PRECISION (TREE_TYPE (lhs));
4088 : : }
4089 : 27 : if (info->bitpos < try_bitpos)
4090 : : {
4091 : 0 : gcc_assert (info->bitpos + bitsize > try_bitpos);
4092 : 0 : if (!BYTES_BIG_ENDIAN)
4093 : : {
4094 : 0 : if (prec <= try_bitpos - info->bitpos)
4095 : 0 : continue;
4096 : 0 : prec -= try_bitpos - info->bitpos;
4097 : : }
4098 : 0 : bitsize -= try_bitpos - info->bitpos;
4099 : 0 : if (BYTES_BIG_ENDIAN && prec > bitsize)
4100 : : prec = bitsize;
4101 : : }
4102 : : else
4103 : 27 : pos_in_buffer = info->bitpos - try_bitpos;
4104 : 27 : if (prec < bitsize)
4105 : : {
4106 : : /* If this is a bool inversion, invert just the least significant
4107 : : prec bits rather than all bits of it. */
4108 : : if (BYTES_BIG_ENDIAN)
4109 : : {
4110 : : pos_in_buffer += bitsize - prec;
4111 : : if (pos_in_buffer >= split_store->size)
4112 : : continue;
4113 : : }
4114 : : bitsize = prec;
4115 : : }
4116 : 27 : if (pos_in_buffer + bitsize > split_store->size)
4117 : 0 : bitsize = split_store->size - pos_in_buffer;
4118 : 27 : unsigned char *p = buf + (pos_in_buffer / BITS_PER_UNIT);
4119 : 27 : if (BYTES_BIG_ENDIAN)
4120 : : clear_bit_region_be (p, (BITS_PER_UNIT - 1
4121 : : - (pos_in_buffer % BITS_PER_UNIT)), bitsize);
4122 : : else
4123 : 27 : clear_bit_region (p, pos_in_buffer % BITS_PER_UNIT, bitsize);
4124 : : }
4125 : 96 : for (unsigned int i = 0; i < buf_size; ++i)
4126 : 80 : buf[i] = ~buf[i];
4127 : 16 : mask = native_interpret_expr (int_type, buf, buf_size);
4128 : 16 : return BIT_XOR_EXPR;
4129 : : }
4130 : :
4131 : : /* Given a merged store group GROUP output the widened version of it.
4132 : : The store chain is against the base object BASE.
4133 : : Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
4134 : : unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
4135 : : Make sure that the number of statements output is less than the number of
4136 : : original statements. If a better sequence is possible emit it and
4137 : : return true. */
4138 : :
4139 : : bool
4140 : 408050 : imm_store_chain_info::output_merged_store (merged_store_group *group)
4141 : : {
4142 : 408050 : const unsigned HOST_WIDE_INT start_byte_pos
4143 : 408050 : = group->bitregion_start / BITS_PER_UNIT;
4144 : 519042 : unsigned int orig_num_stmts = group->stores.length ();
4145 : 408050 : if (orig_num_stmts < 2)
4146 : : return false;
4147 : :
4148 : 408050 : bool allow_unaligned_store
4149 : 408050 : = !STRICT_ALIGNMENT && param_store_merging_allow_unaligned;
4150 : 408050 : bool allow_unaligned_load = allow_unaligned_store;
4151 : 408050 : bool bzero_first = false;
4152 : 408050 : store_immediate_info *store;
4153 : 408050 : unsigned int num_clobber_stmts = 0;
4154 : 408050 : if (group->stores[0]->rhs_code == INTEGER_CST)
4155 : : {
4156 : : unsigned int i;
4157 : 618955 : FOR_EACH_VEC_ELT (group->stores, i, store)
4158 : 507963 : if (gimple_clobber_p (store->stmt))
4159 : 282257 : num_clobber_stmts++;
4160 : 225706 : else if (TREE_CODE (gimple_assign_rhs1 (store->stmt)) == CONSTRUCTOR
4161 : 13838 : && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (store->stmt)) == 0
4162 : 13838 : && group->start == store->bitpos
4163 : 13689 : && group->width == store->bitsize
4164 : 7152 : && (group->start % BITS_PER_UNIT) == 0
4165 : 232858 : && (group->width % BITS_PER_UNIT) == 0)
4166 : : {
4167 : : bzero_first = true;
4168 : : break;
4169 : : }
4170 : : else
4171 : : break;
4172 : 1070912 : FOR_EACH_VEC_ELT_FROM (group->stores, i, store, i)
4173 : 734214 : if (gimple_clobber_p (store->stmt))
4174 : 20536 : num_clobber_stmts++;
4175 : 336698 : if (num_clobber_stmts == orig_num_stmts)
4176 : : return false;
4177 : 225706 : orig_num_stmts -= num_clobber_stmts;
4178 : : }
4179 : 297058 : if (allow_unaligned_store || bzero_first)
4180 : : {
4181 : : /* If unaligned stores are allowed, see how many stores we'd emit
4182 : : for unaligned and how many stores we'd emit for aligned stores.
4183 : : Only use unaligned stores if it allows fewer stores than aligned.
4184 : : Similarly, if there is a whole region clear first, prefer expanding
4185 : : it together compared to expanding clear first followed by merged
4186 : : further stores. */
4187 : 297058 : unsigned cnt[4] = { ~0U, ~0U, ~0U, ~0U };
4188 : 297058 : int pass_min = 0;
4189 : 1485290 : for (int pass = 0; pass < 4; ++pass)
4190 : : {
4191 : 1188232 : if (!allow_unaligned_store && (pass & 1) != 0)
4192 : 0 : continue;
4193 : 1188232 : if (!bzero_first && (pass & 2) != 0)
4194 : 579812 : continue;
4195 : 1216840 : cnt[pass] = split_group (group, (pass & 1) != 0,
4196 : 608420 : allow_unaligned_load, (pass & 2) != 0,
4197 : : NULL, NULL, NULL);
4198 : 608420 : if (cnt[pass] < cnt[pass_min])
4199 : 1188232 : pass_min = pass;
4200 : : }
4201 : 297058 : if ((pass_min & 1) == 0)
4202 : 293616 : allow_unaligned_store = false;
4203 : 297058 : if ((pass_min & 2) == 0)
4204 : 295630 : bzero_first = false;
4205 : : }
4206 : :
4207 : 297058 : auto_vec<class split_store *, 32> split_stores;
4208 : 297058 : split_store *split_store;
4209 : 297058 : unsigned total_orig, total_new, i;
4210 : 297058 : split_group (group, allow_unaligned_store, allow_unaligned_load, bzero_first,
4211 : : &split_stores, &total_orig, &total_new);
4212 : :
4213 : : /* Determine if there is a clobber covering the whole group at the start,
4214 : : followed by proposed split stores that cover the whole group. In that
4215 : : case, prefer the transformation even if
4216 : : split_stores.length () == orig_num_stmts. */
4217 : 297058 : bool clobber_first = false;
4218 : 297058 : if (num_clobber_stmts
4219 : 43419 : && gimple_clobber_p (group->stores[0]->stmt)
4220 : 38567 : && group->start == group->stores[0]->bitpos
4221 : 38567 : && group->width == group->stores[0]->bitsize
4222 : 36039 : && (group->start % BITS_PER_UNIT) == 0
4223 : 333097 : && (group->width % BITS_PER_UNIT) == 0)
4224 : : {
4225 : 36039 : clobber_first = true;
4226 : 36039 : unsigned HOST_WIDE_INT pos = group->start / BITS_PER_UNIT;
4227 : 90577 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4228 : 62234 : if (split_store->bytepos != pos)
4229 : : {
4230 : : clobber_first = false;
4231 : : break;
4232 : : }
4233 : : else
4234 : 54538 : pos += split_store->size / BITS_PER_UNIT;
4235 : 36039 : if (pos != (group->start + group->width) / BITS_PER_UNIT)
4236 : 281660 : clobber_first = false;
4237 : : }
4238 : :
4239 : 594116 : if (split_stores.length () >= orig_num_stmts + clobber_first)
4240 : : {
4241 : :
4242 : : /* We didn't manage to reduce the number of statements. Bail out. */
4243 : 217725 : if (dump_file && (dump_flags & TDF_DETAILS))
4244 : 2 : fprintf (dump_file, "Exceeded original number of stmts (%u)."
4245 : : " Not profitable to emit new sequence.\n",
4246 : : orig_num_stmts);
4247 : 758921 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4248 : 1082392 : delete split_store;
4249 : : return false;
4250 : : }
4251 : 79333 : if (total_orig <= total_new)
4252 : : {
4253 : : /* If number of estimated new statements is above estimated original
4254 : : statements, bail out too. */
4255 : 878 : if (dump_file && (dump_flags & TDF_DETAILS))
4256 : 0 : fprintf (dump_file, "Estimated number of original stmts (%u)"
4257 : : " not larger than estimated number of new"
4258 : : " stmts (%u).\n",
4259 : : total_orig, total_new);
4260 : 1871 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4261 : 1986 : delete split_store;
4262 : : return false;
4263 : : }
4264 : 78455 : if (group->stores[0]->rhs_code == INTEGER_CST)
4265 : : {
4266 : 166295 : bool all_orig = true;
4267 : 166295 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4268 : 152354 : if (!split_store->orig)
4269 : : {
4270 : : all_orig = false;
4271 : : break;
4272 : : }
4273 : 76224 : if (all_orig)
4274 : : {
4275 : 13941 : unsigned int cnt = split_stores.length ();
4276 : : store_immediate_info *store;
4277 : 53120 : FOR_EACH_VEC_ELT (group->stores, i, store)
4278 : 39179 : if (gimple_clobber_p (store->stmt))
4279 : 15338 : ++cnt;
4280 : : /* Punt if we wouldn't make any real changes, i.e. keep all
4281 : : orig stmts + all clobbers. */
4282 : 13941 : if (cnt == group->stores.length ())
4283 : : {
4284 : 13842 : if (dump_file && (dump_flags & TDF_DETAILS))
4285 : 0 : fprintf (dump_file, "Exceeded original number of stmts (%u)."
4286 : : " Not profitable to emit new sequence.\n",
4287 : : orig_num_stmts);
4288 : 37481 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4289 : 47278 : delete split_store;
4290 : 232445 : return false;
4291 : : }
4292 : : }
4293 : : }
4294 : :
4295 : 64613 : gimple_stmt_iterator last_gsi = gsi_for_stmt (group->last_stmt);
4296 : 64613 : gimple_seq seq = NULL;
4297 : 64613 : tree last_vdef, new_vuse;
4298 : 64613 : last_vdef = gimple_vdef (group->last_stmt);
4299 : 64613 : new_vuse = gimple_vuse (group->last_stmt);
4300 : 64613 : tree bswap_res = NULL_TREE;
4301 : :
4302 : : /* Clobbers are not removed. */
4303 : 64613 : if (gimple_clobber_p (group->last_stmt))
4304 : : {
4305 : 773 : new_vuse = make_ssa_name (gimple_vop (cfun), group->last_stmt);
4306 : 773 : gimple_set_vdef (group->last_stmt, new_vuse);
4307 : : }
4308 : :
4309 : 64613 : if (group->stores[0]->rhs_code == LROTATE_EXPR
4310 : 64613 : || group->stores[0]->rhs_code == NOP_EXPR)
4311 : : {
4312 : 521 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
4313 : 521 : gimple *ins_stmt = group->stores[0]->ins_stmt;
4314 : 521 : struct symbolic_number *n = &group->stores[0]->n;
4315 : 521 : bool bswap = group->stores[0]->rhs_code == LROTATE_EXPR;
4316 : :
4317 : 521 : switch (n->range)
4318 : : {
4319 : 336 : case 16:
4320 : 336 : load_type = bswap_type = uint16_type_node;
4321 : 336 : break;
4322 : 22 : case 32:
4323 : 22 : load_type = uint32_type_node;
4324 : 22 : if (bswap)
4325 : : {
4326 : 12 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
4327 : 12 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
4328 : : }
4329 : : break;
4330 : 163 : case 64:
4331 : 163 : load_type = uint64_type_node;
4332 : 163 : if (bswap)
4333 : : {
4334 : 37 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
4335 : 37 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
4336 : : }
4337 : : break;
4338 : 0 : default:
4339 : 0 : gcc_unreachable ();
4340 : : }
4341 : :
4342 : : /* If the loads have each vuse of the corresponding store,
4343 : : we've checked the aliasing already in try_coalesce_bswap and
4344 : : we want to sink the need load into seq. So need to use new_vuse
4345 : : on the load. */
4346 : 521 : if (n->base_addr)
4347 : : {
4348 : 300 : if (n->vuse == NULL)
4349 : : {
4350 : 24 : n->vuse = new_vuse;
4351 : 24 : ins_stmt = NULL;
4352 : : }
4353 : : else
4354 : : /* Update vuse in case it has changed by output_merged_stores. */
4355 : 552 : n->vuse = gimple_vuse (ins_stmt);
4356 : : }
4357 : 521 : bswap_res = bswap_replace (gsi_start (seq), ins_stmt, fndecl,
4358 : : bswap_type, load_type, n, bswap,
4359 : : ~(uint64_t) 0, 0);
4360 : 521 : gcc_assert (bswap_res);
4361 : : }
4362 : :
4363 : 64613 : gimple *stmt = NULL;
4364 : 129226 : auto_vec<gimple *, 32> orig_stmts;
4365 : 64613 : gimple_seq this_seq;
4366 : 64613 : tree addr = force_gimple_operand_1 (unshare_expr (base_addr), &this_seq,
4367 : : is_gimple_mem_ref_addr, NULL_TREE);
4368 : 64613 : gimple_seq_add_seq_without_update (&seq, this_seq);
4369 : :
4370 : 64613 : tree load_addr[2] = { NULL_TREE, NULL_TREE };
4371 : 64613 : gimple_seq load_seq[2] = { NULL, NULL };
4372 : 64613 : gimple_stmt_iterator load_gsi[2] = { gsi_none (), gsi_none () };
4373 : 193839 : for (int j = 0; j < 2; ++j)
4374 : : {
4375 : 129226 : store_operand_info &op = group->stores[0]->ops[j];
4376 : 129226 : if (op.base_addr == NULL_TREE)
4377 : 128305 : continue;
4378 : :
4379 : 921 : store_immediate_info *infol = group->stores.last ();
4380 : 2763 : if (gimple_vuse (op.stmt) == gimple_vuse (infol->ops[j].stmt))
4381 : : {
4382 : : /* We can't pick the location randomly; while we've verified
4383 : : all the loads have the same vuse, they can be still in different
4384 : : basic blocks and we need to pick the one from the last bb:
4385 : : int x = q[0];
4386 : : if (x == N) return;
4387 : : int y = q[1];
4388 : : p[0] = x;
4389 : : p[1] = y;
4390 : : otherwise if we put the wider load at the q[0] load, we might
4391 : : segfault if q[1] is not mapped. */
4392 : 621 : basic_block bb = gimple_bb (op.stmt);
4393 : 621 : gimple *ostmt = op.stmt;
4394 : 621 : store_immediate_info *info;
4395 : 3583 : FOR_EACH_VEC_ELT (group->stores, i, info)
4396 : : {
4397 : 2962 : gimple *tstmt = info->ops[j].stmt;
4398 : 2962 : basic_block tbb = gimple_bb (tstmt);
4399 : 2962 : if (dominated_by_p (CDI_DOMINATORS, tbb, bb))
4400 : : {
4401 : 2958 : ostmt = tstmt;
4402 : 2958 : bb = tbb;
4403 : : }
4404 : : }
4405 : 621 : load_gsi[j] = gsi_for_stmt (ostmt);
4406 : 621 : load_addr[j]
4407 : 621 : = force_gimple_operand_1 (unshare_expr (op.base_addr),
4408 : : &load_seq[j], is_gimple_mem_ref_addr,
4409 : : NULL_TREE);
4410 : : }
4411 : 300 : else if (operand_equal_p (base_addr, op.base_addr, 0))
4412 : 24 : load_addr[j] = addr;
4413 : : else
4414 : : {
4415 : 276 : load_addr[j]
4416 : 276 : = force_gimple_operand_1 (unshare_expr (op.base_addr),
4417 : : &this_seq, is_gimple_mem_ref_addr,
4418 : : NULL_TREE);
4419 : 276 : gimple_seq_add_seq_without_update (&seq, this_seq);
4420 : : }
4421 : : }
4422 : :
4423 : 293785 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4424 : : {
4425 : 229172 : const unsigned HOST_WIDE_INT try_size = split_store->size;
4426 : 229172 : const unsigned HOST_WIDE_INT try_pos = split_store->bytepos;
4427 : 229172 : const unsigned HOST_WIDE_INT try_bitpos = try_pos * BITS_PER_UNIT;
4428 : 229172 : const unsigned HOST_WIDE_INT try_align = split_store->align;
4429 : 229172 : const unsigned HOST_WIDE_INT try_offset = try_pos - start_byte_pos;
4430 : 229172 : tree dest, src;
4431 : 229172 : location_t loc;
4432 : :
4433 : 229172 : if (split_store->orig)
4434 : : {
4435 : : /* If there is just a single non-clobber constituent store
4436 : : which covers the whole area, just reuse the lhs and rhs. */
4437 : 174585 : gimple *orig_stmt = NULL;
4438 : : store_immediate_info *store;
4439 : : unsigned int j;
4440 : 174585 : FOR_EACH_VEC_ELT (split_store->orig_stores, j, store)
4441 : 174585 : if (!gimple_clobber_p (store->stmt))
4442 : : {
4443 : : orig_stmt = store->stmt;
4444 : : break;
4445 : : }
4446 : 157518 : dest = gimple_assign_lhs (orig_stmt);
4447 : 157518 : src = gimple_assign_rhs1 (orig_stmt);
4448 : 157518 : loc = gimple_location (orig_stmt);
4449 : : }
4450 : : else
4451 : : {
4452 : : store_immediate_info *info;
4453 : : unsigned short clique, base;
4454 : : unsigned int k;
4455 : 245085 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4456 : 173431 : orig_stmts.safe_push (info->stmt);
4457 : 71654 : tree offset_type
4458 : 71654 : = get_alias_type_for_stmts (orig_stmts, false, &clique, &base);
4459 : 71654 : tree dest_type;
4460 : 71654 : loc = get_location_for_stmts (orig_stmts);
4461 : 71654 : orig_stmts.truncate (0);
4462 : :
4463 : 71654 : if (group->string_concatenation)
4464 : 70 : dest_type
4465 : 70 : = build_array_type_nelts (char_type_node,
4466 : 70 : try_size / BITS_PER_UNIT);
4467 : : else
4468 : : {
4469 : 71584 : dest_type = build_nonstandard_integer_type (try_size, UNSIGNED);
4470 : 71584 : dest_type = build_aligned_type (dest_type, try_align);
4471 : : }
4472 : 71654 : dest = fold_build2 (MEM_REF, dest_type, addr,
4473 : : build_int_cst (offset_type, try_pos));
4474 : 71654 : if (TREE_CODE (dest) == MEM_REF)
4475 : : {
4476 : 71654 : MR_DEPENDENCE_CLIQUE (dest) = clique;
4477 : 71654 : MR_DEPENDENCE_BASE (dest) = base;
4478 : : }
4479 : :
4480 : 71654 : tree mask;
4481 : 71654 : if (bswap_res || group->string_concatenation)
4482 : 591 : mask = integer_zero_node;
4483 : : else
4484 : 71063 : mask = native_interpret_expr (dest_type,
4485 : 71063 : group->mask + try_offset,
4486 : 71063 : group->buf_size);
4487 : :
4488 : 71654 : tree ops[2];
4489 : 143349 : for (int j = 0;
4490 : 286575 : j < 1 + (split_store->orig_stores[0]->ops[1].val != NULL_TREE);
4491 : : ++j)
4492 : : {
4493 : 71695 : store_operand_info &op = split_store->orig_stores[0]->ops[j];
4494 : 71695 : if (bswap_res)
4495 : 521 : ops[j] = bswap_res;
4496 : 71174 : else if (group->string_concatenation)
4497 : : {
4498 : 140 : ops[j] = build_string (try_size / BITS_PER_UNIT,
4499 : 70 : (const char *) group->val + try_offset);
4500 : 70 : TREE_TYPE (ops[j]) = dest_type;
4501 : : }
4502 : 71104 : else if (op.base_addr)
4503 : : {
4504 : 4436 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4505 : 3244 : orig_stmts.safe_push (info->ops[j].stmt);
4506 : :
4507 : 1192 : offset_type = get_alias_type_for_stmts (orig_stmts, true,
4508 : : &clique, &base);
4509 : 1192 : location_t load_loc = get_location_for_stmts (orig_stmts);
4510 : 1192 : orig_stmts.truncate (0);
4511 : :
4512 : 1192 : unsigned HOST_WIDE_INT load_align = group->load_align[j];
4513 : 1192 : unsigned HOST_WIDE_INT align_bitpos
4514 : 1192 : = known_alignment (try_bitpos
4515 : 1192 : - split_store->orig_stores[0]->bitpos
4516 : 1192 : + op.bitpos);
4517 : 1192 : if (align_bitpos & (load_align - 1))
4518 : 514 : load_align = least_bit_hwi (align_bitpos);
4519 : :
4520 : 1192 : tree load_int_type
4521 : 1192 : = build_nonstandard_integer_type (try_size, UNSIGNED);
4522 : 1192 : load_int_type
4523 : 1192 : = build_aligned_type (load_int_type, load_align);
4524 : :
4525 : 1192 : poly_uint64 load_pos
4526 : 1192 : = exact_div (try_bitpos
4527 : 1192 : - split_store->orig_stores[0]->bitpos
4528 : 1192 : + op.bitpos,
4529 : : BITS_PER_UNIT);
4530 : 1192 : ops[j] = fold_build2 (MEM_REF, load_int_type, load_addr[j],
4531 : : build_int_cst (offset_type, load_pos));
4532 : 1192 : if (TREE_CODE (ops[j]) == MEM_REF)
4533 : : {
4534 : 1192 : MR_DEPENDENCE_CLIQUE (ops[j]) = clique;
4535 : 1192 : MR_DEPENDENCE_BASE (ops[j]) = base;
4536 : : }
4537 : 1192 : if (!integer_zerop (mask))
4538 : : {
4539 : : /* The load might load some bits (that will be masked
4540 : : off later on) uninitialized, avoid -W*uninitialized
4541 : : warnings in that case. */
4542 : 40 : suppress_warning (ops[j], OPT_Wuninitialized);
4543 : : }
4544 : :
4545 : 1192 : stmt = gimple_build_assign (make_ssa_name (dest_type), ops[j]);
4546 : 1192 : gimple_set_location (stmt, load_loc);
4547 : 1192 : if (gsi_bb (load_gsi[j]))
4548 : : {
4549 : 1612 : gimple_set_vuse (stmt, gimple_vuse (op.stmt));
4550 : 806 : gimple_seq_add_stmt_without_update (&load_seq[j], stmt);
4551 : : }
4552 : : else
4553 : : {
4554 : 386 : gimple_set_vuse (stmt, new_vuse);
4555 : 386 : gimple_seq_add_stmt_without_update (&seq, stmt);
4556 : : }
4557 : 1192 : ops[j] = gimple_assign_lhs (stmt);
4558 : 1192 : tree xor_mask;
4559 : 1192 : enum tree_code inv_op
4560 : 1192 : = invert_op (split_store, j, dest_type, xor_mask);
4561 : 1192 : if (inv_op != NOP_EXPR)
4562 : : {
4563 : 17 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4564 : : inv_op, ops[j], xor_mask);
4565 : 17 : gimple_set_location (stmt, load_loc);
4566 : 17 : ops[j] = gimple_assign_lhs (stmt);
4567 : :
4568 : 17 : if (gsi_bb (load_gsi[j]))
4569 : 7 : gimple_seq_add_stmt_without_update (&load_seq[j],
4570 : : stmt);
4571 : : else
4572 : 10 : gimple_seq_add_stmt_without_update (&seq, stmt);
4573 : : }
4574 : : }
4575 : : else
4576 : 69912 : ops[j] = native_interpret_expr (dest_type,
4577 : 69912 : group->val + try_offset,
4578 : 69912 : group->buf_size);
4579 : : }
4580 : :
4581 : 71654 : switch (split_store->orig_stores[0]->rhs_code)
4582 : : {
4583 : : case BIT_AND_EXPR:
4584 : : case BIT_IOR_EXPR:
4585 : : case BIT_XOR_EXPR:
4586 : 197 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4587 : : {
4588 : 156 : tree rhs1 = gimple_assign_rhs1 (info->stmt);
4589 : 156 : orig_stmts.safe_push (SSA_NAME_DEF_STMT (rhs1));
4590 : : }
4591 : 41 : location_t bit_loc;
4592 : 41 : bit_loc = get_location_for_stmts (orig_stmts);
4593 : 41 : orig_stmts.truncate (0);
4594 : :
4595 : 41 : stmt
4596 : 41 : = gimple_build_assign (make_ssa_name (dest_type),
4597 : 41 : split_store->orig_stores[0]->rhs_code,
4598 : : ops[0], ops[1]);
4599 : 41 : gimple_set_location (stmt, bit_loc);
4600 : : /* If there is just one load and there is a separate
4601 : : load_seq[0], emit the bitwise op right after it. */
4602 : 41 : if (load_addr[1] == NULL_TREE && gsi_bb (load_gsi[0]))
4603 : 2 : gimple_seq_add_stmt_without_update (&load_seq[0], stmt);
4604 : : /* Otherwise, if at least one load is in seq, we need to
4605 : : emit the bitwise op right before the store. If there
4606 : : are two loads and are emitted somewhere else, it would
4607 : : be better to emit the bitwise op as early as possible;
4608 : : we don't track where that would be possible right now
4609 : : though. */
4610 : : else
4611 : 39 : gimple_seq_add_stmt_without_update (&seq, stmt);
4612 : 41 : src = gimple_assign_lhs (stmt);
4613 : 41 : tree xor_mask;
4614 : 41 : enum tree_code inv_op;
4615 : 41 : inv_op = invert_op (split_store, 2, dest_type, xor_mask);
4616 : 41 : if (inv_op != NOP_EXPR)
4617 : : {
4618 : 2 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4619 : : inv_op, src, xor_mask);
4620 : 2 : gimple_set_location (stmt, bit_loc);
4621 : 2 : if (load_addr[1] == NULL_TREE && gsi_bb (load_gsi[0]))
4622 : 0 : gimple_seq_add_stmt_without_update (&load_seq[0], stmt);
4623 : : else
4624 : 2 : gimple_seq_add_stmt_without_update (&seq, stmt);
4625 : 2 : src = gimple_assign_lhs (stmt);
4626 : : }
4627 : : break;
4628 : 521 : case LROTATE_EXPR:
4629 : 521 : case NOP_EXPR:
4630 : 521 : src = ops[0];
4631 : 521 : if (!is_gimple_val (src))
4632 : : {
4633 : 0 : stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (src)),
4634 : : src);
4635 : 0 : gimple_seq_add_stmt_without_update (&seq, stmt);
4636 : 0 : src = gimple_assign_lhs (stmt);
4637 : : }
4638 : 521 : if (!useless_type_conversion_p (dest_type, TREE_TYPE (src)))
4639 : : {
4640 : 58 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4641 : : NOP_EXPR, src);
4642 : 58 : gimple_seq_add_stmt_without_update (&seq, stmt);
4643 : 58 : src = gimple_assign_lhs (stmt);
4644 : : }
4645 : 521 : inv_op = invert_op (split_store, 2, dest_type, xor_mask);
4646 : 521 : if (inv_op != NOP_EXPR)
4647 : : {
4648 : 6 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4649 : : inv_op, src, xor_mask);
4650 : 6 : gimple_set_location (stmt, loc);
4651 : 6 : gimple_seq_add_stmt_without_update (&seq, stmt);
4652 : 6 : src = gimple_assign_lhs (stmt);
4653 : : }
4654 : : break;
4655 : 71092 : default:
4656 : 71092 : src = ops[0];
4657 : 71092 : break;
4658 : : }
4659 : :
4660 : : /* If bit insertion is required, we use the source as an accumulator
4661 : : into which the successive bit-field values are manually inserted.
4662 : : FIXME: perhaps use BIT_INSERT_EXPR instead in some cases? */
4663 : 71654 : if (group->bit_insertion)
4664 : 9477 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4665 : 7007 : if (info->rhs_code == BIT_INSERT_EXPR
4666 : 3725 : && info->bitpos < try_bitpos + try_size
4667 : 3725 : && info->bitpos + info->bitsize > try_bitpos)
4668 : : {
4669 : : /* Mask, truncate, convert to final type, shift and ior into
4670 : : the accumulator. Note that every step can be a no-op. */
4671 : 3725 : const HOST_WIDE_INT start_gap = info->bitpos - try_bitpos;
4672 : 3725 : const HOST_WIDE_INT end_gap
4673 : 3725 : = (try_bitpos + try_size) - (info->bitpos + info->bitsize);
4674 : 3725 : tree tem = info->ops[0].val;
4675 : 3725 : if (!INTEGRAL_TYPE_P (TREE_TYPE (tem)))
4676 : : {
4677 : 0 : const unsigned HOST_WIDE_INT size
4678 : 0 : = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (tem)));
4679 : 0 : tree integer_type
4680 : 0 : = build_nonstandard_integer_type (size, UNSIGNED);
4681 : 0 : tem = gimple_build (&seq, loc, VIEW_CONVERT_EXPR,
4682 : : integer_type, tem);
4683 : : }
4684 : 3725 : if (TYPE_PRECISION (TREE_TYPE (tem)) <= info->bitsize)
4685 : : {
4686 : 1334 : tree bitfield_type
4687 : 1334 : = build_nonstandard_integer_type (info->bitsize,
4688 : : UNSIGNED);
4689 : 1334 : tem = gimple_convert (&seq, loc, bitfield_type, tem);
4690 : : }
4691 : 2391 : else if ((BYTES_BIG_ENDIAN ? start_gap : end_gap) > 0)
4692 : : {
4693 : 1276 : wide_int imask
4694 : : = wi::mask (info->bitsize, false,
4695 : 1276 : TYPE_PRECISION (TREE_TYPE (tem)));
4696 : 3828 : tem = gimple_build (&seq, loc,
4697 : 1276 : BIT_AND_EXPR, TREE_TYPE (tem), tem,
4698 : 1276 : wide_int_to_tree (TREE_TYPE (tem),
4699 : : imask));
4700 : 1276 : }
4701 : 3725 : const HOST_WIDE_INT shift
4702 : : = (BYTES_BIG_ENDIAN ? end_gap : start_gap);
4703 : 3725 : if (shift < 0)
4704 : 4 : tem = gimple_build (&seq, loc,
4705 : 4 : RSHIFT_EXPR, TREE_TYPE (tem), tem,
4706 : 4 : build_int_cst (NULL_TREE, -shift));
4707 : 3725 : tem = gimple_convert (&seq, loc, dest_type, tem);
4708 : 3725 : if (shift > 0)
4709 : 2907 : tem = gimple_build (&seq, loc,
4710 : : LSHIFT_EXPR, dest_type, tem,
4711 : : build_int_cst (NULL_TREE, shift));
4712 : 3725 : src = gimple_build (&seq, loc,
4713 : : BIT_IOR_EXPR, dest_type, tem, src);
4714 : : }
4715 : :
4716 : 71654 : if (!integer_zerop (mask))
4717 : : {
4718 : 825 : tree tem = make_ssa_name (dest_type);
4719 : 825 : tree load_src = unshare_expr (dest);
4720 : : /* The load might load some or all bits uninitialized,
4721 : : avoid -W*uninitialized warnings in that case.
4722 : : As optimization, it would be nice if all the bits are
4723 : : provably uninitialized (no stores at all yet or previous
4724 : : store a CLOBBER) we'd optimize away the load and replace
4725 : : it e.g. with 0. */
4726 : 825 : suppress_warning (load_src, OPT_Wuninitialized);
4727 : 825 : stmt = gimple_build_assign (tem, load_src);
4728 : 825 : gimple_set_location (stmt, loc);
4729 : 825 : gimple_set_vuse (stmt, new_vuse);
4730 : 825 : gimple_seq_add_stmt_without_update (&seq, stmt);
4731 : :
4732 : : /* FIXME: If there is a single chunk of zero bits in mask,
4733 : : perhaps use BIT_INSERT_EXPR instead? */
4734 : 825 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4735 : : BIT_AND_EXPR, tem, mask);
4736 : 825 : gimple_set_location (stmt, loc);
4737 : 825 : gimple_seq_add_stmt_without_update (&seq, stmt);
4738 : 825 : tem = gimple_assign_lhs (stmt);
4739 : :
4740 : 825 : if (TREE_CODE (src) == INTEGER_CST)
4741 : 657 : src = wide_int_to_tree (dest_type,
4742 : 657 : wi::bit_and_not (wi::to_wide (src),
4743 : 1314 : wi::to_wide (mask)));
4744 : : else
4745 : : {
4746 : 168 : tree nmask
4747 : 168 : = wide_int_to_tree (dest_type,
4748 : 168 : wi::bit_not (wi::to_wide (mask)));
4749 : 168 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4750 : : BIT_AND_EXPR, src, nmask);
4751 : 168 : gimple_set_location (stmt, loc);
4752 : 168 : gimple_seq_add_stmt_without_update (&seq, stmt);
4753 : 168 : src = gimple_assign_lhs (stmt);
4754 : : }
4755 : 825 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4756 : : BIT_IOR_EXPR, tem, src);
4757 : 825 : gimple_set_location (stmt, loc);
4758 : 825 : gimple_seq_add_stmt_without_update (&seq, stmt);
4759 : 825 : src = gimple_assign_lhs (stmt);
4760 : : }
4761 : : }
4762 : :
4763 : 229172 : stmt = gimple_build_assign (dest, src);
4764 : 229172 : gimple_set_location (stmt, loc);
4765 : 229172 : gimple_set_vuse (stmt, new_vuse);
4766 : 229172 : gimple_seq_add_stmt_without_update (&seq, stmt);
4767 : :
4768 : 229172 : if (group->lp_nr && stmt_could_throw_p (cfun, stmt))
4769 : 72 : add_stmt_to_eh_lp (stmt, group->lp_nr);
4770 : :
4771 : 229172 : tree new_vdef;
4772 : 458344 : if (i < split_stores.length () - 1)
4773 : 164559 : new_vdef = make_ssa_name (gimple_vop (cfun), stmt);
4774 : : else
4775 : : new_vdef = last_vdef;
4776 : :
4777 : 229172 : gimple_set_vdef (stmt, new_vdef);
4778 : 229172 : SSA_NAME_DEF_STMT (new_vdef) = stmt;
4779 : 229172 : new_vuse = new_vdef;
4780 : : }
4781 : :
4782 : 293785 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4783 : 458344 : delete split_store;
4784 : :
4785 : 64613 : gcc_assert (seq);
4786 : 64613 : if (dump_file)
4787 : : {
4788 : 196 : fprintf (dump_file,
4789 : : "New sequence of %u stores to replace old one of %u stores\n",
4790 : : split_stores.length (), orig_num_stmts);
4791 : 98 : if (dump_flags & TDF_DETAILS)
4792 : 25 : print_gimple_seq (dump_file, seq, 0, TDF_VOPS | TDF_MEMSYMS);
4793 : : }
4794 : :
4795 : 64613 : if (gimple_clobber_p (group->last_stmt))
4796 : 773 : update_stmt (group->last_stmt);
4797 : :
4798 : 64613 : if (group->lp_nr > 0)
4799 : : {
4800 : : /* We're going to insert a sequence of (potentially) throwing stores
4801 : : into an active EH region. This means that we're going to create
4802 : : new basic blocks with EH edges pointing to the post landing pad
4803 : : and, therefore, to have to update its PHI nodes, if any. For the
4804 : : virtual PHI node, we're going to use the VDEFs created above, but
4805 : : for the other nodes, we need to record the original reaching defs. */
4806 : 58 : eh_landing_pad lp = get_eh_landing_pad_from_number (group->lp_nr);
4807 : 58 : basic_block lp_bb = label_to_block (cfun, lp->post_landing_pad);
4808 : 58 : basic_block last_bb = gimple_bb (group->last_stmt);
4809 : 58 : edge last_edge = find_edge (last_bb, lp_bb);
4810 : 58 : auto_vec<tree, 16> last_defs;
4811 : 58 : gphi_iterator gpi;
4812 : 106 : for (gpi = gsi_start_phis (lp_bb); !gsi_end_p (gpi); gsi_next (&gpi))
4813 : : {
4814 : 48 : gphi *phi = gpi.phi ();
4815 : 48 : tree last_def;
4816 : 96 : if (virtual_operand_p (gimple_phi_result (phi)))
4817 : 48 : last_def = NULL_TREE;
4818 : : else
4819 : 0 : last_def = gimple_phi_arg_def (phi, last_edge->dest_idx);
4820 : 48 : last_defs.safe_push (last_def);
4821 : : }
4822 : :
4823 : : /* Do the insertion. Then, if new basic blocks have been created in the
4824 : : process, rewind the chain of VDEFs create above to walk the new basic
4825 : : blocks and update the corresponding arguments of the PHI nodes. */
4826 : 58 : update_modified_stmts (seq);
4827 : 58 : if (gimple_find_sub_bbs (seq, &last_gsi))
4828 : 130 : while (last_vdef != gimple_vuse (group->last_stmt))
4829 : : {
4830 : 72 : gimple *stmt = SSA_NAME_DEF_STMT (last_vdef);
4831 : 72 : if (stmt_could_throw_p (cfun, stmt))
4832 : : {
4833 : 72 : edge new_edge = find_edge (gimple_bb (stmt), lp_bb);
4834 : 72 : unsigned int i;
4835 : 72 : for (gpi = gsi_start_phis (lp_bb), i = 0;
4836 : 132 : !gsi_end_p (gpi);
4837 : 60 : gsi_next (&gpi), i++)
4838 : : {
4839 : 60 : gphi *phi = gpi.phi ();
4840 : 60 : tree new_def;
4841 : 120 : if (virtual_operand_p (gimple_phi_result (phi)))
4842 : : new_def = last_vdef;
4843 : : else
4844 : 0 : new_def = last_defs[i];
4845 : 60 : add_phi_arg (phi, new_def, new_edge, UNKNOWN_LOCATION);
4846 : : }
4847 : : }
4848 : 202 : last_vdef = gimple_vuse (stmt);
4849 : : }
4850 : 58 : }
4851 : : else
4852 : 64555 : gsi_insert_seq_after (&last_gsi, seq, GSI_SAME_STMT);
4853 : :
4854 : 193839 : for (int j = 0; j < 2; ++j)
4855 : 129226 : if (load_seq[j])
4856 : 621 : gsi_insert_seq_after (&load_gsi[j], load_seq[j], GSI_SAME_STMT);
4857 : :
4858 : 64613 : return true;
4859 : 297058 : }
4860 : :
4861 : : /* Process the merged_store_group objects created in the coalescing phase.
4862 : : The stores are all against the base object BASE.
4863 : : Try to output the widened stores and delete the original statements if
4864 : : successful. Return true iff any changes were made. */
4865 : :
4866 : : bool
4867 : 381088 : imm_store_chain_info::output_merged_stores ()
4868 : : {
4869 : 381088 : unsigned int i;
4870 : 381088 : merged_store_group *merged_store;
4871 : 381088 : bool ret = false;
4872 : 789138 : FOR_EACH_VEC_ELT (m_merged_store_groups, i, merged_store)
4873 : : {
4874 : 408050 : if (dbg_cnt (store_merging)
4875 : 408050 : && output_merged_store (merged_store))
4876 : : {
4877 : : unsigned int j;
4878 : : store_immediate_info *store;
4879 : 801819 : FOR_EACH_VEC_ELT (merged_store->stores, j, store)
4880 : : {
4881 : 329156 : gimple *stmt = store->stmt;
4882 : 329156 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
4883 : : /* Don't remove clobbers, they are still useful even if
4884 : : everything is overwritten afterwards. */
4885 : 329156 : if (gimple_clobber_p (stmt))
4886 : 12151 : continue;
4887 : 317005 : gsi_remove (&gsi, true);
4888 : 317005 : if (store->lp_nr)
4889 : 202 : remove_stmt_from_eh_lp (stmt);
4890 : 317005 : if (stmt != merged_store->last_stmt)
4891 : : {
4892 : 253165 : unlink_stmt_vdef (stmt);
4893 : 253165 : release_defs (stmt);
4894 : : }
4895 : : }
4896 : : ret = true;
4897 : : }
4898 : : }
4899 : 381088 : if (ret && dump_file)
4900 : 98 : fprintf (dump_file, "Merging successful!\n");
4901 : :
4902 : 381088 : return ret;
4903 : : }
4904 : :
4905 : : /* Coalesce the store_immediate_info objects recorded against the base object
4906 : : BASE in the first phase and output them.
4907 : : Delete the allocated structures.
4908 : : Return true if any changes were made. */
4909 : :
4910 : : bool
4911 : 1791458 : imm_store_chain_info::terminate_and_process_chain ()
4912 : : {
4913 : 1791458 : if (dump_file && (dump_flags & TDF_DETAILS))
4914 : 106 : fprintf (dump_file, "Terminating chain with %u stores\n",
4915 : : m_store_info.length ());
4916 : : /* Process store chain. */
4917 : 1791458 : bool ret = false;
4918 : 1791458 : if (m_store_info.length () > 1)
4919 : : {
4920 : 491105 : ret = coalesce_immediate_stores ();
4921 : 491105 : if (ret)
4922 : 381088 : ret = output_merged_stores ();
4923 : : }
4924 : :
4925 : : /* Delete all the entries we allocated ourselves. */
4926 : 1791458 : store_immediate_info *info;
4927 : 1791458 : unsigned int i;
4928 : 4665032 : FOR_EACH_VEC_ELT (m_store_info, i, info)
4929 : 2873574 : delete info;
4930 : :
4931 : : merged_store_group *merged_info;
4932 : 2199508 : FOR_EACH_VEC_ELT (m_merged_store_groups, i, merged_info)
4933 : 408050 : delete merged_info;
4934 : :
4935 : 1791458 : return ret;
4936 : : }
4937 : :
4938 : : /* Return true iff LHS is a destination potentially interesting for
4939 : : store merging. In practice these are the codes that get_inner_reference
4940 : : can process. */
4941 : :
4942 : : static bool
4943 : 8736051 : lhs_valid_for_store_merging_p (tree lhs)
4944 : : {
4945 : 8736051 : if (DECL_P (lhs))
4946 : : return true;
4947 : :
4948 : 6657776 : switch (TREE_CODE (lhs))
4949 : : {
4950 : : case ARRAY_REF:
4951 : : case ARRAY_RANGE_REF:
4952 : : case BIT_FIELD_REF:
4953 : : case COMPONENT_REF:
4954 : : case MEM_REF:
4955 : : case VIEW_CONVERT_EXPR:
4956 : : return true;
4957 : : default:
4958 : : return false;
4959 : : }
4960 : : }
4961 : :
4962 : : /* Return true if the tree RHS is a constant we want to consider
4963 : : during store merging. In practice accept all codes that
4964 : : native_encode_expr accepts. */
4965 : :
4966 : : static bool
4967 : 4686765 : rhs_valid_for_store_merging_p (tree rhs)
4968 : : {
4969 : 4686765 : unsigned HOST_WIDE_INT size;
4970 : 4686765 : if (TREE_CODE (rhs) == CONSTRUCTOR
4971 : 1018802 : && CONSTRUCTOR_NELTS (rhs) == 0
4972 : 1018802 : && TYPE_SIZE_UNIT (TREE_TYPE (rhs))
4973 : 5705567 : && tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (rhs))))
4974 : : return true;
4975 : 7335926 : return (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (rhs))).is_constant (&size)
4976 : 3667963 : && native_encode_expr (rhs, NULL, size) != 0);
4977 : : }
4978 : :
4979 : : /* Adjust *PBITPOS, *PBITREGION_START and *PBITREGION_END by BYTE_OFF bytes
4980 : : and return true on success or false on failure. */
4981 : :
4982 : : static bool
4983 : 921254 : adjust_bit_pos (poly_offset_int byte_off,
4984 : : poly_int64 *pbitpos,
4985 : : poly_uint64 *pbitregion_start,
4986 : : poly_uint64 *pbitregion_end)
4987 : : {
4988 : 921254 : poly_offset_int bit_off = byte_off << LOG2_BITS_PER_UNIT;
4989 : 921254 : bit_off += *pbitpos;
4990 : :
4991 : 921254 : if (known_ge (bit_off, 0) && bit_off.to_shwi (pbitpos))
4992 : : {
4993 : 914766 : if (maybe_ne (*pbitregion_end, 0U))
4994 : : {
4995 : 5838 : bit_off = byte_off << LOG2_BITS_PER_UNIT;
4996 : 5838 : bit_off += *pbitregion_start;
4997 : 5838 : if (bit_off.to_uhwi (pbitregion_start))
4998 : : {
4999 : 5838 : bit_off = byte_off << LOG2_BITS_PER_UNIT;
5000 : 5838 : bit_off += *pbitregion_end;
5001 : 5838 : if (!bit_off.to_uhwi (pbitregion_end))
5002 : 0 : *pbitregion_end = 0;
5003 : : }
5004 : : else
5005 : 0 : *pbitregion_end = 0;
5006 : : }
5007 : 914766 : return true;
5008 : : }
5009 : : else
5010 : 6488 : return false;
5011 : : }
5012 : :
5013 : : /* If MEM is a memory reference usable for store merging (either as
5014 : : store destination or for loads), return the non-NULL base_addr
5015 : : and set *PBITSIZE, *PBITPOS, *PBITREGION_START and *PBITREGION_END.
5016 : : Otherwise return NULL, *PBITPOS should be still valid even for that
5017 : : case. */
5018 : :
5019 : : static tree
5020 : 5192733 : mem_valid_for_store_merging (tree mem, poly_uint64 *pbitsize,
5021 : : poly_uint64 *pbitpos,
5022 : : poly_uint64 *pbitregion_start,
5023 : : poly_uint64 *pbitregion_end)
5024 : : {
5025 : 5192733 : poly_int64 bitsize, bitpos;
5026 : 5192733 : poly_uint64 bitregion_start = 0, bitregion_end = 0;
5027 : 5192733 : machine_mode mode;
5028 : 5192733 : int unsignedp = 0, reversep = 0, volatilep = 0;
5029 : 5192733 : tree offset;
5030 : 5192733 : tree base_addr = get_inner_reference (mem, &bitsize, &bitpos, &offset, &mode,
5031 : : &unsignedp, &reversep, &volatilep);
5032 : 5192733 : *pbitsize = bitsize;
5033 : 5192733 : if (known_le (bitsize, 0))
5034 : : return NULL_TREE;
5035 : :
5036 : 5191728 : if (TREE_CODE (mem) == COMPONENT_REF
5037 : 5191728 : && DECL_BIT_FIELD_TYPE (TREE_OPERAND (mem, 1)))
5038 : : {
5039 : 28253 : get_bit_range (&bitregion_start, &bitregion_end, mem, &bitpos, &offset);
5040 : 28253 : if (maybe_ne (bitregion_end, 0U))
5041 : 28253 : bitregion_end += 1;
5042 : : }
5043 : :
5044 : 5191728 : if (reversep)
5045 : : return NULL_TREE;
5046 : :
5047 : : /* We do not want to rewrite TARGET_MEM_REFs. */
5048 : 5191263 : if (TREE_CODE (base_addr) == TARGET_MEM_REF)
5049 : : return NULL_TREE;
5050 : : /* In some cases get_inner_reference may return a
5051 : : MEM_REF [ptr + byteoffset]. For the purposes of this pass
5052 : : canonicalize the base_addr to MEM_REF [ptr] and take
5053 : : byteoffset into account in the bitpos. This occurs in
5054 : : PR 23684 and this way we can catch more chains. */
5055 : 5153801 : else if (TREE_CODE (base_addr) == MEM_REF)
5056 : : {
5057 : 914702 : if (!adjust_bit_pos (mem_ref_offset (base_addr), &bitpos,
5058 : : &bitregion_start, &bitregion_end))
5059 : : return NULL_TREE;
5060 : 908214 : base_addr = TREE_OPERAND (base_addr, 0);
5061 : : }
5062 : : /* get_inner_reference returns the base object, get at its
5063 : : address now. */
5064 : : else
5065 : : {
5066 : 4239099 : if (maybe_lt (bitpos, 0))
5067 : : return NULL_TREE;
5068 : 4238834 : base_addr = build_fold_addr_expr (base_addr);
5069 : : }
5070 : :
5071 : 5147048 : if (offset)
5072 : : {
5073 : : /* If the access is variable offset then a base decl has to be
5074 : : address-taken to be able to emit pointer-based stores to it.
5075 : : ??? We might be able to get away with re-using the original
5076 : : base up to the first variable part and then wrapping that inside
5077 : : a BIT_FIELD_REF. */
5078 : 34997 : tree base = get_base_address (base_addr);
5079 : 34997 : if (!base || (DECL_P (base) && !TREE_ADDRESSABLE (base)))
5080 : : return NULL_TREE;
5081 : :
5082 : : /* Similarly to above for the base, remove constant from the offset. */
5083 : 34997 : if (TREE_CODE (offset) == PLUS_EXPR
5084 : 6620 : && TREE_CODE (TREE_OPERAND (offset, 1)) == INTEGER_CST
5085 : 41617 : && adjust_bit_pos (wi::to_poly_offset (TREE_OPERAND (offset, 1)),
5086 : : &bitpos, &bitregion_start, &bitregion_end))
5087 : 6552 : offset = TREE_OPERAND (offset, 0);
5088 : :
5089 : 34997 : base_addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (base_addr),
5090 : : base_addr, offset);
5091 : : }
5092 : :
5093 : 5147048 : if (known_eq (bitregion_end, 0U))
5094 : : {
5095 : 5118993 : bitregion_start = round_down_to_byte_boundary (bitpos);
5096 : 5118993 : bitregion_end = round_up_to_byte_boundary (bitpos + bitsize);
5097 : : }
5098 : :
5099 : 5147048 : *pbitsize = bitsize;
5100 : 5147048 : *pbitpos = bitpos;
5101 : 5147048 : *pbitregion_start = bitregion_start;
5102 : 5147048 : *pbitregion_end = bitregion_end;
5103 : 5147048 : return base_addr;
5104 : : }
5105 : :
5106 : : /* Return true if STMT is a load that can be used for store merging.
5107 : : In that case fill in *OP. BITSIZE, BITPOS, BITREGION_START and
5108 : : BITREGION_END are properties of the corresponding store. */
5109 : :
5110 : : static bool
5111 : 929552 : handled_load (gimple *stmt, store_operand_info *op,
5112 : : poly_uint64 bitsize, poly_uint64 bitpos,
5113 : : poly_uint64 bitregion_start, poly_uint64 bitregion_end)
5114 : : {
5115 : 929552 : if (!is_gimple_assign (stmt))
5116 : : return false;
5117 : 929491 : if (gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR)
5118 : : {
5119 : 966 : tree rhs1 = gimple_assign_rhs1 (stmt);
5120 : 966 : if (TREE_CODE (rhs1) == SSA_NAME
5121 : 966 : && handled_load (SSA_NAME_DEF_STMT (rhs1), op, bitsize, bitpos,
5122 : : bitregion_start, bitregion_end))
5123 : : {
5124 : : /* Don't allow _1 = load; _2 = ~1; _3 = ~_2; which should have
5125 : : been optimized earlier, but if allowed here, would confuse the
5126 : : multiple uses counting. */
5127 : 441 : if (op->bit_not_p)
5128 : : return false;
5129 : 441 : op->bit_not_p = !op->bit_not_p;
5130 : 441 : return true;
5131 : : }
5132 : 525 : return false;
5133 : : }
5134 : 928525 : if (gimple_vuse (stmt)
5135 : 493112 : && gimple_assign_load_p (stmt)
5136 : 493079 : && !stmt_can_throw_internal (cfun, stmt)
5137 : 1418238 : && !gimple_has_volatile_ops (stmt))
5138 : : {
5139 : 489276 : tree mem = gimple_assign_rhs1 (stmt);
5140 : 489276 : op->base_addr
5141 : 489276 : = mem_valid_for_store_merging (mem, &op->bitsize, &op->bitpos,
5142 : : &op->bitregion_start,
5143 : : &op->bitregion_end);
5144 : 489276 : if (op->base_addr != NULL_TREE
5145 : 449491 : && known_eq (op->bitsize, bitsize)
5146 : 898974 : && multiple_p (op->bitpos - bitpos, BITS_PER_UNIT)
5147 : 449483 : && known_ge (op->bitpos - op->bitregion_start,
5148 : : bitpos - bitregion_start)
5149 : 938523 : && known_ge (op->bitregion_end - op->bitpos,
5150 : : bitregion_end - bitpos))
5151 : : {
5152 : 449202 : op->stmt = stmt;
5153 : 449202 : op->val = mem;
5154 : 449202 : op->bit_not_p = false;
5155 : 449202 : return true;
5156 : : }
5157 : : }
5158 : : return false;
5159 : : }
5160 : :
5161 : : /* Return the index number of the landing pad for STMT, if any. */
5162 : :
5163 : : static int
5164 : 2873574 : lp_nr_for_store (gimple *stmt)
5165 : : {
5166 : 2873574 : if (!cfun->can_throw_non_call_exceptions || !cfun->eh)
5167 : : return 0;
5168 : :
5169 : 807678 : if (!stmt_could_throw_p (cfun, stmt))
5170 : : return 0;
5171 : :
5172 : 70965 : return lookup_stmt_eh_lp (stmt);
5173 : : }
5174 : :
5175 : : /* Record the store STMT for store merging optimization if it can be
5176 : : optimized. Return true if any changes were made. */
5177 : :
5178 : : bool
5179 : 4703457 : pass_store_merging::process_store (gimple *stmt)
5180 : : {
5181 : 4703457 : tree lhs = gimple_assign_lhs (stmt);
5182 : 4703457 : tree rhs = gimple_assign_rhs1 (stmt);
5183 : 4703457 : poly_uint64 bitsize, bitpos = 0;
5184 : 4703457 : poly_uint64 bitregion_start = 0, bitregion_end = 0;
5185 : 4703457 : tree base_addr
5186 : 4703457 : = mem_valid_for_store_merging (lhs, &bitsize, &bitpos,
5187 : 4703457 : &bitregion_start, &bitregion_end);
5188 : 4703457 : if (known_eq (bitsize, 0U))
5189 : : return false;
5190 : :
5191 : 4702454 : bool invalid = (base_addr == NULL_TREE
5192 : 4702454 : || (maybe_gt (bitsize,
5193 : : (unsigned int) MAX_BITSIZE_MODE_ANY_INT)
5194 : 157148 : && TREE_CODE (rhs) != INTEGER_CST
5195 : 157148 : && (TREE_CODE (rhs) != CONSTRUCTOR
5196 : 142851 : || CONSTRUCTOR_NELTS (rhs) != 0)));
5197 : 4702454 : enum tree_code rhs_code = ERROR_MARK;
5198 : 4702454 : bool bit_not_p = false;
5199 : 4702454 : struct symbolic_number n;
5200 : 4702454 : gimple *ins_stmt = NULL;
5201 : 14107362 : store_operand_info ops[2];
5202 : 4702454 : if (invalid)
5203 : : ;
5204 : 4683260 : else if (TREE_CODE (rhs) == STRING_CST)
5205 : : {
5206 : 4643 : rhs_code = STRING_CST;
5207 : 4643 : ops[0].val = rhs;
5208 : : }
5209 : 4678617 : else if (rhs_valid_for_store_merging_p (rhs))
5210 : : {
5211 : 2359908 : rhs_code = INTEGER_CST;
5212 : 2359908 : ops[0].val = rhs;
5213 : : }
5214 : 2318709 : else if (TREE_CODE (rhs) == SSA_NAME)
5215 : : {
5216 : 1447771 : gimple *def_stmt = SSA_NAME_DEF_STMT (rhs), *def_stmt1, *def_stmt2;
5217 : 1447771 : if (!is_gimple_assign (def_stmt))
5218 : : invalid = true;
5219 : 911259 : else if (handled_load (def_stmt, &ops[0], bitsize, bitpos,
5220 : : bitregion_start, bitregion_end))
5221 : : rhs_code = MEM_REF;
5222 : 473783 : else if (gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
5223 : : {
5224 : 416 : tree rhs1 = gimple_assign_rhs1 (def_stmt);
5225 : 416 : if (TREE_CODE (rhs1) == SSA_NAME
5226 : 416 : && is_gimple_assign (SSA_NAME_DEF_STMT (rhs1)))
5227 : : {
5228 : : bit_not_p = true;
5229 : : def_stmt = SSA_NAME_DEF_STMT (rhs1);
5230 : : }
5231 : : }
5232 : :
5233 : 1447771 : if (rhs_code == ERROR_MARK && !invalid)
5234 : 473783 : switch ((rhs_code = gimple_assign_rhs_code (def_stmt)))
5235 : : {
5236 : 13845 : case BIT_AND_EXPR:
5237 : 13845 : case BIT_IOR_EXPR:
5238 : 13845 : case BIT_XOR_EXPR:
5239 : 13845 : tree rhs1, rhs2;
5240 : 13845 : rhs1 = gimple_assign_rhs1 (def_stmt);
5241 : 13845 : rhs2 = gimple_assign_rhs2 (def_stmt);
5242 : 13845 : invalid = true;
5243 : 13845 : if (TREE_CODE (rhs1) != SSA_NAME)
5244 : : break;
5245 : 13845 : def_stmt1 = SSA_NAME_DEF_STMT (rhs1);
5246 : 13845 : if (!is_gimple_assign (def_stmt1)
5247 : 13845 : || !handled_load (def_stmt1, &ops[0], bitsize, bitpos,
5248 : : bitregion_start, bitregion_end))
5249 : : break;
5250 : 8148 : if (rhs_valid_for_store_merging_p (rhs2))
5251 : 3659 : ops[1].val = rhs2;
5252 : 4489 : else if (TREE_CODE (rhs2) != SSA_NAME)
5253 : : break;
5254 : : else
5255 : : {
5256 : 4489 : def_stmt2 = SSA_NAME_DEF_STMT (rhs2);
5257 : 4489 : if (!is_gimple_assign (def_stmt2))
5258 : : break;
5259 : 4386 : else if (!handled_load (def_stmt2, &ops[1], bitsize, bitpos,
5260 : : bitregion_start, bitregion_end))
5261 : : break;
5262 : : }
5263 : : invalid = false;
5264 : : break;
5265 : : default:
5266 : : invalid = true;
5267 : : break;
5268 : : }
5269 : :
5270 : 1447771 : unsigned HOST_WIDE_INT const_bitsize;
5271 : 1447771 : if (bitsize.is_constant (&const_bitsize)
5272 : 1447771 : && (const_bitsize % BITS_PER_UNIT) == 0
5273 : 1440740 : && const_bitsize <= 64
5274 : 1279831 : && multiple_p (bitpos, BITS_PER_UNIT))
5275 : : {
5276 : 1279568 : ins_stmt = find_bswap_or_nop_1 (def_stmt, &n, 12);
5277 : 1279568 : if (ins_stmt)
5278 : : {
5279 : 426054 : uint64_t nn = n.n;
5280 : 426054 : for (unsigned HOST_WIDE_INT i = 0;
5281 : 3030361 : i < const_bitsize;
5282 : 2604307 : i += BITS_PER_UNIT, nn >>= BITS_PER_MARKER)
5283 : 2612941 : if ((nn & MARKER_MASK) == 0
5284 : 2612941 : || (nn & MARKER_MASK) == MARKER_BYTE_UNKNOWN)
5285 : : {
5286 : : ins_stmt = NULL;
5287 : : break;
5288 : : }
5289 : 426054 : if (ins_stmt)
5290 : : {
5291 : 417420 : if (invalid)
5292 : : {
5293 : 57939 : rhs_code = LROTATE_EXPR;
5294 : 57939 : ops[0].base_addr = NULL_TREE;
5295 : 57939 : ops[1].base_addr = NULL_TREE;
5296 : : }
5297 : : invalid = false;
5298 : : }
5299 : : }
5300 : : }
5301 : :
5302 : 1447771 : if (invalid
5303 : 945119 : && bitsize.is_constant (&const_bitsize)
5304 : 945119 : && ((const_bitsize % BITS_PER_UNIT) != 0
5305 : 939011 : || !multiple_p (bitpos, BITS_PER_UNIT))
5306 : 1460513 : && const_bitsize <= MAX_FIXED_MODE_SIZE)
5307 : : {
5308 : : /* Bypass a conversion to the bit-field type. */
5309 : 6371 : if (!bit_not_p
5310 : 6371 : && is_gimple_assign (def_stmt)
5311 : 12165 : && CONVERT_EXPR_CODE_P (rhs_code))
5312 : : {
5313 : 4607 : tree rhs1 = gimple_assign_rhs1 (def_stmt);
5314 : 4607 : if (TREE_CODE (rhs1) == SSA_NAME
5315 : 4607 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
5316 : : rhs = rhs1;
5317 : : }
5318 : 6371 : rhs_code = BIT_INSERT_EXPR;
5319 : 6371 : bit_not_p = false;
5320 : 6371 : ops[0].val = rhs;
5321 : 6371 : ops[0].base_addr = NULL_TREE;
5322 : 6371 : ops[1].base_addr = NULL_TREE;
5323 : 6371 : invalid = false;
5324 : : }
5325 : : }
5326 : : else
5327 : : invalid = true;
5328 : :
5329 : 4702454 : unsigned HOST_WIDE_INT const_bitsize, const_bitpos;
5330 : 4702454 : unsigned HOST_WIDE_INT const_bitregion_start, const_bitregion_end;
5331 : 4702454 : if (invalid
5332 : 2873574 : || !bitsize.is_constant (&const_bitsize)
5333 : 2873574 : || !bitpos.is_constant (&const_bitpos)
5334 : 2873574 : || !bitregion_start.is_constant (&const_bitregion_start)
5335 : 4702454 : || !bitregion_end.is_constant (&const_bitregion_end))
5336 : 1828880 : return terminate_all_aliasing_chains (NULL, stmt);
5337 : :
5338 : 2873574 : if (!ins_stmt)
5339 : 2456154 : memset (&n, 0, sizeof (n));
5340 : :
5341 : 2873574 : class imm_store_chain_info **chain_info = NULL;
5342 : 2873574 : bool ret = false;
5343 : 2873574 : if (base_addr)
5344 : 2873574 : chain_info = m_stores.get (base_addr);
5345 : :
5346 : 2873574 : store_immediate_info *info;
5347 : 2873574 : if (chain_info)
5348 : : {
5349 : 1082116 : unsigned int ord = (*chain_info)->m_store_info.length ();
5350 : 2164232 : info = new store_immediate_info (const_bitsize, const_bitpos,
5351 : : const_bitregion_start,
5352 : : const_bitregion_end,
5353 : : stmt, ord, rhs_code, n, ins_stmt,
5354 : : bit_not_p, lp_nr_for_store (stmt),
5355 : 1082116 : ops[0], ops[1]);
5356 : 1082116 : if (dump_file && (dump_flags & TDF_DETAILS))
5357 : : {
5358 : 208 : fprintf (dump_file, "Recording immediate store from stmt:\n");
5359 : 208 : print_gimple_stmt (dump_file, stmt, 0);
5360 : : }
5361 : 1082116 : (*chain_info)->m_store_info.safe_push (info);
5362 : 1082116 : m_n_stores++;
5363 : 1082116 : ret |= terminate_all_aliasing_chains (chain_info, stmt);
5364 : : /* If we reach the limit of stores to merge in a chain terminate and
5365 : : process the chain now. */
5366 : 1082116 : if ((*chain_info)->m_store_info.length ()
5367 : 1082116 : == (unsigned int) param_max_stores_to_merge)
5368 : : {
5369 : 446 : if (dump_file && (dump_flags & TDF_DETAILS))
5370 : 0 : fprintf (dump_file,
5371 : : "Reached maximum number of statements to merge:\n");
5372 : 446 : ret |= terminate_and_process_chain (*chain_info);
5373 : : }
5374 : : }
5375 : : else
5376 : : {
5377 : : /* Store aliases any existing chain? */
5378 : 1791458 : ret |= terminate_all_aliasing_chains (NULL, stmt);
5379 : :
5380 : : /* Start a new chain. */
5381 : 1791458 : class imm_store_chain_info *new_chain
5382 : 1791458 : = new imm_store_chain_info (m_stores_head, base_addr);
5383 : 3582916 : info = new store_immediate_info (const_bitsize, const_bitpos,
5384 : : const_bitregion_start,
5385 : : const_bitregion_end,
5386 : : stmt, 0, rhs_code, n, ins_stmt,
5387 : : bit_not_p, lp_nr_for_store (stmt),
5388 : 1791458 : ops[0], ops[1]);
5389 : 1791458 : new_chain->m_store_info.safe_push (info);
5390 : 1791458 : m_n_stores++;
5391 : 1791458 : m_stores.put (base_addr, new_chain);
5392 : 1791458 : m_n_chains++;
5393 : 1791458 : if (dump_file && (dump_flags & TDF_DETAILS))
5394 : : {
5395 : 53 : fprintf (dump_file, "Starting active chain number %u with statement:\n",
5396 : : m_n_chains);
5397 : 53 : print_gimple_stmt (dump_file, stmt, 0);
5398 : 53 : fprintf (dump_file, "The base object is:\n");
5399 : 53 : print_generic_expr (dump_file, base_addr);
5400 : 53 : fprintf (dump_file, "\n");
5401 : : }
5402 : : }
5403 : :
5404 : : /* Prune oldest chains so that after adding the chain or store above
5405 : : we're again within the limits set by the params. */
5406 : 2873574 : if (m_n_chains > (unsigned)param_max_store_chains_to_track
5407 : 2871040 : || m_n_stores > (unsigned)param_max_stores_to_track)
5408 : : {
5409 : 2543 : if (dump_file && (dump_flags & TDF_DETAILS))
5410 : 0 : fprintf (dump_file, "Too many chains (%u > %d) or stores (%u > %d), "
5411 : : "terminating oldest chain(s).\n", m_n_chains,
5412 : : param_max_store_chains_to_track, m_n_stores,
5413 : : param_max_stores_to_track);
5414 : 2543 : imm_store_chain_info **e = &m_stores_head;
5415 : 2543 : unsigned idx = 0;
5416 : 2543 : unsigned n_stores = 0;
5417 : 167012 : while (*e)
5418 : : {
5419 : 164469 : if (idx >= (unsigned)param_max_store_chains_to_track
5420 : 164469 : || (n_stores + (*e)->m_store_info.length ()
5421 : 161935 : > (unsigned)param_max_stores_to_track))
5422 : 2543 : ret |= terminate_and_process_chain (*e);
5423 : : else
5424 : : {
5425 : 161926 : n_stores += (*e)->m_store_info.length ();
5426 : 161926 : e = &(*e)->next;
5427 : 161926 : ++idx;
5428 : : }
5429 : : }
5430 : : }
5431 : :
5432 : : return ret;
5433 : : }
5434 : :
5435 : : /* Return true if STMT is a store valid for store merging. */
5436 : :
5437 : : static bool
5438 : 32868167 : store_valid_for_store_merging_p (gimple *stmt)
5439 : : {
5440 : 32868167 : return gimple_assign_single_p (stmt)
5441 : 15300997 : && gimple_vdef (stmt)
5442 : 8736051 : && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt))
5443 : 41386137 : && (!gimple_has_volatile_ops (stmt) || gimple_clobber_p (stmt));
5444 : : }
5445 : :
5446 : : enum basic_block_status { BB_INVALID, BB_VALID, BB_EXTENDED_VALID };
5447 : :
5448 : : /* Return the status of basic block BB wrt store merging. */
5449 : :
5450 : : static enum basic_block_status
5451 : 8091240 : get_status_for_store_merging (basic_block bb)
5452 : : {
5453 : 8091240 : unsigned int num_statements = 0;
5454 : 8091240 : unsigned int num_constructors = 0;
5455 : 8091240 : gimple_stmt_iterator gsi;
5456 : 8091240 : edge e;
5457 : 8091240 : gimple *last_stmt = NULL;
5458 : :
5459 : 58797369 : for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5460 : : {
5461 : 51728291 : gimple *stmt = gsi_stmt (gsi);
5462 : :
5463 : 51728291 : if (is_gimple_debug (stmt))
5464 : 29093091 : continue;
5465 : :
5466 : 22635200 : last_stmt = stmt;
5467 : :
5468 : 22635200 : if (store_valid_for_store_merging_p (stmt) && ++num_statements >= 2)
5469 : : break;
5470 : :
5471 : 21648377 : if (is_gimple_assign (stmt)
5472 : 21648377 : && gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
5473 : : {
5474 : 617363 : tree rhs = gimple_assign_rhs1 (stmt);
5475 : 617363 : if (VECTOR_TYPE_P (TREE_TYPE (rhs))
5476 : 136702 : && INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs)))
5477 : 745427 : && gimple_assign_lhs (stmt) != NULL_TREE)
5478 : : {
5479 : 128064 : HOST_WIDE_INT sz
5480 : 128064 : = int_size_in_bytes (TREE_TYPE (rhs)) * BITS_PER_UNIT;
5481 : 128064 : if (sz == 16 || sz == 32 || sz == 64)
5482 : : {
5483 : : num_constructors = 1;
5484 : : break;
5485 : : }
5486 : : }
5487 : : }
5488 : : }
5489 : :
5490 : 8091240 : if (num_statements == 0 && num_constructors == 0)
5491 : : return BB_INVALID;
5492 : :
5493 : 933489 : if (cfun->can_throw_non_call_exceptions && cfun->eh
5494 : 933489 : && store_valid_for_store_merging_p (last_stmt)
5495 : 675601 : && (e = find_fallthru_edge (bb->succs))
5496 : 2494183 : && e->dest == bb->next_bb)
5497 : : return BB_EXTENDED_VALID;
5498 : :
5499 : 1924755 : return (num_statements >= 2 || num_constructors) ? BB_VALID : BB_INVALID;
5500 : : }
5501 : :
5502 : : /* Entry point for the pass. Go over each basic block recording chains of
5503 : : immediate stores. Upon encountering a terminating statement (as defined
5504 : : by stmt_terminates_chain_p) process the recorded stores and emit the widened
5505 : : variants. */
5506 : :
5507 : : unsigned int
5508 : 901309 : pass_store_merging::execute (function *fun)
5509 : : {
5510 : 901309 : basic_block bb;
5511 : 901309 : hash_set<gimple *> orig_stmts;
5512 : 901309 : bool changed = false, open_chains = false;
5513 : :
5514 : : /* If the function can throw and catch non-call exceptions, we'll be trying
5515 : : to merge stores across different basic blocks so we need to first unsplit
5516 : : the EH edges in order to streamline the CFG of the function. */
5517 : 901309 : if (cfun->can_throw_non_call_exceptions && cfun->eh)
5518 : 240917 : unsplit_eh_edges ();
5519 : :
5520 : 901309 : calculate_dominance_info (CDI_DOMINATORS);
5521 : :
5522 : 8992549 : FOR_EACH_BB_FN (bb, fun)
5523 : : {
5524 : 8091240 : const basic_block_status bb_status = get_status_for_store_merging (bb);
5525 : 8091240 : gimple_stmt_iterator gsi;
5526 : :
5527 : 8139110 : if (open_chains && (bb_status == BB_INVALID || !single_pred_p (bb)))
5528 : : {
5529 : 126583 : changed |= terminate_and_process_all_chains ();
5530 : 126583 : open_chains = false;
5531 : : }
5532 : :
5533 : 8091240 : if (bb_status == BB_INVALID)
5534 : 7014113 : continue;
5535 : :
5536 : 1077127 : if (dump_file && (dump_flags & TDF_DETAILS))
5537 : 25 : fprintf (dump_file, "Processing basic block <%d>:\n", bb->index);
5538 : :
5539 : 24541162 : for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
5540 : : {
5541 : 23464035 : gimple *stmt = gsi_stmt (gsi);
5542 : 23464035 : gsi_next (&gsi);
5543 : :
5544 : 23464035 : if (is_gimple_debug (stmt))
5545 : 14148453 : continue;
5546 : :
5547 : 18200397 : if (gimple_has_volatile_ops (stmt) && !gimple_clobber_p (stmt))
5548 : : {
5549 : : /* Terminate all chains. */
5550 : 10874 : if (dump_file && (dump_flags & TDF_DETAILS))
5551 : 1 : fprintf (dump_file, "Volatile access terminates "
5552 : : "all chains\n");
5553 : 10874 : changed |= terminate_and_process_all_chains ();
5554 : 10874 : open_chains = false;
5555 : 10874 : continue;
5556 : : }
5557 : :
5558 : 9304708 : if (is_gimple_assign (stmt)
5559 : 7536190 : && gimple_assign_rhs_code (stmt) == CONSTRUCTOR
5560 : 10436821 : && maybe_optimize_vector_constructor (stmt))
5561 : 5230 : continue;
5562 : :
5563 : 9299478 : if (store_valid_for_store_merging_p (stmt))
5564 : 4703457 : changed |= process_store (stmt);
5565 : : else
5566 : 4596021 : changed |= terminate_all_aliasing_chains (NULL, stmt);
5567 : : }
5568 : :
5569 : 1077127 : if (bb_status == BB_EXTENDED_VALID)
5570 : : open_chains = true;
5571 : : else
5572 : : {
5573 : 924158 : changed |= terminate_and_process_all_chains ();
5574 : 924158 : open_chains = false;
5575 : : }
5576 : : }
5577 : :
5578 : 901309 : if (open_chains)
5579 : 0 : changed |= terminate_and_process_all_chains ();
5580 : :
5581 : : /* If the function can throw and catch non-call exceptions and something
5582 : : changed during the pass, then the CFG has (very likely) changed too. */
5583 : 901309 : if (cfun->can_throw_non_call_exceptions && cfun->eh && changed)
5584 : : {
5585 : 731 : free_dominance_info (CDI_DOMINATORS);
5586 : 731 : return TODO_cleanup_cfg;
5587 : : }
5588 : :
5589 : : return 0;
5590 : 901309 : }
5591 : :
5592 : : } // anon namespace
5593 : :
5594 : : /* Construct and return a store merging pass object. */
5595 : :
5596 : : gimple_opt_pass *
5597 : 280455 : make_pass_store_merging (gcc::context *ctxt)
5598 : : {
5599 : 280455 : return new pass_store_merging (ctxt);
5600 : : }
5601 : :
5602 : : #if CHECKING_P
5603 : :
5604 : : namespace selftest {
5605 : :
5606 : : /* Selftests for store merging helpers. */
5607 : :
5608 : : /* Assert that all elements of the byte arrays X and Y, both of length N
5609 : : are equal. */
5610 : :
5611 : : static void
5612 : 32 : verify_array_eq (unsigned char *x, unsigned char *y, unsigned int n)
5613 : : {
5614 : 112 : for (unsigned int i = 0; i < n; i++)
5615 : : {
5616 : 80 : if (x[i] != y[i])
5617 : : {
5618 : 0 : fprintf (stderr, "Arrays do not match. X:\n");
5619 : 0 : dump_char_array (stderr, x, n);
5620 : 0 : fprintf (stderr, "Y:\n");
5621 : 0 : dump_char_array (stderr, y, n);
5622 : : }
5623 : 80 : ASSERT_EQ (x[i], y[i]);
5624 : : }
5625 : 32 : }
5626 : :
5627 : : /* Test shift_bytes_in_array_left and that it carries bits across between
5628 : : bytes correctly. */
5629 : :
5630 : : static void
5631 : 4 : verify_shift_bytes_in_array_left (void)
5632 : : {
5633 : : /* byte 1 | byte 0
5634 : : 00011111 | 11100000. */
5635 : 4 : unsigned char orig[2] = { 0xe0, 0x1f };
5636 : 4 : unsigned char in[2];
5637 : 4 : memcpy (in, orig, sizeof orig);
5638 : :
5639 : 4 : unsigned char expected[2] = { 0x80, 0x7f };
5640 : 4 : shift_bytes_in_array_left (in, sizeof (in), 2);
5641 : 4 : verify_array_eq (in, expected, sizeof (in));
5642 : :
5643 : 4 : memcpy (in, orig, sizeof orig);
5644 : 4 : memcpy (expected, orig, sizeof orig);
5645 : : /* Check that shifting by zero doesn't change anything. */
5646 : 4 : shift_bytes_in_array_left (in, sizeof (in), 0);
5647 : 4 : verify_array_eq (in, expected, sizeof (in));
5648 : :
5649 : 4 : }
5650 : :
5651 : : /* Test shift_bytes_in_array_right and that it carries bits across between
5652 : : bytes correctly. */
5653 : :
5654 : : static void
5655 : 4 : verify_shift_bytes_in_array_right (void)
5656 : : {
5657 : : /* byte 1 | byte 0
5658 : : 00011111 | 11100000. */
5659 : 4 : unsigned char orig[2] = { 0x1f, 0xe0};
5660 : 4 : unsigned char in[2];
5661 : 4 : memcpy (in, orig, sizeof orig);
5662 : 4 : unsigned char expected[2] = { 0x07, 0xf8};
5663 : 4 : shift_bytes_in_array_right (in, sizeof (in), 2);
5664 : 4 : verify_array_eq (in, expected, sizeof (in));
5665 : :
5666 : 4 : memcpy (in, orig, sizeof orig);
5667 : 4 : memcpy (expected, orig, sizeof orig);
5668 : : /* Check that shifting by zero doesn't change anything. */
5669 : 4 : shift_bytes_in_array_right (in, sizeof (in), 0);
5670 : 4 : verify_array_eq (in, expected, sizeof (in));
5671 : 4 : }
5672 : :
5673 : : /* Test clear_bit_region that it clears exactly the bits asked and
5674 : : nothing more. */
5675 : :
5676 : : static void
5677 : 4 : verify_clear_bit_region (void)
5678 : : {
5679 : : /* Start with all bits set and test clearing various patterns in them. */
5680 : 4 : unsigned char orig[3] = { 0xff, 0xff, 0xff};
5681 : 4 : unsigned char in[3];
5682 : 4 : unsigned char expected[3];
5683 : 4 : memcpy (in, orig, sizeof in);
5684 : :
5685 : : /* Check zeroing out all the bits. */
5686 : 4 : clear_bit_region (in, 0, 3 * BITS_PER_UNIT);
5687 : 4 : expected[0] = expected[1] = expected[2] = 0;
5688 : 4 : verify_array_eq (in, expected, sizeof in);
5689 : :
5690 : 4 : memcpy (in, orig, sizeof in);
5691 : : /* Leave the first and last bits intact. */
5692 : 4 : clear_bit_region (in, 1, 3 * BITS_PER_UNIT - 2);
5693 : 4 : expected[0] = 0x1;
5694 : 4 : expected[1] = 0;
5695 : 4 : expected[2] = 0x80;
5696 : 4 : verify_array_eq (in, expected, sizeof in);
5697 : 4 : }
5698 : :
5699 : : /* Test clear_bit_region_be that it clears exactly the bits asked and
5700 : : nothing more. */
5701 : :
5702 : : static void
5703 : 4 : verify_clear_bit_region_be (void)
5704 : : {
5705 : : /* Start with all bits set and test clearing various patterns in them. */
5706 : 4 : unsigned char orig[3] = { 0xff, 0xff, 0xff};
5707 : 4 : unsigned char in[3];
5708 : 4 : unsigned char expected[3];
5709 : 4 : memcpy (in, orig, sizeof in);
5710 : :
5711 : : /* Check zeroing out all the bits. */
5712 : 4 : clear_bit_region_be (in, BITS_PER_UNIT - 1, 3 * BITS_PER_UNIT);
5713 : 4 : expected[0] = expected[1] = expected[2] = 0;
5714 : 4 : verify_array_eq (in, expected, sizeof in);
5715 : :
5716 : 4 : memcpy (in, orig, sizeof in);
5717 : : /* Leave the first and last bits intact. */
5718 : 4 : clear_bit_region_be (in, BITS_PER_UNIT - 2, 3 * BITS_PER_UNIT - 2);
5719 : 4 : expected[0] = 0x80;
5720 : 4 : expected[1] = 0;
5721 : 4 : expected[2] = 0x1;
5722 : 4 : verify_array_eq (in, expected, sizeof in);
5723 : 4 : }
5724 : :
5725 : :
5726 : : /* Run all of the selftests within this file. */
5727 : :
5728 : : void
5729 : 4 : store_merging_cc_tests (void)
5730 : : {
5731 : 4 : verify_shift_bytes_in_array_left ();
5732 : 4 : verify_shift_bytes_in_array_right ();
5733 : 4 : verify_clear_bit_region ();
5734 : 4 : verify_clear_bit_region_be ();
5735 : 4 : }
5736 : :
5737 : : } // namespace selftest
5738 : : #endif /* CHECKING_P. */
|