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 29353498 : 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 29353498 : fold_mem_info (insn_info *insn, rtx mem, rtx reg, HOST_WIDE_INT off)
143 29353498 : : insn (insn),
144 29353498 : mem (mem),
145 29353498 : reg (reg),
146 29353498 : offset (off),
147 29353498 : 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 7 : : change (change), change_index (index)
165 : {
166 : }
167 : };
168 :
169 : /* Check if CHANGE exists in CHANGES. */
170 :
171 : static bool
172 24 : change_in_vec_p (const auto_vec<change_info *> &changes,
173 : const change_info &change)
174 : {
175 105 : for (const change_info *other_change : changes)
176 47 : if (other_change->change->insn () == change.change->insn ())
177 : return true;
178 :
179 : return false;
180 : }
181 :
182 : /* Instruction changes that are going to be committed, keyed by the id of the
183 : fold group that they belong to (see fold_groups). */
184 : using changes_map_t
185 : = hash_map<int_hash<unsigned, -1U, -2U>, auto_vec<change_info *>>;
186 :
187 : /* Zeroing the constant of a fold insn is only correct if every fold-mem-offset
188 : root that addresses memory through it is updated with the compensating
189 : offset. Roots that share fold insns, directly or through another root,
190 : therefore form a group, which has to be committed, or cancelled, as one
191 : unit. */
192 :
193 : class fold_groups
194 : {
195 : public:
196 : /* Put the def-chain FOLD_INSNS in one group and return its id. Insns that
197 : already belong to a group merge that group into the result, so chains
198 : sharing a fold insn end up in the same group. */
199 51 : unsigned add_chain (const vec<insn_info *> &fold_insns)
200 : {
201 51 : unsigned group = 0;
202 51 : bool found = false;
203 204 : for (insn_info *insn : fold_insns)
204 51 : if (unsigned *seen = m_insn_group.get (insn))
205 : {
206 11 : group = found ? merge (group, *seen) : find (*seen);
207 11 : found = true;
208 : }
209 :
210 51 : if (!found)
211 : {
212 40 : group = m_parent.length ();
213 40 : m_parent.safe_push (group);
214 : }
215 :
216 204 : for (insn_info *insn : fold_insns)
217 51 : m_insn_group.put (insn, group);
218 :
219 51 : return group;
220 : }
221 :
222 : /* Changes to commit, per group. */
223 : changes_map_t changes;
224 :
225 : /* Groups whose changes have been cancelled; no further changes may be
226 : attempted for them. */
227 : auto_bitmap cancelled;
228 :
229 : private:
230 : /* Resolve ID to the id of the group that it now belongs to. */
231 11 : unsigned find (unsigned id)
232 : {
233 11 : while (m_parent[id] != id)
234 : id = m_parent[id];
235 11 : return id;
236 : }
237 :
238 : /* Merge the groups holding A and B and return the surviving id, which
239 : takes over the changes and the cancelled state of the absorbed group. */
240 0 : unsigned merge (unsigned a, unsigned b)
241 : {
242 0 : a = find (a);
243 0 : b = find (b);
244 0 : if (a == b)
245 : return a;
246 :
247 : /* Canonicalize on the smaller id, so that the surviving key does not
248 : depend on the order in which the chains were processed. */
249 0 : if (b < a)
250 0 : std::swap (a, b);
251 0 : m_parent[b] = a;
252 :
253 : /* Take A's entry first: get_or_insert can resize the map, which would
254 : invalidate a pointer to B's entry taken before it. The groups were
255 : disjoint, so the lists cannot overlap. */
256 0 : auto_vec<change_info *> &a_changes = changes.get_or_insert (a);
257 0 : if (auto_vec<change_info *> *b_changes = changes.get (b))
258 : {
259 0 : a_changes.safe_splice (*b_changes);
260 0 : changes.remove (b);
261 : }
262 :
263 0 : if (bitmap_clear_bit (cancelled, b))
264 0 : bitmap_set_bit (cancelled, a);
265 :
266 : return a;
267 : }
268 :
269 : /* Union-find parent of every group id. */
270 : auto_vec<unsigned> m_parent;
271 :
272 : /* The group of each fold insn seen so far. */
273 : hash_map<insn_info *, unsigned> m_insn_group;
274 : };
275 :
276 : /* Test if INSN is a memory load / store that can have an offset folded to it.
277 : Return true when INSN is such an instruction and return through MEM,
278 : REG and OFFSET the RTX that has a MEM code, the register that is
279 : used as a base address and the offset accordingly. */
280 : bool
281 121507984 : get_fold_mem_offset_root (insn_info *insn, rtx *mem, rtx *reg,
282 : HOST_WIDE_INT *offset)
283 : {
284 121507984 : rtx set = single_set (insn->rtl ());
285 121507984 : if (set != NULL_RTX)
286 : {
287 112046238 : rtx src = SET_SRC (set);
288 112046238 : rtx dest = SET_DEST (set);
289 :
290 : /* Don't fold when we have unspec / volatile. */
291 112046238 : if (GET_CODE (src) == UNSPEC
292 112046238 : || GET_CODE (src) == UNSPEC_VOLATILE)
293 : return false;
294 :
295 111225798 : if (MEM_P (src))
296 19400024 : *mem = src;
297 91825774 : else if (MEM_P (dest))
298 21801078 : *mem = dest;
299 70024696 : else if ((GET_CODE (src) == SIGN_EXTEND
300 70024696 : || GET_CODE (src) == ZERO_EXTEND)
301 1123676 : && MEM_P (XEXP (src, 0)))
302 332338 : *mem = XEXP (src, 0);
303 : else
304 : return false;
305 : }
306 : else
307 : return false;
308 :
309 41533440 : rtx mem_addr = XEXP (*mem, 0);
310 41533440 : if (REG_P (mem_addr))
311 : {
312 4859470 : *reg = mem_addr;
313 4859470 : *offset = 0;
314 : }
315 36673970 : else if (GET_CODE (mem_addr) == PLUS
316 26307238 : && REG_P (XEXP (mem_addr, 0))
317 25087342 : && CONST_INT_P (XEXP (mem_addr, 1)))
318 : {
319 24494028 : *reg = XEXP (mem_addr, 0);
320 24494028 : *offset = INTVAL (XEXP (mem_addr, 1));
321 : }
322 : else
323 : return false;
324 :
325 : return true;
326 : }
327 :
328 : /* Return true if DEF's register is conditionally redefined by a cond_exec
329 : before DEF is fully overwritten. RTL-SSA models a cond_exec set as a plain
330 : def, missing the old value preserved on the predicate-false path, so such a
331 : redefinition hides a use of DEF and makes folding it unsafe. */
332 :
333 : static bool
334 12014076 : def_shadowed_by_cond_exec_p (set_info *def)
335 : {
336 23460069 : for (def_info *next = def->next_def (); next; next = next->next_def ())
337 : {
338 11379901 : insn_info *next_insn = next->insn ();
339 11379901 : if (next_insn->is_artificial ())
340 : return false;
341 :
342 5216941 : rtx_insn *next_rtl = next_insn->rtl ();
343 5216941 : if (GET_CODE (PATTERN (next_rtl)) == COND_EXEC)
344 : return true;
345 :
346 : /* A full set kills DEF; once dead it cannot reach a later cond_exec.
347 : Keep scanning past defs that leave DEF partially live. */
348 5216941 : if (simple_regno_set (PATTERN (next_rtl), def->regno ()))
349 : return false;
350 : }
351 : return false;
352 : }
353 :
354 : /* Get the single reaching definition of an instruction inside a BB.
355 : Return the definition or NULL if there's no definition with the desired
356 : criteria. If SINGLE_USE is set to true the DEF must have exactly one
357 : USE resulting in a 1:1 DEF-USE relationship. If set to false, then a
358 : 1:n DEF-USE relationship is accepted and the caller must take care to
359 : ensure all USEs are safe folding. */
360 : static set_info *
361 12014088 : get_single_def_in_bb (insn_info *insn, rtx reg, bool single_use)
362 : {
363 : /* Get the use_info of the base register. */
364 26106200 : for (use_info *use : insn->uses ())
365 : {
366 : /* Other USEs can be ignored and multiple equal USEs are fine. */
367 14092112 : if (use->regno () != REGNO (reg))
368 2078024 : continue;
369 :
370 : /* Don't handle subregs for now. */
371 12014088 : if (use->includes_subregs ())
372 12014088 : return NULL;
373 :
374 : /* Get the DEF of the register. Bail on a cond_exec redefinition of
375 : REG, which hides uses of DEF from RTL-SSA. */
376 12014076 : set_info *def = use->def ();
377 12014076 : if (!def || def_shadowed_by_cond_exec_p (def))
378 : return NULL;
379 :
380 : /* Limit the amount of USEs of DEF to 1. */
381 12014076 : if (single_use && !def->single_nondebug_use ())
382 : return NULL;
383 :
384 : /* Don't handle multiregs for now. */
385 6967602 : if (def->includes_multiregs ())
386 : return NULL;
387 :
388 : /* Only consider uses whose definition comes from a real instruction
389 : and has no notes attached. */
390 6961255 : insn_info *def_insn = def->insn ();
391 6961255 : rtx_insn *def_rtl = def_insn->rtl ();
392 6961255 : if (def_insn->is_artificial ()
393 2769505 : || find_reg_note (def_rtl, REG_EQUIV, NULL_RTX)
394 9183592 : || find_reg_note (def_rtl, REG_EQUAL, NULL_RTX))
395 : return NULL;
396 :
397 : /* No parallel expressions or clobbers. */
398 2214695 : if (def_insn->num_defs () != 1)
399 : return NULL;
400 :
401 1840120 : if (!NONJUMP_INSN_P (def_rtl) || RTX_FRAME_RELATED_P (def_rtl))
402 : return NULL;
403 :
404 : /* Check if the DEF is a SET of the expected form. */
405 1589755 : rtx def_set = simple_regno_set (PATTERN (def_rtl), def->regno ());
406 1589755 : if (!def_set)
407 : return NULL;
408 :
409 : /* Ensure DEF and USE are in the same BB. */
410 1589575 : if (def->bb () != insn->bb ())
411 555643 : return NULL;
412 :
413 : return def;
414 : }
415 :
416 0 : return NULL;
417 : }
418 :
419 : static bool
420 : fold_offsets (insn_info *insn, rtx reg, HOST_WIDE_INT *offset_out,
421 : fold_mem_info *info, bool single_use);
422 :
423 : /* Return the offset computed by fold_offsets, or 0 if the analysis fails.
424 : Used in fold_offsets_1 where failure means no constant contribution. */
425 : static HOST_WIDE_INT
426 204053 : fold_offsets_value (insn_info *insn, rtx reg, fold_mem_info *info,
427 : bool single_use)
428 : {
429 204053 : HOST_WIDE_INT offset;
430 204053 : fold_offsets (insn, reg, &offset, info, single_use);
431 204053 : return offset;
432 : }
433 :
434 : /* Helper function for fold_offsets () that analyses the given INSN.
435 :
436 : For INSN with known pattern, we calculate the value of the propagated
437 : constant and store that in OFFSET_OUT. Foldable INSNs are added to
438 : INFO->fold_insns and fold-agnostic INSNs are added to
439 : INFO->fold_agnostic_insns. It is possible that some INSNs are added to
440 : both lists; when that happens the INSN is a fold insn.
441 :
442 : Returns true when the analysis succeeds. Otherwise false. */
443 : static bool
444 702032 : fold_offsets_1 (insn_info *insn, HOST_WIDE_INT *offset_out,
445 : fold_mem_info *info, bool single_use)
446 : {
447 702032 : bool fold_agnostic = true;
448 702032 : rtx_insn *insn_rtl = insn->rtl ();
449 702032 : rtx set = single_set (insn_rtl);
450 702032 : if (!set)
451 : return false;
452 :
453 702032 : rtx src = SET_SRC (set);
454 702032 : HOST_WIDE_INT offset = 0;
455 :
456 702032 : switch (GET_CODE (src))
457 : {
458 43901 : case PLUS:
459 43901 : {
460 : /* Propagate through add. */
461 43901 : rtx arg1 = XEXP (src, 0);
462 43901 : rtx arg2 = XEXP (src, 1);
463 :
464 43901 : if (REG_P (arg1))
465 13555 : offset += fold_offsets_value (insn, arg1, info, single_use);
466 30346 : else if (GET_CODE (arg1) == ASHIFT
467 22305 : && REG_P (XEXP (arg1, 0))
468 22305 : && CONST_INT_P (XEXP (arg1, 1)))
469 : {
470 : /* Handle R1 = (R2 << C) + ... */
471 22305 : rtx reg = XEXP (arg1, 0);
472 22305 : rtx shamt = XEXP (arg1, 1);
473 22305 : HOST_WIDE_INT scale = HOST_WIDE_INT_1U << INTVAL (shamt);
474 22305 : offset += scale * fold_offsets_value (insn, reg, info, single_use);
475 22305 : }
476 8041 : else if (GET_CODE (arg1) == PLUS
477 7985 : && REG_P (XEXP (arg1, 0))
478 6938 : && REG_P (XEXP (arg1, 1)))
479 : {
480 : /* Handle R1 = (R2 + R3) + ... */
481 6938 : rtx reg1 = XEXP (arg1, 0);
482 6938 : rtx reg2 = XEXP (arg1, 1);
483 6938 : if (REGNO (reg1) != REGNO (reg2))
484 : {
485 6938 : offset += fold_offsets_value (insn, reg1, info, single_use);
486 6938 : offset += fold_offsets_value (insn, reg2, info, single_use);
487 : }
488 : else
489 0 : offset += 2 * fold_offsets_value (insn, reg1, info, single_use);
490 : }
491 1103 : else if (GET_CODE (arg1) == PLUS
492 1047 : && GET_CODE (XEXP (arg1, 0)) == ASHIFT
493 1027 : && REG_P (XEXP (XEXP (arg1, 0), 0))
494 1027 : && CONST_INT_P (XEXP (XEXP (arg1, 0), 1))
495 1027 : && REG_P (XEXP (arg1, 1)))
496 : {
497 : /* Handle R1 = ((R2 << C) + R3) + ... */
498 1027 : rtx reg1 = XEXP (XEXP (arg1, 0), 0);
499 1027 : rtx shamt = XEXP (XEXP (arg1, 0), 1);
500 1027 : rtx reg2 = XEXP (arg1, 1);
501 1027 : HOST_WIDE_INT scale = HOST_WIDE_INT_1U << INTVAL (shamt);
502 1027 : if (REGNO (reg1) != REGNO (reg2))
503 : {
504 1994 : offset += scale
505 997 : * fold_offsets_value (insn, reg1, info, single_use);
506 997 : offset += fold_offsets_value (insn, reg2, info, single_use);
507 : }
508 : else
509 30 : offset += (scale + 1) * fold_offsets_value (insn, reg1, info,
510 : single_use);
511 : }
512 : else
513 : return false;
514 :
515 43825 : if (REG_P (arg2))
516 33092 : offset += fold_offsets_value (insn, arg2, info, single_use);
517 10733 : else if (CONST_INT_P (arg2))
518 : {
519 9544 : if (REG_P (arg1))
520 : {
521 1602 : offset += INTVAL (arg2);
522 : /* This is a R1 = R2 + C instruction, candidate for
523 : folding. */
524 1602 : fold_agnostic = false;
525 : }
526 : }
527 : else
528 : return false;
529 :
530 : /* Pattern recognized for folding. */
531 : break;
532 : }
533 0 : case MINUS:
534 0 : {
535 : /* Propagate through minus. */
536 0 : rtx arg1 = XEXP (src, 0);
537 0 : rtx arg2 = XEXP (src, 1);
538 :
539 0 : if (REG_P (arg1))
540 0 : offset += fold_offsets_value (insn, arg1, info, single_use);
541 : else
542 : return false;
543 :
544 0 : if (REG_P (arg2))
545 0 : offset -= fold_offsets_value (insn, arg2, info, single_use);
546 0 : else if (CONST_INT_P (arg2))
547 : {
548 0 : if (REG_P (arg1))
549 : {
550 0 : offset -= INTVAL (arg2);
551 : /* This is a R1 = R2 - C instruction, candidate for
552 : folding. */
553 0 : fold_agnostic = false;
554 : }
555 : }
556 : else
557 : return false;
558 :
559 : /* Pattern recognized for folding. */
560 : break;
561 : }
562 0 : case NEG:
563 0 : {
564 : /* Propagate through negation. */
565 0 : rtx arg1 = XEXP (src, 0);
566 0 : if (REG_P (arg1))
567 0 : offset = -fold_offsets_value (insn, arg1, info, single_use);
568 : else
569 : return false;
570 :
571 : /* Pattern recognized for folding. */
572 0 : break;
573 : }
574 1089 : case MULT:
575 1089 : {
576 : /* Propagate through multiply by constant. */
577 1089 : rtx arg1 = XEXP (src, 0);
578 1089 : rtx arg2 = XEXP (src, 1);
579 :
580 1089 : if (REG_P (arg1) && CONST_INT_P (arg2))
581 : {
582 1089 : HOST_WIDE_INT scale = INTVAL (arg2);
583 1089 : offset = scale * fold_offsets_value (insn, arg1, info, single_use);
584 : }
585 : else
586 : return false;
587 :
588 : /* Pattern recognized for folding. */
589 1089 : break;
590 : }
591 0 : case ASHIFT:
592 0 : {
593 : /* Propagate through shift left by constant. */
594 0 : rtx arg1 = XEXP (src, 0);
595 0 : rtx arg2 = XEXP (src, 1);
596 :
597 0 : if (REG_P (arg1) && CONST_INT_P (arg2))
598 : {
599 0 : HOST_WIDE_INT scale = (HOST_WIDE_INT_1U << INTVAL (arg2));
600 0 : offset = scale * fold_offsets_value (insn, arg1, info, single_use);
601 : }
602 : else
603 : return false;
604 :
605 : /* Pattern recognized for folding. */
606 0 : break;
607 : }
608 118112 : case REG:
609 118112 : {
610 : /* Propagate through register move. */
611 118112 : offset = fold_offsets_value (insn, src, info, single_use);
612 :
613 : /* Pattern recognized for folding. */
614 118112 : break;
615 : }
616 6 : case CONST_INT:
617 6 : {
618 6 : offset = INTVAL (src);
619 : /* R1 = C is candidate for folding. */
620 6 : fold_agnostic = false;
621 :
622 : /* Pattern recognized for folding. */
623 6 : break;
624 : }
625 : default:
626 : /* Cannot recognize. */
627 : return false;
628 : }
629 :
630 161843 : if (offset_out)
631 161843 : *offset_out = offset;
632 :
633 161843 : if (fold_agnostic)
634 : {
635 160235 : if (!single_use)
636 141083 : info->fold_agnostic_insns.safe_push (insn);
637 : }
638 1608 : else if (!info->fold_insns.contains (insn))
639 1608 : info->fold_insns.safe_push (insn);
640 :
641 : return true;
642 : }
643 :
644 : /* Returns true when all USEs of DEF (which defines REG) meet certain criteria
645 : to be foldable. Otherwise false. */
646 : static bool
647 1033932 : has_foldable_uses_p (set_info *def, rtx reg)
648 : {
649 : /* We only fold through instructions that are transitively used as
650 : memory addresses and do not have other uses. Use the same logic
651 : from offset calculation to visit instructions that can propagate
652 : offsets and keep track of them in CAN_FOLD_INSNS. */
653 10012724 : for (use_info *use : def->nondebug_insn_uses ())
654 : {
655 4655346 : insn_info *use_insn = use->insn ();
656 4655346 : if (use_insn->is_artificial ())
657 : return false;
658 :
659 : /* Only handle an insn with a simple single set here. */
660 4504083 : rtx_insn *use_rtl = use_insn->rtl ();
661 4504083 : if (!NONJUMP_INSN_P (use_rtl) || GET_CODE (PATTERN (use_rtl)) != SET)
662 : return false;
663 :
664 : /* Special case: A foldable memory store is not foldable if it
665 : mentions DEST outside of the address calculation. */
666 4425888 : rtx use_set = PATTERN (use_rtl);
667 4425888 : if (use_set && MEM_P (SET_DEST (use_set))
668 1628677 : && reg_mentioned_p (reg, SET_SRC (use_set)))
669 : return false;
670 :
671 8738880 : if (use->bb () != def->bb ())
672 : return false;
673 : }
674 :
675 : return true;
676 : }
677 :
678 :
679 : /* Function that calculates the offset for INSN that would have to be added to
680 : all its USEs of REG. Foldable INSNs are added to INFO->fold_insns and
681 : fold-agnostic INSNs are added to INFO->fold_agnostic_insns.
682 : It is possible that some INSNs are added to both lists; when that happens
683 : the INSN is a fold insn.
684 :
685 : On success, returns true and stores the offset in *OFFSET_OUT. On failure,
686 : returns false and sets *OFFSET_OUT to 0. */
687 : static bool
688 29557551 : fold_offsets (insn_info *insn, rtx reg, HOST_WIDE_INT *offset_out,
689 : fold_mem_info *info, bool single_use = true)
690 : {
691 29557551 : *offset_out = 0;
692 :
693 : /* We can only affect the values of GPR registers. */
694 29557551 : unsigned int regno = REGNO (reg);
695 29557551 : if (fixed_regs[regno]
696 29557551 : || !TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], regno))
697 : return false;
698 :
699 : /* Get the DEF for REG in INSN. */
700 12014088 : set_info *def = get_single_def_in_bb (insn, reg, single_use);
701 12014088 : if (!def)
702 : return false;
703 :
704 1033932 : insn_info *def_insn = def->insn ();
705 1033932 : rtx_insn *def_rtl = def_insn->rtl ();
706 :
707 1033932 : if (dump_file && (dump_flags & TDF_DETAILS))
708 : {
709 0 : fprintf (dump_file, "For INSN: ");
710 0 : print_rtl_single (dump_file, insn->rtl ());
711 0 : fprintf (dump_file, "...found DEF: ");
712 0 : print_rtl_single (dump_file, def_rtl);
713 : }
714 :
715 1033932 : gcc_assert (REGNO (reg) == def->regno ());
716 :
717 : /* Check if all USEs of DEF are safe. */
718 1033932 : if (!has_foldable_uses_p (def, reg))
719 : {
720 331900 : if (dump_file && (dump_flags & TDF_DETAILS))
721 : {
722 0 : fprintf (dump_file, "has_foldable_uses_p failed for: ");
723 0 : print_rtl_single (dump_file, def_rtl);
724 : }
725 : return false;
726 : }
727 :
728 : /* Check if we know how to handle DEF. */
729 702032 : HOST_WIDE_INT offset;
730 702032 : if (!fold_offsets_1 (def_insn, &offset, info, single_use))
731 : {
732 540189 : if (dump_file && (dump_flags & TDF_DETAILS))
733 : {
734 0 : fprintf (dump_file, "fold_offsets_1 failed for: ");
735 0 : print_rtl_single (dump_file, def_rtl);
736 : }
737 : return false;
738 : }
739 :
740 161843 : if (dump_file && (dump_flags & TDF_DETAILS))
741 : {
742 0 : fprintf (dump_file, "Instruction marked for propagation: ");
743 0 : print_rtl_single (dump_file, def_rtl);
744 : }
745 :
746 161843 : *offset_out = offset;
747 161843 : return true;
748 : }
749 :
750 : /* Check if any of the provided INSNs in INSN_LIST is not marked in the
751 : given bitmap. Return true if at least one INSN is not in the bitmap and
752 : false otherwise. */
753 : static bool
754 1237 : insn_uses_not_in_bitmap (vec<insn_info *> *insn_list, bitmap bm)
755 : {
756 3644 : for (insn_info *insn : *insn_list)
757 : {
758 1187 : gcc_assert (insn->num_defs () == 1);
759 1187 : set_info *def = dyn_cast<set_info *>(insn->defs ()[0]);
760 4817 : for (use_info *use : def->nondebug_insn_uses ())
761 : {
762 2392 : if (!bitmap_bit_p (bm, use->insn ()->uid ()))
763 : {
764 1154 : if (dump_file && (dump_flags & TDF_DETAILS))
765 : {
766 0 : fprintf (dump_file, "Cannot ensure correct transformation as "
767 : "INSN %u has a USE INSN %u that was not analysed.\n",
768 : insn->uid (), use->insn ()->uid ());
769 : }
770 :
771 1237 : return true;
772 : }
773 : }
774 : }
775 :
776 : return false;
777 : }
778 :
779 : /* Check if all USEs of all instructions have been analysed.
780 : If a fold_mem_info is found that has an unknown USE, then
781 : drop it from the list. When this function returns all
782 : fold_mem_infos in the worklist reference instructions that
783 : have been analysed before and can therefore be committed. */
784 : static void
785 988535 : drop_unsafe_candidates (vec<fold_mem_info *> *worklist)
786 : {
787 989689 : bool changed;
788 1979378 : do
789 : {
790 989689 : changed = false;
791 :
792 : /* First mark all analysed INSNs in a bitmap. */
793 989689 : auto_bitmap insn_closure;
794 2971888 : for (fold_mem_info *info : worklist)
795 : {
796 2821 : bitmap_set_bit (insn_closure, info->insn->uid ());
797 12681 : for (insn_info *insn : info->fold_agnostic_insns)
798 4480 : bitmap_set_bit (insn_closure, insn->uid ());
799 12553 : for (insn_info *insn : info->fold_insns)
800 4090 : bitmap_set_bit (insn_closure, insn->uid ());
801 : }
802 :
803 : /* Now check if all uses of fold_insns are marked. */
804 : unsigned i;
805 : fold_mem_info *info;
806 991296 : FOR_EACH_VEC_ELT (*worklist, i, info)
807 : {
808 1185 : if (insn_uses_not_in_bitmap (&info->fold_agnostic_insns, insn_closure)
809 1185 : || insn_uses_not_in_bitmap (&info->fold_insns, insn_closure))
810 : {
811 1154 : if (dump_file && (dump_flags & TDF_DETAILS))
812 : {
813 0 : fprintf (dump_file,
814 : "Dropping fold-mem-offset root INSN %u.\n",
815 0 : info->insn->uid ());
816 : }
817 :
818 : /* Drop INFO from worklist and restart. */
819 1154 : worklist->unordered_remove (i);
820 2308 : delete info;
821 : changed = true;
822 : break;
823 : }
824 : }
825 989689 : }
826 : while (changed);
827 988535 : }
828 :
829 : /* If INSN is a root memory instruction that was affected by any folding
830 : then update its offset as necessary. */
831 : static rtx
832 50 : do_commit_offset (fold_mem_info *info)
833 : {
834 50 : rtx mem = info->mem;
835 50 : rtx reg = info->reg;
836 50 : HOST_WIDE_INT new_offset = info->offset + info->added_offset;
837 :
838 50 : if (info->added_offset == 0)
839 : return NULL_RTX;
840 :
841 50 : rtx new_mem = copy_rtx (mem);
842 :
843 50 : machine_mode mode = GET_MODE (XEXP (new_mem, 0));
844 50 : if (new_offset != 0)
845 50 : XEXP (new_mem, 0)
846 50 : = gen_rtx_PLUS (mode, reg, gen_int_mode (new_offset, mode));
847 : else
848 0 : XEXP (new_mem, 0) = reg;
849 :
850 50 : rtx new_insn = simplify_replace_rtx (info->insn->rtl (), mem, new_mem);
851 :
852 50 : return new_insn;
853 : }
854 :
855 : /* If INSN is a move / add instruction that was folded then replace its
856 : constant with zero. Append the resulting insn_change to CHANGES for the
857 : caller to commit. */
858 : static rtx_insn *
859 17 : do_commit_insn (insn_info *insn, auto_vec<change_info *> *changes)
860 : {
861 17 : rtx_insn *insn_rtl = insn->rtl ();
862 17 : rtx_insn *new_insn_rtl = as_a<rtx_insn *> (copy_rtx (insn_rtl));
863 :
864 : /* If we deleted this INSNs before, then nothing left to do here. */
865 17 : if (insn_rtl->deleted ())
866 : return NULL;
867 :
868 17 : rtx set = single_set (new_insn_rtl);
869 17 : rtx src = SET_SRC (set);
870 :
871 : /* Emit a move and let subsequent passes eliminate it if possible. */
872 17 : if (CONST_INT_P (src))
873 : {
874 : /* Only change if necessary. */
875 0 : if (INTVAL (src))
876 : {
877 : /* INSN is R1 = C. Set C to 0 because it was folded. */
878 0 : SET_SRC (set) = CONST0_RTX (GET_MODE (SET_SRC (set)));
879 0 : change_info *change = new change_info (
880 0 : new insn_change (insn),
881 0 : num_validated_changes ());
882 0 : changes->safe_push (change);
883 :
884 0 : return new_insn_rtl;
885 : }
886 : }
887 : else
888 : {
889 17 : if (!BINARY_P (src))
890 : return NULL;
891 :
892 7 : rtx sec_src_op = XEXP (src, 1);
893 :
894 : /* Only change if necessary. */
895 7 : if (INTVAL (sec_src_op))
896 : {
897 : /* Mark self-assignments for deletion. */
898 7 : rtx dest = SET_DEST (set);
899 7 : change_info *change = nullptr;
900 7 : if (REGNO (dest) == REGNO (XEXP (src, 0)))
901 0 : change = new change_info (
902 0 : new insn_change (insn, insn_change::DELETE),
903 0 : num_validated_changes ());
904 : else
905 : {
906 : /* If INSN is R1 = R2 + C, C is folded to 0, so emit a mov
907 : instead. */
908 7 : new_insn_rtl = gen_move_insn (SET_DEST (set), XEXP (src, 0));
909 7 : change = new change_info (
910 7 : new insn_change (insn), num_validated_changes ());
911 : }
912 :
913 7 : changes->safe_push (change);
914 7 : return new_insn_rtl;
915 : }
916 : }
917 :
918 : return NULL;
919 : }
920 :
921 : /* Order two insn_change objects by the program order of their insns. */
922 :
923 : static bool
924 63 : sort_changes (insn_change *a, insn_change *b)
925 : {
926 63 : return a->insn ()->compare_with (b->insn ()) < 0;
927 : }
928 :
929 : /* Find and return the last definition of INSN. */
930 :
931 : static def_info *
932 0 : get_last_def (insn_info *insn)
933 : {
934 0 : for (def_info *def : insn->defs ())
935 0 : if (def->insn () == insn)
936 0 : return def;
937 :
938 0 : return NULL;
939 : }
940 :
941 : /* Move uses of DEF to the previous definition. */
942 :
943 : static void
944 0 : move_uses_to_prev_def (def_info *def)
945 : {
946 0 : auto set = dyn_cast<set_info *> (def);
947 0 : while (set->first_use ())
948 : {
949 0 : auto prev_set = dyn_cast<set_info *> (def->prev_def ());
950 : if (!prev_set)
951 : break;
952 0 : crtl->ssa->reparent_use (set->first_use (), prev_set);
953 : }
954 0 : }
955 :
956 : /* Cancel GROUP, lowering MIN_INDEX to CHANGE_INDEX so that cancel_changes
957 : drops everything the group has validated so far. */
958 : static void
959 34 : cancel_changes_for_group (int change_index, bitmap cancelled_groups,
960 : unsigned group, int *min_index)
961 : {
962 1 : if (*min_index == -1 || change_index < *min_index)
963 33 : *min_index = change_index;
964 34 : bitmap_set_bit (cancelled_groups, group);
965 0 : }
966 :
967 : /* Store in GROUPS_TO_CANCEL the groups of CHANGES_MAP that have a change at
968 : or after CANCEL_MIN_INDEX, lowering it to the minimum index of each such
969 : group until reaching a fixed-point. */
970 :
971 : static void
972 33 : find_groups_to_cancel (const changes_map_t &changes_map,
973 : bitmap groups_to_cancel,
974 : int *cancel_min_index)
975 : {
976 33 : bool index_changed;
977 66 : do {
978 33 : index_changed = false;
979 68 : for (const auto &entry : changes_map)
980 : {
981 2 : int min_index = INT_MAX;
982 2 : bool cancelled_group = bitmap_bit_p (groups_to_cancel, entry.first);
983 10 : for (change_info *change : entry.second)
984 : {
985 4 : int change_index = change->change_index;
986 4 : if (change_index < min_index)
987 : min_index = change_index;
988 :
989 4 : if (!cancelled_group && change_index >= *cancel_min_index)
990 : {
991 1 : bitmap_set_bit (groups_to_cancel, entry.first);
992 1 : cancelled_group = true;
993 : }
994 : }
995 :
996 2 : if (cancelled_group && min_index < *cancel_min_index)
997 : {
998 0 : *cancel_min_index = min_index;
999 0 : index_changed = true;
1000 0 : break;
1001 : }
1002 : }
1003 : }
1004 : while (index_changed);
1005 33 : }
1006 :
1007 : /* Free all change_info objects (and their inner insn_change) owned by
1008 : CHANGES_INFO. Used on early returns in update_insns before ownership
1009 : is transferred to changes_map. */
1010 :
1011 : static void
1012 34 : free_changes_info (auto_vec<change_info *> &changes_info)
1013 : {
1014 136 : for (change_info *ci : changes_info)
1015 : {
1016 34 : delete ci->change;
1017 34 : delete ci;
1018 : }
1019 34 : }
1020 :
1021 : /* Update the memory offsets and constants in fold insns based on the analysis
1022 : done in fold_mem_offsets_1. ATTEMPT is the attempt object for the current
1023 : changes, which are recorded in GROUPS. */
1024 : static unsigned int
1025 51 : update_insns (fold_mem_info *info,
1026 : obstack_watermark *attempt,
1027 : fold_groups *groups,
1028 : int *cancel_min_index)
1029 : {
1030 51 : insn_info *insn = info->insn;
1031 51 : unsigned int stats_fold_count = 0;
1032 :
1033 51 : auto_vec<change_info *> changes_info;
1034 :
1035 51 : insn_change *change = new insn_change (insn);
1036 51 : change_info *change_inf = new change_info (change, num_validated_changes ());
1037 51 : int change_index = change_inf->change_index;
1038 51 : changes_info.safe_push (change_inf);
1039 :
1040 51 : if (info->fold_insns.is_empty ())
1041 : {
1042 0 : free_changes_info (changes_info);
1043 0 : return stats_fold_count;
1044 : }
1045 :
1046 51 : unsigned group = groups->add_chain (info->fold_insns);
1047 51 : auto_vec<change_info *> *prev_changes = groups->changes.get (group);
1048 :
1049 : /* Abort if changes for this group have been cancelled before. */
1050 51 : if (bitmap_bit_p (groups->cancelled, group))
1051 : {
1052 1 : cancel_changes_for_group (change_index, groups->cancelled, group,
1053 : cancel_min_index);
1054 1 : free_changes_info (changes_info);
1055 1 : return stats_fold_count;
1056 : }
1057 :
1058 : /* Keep a copy of insn_change elements only. */
1059 100 : auto_vec<insn_change *> changes (changes_info.length ());
1060 200 : for (change_info *ci : changes_info)
1061 50 : changes.quick_push (ci->change);
1062 :
1063 100 : auto ignore = ignore_changing_insns (changes);
1064 50 : if (!rtl_ssa::restrict_movement (*change, ignore))
1065 : {
1066 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1067 0 : fprintf (dump_file, "Restrict movement: Cannot update INSN %u.\n",
1068 : insn->uid ());
1069 0 : cancel_changes_for_group (change_index, groups->cancelled, group,
1070 : cancel_min_index);
1071 0 : free_changes_info (changes_info);
1072 0 : return stats_fold_count;
1073 : }
1074 :
1075 50 : rtx new_insn = do_commit_offset (info);
1076 50 : if (new_insn == NULL_RTX)
1077 : {
1078 0 : free_changes_info (changes_info);
1079 0 : return stats_fold_count;
1080 : }
1081 :
1082 50 : rtx_insn *insn_rtl = info->insn->rtl ();
1083 50 : validate_change (insn_rtl, &PATTERN (insn_rtl), PATTERN (new_insn), 1);
1084 :
1085 : /* Check change validity and new instruction cost. */
1086 50 : if (!recog (*attempt, *change, ignore)
1087 44 : || !changes_are_worthwhile (changes)
1088 111 : || !crtl->ssa->verify_insn_changes (changes))
1089 : {
1090 33 : if (dump_file && (dump_flags & TDF_DETAILS))
1091 0 : fprintf (dump_file, "Recog/verify: Cannot update INSN %u.\n",
1092 : insn->uid ());
1093 33 : cancel_changes_for_group (change_index, groups->cancelled, group,
1094 : cancel_min_index);
1095 33 : free_changes_info (changes_info);
1096 33 : return stats_fold_count;
1097 : }
1098 :
1099 17 : if (dump_file)
1100 0 : fprintf (dump_file, "INSN %u: Memory offset changed from "
1101 : HOST_WIDE_INT_PRINT_DEC " to " HOST_WIDE_INT_PRINT_DEC ".\n",
1102 0 : insn->uid (), info->offset, info->offset + info->added_offset);
1103 :
1104 34 : while (!info->fold_insns.is_empty ())
1105 : {
1106 17 : insn_info *fold_insn = info->fold_insns.pop ();
1107 17 : rtx_insn *fold_insn_rtl = fold_insn->rtl ();
1108 :
1109 17 : rtx_insn *new_fold_insn = do_commit_insn (fold_insn, &changes_info);
1110 17 : if (!new_fold_insn)
1111 10 : continue;
1112 :
1113 7 : change_info *last_change = changes_info.last ();
1114 7 : changes.safe_push (last_change->change);
1115 :
1116 14 : std::sort (changes.begin (), changes.end (), sort_changes);
1117 :
1118 14 : auto ignore = ignore_changing_insns (changes);
1119 7 : if (!rtl_ssa::restrict_movement (*last_change->change, ignore))
1120 : {
1121 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1122 0 : fprintf (dump_file, "Restrict movement: Cannot update INSN %u.\n",
1123 : fold_insn->uid ());
1124 0 : cancel_changes_for_group (change_index, groups->cancelled, group,
1125 : cancel_min_index);
1126 0 : free_changes_info (changes_info);
1127 0 : return 0;
1128 : }
1129 :
1130 14 : if (!changes_are_worthwhile (changes)
1131 14 : || !crtl->ssa->verify_insn_changes (changes))
1132 : {
1133 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1134 0 : fprintf (dump_file, "Verify: Cannot update INSN %u.\n",
1135 : fold_insn->uid ());
1136 0 : cancel_changes_for_group (change_index, groups->cancelled, group,
1137 : cancel_min_index);
1138 0 : free_changes_info (changes_info);
1139 0 : return 0;
1140 : }
1141 :
1142 7 : if (last_change->change->is_deletion ())
1143 : {
1144 : /* Find last instruction's def. */
1145 0 : def_info *insn_def = get_last_def (last_change->change->insn ());
1146 :
1147 : /* Move uses of deleted instruction to the previous def. */
1148 0 : move_uses_to_prev_def (insn_def);
1149 : }
1150 : else
1151 : {
1152 7 : last_change->change_index = num_validated_changes ();
1153 7 : validate_change (fold_insn_rtl, &PATTERN (fold_insn_rtl),
1154 7 : PATTERN (new_fold_insn), 1);
1155 7 : if (!recog (*attempt, *last_change->change, ignore))
1156 : {
1157 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1158 0 : fprintf (dump_file, "Recog: Cannot update INSN %u.\n",
1159 : fold_insn->uid ());
1160 0 : cancel_changes_for_group (change_index, groups->cancelled, group,
1161 : cancel_min_index);
1162 0 : free_changes_info (changes_info);
1163 0 : return 0;
1164 : }
1165 : }
1166 :
1167 7 : if (dump_file)
1168 : {
1169 0 : const int last_change_uid = last_change->change->insn ()->uid ();
1170 0 : if (last_change->change->is_deletion ())
1171 0 : fprintf (dump_file, "INSN %u: Marked for deletion.\n",
1172 : last_change_uid);
1173 : else
1174 0 : fprintf (dump_file, "INSN %u: Constant set to zero.\n",
1175 : last_change_uid);
1176 : }
1177 :
1178 7 : stats_fold_count++;
1179 : }
1180 :
1181 : /* Add new changes to the group. */
1182 17 : if (prev_changes)
1183 : {
1184 40 : for (change_info *change : changes_info)
1185 10 : if (!change_in_vec_p (*prev_changes, *change))
1186 10 : prev_changes->safe_push (change);
1187 : else
1188 : {
1189 0 : delete change->change;
1190 0 : delete change;
1191 : }
1192 : }
1193 : else
1194 35 : for (change_info *change : changes_info)
1195 : {
1196 14 : auto_vec<change_info *> &change_vect
1197 14 : = groups->changes.get_or_insert (group);
1198 :
1199 14 : if (!change_in_vec_p (change_vect, *change))
1200 14 : change_vect.safe_push (change);
1201 : else
1202 : {
1203 0 : delete change->change;
1204 0 : delete change;
1205 : }
1206 : }
1207 :
1208 : return stats_fold_count;
1209 50 : }
1210 :
1211 : /* Helper function for fold_mem_offsets. Fold memory offsets by analysing the
1212 : DEF-USE chain. If SINGLE_USE is true the DEFs will only have a single use,
1213 : otherwise they can have multiple uses. */
1214 : static unsigned int
1215 1977070 : fold_mem_offsets_1 (bool single_use)
1216 : {
1217 1977070 : unsigned int stats_fold_count = 0;
1218 :
1219 : /* This collects the instruction changes into groups of interdependent
1220 : def-chains, so that the change cancellation can be restricted to a single
1221 : group if anything goes wrong. */
1222 1977070 : fold_groups groups;
1223 :
1224 1977070 : auto attempt = crtl->ssa->new_change_attempt ();
1225 1977070 : insn_change_watermark watermark;
1226 :
1227 1977070 : int cancel_min_index = -1;
1228 :
1229 : /* Iterate over all nondebug INSNs get our candidates and fold them. */
1230 1977070 : auto_vec<fold_mem_info *> worklist;
1231 193343382 : for (auto insn : iterate_safely (crtl->ssa->nondebug_insns ()))
1232 : {
1233 191366312 : if (!insn->is_real () || !insn->can_be_optimized ())
1234 191365107 : continue;
1235 :
1236 121507984 : rtx mem, reg;
1237 121507984 : HOST_WIDE_INT offset;
1238 121507984 : if (!get_fold_mem_offset_root (insn, &mem, ®, &offset))
1239 92154486 : continue;
1240 :
1241 29353498 : fold_mem_info *info = new fold_mem_info (insn, mem, reg, offset);
1242 :
1243 29353498 : if (dump_file && (dump_flags & TDF_DETAILS))
1244 : {
1245 0 : fprintf (dump_file, "Starting analysis from root: ");
1246 0 : print_rtl_single (dump_file, info->insn->rtl ());
1247 : }
1248 :
1249 : /* Walk DEF-chain and collect info.fold_insns and the resulting
1250 : offset. */
1251 29353498 : if (!fold_offsets (info->insn, info->reg, &info->added_offset, info,
1252 : single_use)
1253 29353498 : || info->added_offset == 0)
1254 : {
1255 58704586 : delete info;
1256 29352293 : continue;
1257 : }
1258 :
1259 1205 : if (dump_file && (dump_flags & TDF_DETAILS))
1260 0 : fprintf (dump_file,
1261 : "Found root offset delta: " HOST_WIDE_INT_PRINT_DEC "\n",
1262 : info->added_offset);
1263 :
1264 1205 : if (single_use)
1265 : {
1266 20 : stats_fold_count += update_insns (info, &attempt, &groups,
1267 : &cancel_min_index);
1268 40 : delete info;
1269 : }
1270 : else
1271 : /* Append candidate. */
1272 1185 : worklist.safe_push (info);
1273 : }
1274 :
1275 1977070 : if (!single_use)
1276 : {
1277 : /* Now drop all fold_mem_infos, which contain INSNs that have unknown
1278 : USEs and are therefore not safe to change. */
1279 988535 : drop_unsafe_candidates (&worklist);
1280 :
1281 1977101 : while (!worklist.is_empty ())
1282 : {
1283 31 : fold_mem_info *info = worklist.pop ();
1284 31 : stats_fold_count += update_insns (info, &attempt, &groups,
1285 : &cancel_min_index);
1286 62 : delete info;
1287 : }
1288 : }
1289 :
1290 : /* In case that instructions have been cancelled, remove related
1291 : instructions from the map and find the minimum index to use in
1292 : cancel_changes. */
1293 1977070 : if (cancel_min_index != -1)
1294 : {
1295 33 : find_groups_to_cancel (groups.changes, groups.cancelled,
1296 : &cancel_min_index);
1297 :
1298 33 : bitmap_iterator bi;
1299 33 : unsigned int key;
1300 67 : EXECUTE_IF_SET_IN_BITMAP (groups.cancelled, 0, key, bi)
1301 : {
1302 34 : auto_vec<change_info *> *changes = groups.changes.get (key);
1303 34 : if (changes)
1304 : {
1305 5 : for (change_info *change : *changes)
1306 : {
1307 2 : if (dump_file)
1308 0 : fprintf (dump_file, "Change cancelled for insn %u.\n",
1309 0 : change->change->insn ()->uid ());
1310 2 : delete change->change;
1311 2 : delete change;
1312 : }
1313 : }
1314 34 : groups.changes.remove (key);
1315 : }
1316 :
1317 33 : cancel_changes (cancel_min_index);
1318 : }
1319 :
1320 1977070 : if (cancel_min_index != 0)
1321 1977038 : confirm_change_group ();
1322 :
1323 : /* change_insns wants the changes in program order, which also makes the
1324 : result independent of the map's traversal order. */
1325 1977070 : auto_vec<insn_change *> live_changes;
1326 1977076 : for (auto entry : groups.changes)
1327 40 : for (change_info *ci : entry.second)
1328 22 : if (ci->change->insn ()->has_been_deleted ())
1329 0 : delete ci->change;
1330 : else
1331 22 : live_changes.safe_push (ci->change);
1332 :
1333 1977076 : std::sort (live_changes.begin (), live_changes.end (), sort_changes);
1334 3954140 : crtl->ssa->change_insns (live_changes);
1335 :
1336 1977098 : for (insn_change *change : live_changes)
1337 22 : delete change;
1338 :
1339 : /* Free the change_info wrappers for successful (non-cancelled) entries.
1340 : Their inner insn_change has already been deleted above. Cancelled
1341 : entries were removed from the map and freed earlier. */
1342 1977076 : for (auto entry : groups.changes)
1343 40 : for (change_info *ci : entry.second)
1344 22 : delete ci;
1345 :
1346 1977070 : return stats_fold_count;
1347 1977070 : }
1348 :
1349 : /* Main function of fold-mem-offsets pass. */
1350 : static unsigned int
1351 988535 : fold_mem_offsets (function *fn)
1352 : {
1353 988535 : bool multi_use_mode = true;
1354 :
1355 : /* Analysing every USE of a DEF (multi-use mode, below) is expensive on
1356 : flow graphs which have a high connectivity and is unlikely to be
1357 : particularly useful there, so gate it on the edge count.
1358 :
1359 : In normal circumstances a cfg should have about twice as many
1360 : edges as blocks. But we do not want to punish small functions
1361 : which have a couple switch statements. Rather than simply
1362 : threshold the number of blocks, use something with a more
1363 : graceful degradation. */
1364 988535 : if (n_edges_for_fn (fn) > 20000 + n_basic_blocks_for_fn (fn) * 4)
1365 0 : multi_use_mode = false;
1366 :
1367 : /* Initialize RTL SSA. */
1368 988535 : calculate_dominance_info (CDI_DOMINATORS);
1369 988535 : df_analyze ();
1370 988535 : crtl->ssa = new rtl_ssa::function_info (cfun);
1371 :
1372 : /* The number of instructions that were simplified or eliminated. */
1373 988535 : int stats_fold_count = 0;
1374 :
1375 : /* Fold mem offsets with DEFs that have a single USE. */
1376 988535 : stats_fold_count += fold_mem_offsets_1 (true);
1377 :
1378 : /* Fold mem offsets with DEFs that have multiple USEs. This expensive
1379 : analysis is skipped for highly-connected CFGs, unless forced on with
1380 : -fexpensive-optimizations. As the latter is enabled by default at -O2,
1381 : the skip only takes effect under -fno-expensive-optimizations. */
1382 988535 : if (multi_use_mode || flag_expensive_optimizations)
1383 : {
1384 988535 : if (dump_file)
1385 22 : fprintf (dump_file, "Starting multi-use analysis\n");
1386 988535 : stats_fold_count += fold_mem_offsets_1 (false);
1387 : }
1388 : else
1389 0 : warning (OPT_Wdisabled_optimization,
1390 : "fold-mem-offsets: disabling multi-use analysis for %d basic "
1391 : "blocks and %d edges/basic block",
1392 : n_basic_blocks_for_fn (fn),
1393 0 : n_edges_for_fn (fn) / n_basic_blocks_for_fn (fn));
1394 :
1395 988535 : statistics_counter_event (cfun, "Number of folded instructions",
1396 : stats_fold_count);
1397 :
1398 988535 : free_dominance_info (CDI_DOMINATORS);
1399 988535 : if (crtl->ssa->perform_pending_updates ())
1400 0 : cleanup_cfg (0);
1401 :
1402 988535 : delete crtl->ssa;
1403 988535 : crtl->ssa = nullptr;
1404 :
1405 988535 : return 0;
1406 : }
1407 :
1408 : const pass_data pass_data_fold_mem =
1409 : {
1410 : RTL_PASS, /* type */
1411 : "fold_mem_offsets", /* name */
1412 : OPTGROUP_NONE, /* optinfo_flags */
1413 : TV_FOLD_MEM_OFFSETS, /* tv_id */
1414 : 0, /* properties_required */
1415 : 0, /* properties_provided */
1416 : 0, /* properties_destroyed */
1417 : 0, /* todo_flags_start */
1418 : TODO_df_finish, /* todo_flags_finish */
1419 : };
1420 :
1421 : class pass_fold_mem_offsets : public rtl_opt_pass
1422 : {
1423 : public:
1424 294536 : pass_fold_mem_offsets (gcc::context *ctxt)
1425 589072 : : rtl_opt_pass (pass_data_fold_mem, ctxt)
1426 : {}
1427 :
1428 : /* opt_pass methods: */
1429 1515929 : bool gate (function *) final override
1430 : {
1431 1515929 : return flag_fold_mem_offsets && optimize >= 2;
1432 : }
1433 :
1434 988535 : unsigned int execute (function *fn) final override
1435 : {
1436 988535 : return fold_mem_offsets (fn);
1437 : }
1438 : }; // class pass_fold_mem_offsets
1439 :
1440 : } // anon namespace
1441 :
1442 : rtl_opt_pass *
1443 294536 : make_pass_fold_mem_offsets (gcc::context *ctxt)
1444 : {
1445 294536 : return new pass_fold_mem_offsets (ctxt);
1446 : }
|
