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