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 271047 : do_shift_rotate (enum tree_code code,
261 : struct symbolic_number *n,
262 : int count)
263 : {
264 271047 : int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
265 271047 : uint64_t head_marker;
266 :
267 271047 : if (count < 0
268 271047 : || count >= TYPE_PRECISION (n->type)
269 542094 : || count % BITS_PER_UNIT != 0)
270 : return false;
271 226853 : 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 226853 : if (size < 64 / BITS_PER_MARKER)
276 82061 : n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
277 :
278 226853 : switch (code)
279 : {
280 208035 : case LSHIFT_EXPR:
281 208035 : n->n <<= count;
282 208035 : break;
283 15095 : case RSHIFT_EXPR:
284 15095 : head_marker = HEAD_MARKER (n->n, size);
285 15095 : n->n >>= count;
286 : /* Arithmetic shift of signed type: result is dependent on the value. */
287 15095 : 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 226853 : if (size < 64 / BITS_PER_MARKER)
303 82061 : 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 329400 : verify_symbolic_number_p (struct symbolic_number *n, gimple *stmt)
312 : {
313 329400 : tree lhs_type;
314 :
315 329400 : lhs_type = TREE_TYPE (gimple_get_lhs (stmt));
316 :
317 329400 : if (TREE_CODE (lhs_type) != INTEGER_TYPE
318 329400 : && TREE_CODE (lhs_type) != ENUMERAL_TYPE)
319 : return false;
320 :
321 318858 : 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 1174406 : init_symbolic_number (struct symbolic_number *n, tree src)
332 : {
333 1174406 : int size;
334 :
335 1174406 : if (!INTEGRAL_TYPE_P (TREE_TYPE (src)) && !POINTER_TYPE_P (TREE_TYPE (src)))
336 : return false;
337 :
338 1024575 : n->base_addr = n->offset = n->alias_set = n->vuse = NULL_TREE;
339 1024575 : 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 1024575 : n->type = TREE_TYPE (src);
345 1024575 : size = TYPE_PRECISION (n->type);
346 1024575 : if (size % BITS_PER_UNIT != 0)
347 : return false;
348 1008882 : size /= BITS_PER_UNIT;
349 1008882 : if (size > 64 / BITS_PER_MARKER)
350 : return false;
351 999136 : n->range = size;
352 999136 : n->n = CMPNOP;
353 999136 : n->n_ops = 1;
354 :
355 999136 : if (size < 64 / BITS_PER_MARKER)
356 466004 : 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 5285987 : 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 5285987 : poly_int64 bitsize, bitpos, bytepos;
371 5285987 : machine_mode mode;
372 5285987 : int unsignedp, reversep, volatilep;
373 5285987 : tree offset, base_addr;
374 :
375 : /* Not prepared to handle PDP endian. */
376 5285987 : if (BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN)
377 : return false;
378 :
379 6239058 : if (!gimple_assign_load_p (stmt) || gimple_has_volatile_ops (stmt))
380 : return false;
381 :
382 947712 : base_addr = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
383 : &unsignedp, &reversep, &volatilep);
384 :
385 947712 : if (TREE_CODE (base_addr) == TARGET_MEM_REF)
386 : /* Do not rewrite TARGET_MEM_REF. */
387 : return false;
388 898528 : else if (TREE_CODE (base_addr) == MEM_REF)
389 : {
390 491258 : poly_offset_int bit_offset = 0;
391 491258 : tree off = TREE_OPERAND (base_addr, 1);
392 :
393 491258 : if (!integer_zerop (off))
394 : {
395 109967 : poly_offset_int boff = mem_ref_offset (base_addr);
396 109967 : boff <<= LOG2_BITS_PER_UNIT;
397 109967 : bit_offset += boff;
398 : }
399 :
400 491258 : base_addr = TREE_OPERAND (base_addr, 0);
401 :
402 : /* Avoid returning a negative bitpos as this may wreak havoc later. */
403 491258 : if (maybe_lt (bit_offset, 0))
404 : {
405 3954 : tree byte_offset = wide_int_to_tree
406 3954 : (sizetype, bits_to_bytes_round_down (bit_offset));
407 3954 : bit_offset = num_trailing_bits (bit_offset);
408 3954 : if (offset)
409 0 : offset = size_binop (PLUS_EXPR, offset, byte_offset);
410 : else
411 3954 : offset = byte_offset;
412 : }
413 :
414 491258 : bitpos += bit_offset.force_shwi ();
415 : }
416 : else
417 407270 : base_addr = build_fold_addr_expr (base_addr);
418 :
419 898528 : if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
420 : return false;
421 897566 : if (!multiple_p (bitsize, BITS_PER_UNIT))
422 : return false;
423 896206 : if (reversep)
424 : return false;
425 :
426 896197 : if (!init_symbolic_number (n, ref))
427 : return false;
428 758061 : n->base_addr = base_addr;
429 758061 : n->offset = offset;
430 758061 : n->bytepos = bytepos;
431 758061 : n->alias_set = reference_alias_ptr_type (ref);
432 758061 : n->vuse = gimple_vuse (stmt);
433 758061 : 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 220882 : 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 220882 : int i, size;
446 220882 : uint64_t mask;
447 220882 : gimple *source_stmt;
448 220882 : struct symbolic_number *n_start;
449 :
450 220882 : tree rhs1 = gimple_assign_rhs1 (source_stmt1);
451 220882 : if (TREE_CODE (rhs1) == BIT_FIELD_REF
452 220882 : && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
453 385 : rhs1 = TREE_OPERAND (rhs1, 0);
454 220882 : tree rhs2 = gimple_assign_rhs1 (source_stmt2);
455 220882 : if (TREE_CODE (rhs2) == BIT_FIELD_REF
456 220882 : && 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 220882 : if (rhs1 != rhs2)
462 : {
463 159376 : uint64_t inc;
464 159376 : HOST_WIDE_INT start1, start2, start_sub, end_sub, end1, end2, end;
465 159376 : struct symbolic_number *toinc_n_ptr, *n_end;
466 159376 : basic_block bb1, bb2;
467 :
468 132955 : if (!n1->base_addr || !n2->base_addr
469 292319 : || !operand_equal_p (n1->base_addr, n2->base_addr, 0))
470 220882 : return NULL;
471 :
472 74123 : if (!n1->offset != !n2->offset
473 74123 : || (n1->offset && !operand_equal_p (n1->offset, n2->offset, 0)))
474 : return NULL;
475 :
476 65292 : start1 = 0;
477 65292 : if (!(n2->bytepos - n1->bytepos).is_constant (&start2))
478 : return NULL;
479 :
480 65292 : if (start1 < start2)
481 : {
482 : n_start = n1;
483 : start_sub = start2 - start1;
484 : }
485 : else
486 : {
487 14856 : n_start = n2;
488 14856 : start_sub = start1 - start2;
489 : }
490 :
491 65292 : bb1 = gimple_bb (source_stmt1);
492 65292 : bb2 = gimple_bb (source_stmt2);
493 65292 : if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
494 : source_stmt = source_stmt1;
495 : else
496 4669 : source_stmt = source_stmt2;
497 :
498 : /* Find the highest address at which a load is performed and
499 : compute related info. */
500 65292 : end1 = start1 + (n1->range - 1);
501 65292 : end2 = start2 + (n2->range - 1);
502 65292 : if (end1 < end2)
503 : {
504 65292 : end = end2;
505 : end_sub = end2 - end1;
506 : }
507 : else
508 : {
509 : end = end1;
510 : end_sub = end1 - end2;
511 : }
512 65292 : n_end = (end2 > end1) ? n2 : n1;
513 :
514 : /* Find symbolic number whose lsb is the most significant. */
515 65292 : if (BYTES_BIG_ENDIAN)
516 : toinc_n_ptr = (n_end == n1) ? n2 : n1;
517 : else
518 65292 : toinc_n_ptr = (n_start == n1) ? n2 : n1;
519 :
520 65292 : 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 65292 : 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 50106 : inc = BYTES_BIG_ENDIAN ? end_sub : start_sub;
530 50106 : size = TYPE_PRECISION (n1->type) / BITS_PER_UNIT;
531 393984 : for (i = 0; i < size; i++, inc <<= BITS_PER_MARKER)
532 : {
533 343878 : unsigned marker
534 343878 : = (toinc_n_ptr->n >> (i * BITS_PER_MARKER)) & MARKER_MASK;
535 343878 : if (marker && marker != MARKER_BYTE_UNKNOWN)
536 132429 : toinc_n_ptr->n += inc;
537 : }
538 : }
539 : else
540 : {
541 61506 : n->range = n1->range;
542 61506 : n_start = n1;
543 61506 : source_stmt = source_stmt1;
544 : }
545 :
546 111612 : if (!n1->alias_set
547 111612 : || alias_ptr_types_compatible_p (n1->alias_set, n2->alias_set))
548 103512 : n->alias_set = n1->alias_set;
549 : else
550 8100 : n->alias_set = ptr_type_node;
551 111612 : n->vuse = n_start->vuse;
552 111612 : n->base_addr = n_start->base_addr;
553 111612 : n->offset = n_start->offset;
554 111612 : n->src = n_start->src;
555 111612 : n->bytepos = n_start->bytepos;
556 111612 : n->type = n_start->type;
557 111612 : size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
558 111612 : uint64_t res_n = n1->n | n2->n;
559 :
560 838951 : for (i = 0, mask = MARKER_MASK; i < size; i++, mask <<= BITS_PER_MARKER)
561 : {
562 728717 : uint64_t masked1, masked2;
563 :
564 728717 : masked1 = n1->n & mask;
565 728717 : masked2 = n2->n & mask;
566 : /* If at least one byte is 0, all of 0 | x == 0 ^ x == 0 + x == x. */
567 728717 : if (masked1 && masked2)
568 : {
569 : /* + can carry into upper bits, just punt. */
570 6523 : if (code == PLUS_EXPR)
571 : return NULL;
572 : /* x | x is still x. */
573 5145 : if (code == BIT_IOR_EXPR && masked1 == masked2)
574 212 : continue;
575 4933 : 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 4871 : res_n |= mask;
590 : }
591 : }
592 110234 : n->n = res_n;
593 110234 : n->n_ops = n1->n_ops + n2->n_ops;
594 :
595 110234 : 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 6289807 : find_bswap_or_nop_1 (gimple *stmt, struct symbolic_number *n, int limit)
606 : {
607 6289807 : enum tree_code code;
608 6289807 : tree rhs1, rhs2 = NULL;
609 6289807 : gimple *rhs1_stmt, *rhs2_stmt, *source_stmt1;
610 6289807 : enum gimple_rhs_class rhs_class;
611 :
612 6289807 : if (!limit
613 6245565 : || !is_gimple_assign (stmt)
614 11582815 : || stmt_can_throw_internal (cfun, stmt))
615 : return NULL;
616 :
617 5285987 : rhs1 = gimple_assign_rhs1 (stmt);
618 :
619 5285987 : if (find_bswap_or_nop_load (stmt, rhs1, n))
620 : return stmt;
621 :
622 : /* Handle BIT_FIELD_REF. */
623 4527926 : if (TREE_CODE (rhs1) == BIT_FIELD_REF
624 4527926 : && TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME)
625 : {
626 10188 : if (!tree_fits_uhwi_p (TREE_OPERAND (rhs1, 1))
627 10188 : || !tree_fits_uhwi_p (TREE_OPERAND (rhs1, 2)))
628 : return NULL;
629 :
630 10188 : unsigned HOST_WIDE_INT bitsize = tree_to_uhwi (TREE_OPERAND (rhs1, 1));
631 10188 : unsigned HOST_WIDE_INT bitpos = tree_to_uhwi (TREE_OPERAND (rhs1, 2));
632 10188 : if (bitpos % BITS_PER_UNIT == 0
633 10188 : && bitsize % BITS_PER_UNIT == 0
634 20376 : && 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 4517738 : if (TREE_CODE (rhs1) != SSA_NAME)
665 : return NULL;
666 :
667 4202711 : code = gimple_assign_rhs_code (stmt);
668 4202711 : rhs_class = gimple_assign_rhs_class (stmt);
669 4202711 : rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
670 :
671 4202711 : if (rhs_class == GIMPLE_BINARY_RHS)
672 3883347 : rhs2 = gimple_assign_rhs2 (stmt);
673 :
674 : /* Handle unary rhs and binary rhs with integer constants as second
675 : operand. */
676 :
677 4202711 : if (rhs_class == GIMPLE_UNARY_RHS
678 3887232 : || (rhs_class == GIMPLE_BINARY_RHS
679 3883347 : && TREE_CODE (rhs2) == INTEGER_CST))
680 : {
681 2010839 : if (code != BIT_AND_EXPR
682 2010839 : && code != LSHIFT_EXPR
683 : && code != RSHIFT_EXPR
684 1934719 : && code != LROTATE_EXPR
685 1883582 : && code != RROTATE_EXPR
686 1877030 : && !CONVERT_EXPR_CODE_P (code))
687 : return NULL;
688 :
689 408661 : 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 408661 : if (!source_stmt1)
694 : {
695 268021 : if (gimple_assign_load_p (stmt)
696 268021 : || !init_symbolic_number (n, rhs1))
697 : return NULL;
698 : source_stmt1 = stmt;
699 : }
700 :
701 381155 : switch (code)
702 : {
703 40217 : case BIT_AND_EXPR:
704 40217 : {
705 40217 : int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
706 40217 : uint64_t val = int_cst_value (rhs2), mask = 0;
707 40217 : uint64_t tmp = (1 << BITS_PER_UNIT) - 1;
708 :
709 : /* Only constants masking full bytes are allowed. */
710 202062 : for (i = 0; i < size; i++, tmp <<= BITS_PER_UNIT)
711 184695 : if ((val & tmp) != 0 && (val & tmp) != tmp)
712 : return NULL;
713 161845 : else if (val & tmp)
714 83628 : mask |= (uint64_t) MARKER_MASK << (i * BITS_PER_MARKER);
715 :
716 17367 : n->n &= mask;
717 : }
718 17367 : break;
719 88817 : case LSHIFT_EXPR:
720 88817 : case RSHIFT_EXPR:
721 88817 : case LROTATE_EXPR:
722 88817 : case RROTATE_EXPR:
723 88817 : if (!do_shift_rotate (code, n, (int) TREE_INT_CST_LOW (rhs2)))
724 : return NULL;
725 : break;
726 252121 : CASE_CONVERT:
727 252121 : {
728 252121 : int i, type_size, old_type_size;
729 252121 : tree type;
730 :
731 252121 : type = TREE_TYPE (gimple_assign_lhs (stmt));
732 252121 : type_size = TYPE_PRECISION (type);
733 252121 : if (type_size % BITS_PER_UNIT != 0)
734 : return NULL;
735 249242 : type_size /= BITS_PER_UNIT;
736 249242 : if (type_size > 64 / BITS_PER_MARKER)
737 : return NULL;
738 :
739 : /* Sign extension: result is dependent on the value. */
740 248585 : old_type_size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
741 351940 : if (!TYPE_UNSIGNED (n->type) && type_size > old_type_size
742 287275 : && HEAD_MARKER (n->n, old_type_size))
743 185495 : for (i = 0; i < type_size - old_type_size; i++)
744 146993 : n->n |= (uint64_t) MARKER_BYTE_UNKNOWN
745 146993 : << ((type_size - 1 - i) * BITS_PER_MARKER);
746 :
747 248585 : 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 123436 : n->n &= ((uint64_t) 1 << (type_size * BITS_PER_MARKER)) - 1;
752 : }
753 248585 : n->type = type;
754 248585 : if (!n->base_addr)
755 165834 : n->range = type_size;
756 : }
757 : break;
758 : default:
759 : return NULL;
760 310575 : };
761 310575 : return verify_symbolic_number_p (n, stmt) ? source_stmt1 : NULL;
762 : }
763 :
764 : /* Handle binary rhs. */
765 :
766 2187987 : if (rhs_class == GIMPLE_BINARY_RHS)
767 : {
768 2187987 : struct symbolic_number n1, n2;
769 2187987 : gimple *source_stmt, *source_stmt2;
770 :
771 2187987 : if (!rhs2 || TREE_CODE (rhs2) != SSA_NAME)
772 : return NULL;
773 :
774 2128208 : rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
775 :
776 2128208 : switch (code)
777 : {
778 1907639 : case BIT_IOR_EXPR:
779 1907639 : case BIT_XOR_EXPR:
780 1907639 : case PLUS_EXPR:
781 1907639 : source_stmt1 = find_bswap_or_nop_1 (rhs1_stmt, &n1, limit - 1);
782 :
783 1907639 : if (!source_stmt1)
784 : return NULL;
785 :
786 252394 : source_stmt2 = find_bswap_or_nop_1 (rhs2_stmt, &n2, limit - 1);
787 :
788 252394 : if (!source_stmt2)
789 : return NULL;
790 :
791 135666 : if (TYPE_PRECISION (n1.type) != TYPE_PRECISION (n2.type))
792 : return NULL;
793 :
794 135666 : if (n1.vuse != n2.vuse)
795 : return NULL;
796 :
797 107545 : source_stmt
798 107545 : = perform_symbolic_merge (source_stmt1, &n1, source_stmt2, &n2, n,
799 : code);
800 :
801 107545 : if (!source_stmt)
802 : return NULL;
803 :
804 18265 : if (!verify_symbolic_number_p (n, stmt))
805 : return NULL;
806 :
807 18264 : break;
808 : default:
809 : return NULL;
810 : }
811 18264 : 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 2132908 : find_bswap_or_nop_2 (gimple *stmt, struct symbolic_number *n, int limit)
821 : {
822 2132908 : if (gimple *ret = find_bswap_or_nop_1 (stmt, n, limit))
823 : return ret;
824 :
825 2124479 : if (!limit
826 2124479 : || !is_gimple_assign (stmt)
827 2124479 : || BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN
828 4248946 : || stmt_can_throw_internal (cfun, stmt))
829 : return NULL;
830 :
831 2124433 : tree rhs1 = gimple_assign_rhs1 (stmt);
832 2124433 : if (gimple_assign_rhs_code (stmt) == VEC_PACK_TRUNC_EXPR
833 2124433 : && TREE_CODE (rhs1) == SSA_NAME)
834 : {
835 1313 : if (BYTES_BIG_ENDIAN)
836 : return NULL; /* For now... */
837 1313 : gimple *rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
838 1313 : tree rhs2 = gimple_assign_rhs2 (stmt);
839 1313 : if (TREE_CODE (rhs2) != SSA_NAME)
840 : return NULL;
841 1313 : gimple *rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
842 1313 : struct symbolic_number n1, n2;
843 :
844 1313 : gimple *source_stmt1 = find_bswap_or_nop_2 (rhs1_stmt, &n1, limit - 1);
845 1313 : 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 2123120 : if (gimple_assign_rhs_code (stmt) != CONSTRUCTOR)
893 : return NULL;
894 :
895 28457 : tree type_size = TYPE_SIZE_UNIT (TREE_TYPE (gimple_get_lhs (stmt)));
896 28457 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (type_size) * BITS_PER_UNIT;
897 28457 : if (sz != 16 && sz != 32 && sz != 64)
898 : return NULL;
899 22803 : if (CONSTRUCTOR_NELTS (rhs1) == 0)
900 : return NULL;
901 22389 : tree eltype = TREE_TYPE (TREE_TYPE (rhs1));
902 22389 : unsigned HOST_WIDE_INT eltsz = int_size_in_bytes (eltype) * BITS_PER_UNIT;
903 22389 : if (TYPE_PRECISION (eltype) != eltsz)
904 : return NULL;
905 22249 : constructor_elt *elt;
906 22249 : unsigned int i;
907 22249 : tree type = build_nonstandard_integer_type (sz, 1);
908 22249 : gimple *ins_stmt = NULL;
909 61394 : FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (rhs1), i, elt)
910 : {
911 35386 : if (TREE_CODE (elt->value) != SSA_NAME
912 35386 : || !INTEGRAL_TYPE_P (TREE_TYPE (elt->value)))
913 18490 : return NULL;
914 34656 : struct symbolic_number n1;
915 34656 : gimple *source_stmt
916 34656 : = find_bswap_or_nop_1 (SSA_NAME_DEF_STMT (elt->value), &n1, limit - 1);
917 :
918 34656 : if (!source_stmt)
919 : return NULL;
920 :
921 24339 : n1.type = type;
922 24339 : if (!n1.base_addr)
923 3997 : n1.range = sz / BITS_PER_UNIT;
924 :
925 24339 : if (i == 0)
926 : {
927 11709 : ins_stmt = source_stmt;
928 11709 : *n = n1;
929 : }
930 : else
931 : {
932 12630 : if (n->vuse != n1.vuse)
933 7443 : return NULL;
934 :
935 7742 : struct symbolic_number n0 = *n;
936 :
937 7742 : if (!BYTES_BIG_ENDIAN)
938 : {
939 7742 : 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 7742 : ins_stmt
945 7742 : = perform_symbolic_merge (ins_stmt, &n0, source_stmt,
946 : &n1, n, BIT_IOR_EXPR);
947 :
948 7742 : 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 53519 : find_bswap_or_nop_finalize (struct symbolic_number *n, uint64_t *cmpxchg,
960 : uint64_t *cmpnop, bool *cast64_to_32)
961 : {
962 53519 : unsigned rsize;
963 53519 : 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 53519 : *cmpxchg = CMPXCHG;
969 53519 : *cmpnop = CMPNOP;
970 53519 : *cast64_to_32 = false;
971 :
972 : /* Find real size of result (highest non-zero byte). */
973 53519 : if (n->base_addr)
974 358139 : for (tmpn = n->n, rsize = 0; tmpn; tmpn >>= BITS_PER_MARKER, rsize++);
975 : else
976 1993 : rsize = n->range;
977 :
978 : /* Zero out the bits corresponding to untouched bytes in original gimple
979 : expression. */
980 53519 : if (n->range < (int) sizeof (int64_t))
981 : {
982 27286 : mask = ((uint64_t) 1 << (n->range * BITS_PER_MARKER)) - 1;
983 27286 : if (n->base_addr == NULL
984 1023 : && n->range == 4
985 28017 : && 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 164 : *cast64_to_32 = true;
992 318 : for (tmpn = n->n; tmpn; tmpn >>= BITS_PER_MARKER)
993 279 : if ((tmpn & MARKER_MASK)
994 279 : && ((tmpn & MARKER_MASK) <= 4 || (tmpn & MARKER_MASK) > 8))
995 : {
996 125 : *cast64_to_32 = false;
997 125 : break;
998 : }
999 : }
1000 27286 : if (*cast64_to_32)
1001 39 : *cmpxchg &= mask;
1002 : else
1003 27247 : *cmpxchg >>= (64 / BITS_PER_MARKER - n->range) * BITS_PER_MARKER;
1004 27286 : *cmpnop &= mask;
1005 : }
1006 :
1007 : /* Zero out the bits corresponding to unused bytes in the result of the
1008 : gimple expression. */
1009 53519 : if (rsize < n->range)
1010 : {
1011 2559 : 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 2559 : mask = ((uint64_t) 1 << (rsize * BITS_PER_MARKER)) - 1;
1023 2559 : if (n->range - rsize == sizeof (int64_t))
1024 : *cmpxchg = 0;
1025 : else
1026 2553 : *cmpxchg >>= (n->range - rsize) * BITS_PER_MARKER;
1027 2559 : *cmpnop &= mask;
1028 : }
1029 2559 : n->range = rsize;
1030 : }
1031 :
1032 53519 : if (*cast64_to_32)
1033 39 : n->range = 8;
1034 53519 : n->range *= BITS_PER_UNIT;
1035 53519 : }
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 13566 : is_bswap_or_nop_p (uint64_t n, uint64_t cmpxchg,
1041 : uint64_t cmpnop, uint64_t* mask,
1042 : bool* bswap)
1043 : {
1044 13566 : *mask = ~(uint64_t) 0;
1045 13566 : if (n == cmpnop)
1046 5255 : *bswap = false;
1047 8311 : else if (n == cmpxchg)
1048 2392 : *bswap = true;
1049 : else
1050 : {
1051 : int set = 0;
1052 13193 : for (uint64_t msk = MARKER_MASK; msk; msk <<= BITS_PER_MARKER)
1053 12630 : if ((n & msk) == 0)
1054 4650 : *mask &= ~msk;
1055 7980 : 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 2131550 : 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 2131550 : tree type_size = TYPE_SIZE_UNIT (TREE_TYPE (gimple_get_lhs (stmt)));
1081 2131550 : 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 2131550 : int limit = tree_to_uhwi (type_size);
1090 2131550 : limit += 2 * (1 + ceil_log2 ((unsigned HOST_WIDE_INT) limit));
1091 2131550 : gimple *ins_stmt = find_bswap_or_nop_2 (stmt, n, limit);
1092 2131550 : if (!ins_stmt)
1093 : return NULL;
1094 :
1095 12143 : uint64_t cmpxchg, cmpnop;
1096 12143 : uint64_t orig_range = n->range * BITS_PER_UNIT;
1097 12143 : 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 12143 : *l_rotate = 0;
1103 12143 : uint64_t tmp_n = n->n;
1104 12143 : 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 4043 : if (n->range == orig_range
1110 : /* There're case like 0x300000200 for uint32->uint64 cast,
1111 : Don't handle this. */
1112 3135 : && n->range == TYPE_PRECISION (n->type)
1113 1792 : && ((orig_range == 32
1114 580 : && optab_handler (rotl_optab, SImode) != CODE_FOR_nothing)
1115 1212 : || (orig_range == 64
1116 1193 : && optab_handler (rotl_optab, DImode) != CODE_FOR_nothing))
1117 5816 : && (tmp_n & MARKER_MASK) < orig_range / BITS_PER_UNIT)
1118 : {
1119 1427 : uint64_t range = (orig_range / BITS_PER_UNIT) * BITS_PER_MARKER;
1120 1427 : uint64_t count = (tmp_n & MARKER_MASK) * BITS_PER_MARKER;
1121 : /* .i.e. handle 0x203040506070800 when lower byte is zero. */
1122 1427 : 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 1423 : tmp_n = tmp_n >> count | tmp_n << (range - count);
1143 1423 : if (orig_range == 32)
1144 347 : tmp_n &= (1ULL << 32) - 1;
1145 1423 : 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 8209 : 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 297180 : pass_optimize_bswap (gcc::context *ctxt)
1178 594360 : : gimple_opt_pass (pass_data_optimize_bswap, ctxt)
1179 : {}
1180 :
1181 : /* opt_pass methods: */
1182 1063018 : bool gate (function *) final override
1183 : {
1184 1063018 : 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 2254 : bswap_view_convert (gimple_stmt_iterator *gsi, tree type, tree val,
1197 : bool before)
1198 : {
1199 2254 : gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (val))
1200 : || POINTER_TYPE_P (TREE_TYPE (val)));
1201 2254 : 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 2254 : 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 6694 : 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 6694 : tree src, tmp, tgt = NULL_TREE;
1247 6694 : gimple *bswap_stmt, *mask_stmt = NULL, *rotl_stmt = NULL;
1248 6694 : tree_code conv_code = NOP_EXPR;
1249 :
1250 6694 : gimple *cur_stmt = gsi_stmt (gsi);
1251 6694 : src = n->src;
1252 6694 : if (cur_stmt)
1253 : {
1254 5808 : tgt = gimple_assign_lhs (cur_stmt);
1255 5808 : if ((gimple_assign_rhs_code (cur_stmt) == CONSTRUCTOR
1256 3579 : || gimple_assign_rhs_code (cur_stmt) == VEC_PACK_TRUNC_EXPR)
1257 2254 : && tgt
1258 8062 : && VECTOR_TYPE_P (TREE_TYPE (tgt)))
1259 : conv_code = VIEW_CONVERT_EXPR;
1260 : }
1261 :
1262 : /* Need to load the value from memory first. */
1263 6694 : if (n->base_addr)
1264 : {
1265 5962 : gimple_stmt_iterator gsi_ins = gsi;
1266 5962 : if (ins_stmt)
1267 5889 : gsi_ins = gsi_for_stmt (ins_stmt);
1268 5962 : tree addr_expr, addr_tmp, val_expr, val_tmp;
1269 5962 : tree load_offset_ptr, aligned_load_type;
1270 5962 : gimple *load_stmt;
1271 5962 : unsigned align = get_object_alignment (src);
1272 5962 : poly_int64 load_offset = 0;
1273 :
1274 5962 : if (cur_stmt)
1275 : {
1276 5519 : basic_block ins_bb = gimple_bb (ins_stmt);
1277 5519 : basic_block cur_bb = gimple_bb (cur_stmt);
1278 5519 : if (!dominated_by_p (CDI_DOMINATORS, cur_bb, ins_bb))
1279 4135 : 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 5519 : if (gimple_bb (cur_stmt) != gimple_bb (ins_stmt))
1285 1110 : reset_flow_sensitive_info (gimple_assign_lhs (cur_stmt));
1286 5519 : gsi_move_before (&gsi, &gsi_ins);
1287 5519 : 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 5962 : addr_expr = build_fold_addr_expr (src);
1295 5962 : if (is_gimple_mem_ref_addr (addr_expr))
1296 588 : addr_tmp = unshare_expr (addr_expr);
1297 : else
1298 : {
1299 5374 : addr_tmp = unshare_expr (n->base_addr);
1300 5374 : 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 5374 : load_offset = n->bytepos;
1306 5374 : 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 5962 : aligned_load_type = load_type;
1322 5962 : if (align < TYPE_ALIGN (load_type))
1323 5214 : aligned_load_type = build_aligned_type (load_type, align);
1324 5962 : load_offset_ptr = build_int_cst (n->alias_set, load_offset);
1325 5962 : val_expr = fold_build2 (MEM_REF, aligned_load_type, addr_tmp,
1326 : load_offset_ptr);
1327 :
1328 5962 : if (!bswap)
1329 : {
1330 4135 : if (n->range == 16)
1331 1213 : nop_stats.found_16bit++;
1332 2922 : else if (n->range == 32)
1333 639 : nop_stats.found_32bit++;
1334 : else
1335 : {
1336 2283 : gcc_assert (n->range == 64);
1337 2283 : nop_stats.found_64bit++;
1338 : }
1339 :
1340 : /* Convert the result of load if necessary. */
1341 4135 : if (tgt && !useless_type_conversion_p (TREE_TYPE (tgt), load_type))
1342 : {
1343 3607 : val_tmp = make_temp_ssa_name (aligned_load_type, NULL,
1344 : "load_dst");
1345 3607 : load_stmt = gimple_build_assign (val_tmp, val_expr);
1346 3607 : gimple_set_vuse (load_stmt, n->vuse);
1347 3607 : gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1348 3607 : if (conv_code == VIEW_CONVERT_EXPR)
1349 2123 : val_tmp = bswap_view_convert (&gsi, TREE_TYPE (tgt), val_tmp,
1350 : true);
1351 3607 : gimple_assign_set_rhs_with_ops (&gsi, conv_code, val_tmp);
1352 3607 : 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 4135 : 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 1133611 : maybe_optimize_vector_constructor (gimple *cur_stmt)
1543 : {
1544 1133611 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
1545 1133611 : struct symbolic_number n;
1546 1133611 : bool bswap;
1547 :
1548 1133611 : gcc_assert (is_gimple_assign (cur_stmt));
1549 1133611 : switch (gimple_assign_rhs_code (cur_stmt))
1550 : {
1551 1133611 : case CONSTRUCTOR:
1552 1133611 : case VEC_PACK_TRUNC_EXPR:
1553 1133611 : break;
1554 0 : default:
1555 0 : gcc_unreachable ();
1556 : }
1557 :
1558 1133611 : tree rhs = gimple_assign_rhs1 (cur_stmt);
1559 1133611 : if (!VECTOR_TYPE_P (TREE_TYPE (rhs))
1560 93579 : || !INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs)))
1561 1223545 : || gimple_assign_lhs (cur_stmt) == NULL_TREE)
1562 : return false;
1563 :
1564 89934 : HOST_WIDE_INT sz = int_size_in_bytes (TREE_TYPE (rhs)) * BITS_PER_UNIT;
1565 89934 : switch (sz)
1566 : {
1567 976 : case 16:
1568 976 : load_type = bswap_type = uint16_type_node;
1569 976 : break;
1570 842 : case 32:
1571 842 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
1572 842 : && can_open_code_p (bswap_optab, SImode))
1573 : {
1574 836 : load_type = uint32_type_node;
1575 836 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
1576 836 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1577 : }
1578 : else
1579 : return false;
1580 836 : break;
1581 22070 : case 64:
1582 22070 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
1583 22070 : && can_open_code_p (bswap_optab, DImode))
1584 : {
1585 21154 : load_type = uint64_type_node;
1586 21154 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
1587 21154 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1588 : }
1589 : else
1590 : return false;
1591 21154 : break;
1592 : default:
1593 : return false;
1594 : }
1595 :
1596 22966 : bool cast64_to_32;
1597 22966 : uint64_t mask, l_rotate;
1598 22966 : gimple *ins_stmt = find_bswap_or_nop (cur_stmt, &n, &bswap,
1599 : &cast64_to_32, &mask, &l_rotate);
1600 22966 : if (!ins_stmt
1601 2211 : || n.range != (unsigned HOST_WIDE_INT) sz
1602 2211 : || cast64_to_32
1603 2211 : || mask != ~(uint64_t) 0)
1604 : return false;
1605 :
1606 2211 : if (bswap && !fndecl && n.range != 16)
1607 : return false;
1608 :
1609 2211 : memset (&nop_stats, 0, sizeof (nop_stats));
1610 2211 : memset (&bswap_stats, 0, sizeof (bswap_stats));
1611 2211 : return bswap_replace (gsi_for_stmt (cur_stmt), ins_stmt, fndecl,
1612 : bswap_type, load_type, &n, bswap, mask,
1613 2211 : 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 982906 : pass_optimize_bswap::execute (function *fun)
1623 : {
1624 982906 : basic_block bb;
1625 982906 : bool bswap32_p, bswap64_p;
1626 982906 : bool changed = false;
1627 982906 : tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1628 :
1629 982906 : bswap32_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
1630 982906 : && can_open_code_p (bswap_optab, SImode));
1631 982906 : bswap64_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
1632 982906 : && 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 982906 : if (bswap32_p)
1637 : {
1638 882060 : tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
1639 882060 : bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1640 : }
1641 :
1642 982906 : if (bswap64_p)
1643 : {
1644 882060 : tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
1645 882060 : bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1646 : }
1647 :
1648 982906 : memset (&nop_stats, 0, sizeof (nop_stats));
1649 982906 : memset (&bswap_stats, 0, sizeof (bswap_stats));
1650 982906 : calculate_dominance_info (CDI_DOMINATORS);
1651 :
1652 10921323 : FOR_EACH_BB_FN (bb, fun)
1653 : {
1654 9938417 : 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 104933143 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1661 : {
1662 85056309 : gimple *ins_stmt, *cur_stmt = gsi_stmt (gsi);
1663 85056309 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
1664 85056309 : enum tree_code code;
1665 85056309 : struct symbolic_number n;
1666 85056309 : bool bswap, cast64_to_32;
1667 85056309 : 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 85056309 : gsi_prev (&gsi);
1676 :
1677 85056309 : if (!is_gimple_assign (cur_stmt))
1678 85052712 : continue;
1679 :
1680 21074150 : code = gimple_assign_rhs_code (cur_stmt);
1681 21074150 : switch (code)
1682 : {
1683 7269 : case LROTATE_EXPR:
1684 7269 : case RROTATE_EXPR:
1685 7269 : if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt))
1686 7269 : || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt))
1687 4393 : % 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 1381944 : case CONSTRUCTOR:
1695 1381944 : case VEC_PACK_TRUNC_EXPR:
1696 1381944 : {
1697 1381944 : tree rhs = gimple_assign_rhs1 (cur_stmt);
1698 1381944 : if (VECTOR_TYPE_P (TREE_TYPE (rhs))
1699 1381944 : && INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs))))
1700 : break;
1701 : }
1702 1375600 : continue;
1703 17583877 : default:
1704 17583877 : continue;
1705 18959477 : }
1706 :
1707 2108584 : ins_stmt = find_bswap_or_nop (cur_stmt, &n, &bswap,
1708 : &cast64_to_32, &mask, &l_rotate);
1709 :
1710 2108584 : if (!ins_stmt)
1711 2102586 : 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 982906 : statistics_counter_event (fun, "16-bit nop implementations found",
1752 : nop_stats.found_16bit);
1753 982906 : statistics_counter_event (fun, "32-bit nop implementations found",
1754 : nop_stats.found_32bit);
1755 982906 : statistics_counter_event (fun, "64-bit nop implementations found",
1756 : nop_stats.found_64bit);
1757 982906 : statistics_counter_event (fun, "16-bit bswap implementations found",
1758 : bswap_stats.found_16bit);
1759 982906 : statistics_counter_event (fun, "32-bit bswap implementations found",
1760 : bswap_stats.found_32bit);
1761 982906 : statistics_counter_event (fun, "64-bit bswap implementations found",
1762 : bswap_stats.found_64bit);
1763 :
1764 982906 : return (changed ? TODO_update_ssa : 0);
1765 : }
1766 :
1767 : } // anon namespace
1768 :
1769 : gimple_opt_pass *
1770 297180 : make_pass_optimize_bswap (gcc::context *ctxt)
1771 : {
1772 297180 : 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 10657070 : store_operand_info::store_operand_info ()
1798 10657070 : : val (NULL_TREE), base_addr (NULL_TREE), bitsize (0), bitpos (0),
1799 10657070 : 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 3237757 : 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 3237757 : : bitsize (bs), bitpos (bp), bitregion_start (brs), bitregion_end (bre),
1860 3237757 : stmt (st), order (ord), rhs_code (rhscode), n (nr),
1861 3237757 : ins_stmt (ins_stmtp), bit_not_p (bitnotp), ops_swapped_p (false),
1862 3237757 : 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 1353635 : clear_bit_region (unsigned char *ptr, unsigned int start,
1969 : unsigned int len)
1970 : {
1971 : /* Degenerate base case. */
1972 1454378 : if (len == 0)
1973 : return;
1974 1454378 : else if (start >= BITS_PER_UNIT)
1975 50364 : clear_bit_region (ptr + 1, start - BITS_PER_UNIT, len);
1976 : /* Second base case. */
1977 1404014 : else if ((start + len) <= BITS_PER_UNIT)
1978 : {
1979 214543 : unsigned char mask = (~0U) << (unsigned char) (BITS_PER_UNIT - len);
1980 214543 : mask >>= BITS_PER_UNIT - (start + len);
1981 :
1982 214543 : ptr[0] &= ~mask;
1983 :
1984 214543 : return;
1985 : }
1986 : /* Clear most significant bits in a byte and proceed with the next byte. */
1987 1189471 : else if (start != 0)
1988 : {
1989 47590 : clear_bit_region (ptr, start, BITS_PER_UNIT - start);
1990 47590 : clear_bit_region (ptr + 1, 0, len - (BITS_PER_UNIT - start));
1991 : }
1992 : /* Whole bytes need to be cleared. */
1993 1141881 : else if (start == 0 && len > BITS_PER_UNIT)
1994 : {
1995 1141881 : 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 1141881 : memset (ptr, '\0', nbytes);
1999 : /* Clear the remaining sub-byte region if there is one. */
2000 1141881 : if (len % BITS_PER_UNIT != 0)
2001 2789 : 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 1051267 : encode_tree_to_bitpos (tree expr, unsigned char *ptr, int bitlen, int bitpos,
2013 : unsigned int total_bytes)
2014 : {
2015 1051267 : unsigned int first_byte = bitpos / BITS_PER_UNIT;
2016 1051267 : bool empty_ctor_p
2017 1051267 : = (TREE_CODE (expr) == CONSTRUCTOR
2018 241515 : && CONSTRUCTOR_NELTS (expr) == 0
2019 241515 : && TYPE_SIZE_UNIT (TREE_TYPE (expr))
2020 1292782 : && tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (expr))));
2021 1051267 : bool sub_byte_op_p = ((bitlen % BITS_PER_UNIT)
2022 1023446 : || (bitpos % BITS_PER_UNIT)
2023 2074173 : || (!int_mode_for_size (bitlen, 0).exists ()
2024 67406 : && !empty_ctor_p));
2025 :
2026 28523 : if (!sub_byte_op_p)
2027 : {
2028 1022744 : if (first_byte >= total_bytes)
2029 : return false;
2030 1022744 : total_bytes -= first_byte;
2031 1022744 : if (empty_ctor_p)
2032 : {
2033 241515 : unsigned HOST_WIDE_INT rhs_bytes
2034 241515 : = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (expr)));
2035 241515 : if (rhs_bytes > total_bytes)
2036 : return false;
2037 241515 : memset (ptr + first_byte, '\0', rhs_bytes);
2038 241515 : return true;
2039 : }
2040 781229 : 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 28523 : unsigned int byte_size;
2088 28523 : 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 28523 : fixed_size_mode mode
2099 28523 : = as_a <fixed_size_mode> (TYPE_MODE (TREE_TYPE (expr)));
2100 28523 : byte_size
2101 28523 : = mode == BLKmode
2102 68 : ? tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (expr)))
2103 28455 : : GET_MODE_SIZE (mode);
2104 : }
2105 : /* Allocate an extra byte so that we have space to shift into. */
2106 28523 : byte_size++;
2107 28523 : unsigned char *tmpbuf = XALLOCAVEC (unsigned char, byte_size);
2108 28523 : 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 28523 : if (!empty_ctor_p
2112 28523 : && 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 28523 : unsigned int padding
2122 28523 : = 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 28523 : if (BYTES_BIG_ENDIAN)
2126 : tmpbuf += padding;
2127 :
2128 28523 : byte_size -= padding;
2129 :
2130 28523 : if (bitlen % BITS_PER_UNIT != 0)
2131 : {
2132 27821 : 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 27821 : clear_bit_region (tmpbuf, bitlen,
2137 27821 : 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 28523 : 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 28523 : clear_bit_region (ptr + first_byte, bitpos % BITS_PER_UNIT, bitlen);
2152 :
2153 28523 : int shift_amnt;
2154 28523 : int bitlen_mod = bitlen % BITS_PER_UNIT;
2155 28523 : int bitpos_mod = bitpos % BITS_PER_UNIT;
2156 :
2157 28523 : bool skip_byte = false;
2158 28523 : 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 28523 : shift_amnt = bitpos % BITS_PER_UNIT;
2183 :
2184 : /* Create the shifted version of EXPR. */
2185 28523 : if (!BYTES_BIG_ENDIAN)
2186 : {
2187 28523 : shift_bytes_in_array_left (tmpbuf, byte_size, shift_amnt);
2188 28523 : if (shift_amnt == 0)
2189 12795 : 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 123917 : for (unsigned int i = 0; i < byte_size; i++)
2206 95394 : 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 18543210 : sort_by_bitpos (const void *x, const void *y)
2216 : {
2217 18543210 : store_immediate_info *const *tmp = (store_immediate_info * const *) x;
2218 18543210 : store_immediate_info *const *tmp2 = (store_immediate_info * const *) y;
2219 :
2220 18543210 : if ((*tmp)->bitpos < (*tmp2)->bitpos)
2221 : return -1;
2222 9523625 : 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 820321 : 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 7017748 : sort_by_order (const void *x, const void *y)
2235 : {
2236 7017748 : store_immediate_info *const *tmp = (store_immediate_info * const *) x;
2237 7017748 : store_immediate_info *const *tmp2 = (store_immediate_info * const *) y;
2238 :
2239 7017748 : if ((*tmp)->order < (*tmp2)->order)
2240 : return -1;
2241 3395677 : 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 886679 : merged_store_group::merged_store_group (store_immediate_info *info)
2251 : {
2252 886679 : start = info->bitpos;
2253 886679 : width = info->bitsize;
2254 886679 : bitregion_start = info->bitregion_start;
2255 886679 : bitregion_end = info->bitregion_end;
2256 : /* VAL has memory allocated for it in apply_stores once the group
2257 : width has been finalized. */
2258 886679 : val = NULL;
2259 886679 : mask = NULL;
2260 886679 : bit_insertion = info->rhs_code == BIT_INSERT_EXPR;
2261 886679 : string_concatenation = info->rhs_code == STRING_CST;
2262 886679 : only_constants = info->rhs_code == INTEGER_CST;
2263 886679 : consecutive = true;
2264 886679 : first_nonmergeable_order = ~0U;
2265 886679 : lp_nr = info->lp_nr;
2266 886679 : unsigned HOST_WIDE_INT align_bitpos = 0;
2267 886679 : get_object_alignment_1 (gimple_assign_lhs (info->stmt),
2268 : &align, &align_bitpos);
2269 886679 : align_base = start - align_bitpos;
2270 2660037 : for (int i = 0; i < 2; ++i)
2271 : {
2272 1773358 : store_operand_info &op = info->ops[i];
2273 1773358 : if (op.base_addr == NULL_TREE)
2274 : {
2275 1561541 : load_align[i] = 0;
2276 1561541 : load_align_base[i] = 0;
2277 : }
2278 : else
2279 : {
2280 211817 : get_object_alignment_1 (op.val, &load_align[i], &align_bitpos);
2281 211817 : load_align_base[i] = op.bitpos - align_bitpos;
2282 : }
2283 : }
2284 886679 : stores.create (1);
2285 886679 : stores.safe_push (info);
2286 886679 : last_stmt = info->stmt;
2287 886679 : last_order = info->order;
2288 886679 : first_stmt = last_stmt;
2289 886679 : first_order = last_order;
2290 886679 : buf_size = 0;
2291 886679 : }
2292 :
2293 886679 : merged_store_group::~merged_store_group ()
2294 : {
2295 886679 : if (val)
2296 421502 : XDELETEVEC (val);
2297 886679 : }
2298 :
2299 : /* Return true if the store described by INFO can be merged into the group. */
2300 :
2301 : bool
2302 730006 : merged_store_group::can_be_merged_into (store_immediate_info *info)
2303 : {
2304 : /* Do not merge bswap patterns. */
2305 730006 : if (info->rhs_code == LROTATE_EXPR)
2306 : return false;
2307 :
2308 715895 : if (info->lp_nr != lp_nr)
2309 : return false;
2310 :
2311 : /* The canonical case. */
2312 715895 : 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 57613 : if (info->rhs_code == BIT_INSERT_EXPR && stores[0]->rhs_code == INTEGER_CST)
2317 2078 : return !string_concatenation;
2318 :
2319 55535 : if (stores[0]->rhs_code == BIT_INSERT_EXPR && info->rhs_code == INTEGER_CST)
2320 4528 : 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 51007 : if (info->rhs_code == MEM_REF
2325 22638 : && (stores[0]->rhs_code == INTEGER_CST
2326 3097 : || stores[0]->rhs_code == BIT_INSERT_EXPR)
2327 20021 : && info->bitregion_start == stores[0]->bitregion_start
2328 767 : && info->bitregion_end == stores[0]->bitregion_end
2329 52541 : && info->bitregion_end - info->bitregion_start <= MAX_FIXED_MODE_SIZE)
2330 765 : return !string_concatenation;
2331 :
2332 50242 : if (stores[0]->rhs_code == MEM_REF
2333 22698 : && (info->rhs_code == INTEGER_CST
2334 22698 : || info->rhs_code == BIT_INSERT_EXPR)
2335 22405 : && info->bitregion_start == stores[0]->bitregion_start
2336 4 : && info->bitregion_end == stores[0]->bitregion_end
2337 50246 : && 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 50240 : if (info->rhs_code == STRING_CST
2342 82 : && stores[0]->rhs_code == INTEGER_CST
2343 50322 : && stores[0]->bitsize == CHAR_BIT)
2344 66 : return !bit_insertion;
2345 :
2346 50174 : if (stores[0]->rhs_code == STRING_CST
2347 26 : && info->rhs_code == INTEGER_CST
2348 50200 : && 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 830412 : merged_store_group::do_merge (store_immediate_info *info)
2359 : {
2360 830412 : bitregion_start = MIN (bitregion_start, info->bitregion_start);
2361 830412 : bitregion_end = MAX (bitregion_end, info->bitregion_end);
2362 :
2363 830412 : unsigned int this_align;
2364 830412 : unsigned HOST_WIDE_INT align_bitpos = 0;
2365 830412 : get_object_alignment_1 (gimple_assign_lhs (info->stmt),
2366 : &this_align, &align_bitpos);
2367 830412 : if (this_align > align)
2368 : {
2369 1107 : align = this_align;
2370 1107 : align_base = info->bitpos - align_bitpos;
2371 : }
2372 2491236 : for (int i = 0; i < 2; ++i)
2373 : {
2374 1660824 : store_operand_info &op = info->ops[i];
2375 1660824 : if (!op.base_addr)
2376 1549289 : continue;
2377 :
2378 111535 : get_object_alignment_1 (op.val, &this_align, &align_bitpos);
2379 111535 : 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 830412 : gimple *stmt = info->stmt;
2387 830412 : stores.safe_push (info);
2388 830412 : if (info->order > last_order)
2389 : {
2390 559519 : last_order = info->order;
2391 559519 : last_stmt = stmt;
2392 : }
2393 270893 : else if (info->order < first_order)
2394 : {
2395 117138 : first_order = info->order;
2396 117138 : first_stmt = stmt;
2397 : }
2398 :
2399 830412 : if (info->bitpos != start + width)
2400 200284 : consecutive = false;
2401 :
2402 : /* We need to use extraction if there is any bit-field. */
2403 830412 : if (info->rhs_code == BIT_INSERT_EXPR)
2404 : {
2405 6827 : bit_insertion = true;
2406 6827 : gcc_assert (!string_concatenation);
2407 : }
2408 :
2409 : /* We want to use concatenation if there is any string. */
2410 830412 : 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 830412 : if (!consecutive)
2418 315322 : string_concatenation = false;
2419 :
2420 830412 : if (info->rhs_code != INTEGER_CST)
2421 119667 : only_constants = false;
2422 830412 : }
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 124448 : merged_store_group::merge_into (store_immediate_info *info)
2430 : {
2431 124448 : do_merge (info);
2432 :
2433 : /* Make sure we're inserting in the position we think we're inserting. */
2434 124448 : gcc_assert (info->bitpos >= start + width
2435 : && info->bitregion_start <= bitregion_end);
2436 :
2437 124448 : width = info->bitpos + info->bitsize - start;
2438 124448 : }
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 705964 : merged_store_group::merge_overlapping (store_immediate_info *info)
2446 : {
2447 705964 : do_merge (info);
2448 :
2449 : /* If the store extends the size of the group, extend the width. */
2450 705964 : if (info->bitpos + info->bitsize > start + width)
2451 511088 : width = info->bitpos + info->bitsize - start;
2452 705964 : }
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 885793 : merged_store_group::apply_stores ()
2460 : {
2461 885793 : store_immediate_info *info;
2462 885793 : unsigned int i;
2463 :
2464 : /* Make sure we have more than one store in the group, otherwise we cannot
2465 : merge anything. */
2466 885793 : if (bitregion_start % BITS_PER_UNIT != 0
2467 885793 : || bitregion_end % BITS_PER_UNIT != 0
2468 1771586 : || stores.length () == 1)
2469 : return false;
2470 :
2471 421502 : buf_size = (bitregion_end - bitregion_start) / BITS_PER_UNIT;
2472 :
2473 : /* Really do string concatenation for large strings only. */
2474 421502 : if (buf_size <= MOVE_MAX)
2475 203273 : string_concatenation = false;
2476 :
2477 : /* String concatenation only works for byte aligned start and end. */
2478 421502 : if (start % BITS_PER_UNIT != 0 || width % BITS_PER_UNIT != 0)
2479 3640 : string_concatenation = false;
2480 :
2481 : /* Create a power-of-2-sized buffer for native_encode_expr. */
2482 421502 : if (!string_concatenation)
2483 842932 : buf_size = 1 << ceil_log2 (buf_size);
2484 :
2485 421502 : val = XNEWVEC (unsigned char, 2 * buf_size);
2486 421502 : mask = val + buf_size;
2487 421502 : memset (val, 0, buf_size);
2488 421502 : memset (mask, ~0U, buf_size);
2489 :
2490 421502 : stores.qsort (sort_by_order);
2491 :
2492 1671166 : FOR_EACH_VEC_ELT (stores, i, info)
2493 : {
2494 1249664 : unsigned int pos_in_buffer = info->bitpos - bitregion_start;
2495 1249664 : tree cst;
2496 1249664 : if (info->ops[0].val && info->ops[0].base_addr == NULL_TREE)
2497 : cst = info->ops[0].val;
2498 189185 : 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 1060796 : bool ret = true;
2503 1060796 : if (cst && info->rhs_code != BIT_INSERT_EXPR)
2504 1051267 : ret = encode_tree_to_bitpos (cst, val, info->bitsize, pos_in_buffer,
2505 1051267 : buf_size);
2506 1249664 : unsigned char *m = mask + (pos_in_buffer / BITS_PER_UNIT);
2507 1249664 : 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 1249664 : clear_bit_region (m, pos_in_buffer % BITS_PER_UNIT, info->bitsize);
2513 1249664 : 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 1249664 : if (!ret)
2534 : return false;
2535 : }
2536 421502 : 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 2042622 : imm_store_chain_info (imm_store_chain_info *&inspt, tree b_a)
2555 2042622 : : next (inspt), pnxp (&inspt), base_addr (b_a)
2556 : {
2557 2042622 : inspt = this;
2558 2042622 : if (next)
2559 : {
2560 701211 : gcc_checking_assert (pnxp == next->pnxp);
2561 701211 : next->pnxp = &next;
2562 : }
2563 2042622 : }
2564 2042622 : ~imm_store_chain_info ()
2565 : {
2566 2042622 : *pnxp = next;
2567 2042622 : if (next)
2568 : {
2569 668559 : gcc_checking_assert (&next == next->pnxp);
2570 668559 : next->pnxp = pnxp;
2571 : }
2572 2042622 : }
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 297180 : pass_store_merging (gcc::context *ctxt)
2597 297180 : : gimple_opt_pass (pass_data_tree_store_merging, ctxt), m_stores_head (),
2598 297180 : m_n_chains (0), m_n_stores (0)
2599 : {
2600 297180 : }
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 1063018 : gate (function *) final override
2607 : {
2608 1063018 : return flag_store_merging
2609 : && BYTES_BIG_ENDIAN == WORDS_BIG_ENDIAN
2610 : && CHAR_BIT == 8
2611 1063018 : && 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 1214757 : pass_store_merging::terminate_and_process_all_chains ()
2646 : {
2647 1214757 : bool ret = false;
2648 2194746 : while (m_stores_head)
2649 979989 : ret |= terminate_and_process_chain (m_stores_head);
2650 1214757 : gcc_assert (m_stores.is_empty ());
2651 1214757 : 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 10336185 : pass_store_merging::terminate_all_aliasing_chains (imm_store_chain_info
2660 : **chain_info,
2661 : gimple *stmt)
2662 : {
2663 10336185 : bool ret = false;
2664 :
2665 : /* If the statement doesn't touch memory it can't alias. */
2666 20187749 : if (!gimple_vuse (stmt))
2667 : return false;
2668 :
2669 17078574 : for (imm_store_chain_info *next = m_stores_head, *cur = next; cur; cur = next)
2670 : {
2671 8840259 : next = cur->next;
2672 :
2673 : /* We already checked all the stores in chain_info and terminated the
2674 : chain if necessary. Skip it here. */
2675 8840259 : if (chain_info && *chain_info == cur)
2676 1195135 : continue;
2677 :
2678 : store_immediate_info *info;
2679 : unsigned int i;
2680 27637419 : FOR_EACH_VEC_ELT (cur->m_store_info, i, info)
2681 : {
2682 12211259 : tree lhs = gimple_assign_lhs (info->stmt);
2683 12211259 : ao_ref lhs_ref;
2684 12211259 : ao_ref_init (&lhs_ref, lhs);
2685 12211259 : if (ref_maybe_used_by_stmt_p (stmt, &lhs_ref)
2686 12211259 : || stmt_may_clobber_ref_p_1 (stmt, &lhs_ref, false))
2687 : {
2688 1059223 : if (dump_file && (dump_flags & TDF_DETAILS))
2689 : {
2690 24 : fprintf (dump_file, "stmt causes chain termination:\n");
2691 24 : print_gimple_stmt (dump_file, stmt, 0);
2692 : }
2693 1059223 : ret |= terminate_and_process_chain (cur);
2694 1059223 : break;
2695 : }
2696 : }
2697 : }
2698 :
2699 : return ret;
2700 : }
2701 :
2702 : /* Helper function. Terminate the recorded chain storing to base object
2703 : BASE. Return true if the merging and output was successful. The m_stores
2704 : entry is removed after the processing in any case. */
2705 :
2706 : bool
2707 2042622 : pass_store_merging::terminate_and_process_chain (imm_store_chain_info *chain_info)
2708 : {
2709 2042622 : m_n_stores -= chain_info->m_store_info.length ();
2710 2042622 : m_n_chains--;
2711 2042622 : bool ret = chain_info->terminate_and_process_chain ();
2712 2042622 : m_stores.remove (chain_info->base_addr);
2713 2042622 : delete chain_info;
2714 2042622 : return ret;
2715 : }
2716 :
2717 : /* Return true if stmts in between FIRST (inclusive) and LAST (exclusive)
2718 : may clobber REF. FIRST and LAST must have non-NULL vdef. We want to
2719 : be able to sink load of REF across stores between FIRST and LAST, up
2720 : to right before LAST. */
2721 :
2722 : bool
2723 33413 : stmts_may_clobber_ref_p (gimple *first, gimple *last, tree ref)
2724 : {
2725 33413 : ao_ref r;
2726 33413 : ao_ref_init (&r, ref);
2727 33413 : unsigned int count = 0;
2728 33413 : tree vop = gimple_vdef (last);
2729 33413 : gimple *stmt;
2730 :
2731 : /* Return true conservatively if the basic blocks are different. */
2732 33413 : if (gimple_bb (first) != gimple_bb (last))
2733 : return true;
2734 :
2735 85832 : do
2736 : {
2737 85832 : stmt = SSA_NAME_DEF_STMT (vop);
2738 85832 : if (stmt_may_clobber_ref_p_1 (stmt, &r, false))
2739 : return true;
2740 : /* Avoid quadratic compile time by bounding the number of checks
2741 : we perform. */
2742 84913 : if (++count > MAX_STORE_ALIAS_CHECKS)
2743 : return true;
2744 84913 : vop = gimple_vuse (stmt);
2745 : }
2746 84913 : while (stmt != first);
2747 :
2748 : return false;
2749 : }
2750 :
2751 : /* Return true if INFO->ops[IDX] is mergeable with the
2752 : corresponding loads already in MERGED_STORE group.
2753 : BASE_ADDR is the base address of the whole store group. */
2754 :
2755 : bool
2756 144083 : compatible_load_p (merged_store_group *merged_store,
2757 : store_immediate_info *info,
2758 : tree base_addr, int idx)
2759 : {
2760 144083 : store_immediate_info *infof = merged_store->stores[0];
2761 144083 : if (!info->ops[idx].base_addr
2762 144083 : || maybe_ne (info->ops[idx].bitpos - infof->ops[idx].bitpos,
2763 144083 : info->bitpos - infof->bitpos)
2764 261340 : || !operand_equal_p (info->ops[idx].base_addr,
2765 117257 : infof->ops[idx].base_addr, 0))
2766 : return false;
2767 :
2768 115310 : store_immediate_info *infol = merged_store->stores.last ();
2769 115310 : tree load_vuse = gimple_vuse (info->ops[idx].stmt);
2770 : /* In this case all vuses should be the same, e.g.
2771 : _1 = s.a; _2 = s.b; _3 = _1 | 1; t.a = _3; _4 = _2 | 2; t.b = _4;
2772 : or
2773 : _1 = s.a; _2 = s.b; t.a = _1; t.b = _2;
2774 : and we can emit the coalesced load next to any of those loads. */
2775 115310 : if (gimple_vuse (infof->ops[idx].stmt) == load_vuse
2776 219578 : && gimple_vuse (infol->ops[idx].stmt) == load_vuse)
2777 : return true;
2778 :
2779 : /* Otherwise, at least for now require that the load has the same
2780 : vuse as the store. See following examples. */
2781 22084 : if (gimple_vuse (info->stmt) != load_vuse)
2782 : return false;
2783 :
2784 17498 : if (gimple_vuse (infof->stmt) != gimple_vuse (infof->ops[idx].stmt)
2785 8749 : || (infof != infol
2786 10266 : && gimple_vuse (infol->stmt) != gimple_vuse (infol->ops[idx].stmt)))
2787 : return false;
2788 :
2789 : /* If the load is from the same location as the store, already
2790 : the construction of the immediate chain info guarantees no intervening
2791 : stores, so no further checks are needed. Example:
2792 : _1 = s.a; _2 = _1 & -7; s.a = _2; _3 = s.b; _4 = _3 & -7; s.b = _4; */
2793 8208 : if (known_eq (info->ops[idx].bitpos, info->bitpos)
2794 8208 : && operand_equal_p (info->ops[idx].base_addr, base_addr, 0))
2795 : return true;
2796 :
2797 : /* Otherwise, we need to punt if any of the loads can be clobbered by any
2798 : of the stores in the group, or any other stores in between those.
2799 : Previous calls to compatible_load_p ensured that for all the
2800 : merged_store->stores IDX loads, no stmts starting with
2801 : merged_store->first_stmt and ending right before merged_store->last_stmt
2802 : clobbers those loads. */
2803 8088 : gimple *first = merged_store->first_stmt;
2804 8088 : gimple *last = merged_store->last_stmt;
2805 : /* The stores are sorted by increasing store bitpos, so if info->stmt store
2806 : comes before the so far first load, we'll be changing
2807 : merged_store->first_stmt. In that case we need to give up if
2808 : any of the earlier processed loads clobber with the stmts in the new
2809 : range. */
2810 8088 : if (info->order < merged_store->first_order)
2811 : {
2812 1347 : for (store_immediate_info *infoc : merged_store->stores)
2813 375 : if (stmts_may_clobber_ref_p (info->stmt, first, infoc->ops[idx].val))
2814 : return false;
2815 222 : first = info->stmt;
2816 : }
2817 : /* Similarly, we could change merged_store->last_stmt, so ensure
2818 : in that case no stmts in the new range clobber any of the earlier
2819 : processed loads. */
2820 7713 : else if (info->order > merged_store->last_order)
2821 : {
2822 48062 : for (store_immediate_info *infoc : merged_store->stores)
2823 25640 : if (stmts_may_clobber_ref_p (last, info->stmt, infoc->ops[idx].val))
2824 : return false;
2825 6996 : last = info->stmt;
2826 : }
2827 : /* And finally, we'd be adding a new load to the set, ensure it isn't
2828 : clobbered in the new range. */
2829 7218 : if (stmts_may_clobber_ref_p (first, last, info->ops[idx].val))
2830 64 : return false;
2831 :
2832 : /* Otherwise, we are looking for:
2833 : _1 = s.a; _2 = _1 ^ 15; t.a = _2; _3 = s.b; _4 = _3 ^ 15; t.b = _4;
2834 : or
2835 : _1 = s.a; t.a = _1; _2 = s.b; t.b = _2; */
2836 : return true;
2837 : }
2838 :
2839 : /* Add all refs loaded to compute VAL to REFS vector. */
2840 :
2841 : void
2842 231 : gather_bswap_load_refs (vec<tree> *refs, tree val)
2843 : {
2844 244 : if (TREE_CODE (val) != SSA_NAME)
2845 : return;
2846 :
2847 242 : gimple *stmt = SSA_NAME_DEF_STMT (val);
2848 242 : if (!is_gimple_assign (stmt))
2849 : return;
2850 :
2851 242 : if (gimple_assign_load_p (stmt))
2852 : {
2853 229 : refs->safe_push (gimple_assign_rhs1 (stmt));
2854 229 : return;
2855 : }
2856 :
2857 13 : switch (gimple_assign_rhs_class (stmt))
2858 : {
2859 2 : case GIMPLE_BINARY_RHS:
2860 2 : gather_bswap_load_refs (refs, gimple_assign_rhs2 (stmt));
2861 : /* FALLTHRU */
2862 13 : case GIMPLE_UNARY_RHS:
2863 13 : gather_bswap_load_refs (refs, gimple_assign_rhs1 (stmt));
2864 13 : break;
2865 0 : default:
2866 0 : gcc_unreachable ();
2867 : }
2868 : }
2869 :
2870 : /* Check if there are any stores in M_STORE_INFO after index I
2871 : (where M_STORE_INFO must be sorted by sort_by_bitpos) that overlap
2872 : a potential group ending with END that have their order
2873 : smaller than LAST_ORDER. ALL_INTEGER_CST_P is true if
2874 : all the stores already merged and the one under consideration
2875 : have rhs_code of INTEGER_CST. Return true if there are no such stores.
2876 : Consider:
2877 : MEM[(long long int *)p_28] = 0;
2878 : MEM[(long long int *)p_28 + 8B] = 0;
2879 : MEM[(long long int *)p_28 + 16B] = 0;
2880 : MEM[(long long int *)p_28 + 24B] = 0;
2881 : _129 = (int) _130;
2882 : MEM[(int *)p_28 + 8B] = _129;
2883 : MEM[(int *)p_28].a = -1;
2884 : We already have
2885 : MEM[(long long int *)p_28] = 0;
2886 : MEM[(int *)p_28].a = -1;
2887 : stmts in the current group and need to consider if it is safe to
2888 : add MEM[(long long int *)p_28 + 8B] = 0; store into the same group.
2889 : There is an overlap between that store and the MEM[(int *)p_28 + 8B] = _129;
2890 : store though, so if we add the MEM[(long long int *)p_28 + 8B] = 0;
2891 : into the group and merging of those 3 stores is successful, merged
2892 : stmts will be emitted at the latest store from that group, i.e.
2893 : LAST_ORDER, which is the MEM[(int *)p_28].a = -1; store.
2894 : The MEM[(int *)p_28 + 8B] = _129; store that originally follows
2895 : the MEM[(long long int *)p_28 + 8B] = 0; would now be before it,
2896 : so we need to refuse merging MEM[(long long int *)p_28 + 8B] = 0;
2897 : into the group. That way it will be its own store group and will
2898 : not be touched. If ALL_INTEGER_CST_P and there are overlapping
2899 : INTEGER_CST stores, those are mergeable using merge_overlapping,
2900 : so don't return false for those.
2901 :
2902 : Similarly, check stores from FIRST_EARLIER (inclusive) to END_EARLIER
2903 : (exclusive), whether they don't overlap the bitrange START to END
2904 : and have order in between FIRST_ORDER and LAST_ORDER. This is to
2905 : prevent merging in cases like:
2906 : MEM <char[12]> [&b + 8B] = {};
2907 : MEM[(short *) &b] = 5;
2908 : _5 = *x_4(D);
2909 : MEM <long long unsigned int> [&b + 2B] = _5;
2910 : MEM[(char *)&b + 16B] = 88;
2911 : MEM[(int *)&b + 20B] = 1;
2912 : The = {} store comes in sort_by_bitpos before the = 88 store, and can't
2913 : be merged with it, because the = _5 store overlaps these and is in between
2914 : them in sort_by_order ordering. If it was merged, the merged store would
2915 : go after the = _5 store and thus change behavior. */
2916 :
2917 : static bool
2918 852568 : check_no_overlap (const vec<store_immediate_info *> &m_store_info,
2919 : unsigned int i,
2920 : bool all_integer_cst_p, unsigned int first_order,
2921 : unsigned int last_order, unsigned HOST_WIDE_INT start,
2922 : unsigned HOST_WIDE_INT end, unsigned int first_earlier,
2923 : unsigned end_earlier)
2924 : {
2925 852568 : unsigned int len = m_store_info.length ();
2926 866937 : for (unsigned int j = first_earlier; j < end_earlier; j++)
2927 : {
2928 14384 : store_immediate_info *info = m_store_info[j];
2929 14384 : if (info->order > first_order
2930 77 : && info->order < last_order
2931 17 : && info->bitpos + info->bitsize > start)
2932 : return false;
2933 : }
2934 940227 : for (++i; i < len; ++i)
2935 : {
2936 491274 : store_immediate_info *info = m_store_info[i];
2937 491274 : if (info->bitpos >= end)
2938 : break;
2939 87693 : if (info->order < last_order
2940 37914 : && (!all_integer_cst_p || info->rhs_code != INTEGER_CST))
2941 : return false;
2942 : }
2943 : return true;
2944 : }
2945 :
2946 : /* Return true if m_store_info[first] and at least one following store
2947 : form a group which store try_size bitsize value which is byte swapped
2948 : from a memory load or some value, or identity from some value.
2949 : This uses the bswap pass APIs. */
2950 :
2951 : bool
2952 284546 : imm_store_chain_info::try_coalesce_bswap (merged_store_group *merged_store,
2953 : unsigned int first,
2954 : unsigned int try_size,
2955 : unsigned int first_earlier)
2956 : {
2957 284546 : unsigned int len = m_store_info.length (), last = first;
2958 284546 : unsigned HOST_WIDE_INT width = m_store_info[first]->bitsize;
2959 284546 : if (width >= try_size)
2960 : return false;
2961 165681 : for (unsigned int i = first + 1; i < len; ++i)
2962 : {
2963 157118 : if (m_store_info[i]->bitpos != m_store_info[first]->bitpos + width
2964 156342 : || m_store_info[i]->lp_nr != merged_store->lp_nr
2965 313460 : || m_store_info[i]->ins_stmt == NULL)
2966 : return false;
2967 155253 : width += m_store_info[i]->bitsize;
2968 155253 : if (width >= try_size)
2969 : {
2970 : last = i;
2971 : break;
2972 : }
2973 : }
2974 73419 : if (width != try_size)
2975 : return false;
2976 :
2977 64306 : bool allow_unaligned
2978 64306 : = !STRICT_ALIGNMENT && param_store_merging_allow_unaligned;
2979 : /* Punt if the combined store would not be aligned and we need alignment. */
2980 64306 : if (!allow_unaligned)
2981 : {
2982 0 : unsigned int align = merged_store->align;
2983 0 : unsigned HOST_WIDE_INT align_base = merged_store->align_base;
2984 0 : for (unsigned int i = first + 1; i <= last; ++i)
2985 : {
2986 0 : unsigned int this_align;
2987 0 : unsigned HOST_WIDE_INT align_bitpos = 0;
2988 0 : get_object_alignment_1 (gimple_assign_lhs (m_store_info[i]->stmt),
2989 : &this_align, &align_bitpos);
2990 0 : if (this_align > align)
2991 : {
2992 0 : align = this_align;
2993 0 : align_base = m_store_info[i]->bitpos - align_bitpos;
2994 : }
2995 : }
2996 0 : unsigned HOST_WIDE_INT align_bitpos
2997 0 : = (m_store_info[first]->bitpos - align_base) & (align - 1);
2998 0 : if (align_bitpos)
2999 0 : align = least_bit_hwi (align_bitpos);
3000 0 : if (align < try_size)
3001 : return false;
3002 : }
3003 :
3004 64306 : tree type;
3005 64306 : switch (try_size)
3006 : {
3007 13407 : case 16: type = uint16_type_node; break;
3008 12004 : case 32: type = uint32_type_node; break;
3009 38895 : case 64: type = uint64_type_node; break;
3010 0 : default: gcc_unreachable ();
3011 : }
3012 64306 : struct symbolic_number n;
3013 64306 : gimple *ins_stmt = NULL;
3014 64306 : int vuse_store = -1;
3015 64306 : unsigned int first_order = merged_store->first_order;
3016 64306 : unsigned int last_order = merged_store->last_order;
3017 64306 : gimple *first_stmt = merged_store->first_stmt;
3018 64306 : gimple *last_stmt = merged_store->last_stmt;
3019 64306 : unsigned HOST_WIDE_INT end = merged_store->start + merged_store->width;
3020 64306 : store_immediate_info *infof = m_store_info[first];
3021 :
3022 215304 : for (unsigned int i = first; i <= last; ++i)
3023 : {
3024 173928 : store_immediate_info *info = m_store_info[i];
3025 173928 : struct symbolic_number this_n = info->n;
3026 173928 : this_n.type = type;
3027 173928 : if (!this_n.base_addr)
3028 12617 : this_n.range = try_size / BITS_PER_UNIT;
3029 : else
3030 : /* Update vuse in case it has changed by output_merged_stores. */
3031 322622 : this_n.vuse = gimple_vuse (info->ins_stmt);
3032 173928 : unsigned int bitpos = info->bitpos - infof->bitpos;
3033 173928 : if (!do_shift_rotate (LSHIFT_EXPR, &this_n,
3034 : BYTES_BIG_ENDIAN
3035 : ? try_size - info->bitsize - bitpos
3036 : : bitpos))
3037 22930 : return false;
3038 173928 : if (this_n.base_addr && vuse_store)
3039 : {
3040 : unsigned int j;
3041 240680 : for (j = first; j <= last; ++j)
3042 383348 : if (this_n.vuse == gimple_vuse (m_store_info[j]->stmt))
3043 : break;
3044 70576 : if (j > last)
3045 : {
3046 49006 : if (vuse_store == 1)
3047 : return false;
3048 : vuse_store = 0;
3049 : }
3050 : }
3051 173928 : if (i == first)
3052 : {
3053 64306 : n = this_n;
3054 64306 : ins_stmt = info->ins_stmt;
3055 : }
3056 : else
3057 : {
3058 109622 : if (n.base_addr && n.vuse != this_n.vuse)
3059 : {
3060 7515 : if (vuse_store == 0)
3061 : return false;
3062 : vuse_store = 1;
3063 : }
3064 105505 : if (info->order > last_order)
3065 : {
3066 102865 : last_order = info->order;
3067 102865 : last_stmt = info->stmt;
3068 : }
3069 2640 : else if (info->order < first_order)
3070 : {
3071 2617 : first_order = info->order;
3072 2617 : first_stmt = info->stmt;
3073 : }
3074 105505 : end = MAX (end, info->bitpos + info->bitsize);
3075 :
3076 105505 : ins_stmt = perform_symbolic_merge (ins_stmt, &n, info->ins_stmt,
3077 : &this_n, &n, BIT_IOR_EXPR);
3078 105505 : if (ins_stmt == NULL)
3079 : return false;
3080 : }
3081 : }
3082 :
3083 41376 : uint64_t cmpxchg, cmpnop;
3084 41376 : bool cast64_to_32;
3085 41376 : find_bswap_or_nop_finalize (&n, &cmpxchg, &cmpnop, &cast64_to_32);
3086 :
3087 : /* A complete byte swap should make the symbolic number to start with
3088 : the largest digit in the highest order byte. Unchanged symbolic
3089 : number indicates a read with same endianness as target architecture. */
3090 41376 : if (n.n != cmpnop && n.n != cmpxchg)
3091 : return false;
3092 :
3093 : /* For now. */
3094 23342 : if (cast64_to_32)
3095 : return false;
3096 :
3097 23341 : if (n.base_addr == NULL_TREE && !is_gimple_val (n.src))
3098 : return false;
3099 :
3100 23341 : if (!check_no_overlap (m_store_info, last, false, first_order, last_order,
3101 : merged_store->start, end, first_earlier, first))
3102 : return false;
3103 :
3104 : /* Don't handle memory copy this way if normal non-bswap processing
3105 : would handle it too. */
3106 23339 : if (n.n == cmpnop && (unsigned) n.n_ops == last - first + 1)
3107 : {
3108 : unsigned int i;
3109 67779 : for (i = first; i <= last; ++i)
3110 45445 : if (m_store_info[i]->rhs_code != MEM_REF)
3111 : break;
3112 22692 : if (i == last + 1)
3113 : return false;
3114 : }
3115 :
3116 1005 : if (n.n == cmpxchg)
3117 647 : switch (try_size)
3118 : {
3119 : case 16:
3120 : /* Will emit LROTATE_EXPR. */
3121 : break;
3122 182 : case 32:
3123 182 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
3124 182 : && can_open_code_p (bswap_optab, SImode))
3125 : break;
3126 : return false;
3127 113 : case 64:
3128 113 : if (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
3129 113 : && can_open_code_p (bswap_optab, DImode))
3130 : break;
3131 : return false;
3132 : default:
3133 : gcc_unreachable ();
3134 : }
3135 :
3136 905 : if (!allow_unaligned && n.base_addr)
3137 : {
3138 0 : unsigned int align = get_object_alignment (n.src);
3139 0 : if (align < try_size)
3140 : return false;
3141 : }
3142 :
3143 : /* If each load has vuse of the corresponding store, need to verify
3144 : the loads can be sunk right before the last store. */
3145 905 : if (vuse_store == 1)
3146 : {
3147 92 : auto_vec<tree, 64> refs;
3148 321 : for (unsigned int i = first; i <= last; ++i)
3149 229 : gather_bswap_load_refs (&refs,
3150 229 : gimple_assign_rhs1 (m_store_info[i]->stmt));
3151 :
3152 437 : for (tree ref : refs)
3153 180 : if (stmts_may_clobber_ref_p (first_stmt, last_stmt, ref))
3154 19 : return false;
3155 73 : n.vuse = NULL_TREE;
3156 92 : }
3157 :
3158 886 : infof->n = n;
3159 886 : infof->ins_stmt = ins_stmt;
3160 4022 : for (unsigned int i = first; i <= last; ++i)
3161 : {
3162 4574 : m_store_info[i]->rhs_code = n.n == cmpxchg ? LROTATE_EXPR : NOP_EXPR;
3163 3136 : m_store_info[i]->ops[0].base_addr = NULL_TREE;
3164 3136 : m_store_info[i]->ops[1].base_addr = NULL_TREE;
3165 3136 : if (i != first)
3166 2250 : merged_store->merge_into (m_store_info[i]);
3167 : }
3168 :
3169 : return true;
3170 : }
3171 :
3172 : /* Go through the candidate stores recorded in m_store_info and merge them
3173 : into merged_store_group objects recorded into m_merged_store_groups
3174 : representing the widened stores. Return true if coalescing was successful
3175 : and the number of widened stores is fewer than the original number
3176 : of stores. */
3177 :
3178 : bool
3179 522013 : imm_store_chain_info::coalesce_immediate_stores ()
3180 : {
3181 : /* Anything less can't be processed. */
3182 522013 : if (m_store_info.length () < 2)
3183 : return false;
3184 :
3185 522013 : if (dump_file && (dump_flags & TDF_DETAILS))
3186 25 : fprintf (dump_file, "Attempting to coalesce %u stores in chain\n",
3187 : m_store_info.length ());
3188 :
3189 522013 : store_immediate_info *info;
3190 522013 : unsigned int i, ignore = 0;
3191 522013 : unsigned int first_earlier = 0;
3192 522013 : unsigned int end_earlier = 0;
3193 :
3194 : /* Order the stores by the bitposition they write to. */
3195 522013 : m_store_info.qsort (sort_by_bitpos);
3196 :
3197 522013 : info = m_store_info[0];
3198 522013 : merged_store_group *merged_store = new merged_store_group (info);
3199 522013 : if (dump_file && (dump_flags & TDF_DETAILS))
3200 25 : fputs ("New store group\n", dump_file);
3201 :
3202 2239161 : FOR_EACH_VEC_ELT (m_store_info, i, info)
3203 : {
3204 1717148 : unsigned HOST_WIDE_INT new_bitregion_start, new_bitregion_end;
3205 :
3206 1717148 : if (i <= ignore)
3207 608568 : goto done;
3208 :
3209 : while (first_earlier < end_earlier
3210 1384749 : && (m_store_info[first_earlier]->bitpos
3211 287590 : + m_store_info[first_earlier]->bitsize
3212 287590 : <= merged_store->start))
3213 276169 : first_earlier++;
3214 :
3215 : /* First try to handle group of stores like:
3216 : p[0] = data >> 24;
3217 : p[1] = data >> 16;
3218 : p[2] = data >> 8;
3219 : p[3] = data;
3220 : using the bswap framework. */
3221 1108580 : if (info->bitpos == merged_store->start + merged_store->width
3222 725436 : && merged_store->stores.length () == 1
3223 397475 : && merged_store->stores[0]->ins_stmt != NULL
3224 133818 : && info->lp_nr == merged_store->lp_nr
3225 1242398 : && info->ins_stmt != NULL)
3226 : {
3227 : unsigned int try_size;
3228 378713 : for (try_size = 64; try_size >= 16; try_size >>= 1)
3229 284546 : if (try_coalesce_bswap (merged_store, i - 1, try_size,
3230 : first_earlier))
3231 : break;
3232 :
3233 95053 : if (try_size >= 16)
3234 : {
3235 886 : ignore = i + merged_store->stores.length () - 1;
3236 886 : m_merged_store_groups.safe_push (merged_store);
3237 886 : if (ignore < m_store_info.length ())
3238 : {
3239 335 : merged_store = new merged_store_group (m_store_info[ignore]);
3240 335 : end_earlier = ignore;
3241 : }
3242 : else
3243 551 : merged_store = NULL;
3244 886 : goto done;
3245 : }
3246 : }
3247 :
3248 1107694 : new_bitregion_start
3249 1107694 : = MIN (merged_store->bitregion_start, info->bitregion_start);
3250 1107694 : new_bitregion_end
3251 1107694 : = MAX (merged_store->bitregion_end, info->bitregion_end);
3252 :
3253 1107694 : if (info->order >= merged_store->first_nonmergeable_order
3254 1106078 : || (((new_bitregion_end - new_bitregion_start + 1) / BITS_PER_UNIT)
3255 1106078 : > (unsigned) param_store_merging_max_size))
3256 : ;
3257 :
3258 : /* |---store 1---|
3259 : |---store 2---|
3260 : Overlapping stores. */
3261 1105988 : else if (IN_RANGE (info->bitpos, merged_store->start,
3262 : merged_store->start + merged_store->width - 1)
3263 : /* |---store 1---||---store 2---|
3264 : Handle also the consecutive INTEGER_CST stores case here,
3265 : as we have here the code to deal with overlaps. */
3266 1105988 : || (info->bitregion_start <= merged_store->bitregion_end
3267 730006 : && info->rhs_code == INTEGER_CST
3268 543406 : && merged_store->only_constants
3269 510979 : && merged_store->can_be_merged_into (info)))
3270 : {
3271 : /* Only allow overlapping stores of constants. */
3272 629055 : if (info->rhs_code == INTEGER_CST
3273 621302 : && merged_store->only_constants
3274 621210 : && info->lp_nr == merged_store->lp_nr)
3275 : {
3276 621198 : unsigned int first_order
3277 621198 : = MIN (merged_store->first_order, info->order);
3278 621198 : unsigned int last_order
3279 621198 : = MAX (merged_store->last_order, info->order);
3280 621198 : unsigned HOST_WIDE_INT end
3281 621198 : = MAX (merged_store->start + merged_store->width,
3282 : info->bitpos + info->bitsize);
3283 621198 : if (check_no_overlap (m_store_info, i, true, first_order,
3284 : last_order, merged_store->start, end,
3285 : first_earlier, end_earlier))
3286 : {
3287 : /* check_no_overlap call above made sure there are no
3288 : overlapping stores with non-INTEGER_CST rhs_code
3289 : in between the first and last of the stores we've
3290 : just merged. If there are any INTEGER_CST rhs_code
3291 : stores in between, we need to merge_overlapping them
3292 : even if in the sort_by_bitpos order there are other
3293 : overlapping stores in between. Keep those stores as is.
3294 : Example:
3295 : MEM[(int *)p_28] = 0;
3296 : MEM[(char *)p_28 + 3B] = 1;
3297 : MEM[(char *)p_28 + 1B] = 2;
3298 : MEM[(char *)p_28 + 2B] = MEM[(char *)p_28 + 6B];
3299 : We can't merge the zero store with the store of two and
3300 : not merge anything else, because the store of one is
3301 : in the original order in between those two, but in
3302 : store_by_bitpos order it comes after the last store that
3303 : we can't merge with them. We can merge the first 3 stores
3304 : and keep the last store as is though. */
3305 621168 : unsigned int len = m_store_info.length ();
3306 621168 : unsigned int try_order = last_order;
3307 621168 : unsigned int first_nonmergeable_order;
3308 621168 : unsigned int k;
3309 621168 : bool last_iter = false;
3310 621168 : int attempts = 0;
3311 646427 : do
3312 : {
3313 646427 : unsigned int max_order = 0;
3314 646427 : unsigned int min_order = first_order;
3315 646427 : unsigned first_nonmergeable_int_order = ~0U;
3316 646427 : unsigned HOST_WIDE_INT this_end = end;
3317 646427 : unsigned HOST_WIDE_INT this_bitregion_start
3318 : = new_bitregion_start;
3319 646427 : unsigned HOST_WIDE_INT this_bitregion_end
3320 : = new_bitregion_end;
3321 646427 : k = i;
3322 646427 : first_nonmergeable_order = ~0U;
3323 783661 : for (unsigned int j = i + 1; j < len; ++j)
3324 : {
3325 476292 : store_immediate_info *info2 = m_store_info[j];
3326 476292 : if (info2->bitpos >= this_end)
3327 : break;
3328 137237 : if (info2->order < try_order)
3329 : {
3330 85686 : if (info2->rhs_code != INTEGER_CST
3331 85683 : || info2->lp_nr != merged_store->lp_nr)
3332 : {
3333 : /* Normally check_no_overlap makes sure this
3334 : doesn't happen, but if end grows below,
3335 : then we need to process more stores than
3336 : check_no_overlap verified. Example:
3337 : MEM[(int *)p_5] = 0;
3338 : MEM[(short *)p_5 + 3B] = 1;
3339 : MEM[(char *)p_5 + 4B] = _9;
3340 : MEM[(char *)p_5 + 2B] = 2; */
3341 : k = 0;
3342 : break;
3343 : }
3344 85683 : if (info2->bitregion_start
3345 : < this_bitregion_start)
3346 : this_bitregion_start = info2->bitregion_start;
3347 85683 : if (info2->bitregion_end
3348 : > this_bitregion_end)
3349 : this_bitregion_end = info2->bitregion_end;
3350 85683 : if (((this_bitregion_end - this_bitregion_start
3351 85683 : + 1) / BITS_PER_UNIT)
3352 : > (unsigned) param_store_merging_max_size)
3353 : {
3354 : k = 0;
3355 : break;
3356 : }
3357 85683 : k = j;
3358 85683 : min_order = MIN (min_order, info2->order);
3359 85683 : this_end = MAX (this_end,
3360 : info2->bitpos + info2->bitsize);
3361 : }
3362 51551 : else if (info2->rhs_code == INTEGER_CST
3363 48416 : && info2->lp_nr == merged_store->lp_nr
3364 48416 : && !last_iter)
3365 : {
3366 48416 : max_order = MAX (max_order, info2->order + 1);
3367 48416 : first_nonmergeable_int_order
3368 48416 : = MIN (first_nonmergeable_int_order,
3369 : info2->order);
3370 : }
3371 : else
3372 3135 : first_nonmergeable_order
3373 3135 : = MIN (first_nonmergeable_order, info2->order);
3374 : }
3375 646427 : if (k > i
3376 646427 : && !check_no_overlap (m_store_info, len - 1, true,
3377 : min_order, try_order,
3378 : merged_store->start, this_end,
3379 : first_earlier, end_earlier))
3380 : k = 0;
3381 646427 : if (k == 0)
3382 : {
3383 3 : if (last_order == try_order)
3384 : break;
3385 : /* If this failed, but only because we grew
3386 : try_order, retry with the last working one,
3387 : so that we merge at least something. */
3388 0 : try_order = last_order;
3389 0 : last_iter = true;
3390 0 : continue;
3391 : }
3392 646424 : last_order = try_order;
3393 : /* Retry with a larger try_order to see if we could
3394 : merge some further INTEGER_CST stores. */
3395 646424 : if (max_order
3396 646424 : && (first_nonmergeable_int_order
3397 646424 : < first_nonmergeable_order))
3398 : {
3399 25260 : try_order = MIN (max_order,
3400 : first_nonmergeable_order);
3401 25260 : try_order
3402 25260 : = MIN (try_order,
3403 : merged_store->first_nonmergeable_order);
3404 25260 : if (try_order > last_order && ++attempts < 16)
3405 25259 : continue;
3406 : }
3407 621165 : first_nonmergeable_order
3408 621165 : = MIN (first_nonmergeable_order,
3409 : first_nonmergeable_int_order);
3410 : end = this_end;
3411 : break;
3412 : }
3413 : while (1);
3414 :
3415 621168 : if (k != 0)
3416 : {
3417 621165 : merged_store->merge_overlapping (info);
3418 :
3419 621165 : merged_store->first_nonmergeable_order
3420 621165 : = MIN (merged_store->first_nonmergeable_order,
3421 : first_nonmergeable_order);
3422 :
3423 706021 : for (unsigned int j = i + 1; j <= k; j++)
3424 : {
3425 84856 : store_immediate_info *info2 = m_store_info[j];
3426 84856 : gcc_assert (info2->bitpos < end);
3427 84856 : if (info2->order < last_order)
3428 : {
3429 84799 : gcc_assert (info2->rhs_code == INTEGER_CST);
3430 84799 : if (info != info2)
3431 84799 : merged_store->merge_overlapping (info2);
3432 : }
3433 : /* Other stores are kept and not merged in any
3434 : way. */
3435 : }
3436 621165 : ignore = k;
3437 621165 : goto done;
3438 : }
3439 : }
3440 : }
3441 : }
3442 : /* |---store 1---||---store 2---|
3443 : This store is consecutive to the previous one.
3444 : Merge it into the current store group. There can be gaps in between
3445 : the stores, but there can't be gaps in between bitregions. */
3446 476933 : else if (info->bitregion_start <= merged_store->bitregion_end
3447 476933 : && merged_store->can_be_merged_into (info))
3448 : {
3449 154742 : store_immediate_info *infof = merged_store->stores[0];
3450 :
3451 : /* All the rhs_code ops that take 2 operands are commutative,
3452 : swap the operands if it could make the operands compatible. */
3453 154742 : if (infof->ops[0].base_addr
3454 142767 : && infof->ops[1].base_addr
3455 1320 : && info->ops[0].base_addr
3456 1320 : && info->ops[1].base_addr
3457 1320 : && known_eq (info->ops[1].bitpos - infof->ops[0].bitpos,
3458 : info->bitpos - infof->bitpos)
3459 156052 : && operand_equal_p (info->ops[1].base_addr,
3460 : infof->ops[0].base_addr, 0))
3461 : {
3462 1103 : std::swap (info->ops[0], info->ops[1]);
3463 1103 : info->ops_swapped_p = true;
3464 : }
3465 154742 : if (check_no_overlap (m_store_info, i, false,
3466 154742 : MIN (merged_store->first_order, info->order),
3467 154742 : MAX (merged_store->last_order, info->order),
3468 : merged_store->start,
3469 154742 : MAX (merged_store->start + merged_store->width,
3470 : info->bitpos + info->bitsize),
3471 : first_earlier, end_earlier))
3472 : {
3473 : /* Turn MEM_REF into BIT_INSERT_EXPR for bit-field stores. */
3474 154740 : if (info->rhs_code == MEM_REF && infof->rhs_code != MEM_REF)
3475 : {
3476 765 : info->rhs_code = BIT_INSERT_EXPR;
3477 765 : info->ops[0].val = gimple_assign_rhs1 (info->stmt);
3478 765 : info->ops[0].base_addr = NULL_TREE;
3479 : }
3480 153975 : else if (infof->rhs_code == MEM_REF && info->rhs_code != MEM_REF)
3481 : {
3482 8 : for (store_immediate_info *infoj : merged_store->stores)
3483 : {
3484 2 : infoj->rhs_code = BIT_INSERT_EXPR;
3485 2 : infoj->ops[0].val = gimple_assign_rhs1 (infoj->stmt);
3486 2 : infoj->ops[0].base_addr = NULL_TREE;
3487 : }
3488 2 : merged_store->bit_insertion = true;
3489 : }
3490 154740 : if ((infof->ops[0].base_addr
3491 142763 : ? compatible_load_p (merged_store, info, base_addr, 0)
3492 11977 : : !info->ops[0].base_addr)
3493 310800 : && (infof->ops[1].base_addr
3494 1320 : ? compatible_load_p (merged_store, info, base_addr, 1)
3495 120885 : : !info->ops[1].base_addr))
3496 : {
3497 122198 : merged_store->merge_into (info);
3498 122198 : goto done;
3499 : }
3500 : }
3501 : }
3502 :
3503 : /* |---store 1---| <gap> |---store 2---|.
3504 : Gap between stores or the rhs not compatible. Start a new group. */
3505 :
3506 : /* Try to apply all the stores recorded for the group to determine
3507 : the bitpattern they write and discard it if that fails.
3508 : This will also reject single-store groups. */
3509 364331 : if (merged_store->apply_stores ())
3510 58788 : m_merged_store_groups.safe_push (merged_store);
3511 : else
3512 305543 : delete merged_store;
3513 :
3514 364331 : merged_store = new merged_store_group (info);
3515 364331 : end_earlier = i;
3516 364331 : if (dump_file && (dump_flags & TDF_DETAILS))
3517 1 : fputs ("New store group\n", dump_file);
3518 :
3519 1717148 : done:
3520 1717148 : if (dump_file && (dump_flags & TDF_DETAILS))
3521 : {
3522 227 : fprintf (dump_file, "Store %u:\nbitsize:" HOST_WIDE_INT_PRINT_DEC
3523 : " bitpos:" HOST_WIDE_INT_PRINT_DEC " val:",
3524 : i, info->bitsize, info->bitpos);
3525 227 : print_generic_expr (dump_file, gimple_assign_rhs1 (info->stmt));
3526 227 : fputc ('\n', dump_file);
3527 : }
3528 : }
3529 :
3530 : /* Record or discard the last store group. */
3531 522013 : if (merged_store)
3532 : {
3533 521462 : if (merged_store->apply_stores ())
3534 362714 : m_merged_store_groups.safe_push (merged_store);
3535 : else
3536 158748 : delete merged_store;
3537 : }
3538 :
3539 1432388 : gcc_assert (m_merged_store_groups.length () <= m_store_info.length ());
3540 :
3541 522013 : bool success
3542 522013 : = !m_merged_store_groups.is_empty ()
3543 388362 : && m_merged_store_groups.length () < m_store_info.length ();
3544 :
3545 388362 : if (success && dump_file)
3546 94 : fprintf (dump_file, "Coalescing successful!\nMerged into %u stores\n",
3547 : m_merged_store_groups.length ());
3548 :
3549 : return success;
3550 : }
3551 :
3552 : /* Return the type to use for the merged stores or loads described by STMTS.
3553 : This is needed to get the alias sets right. If IS_LOAD, look for rhs,
3554 : otherwise lhs. Additionally set *CLIQUEP and *BASEP to MR_DEPENDENCE_*
3555 : of the MEM_REFs if any. */
3556 :
3557 : static tree
3558 99926 : get_alias_type_for_stmts (vec<gimple *> &stmts, bool is_load,
3559 : unsigned short *cliquep, unsigned short *basep)
3560 : {
3561 99926 : gimple *stmt;
3562 99926 : unsigned int i;
3563 99926 : tree type = NULL_TREE;
3564 99926 : tree ret = NULL_TREE;
3565 99926 : *cliquep = 0;
3566 99926 : *basep = 0;
3567 :
3568 341736 : FOR_EACH_VEC_ELT (stmts, i, stmt)
3569 : {
3570 241810 : tree ref = is_load ? gimple_assign_rhs1 (stmt)
3571 233778 : : gimple_assign_lhs (stmt);
3572 241810 : tree type1 = reference_alias_ptr_type (ref);
3573 241810 : tree base = get_base_address (ref);
3574 :
3575 241810 : if (i == 0)
3576 : {
3577 99926 : if (TREE_CODE (base) == MEM_REF)
3578 : {
3579 14947 : *cliquep = MR_DEPENDENCE_CLIQUE (base);
3580 14947 : *basep = MR_DEPENDENCE_BASE (base);
3581 : }
3582 99926 : ret = type = type1;
3583 99926 : continue;
3584 : }
3585 141884 : if (!alias_ptr_types_compatible_p (type, type1))
3586 88969 : ret = ptr_type_node;
3587 141884 : if (TREE_CODE (base) != MEM_REF
3588 21358 : || *cliquep != MR_DEPENDENCE_CLIQUE (base)
3589 161754 : || *basep != MR_DEPENDENCE_BASE (base))
3590 : {
3591 122014 : *cliquep = 0;
3592 122014 : *basep = 0;
3593 : }
3594 : }
3595 99926 : return ret;
3596 : }
3597 :
3598 : /* Return the location_t information we can find among the statements
3599 : in STMTS. */
3600 :
3601 : static location_t
3602 99963 : get_location_for_stmts (vec<gimple *> &stmts)
3603 : {
3604 303558 : for (gimple *stmt : stmts)
3605 102060 : if (gimple_has_location (stmt))
3606 98391 : return gimple_location (stmt);
3607 :
3608 : return UNKNOWN_LOCATION;
3609 : }
3610 :
3611 : /* Used to describe a store resulting from splitting a wide store in smaller
3612 : regularly-sized stores in split_group. */
3613 :
3614 947627 : class split_store
3615 : {
3616 : public:
3617 : unsigned HOST_WIDE_INT bytepos;
3618 : unsigned HOST_WIDE_INT size;
3619 : unsigned HOST_WIDE_INT align;
3620 : auto_vec<store_immediate_info *> orig_stores;
3621 : /* True if there is a single orig stmt covering the whole split store. */
3622 : bool orig;
3623 : split_store (unsigned HOST_WIDE_INT, unsigned HOST_WIDE_INT,
3624 : unsigned HOST_WIDE_INT);
3625 : };
3626 :
3627 : /* Simple constructor. */
3628 :
3629 947627 : split_store::split_store (unsigned HOST_WIDE_INT bp,
3630 : unsigned HOST_WIDE_INT sz,
3631 : unsigned HOST_WIDE_INT al)
3632 947627 : : bytepos (bp), size (sz), align (al), orig (false)
3633 : {
3634 947627 : orig_stores.create (0);
3635 0 : }
3636 :
3637 : /* Record all stores in GROUP that write to the region starting at BITPOS and
3638 : is of size BITSIZE. Record infos for such statements in STORES if
3639 : non-NULL. The stores in GROUP must be sorted by bitposition. Return INFO
3640 : if there is exactly one original store in the range (in that case ignore
3641 : clobber stmts, unless there are only clobber stmts). */
3642 :
3643 : static store_immediate_info *
3644 7562419 : find_constituent_stores (class merged_store_group *group,
3645 : vec<store_immediate_info *> *stores,
3646 : unsigned int *first,
3647 : unsigned HOST_WIDE_INT bitpos,
3648 : unsigned HOST_WIDE_INT bitsize)
3649 : {
3650 7562419 : store_immediate_info *info, *ret = NULL;
3651 7562419 : unsigned int i;
3652 7562419 : bool second = false;
3653 7562419 : bool update_first = true;
3654 7562419 : unsigned HOST_WIDE_INT end = bitpos + bitsize;
3655 19820148 : for (i = *first; group->stores.iterate (i, &info); ++i)
3656 : {
3657 16610475 : unsigned HOST_WIDE_INT stmt_start = info->bitpos;
3658 16610475 : unsigned HOST_WIDE_INT stmt_end = stmt_start + info->bitsize;
3659 16610475 : if (stmt_end <= bitpos)
3660 : {
3661 : /* BITPOS passed to this function never decreases from within the
3662 : same split_group call, so optimize and don't scan info records
3663 : which are known to end before or at BITPOS next time.
3664 : Only do it if all stores before this one also pass this. */
3665 4651332 : if (update_first)
3666 2140600 : *first = i + 1;
3667 4651332 : continue;
3668 : }
3669 : else
3670 11959143 : update_first = false;
3671 :
3672 : /* The stores in GROUP are ordered by bitposition so if we're past
3673 : the region for this group return early. */
3674 11959143 : if (stmt_start >= end)
3675 : return ret;
3676 :
3677 8000690 : if (gimple_clobber_p (info->stmt))
3678 : {
3679 789126 : if (stores)
3680 36722 : stores->safe_push (info);
3681 789126 : if (ret == NULL)
3682 766809 : ret = info;
3683 789126 : continue;
3684 : }
3685 7211564 : if (stores)
3686 : {
3687 1088053 : stores->safe_push (info);
3688 1088053 : if (ret && !gimple_clobber_p (ret->stmt))
3689 : {
3690 : ret = NULL;
3691 : second = true;
3692 : }
3693 : }
3694 6123511 : else if (ret && !gimple_clobber_p (ret->stmt))
3695 : return NULL;
3696 6713034 : if (!second)
3697 6674913 : ret = info;
3698 : }
3699 : return ret;
3700 : }
3701 :
3702 : /* Return how many SSA_NAMEs used to compute value to store in the INFO
3703 : store have multiple uses. If any SSA_NAME has multiple uses, also
3704 : count statements needed to compute it. */
3705 :
3706 : static unsigned
3707 1196876 : count_multiple_uses (store_immediate_info *info)
3708 : {
3709 1196876 : gimple *stmt = info->stmt;
3710 1196876 : unsigned ret = 0;
3711 1196876 : switch (info->rhs_code)
3712 : {
3713 : case INTEGER_CST:
3714 : case STRING_CST:
3715 : return 0;
3716 4903 : case BIT_AND_EXPR:
3717 4903 : case BIT_IOR_EXPR:
3718 4903 : case BIT_XOR_EXPR:
3719 4903 : if (info->bit_not_p)
3720 : {
3721 65 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3722 : ret = 1; /* Fall through below to return
3723 : the BIT_NOT_EXPR stmt and then
3724 : BIT_{AND,IOR,XOR}_EXPR and anything it
3725 : uses. */
3726 : else
3727 : /* stmt is after this the BIT_NOT_EXPR. */
3728 65 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3729 : }
3730 4903 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3731 : {
3732 26 : ret += 1 + info->ops[0].bit_not_p;
3733 26 : if (info->ops[1].base_addr)
3734 26 : ret += 1 + info->ops[1].bit_not_p;
3735 26 : return ret + 1;
3736 : }
3737 4877 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3738 : /* stmt is now the BIT_*_EXPR. */
3739 4877 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3740 2126 : ret += 1 + info->ops[info->ops_swapped_p].bit_not_p;
3741 2751 : else if (info->ops[info->ops_swapped_p].bit_not_p)
3742 : {
3743 171 : gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3744 171 : if (!has_single_use (gimple_assign_rhs1 (stmt2)))
3745 0 : ++ret;
3746 : }
3747 4877 : if (info->ops[1].base_addr == NULL_TREE)
3748 : {
3749 331 : gcc_checking_assert (!info->ops_swapped_p);
3750 : return ret;
3751 : }
3752 4546 : if (!has_single_use (gimple_assign_rhs2 (stmt)))
3753 2068 : ret += 1 + info->ops[1 - info->ops_swapped_p].bit_not_p;
3754 2478 : else if (info->ops[1 - info->ops_swapped_p].bit_not_p)
3755 : {
3756 19 : gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
3757 19 : if (!has_single_use (gimple_assign_rhs1 (stmt2)))
3758 0 : ++ret;
3759 : }
3760 : return ret;
3761 291365 : case MEM_REF:
3762 291365 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3763 191626 : return 1 + info->ops[0].bit_not_p;
3764 99739 : else if (info->ops[0].bit_not_p)
3765 : {
3766 166 : stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
3767 166 : if (!has_single_use (gimple_assign_rhs1 (stmt)))
3768 : return 1;
3769 : }
3770 : return 0;
3771 9597 : case BIT_INSERT_EXPR:
3772 9597 : return has_single_use (gimple_assign_rhs1 (stmt)) ? 0 : 1;
3773 0 : default:
3774 0 : gcc_unreachable ();
3775 : }
3776 : }
3777 :
3778 : /* Split a merged store described by GROUP by populating the SPLIT_STORES
3779 : vector (if non-NULL) with split_store structs describing the byte offset
3780 : (from the base), the bit size and alignment of each store as well as the
3781 : original statements involved in each such split group.
3782 : This is to separate the splitting strategy from the statement
3783 : building/emission/linking done in output_merged_store.
3784 : Return number of new stores.
3785 : If ALLOW_UNALIGNED_STORE is false, then all stores must be aligned.
3786 : If ALLOW_UNALIGNED_LOAD is false, then all loads must be aligned.
3787 : BZERO_FIRST may be true only when the first store covers the whole group
3788 : and clears it; if BZERO_FIRST is true, keep that first store in the set
3789 : unmodified and emit further stores for the overrides only.
3790 : If SPLIT_STORES is NULL, it is just a dry run to count number of
3791 : new stores. */
3792 :
3793 : static unsigned int
3794 1048263 : split_group (merged_store_group *group, bool allow_unaligned_store,
3795 : bool allow_unaligned_load, bool bzero_first,
3796 : vec<split_store *> *split_stores,
3797 : unsigned *total_orig,
3798 : unsigned *total_new)
3799 : {
3800 1048263 : unsigned HOST_WIDE_INT pos = group->bitregion_start;
3801 1048263 : unsigned HOST_WIDE_INT size = group->bitregion_end - pos;
3802 1048263 : unsigned HOST_WIDE_INT bytepos = pos / BITS_PER_UNIT;
3803 1048263 : unsigned HOST_WIDE_INT group_align = group->align;
3804 1048263 : unsigned HOST_WIDE_INT align_base = group->align_base;
3805 1048263 : unsigned HOST_WIDE_INT group_load_align = group_align;
3806 1048263 : bool any_orig = false;
3807 :
3808 1048263 : gcc_assert ((size % BITS_PER_UNIT == 0) && (pos % BITS_PER_UNIT == 0));
3809 :
3810 : /* For bswap framework using sets of stores, all the checking has been done
3811 : earlier in try_coalesce_bswap and the result always needs to be emitted
3812 : as a single store. Likewise for string concatenation. */
3813 1048263 : if (group->stores[0]->rhs_code == LROTATE_EXPR
3814 1046679 : || group->stores[0]->rhs_code == NOP_EXPR
3815 2093868 : || group->string_concatenation)
3816 : {
3817 2766 : gcc_assert (!bzero_first);
3818 2766 : if (total_orig)
3819 : {
3820 : /* Avoid the old/new stmt count heuristics. It should be
3821 : always beneficial. */
3822 922 : total_new[0] = 1;
3823 922 : total_orig[0] = 2;
3824 : }
3825 :
3826 2766 : if (split_stores)
3827 : {
3828 922 : unsigned HOST_WIDE_INT align_bitpos
3829 922 : = (group->start - align_base) & (group_align - 1);
3830 922 : unsigned HOST_WIDE_INT align = group_align;
3831 922 : if (align_bitpos)
3832 130 : align = least_bit_hwi (align_bitpos);
3833 922 : bytepos = group->start / BITS_PER_UNIT;
3834 922 : split_store *store
3835 922 : = new split_store (bytepos, group->width, align);
3836 922 : unsigned int first = 0;
3837 922 : find_constituent_stores (group, &store->orig_stores,
3838 : &first, group->start, group->width);
3839 922 : split_stores->safe_push (store);
3840 : }
3841 :
3842 : return 1;
3843 : }
3844 :
3845 1045497 : unsigned int ret = 0, first = 0;
3846 1045497 : unsigned HOST_WIDE_INT try_pos = bytepos;
3847 :
3848 1045497 : if (total_orig)
3849 : {
3850 341623 : unsigned int i;
3851 341623 : store_immediate_info *info = group->stores[0];
3852 :
3853 341623 : total_new[0] = 0;
3854 341623 : total_orig[0] = 1; /* The orig store. */
3855 341623 : info = group->stores[0];
3856 341623 : if (info->ops[0].base_addr)
3857 78964 : total_orig[0]++;
3858 341623 : if (info->ops[1].base_addr)
3859 1156 : total_orig[0]++;
3860 341623 : switch (info->rhs_code)
3861 : {
3862 1255 : case BIT_AND_EXPR:
3863 1255 : case BIT_IOR_EXPR:
3864 1255 : case BIT_XOR_EXPR:
3865 1255 : total_orig[0]++; /* The orig BIT_*_EXPR stmt. */
3866 1255 : break;
3867 : default:
3868 : break;
3869 : }
3870 341623 : total_orig[0] *= group->stores.length ();
3871 :
3872 1431198 : FOR_EACH_VEC_ELT (group->stores, i, info)
3873 : {
3874 1089575 : total_new[0] += count_multiple_uses (info);
3875 1089575 : total_orig[0] += (info->bit_not_p
3876 1089575 : + info->ops[0].bit_not_p
3877 1089575 : + info->ops[1].bit_not_p);
3878 : }
3879 : }
3880 :
3881 1045497 : if (!allow_unaligned_load)
3882 0 : for (int i = 0; i < 2; ++i)
3883 0 : if (group->load_align[i])
3884 0 : group_load_align = MIN (group_load_align, group->load_align[i]);
3885 :
3886 1045497 : if (bzero_first)
3887 : {
3888 : store_immediate_info *gstore;
3889 23731 : FOR_EACH_VEC_ELT (group->stores, first, gstore)
3890 23731 : if (!gimple_clobber_p (gstore->stmt))
3891 : break;
3892 22556 : ++first;
3893 22556 : ret = 1;
3894 22556 : if (split_stores)
3895 : {
3896 1928 : split_store *store
3897 1928 : = new split_store (bytepos, gstore->bitsize, align_base);
3898 1928 : store->orig_stores.safe_push (gstore);
3899 1928 : store->orig = true;
3900 1928 : any_orig = true;
3901 1928 : split_stores->safe_push (store);
3902 : }
3903 : }
3904 :
3905 5396359 : while (size > 0)
3906 : {
3907 4350862 : if ((allow_unaligned_store || group_align <= BITS_PER_UNIT)
3908 1898755 : && (group->mask[try_pos - bytepos] == (unsigned char) ~0U
3909 1883012 : || (bzero_first && group->val[try_pos - bytepos] == 0)))
3910 : {
3911 : /* Skip padding bytes. */
3912 643811 : ++try_pos;
3913 643811 : size -= BITS_PER_UNIT;
3914 643811 : continue;
3915 : }
3916 :
3917 3707051 : unsigned HOST_WIDE_INT try_bitpos = try_pos * BITS_PER_UNIT;
3918 3707051 : unsigned int try_size = MAX_STORE_BITSIZE, nonmasked;
3919 3707051 : unsigned HOST_WIDE_INT align_bitpos
3920 3707051 : = (try_bitpos - align_base) & (group_align - 1);
3921 3707051 : unsigned HOST_WIDE_INT align = group_align;
3922 3707051 : bool found_orig = false;
3923 3707051 : if (align_bitpos)
3924 990048 : align = least_bit_hwi (align_bitpos);
3925 3707051 : if (!allow_unaligned_store)
3926 2499027 : try_size = MIN (try_size, align);
3927 3707051 : if (!allow_unaligned_load)
3928 : {
3929 : /* If we can't do or don't want to do unaligned stores
3930 : as well as loads, we need to take the loads into account
3931 : as well. */
3932 0 : unsigned HOST_WIDE_INT load_align = group_load_align;
3933 0 : align_bitpos = (try_bitpos - align_base) & (load_align - 1);
3934 0 : if (align_bitpos)
3935 0 : load_align = least_bit_hwi (align_bitpos);
3936 0 : for (int i = 0; i < 2; ++i)
3937 0 : if (group->load_align[i])
3938 : {
3939 0 : align_bitpos
3940 0 : = known_alignment (try_bitpos
3941 0 : - group->stores[0]->bitpos
3942 0 : + group->stores[0]->ops[i].bitpos
3943 0 : - group->load_align_base[i]);
3944 0 : if (align_bitpos & (group_load_align - 1))
3945 : {
3946 0 : unsigned HOST_WIDE_INT a = least_bit_hwi (align_bitpos);
3947 0 : load_align = MIN (load_align, a);
3948 : }
3949 : }
3950 0 : try_size = MIN (try_size, load_align);
3951 : }
3952 3707051 : store_immediate_info *info
3953 3707051 : = find_constituent_stores (group, NULL, &first, try_bitpos, try_size);
3954 3707051 : if (info && !gimple_clobber_p (info->stmt))
3955 : {
3956 : /* If there is just one original statement for the range, see if
3957 : we can just reuse the original store which could be even larger
3958 : than try_size. */
3959 2691620 : unsigned HOST_WIDE_INT stmt_end
3960 2691620 : = ROUND_UP (info->bitpos + info->bitsize, BITS_PER_UNIT);
3961 2691620 : info = find_constituent_stores (group, NULL, &first, try_bitpos,
3962 : stmt_end - try_bitpos);
3963 2691620 : if (info && info->bitpos >= try_bitpos)
3964 : {
3965 2496489 : store_immediate_info *info2 = NULL;
3966 2496489 : unsigned int first_copy = first;
3967 2496489 : if (info->bitpos > try_bitpos
3968 6213 : && stmt_end - try_bitpos <= try_size)
3969 : {
3970 5960 : info2 = find_constituent_stores (group, NULL, &first_copy,
3971 : try_bitpos,
3972 : info->bitpos - try_bitpos);
3973 5960 : gcc_assert (info2 == NULL || gimple_clobber_p (info2->stmt));
3974 : }
3975 2496075 : if (info2 == NULL && stmt_end - try_bitpos < try_size)
3976 : {
3977 424178 : info2 = find_constituent_stores (group, NULL, &first_copy,
3978 : stmt_end,
3979 212089 : (try_bitpos + try_size)
3980 : - stmt_end);
3981 212089 : gcc_assert (info2 == NULL || gimple_clobber_p (info2->stmt));
3982 : }
3983 : if (info2 == NULL)
3984 : {
3985 2476224 : try_size = stmt_end - try_bitpos;
3986 2476224 : found_orig = true;
3987 2476224 : goto found;
3988 : }
3989 : }
3990 : }
3991 :
3992 : /* Approximate store bitsize for the case when there are no padding
3993 : bits. */
3994 1313071 : while (try_size > size)
3995 82244 : try_size /= 2;
3996 : /* Now look for whole padding bytes at the end of that bitsize. */
3997 2315576 : for (nonmasked = try_size / BITS_PER_UNIT; nonmasked > 0; --nonmasked)
3998 2145937 : if (group->mask[try_pos - bytepos + nonmasked - 1]
3999 : != (unsigned char) ~0U
4000 2101802 : && (!bzero_first
4001 1048748 : || group->val[try_pos - bytepos + nonmasked - 1] != 0))
4002 : break;
4003 1230827 : if (nonmasked == 0 || (info && gimple_clobber_p (info->stmt)))
4004 : {
4005 : /* If entire try_size range is padding, skip it. */
4006 669700 : try_pos += try_size / BITS_PER_UNIT;
4007 669700 : size -= try_size;
4008 669700 : continue;
4009 : }
4010 : /* Otherwise try to decrease try_size if second half, last 3 quarters
4011 : etc. are padding. */
4012 561127 : nonmasked *= BITS_PER_UNIT;
4013 570982 : while (nonmasked <= try_size / 2)
4014 : try_size /= 2;
4015 561127 : if (!allow_unaligned_store && group_align > BITS_PER_UNIT)
4016 : {
4017 : /* Now look for whole padding bytes at the start of that bitsize. */
4018 316897 : unsigned int try_bytesize = try_size / BITS_PER_UNIT, masked;
4019 326503 : for (masked = 0; masked < try_bytesize; ++masked)
4020 326503 : if (group->mask[try_pos - bytepos + masked] != (unsigned char) ~0U
4021 324455 : && (!bzero_first
4022 11707 : || group->val[try_pos - bytepos + masked] != 0))
4023 : break;
4024 316897 : masked *= BITS_PER_UNIT;
4025 316897 : gcc_assert (masked < try_size);
4026 316897 : if (masked >= try_size / 2)
4027 : {
4028 5372 : while (masked >= try_size / 2)
4029 : {
4030 2782 : try_size /= 2;
4031 2782 : try_pos += try_size / BITS_PER_UNIT;
4032 2782 : size -= try_size;
4033 2782 : masked -= try_size;
4034 : }
4035 : /* Need to recompute the alignment, so just retry at the new
4036 : position. */
4037 2590 : continue;
4038 : }
4039 : }
4040 :
4041 244230 : found:
4042 3034761 : ++ret;
4043 :
4044 3034761 : if (split_stores)
4045 : {
4046 944777 : split_store *store
4047 944777 : = new split_store (try_pos, try_size, align);
4048 944777 : info = find_constituent_stores (group, &store->orig_stores,
4049 : &first, try_bitpos, try_size);
4050 944777 : if (info
4051 841464 : && !gimple_clobber_p (info->stmt)
4052 841458 : && info->bitpos >= try_bitpos
4053 832676 : && info->bitpos + info->bitsize <= try_bitpos + try_size
4054 1775671 : && (store->orig_stores.length () == 1
4055 32464 : || found_orig
4056 6660 : || (info->bitpos == try_bitpos
4057 6562 : && (info->bitpos + info->bitsize
4058 : == try_bitpos + try_size))))
4059 : {
4060 824234 : store->orig = true;
4061 824234 : any_orig = true;
4062 : }
4063 944777 : split_stores->safe_push (store);
4064 : }
4065 :
4066 3034761 : try_pos += try_size / BITS_PER_UNIT;
4067 3034761 : size -= try_size;
4068 : }
4069 :
4070 1045497 : if (total_orig)
4071 : {
4072 341623 : unsigned int i;
4073 341623 : split_store *store;
4074 : /* If we are reusing some original stores and any of the
4075 : original SSA_NAMEs had multiple uses, we need to subtract
4076 : those now before we add the new ones. */
4077 341623 : if (total_new[0] && any_orig)
4078 : {
4079 156646 : FOR_EACH_VEC_ELT (*split_stores, i, store)
4080 108591 : if (store->orig)
4081 107301 : total_new[0] -= count_multiple_uses (store->orig_stores[0]);
4082 : }
4083 341623 : total_new[0] += ret; /* The new store. */
4084 341623 : store_immediate_info *info = group->stores[0];
4085 341623 : if (info->ops[0].base_addr)
4086 78964 : total_new[0] += ret;
4087 341623 : if (info->ops[1].base_addr)
4088 1156 : total_new[0] += ret;
4089 341623 : switch (info->rhs_code)
4090 : {
4091 1255 : case BIT_AND_EXPR:
4092 1255 : case BIT_IOR_EXPR:
4093 1255 : case BIT_XOR_EXPR:
4094 1255 : total_new[0] += ret; /* The new BIT_*_EXPR stmt. */
4095 1255 : break;
4096 : default:
4097 : break;
4098 : }
4099 1288328 : FOR_EACH_VEC_ELT (*split_stores, i, store)
4100 : {
4101 946705 : unsigned int j;
4102 946705 : bool bit_not_p[3] = { false, false, false };
4103 : /* If all orig_stores have certain bit_not_p set, then
4104 : we'd use a BIT_NOT_EXPR stmt and need to account for it.
4105 : If some orig_stores have certain bit_not_p set, then
4106 : we'd use a BIT_XOR_EXPR with a mask and need to account for
4107 : it. */
4108 2069964 : FOR_EACH_VEC_ELT (store->orig_stores, j, info)
4109 : {
4110 1123259 : if (info->ops[0].bit_not_p)
4111 419 : bit_not_p[0] = true;
4112 1123259 : if (info->ops[1].bit_not_p)
4113 17 : bit_not_p[1] = true;
4114 1123259 : if (info->bit_not_p)
4115 65 : bit_not_p[2] = true;
4116 : }
4117 946705 : total_new[0] += bit_not_p[0] + bit_not_p[1] + bit_not_p[2];
4118 : }
4119 :
4120 : }
4121 :
4122 : return ret;
4123 : }
4124 :
4125 : /* Return the operation through which the operand IDX (if < 2) or
4126 : result (IDX == 2) should be inverted. If NOP_EXPR, no inversion
4127 : is done, if BIT_NOT_EXPR, all bits are inverted, if BIT_XOR_EXPR,
4128 : the bits should be xored with mask. */
4129 :
4130 : static enum tree_code
4131 3992 : invert_op (split_store *split_store, int idx, tree int_type, tree &mask)
4132 : {
4133 3992 : unsigned int i;
4134 3992 : store_immediate_info *info;
4135 3992 : unsigned int cnt = 0;
4136 3992 : bool any_paddings = false;
4137 15308 : FOR_EACH_VEC_ELT (split_store->orig_stores, i, info)
4138 : {
4139 11316 : bool bit_not_p = idx < 2 ? info->ops[idx].bit_not_p : info->bit_not_p;
4140 11316 : if (bit_not_p)
4141 : {
4142 65 : ++cnt;
4143 65 : tree lhs = gimple_assign_lhs (info->stmt);
4144 130 : if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4145 130 : && TYPE_PRECISION (TREE_TYPE (lhs)) < info->bitsize)
4146 : any_paddings = true;
4147 : }
4148 : }
4149 3992 : mask = NULL_TREE;
4150 3992 : if (cnt == 0)
4151 : return NOP_EXPR;
4152 42 : if (cnt == split_store->orig_stores.length () && !any_paddings)
4153 : return BIT_NOT_EXPR;
4154 :
4155 14 : unsigned HOST_WIDE_INT try_bitpos = split_store->bytepos * BITS_PER_UNIT;
4156 14 : unsigned buf_size = split_store->size / BITS_PER_UNIT;
4157 14 : unsigned char *buf
4158 14 : = XALLOCAVEC (unsigned char, buf_size);
4159 14 : memset (buf, ~0U, buf_size);
4160 70 : FOR_EACH_VEC_ELT (split_store->orig_stores, i, info)
4161 : {
4162 56 : bool bit_not_p = idx < 2 ? info->ops[idx].bit_not_p : info->bit_not_p;
4163 56 : if (!bit_not_p)
4164 27 : continue;
4165 : /* Clear regions with bit_not_p and invert afterwards, rather than
4166 : clear regions with !bit_not_p, so that gaps in between stores aren't
4167 : set in the mask. */
4168 29 : unsigned HOST_WIDE_INT bitsize = info->bitsize;
4169 29 : unsigned HOST_WIDE_INT prec = bitsize;
4170 29 : unsigned int pos_in_buffer = 0;
4171 29 : if (any_paddings)
4172 : {
4173 12 : tree lhs = gimple_assign_lhs (info->stmt);
4174 24 : if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4175 24 : && TYPE_PRECISION (TREE_TYPE (lhs)) < bitsize)
4176 12 : prec = TYPE_PRECISION (TREE_TYPE (lhs));
4177 : }
4178 29 : if (info->bitpos < try_bitpos)
4179 : {
4180 0 : gcc_assert (info->bitpos + bitsize > try_bitpos);
4181 0 : if (!BYTES_BIG_ENDIAN)
4182 : {
4183 0 : if (prec <= try_bitpos - info->bitpos)
4184 0 : continue;
4185 0 : prec -= try_bitpos - info->bitpos;
4186 : }
4187 0 : bitsize -= try_bitpos - info->bitpos;
4188 0 : if (BYTES_BIG_ENDIAN && prec > bitsize)
4189 : prec = bitsize;
4190 : }
4191 : else
4192 29 : pos_in_buffer = info->bitpos - try_bitpos;
4193 29 : if (prec < bitsize)
4194 : {
4195 : /* If this is a bool inversion, invert just the least significant
4196 : prec bits rather than all bits of it. */
4197 : if (BYTES_BIG_ENDIAN)
4198 : {
4199 : pos_in_buffer += bitsize - prec;
4200 : if (pos_in_buffer >= split_store->size)
4201 : continue;
4202 : }
4203 : bitsize = prec;
4204 : }
4205 29 : if (pos_in_buffer + bitsize > split_store->size)
4206 0 : bitsize = split_store->size - pos_in_buffer;
4207 29 : unsigned char *p = buf + (pos_in_buffer / BITS_PER_UNIT);
4208 29 : if (BYTES_BIG_ENDIAN)
4209 : clear_bit_region_be (p, (BITS_PER_UNIT - 1
4210 : - (pos_in_buffer % BITS_PER_UNIT)), bitsize);
4211 : else
4212 29 : clear_bit_region (p, pos_in_buffer % BITS_PER_UNIT, bitsize);
4213 : }
4214 74 : for (unsigned int i = 0; i < buf_size; ++i)
4215 60 : buf[i] = ~buf[i];
4216 14 : mask = native_interpret_expr (int_type, buf, buf_size);
4217 14 : return BIT_XOR_EXPR;
4218 : }
4219 :
4220 : /* Given a merged store group GROUP output the widened version of it.
4221 : The store chain is against the base object BASE.
4222 : Try store sizes of at most MAX_STORE_BITSIZE bits wide and don't output
4223 : unaligned stores for STRICT_ALIGNMENT targets or if it's too expensive.
4224 : Make sure that the number of statements output is less than the number of
4225 : original statements. If a better sequence is possible emit it and
4226 : return true. */
4227 :
4228 : bool
4229 422388 : imm_store_chain_info::output_merged_store (merged_store_group *group)
4230 : {
4231 422388 : const unsigned HOST_WIDE_INT start_byte_pos
4232 422388 : = group->bitregion_start / BITS_PER_UNIT;
4233 422388 : unsigned int orig_num_stmts = group->stores.length ();
4234 422388 : if (orig_num_stmts < 2)
4235 : return false;
4236 :
4237 422388 : bool allow_unaligned_store
4238 422388 : = !STRICT_ALIGNMENT && param_store_merging_allow_unaligned;
4239 422388 : bool allow_unaligned_load = allow_unaligned_store;
4240 422388 : bool bzero_first = false;
4241 422388 : store_immediate_info *store;
4242 422388 : unsigned int num_clobber_stmts = 0;
4243 422388 : if (group->stores[0]->rhs_code == INTEGER_CST)
4244 : {
4245 : unsigned int i;
4246 519205 : FOR_EACH_VEC_ELT (group->stores, i, store)
4247 439362 : if (gimple_clobber_p (store->stmt))
4248 : num_clobber_stmts++;
4249 259924 : else if (TREE_CODE (gimple_assign_rhs1 (store->stmt)) == CONSTRUCTOR
4250 15257 : && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (store->stmt)) == 0
4251 15257 : && group->start == store->bitpos
4252 14710 : && group->width == store->bitsize
4253 10314 : && (group->start % BITS_PER_UNIT) == 0
4254 270238 : && (group->width % BITS_PER_UNIT) == 0)
4255 : {
4256 : bzero_first = true;
4257 : break;
4258 : }
4259 : else
4260 : break;
4261 1208743 : FOR_EACH_VEC_ELT_FROM (group->stores, i, store, i)
4262 868976 : if (gimple_clobber_p (store->stmt))
4263 1947 : num_clobber_stmts++;
4264 339767 : if (num_clobber_stmts == orig_num_stmts)
4265 : return false;
4266 259924 : orig_num_stmts -= num_clobber_stmts;
4267 : }
4268 342545 : if (allow_unaligned_store || bzero_first)
4269 : {
4270 : /* If unaligned stores are allowed, see how many stores we'd emit
4271 : for unaligned and how many stores we'd emit for aligned stores.
4272 : Only use unaligned stores if it allows fewer stores than aligned.
4273 : Similarly, if there is a whole region clear first, prefer expanding
4274 : it together compared to expanding clear first followed by merged
4275 : further stores. */
4276 342545 : unsigned cnt[4] = { ~0U, ~0U, ~0U, ~0U };
4277 342545 : int pass_min = 0;
4278 1712725 : for (int pass = 0; pass < 4; ++pass)
4279 : {
4280 1370180 : if (!allow_unaligned_store && (pass & 1) != 0)
4281 0 : continue;
4282 1370180 : if (!bzero_first && (pass & 2) != 0)
4283 664462 : continue;
4284 1411436 : cnt[pass] = split_group (group, (pass & 1) != 0,
4285 705718 : allow_unaligned_load, (pass & 2) != 0,
4286 : NULL, NULL, NULL);
4287 705718 : if (cnt[pass] < cnt[pass_min])
4288 1370180 : pass_min = pass;
4289 : }
4290 342545 : if ((pass_min & 1) == 0)
4291 334089 : allow_unaligned_store = false;
4292 342545 : if ((pass_min & 2) == 0)
4293 340617 : bzero_first = false;
4294 : }
4295 :
4296 342545 : auto_vec<class split_store *, 32> split_stores;
4297 342545 : split_store *split_store;
4298 342545 : unsigned total_orig, total_new, i;
4299 342545 : split_group (group, allow_unaligned_store, allow_unaligned_load, bzero_first,
4300 : &split_stores, &total_orig, &total_new);
4301 :
4302 : /* Determine if there is a clobber covering the whole group at the start,
4303 : followed by proposed split stores that cover the whole group. In that
4304 : case, prefer the transformation even if
4305 : split_stores.length () == orig_num_stmts. */
4306 342545 : bool clobber_first = false;
4307 342545 : if (num_clobber_stmts
4308 19919 : && gimple_clobber_p (group->stores[0]->stmt)
4309 19444 : && group->start == group->stores[0]->bitpos
4310 19444 : && group->width == group->stores[0]->bitsize
4311 19221 : && (group->start % BITS_PER_UNIT) == 0
4312 361766 : && (group->width % BITS_PER_UNIT) == 0)
4313 : {
4314 19221 : clobber_first = true;
4315 19221 : unsigned HOST_WIDE_INT pos = group->start / BITS_PER_UNIT;
4316 47990 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4317 34306 : if (split_store->bytepos != pos)
4318 : {
4319 : clobber_first = false;
4320 : break;
4321 : }
4322 : else
4323 28769 : pos += split_store->size / BITS_PER_UNIT;
4324 19221 : if (pos != (group->start + group->width) / BITS_PER_UNIT)
4325 337282 : clobber_first = false;
4326 : }
4327 :
4328 685090 : if (split_stores.length () >= orig_num_stmts + clobber_first)
4329 : {
4330 :
4331 : /* We didn't manage to reduce the number of statements. Bail out. */
4332 250744 : if (dump_file && (dump_flags & TDF_DETAILS))
4333 2 : fprintf (dump_file, "Exceeded original number of stmts (%u)."
4334 : " Not profitable to emit new sequence.\n",
4335 : orig_num_stmts);
4336 877564 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4337 1253640 : delete split_store;
4338 : return false;
4339 : }
4340 91801 : if (total_orig <= total_new)
4341 : {
4342 : /* If number of estimated new statements is above estimated original
4343 : statements, bail out too. */
4344 1644 : if (dump_file && (dump_flags & TDF_DETAILS))
4345 0 : fprintf (dump_file, "Estimated number of original stmts (%u)"
4346 : " not larger than estimated number of new"
4347 : " stmts (%u).\n",
4348 : total_orig, total_new);
4349 3586 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4350 3884 : delete split_store;
4351 : return false;
4352 : }
4353 90157 : if (group->stores[0]->rhs_code == INTEGER_CST)
4354 : {
4355 174687 : bool all_orig = true;
4356 174687 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4357 170705 : if (!split_store->orig)
4358 : {
4359 : all_orig = false;
4360 : break;
4361 : }
4362 84558 : if (all_orig)
4363 : {
4364 : unsigned int cnt = split_stores.length ();
4365 : store_immediate_info *store;
4366 16415 : FOR_EACH_VEC_ELT (group->stores, i, store)
4367 12433 : if (gimple_clobber_p (store->stmt))
4368 3988 : ++cnt;
4369 : /* Punt if we wouldn't make any real changes, i.e. keep all
4370 : orig stmts + all clobbers. */
4371 3982 : if (cnt == group->stores.length ())
4372 : {
4373 3959 : if (dump_file && (dump_flags & TDF_DETAILS))
4374 0 : fprintf (dump_file, "Exceeded original number of stmts (%u)."
4375 : " Not profitable to emit new sequence.\n",
4376 : orig_num_stmts);
4377 12336 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4378 16754 : delete split_store;
4379 342545 : return false;
4380 : }
4381 : }
4382 : }
4383 :
4384 86198 : gimple_stmt_iterator last_gsi = gsi_for_stmt (group->last_stmt);
4385 86198 : gimple_seq seq = NULL;
4386 86198 : tree last_vdef, new_vuse;
4387 86198 : last_vdef = gimple_vdef (group->last_stmt);
4388 86198 : new_vuse = gimple_vuse (group->last_stmt);
4389 86198 : tree bswap_res = NULL_TREE;
4390 :
4391 : /* Clobbers are not removed. */
4392 86198 : if (gimple_clobber_p (group->last_stmt))
4393 : {
4394 6 : new_vuse = make_ssa_name (gimple_vop (cfun), group->last_stmt);
4395 6 : gimple_set_vdef (group->last_stmt, new_vuse);
4396 : }
4397 :
4398 86198 : if (group->stores[0]->rhs_code == LROTATE_EXPR
4399 86198 : || group->stores[0]->rhs_code == NOP_EXPR)
4400 : {
4401 886 : tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
4402 886 : gimple *ins_stmt = group->stores[0]->ins_stmt;
4403 886 : struct symbolic_number *n = &group->stores[0]->n;
4404 886 : bool bswap = group->stores[0]->rhs_code == LROTATE_EXPR;
4405 :
4406 886 : switch (n->range)
4407 : {
4408 470 : case 16:
4409 470 : load_type = bswap_type = uint16_type_node;
4410 470 : break;
4411 219 : case 32:
4412 219 : load_type = uint32_type_node;
4413 219 : if (bswap)
4414 : {
4415 109 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
4416 109 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
4417 : }
4418 : break;
4419 197 : case 64:
4420 197 : load_type = uint64_type_node;
4421 197 : if (bswap)
4422 : {
4423 71 : fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64);
4424 71 : bswap_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
4425 : }
4426 : break;
4427 0 : default:
4428 0 : gcc_unreachable ();
4429 : }
4430 :
4431 : /* If the loads have each vuse of the corresponding store,
4432 : we've checked the aliasing already in try_coalesce_bswap and
4433 : we want to sink the need load into seq. So need to use new_vuse
4434 : on the load. */
4435 886 : if (n->base_addr)
4436 : {
4437 443 : if (n->vuse == NULL)
4438 : {
4439 73 : n->vuse = new_vuse;
4440 73 : ins_stmt = NULL;
4441 : }
4442 : else
4443 : /* Update vuse in case it has changed by output_merged_stores. */
4444 740 : n->vuse = gimple_vuse (ins_stmt);
4445 : }
4446 886 : bswap_res = bswap_replace (gsi_start (seq), ins_stmt, fndecl,
4447 : bswap_type, load_type, n, bswap,
4448 : ~(uint64_t) 0, 0);
4449 886 : gcc_assert (bswap_res);
4450 : }
4451 :
4452 86198 : gimple *stmt = NULL;
4453 172396 : auto_vec<gimple *, 32> orig_stmts;
4454 86198 : gimple_seq this_seq;
4455 86198 : tree addr = force_gimple_operand_1 (unshare_expr (base_addr), &this_seq,
4456 : is_gimple_mem_ref_addr, NULL_TREE);
4457 86198 : gimple_seq_add_seq_without_update (&seq, this_seq);
4458 :
4459 86198 : tree load_addr[2] = { NULL_TREE, NULL_TREE };
4460 86198 : gimple_seq load_seq[2] = { NULL, NULL };
4461 86198 : gimple_stmt_iterator load_gsi[2] = { gsi_none (), gsi_none () };
4462 258594 : for (int j = 0; j < 2; ++j)
4463 : {
4464 172396 : store_operand_info &op = group->stores[0]->ops[j];
4465 172396 : if (op.base_addr == NULL_TREE)
4466 169772 : continue;
4467 :
4468 2624 : store_immediate_info *infol = group->stores.last ();
4469 7872 : if (gimple_vuse (op.stmt) == gimple_vuse (infol->ops[j].stmt))
4470 : {
4471 : /* We can't pick the location randomly; while we've verified
4472 : all the loads have the same vuse, they can be still in different
4473 : basic blocks and we need to pick the one from the last bb:
4474 : int x = q[0];
4475 : if (x == N) return;
4476 : int y = q[1];
4477 : p[0] = x;
4478 : p[1] = y;
4479 : otherwise if we put the wider load at the q[0] load, we might
4480 : segfault if q[1] is not mapped. */
4481 1543 : basic_block bb = gimple_bb (op.stmt);
4482 1543 : gimple *ostmt = op.stmt;
4483 1543 : store_immediate_info *info;
4484 11708 : FOR_EACH_VEC_ELT (group->stores, i, info)
4485 : {
4486 10165 : gimple *tstmt = info->ops[j].stmt;
4487 10165 : basic_block tbb = gimple_bb (tstmt);
4488 10165 : if (dominated_by_p (CDI_DOMINATORS, tbb, bb))
4489 : {
4490 10144 : ostmt = tstmt;
4491 10144 : bb = tbb;
4492 : }
4493 : }
4494 1543 : load_gsi[j] = gsi_for_stmt (ostmt);
4495 1543 : load_addr[j]
4496 1543 : = force_gimple_operand_1 (unshare_expr (op.base_addr),
4497 : &load_seq[j], is_gimple_mem_ref_addr,
4498 : NULL_TREE);
4499 : }
4500 1081 : else if (operand_equal_p (base_addr, op.base_addr, 0))
4501 38 : load_addr[j] = addr;
4502 : else
4503 : {
4504 1043 : load_addr[j]
4505 1043 : = force_gimple_operand_1 (unshare_expr (op.base_addr),
4506 : &this_seq, is_gimple_mem_ref_addr,
4507 : NULL_TREE);
4508 1043 : gimple_seq_add_seq_without_update (&seq, this_seq);
4509 : }
4510 : }
4511 :
4512 396686 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4513 : {
4514 310488 : const unsigned HOST_WIDE_INT try_size = split_store->size;
4515 310488 : const unsigned HOST_WIDE_INT try_pos = split_store->bytepos;
4516 310488 : const unsigned HOST_WIDE_INT try_bitpos = try_pos * BITS_PER_UNIT;
4517 310488 : const unsigned HOST_WIDE_INT try_align = split_store->align;
4518 310488 : const unsigned HOST_WIDE_INT try_offset = try_pos - start_byte_pos;
4519 310488 : tree dest, src;
4520 310488 : location_t loc;
4521 :
4522 310488 : if (split_store->orig)
4523 : {
4524 : /* If there is just a single non-clobber constituent store
4525 : which covers the whole area, just reuse the lhs and rhs. */
4526 219682 : gimple *orig_stmt = NULL;
4527 : store_immediate_info *store;
4528 : unsigned int j;
4529 219682 : FOR_EACH_VEC_ELT (split_store->orig_stores, j, store)
4530 219682 : if (!gimple_clobber_p (store->stmt))
4531 : {
4532 : orig_stmt = store->stmt;
4533 : break;
4534 : }
4535 213631 : dest = gimple_assign_lhs (orig_stmt);
4536 213631 : src = gimple_assign_rhs1 (orig_stmt);
4537 213631 : loc = gimple_location (orig_stmt);
4538 : }
4539 : else
4540 : {
4541 : store_immediate_info *info;
4542 : unsigned short clique, base;
4543 : unsigned int k;
4544 330635 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4545 233778 : orig_stmts.safe_push (info->stmt);
4546 96857 : tree offset_type
4547 96857 : = get_alias_type_for_stmts (orig_stmts, false, &clique, &base);
4548 96857 : tree dest_type;
4549 96857 : loc = get_location_for_stmts (orig_stmts);
4550 96857 : orig_stmts.truncate (0);
4551 :
4552 96857 : if (group->string_concatenation)
4553 36 : dest_type
4554 36 : = build_array_type_nelts (char_type_node,
4555 36 : try_size / BITS_PER_UNIT);
4556 : else
4557 : {
4558 96821 : dest_type = build_nonstandard_integer_type (try_size, UNSIGNED);
4559 96821 : dest_type = build_aligned_type (dest_type, try_align);
4560 : }
4561 96857 : dest = fold_build2 (MEM_REF, dest_type, addr,
4562 : build_int_cst (offset_type, try_pos));
4563 96857 : if (TREE_CODE (dest) == MEM_REF)
4564 : {
4565 96857 : MR_DEPENDENCE_CLIQUE (dest) = clique;
4566 96857 : MR_DEPENDENCE_BASE (dest) = base;
4567 : }
4568 :
4569 96857 : tree mask;
4570 96857 : if (bswap_res || group->string_concatenation)
4571 922 : mask = integer_zero_node;
4572 : else
4573 95935 : mask = native_interpret_expr (dest_type,
4574 95935 : group->mask + try_offset,
4575 95935 : group->buf_size);
4576 :
4577 96857 : tree ops[2];
4578 193751 : for (int j = 0;
4579 387391 : j < 1 + (split_store->orig_stores[0]->ops[1].val != NULL_TREE);
4580 : ++j)
4581 : {
4582 96894 : store_operand_info &op = split_store->orig_stores[0]->ops[j];
4583 96894 : if (bswap_res)
4584 886 : ops[j] = bswap_res;
4585 96008 : else if (group->string_concatenation)
4586 : {
4587 72 : ops[j] = build_string (try_size / BITS_PER_UNIT,
4588 36 : (const char *) group->val + try_offset);
4589 36 : TREE_TYPE (ops[j]) = dest_type;
4590 : }
4591 95972 : else if (op.base_addr)
4592 : {
4593 11101 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4594 8032 : orig_stmts.safe_push (info->ops[j].stmt);
4595 :
4596 3069 : offset_type = get_alias_type_for_stmts (orig_stmts, true,
4597 : &clique, &base);
4598 3069 : location_t load_loc = get_location_for_stmts (orig_stmts);
4599 3069 : orig_stmts.truncate (0);
4600 :
4601 3069 : unsigned HOST_WIDE_INT load_align = group->load_align[j];
4602 3069 : unsigned HOST_WIDE_INT align_bitpos
4603 3069 : = known_alignment (try_bitpos
4604 3069 : - split_store->orig_stores[0]->bitpos
4605 3069 : + op.bitpos);
4606 3069 : if (align_bitpos & (load_align - 1))
4607 747 : load_align = least_bit_hwi (align_bitpos);
4608 :
4609 3069 : tree load_int_type
4610 3069 : = build_nonstandard_integer_type (try_size, UNSIGNED);
4611 3069 : load_int_type
4612 3069 : = build_aligned_type (load_int_type, load_align);
4613 :
4614 3069 : poly_uint64 load_pos
4615 3069 : = exact_div (try_bitpos
4616 3069 : - split_store->orig_stores[0]->bitpos
4617 3069 : + op.bitpos,
4618 : BITS_PER_UNIT);
4619 3069 : ops[j] = fold_build2 (MEM_REF, load_int_type, load_addr[j],
4620 : build_int_cst (offset_type, load_pos));
4621 3069 : if (TREE_CODE (ops[j]) == MEM_REF)
4622 : {
4623 3069 : MR_DEPENDENCE_CLIQUE (ops[j]) = clique;
4624 3069 : MR_DEPENDENCE_BASE (ops[j]) = base;
4625 : }
4626 3069 : if (!integer_zerop (mask))
4627 : {
4628 : /* The load might load some bits (that will be masked
4629 : off later on) uninitialized, avoid -W*uninitialized
4630 : warnings in that case. */
4631 118 : suppress_warning (ops[j], OPT_Wuninitialized);
4632 : }
4633 :
4634 3069 : stmt = gimple_build_assign (make_ssa_name (dest_type), ops[j]);
4635 3069 : gimple_set_location (stmt, load_loc);
4636 3069 : if (gsi_bb (load_gsi[j]))
4637 : {
4638 3726 : gimple_set_vuse (stmt, gimple_vuse (op.stmt));
4639 1863 : gimple_seq_add_stmt_without_update (&load_seq[j], stmt);
4640 : }
4641 : else
4642 : {
4643 1206 : gimple_set_vuse (stmt, new_vuse);
4644 1206 : gimple_seq_add_stmt_without_update (&seq, stmt);
4645 : }
4646 3069 : ops[j] = gimple_assign_lhs (stmt);
4647 3069 : tree xor_mask;
4648 3069 : enum tree_code inv_op
4649 3069 : = invert_op (split_store, j, dest_type, xor_mask);
4650 3069 : if (inv_op != NOP_EXPR)
4651 : {
4652 17 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4653 : inv_op, ops[j], xor_mask);
4654 17 : gimple_set_location (stmt, load_loc);
4655 17 : ops[j] = gimple_assign_lhs (stmt);
4656 :
4657 17 : if (gsi_bb (load_gsi[j]))
4658 7 : gimple_seq_add_stmt_without_update (&load_seq[j],
4659 : stmt);
4660 : else
4661 10 : gimple_seq_add_stmt_without_update (&seq, stmt);
4662 : }
4663 : }
4664 : else
4665 92903 : ops[j] = native_interpret_expr (dest_type,
4666 92903 : group->val + try_offset,
4667 92903 : group->buf_size);
4668 : }
4669 :
4670 96857 : switch (split_store->orig_stores[0]->rhs_code)
4671 : {
4672 : case BIT_AND_EXPR:
4673 : case BIT_IOR_EXPR:
4674 : case BIT_XOR_EXPR:
4675 185 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4676 : {
4677 148 : tree rhs1 = gimple_assign_rhs1 (info->stmt);
4678 148 : orig_stmts.safe_push (SSA_NAME_DEF_STMT (rhs1));
4679 : }
4680 37 : location_t bit_loc;
4681 37 : bit_loc = get_location_for_stmts (orig_stmts);
4682 37 : orig_stmts.truncate (0);
4683 :
4684 37 : stmt
4685 37 : = gimple_build_assign (make_ssa_name (dest_type),
4686 37 : split_store->orig_stores[0]->rhs_code,
4687 : ops[0], ops[1]);
4688 37 : gimple_set_location (stmt, bit_loc);
4689 : /* If there is just one load and there is a separate
4690 : load_seq[0], emit the bitwise op right after it. */
4691 37 : if (load_addr[1] == NULL_TREE && gsi_bb (load_gsi[0]))
4692 0 : gimple_seq_add_stmt_without_update (&load_seq[0], stmt);
4693 : /* Otherwise, if at least one load is in seq, we need to
4694 : emit the bitwise op right before the store. If there
4695 : are two loads and are emitted somewhere else, it would
4696 : be better to emit the bitwise op as early as possible;
4697 : we don't track where that would be possible right now
4698 : though. */
4699 : else
4700 37 : gimple_seq_add_stmt_without_update (&seq, stmt);
4701 37 : src = gimple_assign_lhs (stmt);
4702 37 : tree xor_mask;
4703 37 : enum tree_code inv_op;
4704 37 : inv_op = invert_op (split_store, 2, dest_type, xor_mask);
4705 37 : if (inv_op != NOP_EXPR)
4706 : {
4707 2 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4708 : inv_op, src, xor_mask);
4709 2 : gimple_set_location (stmt, bit_loc);
4710 2 : if (load_addr[1] == NULL_TREE && gsi_bb (load_gsi[0]))
4711 0 : gimple_seq_add_stmt_without_update (&load_seq[0], stmt);
4712 : else
4713 2 : gimple_seq_add_stmt_without_update (&seq, stmt);
4714 2 : src = gimple_assign_lhs (stmt);
4715 : }
4716 : break;
4717 886 : case LROTATE_EXPR:
4718 886 : case NOP_EXPR:
4719 886 : src = ops[0];
4720 886 : if (!is_gimple_val (src))
4721 : {
4722 0 : stmt = gimple_build_assign (make_ssa_name (TREE_TYPE (src)),
4723 : src);
4724 0 : gimple_seq_add_stmt_without_update (&seq, stmt);
4725 0 : src = gimple_assign_lhs (stmt);
4726 : }
4727 886 : if (!useless_type_conversion_p (dest_type, TREE_TYPE (src)))
4728 : {
4729 90 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4730 : NOP_EXPR, src);
4731 90 : gimple_seq_add_stmt_without_update (&seq, stmt);
4732 90 : src = gimple_assign_lhs (stmt);
4733 : }
4734 886 : inv_op = invert_op (split_store, 2, dest_type, xor_mask);
4735 886 : if (inv_op != NOP_EXPR)
4736 : {
4737 2 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4738 : inv_op, src, xor_mask);
4739 2 : gimple_set_location (stmt, loc);
4740 2 : gimple_seq_add_stmt_without_update (&seq, stmt);
4741 2 : src = gimple_assign_lhs (stmt);
4742 : }
4743 : break;
4744 95934 : default:
4745 95934 : src = ops[0];
4746 95934 : break;
4747 : }
4748 :
4749 : /* If bit insertion is required, we use the source as an accumulator
4750 : into which the successive bit-field values are manually inserted.
4751 : FIXME: perhaps use BIT_INSERT_EXPR instead in some cases? */
4752 96857 : if (group->bit_insertion)
4753 18908 : FOR_EACH_VEC_ELT (split_store->orig_stores, k, info)
4754 15028 : if (info->rhs_code == BIT_INSERT_EXPR
4755 7664 : && info->bitpos < try_bitpos + try_size
4756 7664 : && info->bitpos + info->bitsize > try_bitpos)
4757 : {
4758 : /* Mask, truncate, convert to final type, shift and ior into
4759 : the accumulator. Note that every step can be a no-op. */
4760 7664 : const HOST_WIDE_INT start_gap = info->bitpos - try_bitpos;
4761 7664 : const HOST_WIDE_INT end_gap
4762 7664 : = (try_bitpos + try_size) - (info->bitpos + info->bitsize);
4763 7664 : tree tem = info->ops[0].val;
4764 7664 : if (!INTEGRAL_TYPE_P (TREE_TYPE (tem)))
4765 : {
4766 0 : const unsigned HOST_WIDE_INT size
4767 0 : = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (tem)));
4768 0 : tree integer_type
4769 0 : = build_nonstandard_integer_type (size, UNSIGNED);
4770 0 : tem = gimple_build (&seq, loc, VIEW_CONVERT_EXPR,
4771 : integer_type, tem);
4772 : }
4773 7664 : if (TYPE_PRECISION (TREE_TYPE (tem)) <= info->bitsize)
4774 : {
4775 4974 : tree bitfield_type
4776 4974 : = build_nonstandard_integer_type (info->bitsize,
4777 : UNSIGNED);
4778 4974 : tem = gimple_convert (&seq, loc, bitfield_type, tem);
4779 : }
4780 2690 : else if ((BYTES_BIG_ENDIAN ? start_gap : end_gap) > 0)
4781 : {
4782 1625 : wide_int imask
4783 : = wi::mask (info->bitsize, false,
4784 1625 : TYPE_PRECISION (TREE_TYPE (tem)));
4785 4875 : tem = gimple_build (&seq, loc,
4786 1625 : BIT_AND_EXPR, TREE_TYPE (tem), tem,
4787 1625 : wide_int_to_tree (TREE_TYPE (tem),
4788 3250 : imask));
4789 1625 : }
4790 7664 : const HOST_WIDE_INT shift
4791 : = (BYTES_BIG_ENDIAN ? end_gap : start_gap);
4792 7664 : if (shift < 0)
4793 4 : tem = gimple_build (&seq, loc,
4794 4 : RSHIFT_EXPR, TREE_TYPE (tem), tem,
4795 4 : build_int_cst (integer_type_node, -shift));
4796 7664 : tem = gimple_convert (&seq, loc, dest_type, tem);
4797 7664 : if (shift > 0)
4798 5668 : tem = gimple_build (&seq, loc,
4799 : LSHIFT_EXPR, dest_type, tem,
4800 5668 : build_int_cst (integer_type_node, shift));
4801 7664 : src = gimple_build (&seq, loc,
4802 : BIT_IOR_EXPR, dest_type, tem, src);
4803 : }
4804 :
4805 96857 : if (!integer_zerop (mask))
4806 : {
4807 2961 : tree tem = make_ssa_name (dest_type);
4808 2961 : tree load_src = unshare_expr (dest);
4809 : /* The load might load some or all bits uninitialized,
4810 : avoid -W*uninitialized warnings in that case.
4811 : As optimization, it would be nice if all the bits are
4812 : provably uninitialized (no stores at all yet or previous
4813 : store a CLOBBER) we'd optimize away the load and replace
4814 : it e.g. with 0. */
4815 2961 : suppress_warning (load_src, OPT_Wuninitialized);
4816 2961 : stmt = gimple_build_assign (tem, load_src);
4817 2961 : gimple_set_location (stmt, loc);
4818 2961 : gimple_set_vuse (stmt, new_vuse);
4819 2961 : gimple_seq_add_stmt_without_update (&seq, stmt);
4820 :
4821 : /* FIXME: If there is a single chunk of zero bits in mask,
4822 : perhaps use BIT_INSERT_EXPR instead? */
4823 2961 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4824 : BIT_AND_EXPR, tem, mask);
4825 2961 : gimple_set_location (stmt, loc);
4826 2961 : gimple_seq_add_stmt_without_update (&seq, stmt);
4827 2961 : tem = gimple_assign_lhs (stmt);
4828 :
4829 2961 : if (TREE_CODE (src) == INTEGER_CST)
4830 1271 : src = wide_int_to_tree (dest_type,
4831 1271 : wi::bit_and_not (wi::to_wide (src),
4832 2542 : wi::to_wide (mask)));
4833 : else
4834 : {
4835 1690 : tree nmask
4836 1690 : = wide_int_to_tree (dest_type,
4837 1690 : wi::bit_not (wi::to_wide (mask)));
4838 1690 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4839 : BIT_AND_EXPR, src, nmask);
4840 1690 : gimple_set_location (stmt, loc);
4841 1690 : gimple_seq_add_stmt_without_update (&seq, stmt);
4842 1690 : src = gimple_assign_lhs (stmt);
4843 : }
4844 2961 : stmt = gimple_build_assign (make_ssa_name (dest_type),
4845 : BIT_IOR_EXPR, tem, src);
4846 2961 : gimple_set_location (stmt, loc);
4847 2961 : gimple_seq_add_stmt_without_update (&seq, stmt);
4848 2961 : src = gimple_assign_lhs (stmt);
4849 : }
4850 : }
4851 :
4852 310488 : stmt = gimple_build_assign (dest, src);
4853 310488 : gimple_set_location (stmt, loc);
4854 310488 : gimple_set_vuse (stmt, new_vuse);
4855 310488 : gimple_seq_add_stmt_without_update (&seq, stmt);
4856 :
4857 310488 : if (group->lp_nr && stmt_could_throw_p (cfun, stmt))
4858 53 : add_stmt_to_eh_lp (stmt, group->lp_nr);
4859 :
4860 310488 : tree new_vdef;
4861 620976 : if (i < split_stores.length () - 1)
4862 224290 : new_vdef = make_ssa_name (gimple_vop (cfun), stmt);
4863 : else
4864 : new_vdef = last_vdef;
4865 :
4866 310488 : gimple_set_vdef (stmt, new_vdef);
4867 310488 : SSA_NAME_DEF_STMT (new_vdef) = stmt;
4868 310488 : new_vuse = new_vdef;
4869 : }
4870 :
4871 396686 : FOR_EACH_VEC_ELT (split_stores, i, split_store)
4872 620976 : delete split_store;
4873 :
4874 86198 : gcc_assert (seq);
4875 86198 : if (dump_file)
4876 : {
4877 184 : fprintf (dump_file,
4878 : "New sequence of %u stores to replace old one of %u stores\n",
4879 : split_stores.length (), orig_num_stmts);
4880 92 : if (dump_flags & TDF_DETAILS)
4881 23 : print_gimple_seq (dump_file, seq, 0, TDF_VOPS | TDF_MEMSYMS);
4882 : }
4883 :
4884 86198 : if (gimple_clobber_p (group->last_stmt))
4885 6 : update_stmt (group->last_stmt);
4886 :
4887 86198 : if (group->lp_nr > 0)
4888 : {
4889 : /* We're going to insert a sequence of (potentially) throwing stores
4890 : into an active EH region. This means that we're going to create
4891 : new basic blocks with EH edges pointing to the post landing pad
4892 : and, therefore, to have to update its PHI nodes, if any. For the
4893 : virtual PHI node, we're going to use the VDEFs created above, but
4894 : for the other nodes, we need to record the original reaching defs. */
4895 46 : eh_landing_pad lp = get_eh_landing_pad_from_number (group->lp_nr);
4896 46 : basic_block lp_bb = label_to_block (cfun, lp->post_landing_pad);
4897 46 : basic_block last_bb = gimple_bb (group->last_stmt);
4898 46 : edge last_edge = find_edge (last_bb, lp_bb);
4899 46 : auto_vec<tree, 16> last_defs;
4900 46 : gphi_iterator gpi;
4901 98 : for (gpi = gsi_start_phis (lp_bb); !gsi_end_p (gpi); gsi_next (&gpi))
4902 : {
4903 52 : gphi *phi = gpi.phi ();
4904 52 : tree last_def;
4905 104 : if (virtual_operand_p (gimple_phi_result (phi)))
4906 46 : last_def = NULL_TREE;
4907 : else
4908 6 : last_def = gimple_phi_arg_def (phi, last_edge->dest_idx);
4909 52 : last_defs.safe_push (last_def);
4910 : }
4911 :
4912 : /* Do the insertion. Then, if new basic blocks have been created in the
4913 : process, rewind the chain of VDEFs create above to walk the new basic
4914 : blocks and update the corresponding arguments of the PHI nodes. */
4915 46 : update_modified_stmts (seq);
4916 46 : if (gimple_find_sub_bbs (seq, &last_gsi))
4917 198 : while (last_vdef != gimple_vuse (group->last_stmt))
4918 : {
4919 53 : gimple *stmt = SSA_NAME_DEF_STMT (last_vdef);
4920 53 : if (stmt_could_throw_p (cfun, stmt))
4921 : {
4922 53 : edge new_edge = find_edge (gimple_bb (stmt), lp_bb);
4923 53 : unsigned int i;
4924 53 : for (gpi = gsi_start_phis (lp_bb), i = 0;
4925 112 : !gsi_end_p (gpi);
4926 59 : gsi_next (&gpi), i++)
4927 : {
4928 59 : gphi *phi = gpi.phi ();
4929 59 : tree new_def;
4930 118 : if (virtual_operand_p (gimple_phi_result (phi)))
4931 : new_def = last_vdef;
4932 : else
4933 6 : new_def = last_defs[i];
4934 59 : add_phi_arg (phi, new_def, new_edge, UNKNOWN_LOCATION);
4935 : }
4936 : }
4937 106 : last_vdef = gimple_vuse (stmt);
4938 : }
4939 46 : }
4940 : else
4941 86152 : gsi_insert_seq_after (&last_gsi, seq, GSI_SAME_STMT);
4942 :
4943 258594 : for (int j = 0; j < 2; ++j)
4944 172396 : if (load_seq[j])
4945 1543 : gsi_insert_seq_after (&load_gsi[j], load_seq[j], GSI_SAME_STMT);
4946 :
4947 86198 : return true;
4948 342545 : }
4949 :
4950 : /* Process the merged_store_group objects created in the coalescing phase.
4951 : The stores are all against the base object BASE.
4952 : Try to output the widened stores and delete the original statements if
4953 : successful. Return true iff any changes were made. */
4954 :
4955 : bool
4956 388362 : imm_store_chain_info::output_merged_stores ()
4957 : {
4958 388362 : unsigned int i;
4959 388362 : merged_store_group *merged_store;
4960 388362 : bool ret = false;
4961 810750 : FOR_EACH_VEC_ELT (m_merged_store_groups, i, merged_store)
4962 : {
4963 422388 : if (dbg_cnt (store_merging)
4964 422388 : && output_merged_store (merged_store))
4965 : {
4966 : unsigned int j;
4967 : store_immediate_info *store;
4968 949520 : FOR_EACH_VEC_ELT (merged_store->stores, j, store)
4969 : {
4970 440934 : gimple *stmt = store->stmt;
4971 440934 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
4972 : /* Don't remove clobbers, they are still useful even if
4973 : everything is overwritten afterwards. */
4974 440934 : if (gimple_clobber_p (stmt))
4975 2895 : continue;
4976 438039 : gsi_remove (&gsi, true);
4977 438039 : if (store->lp_nr)
4978 165 : remove_stmt_from_eh_lp (stmt);
4979 438039 : if (stmt != merged_store->last_stmt)
4980 : {
4981 351847 : unlink_stmt_vdef (stmt);
4982 351847 : release_defs (stmt);
4983 : }
4984 : }
4985 : ret = true;
4986 : }
4987 : }
4988 388362 : if (ret && dump_file)
4989 92 : fprintf (dump_file, "Merging successful!\n");
4990 :
4991 388362 : return ret;
4992 : }
4993 :
4994 : /* Coalesce the store_immediate_info objects recorded against the base object
4995 : BASE in the first phase and output them.
4996 : Delete the allocated structures.
4997 : Return true if any changes were made. */
4998 :
4999 : bool
5000 2042622 : imm_store_chain_info::terminate_and_process_chain ()
5001 : {
5002 2042622 : if (dump_file && (dump_flags & TDF_DETAILS))
5003 98 : fprintf (dump_file, "Terminating chain with %u stores\n",
5004 : m_store_info.length ());
5005 : /* Process store chain. */
5006 2042622 : bool ret = false;
5007 2042622 : if (m_store_info.length () > 1)
5008 : {
5009 522013 : ret = coalesce_immediate_stores ();
5010 522013 : if (ret)
5011 388362 : ret = output_merged_stores ();
5012 : }
5013 :
5014 : /* Delete all the entries we allocated ourselves. */
5015 2042622 : store_immediate_info *info;
5016 2042622 : unsigned int i;
5017 5280379 : FOR_EACH_VEC_ELT (m_store_info, i, info)
5018 3237757 : delete info;
5019 :
5020 : merged_store_group *merged_info;
5021 2465010 : FOR_EACH_VEC_ELT (m_merged_store_groups, i, merged_info)
5022 422388 : delete merged_info;
5023 :
5024 2042622 : return ret;
5025 : }
5026 :
5027 : /* Return true iff LHS is a destination potentially interesting for
5028 : store merging. In practice these are the codes that get_inner_reference
5029 : can process. */
5030 :
5031 : static bool
5032 9877099 : lhs_valid_for_store_merging_p (tree lhs)
5033 : {
5034 9877099 : if (DECL_P (lhs))
5035 : return true;
5036 :
5037 7529209 : switch (TREE_CODE (lhs))
5038 : {
5039 : case ARRAY_REF:
5040 : case ARRAY_RANGE_REF:
5041 : case BIT_FIELD_REF:
5042 : case COMPONENT_REF:
5043 : case MEM_REF:
5044 : case VIEW_CONVERT_EXPR:
5045 : return true;
5046 : default:
5047 : return false;
5048 : }
5049 : }
5050 :
5051 : /* Return true if the tree RHS is a constant we want to consider
5052 : during store merging. In practice accept all codes that
5053 : native_encode_expr accepts. */
5054 :
5055 : static bool
5056 5312498 : rhs_valid_for_store_merging_p (tree rhs)
5057 : {
5058 5312498 : unsigned HOST_WIDE_INT size;
5059 5312498 : if (TREE_CODE (rhs) == CONSTRUCTOR
5060 1039177 : && CONSTRUCTOR_NELTS (rhs) == 0
5061 1039177 : && TYPE_SIZE_UNIT (TREE_TYPE (rhs))
5062 6351675 : && tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (rhs))))
5063 : return true;
5064 8546642 : return (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (rhs))).is_constant (&size)
5065 4273321 : && native_encode_expr (rhs, NULL, size) != 0);
5066 : }
5067 :
5068 : /* Adjust *PBITPOS, *PBITREGION_START and *PBITREGION_END by BYTE_OFF bytes
5069 : and return true on success or false on failure. */
5070 :
5071 : static bool
5072 1122874 : adjust_bit_pos (poly_offset_int byte_off,
5073 : poly_int64 *pbitpos,
5074 : poly_uint64 *pbitregion_start,
5075 : poly_uint64 *pbitregion_end)
5076 : {
5077 1122874 : poly_offset_int bit_off = byte_off << LOG2_BITS_PER_UNIT;
5078 1122874 : bit_off += *pbitpos;
5079 :
5080 1122874 : if (known_ge (bit_off, 0) && bit_off.to_shwi (pbitpos))
5081 : {
5082 1114062 : if (maybe_ne (*pbitregion_end, 0U))
5083 : {
5084 6950 : bit_off = byte_off << LOG2_BITS_PER_UNIT;
5085 6950 : bit_off += *pbitregion_start;
5086 6950 : if (bit_off.to_uhwi (pbitregion_start))
5087 : {
5088 6950 : bit_off = byte_off << LOG2_BITS_PER_UNIT;
5089 6950 : bit_off += *pbitregion_end;
5090 6950 : if (!bit_off.to_uhwi (pbitregion_end))
5091 0 : *pbitregion_end = 0;
5092 : }
5093 : else
5094 0 : *pbitregion_end = 0;
5095 : }
5096 : return true;
5097 : }
5098 : else
5099 8812 : return false;
5100 : }
5101 :
5102 : /* If MEM is a memory reference usable for store merging (either as
5103 : store destination or for loads), return the non-NULL base_addr
5104 : and set *PBITSIZE, *PBITPOS, *PBITREGION_START and *PBITREGION_END.
5105 : Otherwise return NULL, *PBITPOS should be still valid even for that
5106 : case. */
5107 :
5108 : static tree
5109 5910454 : mem_valid_for_store_merging (tree mem, poly_uint64 *pbitsize,
5110 : poly_uint64 *pbitpos,
5111 : poly_uint64 *pbitregion_start,
5112 : poly_uint64 *pbitregion_end)
5113 : {
5114 5910454 : poly_int64 bitsize, bitpos;
5115 5910454 : poly_uint64 bitregion_start = 0, bitregion_end = 0;
5116 5910454 : machine_mode mode;
5117 5910454 : int unsignedp = 0, reversep = 0, volatilep = 0;
5118 5910454 : tree offset;
5119 5910454 : tree base_addr = get_inner_reference (mem, &bitsize, &bitpos, &offset, &mode,
5120 : &unsignedp, &reversep, &volatilep);
5121 5910454 : *pbitsize = bitsize;
5122 5910454 : if (known_le (bitsize, 0))
5123 : return NULL_TREE;
5124 :
5125 5909228 : if (TREE_CODE (mem) == COMPONENT_REF
5126 5909228 : && DECL_BIT_FIELD_TYPE (TREE_OPERAND (mem, 1)))
5127 : {
5128 48668 : get_bit_range (&bitregion_start, &bitregion_end, mem, &bitpos, &offset);
5129 48668 : if (maybe_ne (bitregion_end, 0U))
5130 48668 : bitregion_end += 1;
5131 : }
5132 :
5133 5909228 : if (reversep)
5134 : return NULL_TREE;
5135 :
5136 : /* We do not want to rewrite TARGET_MEM_REFs. */
5137 5908732 : if (TREE_CODE (base_addr) == TARGET_MEM_REF)
5138 : return NULL_TREE;
5139 : /* In some cases get_inner_reference may return a
5140 : MEM_REF [ptr + byteoffset]. For the purposes of this pass
5141 : canonicalize the base_addr to MEM_REF [ptr] and take
5142 : byteoffset into account in the bitpos. This occurs in
5143 : PR 23684 and this way we can catch more chains. */
5144 5858533 : else if (TREE_CODE (base_addr) == MEM_REF)
5145 : {
5146 1119124 : if (!adjust_bit_pos (mem_ref_offset (base_addr), &bitpos,
5147 : &bitregion_start, &bitregion_end))
5148 : return NULL_TREE;
5149 1110312 : base_addr = TREE_OPERAND (base_addr, 0);
5150 : }
5151 : /* get_inner_reference returns the base object, get at its
5152 : address now. */
5153 : else
5154 : {
5155 4739409 : if (maybe_lt (bitpos, 0))
5156 : return NULL_TREE;
5157 4739279 : base_addr = build_fold_addr_expr (base_addr);
5158 : }
5159 :
5160 5849591 : if (offset)
5161 : {
5162 : /* If the access is variable offset then a base decl has to be
5163 : address-taken to be able to emit pointer-based stores to it.
5164 : ??? We might be able to get away with re-using the original
5165 : base up to the first variable part and then wrapping that inside
5166 : a BIT_FIELD_REF. */
5167 34915 : tree base = get_base_address (base_addr);
5168 34915 : if (!base || (DECL_P (base) && !TREE_ADDRESSABLE (base)))
5169 : return NULL_TREE;
5170 :
5171 : /* Similarly to above for the base, remove constant from the offset. */
5172 34915 : if (TREE_CODE (offset) == PLUS_EXPR
5173 3806 : && TREE_CODE (TREE_OPERAND (offset, 1)) == INTEGER_CST
5174 38721 : && adjust_bit_pos (wi::to_poly_offset (TREE_OPERAND (offset, 1)),
5175 : &bitpos, &bitregion_start, &bitregion_end))
5176 3750 : offset = TREE_OPERAND (offset, 0);
5177 :
5178 34915 : base_addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (base_addr),
5179 : base_addr, offset);
5180 : }
5181 :
5182 5849591 : if (known_eq (bitregion_end, 0U))
5183 : {
5184 5801499 : bitregion_start = round_down_to_byte_boundary (bitpos);
5185 5801499 : bitregion_end = round_up_to_byte_boundary (bitpos + bitsize);
5186 : }
5187 :
5188 11699182 : *pbitsize = bitsize;
5189 5849591 : *pbitpos = bitpos;
5190 5849591 : *pbitregion_start = bitregion_start;
5191 5849591 : *pbitregion_end = bitregion_end;
5192 5849591 : return base_addr;
5193 : }
5194 :
5195 : /* Return true if STMT is a load that can be used for store merging.
5196 : In that case fill in *OP. BITSIZE, BITPOS, BITREGION_START and
5197 : BITREGION_END are properties of the corresponding store. */
5198 :
5199 : static bool
5200 1099449 : handled_load (gimple *stmt, store_operand_info *op,
5201 : poly_uint64 bitsize, poly_uint64 bitpos,
5202 : poly_uint64 bitregion_start, poly_uint64 bitregion_end)
5203 : {
5204 1099449 : if (!is_gimple_assign (stmt))
5205 : return false;
5206 1099340 : if (gimple_assign_rhs_code (stmt) == BIT_NOT_EXPR)
5207 : {
5208 1763 : tree rhs1 = gimple_assign_rhs1 (stmt);
5209 1763 : if (TREE_CODE (rhs1) == SSA_NAME
5210 1763 : && handled_load (SSA_NAME_DEF_STMT (rhs1), op, bitsize, bitpos,
5211 : bitregion_start, bitregion_end))
5212 : {
5213 : /* Don't allow _1 = load; _2 = ~1; _3 = ~_2; which should have
5214 : been optimized earlier, but if allowed here, would confuse the
5215 : multiple uses counting. */
5216 919 : if (op->bit_not_p)
5217 : return false;
5218 919 : op->bit_not_p = !op->bit_not_p;
5219 919 : return true;
5220 : }
5221 : return false;
5222 : }
5223 1097577 : if (gimple_vuse (stmt)
5224 584376 : && gimple_assign_load_p (stmt)
5225 584343 : && !stmt_can_throw_internal (cfun, stmt)
5226 1678609 : && !gimple_has_volatile_ops (stmt))
5227 : {
5228 580699 : tree mem = gimple_assign_rhs1 (stmt);
5229 580699 : op->base_addr
5230 580699 : = mem_valid_for_store_merging (mem, &op->bitsize, &op->bitpos,
5231 : &op->bitregion_start,
5232 : &op->bitregion_end);
5233 580699 : if (op->base_addr != NULL_TREE
5234 527547 : && known_eq (op->bitsize, bitsize)
5235 1055062 : && multiple_p (op->bitpos - bitpos, BITS_PER_UNIT)
5236 527527 : && known_ge (op->bitpos - op->bitregion_start,
5237 : bitpos - bitregion_start)
5238 1107988 : && known_ge (op->bitregion_end - op->bitpos,
5239 : bitregion_end - bitpos))
5240 : {
5241 527230 : op->stmt = stmt;
5242 527230 : op->val = mem;
5243 527230 : op->bit_not_p = false;
5244 527230 : return true;
5245 : }
5246 : }
5247 : return false;
5248 : }
5249 :
5250 : /* Return the index number of the landing pad for STMT, if any. */
5251 :
5252 : static int
5253 3237757 : lp_nr_for_store (gimple *stmt)
5254 : {
5255 3237757 : if (!cfun->can_throw_non_call_exceptions || !cfun->eh)
5256 : return 0;
5257 :
5258 805365 : if (!stmt_could_throw_p (cfun, stmt))
5259 : return 0;
5260 :
5261 78153 : return lookup_stmt_eh_lp (stmt);
5262 : }
5263 :
5264 : /* Record the store STMT for store merging optimization if it can be
5265 : optimized. Return true if any changes were made. */
5266 :
5267 : bool
5268 5329755 : pass_store_merging::process_store (gimple *stmt)
5269 : {
5270 5329755 : tree lhs = gimple_assign_lhs (stmt);
5271 5329755 : tree rhs = gimple_assign_rhs1 (stmt);
5272 5329755 : poly_uint64 bitsize, bitpos = 0;
5273 5329755 : poly_uint64 bitregion_start = 0, bitregion_end = 0;
5274 5329755 : tree base_addr
5275 5329755 : = mem_valid_for_store_merging (lhs, &bitsize, &bitpos,
5276 5329755 : &bitregion_start, &bitregion_end);
5277 5329755 : if (known_eq (bitsize, 0U))
5278 : return false;
5279 :
5280 5328535 : bool invalid = (base_addr == NULL_TREE
5281 5328535 : || (maybe_gt (bitsize,
5282 : (unsigned int) MAX_BITSIZE_MODE_ANY_INT)
5283 165213 : && TREE_CODE (rhs) != INTEGER_CST
5284 165213 : && (TREE_CODE (rhs) != CONSTRUCTOR
5285 150789 : || CONSTRUCTOR_NELTS (rhs) != 0)));
5286 5328535 : enum tree_code rhs_code = ERROR_MARK;
5287 5328535 : bool bit_not_p = false;
5288 5328535 : struct symbolic_number n;
5289 5328535 : gimple *ins_stmt = NULL;
5290 15985605 : store_operand_info ops[2];
5291 5328535 : if (invalid)
5292 : ;
5293 5307620 : else if (TREE_CODE (rhs) == STRING_CST)
5294 : {
5295 3684 : rhs_code = STRING_CST;
5296 3684 : ops[0].val = rhs;
5297 : }
5298 5303936 : else if (rhs_valid_for_store_merging_p (rhs))
5299 : {
5300 2635861 : rhs_code = INTEGER_CST;
5301 2635861 : ops[0].val = rhs;
5302 : }
5303 2668075 : else if (TREE_CODE (rhs) == SSA_NAME)
5304 : {
5305 1740088 : gimple *def_stmt = SSA_NAME_DEF_STMT (rhs), *def_stmt1, *def_stmt2;
5306 1740088 : if (!is_gimple_assign (def_stmt))
5307 : invalid = true;
5308 1078097 : else if (handled_load (def_stmt, &ops[0], bitsize, bitpos,
5309 : bitregion_start, bitregion_end))
5310 : rhs_code = MEM_REF;
5311 562311 : else if (gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
5312 : {
5313 721 : tree rhs1 = gimple_assign_rhs1 (def_stmt);
5314 721 : if (TREE_CODE (rhs1) == SSA_NAME
5315 721 : && is_gimple_assign (SSA_NAME_DEF_STMT (rhs1)))
5316 : {
5317 : bit_not_p = true;
5318 : def_stmt = SSA_NAME_DEF_STMT (rhs1);
5319 : }
5320 : }
5321 :
5322 1740088 : if (rhs_code == ERROR_MARK && !invalid)
5323 562311 : switch ((rhs_code = gimple_assign_rhs_code (def_stmt)))
5324 : {
5325 16657 : case BIT_AND_EXPR:
5326 16657 : case BIT_IOR_EXPR:
5327 16657 : case BIT_XOR_EXPR:
5328 16657 : tree rhs1, rhs2;
5329 16657 : rhs1 = gimple_assign_rhs1 (def_stmt);
5330 16657 : rhs2 = gimple_assign_rhs2 (def_stmt);
5331 16657 : invalid = true;
5332 16657 : if (TREE_CODE (rhs1) != SSA_NAME)
5333 : break;
5334 16657 : def_stmt1 = SSA_NAME_DEF_STMT (rhs1);
5335 16657 : if (!is_gimple_assign (def_stmt1)
5336 16657 : || !handled_load (def_stmt1, &ops[0], bitsize, bitpos,
5337 : bitregion_start, bitregion_end))
5338 : break;
5339 8562 : if (rhs_valid_for_store_merging_p (rhs2))
5340 4461 : ops[1].val = rhs2;
5341 4101 : else if (TREE_CODE (rhs2) != SSA_NAME)
5342 : break;
5343 : else
5344 : {
5345 4101 : def_stmt2 = SSA_NAME_DEF_STMT (rhs2);
5346 4101 : if (!is_gimple_assign (def_stmt2))
5347 : break;
5348 4008 : else if (!handled_load (def_stmt2, &ops[1], bitsize, bitpos,
5349 : bitregion_start, bitregion_end))
5350 : break;
5351 : }
5352 : invalid = false;
5353 : break;
5354 : default:
5355 : invalid = true;
5356 : break;
5357 : }
5358 :
5359 1740088 : unsigned HOST_WIDE_INT const_bitsize;
5360 1740088 : if (bitsize.is_constant (&const_bitsize)
5361 1740088 : && (const_bitsize % BITS_PER_UNIT) == 0
5362 1727076 : && const_bitsize <= 64
5363 1553817 : && multiple_p (bitpos, BITS_PER_UNIT))
5364 : {
5365 1553549 : ins_stmt = find_bswap_or_nop_1 (def_stmt, &n, 12);
5366 1553549 : if (ins_stmt)
5367 : {
5368 515451 : uint64_t nn = n.n;
5369 515451 : for (unsigned HOST_WIDE_INT i = 0;
5370 3639245 : i < const_bitsize;
5371 3123794 : i += BITS_PER_UNIT, nn >>= BITS_PER_MARKER)
5372 3136066 : if ((nn & MARKER_MASK) == 0
5373 3136066 : || (nn & MARKER_MASK) == MARKER_BYTE_UNKNOWN)
5374 : {
5375 : ins_stmt = NULL;
5376 : break;
5377 : }
5378 515451 : if (ins_stmt)
5379 : {
5380 503179 : if (invalid)
5381 : {
5382 63381 : rhs_code = LROTATE_EXPR;
5383 63381 : ops[0].base_addr = NULL_TREE;
5384 63381 : ops[1].base_addr = NULL_TREE;
5385 : }
5386 : invalid = false;
5387 : }
5388 : }
5389 : }
5390 :
5391 63381 : if (invalid
5392 1153578 : && bitsize.is_constant (&const_bitsize)
5393 1153578 : && ((const_bitsize % BITS_PER_UNIT) != 0
5394 1141841 : || !multiple_p (bitpos, BITS_PER_UNIT))
5395 1260917 : && const_bitsize <= MAX_FIXED_MODE_SIZE)
5396 : {
5397 : /* Bypass a conversion to the bit-field type. */
5398 12004 : if (!bit_not_p
5399 11965 : && is_gimple_assign (def_stmt)
5400 18508 : && CONVERT_EXPR_CODE_P (rhs_code))
5401 : {
5402 5020 : tree rhs1 = gimple_assign_rhs1 (def_stmt);
5403 5020 : if (TREE_CODE (rhs1) == SSA_NAME
5404 5020 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
5405 : rhs = rhs1;
5406 : }
5407 12004 : rhs_code = BIT_INSERT_EXPR;
5408 12004 : bit_not_p = false;
5409 12004 : ops[0].val = rhs;
5410 12004 : ops[0].base_addr = NULL_TREE;
5411 12004 : ops[1].base_addr = NULL_TREE;
5412 12004 : invalid = false;
5413 : }
5414 : }
5415 : else
5416 : invalid = true;
5417 :
5418 4379633 : unsigned HOST_WIDE_INT const_bitsize, const_bitpos;
5419 4379633 : unsigned HOST_WIDE_INT const_bitregion_start, const_bitregion_end;
5420 12004 : if (invalid
5421 3238059 : || !bitsize.is_constant (&const_bitsize)
5422 3238059 : || !bitpos.is_constant (&const_bitpos)
5423 3238059 : || !bitregion_start.is_constant (&const_bitregion_start)
5424 3238059 : || !bitregion_end.is_constant (&const_bitregion_end)
5425 4367629 : || ((const_bitregion_end - const_bitregion_start + 1) / BITS_PER_UNIT
5426 3238059 : > (unsigned) param_store_merging_max_size))
5427 2090778 : return terminate_all_aliasing_chains (NULL, stmt);
5428 :
5429 3237757 : if (!ins_stmt)
5430 2734587 : memset (&n, 0, sizeof (n));
5431 :
5432 3237757 : class imm_store_chain_info **chain_info = NULL;
5433 3237757 : bool ret = false;
5434 3237757 : if (base_addr)
5435 3237757 : chain_info = m_stores.get (base_addr);
5436 :
5437 3237757 : store_immediate_info *info;
5438 3237757 : if (chain_info)
5439 : {
5440 1195135 : unsigned int ord = (*chain_info)->m_store_info.length ();
5441 2390270 : info = new store_immediate_info (const_bitsize, const_bitpos,
5442 : const_bitregion_start,
5443 : const_bitregion_end,
5444 : stmt, ord, rhs_code, n, ins_stmt,
5445 : bit_not_p, lp_nr_for_store (stmt),
5446 1195135 : ops[0], ops[1]);
5447 1195135 : if (dump_file && (dump_flags & TDF_DETAILS))
5448 : {
5449 202 : fprintf (dump_file, "Recording immediate store from stmt:\n");
5450 202 : print_gimple_stmt (dump_file, stmt, 0);
5451 : }
5452 1195135 : (*chain_info)->m_store_info.safe_push (info);
5453 1195135 : m_n_stores++;
5454 1195135 : ret |= terminate_all_aliasing_chains (chain_info, stmt);
5455 : /* If we reach the limit of stores to merge in a chain terminate and
5456 : process the chain now. */
5457 1195135 : if ((*chain_info)->m_store_info.length ()
5458 1195135 : == (unsigned int) param_max_stores_to_merge)
5459 : {
5460 582 : if (dump_file && (dump_flags & TDF_DETAILS))
5461 0 : fprintf (dump_file,
5462 : "Reached maximum number of statements to merge:\n");
5463 582 : ret |= terminate_and_process_chain (*chain_info);
5464 : }
5465 : }
5466 : else
5467 : {
5468 : /* Store aliases any existing chain? */
5469 2042622 : ret |= terminate_all_aliasing_chains (NULL, stmt);
5470 :
5471 : /* Start a new chain. */
5472 2042622 : class imm_store_chain_info *new_chain
5473 2042622 : = new imm_store_chain_info (m_stores_head, base_addr);
5474 4085244 : info = new store_immediate_info (const_bitsize, const_bitpos,
5475 : const_bitregion_start,
5476 : const_bitregion_end,
5477 : stmt, 0, rhs_code, n, ins_stmt,
5478 : bit_not_p, lp_nr_for_store (stmt),
5479 2042622 : ops[0], ops[1]);
5480 2042622 : new_chain->m_store_info.safe_push (info);
5481 2042622 : m_n_stores++;
5482 2042622 : m_stores.put (base_addr, new_chain);
5483 2042622 : m_n_chains++;
5484 2042622 : if (dump_file && (dump_flags & TDF_DETAILS))
5485 : {
5486 49 : fprintf (dump_file, "Starting active chain number %u with statement:\n",
5487 : m_n_chains);
5488 49 : print_gimple_stmt (dump_file, stmt, 0);
5489 49 : fprintf (dump_file, "The base object is:\n");
5490 49 : print_generic_expr (dump_file, base_addr);
5491 49 : fprintf (dump_file, "\n");
5492 : }
5493 : }
5494 :
5495 : /* Prune oldest chains so that after adding the chain or store above
5496 : we're again within the limits set by the params. */
5497 3237757 : if (m_n_chains > (unsigned)param_max_store_chains_to_track
5498 3234933 : || m_n_stores > (unsigned)param_max_stores_to_track)
5499 : {
5500 2828 : if (dump_file && (dump_flags & TDF_DETAILS))
5501 0 : fprintf (dump_file, "Too many chains (%u > %d) or stores (%u > %d), "
5502 : "terminating oldest chain(s).\n", m_n_chains,
5503 : param_max_store_chains_to_track, m_n_stores,
5504 : param_max_stores_to_track);
5505 2828 : imm_store_chain_info **e = &m_stores_head;
5506 2828 : unsigned idx = 0;
5507 2828 : unsigned n_stores = 0;
5508 186142 : while (*e)
5509 : {
5510 183314 : if (idx >= (unsigned)param_max_store_chains_to_track
5511 183314 : || (n_stores + (*e)->m_store_info.length ()
5512 180490 : > (unsigned)param_max_stores_to_track))
5513 2828 : ret |= terminate_and_process_chain (*e);
5514 : else
5515 : {
5516 180486 : n_stores += (*e)->m_store_info.length ();
5517 180486 : e = &(*e)->next;
5518 180486 : ++idx;
5519 : }
5520 : }
5521 : }
5522 :
5523 : return ret;
5524 : }
5525 :
5526 : /* Return true if STMT is a store valid for store merging. */
5527 :
5528 : static bool
5529 37437096 : store_valid_for_store_merging_p (gimple *stmt)
5530 : {
5531 37437096 : return gimple_assign_single_p (stmt)
5532 17170642 : && gimple_vdef (stmt)
5533 9877099 : && lhs_valid_for_store_merging_p (gimple_assign_lhs (stmt))
5534 47047893 : && (!gimple_has_volatile_ops (stmt) || gimple_clobber_p (stmt));
5535 : }
5536 :
5537 : enum basic_block_status { BB_INVALID, BB_VALID, BB_EXTENDED_VALID };
5538 :
5539 : /* Return the status of basic block BB wrt store merging. */
5540 :
5541 : static enum basic_block_status
5542 9229994 : get_status_for_store_merging (basic_block bb)
5543 : {
5544 9229994 : unsigned int num_statements = 0;
5545 9229994 : unsigned int num_constructors = 0;
5546 9229994 : gimple_stmt_iterator gsi;
5547 9229994 : edge e;
5548 9229994 : gimple *last_stmt = NULL;
5549 :
5550 77472039 : for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5551 : {
5552 69418578 : gimple *stmt = gsi_stmt (gsi);
5553 :
5554 69418578 : if (is_gimple_debug (stmt))
5555 43191478 : continue;
5556 :
5557 26227100 : last_stmt = stmt;
5558 :
5559 26227100 : if (store_valid_for_store_merging_p (stmt) && ++num_statements >= 2)
5560 : break;
5561 :
5562 25068082 : if (is_gimple_assign (stmt)
5563 25068082 : && (gimple_assign_rhs_code (stmt) == CONSTRUCTOR
5564 15647579 : || gimple_assign_rhs_code (stmt) == VEC_PACK_TRUNC_EXPR))
5565 : {
5566 671600 : tree rhs = gimple_assign_rhs1 (stmt);
5567 671600 : if (VECTOR_TYPE_P (TREE_TYPE (rhs))
5568 129950 : && INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (rhs)))
5569 788000 : && gimple_assign_lhs (stmt) != NULL_TREE)
5570 : {
5571 116400 : HOST_WIDE_INT sz
5572 116400 : = int_size_in_bytes (TREE_TYPE (rhs)) * BITS_PER_UNIT;
5573 116400 : if (sz == 16 || sz == 32 || sz == 64)
5574 : {
5575 : num_constructors = 1;
5576 : break;
5577 : }
5578 : }
5579 : }
5580 : }
5581 :
5582 9229994 : if (num_statements == 0 && num_constructors == 0)
5583 : return BB_INVALID;
5584 :
5585 872591 : if (cfun->can_throw_non_call_exceptions && cfun->eh
5586 872591 : && store_valid_for_store_merging_p (last_stmt)
5587 669268 : && (e = find_fallthru_edge (bb->succs))
5588 2721534 : && e->dest == bb->next_bb)
5589 : return BB_EXTENDED_VALID;
5590 :
5591 2170361 : return (num_statements >= 2 || num_constructors) ? BB_VALID : BB_INVALID;
5592 : }
5593 :
5594 : /* Entry point for the pass. Go over each basic block recording chains of
5595 : immediate stores. Upon encountering a terminating statement (as defined
5596 : by stmt_terminates_chain_p) process the recorded stores and emit the widened
5597 : variants. */
5598 :
5599 : unsigned int
5600 983021 : pass_store_merging::execute (function *fun)
5601 : {
5602 983021 : basic_block bb;
5603 983021 : hash_set<gimple *> orig_stmts;
5604 983021 : bool changed = false, open_chains = false;
5605 :
5606 : /* If the function can throw and catch non-call exceptions, we'll be trying
5607 : to merge stores across different basic blocks so we need to first unsplit
5608 : the EH edges in order to streamline the CFG of the function. */
5609 983021 : if (cfun->can_throw_non_call_exceptions && cfun->eh)
5610 241085 : unsplit_eh_edges ();
5611 :
5612 983021 : calculate_dominance_info (CDI_DOMINATORS);
5613 :
5614 10213015 : FOR_EACH_BB_FN (bb, fun)
5615 : {
5616 9229994 : const basic_block_status bb_status = get_status_for_store_merging (bb);
5617 9229994 : gimple_stmt_iterator gsi;
5618 :
5619 9269532 : if (open_chains && (bb_status == BB_INVALID || !single_pred_p (bb)))
5620 : {
5621 119998 : changed |= terminate_and_process_all_chains ();
5622 119998 : open_chains = false;
5623 : }
5624 :
5625 9229994 : if (bb_status == BB_INVALID)
5626 8007188 : continue;
5627 :
5628 1222806 : if (dump_file && (dump_flags & TDF_DETAILS))
5629 23 : fprintf (dump_file, "Processing basic block <%d>:\n", bb->index);
5630 :
5631 32342498 : for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
5632 : {
5633 31119692 : gimple *stmt = gsi_stmt (gsi);
5634 31119692 : gsi_next (&gsi);
5635 :
5636 31119692 : if (is_gimple_debug (stmt))
5637 20770404 : continue;
5638 :
5639 20213955 : if (gimple_has_volatile_ops (stmt) && !gimple_clobber_p (stmt))
5640 : {
5641 : /* Terminate all chains. */
5642 9672 : if (dump_file && (dump_flags & TDF_DETAILS))
5643 1 : fprintf (dump_file, "Volatile access terminates "
5644 : "all chains\n");
5645 9672 : changed |= terminate_and_process_all_chains ();
5646 9672 : open_chains = false;
5647 9672 : continue;
5648 : }
5649 :
5650 10339616 : if (is_gimple_assign (stmt)
5651 8328001 : && (gimple_assign_rhs_code (stmt) == CONSTRUCTOR
5652 7197214 : || gimple_assign_rhs_code (stmt) == VEC_PACK_TRUNC_EXPR)
5653 11473227 : && maybe_optimize_vector_constructor (stmt))
5654 2211 : continue;
5655 :
5656 10337405 : if (store_valid_for_store_merging_p (stmt))
5657 5329755 : changed |= process_store (stmt);
5658 : else
5659 5007650 : changed |= terminate_all_aliasing_chains (NULL, stmt);
5660 : }
5661 :
5662 1222806 : if (bb_status == BB_EXTENDED_VALID)
5663 : open_chains = true;
5664 : else
5665 : {
5666 1085087 : changed |= terminate_and_process_all_chains ();
5667 1085087 : open_chains = false;
5668 : }
5669 : }
5670 :
5671 983021 : if (open_chains)
5672 0 : changed |= terminate_and_process_all_chains ();
5673 :
5674 : /* If the function can throw and catch non-call exceptions and something
5675 : changed during the pass, then the CFG has (very likely) changed too. */
5676 983021 : if (cfun->can_throw_non_call_exceptions && cfun->eh && changed)
5677 : {
5678 997 : free_dominance_info (CDI_DOMINATORS);
5679 997 : return TODO_cleanup_cfg;
5680 : }
5681 :
5682 : return 0;
5683 983021 : }
5684 :
5685 : } // anon namespace
5686 :
5687 : /* Construct and return a store merging pass object. */
5688 :
5689 : gimple_opt_pass *
5690 297180 : make_pass_store_merging (gcc::context *ctxt)
5691 : {
5692 297180 : return new pass_store_merging (ctxt);
5693 : }
5694 :
5695 : #if CHECKING_P
5696 :
5697 : namespace selftest {
5698 :
5699 : /* Selftests for store merging helpers. */
5700 :
5701 : /* Assert that all elements of the byte arrays X and Y, both of length N
5702 : are equal. */
5703 :
5704 : static void
5705 32 : verify_array_eq (unsigned char *x, unsigned char *y, unsigned int n)
5706 : {
5707 112 : for (unsigned int i = 0; i < n; i++)
5708 : {
5709 80 : if (x[i] != y[i])
5710 : {
5711 0 : fprintf (stderr, "Arrays do not match. X:\n");
5712 0 : dump_char_array (stderr, x, n);
5713 0 : fprintf (stderr, "Y:\n");
5714 0 : dump_char_array (stderr, y, n);
5715 : }
5716 80 : ASSERT_EQ (x[i], y[i]);
5717 : }
5718 32 : }
5719 :
5720 : /* Test shift_bytes_in_array_left and that it carries bits across between
5721 : bytes correctly. */
5722 :
5723 : static void
5724 4 : verify_shift_bytes_in_array_left (void)
5725 : {
5726 : /* byte 1 | byte 0
5727 : 00011111 | 11100000. */
5728 4 : unsigned char orig[2] = { 0xe0, 0x1f };
5729 4 : unsigned char in[2];
5730 4 : memcpy (in, orig, sizeof orig);
5731 :
5732 4 : unsigned char expected[2] = { 0x80, 0x7f };
5733 4 : shift_bytes_in_array_left (in, sizeof (in), 2);
5734 4 : verify_array_eq (in, expected, sizeof (in));
5735 :
5736 4 : memcpy (in, orig, sizeof orig);
5737 4 : memcpy (expected, orig, sizeof orig);
5738 : /* Check that shifting by zero doesn't change anything. */
5739 4 : shift_bytes_in_array_left (in, sizeof (in), 0);
5740 4 : verify_array_eq (in, expected, sizeof (in));
5741 :
5742 4 : }
5743 :
5744 : /* Test shift_bytes_in_array_right and that it carries bits across between
5745 : bytes correctly. */
5746 :
5747 : static void
5748 4 : verify_shift_bytes_in_array_right (void)
5749 : {
5750 : /* byte 1 | byte 0
5751 : 00011111 | 11100000. */
5752 4 : unsigned char orig[2] = { 0x1f, 0xe0};
5753 4 : unsigned char in[2];
5754 4 : memcpy (in, orig, sizeof orig);
5755 4 : unsigned char expected[2] = { 0x07, 0xf8};
5756 4 : shift_bytes_in_array_right (in, sizeof (in), 2);
5757 4 : verify_array_eq (in, expected, sizeof (in));
5758 :
5759 4 : memcpy (in, orig, sizeof orig);
5760 4 : memcpy (expected, orig, sizeof orig);
5761 : /* Check that shifting by zero doesn't change anything. */
5762 4 : shift_bytes_in_array_right (in, sizeof (in), 0);
5763 4 : verify_array_eq (in, expected, sizeof (in));
5764 4 : }
5765 :
5766 : /* Test clear_bit_region that it clears exactly the bits asked and
5767 : nothing more. */
5768 :
5769 : static void
5770 4 : verify_clear_bit_region (void)
5771 : {
5772 : /* Start with all bits set and test clearing various patterns in them. */
5773 4 : unsigned char orig[3] = { 0xff, 0xff, 0xff};
5774 4 : unsigned char in[3];
5775 4 : unsigned char expected[3];
5776 4 : memcpy (in, orig, sizeof in);
5777 :
5778 : /* Check zeroing out all the bits. */
5779 4 : clear_bit_region (in, 0, 3 * BITS_PER_UNIT);
5780 4 : expected[0] = expected[1] = expected[2] = 0;
5781 4 : verify_array_eq (in, expected, sizeof in);
5782 :
5783 4 : memcpy (in, orig, sizeof in);
5784 : /* Leave the first and last bits intact. */
5785 4 : clear_bit_region (in, 1, 3 * BITS_PER_UNIT - 2);
5786 4 : expected[0] = 0x1;
5787 4 : expected[1] = 0;
5788 4 : expected[2] = 0x80;
5789 4 : verify_array_eq (in, expected, sizeof in);
5790 4 : }
5791 :
5792 : /* Test clear_bit_region_be that it clears exactly the bits asked and
5793 : nothing more. */
5794 :
5795 : static void
5796 4 : verify_clear_bit_region_be (void)
5797 : {
5798 : /* Start with all bits set and test clearing various patterns in them. */
5799 4 : unsigned char orig[3] = { 0xff, 0xff, 0xff};
5800 4 : unsigned char in[3];
5801 4 : unsigned char expected[3];
5802 4 : memcpy (in, orig, sizeof in);
5803 :
5804 : /* Check zeroing out all the bits. */
5805 4 : clear_bit_region_be (in, BITS_PER_UNIT - 1, 3 * BITS_PER_UNIT);
5806 4 : expected[0] = expected[1] = expected[2] = 0;
5807 4 : verify_array_eq (in, expected, sizeof in);
5808 :
5809 4 : memcpy (in, orig, sizeof in);
5810 : /* Leave the first and last bits intact. */
5811 4 : clear_bit_region_be (in, BITS_PER_UNIT - 2, 3 * BITS_PER_UNIT - 2);
5812 4 : expected[0] = 0x80;
5813 4 : expected[1] = 0;
5814 4 : expected[2] = 0x1;
5815 4 : verify_array_eq (in, expected, sizeof in);
5816 4 : }
5817 :
5818 :
5819 : /* Run all of the selftests within this file. */
5820 :
5821 : void
5822 4 : store_merging_cc_tests (void)
5823 : {
5824 4 : verify_shift_bytes_in_array_left ();
5825 4 : verify_shift_bytes_in_array_right ();
5826 4 : verify_clear_bit_region ();
5827 4 : verify_clear_bit_region_be ();
5828 4 : }
5829 :
5830 : } // namespace selftest
5831 : #endif /* CHECKING_P. */
|