Line data Source code
1 : /* Late RTL pass to fold memory offsets.
2 : Copyright (C) 2023-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #define INCLUDE_ALGORITHM
21 : #define INCLUDE_FUNCTIONAL
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "rtl.h"
27 : #include "rtlanal.h"
28 : #include "df.h"
29 : #include "rtl-ssa.h"
30 :
31 : #include "predict.h"
32 : #include "cfgrtl.h"
33 : #include "cfgcleanup.h"
34 : #include "tree-pass.h"
35 : #include "target.h"
36 :
37 : #include "tm.h"
38 : #include "tree.h"
39 : #include "expr.h"
40 : #include "regs.h"
41 : #include "memmodel.h"
42 : #include "emit-rtl.h"
43 : #include "insn-config.h"
44 : #include "recog.h"
45 : #include "diagnostic-core.h"
46 :
47 : /* This pass tries to optimize memory offset calculations by moving constants
48 : from add instructions to the memory instructions (loads / stores).
49 : For example it can transform code like this:
50 :
51 : add t4, sp, 16
52 : add t2, a6, t4
53 : shl t3, t2, 1
54 : ld a2, 0(t3)
55 : add a2, 1
56 : sd a2, 8(t2)
57 :
58 : into the following (one instruction less):
59 :
60 : add t2, a6, sp
61 : shl t3, t2, 1
62 : ld a2, 32(t3)
63 : add a2, 1
64 : sd a2, 24(t2)
65 :
66 : Although the previous passes try to emit efficient offset calculations
67 : this pass is still beneficial because:
68 :
69 : - The mechanisms that optimize memory offsets usually work with specific
70 : patterns or have limitations. This pass is designed to fold offsets
71 : through complex calculations that affect multiple memory operations
72 : and have partially overlapping calculations.
73 :
74 : - There are cases where add instructions are introduced in late rtl passes
75 : and the rest of the pipeline cannot eliminate them. Arrays and structs
76 : allocated on the stack can result in unwanted add instructions that
77 : cannot be eliminated easily.
78 :
79 : The pass differentiates between the following instructions:
80 :
81 : - fold-mem-offset root insn: loads/stores where constants will be folded into
82 : the address offset. E.g.:
83 : (set (mem:DI (plus:DI (reg:DI sp) (const_int 40))) (reg:DI ra))
84 : - fold-agnostic insns: instructions that may have an impact on the offset
85 : calculation, but that don't require any fixup when folding. E.g.:
86 : (set (reg:DI a0) (ashift:DI (reg:DI s1) (const_int 1)))
87 : - fold insns: instructions that provide constants, which will be forwarded
88 : into the loads/stores as offset. When folding, the constants will be
89 : set to zero. E.g.:
90 : (set (reg:DI s0) (plus:DI (reg:DI sp) (const_int 8)))
91 :
92 : The pass utilizes the RTL SSA framework to get the data dependencies
93 : and operates in the following phases:
94 :
95 : - Phase 1: Iterate over all instructions to identify fold-mem-offset roots.
96 : - Phase 2: Walk back along the def-chain of fold-agnostic or fold insns.
97 : When successful a new offset of the fold-mem-offset is calculated
98 : and a vec of fold insns that need adjustments is created.
99 : - Phase 3: Drop all fold-mem-offset roots that won't accept the updated
100 : offset.
101 : - Phase 4: Ensure that the defs of all fold insns are used only by
102 : fold-mem-offsets insns (only needed if DEFs with multiple USEs
103 : are handled, which is the default (see multi_use_mode below),
104 : or forced on via -fexpensive-optimizations).
105 : - Phase 5: Update all fold-mem-offset roots and adjust the fold insns.
106 :
107 : When we walk the DEF-chain we have two choices of operations:
108 :
109 : - We only allow DEFs that have exactly one USE (in the instruction
110 : that we come from). This greatly simplifies the problem, but also misses
111 : some cases.
112 : - We allow DEFs to have multiple USEs. E.g. a single ADDI may define a
113 : value that is used by two LOADs. In this case, we need to ensure that all
114 : USE-chains remain correct after we apply our transformation. We do this
115 : by allowing only USEs that are part of any other fold-mem-offset chain in
116 : phase 4 above. This mode is enabled by default, but is disabled for
117 : highly-connected CFGs (unless -fexpensive-optimizations forces it on).
118 :
119 : This pass should run before hard register propagation because it creates
120 : register moves that we expect to be eliminated. */
121 :
122 : using namespace rtl_ssa;
123 :
124 : namespace {
125 :
126 : /* Class that holds in FOLD_INSNS the instructions that if folded the offset
127 : of a memory instruction would increase by ADDED_OFFSET. */
128 28898076 : class fold_mem_info {
129 : public:
130 : /* fold-mem-offset root details. */
131 : insn_info *insn;
132 : rtx mem;
133 : rtx reg;
134 : HOST_WIDE_INT offset;
135 : /* Resulting offset if def-chain gets folded into fold-mem-offset root. */
136 : HOST_WIDE_INT added_offset;
137 :
138 : /* Def-chain for offset. */
139 : auto_vec<insn_info *> fold_agnostic_insns;
140 : auto_vec<insn_info *> fold_insns;
141 :
142 28898076 : fold_mem_info (insn_info *insn, rtx mem, rtx reg, HOST_WIDE_INT off)
143 28898076 : : insn (insn),
144 28898076 : mem (mem),
145 28898076 : reg (reg),
146 28898076 : offset (off),
147 28898076 : added_offset (0)
148 : {
149 : }
150 : };
151 :
152 : class change_info {
153 : public:
154 : insn_change *change;
155 : /* Index specifying the order in RTL SSA's instruction changes. */
156 : int change_index;
157 :
158 : change_info (insn_change *change)
159 : : change (change), change_index (0)
160 : {
161 : }
162 :
163 58 : change_info (insn_change *change, int index)
164 58 : : change (change), change_index (index)
165 : {
166 : }
167 : };
168 :
169 : /* Test if INSN is a memory load / store that can have an offset folded to it.
170 : Return true when INSN is such an instruction and return through MEM,
171 : REG and OFFSET the RTX that has a MEM code, the register that is
172 : used as a base address and the offset accordingly. */
173 : bool
174 119586972 : get_fold_mem_offset_root (insn_info *insn, rtx *mem, rtx *reg,
175 : HOST_WIDE_INT *offset)
176 : {
177 119586972 : rtx set = single_set (insn->rtl ());
178 119586972 : if (set != NULL_RTX)
179 : {
180 110282178 : rtx src = SET_SRC (set);
181 110282178 : rtx dest = SET_DEST (set);
182 :
183 : /* Don't fold when we have unspec / volatile. */
184 110282178 : if (GET_CODE (src) == UNSPEC
185 110282178 : || GET_CODE (src) == UNSPEC_VOLATILE)
186 : return false;
187 :
188 109469768 : if (MEM_P (src))
189 19168348 : *mem = src;
190 90301420 : else if (MEM_P (dest))
191 21518460 : *mem = dest;
192 68782960 : else if ((GET_CODE (src) == SIGN_EXTEND
193 68782960 : || GET_CODE (src) == ZERO_EXTEND)
194 1103948 : && MEM_P (XEXP (src, 0)))
195 329108 : *mem = XEXP (src, 0);
196 : else
197 : return false;
198 : }
199 : else
200 : return false;
201 :
202 41015916 : rtx mem_addr = XEXP (*mem, 0);
203 41015916 : if (REG_P (mem_addr))
204 : {
205 4810802 : *reg = mem_addr;
206 4810802 : *offset = 0;
207 : }
208 36205114 : else if (GET_CODE (mem_addr) == PLUS
209 25916398 : && REG_P (XEXP (mem_addr, 0))
210 24684912 : && CONST_INT_P (XEXP (mem_addr, 1)))
211 : {
212 24087274 : *reg = XEXP (mem_addr, 0);
213 24087274 : *offset = INTVAL (XEXP (mem_addr, 1));
214 : }
215 : else
216 : return false;
217 :
218 : return true;
219 : }
220 :
221 : /* Return true if DEF's register is conditionally redefined by a cond_exec
222 : before DEF is fully overwritten. RTL-SSA models a cond_exec set as a plain
223 : def, missing the old value preserved on the predicate-false path, so such a
224 : redefinition hides a use of DEF and makes folding it unsafe. */
225 :
226 : static bool
227 11819380 : def_shadowed_by_cond_exec_p (set_info *def)
228 : {
229 23771584 : for (def_info *next = def->next_def (); next; next = next->next_def ())
230 : {
231 11194518 : insn_info *next_insn = next->insn ();
232 11194518 : if (next_insn->is_artificial ())
233 : return false;
234 :
235 5128080 : rtx_insn *next_rtl = next_insn->rtl ();
236 5128080 : if (GET_CODE (PATTERN (next_rtl)) == COND_EXEC)
237 : return true;
238 :
239 : /* A full set kills DEF; once dead it cannot reach a later cond_exec.
240 : Keep scanning past defs that leave DEF partially live. */
241 5128080 : if (simple_regno_set (PATTERN (next_rtl), def->regno ()))
242 : return false;
243 : }
244 : return false;
245 : }
246 :
247 : /* Get the single reaching definition of an instruction inside a BB.
248 : Return the definition or NULL if there's no definition with the desired
249 : criteria. If SINGLE_USE is set to true the DEF must have exactly one
250 : USE resulting in a 1:1 DEF-USE relationship. If set to false, then a
251 : 1:n DEF-USE relationship is accepted and the caller must take care to
252 : ensure all USEs are safe folding. */
253 : static set_info *
254 11819392 : get_single_def_in_bb (insn_info *insn, rtx reg, bool single_use)
255 : {
256 : /* Get the use_info of the base register. */
257 13856712 : for (use_info *use : insn->uses ())
258 : {
259 : /* Other USEs can be ignored and multiple equal USEs are fine. */
260 13856712 : if (use->regno () != REGNO (reg))
261 2037320 : continue;
262 :
263 : /* Don't handle subregs for now. */
264 11819392 : if (use->includes_subregs ())
265 11819392 : return NULL;
266 :
267 : /* Get the DEF of the register. Bail on a cond_exec redefinition of
268 : REG, which hides uses of DEF from RTL-SSA. */
269 11819380 : set_info *def = use->def ();
270 11819380 : if (!def || def_shadowed_by_cond_exec_p (def))
271 0 : return NULL;
272 :
273 : /* Limit the amount of USEs of DEF to 1. */
274 11819380 : if (single_use && !def->single_nondebug_use ())
275 : return NULL;
276 :
277 : /* Don't handle multiregs for now. */
278 6851544 : if (def->includes_multiregs ())
279 : return NULL;
280 :
281 : /* Only consider uses whose definition comes from a real instruction
282 : and has no notes attached. */
283 6845337 : insn_info *def_insn = def->insn ();
284 6845337 : rtx_insn *def_rtl = def_insn->rtl ();
285 6845337 : if (def_insn->is_artificial ()
286 2733164 : || find_reg_note (def_rtl, REG_EQUIV, NULL_RTX)
287 9040253 : || find_reg_note (def_rtl, REG_EQUAL, NULL_RTX))
288 4657681 : return NULL;
289 :
290 : /* No parallel expressions or clobbers. */
291 2187656 : if (def_insn->num_defs () != 1)
292 : return NULL;
293 :
294 1816037 : if (!NONJUMP_INSN_P (def_rtl) || RTX_FRAME_RELATED_P (def_rtl))
295 : return NULL;
296 :
297 : /* Check if the DEF is a SET of the expected form. */
298 1565993 : rtx def_set = simple_regno_set (PATTERN (def_rtl), def->regno ());
299 1565993 : if (!def_set)
300 : return NULL;
301 :
302 : /* Ensure DEF and USE are in the same BB. */
303 1565813 : if (def->bb () != insn->bb ())
304 : return NULL;
305 :
306 : return def;
307 : }
308 :
309 0 : return NULL;
310 : }
311 :
312 : static bool
313 : fold_offsets (insn_info *insn, rtx reg, HOST_WIDE_INT *offset_out,
314 : fold_mem_info *info, bool single_use);
315 :
316 : /* Return the offset computed by fold_offsets, or 0 if the analysis fails.
317 : Used in fold_offsets_1 where failure means no constant contribution. */
318 : static HOST_WIDE_INT
319 204058 : fold_offsets_value (insn_info *insn, rtx reg, fold_mem_info *info,
320 : bool single_use)
321 : {
322 204058 : HOST_WIDE_INT offset;
323 204058 : fold_offsets (insn, reg, &offset, info, single_use);
324 204058 : return offset;
325 : }
326 :
327 : /* Helper function for fold_offsets () that analyses the given INSN.
328 :
329 : For INSN with known pattern, we calculate the value of the propagated
330 : constant and store that in OFFSET_OUT. Foldable INSNs are added to
331 : INFO->fold_insns and fold-agnostic INSNs are added to
332 : INFO->fold_agnostic_insns. It is possible that some INSNs are added to
333 : both lists; when that happens the INSN is a fold insn.
334 :
335 : Returns true when the analysis succeeds. Otherwise false. */
336 : static bool
337 699397 : fold_offsets_1 (insn_info *insn, HOST_WIDE_INT *offset_out,
338 : fold_mem_info *info, bool single_use)
339 : {
340 699397 : bool fold_agnostic = true;
341 699397 : rtx_insn *insn_rtl = insn->rtl ();
342 699397 : rtx set = single_set (insn_rtl);
343 699397 : if (!set)
344 : return false;
345 :
346 699397 : rtx src = SET_SRC (set);
347 699397 : HOST_WIDE_INT offset = 0;
348 :
349 699397 : switch (GET_CODE (src))
350 : {
351 44441 : case PLUS:
352 44441 : {
353 : /* Propagate through add. */
354 44441 : rtx arg1 = XEXP (src, 0);
355 44441 : rtx arg2 = XEXP (src, 1);
356 :
357 44441 : if (REG_P (arg1))
358 12908 : offset += fold_offsets_value (insn, arg1, info, single_use);
359 31533 : else if (GET_CODE (arg1) == ASHIFT
360 23453 : && REG_P (XEXP (arg1, 0))
361 23453 : && CONST_INT_P (XEXP (arg1, 1)))
362 : {
363 : /* Handle R1 = (R2 << C) + ... */
364 23453 : rtx reg = XEXP (arg1, 0);
365 23453 : rtx shamt = XEXP (arg1, 1);
366 23453 : HOST_WIDE_INT scale = HOST_WIDE_INT_1U << INTVAL (shamt);
367 23453 : offset += scale * fold_offsets_value (insn, reg, info, single_use);
368 23453 : }
369 8080 : else if (GET_CODE (arg1) == PLUS
370 8028 : && REG_P (XEXP (arg1, 0))
371 6956 : && REG_P (XEXP (arg1, 1)))
372 : {
373 : /* Handle R1 = (R2 + R3) + ... */
374 6956 : rtx reg1 = XEXP (arg1, 0);
375 6956 : rtx reg2 = XEXP (arg1, 1);
376 6956 : if (REGNO (reg1) != REGNO (reg2))
377 : {
378 6956 : offset += fold_offsets_value (insn, reg1, info, single_use);
379 6956 : offset += fold_offsets_value (insn, reg2, info, single_use);
380 : }
381 : else
382 0 : offset += 2 * fold_offsets_value (insn, reg1, info, single_use);
383 : }
384 1124 : else if (GET_CODE (arg1) == PLUS
385 1072 : && GET_CODE (XEXP (arg1, 0)) == ASHIFT
386 1066 : && REG_P (XEXP (XEXP (arg1, 0), 0))
387 1066 : && CONST_INT_P (XEXP (XEXP (arg1, 0), 1))
388 1066 : && REG_P (XEXP (arg1, 1)))
389 : {
390 : /* Handle R1 = ((R2 << C) + R3) + ... */
391 1066 : rtx reg1 = XEXP (XEXP (arg1, 0), 0);
392 1066 : rtx shamt = XEXP (XEXP (arg1, 0), 1);
393 1066 : rtx reg2 = XEXP (arg1, 1);
394 1066 : HOST_WIDE_INT scale = HOST_WIDE_INT_1U << INTVAL (shamt);
395 1066 : if (REGNO (reg1) != REGNO (reg2))
396 : {
397 2072 : offset += scale
398 1036 : * fold_offsets_value (insn, reg1, info, single_use);
399 1036 : offset += fold_offsets_value (insn, reg2, info, single_use);
400 : }
401 : else
402 30 : offset += (scale + 1) * fold_offsets_value (insn, reg1, info,
403 : single_use);
404 : }
405 : else
406 : return false;
407 :
408 44383 : if (REG_P (arg2))
409 33337 : offset += fold_offsets_value (insn, arg2, info, single_use);
410 11046 : else if (CONST_INT_P (arg2))
411 : {
412 9584 : if (REG_P (arg1))
413 : {
414 1736 : offset += INTVAL (arg2);
415 : /* This is a R1 = R2 + C instruction, candidate for
416 : folding. */
417 1736 : fold_agnostic = false;
418 : }
419 : }
420 : else
421 : return false;
422 :
423 : /* Pattern recognized for folding. */
424 : break;
425 : }
426 0 : case MINUS:
427 0 : {
428 : /* Propagate through minus. */
429 0 : rtx arg1 = XEXP (src, 0);
430 0 : rtx arg2 = XEXP (src, 1);
431 :
432 0 : if (REG_P (arg1))
433 0 : offset += fold_offsets_value (insn, arg1, info, single_use);
434 : else
435 : return false;
436 :
437 0 : if (REG_P (arg2))
438 0 : offset -= fold_offsets_value (insn, arg2, info, single_use);
439 0 : else if (CONST_INT_P (arg2))
440 : {
441 0 : if (REG_P (arg1))
442 : {
443 0 : offset -= INTVAL (arg2);
444 : /* This is a R1 = R2 - C instruction, candidate for
445 : folding. */
446 0 : fold_agnostic = false;
447 : }
448 : }
449 : else
450 : return false;
451 :
452 : /* Pattern recognized for folding. */
453 : break;
454 : }
455 0 : case NEG:
456 0 : {
457 : /* Propagate through negation. */
458 0 : rtx arg1 = XEXP (src, 0);
459 0 : if (REG_P (arg1))
460 0 : offset = -fold_offsets_value (insn, arg1, info, single_use);
461 : else
462 : return false;
463 :
464 : /* Pattern recognized for folding. */
465 0 : break;
466 : }
467 1093 : case MULT:
468 1093 : {
469 : /* Propagate through multiply by constant. */
470 1093 : rtx arg1 = XEXP (src, 0);
471 1093 : rtx arg2 = XEXP (src, 1);
472 :
473 1093 : if (REG_P (arg1) && CONST_INT_P (arg2))
474 : {
475 1093 : HOST_WIDE_INT scale = INTVAL (arg2);
476 1093 : offset = scale * fold_offsets_value (insn, arg1, info, single_use);
477 : }
478 : else
479 : return false;
480 :
481 : /* Pattern recognized for folding. */
482 1093 : break;
483 : }
484 0 : case ASHIFT:
485 0 : {
486 : /* Propagate through shift left by constant. */
487 0 : rtx arg1 = XEXP (src, 0);
488 0 : rtx arg2 = XEXP (src, 1);
489 :
490 0 : if (REG_P (arg1) && CONST_INT_P (arg2))
491 : {
492 0 : HOST_WIDE_INT scale = (HOST_WIDE_INT_1U << INTVAL (arg2));
493 0 : offset = scale * fold_offsets_value (insn, arg1, info, single_use);
494 : }
495 : else
496 : return false;
497 :
498 : /* Pattern recognized for folding. */
499 0 : break;
500 : }
501 117253 : case REG:
502 117253 : {
503 : /* Propagate through register move. */
504 117253 : offset = fold_offsets_value (insn, src, info, single_use);
505 :
506 : /* Pattern recognized for folding. */
507 117253 : break;
508 : }
509 6 : case CONST_INT:
510 6 : {
511 6 : offset = INTVAL (src);
512 : /* R1 = C is candidate for folding. */
513 6 : fold_agnostic = false;
514 :
515 : /* Pattern recognized for folding. */
516 6 : break;
517 : }
518 : default:
519 : /* Cannot recognize. */
520 : return false;
521 : }
522 :
523 161273 : if (offset_out)
524 161273 : *offset_out = offset;
525 :
526 161273 : if (fold_agnostic)
527 : {
528 159531 : if (!single_use)
529 139710 : info->fold_agnostic_insns.safe_push (insn);
530 : }
531 1742 : else if (!info->fold_insns.contains (insn))
532 1742 : info->fold_insns.safe_push (insn);
533 :
534 : return true;
535 : }
536 :
537 : /* Returns true when all USEs of DEF (which defines REG) meet certain criteria
538 : to be foldable. Otherwise false. */
539 : static bool
540 1021182 : has_foldable_uses_p (set_info *def, rtx reg)
541 : {
542 : /* We only fold through instructions that are transitively used as
543 : memory addresses and do not have other uses. Use the same logic
544 : from offset calculation to visit instructions that can propagate
545 : offsets and keep track of them in CAN_FOLD_INSNS. */
546 10633162 : for (use_info *use : def->nondebug_insn_uses ())
547 : {
548 4617184 : insn_info *use_insn = use->insn ();
549 4617184 : if (use_insn->is_artificial ())
550 : return false;
551 :
552 : /* Only handle an insn with a simple single set here. */
553 4472423 : rtx_insn *use_rtl = use_insn->rtl ();
554 4472423 : if (!NONJUMP_INSN_P (use_rtl) || GET_CODE (PATTERN (use_rtl)) != SET)
555 : return false;
556 :
557 : /* Special case: A foldable memory store is not foldable if it
558 : mentions DEST outside of the address calculation. */
559 4396056 : rtx use_set = PATTERN (use_rtl);
560 4396056 : if (use_set && MEM_P (SET_DEST (use_set))
561 1605031 : && reg_mentioned_p (reg, SET_SRC (use_set)))
562 : return false;
563 :
564 8678744 : if (use->bb () != def->bb ())
565 : return false;
566 : }
567 :
568 : return true;
569 : }
570 :
571 :
572 : /* Function that calculates the offset for INSN that would have to be added to
573 : all its USEs of REG. Foldable INSNs are added to INFO->fold_insns and
574 : fold-agnostic INSNs are added to INFO->fold_agnostic_insns.
575 : It is possible that some INSNs are added to both lists; when that happens
576 : the INSN is a fold insn.
577 :
578 : On success, returns true and stores the offset in *OFFSET_OUT. On failure,
579 : returns false and sets *OFFSET_OUT to 0. */
580 : static bool
581 29102134 : fold_offsets (insn_info *insn, rtx reg, HOST_WIDE_INT *offset_out,
582 : fold_mem_info *info, bool single_use = true)
583 : {
584 29102134 : *offset_out = 0;
585 :
586 : /* We can only affect the values of GPR registers. */
587 29102134 : unsigned int regno = REGNO (reg);
588 29102134 : if (fixed_regs[regno]
589 29102134 : || !TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], regno))
590 : return false;
591 :
592 : /* Get the DEF for REG in INSN. */
593 11819392 : set_info *def = get_single_def_in_bb (insn, reg, single_use);
594 11819392 : if (!def)
595 : return false;
596 :
597 1021182 : insn_info *def_insn = def->insn ();
598 1021182 : rtx_insn *def_rtl = def_insn->rtl ();
599 :
600 1021182 : if (dump_file && (dump_flags & TDF_DETAILS))
601 : {
602 0 : fprintf (dump_file, "For INSN: ");
603 0 : print_rtl_single (dump_file, insn->rtl ());
604 0 : fprintf (dump_file, "...found DEF: ");
605 0 : print_rtl_single (dump_file, def_rtl);
606 : }
607 :
608 1021182 : gcc_assert (REGNO (reg) == def->regno ());
609 :
610 : /* Check if all USEs of DEF are safe. */
611 1021182 : if (!has_foldable_uses_p (def, reg))
612 : {
613 321785 : if (dump_file && (dump_flags & TDF_DETAILS))
614 : {
615 0 : fprintf (dump_file, "has_foldable_uses_p failed for: ");
616 0 : print_rtl_single (dump_file, def_rtl);
617 : }
618 321785 : return false;
619 : }
620 :
621 : /* Check if we know how to handle DEF. */
622 699397 : HOST_WIDE_INT offset;
623 699397 : if (!fold_offsets_1 (def_insn, &offset, info, single_use))
624 : {
625 538124 : if (dump_file && (dump_flags & TDF_DETAILS))
626 : {
627 0 : fprintf (dump_file, "fold_offsets_1 failed for: ");
628 0 : print_rtl_single (dump_file, def_rtl);
629 : }
630 538124 : return false;
631 : }
632 :
633 161273 : if (dump_file && (dump_flags & TDF_DETAILS))
634 : {
635 0 : fprintf (dump_file, "Instruction marked for propagation: ");
636 0 : print_rtl_single (dump_file, def_rtl);
637 : }
638 :
639 161273 : *offset_out = offset;
640 161273 : return true;
641 : }
642 :
643 : /* Check if any of the provided INSNs in INSN_LIST is not marked in the
644 : given bitmap. Return true if at least one INSN is not in the bitmap and
645 : false otherwise. */
646 : static bool
647 1406 : insn_uses_not_in_bitmap (vec<insn_info *> *insn_list, bitmap bm)
648 : {
649 4181 : for (insn_info *insn : *insn_list)
650 : {
651 1354 : gcc_assert (insn->num_defs () == 1);
652 1354 : set_info *def = dyn_cast<set_info *>(insn->defs ()[0]);
653 5928 : for (use_info *use : def->nondebug_insn_uses ())
654 : {
655 2897 : if (!bitmap_bit_p (bm, use->insn ()->uid ()))
656 : {
657 1287 : if (dump_file && (dump_flags & TDF_DETAILS))
658 : {
659 0 : fprintf (dump_file, "Cannot ensure correct transformation as "
660 : "INSN %u has a USE INSN %u that was not analysed.\n",
661 : insn->uid (), use->insn ()->uid ());
662 : }
663 :
664 1287 : return true;
665 : }
666 : }
667 : }
668 :
669 : return false;
670 : }
671 :
672 : /* Check if all USEs of all instructions have been analysed.
673 : If a fold_mem_info is found that has an unknown USE, then
674 : drop it from the list. When this function returns all
675 : fold_mem_infos in the worklist reference instructions that
676 : have been analysed before and can therefore be committed. */
677 : static void
678 976481 : drop_unsafe_candidates (vec<fold_mem_info *> *worklist)
679 : {
680 977768 : bool changed;
681 1955536 : do
682 : {
683 977768 : changed = false;
684 :
685 : /* First mark all analysed INSNs in a bitmap. */
686 977768 : auto_bitmap insn_closure;
687 2939427 : for (fold_mem_info *info : worklist)
688 : {
689 6123 : bitmap_set_bit (insn_closure, info->insn->uid ());
690 25886 : for (insn_info *insn : info->fold_agnostic_insns)
691 7779 : bitmap_set_bit (insn_closure, insn->uid ());
692 25758 : for (insn_info *insn : info->fold_insns)
693 7389 : bitmap_set_bit (insn_closure, insn->uid ());
694 : }
695 :
696 : /* Now check if all uses of fold_insns are marked. */
697 : unsigned i;
698 : fold_mem_info *info;
699 979517 : FOR_EACH_VEC_ELT (*worklist, i, info)
700 : {
701 1319 : if (insn_uses_not_in_bitmap (&info->fold_agnostic_insns, insn_closure)
702 1319 : || insn_uses_not_in_bitmap (&info->fold_insns, insn_closure))
703 : {
704 1287 : if (dump_file && (dump_flags & TDF_DETAILS))
705 : {
706 0 : fprintf (dump_file,
707 : "Dropping fold-mem-offset root INSN %u.\n",
708 0 : info->insn->uid ());
709 : }
710 :
711 : /* Drop INFO from worklist and restart. */
712 1287 : worklist->unordered_remove (i);
713 2574 : delete info;
714 : changed = true;
715 : break;
716 : }
717 : }
718 977768 : }
719 : while (changed);
720 976481 : }
721 :
722 : /* If INSN is a root memory instruction that was affected by any folding
723 : then update its offset as necessary. */
724 : static rtx
725 51 : do_commit_offset (fold_mem_info *info)
726 : {
727 51 : rtx mem = info->mem;
728 51 : rtx reg = info->reg;
729 51 : HOST_WIDE_INT new_offset = info->offset + info->added_offset;
730 :
731 51 : if (info->added_offset == 0)
732 : return NULL_RTX;
733 :
734 51 : rtx new_mem = copy_rtx (mem);
735 :
736 51 : machine_mode mode = GET_MODE (XEXP (new_mem, 0));
737 51 : if (new_offset != 0)
738 51 : XEXP (new_mem, 0)
739 51 : = gen_rtx_PLUS (mode, reg, gen_int_mode (new_offset, mode));
740 : else
741 0 : XEXP (new_mem, 0) = reg;
742 :
743 51 : rtx new_insn = simplify_replace_rtx (info->insn->rtl (), mem, new_mem);
744 :
745 51 : return new_insn;
746 : }
747 :
748 : /* If INSN is a move / add instruction that was folded then replace its
749 : constant with zero. Append the resulting insn_change to CHANGES for the
750 : caller to commit. */
751 : static rtx_insn *
752 16 : do_commit_insn (insn_info *insn, auto_vec<change_info *> *changes)
753 : {
754 16 : rtx_insn *insn_rtl = insn->rtl ();
755 16 : rtx_insn *new_insn_rtl = as_a<rtx_insn *> (copy_rtx (insn_rtl));
756 :
757 : /* If we deleted this INSNs before, then nothing left to do here. */
758 16 : if (insn_rtl->deleted ())
759 : return NULL;
760 :
761 16 : rtx set = single_set (new_insn_rtl);
762 16 : rtx src = SET_SRC (set);
763 :
764 : /* Emit a move and let subsequent passes eliminate it if possible. */
765 16 : if (CONST_INT_P (src))
766 : {
767 : /* Only change if necessary. */
768 0 : if (INTVAL (src))
769 : {
770 : /* INSN is R1 = C. Set C to 0 because it was folded. */
771 0 : SET_SRC (set) = CONST0_RTX (GET_MODE (SET_SRC (set)));
772 0 : change_info *change = new change_info (
773 0 : new insn_change (insn),
774 0 : num_validated_changes ());
775 0 : changes->safe_push (change);
776 :
777 0 : return new_insn_rtl;
778 : }
779 : }
780 : else
781 : {
782 16 : if (!BINARY_P (src))
783 : return NULL;
784 :
785 6 : rtx sec_src_op = XEXP (src, 1);
786 :
787 : /* Only change if necessary. */
788 6 : if (INTVAL (sec_src_op))
789 : {
790 : /* Mark self-assignments for deletion. */
791 6 : rtx dest = SET_DEST (set);
792 6 : change_info *change = nullptr;
793 6 : if (REGNO (dest) == REGNO (XEXP (src, 0)))
794 0 : change = new change_info (
795 0 : new insn_change (insn, insn_change::DELETE),
796 0 : num_validated_changes ());
797 : else
798 : {
799 : /* If INSN is R1 = R2 + C, C is folded to 0, so emit a mov
800 : instead. */
801 6 : new_insn_rtl = gen_move_insn (SET_DEST (set), XEXP (src, 0));
802 6 : change = new change_info (
803 6 : new insn_change (insn), num_validated_changes ());
804 : }
805 :
806 6 : changes->safe_push (change);
807 6 : return new_insn_rtl;
808 : }
809 : }
810 :
811 : return NULL;
812 : }
813 :
814 : /* Order two insn_change objects by the program order of their insns. */
815 :
816 : static bool
817 61 : sort_changes (insn_change *a, insn_change *b)
818 : {
819 61 : return a->insn ()->compare_with (b->insn ()) < 0;
820 : }
821 :
822 : /* A changes_map entry copied out for deterministic, regno-ordered traversal:
823 : REGNO is the map key and CHANGES the insn_change list for it. */
824 :
825 : struct regno_changes
826 : {
827 : unsigned regno;
828 : auto_vec<insn_change *> *changes;
829 : };
830 :
831 : /* qsort comparator that orders regno_changes entries by ascending regno. */
832 :
833 : static int
834 0 : sort_pairs (const void *p1, const void *p2)
835 : {
836 0 : const regno_changes *a = (const regno_changes *) p1;
837 0 : const regno_changes *b = (const regno_changes *) p2;
838 :
839 0 : if (a->regno < b->regno)
840 : return -1;
841 0 : if (a->regno > b->regno)
842 0 : return 1;
843 : return 0;
844 : }
845 :
846 : /* Find and return the last definition of INSN. */
847 :
848 : static def_info *
849 0 : get_last_def (insn_info *insn)
850 : {
851 0 : for (def_info *def : insn->defs ())
852 0 : if (def->insn () == insn)
853 0 : return def;
854 :
855 0 : return NULL;
856 : }
857 :
858 : /* Move uses of DEF to the previous definition. */
859 :
860 : static void
861 0 : move_uses_to_prev_def (def_info *def)
862 : {
863 0 : auto set = dyn_cast<set_info *> (def);
864 0 : while (set->first_use ())
865 : {
866 0 : auto prev_set = dyn_cast<set_info *> (def->prev_def ());
867 : if (!prev_set)
868 : break;
869 0 : crtl->ssa->reparent_use (set->first_use (), prev_set);
870 : }
871 0 : }
872 :
873 : /* Check if CHANGE exists in CHANGES. */
874 :
875 : static bool
876 22 : change_in_vec_p (const auto_vec<change_info *> &changes,
877 : const change_info &change)
878 : {
879 100 : for (const change_info *other_change : changes)
880 46 : if (other_change->change->insn () == change.change->insn ())
881 : return true;
882 :
883 : return false;
884 : }
885 :
886 : /* Cancel current changes, clear CHANGES vector and update REMOVED_REGNOS. */
887 : static void
888 36 : cancel_changes_for_group (int change_index, bitmap removed_regnos,
889 : unsigned regno, int *min_index)
890 : {
891 1 : if (*min_index == -1 || change_index < *min_index)
892 35 : *min_index = change_index;
893 36 : bitmap_set_bit (removed_regnos, regno);
894 0 : }
895 :
896 : /* Find the keys in CHANGES_MAP that need to be removed, based on
897 : CANCEL_MIN_INDEX and store them in KEYS_TO_REMOVE. We do this by iterating
898 : the entries of the map recalculating the minimum index, until reaching a
899 : fixed-point. */
900 :
901 : static void
902 35 : find_keys_to_remove (const hash_map<int_hash<unsigned, -1U, -2U>,
903 : auto_vec<change_info *>> &changes_map,
904 : bitmap keys_to_remove,
905 : int *cancel_min_index)
906 : {
907 35 : bool index_changed;
908 70 : do {
909 35 : index_changed = false;
910 74 : for (const auto &entry : changes_map)
911 : {
912 2 : int min_index = INT_MAX;
913 2 : bool cancelled_group = bitmap_bit_p (keys_to_remove, entry.first);
914 10 : for (change_info *change : entry.second)
915 : {
916 4 : int change_index = change->change_index;
917 4 : if (change_index < min_index)
918 : min_index = change_index;
919 :
920 4 : if (!cancelled_group && change_index >= *cancel_min_index)
921 : {
922 1 : bitmap_set_bit (keys_to_remove, entry.first);
923 1 : cancelled_group = true;
924 : }
925 : }
926 :
927 2 : if (cancelled_group && min_index < *cancel_min_index)
928 : {
929 0 : *cancel_min_index = min_index;
930 0 : index_changed = true;
931 0 : break;
932 : }
933 : }
934 : }
935 : while (index_changed);
936 35 : }
937 :
938 : /* Free all change_info objects (and their inner insn_change) owned by
939 : CHANGES_INFO. Used on early returns in update_insns before ownership
940 : is transferred to changes_map. */
941 :
942 : static void
943 36 : free_changes_info (auto_vec<change_info *> &changes_info)
944 : {
945 144 : for (change_info *ci : changes_info)
946 : {
947 36 : delete ci->change;
948 36 : delete ci;
949 : }
950 36 : }
951 :
952 : /* Update the memory offsets and constants in fold insns based on the analysis
953 : done in fold_mem_offsets_1, using RTL SSA. ATTEMPT is the attempt object
954 : for the current changes. CHANGES_MAP holds the changes that are going
955 : to performed and is updated inside the function. REMOVED_REGNOS holds the
956 : keys of the map that have been removed, in order to prevent new attempts
957 : on these. */
958 : static unsigned int
959 52 : update_insns (fold_mem_info *info,
960 : obstack_watermark *attempt,
961 : hash_map<int_hash<unsigned, -1U, -2U>, auto_vec<change_info *>>
962 : *changes_map,
963 : bitmap removed_regnos,
964 : int *cancel_min_index)
965 : {
966 52 : insn_info *insn = info->insn;
967 52 : unsigned int stats_fold_count = 0;
968 :
969 52 : auto_vec<change_info *> changes_info;
970 :
971 52 : insn_change *change = new insn_change (insn);
972 52 : change_info *change_inf = new change_info (change, num_validated_changes ());
973 52 : int change_index = change_inf->change_index;
974 52 : changes_info.safe_push (change_inf);
975 :
976 52 : if (info->fold_insns.is_empty ())
977 : {
978 0 : free_changes_info (changes_info);
979 0 : return stats_fold_count;
980 : }
981 :
982 52 : const rtx_insn *last_fold_insn_rtl = info->fold_insns.last ()->rtl ();
983 52 : rtx last_set = single_set (last_fold_insn_rtl);
984 52 : if (!last_set)
985 : {
986 0 : free_changes_info (changes_info);
987 0 : return stats_fold_count;
988 : }
989 52 : unsigned regno_key = REGNO (SET_DEST (last_set));
990 52 : auto_vec<change_info *> *prev_changes = changes_map->get (regno_key);
991 :
992 : /* Abort if changes for this key have been cancelled before. */
993 52 : if (bitmap_bit_p (removed_regnos, regno_key))
994 : {
995 1 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
996 : cancel_min_index);
997 1 : free_changes_info (changes_info);
998 1 : return stats_fold_count;
999 : }
1000 :
1001 : /* Keep a copy of insn_change elements only. */
1002 102 : auto_vec<insn_change *> changes (changes_info.length ());
1003 204 : for (change_info *ci : changes_info)
1004 51 : changes.quick_push (ci->change);
1005 :
1006 102 : auto ignore = ignore_changing_insns (changes);
1007 51 : if (!rtl_ssa::restrict_movement (*change, ignore))
1008 : {
1009 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1010 0 : fprintf (dump_file, "Restrict movement: Cannot update INSN %u.\n",
1011 : insn->uid ());
1012 0 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
1013 : cancel_min_index);
1014 0 : free_changes_info (changes_info);
1015 0 : return stats_fold_count;
1016 : }
1017 :
1018 51 : rtx new_insn = do_commit_offset (info);
1019 51 : if (new_insn == NULL_RTX)
1020 : {
1021 0 : free_changes_info (changes_info);
1022 0 : return stats_fold_count;
1023 : }
1024 :
1025 51 : rtx_insn *insn_rtl = info->insn->rtl ();
1026 51 : validate_change (insn_rtl, &PATTERN (insn_rtl), PATTERN (new_insn), 1);
1027 :
1028 : /* Check change validity and new instruction cost. */
1029 51 : if (!recog (*attempt, *change, ignore)
1030 45 : || !changes_are_worthwhile (changes)
1031 83 : || !crtl->ssa->verify_insn_changes (changes))
1032 : {
1033 35 : if (dump_file && (dump_flags & TDF_DETAILS))
1034 0 : fprintf (dump_file, "Recog/verify: Cannot update INSN %u.\n",
1035 : insn->uid ());
1036 35 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
1037 : cancel_min_index);
1038 35 : free_changes_info (changes_info);
1039 35 : return stats_fold_count;
1040 : }
1041 :
1042 16 : if (dump_file)
1043 0 : fprintf (dump_file, "INSN %u: Memory offset changed from "
1044 : HOST_WIDE_INT_PRINT_DEC " to " HOST_WIDE_INT_PRINT_DEC ".\n",
1045 0 : insn->uid (), info->offset, info->offset + info->added_offset);
1046 :
1047 32 : while (!info->fold_insns.is_empty ())
1048 : {
1049 16 : insn_info *fold_insn = info->fold_insns.pop ();
1050 16 : rtx_insn *fold_insn_rtl = fold_insn->rtl ();
1051 :
1052 16 : rtx_insn *new_fold_insn = do_commit_insn (fold_insn, &changes_info);
1053 16 : if (!new_fold_insn)
1054 10 : continue;
1055 :
1056 6 : change_info *last_change = changes_info.last ();
1057 6 : changes.safe_push (last_change->change);
1058 :
1059 12 : std::sort (changes.begin (), changes.end (), sort_changes);
1060 :
1061 12 : auto ignore = ignore_changing_insns (changes);
1062 6 : if (!rtl_ssa::restrict_movement (*last_change->change, ignore))
1063 : {
1064 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1065 0 : fprintf (dump_file, "Restrict movement: Cannot update INSN %u.\n",
1066 : fold_insn->uid ());
1067 0 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
1068 : cancel_min_index);
1069 0 : free_changes_info (changes_info);
1070 0 : return 0;
1071 : }
1072 :
1073 12 : if (!changes_are_worthwhile (changes)
1074 12 : || !crtl->ssa->verify_insn_changes (changes))
1075 : {
1076 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1077 0 : fprintf (dump_file, "Verify: Cannot update INSN %u.\n",
1078 : fold_insn->uid ());
1079 0 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
1080 : cancel_min_index);
1081 0 : free_changes_info (changes_info);
1082 0 : return 0;
1083 : }
1084 :
1085 6 : if (last_change->change->is_deletion ())
1086 : {
1087 : /* Find last instruction's def. */
1088 0 : def_info *insn_def = get_last_def (last_change->change->insn ());
1089 :
1090 : /* Move uses of deleted instruction to the previous def. */
1091 0 : move_uses_to_prev_def (insn_def);
1092 : }
1093 : else
1094 : {
1095 6 : last_change->change_index = num_validated_changes ();
1096 6 : validate_change (fold_insn_rtl, &PATTERN (fold_insn_rtl),
1097 6 : PATTERN (new_fold_insn), 1);
1098 6 : if (!recog (*attempt, *last_change->change, ignore))
1099 : {
1100 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1101 0 : fprintf (dump_file, "Recog: Cannot update INSN %u.\n",
1102 : fold_insn->uid ());
1103 0 : cancel_changes_for_group (change_index, removed_regnos, regno_key,
1104 : cancel_min_index);
1105 0 : free_changes_info (changes_info);
1106 0 : return 0;
1107 : }
1108 : }
1109 :
1110 6 : if (dump_file)
1111 : {
1112 0 : const int last_change_uid = last_change->change->insn ()->uid ();
1113 0 : if (last_change->change->is_deletion ())
1114 0 : fprintf (dump_file, "INSN %u: Marked for deletion.\n",
1115 : last_change_uid);
1116 : else
1117 0 : fprintf (dump_file, "INSN %u: Constant set to zero.\n",
1118 : last_change_uid);
1119 : }
1120 :
1121 6 : stats_fold_count++;
1122 : }
1123 :
1124 : /* Add new changes to changes_map. */
1125 16 : if (prev_changes)
1126 : {
1127 40 : for (change_info *change : changes_info)
1128 10 : if (!change_in_vec_p (*prev_changes, *change))
1129 10 : prev_changes->safe_push (change);
1130 : else
1131 : {
1132 0 : delete change->change;
1133 0 : delete change;
1134 : }
1135 : }
1136 : else
1137 30 : for (change_info *change : changes_info)
1138 : {
1139 12 : auto_vec<change_info *> &change_vect
1140 12 : = changes_map->get_or_insert (regno_key);
1141 :
1142 12 : if (!change_in_vec_p (change_vect, *change))
1143 12 : change_vect.safe_push (change);
1144 : else
1145 : {
1146 0 : delete change->change;
1147 0 : delete change;
1148 : }
1149 : }
1150 :
1151 : return stats_fold_count;
1152 51 : }
1153 :
1154 : /* Helper function for fold_mem_offsets. Fold memory offsets by analysing the
1155 : DEF-USE chain. If SINGLE_USE is true the DEFs will only have a single use,
1156 : otherwise they can have multiple uses. */
1157 : static unsigned int
1158 1952962 : fold_mem_offsets_1 (bool single_use)
1159 : {
1160 1952962 : unsigned int stats_fold_count = 0;
1161 :
1162 : /* This maps the instruction changes to the register defined by the last
1163 : fold_insn of the def-chain (the one nearest the fold-mem-offset root).
1164 : We use this so that we can group interdependent instructions. In this
1165 : way, we can restrict the change cancellation in a group only, if anything
1166 : goes wrong. */
1167 1952962 : hash_map<int_hash<unsigned, -1U, -2U>, auto_vec<change_info *>> changes_map;
1168 :
1169 1952962 : auto attempt = crtl->ssa->new_change_attempt ();
1170 1952962 : insn_change_watermark watermark;
1171 :
1172 : /* Set of removed reg numbers (keys to changes_map). If a change for a reg
1173 : number has been cancelled, we need to invalidate any future changes. */
1174 1952962 : auto_bitmap removed_regnos;
1175 :
1176 1952962 : int cancel_min_index = -1;
1177 :
1178 : /* Iterate over all nondebug INSNs get our candidates and fold them. */
1179 1952962 : auto_vec<fold_mem_info *> worklist;
1180 378707586 : for (auto insn : iterate_safely (crtl->ssa->nondebug_insns ()))
1181 : {
1182 188377312 : if (!insn->is_real () || !insn->can_be_optimized ())
1183 188375973 : continue;
1184 :
1185 119586972 : rtx mem, reg;
1186 119586972 : HOST_WIDE_INT offset;
1187 119586972 : if (!get_fold_mem_offset_root (insn, &mem, ®, &offset))
1188 90688896 : continue;
1189 :
1190 28898076 : fold_mem_info *info = new fold_mem_info (insn, mem, reg, offset);
1191 :
1192 28898076 : if (dump_file && (dump_flags & TDF_DETAILS))
1193 : {
1194 0 : fprintf (dump_file, "Starting analysis from root: ");
1195 0 : print_rtl_single (dump_file, info->insn->rtl ());
1196 : }
1197 :
1198 : /* Walk DEF-chain and collect info.fold_insns and the resulting
1199 : offset. */
1200 28898076 : if (!fold_offsets (info->insn, info->reg, &info->added_offset, info,
1201 : single_use)
1202 28898076 : || info->added_offset == 0)
1203 : {
1204 57793474 : delete info;
1205 28896737 : continue;
1206 : }
1207 :
1208 1339 : if (dump_file && (dump_flags & TDF_DETAILS))
1209 0 : fprintf (dump_file,
1210 : "Found root offset delta: " HOST_WIDE_INT_PRINT_DEC "\n",
1211 : info->added_offset);
1212 :
1213 1339 : if (single_use)
1214 : {
1215 20 : stats_fold_count += update_insns (info, &attempt, &changes_map,
1216 : removed_regnos, &cancel_min_index);
1217 40 : delete info;
1218 : }
1219 : else
1220 : /* Append candidate. */
1221 1319 : worklist.safe_push (info);
1222 : }
1223 :
1224 1952962 : if (!single_use)
1225 : {
1226 : /* Now drop all fold_mem_infos, which contain INSNs that have unknown
1227 : USEs and are therefore not safe to change. */
1228 976481 : drop_unsafe_candidates (&worklist);
1229 :
1230 1952994 : while (!worklist.is_empty ())
1231 : {
1232 32 : fold_mem_info *info = worklist.pop ();
1233 32 : stats_fold_count += update_insns (info, &attempt, &changes_map,
1234 : removed_regnos, &cancel_min_index);
1235 64 : delete info;
1236 : }
1237 : }
1238 :
1239 : /* In case that instructions have been cancelled, remove related
1240 : instructions from the map and find the minimum index to use in
1241 : cancel_changes. */
1242 1952962 : if (cancel_min_index != -1)
1243 : {
1244 35 : find_keys_to_remove (changes_map, removed_regnos, &cancel_min_index);
1245 :
1246 35 : bitmap_iterator bi;
1247 35 : unsigned int key;
1248 71 : EXECUTE_IF_SET_IN_BITMAP (removed_regnos, 0, key, bi)
1249 : {
1250 36 : auto_vec<change_info *> *changes = changes_map.get (key);
1251 36 : if (changes)
1252 : {
1253 5 : for (change_info *change : *changes)
1254 : {
1255 2 : if (dump_file)
1256 0 : fprintf (dump_file, "Change cancelled for insn %u.\n",
1257 0 : change->change->insn ()->uid ());
1258 2 : delete change->change;
1259 2 : delete change;
1260 : }
1261 : }
1262 36 : changes_map.remove (key);
1263 : }
1264 :
1265 35 : cancel_changes (cancel_min_index);
1266 : }
1267 :
1268 1952962 : if (cancel_min_index != 0)
1269 1952928 : confirm_change_group ();
1270 :
1271 : /* Copy the map into a vector and sort it for traversal. */
1272 1952962 : unsigned int map_entries_num = changes_map.elements ();
1273 1952962 : auto_vec<regno_changes> regno_changes_vec (map_entries_num);
1274 :
1275 1952967 : for (auto entry : changes_map)
1276 : {
1277 5 : auto_vec<insn_change *> *changes_vec
1278 10 : = new auto_vec<insn_change *> (entry.second.length ());
1279 :
1280 35 : for (change_info *change : entry.second)
1281 20 : changes_vec->quick_push (change->change);
1282 :
1283 5 : regno_changes rc;
1284 5 : rc.regno = static_cast<unsigned> (entry.first);
1285 5 : rc.changes = changes_vec;
1286 5 : regno_changes_vec.quick_push (rc);
1287 : }
1288 :
1289 1952962 : regno_changes_vec.qsort (sort_pairs);
1290 :
1291 1952977 : for (const auto &rc : regno_changes_vec)
1292 : {
1293 5 : auto_vec<insn_change *> &changes = *rc.changes;
1294 :
1295 : /* Skip already deleted instructions. */
1296 10 : auto_vec<insn_change *> live_changes (changes.length ());
1297 35 : for (insn_change *change : changes)
1298 20 : if (change->insn ()->has_been_deleted ())
1299 0 : delete change;
1300 : else
1301 20 : live_changes.quick_push (change);
1302 :
1303 10 : std::sort (live_changes.begin (), live_changes.end (), sort_changes);
1304 10 : crtl->ssa->change_insns (live_changes);
1305 :
1306 30 : for (insn_change *change : live_changes)
1307 20 : delete change;
1308 :
1309 10 : delete rc.changes;
1310 5 : }
1311 :
1312 : /* Free the change_info wrappers for successful (non-cancelled) entries.
1313 : Their inner insn_change has already been deleted above. Cancelled
1314 : entries were removed from changes_map and freed earlier. */
1315 1952972 : for (auto entry : changes_map)
1316 35 : for (change_info *ci : entry.second)
1317 20 : delete ci;
1318 :
1319 1952962 : return stats_fold_count;
1320 1952962 : }
1321 :
1322 : /* Main function of fold-mem-offsets pass. */
1323 : static unsigned int
1324 976481 : fold_mem_offsets (function *fn)
1325 : {
1326 976481 : bool multi_use_mode = true;
1327 :
1328 : /* Analysing every USE of a DEF (multi-use mode, below) is expensive on
1329 : flow graphs which have a high connectivity and is unlikely to be
1330 : particularly useful there, so gate it on the edge count.
1331 :
1332 : In normal circumstances a cfg should have about twice as many
1333 : edges as blocks. But we do not want to punish small functions
1334 : which have a couple switch statements. Rather than simply
1335 : threshold the number of blocks, use something with a more
1336 : graceful degradation. */
1337 976481 : if (n_edges_for_fn (fn) > 20000 + n_basic_blocks_for_fn (fn) * 4)
1338 0 : multi_use_mode = false;
1339 :
1340 : /* Initialize RTL SSA. */
1341 976481 : calculate_dominance_info (CDI_DOMINATORS);
1342 976481 : df_analyze ();
1343 976481 : crtl->ssa = new rtl_ssa::function_info (cfun);
1344 :
1345 : /* The number of instructions that were simplified or eliminated. */
1346 976481 : int stats_fold_count = 0;
1347 :
1348 : /* Fold mem offsets with DEFs that have a single USE. */
1349 976481 : stats_fold_count += fold_mem_offsets_1 (true);
1350 :
1351 : /* Fold mem offsets with DEFs that have multiple USEs. This expensive
1352 : analysis is skipped for highly-connected CFGs, unless forced on with
1353 : -fexpensive-optimizations. As the latter is enabled by default at -O2,
1354 : the skip only takes effect under -fno-expensive-optimizations. */
1355 976481 : if (multi_use_mode || flag_expensive_optimizations)
1356 : {
1357 976481 : if (dump_file)
1358 22 : fprintf (dump_file, "Starting multi-use analysis\n");
1359 976481 : stats_fold_count += fold_mem_offsets_1 (false);
1360 : }
1361 : else
1362 0 : warning (OPT_Wdisabled_optimization,
1363 : "fold-mem-offsets: disabling multi-use analysis for %d basic "
1364 : "blocks and %d edges/basic block",
1365 : n_basic_blocks_for_fn (fn),
1366 0 : n_edges_for_fn (fn) / n_basic_blocks_for_fn (fn));
1367 :
1368 976481 : statistics_counter_event (cfun, "Number of folded instructions",
1369 : stats_fold_count);
1370 :
1371 976481 : free_dominance_info (CDI_DOMINATORS);
1372 976481 : if (crtl->ssa->perform_pending_updates ())
1373 0 : cleanup_cfg (0);
1374 :
1375 976481 : delete crtl->ssa;
1376 976481 : crtl->ssa = nullptr;
1377 :
1378 976481 : return 0;
1379 : }
1380 :
1381 : const pass_data pass_data_fold_mem =
1382 : {
1383 : RTL_PASS, /* type */
1384 : "fold_mem_offsets", /* name */
1385 : OPTGROUP_NONE, /* optinfo_flags */
1386 : TV_FOLD_MEM_OFFSETS, /* tv_id */
1387 : 0, /* properties_required */
1388 : 0, /* properties_provided */
1389 : 0, /* properties_destroyed */
1390 : 0, /* todo_flags_start */
1391 : TODO_df_finish, /* todo_flags_finish */
1392 : };
1393 :
1394 : class pass_fold_mem_offsets : public rtl_opt_pass
1395 : {
1396 : public:
1397 292371 : pass_fold_mem_offsets (gcc::context *ctxt)
1398 584742 : : rtl_opt_pass (pass_data_fold_mem, ctxt)
1399 : {}
1400 :
1401 : /* opt_pass methods: */
1402 1504958 : bool gate (function *) final override
1403 : {
1404 1504958 : return flag_fold_mem_offsets && optimize >= 2;
1405 : }
1406 :
1407 976481 : unsigned int execute (function *fn) final override
1408 : {
1409 976481 : return fold_mem_offsets (fn);
1410 : }
1411 : }; // class pass_fold_mem_offsets
1412 :
1413 : } // anon namespace
1414 :
1415 : rtl_opt_pass *
1416 292371 : make_pass_fold_mem_offsets (gcc::context *ctxt)
1417 : {
1418 292371 : return new pass_fold_mem_offsets (ctxt);
1419 : }
|
