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
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
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
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). */
38 #include "coretypes.h"
40 #include "diagnostic-core.h"
43 #include "hard-reg-set.h"
48 #include "dominance.h"
50 #include "basic-block.h"
52 #include "insn-config.h"
54 #include "tree-pass.h"
57 /* Find the root of unionfind tree (the representative of set). */
60 web_entry_base::unionfind_root ()
62 web_entry_base *element = this, *element1 = this, *element2;
64 while (element->pred ())
65 element = element->pred ();
66 while (element1->pred ())
68 element2 = element1->pred ();
69 element1->set_pred (element);
76 Return true if FIRST and SECOND points to the same web entry structure and
77 nothing is done. Otherwise, return false. */
80 unionfind_union (web_entry_base *first, web_entry_base *second)
82 first = first->unionfind_root ();
83 second = second->unionfind_root ();
86 second->set_pred (first);
90 class web_entry : public web_entry_base
96 rtx reg () { return reg_pvt; }
97 void set_reg (rtx r) { reg_pvt = r; }
100 /* For INSN, union all defs and uses that are linked by match_dup.
101 FUN is the function that does the union. */
104 union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
105 bool (*fun) (web_entry_base *, web_entry_base *))
107 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
108 df_ref use_link = DF_INSN_INFO_USES (insn_info);
109 df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
110 struct web_entry *dup_entry;
115 for (i = 0; i < recog_data.n_dups; i++)
117 int op = recog_data.dup_num[i];
118 enum op_type type = recog_data.operand_type[op];
120 struct web_entry *entry;
122 dup_entry = use_entry;
123 for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
124 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
127 if (dupref == NULL && type == OP_INOUT)
129 dup_entry = def_entry;
130 for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
131 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
134 /* ??? *DUPREF can still be zero, because when an operand matches
135 a memory, DF_REF_LOC (use_link[n]) points to the register part
136 of the address, whereas recog_data.dup_loc[m] points to the
137 entire memory ref, thus we fail to find the duplicate entry,
138 even though it is there.
139 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
140 -O3 -fomit-frame-pointer -funroll-loops */
142 || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
145 ref = type == OP_IN ? use_link : def_link;
146 entry = type == OP_IN ? use_entry : def_entry;
147 for (; ref; ref = DF_REF_NEXT_LOC (ref))
149 rtx *l = DF_REF_LOC (ref);
150 if (l == recog_data.operand_loc[op])
152 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
156 if (!ref && type == OP_INOUT)
159 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
161 rtx *l = DF_REF_LOC (ref);
162 if (l == recog_data.operand_loc[op])
164 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
170 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
174 /* For each use, all possible defs reaching it must come in the same
175 register, union them.
176 FUN is the function that does the union.
178 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
179 register, so that all uninitialized uses of the register can be
180 combined into a single web. We actually offset it by 2, because
181 the values 0 and 1 are reserved for use by entry_register. */
184 union_defs (df_ref use, web_entry *def_entry,
185 unsigned int *used, web_entry *use_entry,
186 bool (*fun) (web_entry_base *, web_entry_base *))
188 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
189 struct df_link *link = DF_REF_CHAIN (use);
196 set = single_set (insn_info->insn);
197 FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
199 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
200 (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
205 /* Union all occurrences of the same register in reg notes. */
207 /* Recognize trivial noop moves and attempt to keep them as noop. */
210 && SET_SRC (set) == DF_REF_REG (use)
211 && SET_SRC (set) == SET_DEST (set))
215 FOR_EACH_INSN_INFO_DEF (def, insn_info)
216 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
217 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
220 /* UD chains of uninitialized REGs are empty. Keeping all uses of
221 the same uninitialized REG in a single web is not necessary for
222 correctness, since the uses are undefined, but it's wasteful to
223 allocate one register or slot for each reference. Furthermore,
224 creating new pseudos for uninitialized references in debug insns
225 (see PR 42631) causes -fcompare-debug failures. We record the
226 number of the first uninitialized reference we found, and merge
227 with it any other uninitialized references to the same
231 int regno = REGNO (DF_REF_REAL_REG (use));
233 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
235 used[regno] = DF_REF_ID (use) + 2;
240 (*fun) (use_entry + DF_REF_ID (use),
241 def_entry + DF_REF_ID (link->ref));
245 /* A READ_WRITE use requires the corresponding def to be in the same
246 register. Find it and union. */
247 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
252 FOR_EACH_INSN_INFO_DEF (def, insn_info)
253 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
254 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
258 /* Find the corresponding register for the given entry. */
261 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
266 /* Find the corresponding web and see if it has been visited. */
267 root = (web_entry *)entry->unionfind_root ();
271 /* We are seeing this web for the first time, do the assignment. */
272 reg = DF_REF_REAL_REG (ref);
274 /* In case the original register is already assigned, generate new
275 one. Since we use USED to merge uninitialized refs into a single
276 web, we might found an element to be nonzero without our having
277 used it. Test for 1, because union_defs saves it for our use,
278 and there won't be any use for the other values when we get to
280 if (used[REGNO (reg)] != 1)
281 newreg = reg, used[REGNO (reg)] = 1;
284 newreg = gen_reg_rtx (GET_MODE (reg));
285 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
286 REG_POINTER (newreg) = REG_POINTER (reg);
287 REG_ATTRS (newreg) = REG_ATTRS (reg);
289 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
293 root->set_reg (newreg);
297 /* Replace the reference by REG. */
300 replace_ref (df_ref ref, rtx reg)
302 rtx oldreg = DF_REF_REAL_REG (ref);
303 rtx *loc = DF_REF_REAL_LOC (ref);
304 unsigned int uid = DF_REF_INSN_UID (ref);
309 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
310 uid, REGNO (oldreg), REGNO (reg));
312 df_insn_rescan (DF_REF_INSN (ref));
318 const pass_data pass_data_web =
322 OPTGROUP_NONE, /* optinfo_flags */
324 0, /* properties_required */
325 0, /* properties_provided */
326 0, /* properties_destroyed */
327 0, /* todo_flags_start */
328 TODO_df_finish, /* todo_flags_finish */
331 class pass_web : public rtl_opt_pass
334 pass_web (gcc::context *ctxt)
335 : rtl_opt_pass (pass_data_web, ctxt)
338 /* opt_pass methods: */
339 virtual bool gate (function *) { return (optimize > 0 && flag_web); }
340 virtual unsigned int execute (function *);
345 pass_web::execute (function *fun)
347 web_entry *def_entry;
348 web_entry *use_entry;
349 unsigned int max = max_reg_num ();
352 unsigned int uses_num = 0;
355 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
356 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
357 df_chain_add_problem (DF_UD_CHAIN);
359 df_set_flags (DF_DEFER_INSN_RESCAN);
361 /* Assign ids to the uses. */
362 FOR_ALL_BB_FN (bb, fun)
363 FOR_BB_INSNS (bb, insn)
365 if (NONDEBUG_INSN_P (insn))
367 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
369 FOR_EACH_INSN_INFO_USE (use, insn_info)
370 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
371 DF_REF_ID (use) = uses_num++;
372 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
373 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
374 DF_REF_ID (use) = uses_num++;
378 /* Record the number of uses and defs at the beginning of the optimization. */
379 def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
380 used = XCNEWVEC (unsigned, max);
381 use_entry = XCNEWVEC (web_entry, uses_num);
383 /* Produce the web. */
384 FOR_ALL_BB_FN (bb, fun)
385 FOR_BB_INSNS (bb, insn)
386 if (NONDEBUG_INSN_P (insn))
388 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
390 union_match_dups (insn, def_entry, use_entry, unionfind_union);
391 FOR_EACH_INSN_INFO_USE (use, insn_info)
392 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
393 union_defs (use, def_entry, used, use_entry, unionfind_union);
394 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
395 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
396 union_defs (use, def_entry, used, use_entry, unionfind_union);
399 /* Update the instruction stream, allocating new registers for split pseudos
401 FOR_ALL_BB_FN (bb, fun)
402 FOR_BB_INSNS (bb, insn)
403 if (NONDEBUG_INSN_P (insn)
404 /* Ignore naked clobber. For example, reg 134 in the second insn
405 of the following sequence will not be replaced.
407 (insn (clobber (reg:SI 134)))
409 (insn (set (reg:SI 0 r0) (reg:SI 134)))
411 Thus the later passes can optimize them away. */
412 && GET_CODE (PATTERN (insn)) != CLOBBER)
414 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
416 FOR_EACH_INSN_INFO_USE (use, insn_info)
417 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
418 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
420 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
421 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
422 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
424 FOR_EACH_INSN_INFO_DEF (def, insn_info)
425 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
426 replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
439 make_pass_web (gcc::context *ctxt)
441 return new pass_web (ctxt);