Branch data Line data Source code
1 : : // Late-stage instruction combination pass.
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 it under
7 : : // the terms of the GNU General Public License as published by the Free
8 : : // Software Foundation; either version 3, or (at your option) any later
9 : : // version.
10 : : //
11 : : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : // 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 : : // The current purpose of this pass is to substitute definitions into
21 : : // all uses, so that the definition can be removed. However, it could
22 : : // be extended to handle other combination-related optimizations in future.
23 : : //
24 : : // The pass can run before or after register allocation. When running
25 : : // before register allocation, it tries to avoid cases that are likely
26 : : // to increase register pressure. For the same reason, it avoids moving
27 : : // instructions around, even if doing so would allow an optimization to
28 : : // succeed. These limitations are removed when running after register
29 : : // allocation.
30 : :
31 : : #define INCLUDE_ALGORITHM
32 : : #define INCLUDE_FUNCTIONAL
33 : : #define INCLUDE_ARRAY
34 : : #include "config.h"
35 : : #include "system.h"
36 : : #include "coretypes.h"
37 : : #include "backend.h"
38 : : #include "rtl.h"
39 : : #include "df.h"
40 : : #include "rtl-ssa.h"
41 : : #include "print-rtl.h"
42 : : #include "tree-pass.h"
43 : : #include "cfgcleanup.h"
44 : : #include "target.h"
45 : : #include "dbgcnt.h"
46 : :
47 : : using namespace rtl_ssa;
48 : :
49 : : namespace {
50 : : const pass_data pass_data_late_combine =
51 : : {
52 : : RTL_PASS, // type
53 : : "late_combine", // name
54 : : OPTGROUP_NONE, // optinfo_flags
55 : : TV_LATE_COMBINE, // tv_id
56 : : 0, // properties_required
57 : : 0, // properties_provided
58 : : 0, // properties_destroyed
59 : : 0, // todo_flags_start
60 : : TODO_df_finish, // todo_flags_finish
61 : : };
62 : :
63 : : // Represents an attempt to substitute a single-set definition into all
64 : : // uses of the definition.
65 : : class insn_combination
66 : : {
67 : : public:
68 : : insn_combination (set_info *, rtx, rtx);
69 : : bool run ();
70 : : array_slice<insn_change *const> use_changes () const;
71 : :
72 : : private:
73 : : use_array get_new_uses (use_info *);
74 : : bool substitute_nondebug_use (use_info *);
75 : : bool substitute_nondebug_uses (set_info *);
76 : : bool try_to_preserve_debug_info (insn_change &, use_info *);
77 : : void substitute_debug_use (use_info *);
78 : : bool substitute_note (insn_info *, rtx, bool);
79 : : void substitute_notes (insn_info *, bool);
80 : : void substitute_note_uses (use_info *);
81 : : void substitute_optional_uses (set_info *);
82 : :
83 : : // Represents the state of the function's RTL at the start of this
84 : : // combination attempt.
85 : : insn_change_watermark m_rtl_watermark;
86 : :
87 : : // Represents the rtl-ssa state at the start of this combination attempt.
88 : : obstack_watermark m_attempt;
89 : :
90 : : // The instruction that contains the definition, and that we're trying
91 : : // to delete.
92 : : insn_info *m_def_insn;
93 : :
94 : : // The definition itself.
95 : : set_info *m_def;
96 : :
97 : : // The destination and source of the single set that defines m_def.
98 : : // The destination is known to be a plain REG.
99 : : rtx m_dest;
100 : : rtx m_src;
101 : :
102 : : // Contains the full list of changes that we want to make, in reverse
103 : : // postorder.
104 : : auto_vec<insn_change *> m_nondebug_changes;
105 : : };
106 : :
107 : : // Class that represents one run of the pass.
108 : 5565756 : class late_combine
109 : : {
110 : : public:
111 : : unsigned int execute (function *);
112 : :
113 : : private:
114 : : rtx optimizable_set (insn_info *);
115 : : bool check_register_pressure (insn_info *, rtx);
116 : : bool check_uses (set_info *, rtx);
117 : : bool combine_into_uses (insn_info *, insn_info *);
118 : :
119 : : auto_vec<insn_info *> m_worklist;
120 : : };
121 : :
122 : 20249599 : insn_combination::insn_combination (set_info *def, rtx dest, rtx src)
123 : 20249599 : : m_rtl_watermark (),
124 : 20249599 : m_attempt (crtl->ssa->new_change_attempt ()),
125 : 20249599 : m_def_insn (def->insn ()),
126 : 20249599 : m_def (def),
127 : 20249599 : m_dest (dest),
128 : 20249599 : m_src (src),
129 : 20249599 : m_nondebug_changes ()
130 : : {
131 : 20249599 : }
132 : :
133 : : array_slice<insn_change *const>
134 : 2163241 : insn_combination::use_changes () const
135 : : {
136 : 2163241 : return { m_nondebug_changes.address () + 1,
137 : 2163241 : m_nondebug_changes.length () - 1 };
138 : : }
139 : :
140 : : // USE is a direct or indirect use of m_def. Return the list of uses
141 : : // that would be needed after substituting m_def into the instruction.
142 : : // The returned list is marked as invalid if USE's insn and m_def_insn
143 : : // use different definitions for the same resource (register or memory).
144 : : use_array
145 : 25746569 : insn_combination::get_new_uses (use_info *use)
146 : : {
147 : 25746569 : auto *def = use->def ();
148 : 25746569 : auto *use_insn = use->insn ();
149 : :
150 : 25746569 : use_array new_uses = use_insn->uses ();
151 : 25746569 : new_uses = remove_uses_of_def (m_attempt, new_uses, def);
152 : 25746569 : new_uses = merge_access_arrays (m_attempt, m_def_insn->uses (), new_uses);
153 : 51407899 : if (new_uses.is_valid () && use->ebb () != m_def->ebb ())
154 : 4083209 : new_uses = crtl->ssa->make_uses_available (m_attempt, new_uses, use->bb (),
155 : 4083209 : use_insn->is_debug_insn ());
156 : 25746569 : return new_uses;
157 : : }
158 : :
159 : : // Start the process of trying to replace USE by substitution, given that
160 : : // USE occurs in a non-debug instruction. Check:
161 : : //
162 : : // - that the substitution can be represented in RTL
163 : : //
164 : : // - that each use of a resource (register or memory) within the new
165 : : // instruction has a consistent definition
166 : : //
167 : : // - that the new instruction is a recognized pattern
168 : : //
169 : : // - that the instruction can be placed somewhere that makes all definitions
170 : : // and uses valid, and that permits any new hard-register clobbers added
171 : : // during the recognition process
172 : : //
173 : : // Return true on success.
174 : : bool
175 : 24951033 : insn_combination::substitute_nondebug_use (use_info *use)
176 : : {
177 : 24951033 : insn_info *use_insn = use->insn ();
178 : 24951033 : rtx_insn *use_rtl = use_insn->rtl ();
179 : :
180 : 24951033 : if (dump_file && (dump_flags & TDF_DETAILS))
181 : 0 : dump_insn_slim (dump_file, use->insn ()->rtl ());
182 : :
183 : : // Reject second and subsequent uses if the target does not allow
184 : : // the defining instruction to be copied.
185 : 24951033 : if (targetm.cannot_copy_insn_p
186 : 0 : && m_nondebug_changes.length () >= 2
187 : 24951033 : && targetm.cannot_copy_insn_p (m_def_insn->rtl ()))
188 : : {
189 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
190 : 0 : fprintf (dump_file, "-- The target does not allow multiple"
191 : 0 : " copies of insn %d\n", m_def_insn->uid ());
192 : 0 : return false;
193 : : }
194 : :
195 : : // Check that we can change the instruction pattern. Leave recognition
196 : : // of the result till later.
197 : 24951033 : insn_propagation prop (use_rtl, m_dest, m_src);
198 : 24951033 : if (!prop.apply_to_pattern (&PATTERN (use_rtl))
199 : 24951033 : || prop.num_replacements == 0)
200 : : {
201 : 506583 : if (dump_file && (dump_flags & TDF_DETAILS))
202 : 0 : fprintf (dump_file, "-- RTL substitution failed\n");
203 : 506583 : return false;
204 : : }
205 : :
206 : 24444450 : use_array new_uses = get_new_uses (use);
207 : 24444450 : if (!new_uses.is_valid ())
208 : : {
209 : 1006321 : if (dump_file && (dump_flags & TDF_DETAILS))
210 : 0 : fprintf (dump_file, "-- could not prove that all sources"
211 : : " are available\n");
212 : 1006321 : return false;
213 : : }
214 : :
215 : : // Create a tentative change for the use.
216 : 23438129 : auto *where = XOBNEW (m_attempt, insn_change);
217 : 23438129 : auto *use_change = new (where) insn_change (use_insn);
218 : 23438129 : m_nondebug_changes.safe_push (use_change);
219 : 23438129 : use_change->new_uses = new_uses;
220 : :
221 : 23438129 : struct local_ignore : ignore_nothing
222 : : {
223 : 23438129 : local_ignore (const set_info *def, const insn_info *use_insn)
224 : 23438129 : : m_def (def), m_use_insn (use_insn) {}
225 : :
226 : : // We don't limit the number of insns per optimization, so ignoring all
227 : : // insns for all insns would lead to quadratic complexity. Just ignore
228 : : // the use and definition, which should be enough for most purposes.
229 : : bool
230 : 135514517 : should_ignore_insn (const insn_info *insn)
231 : : {
232 : 135514517 : return insn == m_def->insn () || insn == m_use_insn;
233 : : }
234 : :
235 : : // Ignore the definition that we're removing, and all uses of it.
236 : 46857413 : bool should_ignore_def (const def_info *def) { return def == m_def; }
237 : :
238 : : const set_info *m_def;
239 : : const insn_info *m_use_insn;
240 : : };
241 : :
242 : 23438129 : auto ignore = local_ignore (m_def, use_insn);
243 : :
244 : : // Moving instructions before register allocation could increase
245 : : // register pressure. Only try moving them after RA.
246 : 23438129 : if (reload_completed && can_move_insn_p (use_insn))
247 : 8120948 : use_change->move_range = { use_insn->bb ()->head_insn (),
248 : 8120948 : use_insn->ebb ()->last_bb ()->end_insn () };
249 : 23438129 : if (!restrict_movement (*use_change, ignore))
250 : : {
251 : 745768 : if (dump_file && (dump_flags & TDF_DETAILS))
252 : 0 : fprintf (dump_file, "-- cannot satisfy all definitions and uses"
253 : 0 : " in insn %d\n", INSN_UID (use_insn->rtl ()));
254 : 745768 : return false;
255 : : }
256 : :
257 : 22692361 : if (!recog (m_attempt, *use_change, ignore))
258 : : return false;
259 : :
260 : : return true;
261 : : }
262 : :
263 : : // Apply substitute_nondebug_use to all direct and indirect uses of DEF.
264 : : // There will be at most one level of indirection.
265 : : bool
266 : 20837577 : insn_combination::substitute_nondebug_uses (set_info *def)
267 : : {
268 : 62093408 : for (use_info *use : def->nondebug_insn_uses ())
269 : 28113372 : if (!use->is_live_out_use ()
270 : 25022325 : && !use->only_occurs_in_notes ()
271 : 53064405 : && !substitute_nondebug_use (use))
272 : 18422955 : return false;
273 : :
274 : 5935932 : for (use_info *use : def->phi_uses ())
275 : 587978 : if (!substitute_nondebug_uses (use->phi ()))
276 : 518710 : return false;
277 : :
278 : 2414622 : return true;
279 : : }
280 : :
281 : : // USE_CHANGE.insn () is a debug instruction that uses m_def. Try to
282 : : // substitute the definition into the instruction and try to describe
283 : : // the result in USE_CHANGE. Return true on success. Failure means that
284 : : // the instruction must be reset instead.
285 : : bool
286 : 1260837 : insn_combination::try_to_preserve_debug_info (insn_change &use_change,
287 : : use_info *use)
288 : : {
289 : : // Punt on unsimplified subregs of hard registers. In that case,
290 : : // propagation can succeed and create a wider reg than the one we
291 : : // started with.
292 : 1260837 : if (HARD_REGISTER_NUM_P (use->regno ())
293 : 1260837 : && use->includes_subregs ())
294 : : return false;
295 : :
296 : 1260802 : insn_info *use_insn = use_change.insn ();
297 : 1260802 : rtx_insn *use_rtl = use_insn->rtl ();
298 : :
299 : 1260802 : use_change.new_uses = get_new_uses (use);
300 : 1261351 : if (!use_change.new_uses.is_valid ()
301 : 1256793 : || !restrict_movement (use_change))
302 : 12514 : return false;
303 : :
304 : 1248288 : insn_propagation prop (use_rtl, m_dest, m_src);
305 : 1248288 : return prop.apply_to_pattern (&INSN_VAR_LOCATION_LOC (use_rtl));
306 : : }
307 : :
308 : : // USE_INSN is a debug instruction that uses m_def. Update it to reflect
309 : : // the fact that m_def is going to disappear. Try to preserve the source
310 : : // value if possible, but reset the instruction if not.
311 : : void
312 : 1260837 : insn_combination::substitute_debug_use (use_info *use)
313 : : {
314 : 2521674 : auto *use_insn = use->insn ();
315 : 1260837 : rtx_insn *use_rtl = use_insn->rtl ();
316 : :
317 : 1260837 : auto use_change = insn_change (use_insn);
318 : 1260837 : if (!try_to_preserve_debug_info (use_change, use))
319 : : {
320 : 12632 : use_change.new_uses = {};
321 : 12632 : use_change.move_range = use_change.insn ();
322 : 12632 : INSN_VAR_LOCATION_LOC (use_rtl) = gen_rtx_UNKNOWN_VAR_LOC ();
323 : : }
324 : 1260837 : insn_change *changes[] = { &use_change };
325 : 1260837 : crtl->ssa->change_insns (changes);
326 : 1260837 : }
327 : :
328 : : // NOTE is a reg note of USE_INSN, which previously used m_def. Update
329 : : // the note to reflect the fact that m_def is going to disappear. Return
330 : : // true on success, or false if the note must be deleted.
331 : : //
332 : : // CAN_PROPAGATE is true if m_dest can be replaced with m_use.
333 : : bool
334 : 3575153 : insn_combination::substitute_note (insn_info *use_insn, rtx note,
335 : : bool can_propagate)
336 : : {
337 : 3575153 : if (REG_NOTE_KIND (note) == REG_EQUAL
338 : 3575153 : || REG_NOTE_KIND (note) == REG_EQUIV)
339 : : {
340 : 178309 : insn_propagation prop (use_insn->rtl (), m_dest, m_src);
341 : 178309 : return (prop.apply_to_note (&XEXP (note, 0))
342 : 178309 : && (can_propagate || prop.num_replacements == 0));
343 : : }
344 : : return true;
345 : : }
346 : :
347 : : // Update USE_INSN's notes after deciding to go ahead with the optimization.
348 : : // CAN_PROPAGATE is true if m_dest can be replaced with m_use.
349 : : void
350 : 5692825 : insn_combination::substitute_notes (insn_info *use_insn, bool can_propagate)
351 : : {
352 : 5692825 : rtx_insn *use_rtl = use_insn->rtl ();
353 : 5692825 : rtx *ptr = ®_NOTES (use_rtl);
354 : 9267978 : while (rtx note = *ptr)
355 : : {
356 : 3575153 : if (substitute_note (use_insn, note, can_propagate))
357 : 3573047 : ptr = &XEXP (note, 1);
358 : : else
359 : 2106 : *ptr = XEXP (note, 1);
360 : : }
361 : 5692825 : }
362 : :
363 : : // We've decided to go ahead with the substitution. Update all REG_NOTES
364 : : // involving USE.
365 : : void
366 : 5692825 : insn_combination::substitute_note_uses (use_info *use)
367 : : {
368 : 5692825 : insn_info *use_insn = use->insn ();
369 : :
370 : 5692825 : bool can_propagate = true;
371 : 5692825 : if (use->only_occurs_in_notes ())
372 : : {
373 : : // The only uses are in notes. Try to keep the note if we can,
374 : : // but removing it is better than aborting the optimization.
375 : 41317 : insn_change use_change (use_insn);
376 : 41317 : use_change.new_uses = get_new_uses (use);
377 : 41317 : if (!use_change.new_uses.is_valid ()
378 : 41010 : || !restrict_movement (use_change))
379 : : {
380 : 2096 : use_change.move_range = use_insn;
381 : 2096 : use_change.new_uses = remove_uses_of_def (m_attempt,
382 : : use_insn->uses (),
383 : 2096 : use->def ());
384 : 2096 : can_propagate = false;
385 : : }
386 : 41317 : if (dump_file && (dump_flags & TDF_DETAILS))
387 : : {
388 : 0 : fprintf (dump_file, "%s notes in:\n",
389 : : can_propagate ? "updating" : "removing");
390 : 0 : dump_insn_slim (dump_file, use_insn->rtl ());
391 : : }
392 : 41317 : substitute_notes (use_insn, can_propagate);
393 : 41317 : insn_change *changes[] = { &use_change };
394 : 41317 : crtl->ssa->change_insns (changes);
395 : : }
396 : : else
397 : : // We've already decided to update the insn's pattern and know that m_src
398 : : // will be available at the insn's new location. Now update its notes.
399 : 5651508 : substitute_notes (use_insn, can_propagate);
400 : 5692825 : }
401 : :
402 : : // We've decided to go ahead with the substitution and we've dealt with
403 : : // all uses that occur in the patterns of non-debug insns. Update all
404 : : // other uses for the fact that m_def is about to disappear.
405 : : void
406 : 2190347 : insn_combination::substitute_optional_uses (set_info *def)
407 : : {
408 : 4380694 : if (auto insn_uses = def->all_insn_uses ())
409 : : {
410 : : use_info *use = *insn_uses.begin ();
411 : 10463575 : while (use)
412 : : {
413 : 8308094 : use_info *next_use = use->next_any_insn_use ();
414 : 8308094 : if (use->is_in_debug_insn ())
415 : 1260837 : substitute_debug_use (use);
416 : 7047257 : else if (!use->is_live_out_use ())
417 : 5692825 : substitute_note_uses (use);
418 : : use = next_use;
419 : : }
420 : : }
421 : 4407800 : for (use_info *use : def->phi_uses ())
422 : 27106 : substitute_optional_uses (use->phi ());
423 : 2190347 : }
424 : :
425 : : // Try to perform the substitution. Return true on success.
426 : : bool
427 : 20249599 : insn_combination::run ()
428 : : {
429 : 20249599 : if (dump_file && (dump_flags & TDF_DETAILS))
430 : : {
431 : 0 : fprintf (dump_file, "\ntrying to combine definition of r%d in:\n",
432 : 0 : m_def->regno ());
433 : 0 : dump_insn_slim (dump_file, m_def_insn->rtl ());
434 : 0 : fprintf (dump_file, "into:\n");
435 : : }
436 : :
437 : 20249599 : auto def_change = insn_change::delete_insn (m_def_insn);
438 : 20249599 : m_nondebug_changes.safe_push (&def_change);
439 : :
440 : 20249599 : if (!substitute_nondebug_uses (m_def)
441 : 4690708 : || !changes_are_worthwhile (m_nondebug_changes)
442 : 24587029 : || !crtl->ssa->verify_insn_changes (m_nondebug_changes))
443 : 18086358 : return false;
444 : :
445 : : // We've now decided that the optimization is valid and profitable.
446 : : // Allow it to be suppressed for bisection purposes.
447 : 2163241 : if (!dbg_cnt (::late_combine))
448 : : return false;
449 : :
450 : 2163241 : substitute_optional_uses (m_def);
451 : :
452 : 2163241 : confirm_change_group ();
453 : 4326482 : crtl->ssa->change_insns (m_nondebug_changes);
454 : 2163241 : return true;
455 : : }
456 : :
457 : : // See whether INSN is a single_set that we can optimize. Return the
458 : : // set if so, otherwise return null.
459 : : rtx
460 : 62002809 : late_combine::optimizable_set (insn_info *insn)
461 : : {
462 : 62002809 : if (!insn->can_be_optimized ()
463 : 62002809 : || insn->is_asm ()
464 : 61985913 : || insn->is_call ()
465 : 61253097 : || insn->has_volatile_refs ()
466 : 60587816 : || insn->has_pre_post_modify ()
467 : 122590625 : || !can_move_insn_p (insn))
468 : 9126861 : return NULL_RTX;
469 : :
470 : 52875948 : return single_set (insn->rtl ());
471 : : }
472 : :
473 : : // Suppose that we can replace all uses of SET_DEST (SET) with SET_SRC (SET),
474 : : // where SET occurs in INSN. Return true if doing so is not likely to
475 : : // increase register pressure.
476 : : bool
477 : 25445330 : late_combine::check_register_pressure (insn_info *insn, rtx set)
478 : : {
479 : : // Plain register-to-register moves do not establish a register class
480 : : // preference and have no well-defined effect on the register allocator.
481 : : // If changes in register class are needed, the register allocator is
482 : : // in the best position to place those changes. If no change in
483 : : // register class is needed, then the optimization reduces register
484 : : // pressure if SET_SRC (set) was already live at uses, otherwise the
485 : : // optimization is pressure-neutral.
486 : 25445330 : rtx src = SET_SRC (set);
487 : 25445330 : if (REG_P (src))
488 : : return true;
489 : :
490 : : // On the same basis, substituting a SET_SRC that contains a single
491 : : // pseudo register either reduces pressure or is pressure-neutral,
492 : : // subject to the constraints below. We would need to do more
493 : : // analysis for SET_SRCs that use more than one pseudo register.
494 : 18531341 : unsigned int nregs = 0;
495 : 34248676 : for (auto *use : insn->uses ())
496 : 18813164 : if (use->is_reg ()
497 : 15817022 : && !HARD_REGISTER_NUM_P (use->regno ())
498 : 31255793 : && !use->only_occurs_in_notes ())
499 : 12365126 : if (++nregs > 1)
500 : 6127009 : return false;
501 : :
502 : : // If there are no pseudo registers in SET_SRC then the optimization
503 : : // should improve register pressure.
504 : 15435512 : if (nregs == 0)
505 : : return true;
506 : :
507 : : // We'd be substituting (set (reg R1) SRC) where SRC is known to
508 : : // contain a single pseudo register R2. Assume for simplicity that
509 : : // each new use of R2 would need to be in the same class C as the
510 : : // current use of R2. If, for a realistic allocation, C is a
511 : : // non-strict superset of the R1's register class, the effect on
512 : : // register pressure should be positive or neutral. If instead
513 : : // R1 occupies a different register class from R2, or if R1 has
514 : : // more allocation freedom than R2, then there's a higher risk that
515 : : // the effect on register pressure could be negative.
516 : : //
517 : : // First use constrain_operands to get the most likely choice of
518 : : // alternative. For simplicity, just handle the case where the
519 : : // output operand is operand 0.
520 : 6173468 : extract_insn (insn->rtl ());
521 : 6173468 : rtx dest = SET_DEST (set);
522 : 6173468 : if (recog_data.n_operands == 0
523 : 6173468 : || recog_data.operand[0] != dest)
524 : : return false;
525 : :
526 : 3940208 : if (!constrain_operands (0, get_enabled_alternatives (insn->rtl ())))
527 : : return false;
528 : :
529 : 3940208 : preprocess_constraints (insn->rtl ());
530 : 3940208 : auto *alt = which_op_alt ();
531 : 3940208 : auto dest_class = alt[0].cl;
532 : :
533 : : // Check operands 1 and above.
534 : 10653720 : auto check_src = [&] (unsigned int i)
535 : : {
536 : 6713512 : if (recog_data.is_operator[i])
537 : : return true;
538 : :
539 : 6628193 : rtx op = recog_data.operand[i];
540 : 6628193 : if (CONSTANT_P (op))
541 : : return true;
542 : :
543 : 4044342 : if (SUBREG_P (op))
544 : 553398 : op = SUBREG_REG (op);
545 : 4044342 : if (REG_P (op))
546 : : {
547 : : // Ignore hard registers. We've already rejected uses of non-fixed
548 : : // hard registers in the SET_SRC.
549 : 3533967 : if (HARD_REGISTER_P (op))
550 : : return true;
551 : :
552 : : // Make sure that the source operand's class is at least as
553 : : // permissive as the destination operand's class.
554 : 3532284 : auto src_class = alternative_class (alt, i);
555 : 3532284 : if (dest_class != src_class)
556 : : {
557 : 303093 : auto extra_dest_regs = (reg_class_contents[dest_class]
558 : 303093 : & ~reg_class_contents[src_class]
559 : 303093 : & ~fixed_reg_set);
560 : 606186 : if (!hard_reg_set_empty_p (extra_dest_regs))
561 : 93121 : return false;
562 : : }
563 : :
564 : : // Make sure that the source operand occupies no more hard
565 : : // registers than the destination operand. This mostly matters
566 : : // for subregs.
567 : 6878326 : if (targetm.class_max_nregs (dest_class, GET_MODE (dest))
568 : 3439163 : < targetm.class_max_nregs (src_class, GET_MODE (op)))
569 : : return false;
570 : :
571 : : return true;
572 : : }
573 : : return false;
574 : 3940208 : };
575 : 9860854 : for (int i = 1; i < recog_data.n_operands; ++i)
576 : 6718566 : if (recog_data.operand_type[i] != OP_OUT && !check_src (i))
577 : : return false;
578 : :
579 : : return true;
580 : : }
581 : :
582 : : // Check uses of DEF to see whether there is anything obvious that
583 : : // prevents the substitution of SET into uses of DEF.
584 : : bool
585 : 45878362 : late_combine::check_uses (set_info *def, rtx set)
586 : : {
587 : 45878362 : use_info *prev_use = nullptr;
588 : 186512302 : for (use_info *use : def->nondebug_insn_uses ())
589 : : {
590 : 63739542 : insn_info *use_insn = use->insn ();
591 : :
592 : 63739542 : if (use->is_live_out_use ())
593 : 13265611 : continue;
594 : 50473931 : if (use->only_occurs_in_notes ())
595 : 170309 : continue;
596 : :
597 : : // We cannot replace all uses if the value is live on exit.
598 : 50303622 : if (use->is_artificial ())
599 : 45878362 : return false;
600 : :
601 : : // Avoid increasing the complexity of instructions that
602 : : // reference allocatable hard registers.
603 : 49601716 : if (!REG_P (SET_SRC (set))
604 : 34662687 : && !reload_completed
605 : 62916327 : && (accesses_include_nonfixed_hard_registers (use_insn->uses ())
606 : 10046499 : || accesses_include_nonfixed_hard_registers (use_insn->defs ())))
607 : 4475538 : return false;
608 : :
609 : : // Don't substitute into a non-local goto, since it can then be
610 : : // treated as a jump to local label, e.g. in shorten_branches.
611 : : // ??? But this shouldn't be necessary.
612 : 45126178 : if (use_insn->is_jump ()
613 : 45126178 : && find_reg_note (use_insn->rtl (), REG_NON_LOCAL_GOTO, NULL_RTX))
614 : : return false;
615 : :
616 : : // Reject cases where one of the uses is a function argument.
617 : : // The combine attempt should fail anyway, but this is a common
618 : : // case that is easy to check early.
619 : 45125146 : if (use_insn->is_call ()
620 : 10657446 : && HARD_REGISTER_P (SET_DEST (set))
621 : 55770894 : && find_reg_fusage (use_insn->rtl (), USE, SET_DEST (set)))
622 : : return false;
623 : :
624 : : // We'll keep the uses in their original order, even if we move
625 : : // them relative to other instructions. Make sure that non-final
626 : : // uses do not change any values that occur in the SET_SRC.
627 : 54745195 : if (prev_use && prev_use->ebb () == use->ebb ())
628 : : {
629 : 7694951 : def_info *ultimate_def = look_through_degenerate_phi (def);
630 : 7694951 : if (insn_clobbers_resources (prev_use->insn (),
631 : 7694951 : ultimate_def->insn ()->uses ()))
632 : : return false;
633 : : }
634 : :
635 : : prev_use = use;
636 : : }
637 : :
638 : 60400761 : for (use_info *use : def->phi_uses ())
639 : 9267010 : if (!use->phi ()->is_degenerate ()
640 : 9267010 : || !check_uses (use->phi (), set))
641 : 7899467 : return false;
642 : :
643 : 21617142 : return true;
644 : : }
645 : :
646 : : // Try to remove INSN by substituting a definition into all uses.
647 : : // If the optimization moves any instructions before CURSOR, add those
648 : : // instructions to the end of m_worklist.
649 : : bool
650 : 102242911 : late_combine::combine_into_uses (insn_info *insn, insn_info *cursor)
651 : : {
652 : : // For simplicity, don't try to handle sets of multiple hard registers.
653 : : // And for correctness, don't remove any assignments to the stack or
654 : : // frame pointers, since that would implicitly change the set of valid
655 : : // memory locations between this assignment and the next.
656 : : //
657 : : // Removing assignments to the hard frame pointer would invalidate
658 : : // backtraces.
659 : 102242911 : set_info *def = single_set_info (insn);
660 : 102242911 : if (!def
661 : 79585527 : || !def->is_reg ()
662 : 62474877 : || def->regno () == STACK_POINTER_REGNUM
663 : 62474877 : || def->regno () == FRAME_POINTER_REGNUM
664 : 164717788 : || def->regno () == HARD_FRAME_POINTER_REGNUM)
665 : : return false;
666 : :
667 : 62002809 : rtx set = optimizable_set (insn);
668 : 62002809 : if (!set)
669 : : return false;
670 : :
671 : : // For simplicity, don't try to handle subreg destinations.
672 : 52872374 : rtx dest = SET_DEST (set);
673 : 52872374 : if (!REG_P (dest) || def->regno () != REGNO (dest))
674 : : return false;
675 : :
676 : : // Don't prolong the live ranges of allocatable hard registers, or put
677 : : // them into more complicated instructions. Failing to prevent this
678 : : // could lead to spill failures, or at least to worst register allocation.
679 : 52603696 : if (!reload_completed
680 : 52603696 : && accesses_include_nonfixed_hard_registers (insn->uses ()))
681 : 2735292 : return false;
682 : :
683 : 49868404 : if (!reload_completed && !check_register_pressure (insn, set))
684 : : return false;
685 : :
686 : 43741395 : if (!check_uses (def, set))
687 : : return false;
688 : :
689 : 20249599 : insn_combination combination (def, SET_DEST (set), SET_SRC (set));
690 : 20249599 : if (!combination.run ())
691 : : return false;
692 : :
693 : 2163241 : for (auto *use_change : combination.use_changes ())
694 : 2128285 : if (*use_change->insn () < *cursor)
695 : 0 : m_worklist.safe_push (use_change->insn ());
696 : : else
697 : : break;
698 : 2163241 : return true;
699 : 20249599 : }
700 : :
701 : : // Run the pass on function FN.
702 : : unsigned int
703 : 1855252 : late_combine::execute (function *fn)
704 : : {
705 : : // Initialization.
706 : 1855252 : calculate_dominance_info (CDI_DOMINATORS);
707 : 1855252 : df_analyze ();
708 : 1855252 : crtl->ssa = new rtl_ssa::function_info (fn);
709 : : // Don't allow memory_operand to match volatile MEMs.
710 : 1855252 : init_recog_no_volatile ();
711 : :
712 : 1855252 : insn_info *insn = *crtl->ssa->nondebug_insns ().begin ();
713 : 162840854 : while (insn)
714 : : {
715 : 160985602 : if (!insn->is_artificial ())
716 : : {
717 : 102242911 : insn_info *prev = insn->prev_nondebug_insn ();
718 : 102242911 : if (combine_into_uses (insn, prev))
719 : : {
720 : : // Any instructions that get added to the worklist were
721 : : // previously after PREV. Thus if we were able to move
722 : : // an instruction X before PREV during one combination,
723 : : // X cannot depend on any instructions that we move before
724 : : // PREV during subsequent combinations. This means that
725 : : // the worklist should be free of backwards dependencies,
726 : : // even if it isn't necessarily in RPO.
727 : 2163241 : for (unsigned int i = 0; i < m_worklist.length (); ++i)
728 : 0 : combine_into_uses (m_worklist[i], prev);
729 : 2163241 : m_worklist.truncate (0);
730 : 2163241 : insn = prev;
731 : : }
732 : : }
733 : 160985602 : insn = insn->next_nondebug_insn ();
734 : : }
735 : :
736 : : // Finalization.
737 : 1855252 : if (crtl->ssa->perform_pending_updates ())
738 : 510 : cleanup_cfg (0);
739 : :
740 : 1855252 : delete crtl->ssa;
741 : 1855252 : crtl->ssa = nullptr;
742 : :
743 : : // Make the recognizer allow volatile MEMs again.
744 : 1855252 : init_recog ();
745 : 1855252 : free_dominance_info (CDI_DOMINATORS);
746 : 1855252 : return 0;
747 : : }
748 : :
749 : : class pass_late_combine : public rtl_opt_pass
750 : : {
751 : : public:
752 : 565732 : pass_late_combine (gcc::context *ctxt)
753 : 1131464 : : rtl_opt_pass (pass_data_late_combine, ctxt)
754 : : {}
755 : :
756 : : // opt_pass methods:
757 : 282866 : opt_pass *clone () override { return new pass_late_combine (m_ctxt); }
758 : : bool gate (function *) override;
759 : : unsigned int execute (function *) override;
760 : : };
761 : :
762 : : bool
763 : 2863260 : pass_late_combine::gate (function *)
764 : : {
765 : 2863260 : return optimize > 0 && flag_late_combine_instructions;
766 : : }
767 : :
768 : : unsigned int
769 : 1855252 : pass_late_combine::execute (function *fn)
770 : : {
771 : 1855252 : return late_combine ().execute (fn);
772 : : }
773 : :
774 : : } // end namespace
775 : :
776 : : // Create a new CC fusion pass instance.
777 : :
778 : : rtl_opt_pass *
779 : 282866 : make_pass_late_combine (gcc::context *ctxt)
780 : : {
781 : 282866 : return new pass_late_combine (ctxt);
782 : : }
|
