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