[PR c++/84968] reject stmt-exprs in noexcept constexprs
[official-gcc.git] / gcc / web.c
blob1bbb8f32562fad40b783142d85ce1fb0f7b5f74e
1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2018 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 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). */
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"
41 #include "tree-pass.h"
44 /* Find the root of unionfind tree (the representative of set). */
46 web_entry_base *
47 web_entry_base::unionfind_root ()
49 web_entry_base *element = this, *element1 = this, *element2;
51 while (element->pred ())
52 element = element->pred ();
53 while (element1->pred ())
55 element2 = element1->pred ();
56 element1->set_pred (element);
57 element1 = element2;
59 return element;
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. */
66 bool
67 unionfind_union (web_entry_base *first, web_entry_base *second)
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;
77 class web_entry : public web_entry_base
79 private:
80 rtx reg_pvt;
82 public:
83 rtx reg () { return reg_pvt; }
84 void set_reg (rtx r) { reg_pvt = r; }
87 /* For INSN, union all defs and uses that are linked by match_dup.
88 FUN is the function that does the union. */
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 *))
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;
100 extract_insn (insn);
102 for (i = 0; i < recog_data.n_dups; i++)
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;
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;
114 if (dupref == NULL && type == OP_INOUT)
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;
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;
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))
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;
143 if (!ref && type == OP_INOUT)
145 entry = use_entry;
146 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
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;
156 gcc_assert (ref);
157 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
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.
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. */
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 *))
175 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
176 struct df_link *link = DF_REF_CHAIN (use);
177 rtx set;
179 if (insn_info)
181 df_ref eq_use;
183 set = single_set (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));
189 else
190 set = NULL;
192 /* Union all occurrences of the same register in reg notes. */
194 /* Recognize trivial noop moves and attempt to keep them as noop. */
196 if (set
197 && SET_SRC (set) == DF_REF_REG (use)
198 && SET_SRC (set) == SET_DEST (set))
200 df_ref def;
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));
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)
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;
225 while (link)
227 (*fun) (use_entry + DF_REF_ID (use),
228 def_entry + DF_REF_ID (link->ref));
229 link = link->next;
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)
237 df_ref def;
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));
245 /* Find the corresponding register for the given entry. */
247 static rtx
248 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
250 web_entry *root;
251 rtx reg, newreg;
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 ();
258 /* We are seeing this web for the first time, do the assignment. */
259 reg = DF_REF_REAL_REG (ref);
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
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 (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
277 REGNO (newreg));
280 root->set_reg (newreg);
281 return newreg;
284 /* Replace the reference by REG. */
286 static void
287 replace_ref (df_ref ref, rtx reg)
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);
293 if (oldreg == reg)
294 return;
295 if (dump_file)
296 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
297 uid, REGNO (oldreg), REGNO (reg));
298 *loc = reg;
299 df_insn_rescan (DF_REF_INSN (ref));
303 namespace {
305 const pass_data pass_data_web =
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 */
318 class pass_web : public rtl_opt_pass
320 public:
321 pass_web (gcc::context *ctxt)
322 : rtl_opt_pass (pass_data_web, ctxt)
325 /* opt_pass methods: */
326 virtual bool gate (function *) { return (optimize > 0 && flag_web); }
327 virtual unsigned int execute (function *);
329 }; // class pass_web
331 unsigned int
332 pass_web::execute (function *fun)
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;
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);
348 /* Assign ids to the uses. */
349 FOR_ALL_BB_FN (bb, fun)
350 FOR_BB_INSNS (bb, insn)
352 if (NONDEBUG_INSN_P (insn))
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++;
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);
370 /* Produce the web. */
371 FOR_ALL_BB_FN (bb, fun)
372 FOR_BB_INSNS (bb, insn)
373 if (NONDEBUG_INSN_P (insn))
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, 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, 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, unionfind_union);
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.
394 (insn (clobber (reg:SI 134)))
396 (insn (set (reg:SI 0 r0) (reg:SI 134)))
398 Thus the later passes can optimize them away. */
399 && GET_CODE (PATTERN (insn)) != CLOBBER)
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 (use, entry_register (use_entry + DF_REF_ID (use),
406 use, used));
407 FOR_EACH_INSN_INFO_EQ_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_DEF (def, insn_info)
412 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
413 replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
414 def, used));
417 free (def_entry);
418 free (use_entry);
419 free (used);
420 return 0;
423 } // anon namespace
425 rtl_opt_pass *
426 make_pass_web (gcc::context *ctxt)
428 return new pass_web (ctxt);