Branch data Line data Source code
1 : : /* Web construction code for GNU compiler.
2 : : Contributed by Jan Hubicka.
3 : : Copyright (C) 2001-2024 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 : 14505471 : web_entry_base::unionfind_root ()
48 : : {
49 : 14505471 : web_entry_base *element = this, *element1 = this, *element2;
50 : :
51 : 25962243 : while (element->pred ())
52 : : element = element->pred ();
53 : 25962243 : while (element1->pred ())
54 : : {
55 : 11456772 : element2 = element1->pred ();
56 : 11456772 : element1->set_pred (element);
57 : 11456772 : element1 = element2;
58 : : }
59 : 14505471 : 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 : 4709233 : unionfind_union (web_entry_base *first, web_entry_base *second)
68 : : {
69 : 4709233 : first = first->unionfind_root ();
70 : 4709233 : second = second->unionfind_root ();
71 : 4709233 : if (first == second)
72 : : return true;
73 : 3679875 : second->set_pred (first);
74 : 3679875 : return false;
75 : : }
76 : :
77 : : struct web_entry : public web_entry_base
78 : : {
79 : : private:
80 : : rtx reg_pvt;
81 : :
82 : : public:
83 : 5087005 : rtx reg () { return reg_pvt; }
84 : 1407130 : 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 : 3344882 : 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 : 3344882 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
95 : 3344882 : df_ref use_link = DF_INSN_INFO_USES (insn_info);
96 : 3344882 : df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
97 : 3344882 : struct web_entry *dup_entry;
98 : 3344882 : int i;
99 : :
100 : 3344882 : extract_insn (insn);
101 : :
102 : 3386976 : for (i = 0; i < recog_data.n_dups; i++)
103 : : {
104 : 42094 : int op = recog_data.dup_num[i];
105 : 42094 : enum op_type type = recog_data.operand_type[op];
106 : 42094 : df_ref ref, dupref;
107 : 42094 : struct web_entry *entry;
108 : :
109 : 42094 : dup_entry = use_entry;
110 : 114367 : for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
111 : 98678 : if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
112 : : break;
113 : :
114 : 42094 : if (dupref == NULL && type == OP_INOUT)
115 : : {
116 : 11828 : dup_entry = def_entry;
117 : 11828 : for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
118 : 7041 : 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 : 42094 : if (dupref == NULL
129 : 26414 : || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
130 : 16290 : continue;
131 : :
132 : 25804 : ref = type == OP_IN ? use_link : def_link;
133 : 9 : entry = type == OP_IN ? use_entry : def_entry;
134 : 58931 : for (; ref; ref = DF_REF_NEXT_LOC (ref))
135 : : {
136 : 58922 : rtx *l = DF_REF_LOC (ref);
137 : 58922 : if (l == recog_data.operand_loc[op])
138 : : break;
139 : 33127 : if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
140 : : break;
141 : : }
142 : :
143 : 25804 : 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 : 25804 : gcc_assert (ref);
157 : 25804 : (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
158 : : }
159 : 3344882 : }
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 : 3361932 : 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 : 3361932 : struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
176 : 3361932 : struct df_link *link = DF_REF_CHAIN (use);
177 : 3361932 : rtx set;
178 : :
179 : 3361932 : if (insn_info)
180 : : {
181 : 3361932 : df_ref eq_use;
182 : :
183 : 3361932 : set = single_set (insn_info->insn);
184 : 3558730 : FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
185 : 196798 : if (use != eq_use
186 : 154100 : && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
187 : 31591 : (*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 : 3361932 : if (set
197 : 3343577 : && SET_SRC (set) == DF_REF_REG (use)
198 : 534509 : && 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 : 3361932 : if (!link)
217 : : {
218 : 12556 : int regno = REGNO (DF_REF_REAL_REG (use));
219 : 12556 : if (used[regno])
220 : 8572 : (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
221 : : else
222 : 3984 : used[regno] = DF_REF_ID (use) + 2;
223 : : }
224 : :
225 : 8002913 : while (link)
226 : : {
227 : 4640981 : (*fun) (use_entry + DF_REF_ID (use),
228 : 4640981 : def_entry + DF_REF_ID (link->ref));
229 : 4640981 : 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 : 3361932 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
235 : 2285 : if (insn_info)
236 : : {
237 : 2285 : df_ref def;
238 : :
239 : 4570 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
240 : 2285 : if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
241 : 2285 : (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
242 : : }
243 : 3361932 : }
244 : :
245 : : /* Find the corresponding register for the given entry. */
246 : :
247 : : static rtx
248 : 5087005 : entry_register (web_entry *entry, df_ref ref, unsigned int *used)
249 : : {
250 : 5087005 : web_entry *root;
251 : 5087005 : rtx reg, newreg;
252 : :
253 : : /* Find the corresponding web and see if it has been visited. */
254 : 5087005 : root = (web_entry *)entry->unionfind_root ();
255 : 5087005 : if (root->reg ())
256 : : return root->reg ();
257 : :
258 : : /* We are seeing this web for the first time, do the assignment. */
259 : 1407130 : 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 : 1407130 : if (used[REGNO (reg)] != 1)
268 : 1044614 : newreg = reg, used[REGNO (reg)] = 1;
269 : : else
270 : : {
271 : 362516 : newreg = gen_reg_rtx (GET_MODE (reg));
272 : 362516 : REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
273 : 362516 : REG_POINTER (newreg) = REG_POINTER (reg);
274 : 362516 : REG_ATTRS (newreg) = REG_ATTRS (reg);
275 : 362516 : if (dump_file)
276 : 146 : fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
277 : : REGNO (newreg));
278 : : }
279 : :
280 : 1407130 : root->set_reg (newreg);
281 : 1407130 : return newreg;
282 : : }
283 : :
284 : : /* Replace the reference by REG. */
285 : :
286 : : static void
287 : 5087005 : replace_ref (df_ref ref, rtx reg)
288 : : {
289 : 5087005 : rtx oldreg = DF_REF_REAL_REG (ref);
290 : 5087005 : rtx *loc = DF_REF_REAL_LOC (ref);
291 : 5087005 : unsigned int uid = DF_REF_INSN_UID (ref);
292 : :
293 : 5087005 : if (oldreg == reg)
294 : : return;
295 : 956959 : if (dump_file)
296 : 428 : fprintf (dump_file, "Updating insn %i (%i->%i)\n",
297 : : uid, REGNO (oldreg), REGNO (reg));
298 : 956959 : *loc = reg;
299 : 956959 : 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 : 280114 : pass_web (gcc::context *ctxt)
322 : 560228 : : rtl_opt_pass (pass_data_web, ctxt)
323 : : {}
324 : :
325 : : /* opt_pass methods: */
326 : 1415668 : 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 : 21315 : pass_web::execute (function *fun)
333 : : {
334 : 21315 : web_entry *def_entry;
335 : 21315 : web_entry *use_entry;
336 : 21315 : unsigned int max = max_reg_num ();
337 : 21315 : unsigned int *used;
338 : 21315 : basic_block bb;
339 : 21315 : unsigned int uses_num = 0;
340 : 21315 : rtx_insn *insn;
341 : :
342 : 21315 : df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
343 : 21315 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
344 : 21315 : df_chain_add_problem (DF_UD_CHAIN);
345 : 21315 : df_analyze ();
346 : 21315 : df_set_flags (DF_DEFER_INSN_RESCAN);
347 : :
348 : : /* Assign ids to the uses. */
349 : 561874 : FOR_ALL_BB_FN (bb, fun)
350 : 5528531 : FOR_BB_INSNS (bb, insn)
351 : : {
352 : 4987972 : if (NONDEBUG_INSN_P (insn))
353 : : {
354 : 3344882 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
355 : 3344882 : df_ref use;
356 : 7885552 : FOR_EACH_INSN_INFO_USE (use, insn_info)
357 : 4540670 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
358 : 3319234 : DF_REF_ID (use) = uses_num++;
359 : 3451762 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
360 : 106880 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
361 : 42698 : DF_REF_ID (use) = uses_num++;
362 : : }
363 : : }
364 : :
365 : : /* Record the number of uses and defs at the beginning of the optimization. */
366 : 21315 : def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
367 : 21315 : used = XCNEWVEC (unsigned, max);
368 : 21315 : use_entry = XCNEWVEC (web_entry, uses_num);
369 : :
370 : : /* Produce the web. */
371 : 561874 : FOR_ALL_BB_FN (bb, fun)
372 : 5528531 : FOR_BB_INSNS (bb, insn)
373 : 4987972 : if (NONDEBUG_INSN_P (insn))
374 : : {
375 : 3344882 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
376 : 3344882 : df_ref use;
377 : 3344882 : union_match_dups (insn, def_entry, use_entry, unionfind_union);
378 : 7885552 : FOR_EACH_INSN_INFO_USE (use, insn_info)
379 : 4540670 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
380 : 3319234 : union_defs (use, def_entry, used, use_entry, unionfind_union);
381 : 3451762 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
382 : 106880 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
383 : 42698 : 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 : 561874 : FOR_ALL_BB_FN (bb, fun)
389 : 5528531 : FOR_BB_INSNS (bb, insn)
390 : 4987972 : 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 : 4987972 : && GET_CODE (PATTERN (insn)) != CLOBBER)
400 : : {
401 : 3344060 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
402 : 3344060 : df_ref def, use;
403 : 7884596 : FOR_EACH_INSN_INFO_USE (use, insn_info)
404 : 4540536 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
405 : 3319234 : replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
406 : : use, used));
407 : 3450940 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
408 : 106880 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
409 : 42698 : replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
410 : : use, used));
411 : 17809652 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
412 : 14465592 : if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
413 : 1725073 : replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
414 : : def, used));
415 : : }
416 : :
417 : 21315 : free (def_entry);
418 : 21315 : free (use_entry);
419 : 21315 : free (used);
420 : 21315 : return 0;
421 : : }
422 : :
423 : : } // anon namespace
424 : :
425 : : rtl_opt_pass *
426 : 280114 : make_pass_web (gcc::context *ctxt)
427 : : {
428 : 280114 : return new pass_web (ctxt);
429 : : }
|
