1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2013 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"
46 #include "basic-block.h"
49 #include "insn-config.h"
51 #include "tree-pass.h"
54 /* Find the root of unionfind tree (the representative of set). */
57 unionfind_root (struct web_entry *element)
59 struct web_entry *element1 = element, *element2;
62 element = element->pred;
63 while (element1->pred)
65 element2 = element1->pred;
66 element1->pred = element;
73 Return true if FIRST and SECOND points to the same web entry structure and
74 nothing is done. Otherwise, return false. */
77 unionfind_union (struct web_entry *first, struct web_entry *second)
79 first = unionfind_root (first);
80 second = unionfind_root (second);
87 /* For INSN, union all defs and uses that are linked by match_dup.
88 FUN is the function that does the union. */
91 union_match_dups (rtx insn, struct web_entry *def_entry,
92 struct web_entry *use_entry,
93 bool (*fun) (struct web_entry *, struct web_entry *))
95 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
96 df_ref *use_link = DF_INSN_INFO_USES (insn_info);
97 df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
98 struct web_entry *dup_entry;
103 for (i = 0; i < recog_data.n_dups; i++)
105 int op = recog_data.dup_num[i];
106 enum op_type type = recog_data.operand_type[op];
107 df_ref *ref, *dupref;
108 struct web_entry *entry;
110 for (dup_entry = use_entry, dupref = use_link; *dupref; dupref++)
111 if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
114 if (*dupref == NULL && type == OP_INOUT)
117 for (dup_entry = def_entry, dupref = def_link; *dupref; dupref++)
118 if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
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 */
129 || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
132 ref = type == OP_IN ? use_link : def_link;
133 entry = type == OP_IN ? use_entry : def_entry;
136 if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
138 if (DF_REF_REAL_LOC (*ref) == recog_data.operand_loc[op])
142 if (!*ref && type == OP_INOUT)
144 for (ref = use_link, entry = use_entry; *ref; ref++)
146 if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
148 if (DF_REF_REAL_LOC (*ref) == recog_data.operand_loc[op])
154 (*fun) (dup_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
158 /* For each use, all possible defs reaching it must come in the same
159 register, union them.
160 FUN is the function that does the union.
162 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
163 register, so that all uninitialized uses of the register can be
164 combined into a single web. We actually offset it by 2, because
165 the values 0 and 1 are reserved for use by entry_register. */
168 union_defs (df_ref use, struct web_entry *def_entry,
169 unsigned int *used, struct web_entry *use_entry,
170 bool (*fun) (struct web_entry *, struct web_entry *))
172 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
173 struct df_link *link = DF_REF_CHAIN (use);
180 rtx insn = insn_info->insn;
181 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
182 def_link = DF_INSN_INFO_DEFS (insn_info);
183 set = single_set (insn);
187 /* An artificial use. It links up with nothing. */
193 /* Union all occurrences of the same register in reg notes. */
198 if (use != *eq_use_link
199 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
200 (*fun) (use_entry + DF_REF_ID (use),
201 use_entry + DF_REF_ID (*eq_use_link));
205 /* Recognize trivial noop moves and attempt to keep them as noop. */
208 && SET_SRC (set) == DF_REF_REG (use)
209 && SET_SRC (set) == SET_DEST (set))
214 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
215 (*fun) (use_entry + DF_REF_ID (use),
216 def_entry + DF_REF_ID (*def_link));
221 /* UD chains of uninitialized REGs are empty. Keeping all uses of
222 the same uninitialized REG in a single web is not necessary for
223 correctness, since the uses are undefined, but it's wasteful to
224 allocate one register or slot for each reference. Furthermore,
225 creating new pseudos for uninitialized references in debug insns
226 (see PR 42631) causes -fcompare-debug failures. We record the
227 number of the first uninitialized reference we found, and merge
228 with it any other uninitialized references to the same
232 int regno = REGNO (DF_REF_REAL_REG (use));
234 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
236 used[regno] = DF_REF_ID (use) + 2;
241 (*fun) (use_entry + DF_REF_ID (use),
242 def_entry + DF_REF_ID (link->ref));
246 /* A READ_WRITE use requires the corresponding def to be in the same
247 register. Find it and union. */
248 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
253 link = DF_INSN_INFO_DEFS (insn_info);
260 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
261 (*fun) (use_entry + DF_REF_ID (use),
262 def_entry + DF_REF_ID (*link));
268 /* Find the corresponding register for the given entry. */
271 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
273 struct web_entry *root;
276 /* Find the corresponding web and see if it has been visited. */
277 root = unionfind_root (entry);
281 /* We are seeing this web for the first time, do the assignment. */
282 reg = DF_REF_REAL_REG (ref);
284 /* In case the original register is already assigned, generate new
285 one. Since we use USED to merge uninitialized refs into a single
286 web, we might found an element to be nonzero without our having
287 used it. Test for 1, because union_defs saves it for our use,
288 and there won't be any use for the other values when we get to
290 if (used[REGNO (reg)] != 1)
291 newreg = reg, used[REGNO (reg)] = 1;
294 newreg = gen_reg_rtx (GET_MODE (reg));
295 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
296 REG_POINTER (newreg) = REG_POINTER (reg);
297 REG_ATTRS (newreg) = REG_ATTRS (reg);
299 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
307 /* Replace the reference by REG. */
310 replace_ref (df_ref ref, rtx reg)
312 rtx oldreg = DF_REF_REAL_REG (ref);
313 rtx *loc = DF_REF_REAL_LOC (ref);
314 unsigned int uid = DF_REF_INSN_UID (ref);
319 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
320 uid, REGNO (oldreg), REGNO (reg));
322 df_insn_rescan (DF_REF_INSN (ref));
327 gate_handle_web (void)
329 return (optimize > 0 && flag_web);
332 /* Main entry point. */
337 struct web_entry *def_entry;
338 struct web_entry *use_entry;
339 unsigned int max = max_reg_num ();
342 unsigned int uses_num = 0;
345 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
346 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
347 df_chain_add_problem (DF_UD_CHAIN);
349 df_set_flags (DF_DEFER_INSN_RESCAN);
351 /* Assign ids to the uses. */
353 FOR_BB_INSNS (bb, insn)
355 unsigned int uid = INSN_UID (insn);
356 if (NONDEBUG_INSN_P (insn))
359 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
361 df_ref use = *use_rec;
362 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
363 DF_REF_ID (use) = uses_num++;
365 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
367 df_ref use = *use_rec;
368 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
369 DF_REF_ID (use) = uses_num++;
374 /* Record the number of uses and defs at the beginning of the optimization. */
375 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
376 used = XCNEWVEC (unsigned, max);
377 use_entry = XCNEWVEC (struct web_entry, uses_num);
379 /* Produce the web. */
381 FOR_BB_INSNS (bb, insn)
383 unsigned int uid = INSN_UID (insn);
384 if (NONDEBUG_INSN_P (insn))
387 union_match_dups (insn, def_entry, use_entry, unionfind_union);
388 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
390 df_ref use = *use_rec;
391 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
392 union_defs (use, def_entry, used, use_entry, unionfind_union);
394 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
396 df_ref use = *use_rec;
397 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
398 union_defs (use, def_entry, used, use_entry, unionfind_union);
403 /* Update the instruction stream, allocating new registers for split pseudos
406 FOR_BB_INSNS (bb, insn)
408 unsigned int uid = INSN_UID (insn);
410 if (NONDEBUG_INSN_P (insn)
411 /* Ignore naked clobber. For example, reg 134 in the second insn
412 of the following sequence will not be replaced.
414 (insn (clobber (reg:SI 134)))
416 (insn (set (reg:SI 0 r0) (reg:SI 134)))
418 Thus the later passes can optimize them away. */
419 && GET_CODE (PATTERN (insn)) != CLOBBER)
423 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
425 df_ref use = *use_rec;
426 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
427 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
429 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
431 df_ref use = *use_rec;
432 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
433 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
435 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
437 df_ref def = *def_rec;
438 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
439 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
450 struct rtl_opt_pass pass_web =
455 OPTGROUP_NONE, /* optinfo_flags */
456 gate_handle_web, /* gate */
457 web_main, /* execute */
460 0, /* static_pass_number */
462 0, /* properties_required */
463 0, /* properties_provided */
464 0, /* properties_destroyed */
465 0, /* todo_flags_start */
466 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */