PR go/67101
[official-gcc.git] / gcc / web.c
blob839b03e94a3e674ec828e532ec1b3921e03be22e
1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2015 Free Software Foundation, Inc.
5 This file is part of GCC.
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.
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.
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/>. */
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.
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.
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). */
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 "diagnostic-core.h"
44 #include "flags.h"
45 #include "insn-config.h"
46 #include "recog.h"
47 #include "tree-pass.h"
50 /* Find the root of unionfind tree (the representative of set). */
52 web_entry_base *
53 web_entry_base::unionfind_root ()
55 web_entry_base *element = this, *element1 = this, *element2;
57 while (element->pred ())
58 element = element->pred ();
59 while (element1->pred ())
61 element2 = element1->pred ();
62 element1->set_pred (element);
63 element1 = element2;
65 return element;
68 /* Union sets.
69 Return true if FIRST and SECOND points to the same web entry structure and
70 nothing is done. Otherwise, return false. */
72 bool
73 unionfind_union (web_entry_base *first, web_entry_base *second)
75 first = first->unionfind_root ();
76 second = second->unionfind_root ();
77 if (first == second)
78 return true;
79 second->set_pred (first);
80 return false;
83 class web_entry : public web_entry_base
85 private:
86 rtx reg_pvt;
88 public:
89 rtx reg () { return reg_pvt; }
90 void set_reg (rtx r) { reg_pvt = r; }
93 /* For INSN, union all defs and uses that are linked by match_dup.
94 FUN is the function that does the union. */
96 static void
97 union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
98 bool (*fun) (web_entry_base *, web_entry_base *))
100 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
101 df_ref use_link = DF_INSN_INFO_USES (insn_info);
102 df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
103 struct web_entry *dup_entry;
104 int i;
106 extract_insn (insn);
108 for (i = 0; i < recog_data.n_dups; i++)
110 int op = recog_data.dup_num[i];
111 enum op_type type = recog_data.operand_type[op];
112 df_ref ref, dupref;
113 struct web_entry *entry;
115 dup_entry = use_entry;
116 for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
117 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
118 break;
120 if (dupref == NULL && type == OP_INOUT)
122 dup_entry = def_entry;
123 for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
124 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
125 break;
127 /* ??? *DUPREF can still be zero, because when an operand matches
128 a memory, DF_REF_LOC (use_link[n]) points to the register part
129 of the address, whereas recog_data.dup_loc[m] points to the
130 entire memory ref, thus we fail to find the duplicate entry,
131 even though it is there.
132 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
133 -O3 -fomit-frame-pointer -funroll-loops */
134 if (dupref == NULL
135 || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
136 continue;
138 ref = type == OP_IN ? use_link : def_link;
139 entry = type == OP_IN ? use_entry : def_entry;
140 for (; ref; ref = DF_REF_NEXT_LOC (ref))
142 rtx *l = DF_REF_LOC (ref);
143 if (l == recog_data.operand_loc[op])
144 break;
145 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
146 break;
149 if (!ref && type == OP_INOUT)
151 entry = use_entry;
152 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
154 rtx *l = DF_REF_LOC (ref);
155 if (l == recog_data.operand_loc[op])
156 break;
157 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
158 break;
162 gcc_assert (ref);
163 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
167 /* For each use, all possible defs reaching it must come in the same
168 register, union them.
169 FUN is the function that does the union.
171 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
172 register, so that all uninitialized uses of the register can be
173 combined into a single web. We actually offset it by 2, because
174 the values 0 and 1 are reserved for use by entry_register. */
176 void
177 union_defs (df_ref use, web_entry *def_entry,
178 unsigned int *used, web_entry *use_entry,
179 bool (*fun) (web_entry_base *, web_entry_base *))
181 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
182 struct df_link *link = DF_REF_CHAIN (use);
183 rtx set;
185 if (insn_info)
187 df_ref eq_use;
189 set = single_set (insn_info->insn);
190 FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
191 if (use != eq_use
192 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
193 (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
195 else
196 set = NULL;
198 /* Union all occurrences of the same register in reg notes. */
200 /* Recognize trivial noop moves and attempt to keep them as noop. */
202 if (set
203 && SET_SRC (set) == DF_REF_REG (use)
204 && SET_SRC (set) == SET_DEST (set))
206 df_ref def;
208 FOR_EACH_INSN_INFO_DEF (def, insn_info)
209 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
210 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
213 /* UD chains of uninitialized REGs are empty. Keeping all uses of
214 the same uninitialized REG in a single web is not necessary for
215 correctness, since the uses are undefined, but it's wasteful to
216 allocate one register or slot for each reference. Furthermore,
217 creating new pseudos for uninitialized references in debug insns
218 (see PR 42631) causes -fcompare-debug failures. We record the
219 number of the first uninitialized reference we found, and merge
220 with it any other uninitialized references to the same
221 register. */
222 if (!link)
224 int regno = REGNO (DF_REF_REAL_REG (use));
225 if (used[regno])
226 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
227 else
228 used[regno] = DF_REF_ID (use) + 2;
231 while (link)
233 (*fun) (use_entry + DF_REF_ID (use),
234 def_entry + DF_REF_ID (link->ref));
235 link = link->next;
238 /* A READ_WRITE use requires the corresponding def to be in the same
239 register. Find it and union. */
240 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
241 if (insn_info)
243 df_ref def;
245 FOR_EACH_INSN_INFO_DEF (def, insn_info)
246 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
247 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
251 /* Find the corresponding register for the given entry. */
253 static rtx
254 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
256 web_entry *root;
257 rtx reg, newreg;
259 /* Find the corresponding web and see if it has been visited. */
260 root = (web_entry *)entry->unionfind_root ();
261 if (root->reg ())
262 return root->reg ();
264 /* We are seeing this web for the first time, do the assignment. */
265 reg = DF_REF_REAL_REG (ref);
267 /* In case the original register is already assigned, generate new
268 one. Since we use USED to merge uninitialized refs into a single
269 web, we might found an element to be nonzero without our having
270 used it. Test for 1, because union_defs saves it for our use,
271 and there won't be any use for the other values when we get to
272 this point. */
273 if (used[REGNO (reg)] != 1)
274 newreg = reg, used[REGNO (reg)] = 1;
275 else
277 newreg = gen_reg_rtx (GET_MODE (reg));
278 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
279 REG_POINTER (newreg) = REG_POINTER (reg);
280 REG_ATTRS (newreg) = REG_ATTRS (reg);
281 if (dump_file)
282 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
283 REGNO (newreg));
286 root->set_reg (newreg);
287 return newreg;
290 /* Replace the reference by REG. */
292 static void
293 replace_ref (df_ref ref, rtx reg)
295 rtx oldreg = DF_REF_REAL_REG (ref);
296 rtx *loc = DF_REF_REAL_LOC (ref);
297 unsigned int uid = DF_REF_INSN_UID (ref);
299 if (oldreg == reg)
300 return;
301 if (dump_file)
302 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
303 uid, REGNO (oldreg), REGNO (reg));
304 *loc = reg;
305 df_insn_rescan (DF_REF_INSN (ref));
309 namespace {
311 const pass_data pass_data_web =
313 RTL_PASS, /* type */
314 "web", /* name */
315 OPTGROUP_NONE, /* optinfo_flags */
316 TV_WEB, /* tv_id */
317 0, /* properties_required */
318 0, /* properties_provided */
319 0, /* properties_destroyed */
320 0, /* todo_flags_start */
321 TODO_df_finish, /* todo_flags_finish */
324 class pass_web : public rtl_opt_pass
326 public:
327 pass_web (gcc::context *ctxt)
328 : rtl_opt_pass (pass_data_web, ctxt)
331 /* opt_pass methods: */
332 virtual bool gate (function *) { return (optimize > 0 && flag_web); }
333 virtual unsigned int execute (function *);
335 }; // class pass_web
337 unsigned int
338 pass_web::execute (function *fun)
340 web_entry *def_entry;
341 web_entry *use_entry;
342 unsigned int max = max_reg_num ();
343 unsigned int *used;
344 basic_block bb;
345 unsigned int uses_num = 0;
346 rtx_insn *insn;
348 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
349 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
350 df_chain_add_problem (DF_UD_CHAIN);
351 df_analyze ();
352 df_set_flags (DF_DEFER_INSN_RESCAN);
354 /* Assign ids to the uses. */
355 FOR_ALL_BB_FN (bb, fun)
356 FOR_BB_INSNS (bb, insn)
358 if (NONDEBUG_INSN_P (insn))
360 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
361 df_ref use;
362 FOR_EACH_INSN_INFO_USE (use, insn_info)
363 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
364 DF_REF_ID (use) = uses_num++;
365 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
366 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
367 DF_REF_ID (use) = uses_num++;
371 /* Record the number of uses and defs at the beginning of the optimization. */
372 def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
373 used = XCNEWVEC (unsigned, max);
374 use_entry = XCNEWVEC (web_entry, uses_num);
376 /* Produce the web. */
377 FOR_ALL_BB_FN (bb, fun)
378 FOR_BB_INSNS (bb, insn)
379 if (NONDEBUG_INSN_P (insn))
381 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
382 df_ref use;
383 union_match_dups (insn, def_entry, use_entry, unionfind_union);
384 FOR_EACH_INSN_INFO_USE (use, insn_info)
385 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
386 union_defs (use, def_entry, used, use_entry, unionfind_union);
387 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
388 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
389 union_defs (use, def_entry, used, use_entry, unionfind_union);
392 /* Update the instruction stream, allocating new registers for split pseudos
393 in progress. */
394 FOR_ALL_BB_FN (bb, fun)
395 FOR_BB_INSNS (bb, insn)
396 if (NONDEBUG_INSN_P (insn)
397 /* Ignore naked clobber. For example, reg 134 in the second insn
398 of the following sequence will not be replaced.
400 (insn (clobber (reg:SI 134)))
402 (insn (set (reg:SI 0 r0) (reg:SI 134)))
404 Thus the later passes can optimize them away. */
405 && GET_CODE (PATTERN (insn)) != CLOBBER)
407 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
408 df_ref def, use;
409 FOR_EACH_INSN_INFO_USE (use, insn_info)
410 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
411 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
412 use, used));
413 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
414 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
415 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
416 use, used));
417 FOR_EACH_INSN_INFO_DEF (def, insn_info)
418 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
419 replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
420 def, used));
423 free (def_entry);
424 free (use_entry);
425 free (used);
426 return 0;
429 } // anon namespace
431 rtl_opt_pass *
432 make_pass_web (gcc::context *ctxt)
434 return new pass_web (ctxt);