Line data Source code
1 : /* Web construction code for GNU compiler.
2 : Contributed by Jan Hubicka.
3 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : /* Simple optimization pass that splits independent uses of each pseudo,
22 : increasing effectiveness of other optimizations. The optimization can
23 : serve as an example of use for the dataflow module.
24 :
25 : TODO
26 : - We may use profile information and ignore infrequent use for the
27 : purpose of web unifying, inserting the compensation code later to
28 : implement full induction variable expansion for loops (currently
29 : we expand only if the induction variable is dead afterward, which
30 : is often the case). */
31 :
32 : #include "config.h"
33 : #include "system.h"
34 : #include "coretypes.h"
35 : #include "backend.h"
36 : #include "rtl.h"
37 : #include "df.h"
38 : #include "insn-config.h"
39 : #include "recog.h"
40 :
41 : #include "tree-pass.h"
42 :
43 :
44 : /* Find the root of unionfind tree (the representative of set). */
45 :
46 : web_entry_base *
47 15086471 : web_entry_base::unionfind_root ()
48 : {
49 15086471 : web_entry_base *element = this, *element1 = this, *element2;
50 :
51 26844118 : while (element->pred ())
52 : element = element->pred ();
53 26844118 : while (element1->pred ())
54 : {
55 11757647 : element2 = element1->pred ();
56 11757647 : element1->set_pred (element);
57 11757647 : element1 = element2;
58 : }
59 15086471 : return element;
60 : }
61 :
62 : /* Union sets.
63 : Return true if FIRST and SECOND points to the same web entry structure and
64 : nothing is done. Otherwise, return false. */
65 :
66 : bool
67 4834441 : unionfind_union (web_entry_base *first, web_entry_base *second)
68 : {
69 4834441 : first = first->unionfind_root ();
70 4834441 : second = second->unionfind_root ();
71 4834441 : if (first == second)
72 : return true;
73 3901659 : second->set_pred (first);
74 3901659 : return false;
75 : }
76 :
77 : struct web_entry : public web_entry_base
78 : {
79 : private:
80 : rtx reg_pvt;
81 :
82 : public:
83 5417589 : rtx reg () { return reg_pvt; }
84 1515930 : void set_reg (rtx r) { reg_pvt = r; }
85 : };
86 :
87 : /* For INSN, union all defs and uses that are linked by match_dup.
88 : FUN is the function that does the union. */
89 :
90 : static void
91 3560475 : union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
92 : bool (*fun) (web_entry_base *, web_entry_base *))
93 : {
94 3560475 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
95 3560475 : df_ref use_link = DF_INSN_INFO_USES (insn_info);
96 3560475 : df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
97 3560475 : struct web_entry *dup_entry;
98 3560475 : int i;
99 :
100 3560475 : extract_insn (insn);
101 :
102 3605987 : for (i = 0; i < recog_data.n_dups; i++)
103 : {
104 45512 : int op = recog_data.dup_num[i];
105 45512 : enum op_type type = recog_data.operand_type[op];
106 45512 : df_ref ref, dupref;
107 45512 : struct web_entry *entry;
108 :
109 45512 : dup_entry = use_entry;
110 121404 : for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
111 105546 : if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
112 : break;
113 :
114 45512 : if (dupref == NULL && type == OP_INOUT)
115 : {
116 11809 : dup_entry = def_entry;
117 11809 : for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
118 7025 : if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
119 : break;
120 : }
121 : /* ??? *DUPREF can still be zero, because when an operand matches
122 : a memory, DF_REF_LOC (use_link[n]) points to the register part
123 : of the address, whereas recog_data.dup_loc[m] points to the
124 : entire memory ref, thus we fail to find the duplicate entry,
125 : even though it is there.
126 : Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
127 : -O3 -fomit-frame-pointer -funroll-loops */
128 45512 : if (dupref == NULL
129 29663 : || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
130 16460 : continue;
131 :
132 29052 : ref = type == OP_IN ? use_link : def_link;
133 29052 : entry = type == OP_IN ? use_entry : def_entry;
134 65054 : for (; ref; ref = DF_REF_NEXT_LOC (ref))
135 : {
136 65045 : rtx *l = DF_REF_LOC (ref);
137 65045 : if (l == recog_data.operand_loc[op])
138 : break;
139 36002 : if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
140 : break;
141 : }
142 :
143 29052 : if (!ref && type == OP_INOUT)
144 : {
145 9 : entry = use_entry;
146 9 : for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
147 : {
148 9 : rtx *l = DF_REF_LOC (ref);
149 9 : if (l == recog_data.operand_loc[op])
150 : break;
151 0 : if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
152 : break;
153 : }
154 : }
155 :
156 29052 : gcc_assert (ref);
157 29052 : (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
158 : }
159 3560475 : }
160 :
161 : /* For each use, all possible defs reaching it must come in the same
162 : register, union them.
163 : FUN is the function that does the union.
164 :
165 : In USED, we keep the DF_REF_ID of the first uninitialized uses of a
166 : register, so that all uninitialized uses of the register can be
167 : combined into a single web. We actually offset it by 2, because
168 : the values 0 and 1 are reserved for use by entry_register. */
169 :
170 : void
171 3600410 : union_defs (df_ref use, web_entry *def_entry,
172 : unsigned int *used, web_entry *use_entry,
173 : bool (*fun) (web_entry_base *, web_entry_base *))
174 : {
175 3600410 : struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
176 3600410 : struct df_link *link = DF_REF_CHAIN (use);
177 3600410 : rtx set;
178 :
179 3600410 : if (insn_info)
180 : {
181 3600410 : df_ref eq_use;
182 :
183 3600410 : set = single_set (insn_info->insn);
184 3808917 : FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
185 208507 : if (use != eq_use
186 162935 : && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
187 34161 : (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
188 : }
189 : else
190 : set = NULL;
191 :
192 : /* Union all occurrences of the same register in reg notes. */
193 :
194 : /* Recognize trivial noop moves and attempt to keep them as noop. */
195 :
196 3600410 : if (set
197 3580284 : && SET_SRC (set) == DF_REF_REG (use)
198 567909 : && SET_SRC (set) == SET_DEST (set))
199 : {
200 0 : df_ref def;
201 :
202 0 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
203 0 : if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
204 0 : (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
205 : }
206 :
207 : /* UD chains of uninitialized REGs are empty. Keeping all uses of
208 : the same uninitialized REG in a single web is not necessary for
209 : correctness, since the uses are undefined, but it's wasteful to
210 : allocate one register or slot for each reference. Furthermore,
211 : creating new pseudos for uninitialized references in debug insns
212 : (see PR 42631) causes -fcompare-debug failures. We record the
213 : number of the first uninitialized reference we found, and merge
214 : with it any other uninitialized references to the same
215 : register. */
216 3600410 : if (!link)
217 : {
218 14231 : int regno = REGNO (DF_REF_REAL_REG (use));
219 14231 : if (used[regno])
220 9140 : (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
221 : else
222 5091 : used[regno] = DF_REF_ID (use) + 2;
223 : }
224 :
225 8360198 : while (link)
226 : {
227 4759788 : (*fun) (use_entry + DF_REF_ID (use),
228 4759788 : def_entry + DF_REF_ID (link->ref));
229 4759788 : link = link->next;
230 : }
231 :
232 : /* A READ_WRITE use requires the corresponding def to be in the same
233 : register. Find it and union. */
234 3600410 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
235 2300 : if (insn_info)
236 : {
237 2300 : df_ref def;
238 :
239 4600 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
240 2300 : if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
241 2300 : (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
242 : }
243 3600410 : }
244 :
245 : /* Find the corresponding register for the given entry. */
246 :
247 : static rtx
248 5417589 : entry_register (web_entry *entry, df_ref ref, unsigned int *used)
249 : {
250 5417589 : web_entry *root;
251 5417589 : rtx reg, newreg;
252 :
253 : /* Find the corresponding web and see if it has been visited. */
254 5417589 : root = (web_entry *)entry->unionfind_root ();
255 5417589 : if (root->reg ())
256 : return root->reg ();
257 :
258 : /* We are seeing this web for the first time, do the assignment. */
259 1515930 : reg = DF_REF_REAL_REG (ref);
260 :
261 : /* In case the original register is already assigned, generate new
262 : one. Since we use USED to merge uninitialized refs into a single
263 : web, we might found an element to be nonzero without our having
264 : used it. Test for 1, because union_defs saves it for our use,
265 : and there won't be any use for the other values when we get to
266 : this point. */
267 1515930 : if (used[REGNO (reg)] != 1)
268 1111649 : newreg = reg, used[REGNO (reg)] = 1;
269 : else
270 : {
271 404281 : newreg = gen_reg_rtx (GET_MODE (reg));
272 404281 : REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
273 404281 : REG_POINTER (newreg) = REG_POINTER (reg);
274 404281 : REG_ATTRS (newreg) = REG_ATTRS (reg);
275 404281 : if (dump_file)
276 146 : fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
277 : REGNO (newreg));
278 : }
279 :
280 1515930 : root->set_reg (newreg);
281 1515930 : return newreg;
282 : }
283 :
284 : /* Replace the reference by REG. */
285 :
286 : static void
287 5417589 : replace_ref (df_ref ref, rtx reg)
288 : {
289 5417589 : rtx oldreg = DF_REF_REAL_REG (ref);
290 5417589 : rtx *loc = DF_REF_REAL_LOC (ref);
291 5417589 : unsigned int uid = DF_REF_INSN_UID (ref);
292 :
293 5417589 : if (oldreg == reg)
294 : return;
295 1086863 : if (dump_file)
296 428 : fprintf (dump_file, "Updating insn %i (%i->%i)\n",
297 : uid, REGNO (oldreg), REGNO (reg));
298 1086863 : *loc = reg;
299 1086863 : df_insn_rescan (DF_REF_INSN (ref));
300 : }
301 :
302 :
303 : namespace {
304 :
305 : const pass_data pass_data_web =
306 : {
307 : RTL_PASS, /* type */
308 : "web", /* name */
309 : OPTGROUP_NONE, /* optinfo_flags */
310 : TV_WEB, /* tv_id */
311 : 0, /* properties_required */
312 : 0, /* properties_provided */
313 : 0, /* properties_destroyed */
314 : 0, /* todo_flags_start */
315 : TODO_df_finish, /* todo_flags_finish */
316 : };
317 :
318 : class pass_web : public rtl_opt_pass
319 : {
320 : public:
321 287872 : pass_web (gcc::context *ctxt)
322 575744 : : rtl_opt_pass (pass_data_web, ctxt)
323 : {}
324 :
325 : /* opt_pass methods: */
326 1480955 : bool gate (function *) final override { return (optimize > 0 && flag_web); }
327 : unsigned int execute (function *) final override;
328 :
329 : }; // class pass_web
330 :
331 : unsigned int
332 22438 : pass_web::execute (function *fun)
333 : {
334 22438 : web_entry *def_entry;
335 22438 : web_entry *use_entry;
336 22438 : unsigned int max = max_reg_num ();
337 22438 : unsigned int *used;
338 22438 : basic_block bb;
339 22438 : unsigned int uses_num = 0;
340 22438 : rtx_insn *insn;
341 :
342 22438 : df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
343 22438 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
344 22438 : df_chain_add_problem (DF_UD_CHAIN);
345 22438 : df_analyze ();
346 22438 : df_set_flags (DF_DEFER_INSN_RESCAN);
347 :
348 : /* Assign ids to the uses. */
349 596714 : FOR_ALL_BB_FN (bb, fun)
350 5849997 : FOR_BB_INSNS (bb, insn)
351 : {
352 5275721 : if (NONDEBUG_INSN_P (insn))
353 : {
354 3560475 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
355 3560475 : df_ref use;
356 8414973 : FOR_EACH_INSN_INFO_USE (use, insn_info)
357 4854498 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
358 3554838 : DF_REF_ID (use) = uses_num++;
359 3672634 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
360 112159 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
361 45572 : DF_REF_ID (use) = uses_num++;
362 : }
363 : }
364 :
365 : /* Record the number of uses and defs at the beginning of the optimization. */
366 22438 : def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
367 22438 : used = XCNEWVEC (unsigned, max);
368 22438 : use_entry = XCNEWVEC (web_entry, uses_num);
369 :
370 : /* Produce the web. */
371 596714 : FOR_ALL_BB_FN (bb, fun)
372 5849997 : FOR_BB_INSNS (bb, insn)
373 5275721 : if (NONDEBUG_INSN_P (insn))
374 : {
375 3560475 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
376 3560475 : df_ref use;
377 3560475 : union_match_dups (insn, def_entry, use_entry, unionfind_union);
378 8414973 : FOR_EACH_INSN_INFO_USE (use, insn_info)
379 4854498 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
380 3554838 : union_defs (use, def_entry, used, use_entry, unionfind_union);
381 3672634 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
382 112159 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
383 45572 : union_defs (use, def_entry, used, use_entry, unionfind_union);
384 : }
385 :
386 : /* Update the instruction stream, allocating new registers for split pseudos
387 : in progress. */
388 596714 : FOR_ALL_BB_FN (bb, fun)
389 5849997 : FOR_BB_INSNS (bb, insn)
390 5275721 : if (NONDEBUG_INSN_P (insn)
391 : /* Ignore naked clobber. For example, reg 134 in the second insn
392 : of the following sequence will not be replaced.
393 :
394 : (insn (clobber (reg:SI 134)))
395 :
396 : (insn (set (reg:SI 0 r0) (reg:SI 134)))
397 :
398 : Thus the later passes can optimize them away. */
399 5275721 : && GET_CODE (PATTERN (insn)) != CLOBBER)
400 : {
401 3559615 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
402 3559615 : df_ref def, use;
403 8413969 : FOR_EACH_INSN_INFO_USE (use, insn_info)
404 4854354 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
405 3554838 : replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
406 : use, used));
407 3671774 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
408 112159 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
409 45572 : replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
410 : use, used));
411 19076937 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
412 15517322 : if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
413 1817179 : replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
414 : def, used));
415 : }
416 :
417 22438 : free (def_entry);
418 22438 : free (use_entry);
419 22438 : free (used);
420 22438 : return 0;
421 : }
422 :
423 : } // anon namespace
424 :
425 : rtl_opt_pass *
426 287872 : make_pass_web (gcc::context *ctxt)
427 : {
428 287872 : return new pass_web (ctxt);
429 : }
|
