1 | /* Web construction code for GNU compiler. |
2 | Contributed by Jan Hubicka. |
3 | Copyright (C) 2001-2023 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 | web_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 | |
66 | bool |
67 | unionfind_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 | |
77 | struct 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 | |
90 | static void |
91 | 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 | 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 | |
170 | void |
171 | 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 | 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 | |
247 | static rtx |
248 | entry_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 | |
286 | static void |
287 | replace_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 | |
303 | namespace { |
304 | |
305 | const 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 | |
318 | class pass_web : public rtl_opt_pass |
319 | { |
320 | public: |
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 | |
331 | unsigned int |
332 | pass_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 | |
425 | rtl_opt_pass * |
426 | make_pass_web (gcc::context *ctxt) |
427 | { |
428 | return new pass_web (ctxt); |
429 | } |
430 | |