1/* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2023 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
46web_entry_base *
47web_entry_base::unionfind_root ()
48{
49 web_entry_base *element = this, *element1 = this, *element2;
50
51 while (element->pred ())
52 element = element->pred ();
53 while (element1->pred ())
54 {
55 element2 = element1->pred ();
56 element1->set_pred (element);
57 element1 = element2;
58 }
59 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
66bool
67unionfind_union (web_entry_base *first, web_entry_base *second)
68{
69 first = first->unionfind_root ();
70 second = second->unionfind_root ();
71 if (first == second)
72 return true;
73 second->set_pred (first);
74 return false;
75}
76
77struct web_entry : public web_entry_base
78{
79 private:
80 rtx reg_pvt;
81
82 public:
83 rtx reg () { return reg_pvt; }
84 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
90static void
91union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
92 bool (*fun) (web_entry_base *, web_entry_base *))
93{
94 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
95 df_ref use_link = DF_INSN_INFO_USES (insn_info);
96 df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
97 struct web_entry *dup_entry;
98 int i;
99
100 extract_insn (insn);
101
102 for (i = 0; i < recog_data.n_dups; i++)
103 {
104 int op = recog_data.dup_num[i];
105 enum op_type type = recog_data.operand_type[op];
106 df_ref ref, dupref;
107 struct web_entry *entry;
108
109 dup_entry = use_entry;
110 for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
111 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
112 break;
113
114 if (dupref == NULL && type == OP_INOUT)
115 {
116 dup_entry = def_entry;
117 for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
118 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 if (dupref == NULL
129 || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
130 continue;
131
132 ref = type == OP_IN ? use_link : def_link;
133 entry = type == OP_IN ? use_entry : def_entry;
134 for (; ref; ref = DF_REF_NEXT_LOC (ref))
135 {
136 rtx *l = DF_REF_LOC (ref);
137 if (l == recog_data.operand_loc[op])
138 break;
139 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
140 break;
141 }
142
143 if (!ref && type == OP_INOUT)
144 {
145 entry = use_entry;
146 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
147 {
148 rtx *l = DF_REF_LOC (ref);
149 if (l == recog_data.operand_loc[op])
150 break;
151 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
152 break;
153 }
154 }
155
156 gcc_assert (ref);
157 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
158 }
159}
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
170void
171union_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 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
176 struct df_link *link = DF_REF_CHAIN (use);
177 rtx set;
178
179 if (insn_info)
180 {
181 df_ref eq_use;
182
183 set = single_set (insn: insn_info->insn);
184 FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
185 if (use != eq_use
186 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
187 (*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 if (set
197 && SET_SRC (set) == DF_REF_REG (use)
198 && SET_SRC (set) == SET_DEST (set))
199 {
200 df_ref def;
201
202 FOR_EACH_INSN_INFO_DEF (def, insn_info)
203 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
204 (*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 if (!link)
217 {
218 int regno = REGNO (DF_REF_REAL_REG (use));
219 if (used[regno])
220 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
221 else
222 used[regno] = DF_REF_ID (use) + 2;
223 }
224
225 while (link)
226 {
227 (*fun) (use_entry + DF_REF_ID (use),
228 def_entry + DF_REF_ID (link->ref));
229 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 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
235 if (insn_info)
236 {
237 df_ref def;
238
239 FOR_EACH_INSN_INFO_DEF (def, insn_info)
240 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
241 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
242 }
243}
244
245/* Find the corresponding register for the given entry. */
246
247static rtx
248entry_register (web_entry *entry, df_ref ref, unsigned int *used)
249{
250 web_entry *root;
251 rtx reg, newreg;
252
253 /* Find the corresponding web and see if it has been visited. */
254 root = (web_entry *)entry->unionfind_root ();
255 if (root->reg ())
256 return root->reg ();
257
258 /* We are seeing this web for the first time, do the assignment. */
259 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 if (used[REGNO (reg)] != 1)
268 newreg = reg, used[REGNO (reg)] = 1;
269 else
270 {
271 newreg = gen_reg_rtx (GET_MODE (reg));
272 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
273 REG_POINTER (newreg) = REG_POINTER (reg);
274 REG_ATTRS (newreg) = REG_ATTRS (reg);
275 if (dump_file)
276 fprintf (stream: dump_file, format: "Web oldreg=%i newreg=%i\n", REGNO (reg),
277 REGNO (newreg));
278 }
279
280 root->set_reg (newreg);
281 return newreg;
282}
283
284/* Replace the reference by REG. */
285
286static void
287replace_ref (df_ref ref, rtx reg)
288{
289 rtx oldreg = DF_REF_REAL_REG (ref);
290 rtx *loc = DF_REF_REAL_LOC (ref);
291 unsigned int uid = DF_REF_INSN_UID (ref);
292
293 if (oldreg == reg)
294 return;
295 if (dump_file)
296 fprintf (stream: dump_file, format: "Updating insn %i (%i->%i)\n",
297 uid, REGNO (oldreg), REGNO (reg));
298 *loc = reg;
299 df_insn_rescan (DF_REF_INSN (ref));
300}
301
302
303namespace {
304
305const pass_data pass_data_web =
306{
307 .type: RTL_PASS, /* type */
308 .name: "web", /* name */
309 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
310 .tv_id: TV_WEB, /* tv_id */
311 .properties_required: 0, /* properties_required */
312 .properties_provided: 0, /* properties_provided */
313 .properties_destroyed: 0, /* properties_destroyed */
314 .todo_flags_start: 0, /* todo_flags_start */
315 TODO_df_finish, /* todo_flags_finish */
316};
317
318class pass_web : public rtl_opt_pass
319{
320public:
321 pass_web (gcc::context *ctxt)
322 : rtl_opt_pass (pass_data_web, ctxt)
323 {}
324
325 /* opt_pass methods: */
326 bool gate (function *) final override { return (optimize > 0 && flag_web); }
327 unsigned int execute (function *) final override;
328
329}; // class pass_web
330
331unsigned int
332pass_web::execute (function *fun)
333{
334 web_entry *def_entry;
335 web_entry *use_entry;
336 unsigned int max = max_reg_num ();
337 unsigned int *used;
338 basic_block bb;
339 unsigned int uses_num = 0;
340 rtx_insn *insn;
341
342 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
343 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
344 df_chain_add_problem (DF_UD_CHAIN);
345 df_analyze ();
346 df_set_flags (DF_DEFER_INSN_RESCAN);
347
348 /* Assign ids to the uses. */
349 FOR_ALL_BB_FN (bb, fun)
350 FOR_BB_INSNS (bb, insn)
351 {
352 if (NONDEBUG_INSN_P (insn))
353 {
354 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
355 df_ref use;
356 FOR_EACH_INSN_INFO_USE (use, insn_info)
357 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
358 DF_REF_ID (use) = uses_num++;
359 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
360 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
361 DF_REF_ID (use) = uses_num++;
362 }
363 }
364
365 /* Record the number of uses and defs at the beginning of the optimization. */
366 def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
367 used = XCNEWVEC (unsigned, max);
368 use_entry = XCNEWVEC (web_entry, uses_num);
369
370 /* Produce the web. */
371 FOR_ALL_BB_FN (bb, fun)
372 FOR_BB_INSNS (bb, insn)
373 if (NONDEBUG_INSN_P (insn))
374 {
375 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
376 df_ref use;
377 union_match_dups (insn, def_entry, use_entry, fun: unionfind_union);
378 FOR_EACH_INSN_INFO_USE (use, insn_info)
379 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
380 union_defs (use, def_entry, used, use_entry, fun: unionfind_union);
381 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
382 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
383 union_defs (use, def_entry, used, use_entry, fun: unionfind_union);
384 }
385
386 /* Update the instruction stream, allocating new registers for split pseudos
387 in progress. */
388 FOR_ALL_BB_FN (bb, fun)
389 FOR_BB_INSNS (bb, insn)
390 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 && GET_CODE (PATTERN (insn)) != CLOBBER)
400 {
401 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
402 df_ref def, use;
403 FOR_EACH_INSN_INFO_USE (use, insn_info)
404 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
405 replace_ref (ref: use, reg: entry_register (entry: use_entry + DF_REF_ID (use),
406 ref: use, used));
407 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
408 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
409 replace_ref (ref: use, reg: entry_register (entry: use_entry + DF_REF_ID (use),
410 ref: use, used));
411 FOR_EACH_INSN_INFO_DEF (def, insn_info)
412 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
413 replace_ref (ref: def, reg: entry_register (entry: def_entry + DF_REF_ID (def),
414 ref: def, used));
415 }
416
417 free (ptr: def_entry);
418 free (ptr: use_entry);
419 free (ptr: used);
420 return 0;
421}
422
423} // anon namespace
424
425rtl_opt_pass *
426make_pass_web (gcc::context *ctxt)
427{
428 return new pass_web (ctxt);
429}
430

source code of gcc/web.cc