Branch data Line data Source code
1 : : /* Late RTL pass to fold memory offsets.
2 : : Copyright (C) 2023-2025 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 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "tm.h"
24 : : #include "rtl.h"
25 : : #include "tree.h"
26 : : #include "expr.h"
27 : : #include "backend.h"
28 : : #include "regs.h"
29 : : #include "target.h"
30 : : #include "memmodel.h"
31 : : #include "emit-rtl.h"
32 : : #include "insn-config.h"
33 : : #include "recog.h"
34 : : #include "predict.h"
35 : : #include "df.h"
36 : : #include "tree-pass.h"
37 : : #include "cfgrtl.h"
38 : : #include "diagnostic-core.h"
39 : :
40 : : /* This pass tries to optimize memory offset calculations by moving constants
41 : : from add instructions to the memory instructions (loads / stores).
42 : : For example it can transform code like this:
43 : :
44 : : add t4, sp, 16
45 : : add t2, a6, t4
46 : : shl t3, t2, 1
47 : : ld a2, 0(t3)
48 : : add a2, 1
49 : : sd a2, 8(t2)
50 : :
51 : : into the following (one instruction less):
52 : :
53 : : add t2, a6, sp
54 : : shl t3, t2, 1
55 : : ld a2, 32(t3)
56 : : add a2, 1
57 : : sd a2, 24(t2)
58 : :
59 : : Although the previous passes try to emit efficient offset calculations
60 : : this pass is still beneficial because:
61 : :
62 : : - The mechanisms that optimize memory offsets usually work with specific
63 : : patterns or have limitations. This pass is designed to fold offsets
64 : : through complex calculations that affect multiple memory operations
65 : : and have partially overlapping calculations.
66 : :
67 : : - There are cases where add instructions are introduced in late rtl passes
68 : : and the rest of the pipeline cannot eliminate them. Arrays and structs
69 : : allocated on the stack can result in unwanted add instructions that
70 : : cannot be eliminated easily.
71 : :
72 : : This pass works on a basic block level and consists of 4 phases:
73 : :
74 : : - Phase 1 (Analysis): Find "foldable" instructions.
75 : : Foldable instructions are those that we know how to propagate
76 : : a constant addition through (add, shift, move, ...) and only have other
77 : : foldable instructions for uses. In that phase a DFS traversal on the
78 : : definition tree is performed and foldable instructions are marked on
79 : : a bitmap. The add immediate instructions that are reachable in this
80 : : DFS are candidates for folding since all the intermediate calculations
81 : : affected by them are also foldable.
82 : :
83 : : - Phase 2 (Validity): Traverse and calculate the offsets that would result
84 : : from folding the add immediate instructions. Check whether the
85 : : calculated offsets result in a valid instruction for the target.
86 : :
87 : : - Phase 3 (Commit offsets): Traverse again. It is now known which folds
88 : : are valid so at this point change the offsets in the memory instructions.
89 : :
90 : : - Phase 4 (Commit instruction deletions): Scan all instructions and delete
91 : : or simplify (reduce to move) all add immediate instructions that were
92 : : folded.
93 : :
94 : : This pass should run before hard register propagation because it creates
95 : : register moves that we expect to be eliminated. */
96 : :
97 : : namespace {
98 : :
99 : : const pass_data pass_data_fold_mem =
100 : : {
101 : : RTL_PASS, /* type */
102 : : "fold_mem_offsets", /* name */
103 : : OPTGROUP_NONE, /* optinfo_flags */
104 : : TV_FOLD_MEM_OFFSETS, /* tv_id */
105 : : 0, /* properties_required */
106 : : 0, /* properties_provided */
107 : : 0, /* properties_destroyed */
108 : : 0, /* todo_flags_start */
109 : : TODO_df_finish, /* todo_flags_finish */
110 : : };
111 : :
112 : : class pass_fold_mem_offsets : public rtl_opt_pass
113 : : {
114 : : public:
115 : 282866 : pass_fold_mem_offsets (gcc::context *ctxt)
116 : 565732 : : rtl_opt_pass (pass_data_fold_mem, ctxt)
117 : : {}
118 : :
119 : : /* opt_pass methods: */
120 : 1431630 : virtual bool gate (function *)
121 : : {
122 : 1431630 : return flag_fold_mem_offsets && optimize >= 2;
123 : : }
124 : :
125 : : virtual unsigned int execute (function *);
126 : : }; // class pass_fold_mem_offsets
127 : :
128 : : /* Class that holds in FOLD_INSNS the instructions that if folded the offset
129 : : of a memory instruction would increase by ADDED_OFFSET. */
130 : 11773256 : class fold_mem_info {
131 : : public:
132 : : auto_bitmap fold_insns;
133 : : HOST_WIDE_INT added_offset;
134 : : };
135 : :
136 : : typedef hash_map<rtx_insn *, fold_mem_info *> fold_info_map;
137 : :
138 : : /* Tracks which instructions can be reached through instructions that can
139 : : propagate offsets for folding. */
140 : : static bitmap_head can_fold_insns;
141 : :
142 : : /* Marks instructions that are currently eligible for folding. */
143 : : static bitmap_head candidate_fold_insns;
144 : :
145 : : /* Tracks instructions that cannot be folded because it turned out that
146 : : folding will result in creating an invalid memory instruction.
147 : : An instruction can be in both CANDIDATE_FOLD_INSNS and CANNOT_FOLD_INSNS
148 : : at the same time, in which case it is not legal to fold. */
149 : : static bitmap_head cannot_fold_insns;
150 : :
151 : : /* The number of instructions that were simplified or eliminated. */
152 : : static int stats_fold_count;
153 : :
154 : : /* Get the single reaching definition of an instruction inside a BB.
155 : : The definition is desired for REG used in INSN.
156 : : Return the definition insn or NULL if there's no definition with
157 : : the desired criteria. */
158 : : static rtx_insn *
159 : 23649950 : get_single_def_in_bb (rtx_insn *insn, rtx reg)
160 : : {
161 : 23649950 : df_ref use;
162 : 23649950 : struct df_link *ref_chain, *ref_link;
163 : :
164 : 28429628 : FOR_EACH_INSN_USE (use, insn)
165 : : {
166 : 28429628 : if (GET_CODE (DF_REF_REG (use)) == SUBREG)
167 : : return NULL;
168 : 28429628 : if (REGNO (DF_REF_REG (use)) == REGNO (reg))
169 : : break;
170 : : }
171 : :
172 : 23649950 : if (!use)
173 : : return NULL;
174 : :
175 : 23649950 : ref_chain = DF_REF_CHAIN (use);
176 : :
177 : 23649950 : if (!ref_chain)
178 : : return NULL;
179 : :
180 : 52788598 : for (ref_link = ref_chain; ref_link; ref_link = ref_link->next)
181 : : {
182 : : /* Problem getting some definition for this instruction. */
183 : 30106115 : if (ref_link->ref == NULL)
184 : : return NULL;
185 : 30106115 : if (DF_REF_INSN_INFO (ref_link->ref) == NULL)
186 : : return NULL;
187 : 29138852 : if (global_regs[REGNO (reg)]
188 : 29138852 : && !set_of (reg, DF_REF_INSN (ref_link->ref)))
189 : : return NULL;
190 : : }
191 : :
192 : 22682483 : if (ref_chain->next)
193 : : return NULL;
194 : :
195 : 19951323 : rtx_insn *def = DF_REF_INSN (ref_chain->ref);
196 : :
197 : 19951323 : if (BLOCK_FOR_INSN (def) != BLOCK_FOR_INSN (insn))
198 : : return NULL;
199 : :
200 : 8043475 : if (DF_INSN_LUID (def) > DF_INSN_LUID (insn))
201 : : return NULL;
202 : :
203 : : return def;
204 : : }
205 : :
206 : : /* Get all uses of REG which is set in INSN. Return the use list or NULL if a
207 : : use is missing / irregular. If SUCCESS is not NULL then set it to false if
208 : : there are missing / irregular uses and true otherwise. */
209 : : static df_link *
210 : 264913 : get_uses (rtx_insn *insn, rtx reg, bool *success)
211 : : {
212 : 264913 : df_ref def;
213 : :
214 : 264913 : if (success)
215 : 264913 : *success = false;
216 : :
217 : 264913 : FOR_EACH_INSN_DEF (def, insn)
218 : 264913 : if (REGNO (DF_REF_REG (def)) == REGNO (reg))
219 : : break;
220 : :
221 : 264913 : if (!def)
222 : : return NULL;
223 : :
224 : 264913 : df_link *ref_chain = DF_REF_CHAIN (def);
225 : 264913 : int insn_luid = DF_INSN_LUID (insn);
226 : 264913 : basic_block insn_bb = BLOCK_FOR_INSN (insn);
227 : :
228 : 1719766 : for (df_link *ref_link = ref_chain; ref_link; ref_link = ref_link->next)
229 : : {
230 : : /* Problem getting a use for this instruction. */
231 : 1615187 : if (ref_link->ref == NULL)
232 : : return NULL;
233 : 1615187 : if (DF_REF_CLASS (ref_link->ref) != DF_REF_REGULAR)
234 : : return NULL;
235 : :
236 : 1610651 : rtx_insn *use = DF_REF_INSN (ref_link->ref);
237 : 1610651 : if (DEBUG_INSN_P (use))
238 : 233193 : continue;
239 : :
240 : : /* We do not handle REG_EQUIV/REG_EQ notes for now. */
241 : 1377458 : if (DF_REF_FLAGS (ref_link->ref) & DF_REF_IN_NOTE)
242 : : return NULL;
243 : 1325590 : if (BLOCK_FOR_INSN (use) != insn_bb)
244 : : return NULL;
245 : : /* Punt if use appears before def in the basic block. See PR111601. */
246 : 1221686 : if (DF_INSN_LUID (use) < insn_luid)
247 : : return NULL;
248 : : }
249 : :
250 : 104579 : if (success)
251 : 104579 : *success = true;
252 : :
253 : : return ref_chain;
254 : : }
255 : :
256 : : static HOST_WIDE_INT
257 : : fold_offsets (rtx_insn *insn, rtx reg, bool analyze, bitmap foldable_insns);
258 : :
259 : : /* Helper function for fold_offsets.
260 : :
261 : : If DO_RECURSION is false and ANALYZE is true this function returns true iff
262 : : it understands the structure of INSN and knows how to propagate constants
263 : : through it. In this case OFFSET_OUT and FOLDABLE_INSNS are unused.
264 : :
265 : : If DO_RECURSION is true then it also calls fold_offsets for each recognized
266 : : part of INSN with the appropriate arguments.
267 : :
268 : : If DO_RECURSION is true and ANALYZE is false then offset that would result
269 : : from folding is computed and is returned through the pointer OFFSET_OUT.
270 : : The instructions that can be folded are recorded in FOLDABLE_INSNS. */
271 : : static bool
272 : 1741913 : fold_offsets_1 (rtx_insn *insn, bool analyze, bool do_recursion,
273 : : HOST_WIDE_INT *offset_out, bitmap foldable_insns)
274 : : {
275 : : /* Doesn't make sense if both DO_RECURSION and ANALYZE are false. */
276 : 1741913 : gcc_checking_assert (do_recursion || analyze);
277 : 1741913 : gcc_checking_assert (GET_CODE (PATTERN (insn)) == SET);
278 : :
279 : 1741913 : rtx src = SET_SRC (PATTERN (insn));
280 : 1741913 : HOST_WIDE_INT offset = 0;
281 : :
282 : 1741913 : switch (GET_CODE (src))
283 : : {
284 : 81974 : case PLUS:
285 : 81974 : {
286 : : /* Propagate through add. */
287 : 81974 : rtx arg1 = XEXP (src, 0);
288 : 81974 : rtx arg2 = XEXP (src, 1);
289 : :
290 : 81974 : if (REG_P (arg1))
291 : : {
292 : 23739 : if (do_recursion)
293 : 3258 : offset += fold_offsets (insn, arg1, analyze, foldable_insns);
294 : : }
295 : 58235 : else if (GET_CODE (arg1) == ASHIFT
296 : 45833 : && REG_P (XEXP (arg1, 0))
297 : 45833 : && CONST_INT_P (XEXP (arg1, 1)))
298 : : {
299 : : /* Handle R1 = (R2 << C) + ... */
300 : 45833 : if (do_recursion)
301 : : {
302 : 15263 : HOST_WIDE_INT scale
303 : 15263 : = (HOST_WIDE_INT_1U << INTVAL (XEXP (arg1, 1)));
304 : 15263 : offset += scale * fold_offsets (insn, XEXP (arg1, 0), analyze,
305 : : foldable_insns);
306 : : }
307 : : }
308 : 12402 : else if (GET_CODE (arg1) == PLUS
309 : 12344 : && REG_P (XEXP (arg1, 0))
310 : 10739 : && REG_P (XEXP (arg1, 1)))
311 : : {
312 : : /* Handle R1 = (R2 + R3) + ... */
313 : 10739 : if (do_recursion)
314 : : {
315 : 4499 : offset += fold_offsets (insn, XEXP (arg1, 0), analyze,
316 : : foldable_insns);
317 : 4499 : offset += fold_offsets (insn, XEXP (arg1, 1), analyze,
318 : : foldable_insns);
319 : : }
320 : : }
321 : 1663 : else if (GET_CODE (arg1) == PLUS
322 : 1605 : && GET_CODE (XEXP (arg1, 0)) == ASHIFT
323 : 1601 : && REG_P (XEXP (XEXP (arg1, 0), 0))
324 : 1601 : && CONST_INT_P (XEXP (XEXP (arg1, 0), 1))
325 : 1601 : && REG_P (XEXP (arg1, 1)))
326 : : {
327 : : /* Handle R1 = ((R2 << C) + R3) + ... */
328 : 1601 : if (do_recursion)
329 : : {
330 : 569 : HOST_WIDE_INT scale
331 : 569 : = (HOST_WIDE_INT_1U << INTVAL (XEXP (XEXP (arg1, 0), 1)));
332 : 569 : offset += scale * fold_offsets (insn, XEXP (XEXP (arg1, 0), 0),
333 : : analyze, foldable_insns);
334 : 569 : offset += fold_offsets (insn, XEXP (arg1, 1), analyze,
335 : : foldable_insns);
336 : : }
337 : : }
338 : : else
339 : : return false;
340 : :
341 : 81912 : if (REG_P (arg2))
342 : : {
343 : 56498 : if (do_recursion)
344 : 18129 : offset += fold_offsets (insn, arg2, analyze, foldable_insns);
345 : : }
346 : 25414 : else if (CONST_INT_P (arg2))
347 : : {
348 : 22860 : if (REG_P (arg1))
349 : : {
350 : 11172 : offset += INTVAL (arg2);
351 : : /* This is a R1 = R2 + C instruction, candidate for folding. */
352 : 11172 : if (!analyze)
353 : 326 : bitmap_set_bit (foldable_insns, INSN_UID (insn));
354 : : }
355 : : }
356 : : else
357 : : return false;
358 : :
359 : : /* Pattern recognized for folding. */
360 : : break;
361 : : }
362 : 0 : case MINUS:
363 : 0 : {
364 : : /* Propagate through minus. */
365 : 0 : rtx arg1 = XEXP (src, 0);
366 : 0 : rtx arg2 = XEXP (src, 1);
367 : :
368 : 0 : if (REG_P (arg1))
369 : : {
370 : 0 : if (do_recursion)
371 : 0 : offset += fold_offsets (insn, arg1, analyze, foldable_insns);
372 : : }
373 : : else
374 : : return false;
375 : :
376 : 0 : if (REG_P (arg2))
377 : : {
378 : 0 : if (do_recursion)
379 : 0 : offset -= fold_offsets (insn, arg2, analyze, foldable_insns);
380 : : }
381 : 0 : else if (CONST_INT_P (arg2))
382 : : {
383 : 0 : if (REG_P (arg1))
384 : : {
385 : 0 : offset -= INTVAL (arg2);
386 : : /* This is a R1 = R2 - C instruction, candidate for folding. */
387 : 0 : if (!analyze)
388 : 0 : bitmap_set_bit (foldable_insns, INSN_UID (insn));
389 : : }
390 : : }
391 : : else
392 : : return false;
393 : :
394 : : /* Pattern recognized for folding. */
395 : : break;
396 : : }
397 : 0 : case NEG:
398 : 0 : {
399 : : /* Propagate through negation. */
400 : 0 : rtx arg1 = XEXP (src, 0);
401 : 0 : if (REG_P (arg1))
402 : : {
403 : 0 : if (do_recursion)
404 : 0 : offset = -fold_offsets (insn, arg1, analyze, foldable_insns);
405 : : }
406 : : else
407 : : return false;
408 : :
409 : : /* Pattern recognized for folding. */
410 : : break;
411 : : }
412 : 152 : case MULT:
413 : 152 : {
414 : : /* Propagate through multiply by constant. */
415 : 152 : rtx arg1 = XEXP (src, 0);
416 : 152 : rtx arg2 = XEXP (src, 1);
417 : :
418 : 152 : if (REG_P (arg1) && CONST_INT_P (arg2))
419 : : {
420 : 152 : if (do_recursion)
421 : : {
422 : 9 : HOST_WIDE_INT scale = INTVAL (arg2);
423 : 9 : offset = scale * fold_offsets (insn, arg1, analyze,
424 : : foldable_insns);
425 : : }
426 : : }
427 : : else
428 : : return false;
429 : :
430 : : /* Pattern recognized for folding. */
431 : : break;
432 : : }
433 : 0 : case ASHIFT:
434 : 0 : {
435 : : /* Propagate through shift left by constant. */
436 : 0 : rtx arg1 = XEXP (src, 0);
437 : 0 : rtx arg2 = XEXP (src, 1);
438 : :
439 : 0 : if (REG_P (arg1) && CONST_INT_P (arg2))
440 : : {
441 : 0 : if (do_recursion)
442 : : {
443 : 0 : HOST_WIDE_INT scale = (HOST_WIDE_INT_1U << INTVAL (arg2));
444 : 0 : offset = scale * fold_offsets (insn, arg1, analyze,
445 : : foldable_insns);
446 : : }
447 : : }
448 : : else
449 : : return false;
450 : :
451 : : /* Pattern recognized for folding. */
452 : : break;
453 : : }
454 : 265635 : case REG:
455 : 265635 : {
456 : : /* Propagate through register move. */
457 : 265635 : if (do_recursion)
458 : 56643 : offset = fold_offsets (insn, src, analyze, foldable_insns);
459 : :
460 : : /* Pattern recognized for folding. */
461 : : break;
462 : : }
463 : 22 : case CONST_INT:
464 : 22 : {
465 : 22 : offset = INTVAL (src);
466 : : /* R1 = C is candidate for folding. */
467 : 22 : if (!analyze)
468 : 7 : bitmap_set_bit (foldable_insns, INSN_UID (insn));
469 : :
470 : : /* Pattern recognized for folding. */
471 : : break;
472 : : }
473 : : default:
474 : : /* Cannot recognize. */
475 : : return false;
476 : : }
477 : :
478 : 345167 : if (do_recursion && !analyze)
479 : 50410 : *offset_out = offset;
480 : :
481 : : return true;
482 : : }
483 : :
484 : : /* Function that computes the offset that would have to be added to all uses
485 : : of REG if the instructions marked in FOLDABLE_INSNS were to be eliminated.
486 : :
487 : : If ANALYZE is true then mark in CAN_FOLD_INSNS which instructions
488 : : transitively only affect other instructions found in CAN_FOLD_INSNS.
489 : : If ANALYZE is false then compute the offset required for folding. */
490 : : static HOST_WIDE_INT
491 : 23649950 : fold_offsets (rtx_insn *insn, rtx reg, bool analyze, bitmap foldable_insns)
492 : : {
493 : 23649950 : rtx_insn *def = get_single_def_in_bb (insn, reg);
494 : :
495 : 23649950 : if (!def || RTX_FRAME_RELATED_P (def) || GET_CODE (PATTERN (def)) != SET)
496 : : return 0;
497 : :
498 : 3332202 : rtx dest = SET_DEST (PATTERN (def));
499 : :
500 : 3332202 : if (!REG_P (dest))
501 : : return 0;
502 : :
503 : : /* We can only affect the values of GPR registers. */
504 : 2113762 : unsigned int dest_regno = REGNO (dest);
505 : 2113762 : if (fixed_regs[dest_regno]
506 : 2113762 : || !TEST_HARD_REG_BIT (reg_class_contents[GENERAL_REGS], dest_regno))
507 : : return 0;
508 : :
509 : 2112383 : if (analyze)
510 : : {
511 : : /* Check if we know how to handle DEF. */
512 : 1051258 : if (!fold_offsets_1 (def, true, false, NULL, NULL))
513 : 1021414 : return 0;
514 : :
515 : : /* We only fold through instructions that are transitively used as
516 : : memory addresses and do not have other uses. Use the same logic
517 : : from offset calculation to visit instructions that can propagate
518 : : offsets and keep track of them in CAN_FOLD_INSNS. */
519 : 264913 : bool success;
520 : 264913 : struct df_link *uses = get_uses (def, dest, &success), *ref_link;
521 : :
522 : 264913 : if (!success)
523 : : return 0;
524 : :
525 : 169897 : for (ref_link = uses; ref_link; ref_link = ref_link->next)
526 : : {
527 : 140053 : rtx_insn *use = DF_REF_INSN (ref_link->ref);
528 : :
529 : 140053 : if (DEBUG_INSN_P (use))
530 : 10615 : continue;
531 : :
532 : : /* Punt if the use is anything more complicated than a set
533 : : (clobber, use, etc). */
534 : 129438 : if (!NONJUMP_INSN_P (use) || GET_CODE (PATTERN (use)) != SET)
535 : : return 0;
536 : :
537 : : /* This use affects instructions outside of CAN_FOLD_INSNS. */
538 : 110299 : if (!bitmap_bit_p (&can_fold_insns, INSN_UID (use)))
539 : : return 0;
540 : :
541 : 56126 : rtx use_set = PATTERN (use);
542 : :
543 : : /* Special case: A foldable memory store is not foldable if it
544 : : mentions DEST outside of the address calculation. */
545 : 56126 : if (use_set && MEM_P (SET_DEST (use_set))
546 : 83863 : && reg_mentioned_p (dest, SET_SRC (use_set)))
547 : : return 0;
548 : : }
549 : :
550 : 29844 : bitmap_set_bit (&can_fold_insns, INSN_UID (def));
551 : :
552 : 29844 : if (dump_file && (dump_flags & TDF_DETAILS))
553 : : {
554 : 0 : fprintf (dump_file, "Instruction marked for propagation: ");
555 : 0 : print_rtl_single (dump_file, def);
556 : : }
557 : : }
558 : : else
559 : : {
560 : : /* We cannot propagate through this instruction. */
561 : 1061125 : if (!bitmap_bit_p (&can_fold_insns, INSN_UID (def)))
562 : : return 0;
563 : : }
564 : :
565 : 690655 : HOST_WIDE_INT offset = 0;
566 : 690655 : bool recognized = fold_offsets_1 (def, analyze, true, &offset,
567 : : foldable_insns);
568 : :
569 : 690655 : if (!recognized)
570 : : return 0;
571 : :
572 : 80254 : return offset;
573 : : }
574 : :
575 : : /* Test if INSN is a memory load / store that can have an offset folded to it.
576 : : Return true iff INSN is such an instruction and return through MEM_OUT,
577 : : REG_OUT and OFFSET_OUT the RTX that has a MEM code, the register that is
578 : : used as a base address and the offset accordingly.
579 : : All of the out pointers may be NULL in which case they will be ignored. */
580 : : bool
581 : 228567924 : get_fold_mem_root (rtx_insn *insn, rtx *mem_out, rtx *reg_out,
582 : : HOST_WIDE_INT *offset_out)
583 : : {
584 : 228567924 : rtx set = single_set (insn);
585 : 228567924 : rtx mem = NULL_RTX;
586 : :
587 : 228567924 : if (set != NULL_RTX)
588 : : {
589 : 111593192 : rtx src = SET_SRC (set);
590 : 111593192 : rtx dest = SET_DEST (set);
591 : :
592 : : /* Don't fold when we have unspec / volatile. */
593 : 111593192 : if (GET_CODE (src) == UNSPEC
594 : 111593192 : || GET_CODE (src) == UNSPEC_VOLATILE
595 : 110914192 : || GET_CODE (dest) == UNSPEC
596 : 110914192 : || GET_CODE (dest) == UNSPEC_VOLATILE)
597 : : return false;
598 : :
599 : 110914192 : if (MEM_P (src))
600 : : mem = src;
601 : 83141066 : else if (MEM_P (dest))
602 : : mem = dest;
603 : 53874238 : else if ((GET_CODE (src) == SIGN_EXTEND
604 : 53874238 : || GET_CODE (src) == ZERO_EXTEND)
605 : 1124682 : && MEM_P (XEXP (src, 0)))
606 : : mem = XEXP (src, 0);
607 : : }
608 : :
609 : : if (mem == NULL_RTX)
610 : : return false;
611 : :
612 : 57497598 : rtx mem_addr = XEXP (mem, 0);
613 : 57497598 : rtx reg;
614 : 57497598 : HOST_WIDE_INT offset;
615 : :
616 : 57497598 : if (REG_P (mem_addr))
617 : : {
618 : : reg = mem_addr;
619 : : offset = 0;
620 : : }
621 : 49493078 : else if (GET_CODE (mem_addr) == PLUS
622 : 40495166 : && REG_P (XEXP (mem_addr, 0))
623 : 39627808 : && CONST_INT_P (XEXP (mem_addr, 1)))
624 : : {
625 : 39088504 : reg = XEXP (mem_addr, 0);
626 : 39088504 : offset = INTVAL (XEXP (mem_addr, 1));
627 : : }
628 : : else
629 : : return false;
630 : :
631 : 47093024 : if (mem_out)
632 : 35319768 : *mem_out = mem;
633 : 47093024 : if (reg_out)
634 : 47093024 : *reg_out = reg;
635 : 47093024 : if (offset_out)
636 : 35319768 : *offset_out = offset;
637 : :
638 : : return true;
639 : : }
640 : :
641 : : /* If INSN is a root memory instruction then do a DFS traversal on its
642 : : definitions and find folding candidates. */
643 : : static void
644 : 102510706 : do_analysis (rtx_insn *insn)
645 : : {
646 : 102510706 : rtx reg;
647 : 102510706 : if (!get_fold_mem_root (insn, NULL, ®, NULL))
648 : 90737450 : return;
649 : :
650 : 11773256 : if (dump_file && (dump_flags & TDF_DETAILS))
651 : : {
652 : 0 : fprintf (dump_file, "Starting analysis from root: ");
653 : 0 : print_rtl_single (dump_file, insn);
654 : : }
655 : :
656 : : /* Analyse folding opportunities for this memory instruction. */
657 : 11773256 : bitmap_set_bit (&can_fold_insns, INSN_UID (insn));
658 : 11773256 : fold_offsets (insn, reg, true, NULL);
659 : : }
660 : :
661 : : static void
662 : 102510706 : do_fold_info_calculation (rtx_insn *insn, fold_info_map *fold_info)
663 : : {
664 : 102510706 : rtx mem, reg;
665 : 102510706 : HOST_WIDE_INT cur_offset;
666 : 102510706 : if (!get_fold_mem_root (insn, &mem, ®, &cur_offset))
667 : 90737450 : return;
668 : :
669 : 11773256 : fold_mem_info *info = new fold_mem_info;
670 : 11773256 : info->added_offset = fold_offsets (insn, reg, false, info->fold_insns);
671 : :
672 : 11773256 : fold_info->put (insn, info);
673 : : }
674 : :
675 : : /* If INSN is a root memory instruction then compute a potentially new offset
676 : : for it and test if the resulting instruction is valid. */
677 : : static void
678 : 11773256 : do_check_validity (rtx_insn *insn, fold_mem_info *info)
679 : : {
680 : 11773256 : rtx mem, reg;
681 : 11773256 : HOST_WIDE_INT cur_offset;
682 : 11773256 : if (!get_fold_mem_root (insn, &mem, ®, &cur_offset))
683 : 0 : return;
684 : :
685 : 11773256 : HOST_WIDE_INT new_offset = cur_offset + info->added_offset;
686 : :
687 : : /* Test if it is valid to change MEM's address offset to NEW_OFFSET. */
688 : 11773256 : int icode = INSN_CODE (insn);
689 : 11773256 : INSN_CODE (insn) = -1;
690 : 11773256 : rtx mem_addr = XEXP (mem, 0);
691 : 11773256 : machine_mode mode = GET_MODE (mem_addr);
692 : 11773256 : if (new_offset != 0)
693 : 9772302 : XEXP (mem, 0) = gen_rtx_PLUS (mode, reg, gen_int_mode (new_offset, mode));
694 : : else
695 : 2000954 : XEXP (mem, 0) = reg;
696 : :
697 : 11773256 : bool illegal = insn_invalid_p (insn, false)
698 : 23546506 : || !memory_address_addr_space_p (mode, XEXP (mem, 0),
699 : 11855154 : MEM_ADDR_SPACE (mem));
700 : :
701 : : /* Restore the instruction. */
702 : 11773256 : XEXP (mem, 0) = mem_addr;
703 : 11773256 : INSN_CODE (insn) = icode;
704 : :
705 : 11773256 : if (illegal)
706 : 6 : bitmap_ior_into (&cannot_fold_insns, info->fold_insns);
707 : : else
708 : 11773250 : bitmap_ior_into (&candidate_fold_insns, info->fold_insns);
709 : : }
710 : :
711 : : static bool
712 : 9613728 : compute_validity_closure (fold_info_map *fold_info)
713 : : {
714 : : /* Let's say we have an arbitrary chain of foldable instructions xN = xN + C
715 : : and memory operations rN that use xN as shown below. If folding x1 in r1
716 : : turns out to be invalid for whatever reason then it's also invalid to fold
717 : : any of the other xN into any rN. That means that we need the transitive
718 : : closure of validity to determine whether we can fold a xN instruction.
719 : :
720 : : +--------------+ +-------------------+ +-------------------+
721 : : | r1 = mem[x1] | | r2 = mem[x1 + x2] | | r3 = mem[x2 + x3] | ...
722 : : +--------------+ +-------------------+ +-------------------+
723 : : ^ ^ ^ ^ ^
724 : : | / | / | ...
725 : : | / | / |
726 : : +-------------+ / +-------------+ / +-------------+
727 : : | x1 = x1 + 1 |-----+ | x2 = x2 + 1 |-----+ | x3 = x3 + 1 |--- ...
728 : : +-------------+ +-------------+ +-------------+
729 : : ^ ^ ^
730 : : | | |
731 : : ... ... ...
732 : : */
733 : :
734 : : /* In general three iterations should be enough for most cases, but allow up
735 : : to five when -fexpensive-optimizations is used. */
736 : 9613728 : int max_iters = 3 + 2 * flag_expensive_optimizations;
737 : 9613728 : for (int pass = 0; pass < max_iters; pass++)
738 : : {
739 : 9613728 : bool made_changes = false;
740 : 21386984 : for (fold_info_map::iterator iter = fold_info->begin ();
741 : 33160240 : iter != fold_info->end (); ++iter)
742 : : {
743 : 11773256 : fold_mem_info *info = (*iter).second;
744 : 11773256 : if (bitmap_intersect_p (&cannot_fold_insns, info->fold_insns))
745 : 6 : made_changes |= bitmap_ior_into (&cannot_fold_insns,
746 : : info->fold_insns);
747 : : }
748 : :
749 : 9613728 : if (!made_changes)
750 : : return true;
751 : : }
752 : :
753 : : return false;
754 : : }
755 : :
756 : : /* If INSN is a root memory instruction that was affected by any folding
757 : : then update its offset as necessary. */
758 : : static void
759 : 11773256 : do_commit_offset (rtx_insn *insn, fold_mem_info *info)
760 : : {
761 : 11773256 : rtx mem, reg;
762 : 11773256 : HOST_WIDE_INT cur_offset;
763 : 11773256 : if (!get_fold_mem_root (insn, &mem, ®, &cur_offset))
764 : 11772929 : return;
765 : :
766 : 11773256 : HOST_WIDE_INT new_offset = cur_offset + info->added_offset;
767 : :
768 : 11773256 : if (new_offset == cur_offset)
769 : : return;
770 : :
771 : 333 : gcc_assert (!bitmap_empty_p (info->fold_insns));
772 : :
773 : 333 : if (bitmap_intersect_p (&cannot_fold_insns, info->fold_insns))
774 : : return;
775 : :
776 : 327 : if (dump_file)
777 : : {
778 : 0 : fprintf (dump_file, "Memory offset changed from "
779 : : HOST_WIDE_INT_PRINT_DEC " to " HOST_WIDE_INT_PRINT_DEC
780 : : " for instruction:\n", cur_offset, new_offset);
781 : 0 : print_rtl_single (dump_file, insn);
782 : : }
783 : :
784 : 327 : machine_mode mode = GET_MODE (XEXP (mem, 0));
785 : 327 : if (new_offset != 0)
786 : 327 : XEXP (mem, 0) = gen_rtx_PLUS (mode, reg, gen_int_mode (new_offset, mode));
787 : : else
788 : 0 : XEXP (mem, 0) = reg;
789 : 327 : INSN_CODE (insn) = recog (PATTERN (insn), insn, 0);
790 : 327 : df_insn_rescan (insn);
791 : : }
792 : :
793 : : /* If INSN is a move / add instruction that was folded then replace its
794 : : constant part with zero. */
795 : : static void
796 : 102510773 : do_commit_insn (rtx_insn *insn)
797 : : {
798 : 102510773 : if (bitmap_bit_p (&candidate_fold_insns, INSN_UID (insn))
799 : 102510773 : && !bitmap_bit_p (&cannot_fold_insns, INSN_UID (insn)))
800 : : {
801 : 67 : if (dump_file)
802 : : {
803 : 0 : fprintf (dump_file, "Instruction folded:");
804 : 0 : print_rtl_single (dump_file, insn);
805 : : }
806 : :
807 : 67 : stats_fold_count++;
808 : :
809 : 67 : rtx set = single_set (insn);
810 : 67 : rtx dest = SET_DEST (set);
811 : 67 : rtx src = SET_SRC (set);
812 : :
813 : : /* Emit a move and let subsequent passes eliminate it if possible. */
814 : 67 : if (GET_CODE (src) == CONST_INT)
815 : : {
816 : : /* INSN is R1 = C.
817 : : Replace it with R1 = 0 because C was folded. */
818 : 1 : rtx mov_rtx
819 : 1 : = gen_move_insn (dest, gen_int_mode (0, GET_MODE (dest)));
820 : 1 : df_insn_rescan (emit_insn_after (mov_rtx, insn));
821 : : }
822 : : else
823 : : {
824 : : /* INSN is R1 = R2 + C.
825 : : Replace it with R1 = R2 because C was folded. */
826 : 66 : rtx arg1 = XEXP (src, 0);
827 : :
828 : : /* If the DEST == ARG1 then the move is a no-op. */
829 : 66 : if (REGNO (dest) != REGNO (arg1))
830 : : {
831 : 66 : gcc_checking_assert (GET_MODE (dest) == GET_MODE (arg1));
832 : 66 : rtx mov_rtx = gen_move_insn (dest, arg1);
833 : 66 : df_insn_rescan (emit_insn_after (mov_rtx, insn));
834 : : }
835 : : }
836 : :
837 : : /* Delete the original move / add instruction. */
838 : 67 : delete_insn (insn);
839 : : }
840 : 102510773 : }
841 : :
842 : : unsigned int
843 : 927715 : pass_fold_mem_offsets::execute (function *fn)
844 : : {
845 : : /* Computing UD/DU chains for flow graphs which have a high connectivity
846 : : will take a long time and is unlikely to be particularly useful.
847 : :
848 : : In normal circumstances a cfg should have about twice as many
849 : : edges as blocks. But we do not want to punish small functions
850 : : which have a couple switch statements. Rather than simply
851 : : threshold the number of blocks, uses something with a more
852 : : graceful degradation. */
853 : 927715 : if (n_edges_for_fn (fn) > 20000 + n_basic_blocks_for_fn (fn) * 4)
854 : : {
855 : 0 : warning (OPT_Wdisabled_optimization,
856 : : "fold-mem-offsets: %d basic blocks and %d edges/basic block",
857 : : n_basic_blocks_for_fn (cfun),
858 : 0 : n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
859 : 0 : return 0;
860 : : }
861 : :
862 : 927715 : df_set_flags (DF_EQ_NOTES + DF_RD_PRUNE_DEAD_DEFS + DF_DEFER_INSN_RESCAN);
863 : 927715 : df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
864 : 927715 : df_analyze ();
865 : :
866 : 927715 : bitmap_initialize (&can_fold_insns, NULL);
867 : 927715 : bitmap_initialize (&candidate_fold_insns, NULL);
868 : 927715 : bitmap_initialize (&cannot_fold_insns, NULL);
869 : :
870 : 927715 : stats_fold_count = 0;
871 : :
872 : 927715 : basic_block bb;
873 : 927715 : rtx_insn *insn;
874 : 12821539 : FOR_ALL_BB_FN (bb, fn)
875 : : {
876 : : /* There is a conflict between this pass and RISCV's shorten-memrefs
877 : : pass. For now disable folding if optimizing for size because
878 : : otherwise this cancels the effects of shorten-memrefs. */
879 : 11893824 : if (optimize_bb_for_size_p (bb))
880 : 2280096 : continue;
881 : :
882 : 9613728 : fold_info_map fold_info;
883 : :
884 : 9613728 : bitmap_clear (&can_fold_insns);
885 : 9613728 : bitmap_clear (&candidate_fold_insns);
886 : 9613728 : bitmap_clear (&cannot_fold_insns);
887 : :
888 : 112124434 : FOR_BB_INSNS (bb, insn)
889 : 102510706 : do_analysis (insn);
890 : :
891 : 112124434 : FOR_BB_INSNS (bb, insn)
892 : 102510706 : do_fold_info_calculation (insn, &fold_info);
893 : :
894 : 112124434 : FOR_BB_INSNS (bb, insn)
895 : 102510706 : if (fold_mem_info **info = fold_info.get (insn))
896 : 11773256 : do_check_validity (insn, *info);
897 : :
898 : 9613728 : if (compute_validity_closure (&fold_info))
899 : : {
900 : 112124434 : FOR_BB_INSNS (bb, insn)
901 : 102510706 : if (fold_mem_info **info = fold_info.get (insn))
902 : 11773256 : do_commit_offset (insn, *info);
903 : :
904 : 112124501 : FOR_BB_INSNS (bb, insn)
905 : 102510773 : do_commit_insn (insn);
906 : : }
907 : :
908 : 21386984 : for (fold_info_map::iterator iter = fold_info.begin ();
909 : 42773968 : iter != fold_info.end (); ++iter)
910 : 23546512 : delete (*iter).second;
911 : 9613728 : }
912 : :
913 : 927715 : statistics_counter_event (cfun, "Number of folded instructions",
914 : : stats_fold_count);
915 : :
916 : 927715 : bitmap_release (&can_fold_insns);
917 : 927715 : bitmap_release (&candidate_fold_insns);
918 : 927715 : bitmap_release (&cannot_fold_insns);
919 : :
920 : 927715 : return 0;
921 : : }
922 : :
923 : : } // anon namespace
924 : :
925 : : rtl_opt_pass *
926 : 282866 : make_pass_fold_mem_offsets (gcc::context *ctxt)
927 : : {
928 : 282866 : return new pass_fold_mem_offsets (ctxt);
929 : : }
|
