1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001, 2002, 2004, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Simple optimization pass that splits independent uses of each pseudo,
23 increasing effectiveness of other optimizations. The optimization can
24 serve as an example of use for the dataflow module.
26 We don't split registers with REG_USERVAR set unless -fmessy-debugging
27 is specified, because debugging information about such split variables
31 - Add code to keep debugging up-to-date after splitting user variable
32 pseudos. This can be done by keeping track of all the pseudos used
33 for the variable and using life analysis information before reload
34 to determine which one is live and, in case more than one are live,
35 choose the one with the latest definition.
37 Other optimization passes can benefit from the infrastructure too.
39 - We may use profile information and ignore infrequent use for the
40 purpose of web unifying, inserting the compensation code later to
41 implement full induction variable expansion for loops (currently
42 we expand only if the induction variable is dead afterward, which
43 is often the case). */
47 #include "coretypes.h"
52 #include "hard-reg-set.h"
55 #include "basic-block.h"
60 #include "tree-pass.h"
63 static rtx entry_register (struct web_entry *, struct df_ref *, char *);
64 static void replace_ref (struct df_ref *, rtx);
66 /* Find the root of unionfind tree (the representative of set). */
69 unionfind_root (struct web_entry *element)
71 struct web_entry *element1 = element, *element2;
74 element = element->pred;
75 while (element1->pred)
77 element2 = element1->pred;
78 element1->pred = element;
85 Return true if FIRST and SECOND points to the same web entry structure and
86 nothing is done. Otherwise, return false. */
89 unionfind_union (struct web_entry *first, struct web_entry *second)
91 first = unionfind_root (first);
92 second = unionfind_root (second);
99 /* For each use, all possible defs reaching it must come in the same
100 register, union them.
101 FUN is the function that does the union. */
104 union_defs (struct df_ref *use, struct web_entry *def_entry,
105 struct web_entry *use_entry,
106 bool (*fun) (struct web_entry *, struct web_entry *))
108 rtx insn = DF_REF_INSN (use);
109 struct df_link *link = DF_REF_CHAIN (use);
110 struct df_ref **use_link;
111 struct df_ref **eq_use_link;
112 struct df_ref **def_link;
117 use_link = DF_INSN_USES (insn);
118 eq_use_link = DF_INSN_EQ_USES (insn);
119 def_link = DF_INSN_DEFS (insn);
120 set = single_set (insn);
130 /* Some instructions may use match_dup for their operands. In case the
131 operands are dead, we will assign them different pseudos, creating
132 invalid instructions, so union all uses of the same operand for each
139 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link))
140 (*fun) (use_entry + DF_REF_ID (use),
141 use_entry + DF_REF_ID (*use_link));
148 if (use != *eq_use_link
149 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
150 (*fun) (use_entry + DF_REF_ID (use),
151 use_entry + DF_REF_ID (*eq_use_link));
155 /* Recognize trivial noop moves and attempt to keep them as noop. */
158 && SET_SRC (set) == DF_REF_REG (use)
159 && SET_SRC (set) == SET_DEST (set))
164 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
165 (*fun) (use_entry + DF_REF_ID (use),
166 def_entry + DF_REF_ID (*def_link));
172 (*fun) (use_entry + DF_REF_ID (use),
173 def_entry + DF_REF_ID (link->ref));
177 /* A READ_WRITE use requires the corresponding def to be in the same
178 register. Find it and union. */
179 if (use->flags & DF_REF_READ_WRITE)
181 struct df_ref **link;
183 if (DF_REF_INSN (use))
184 link = DF_INSN_DEFS (DF_REF_INSN (use));
191 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
192 (*fun) (use_entry + DF_REF_ID (use),
193 def_entry + DF_REF_ID (*link));
199 /* Find the corresponding register for the given entry. */
202 entry_register (struct web_entry *entry, struct df_ref *ref, char *used)
204 struct web_entry *root;
207 /* Find the corresponding web and see if it has been visited. */
208 root = unionfind_root (entry);
212 /* We are seeing this web for the first time, do the assignment. */
213 reg = DF_REF_REAL_REG (ref);
215 /* In case the original register is already assigned, generate new one. */
216 if (!used[REGNO (reg)])
217 newreg = reg, used[REGNO (reg)] = 1;
218 else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
223 "New web forced to keep reg=%i (user variable)\n",
228 newreg = gen_reg_rtx (GET_MODE (reg));
229 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
230 REG_POINTER (newreg) = REG_POINTER (reg);
231 REG_ATTRS (newreg) = REG_ATTRS (reg);
233 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
241 /* Replace the reference by REG. */
244 replace_ref (struct df_ref *ref, rtx reg)
246 rtx oldreg = DF_REF_REAL_REG (ref);
247 rtx *loc = DF_REF_REAL_LOC (ref);
248 unsigned int uid = INSN_UID (DF_REF_INSN (ref));
253 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
254 uid, REGNO (oldreg), REGNO (reg));
256 df_insn_rescan (DF_REF_INSN (ref));
261 gate_handle_web (void)
263 return (optimize > 0 && flag_web);
266 /* Main entry point. */
271 struct web_entry *def_entry;
272 struct web_entry *use_entry;
273 unsigned int max = max_reg_num ();
276 unsigned int uses_num = 0;
279 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
280 df_chain_add_problem (DF_UD_CHAIN);
282 df_set_flags (DF_DEFER_INSN_RESCAN);
284 /* Assign ids to the uses. */
286 FOR_BB_INSNS (bb, insn)
288 unsigned int uid = INSN_UID (insn);
291 struct df_ref **use_rec;
292 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
294 struct df_ref *use = *use_rec;
295 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
296 DF_REF_ID (use) = uses_num++;
298 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
300 struct df_ref *use = *use_rec;
301 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
302 DF_REF_ID (use) = uses_num++;
307 /* Record the number of uses and defs at the beginning of the optimization. */
308 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
309 used = XCNEWVEC (char, max);
310 use_entry = XCNEWVEC (struct web_entry, uses_num);
312 /* Produce the web. */
314 FOR_BB_INSNS (bb, insn)
316 unsigned int uid = INSN_UID (insn);
319 struct df_ref **use_rec;
320 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
322 struct df_ref *use = *use_rec;
323 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
324 union_defs (use, def_entry, use_entry, unionfind_union);
326 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
328 struct df_ref *use = *use_rec;
329 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
330 union_defs (use, def_entry, use_entry, unionfind_union);
335 /* Update the instruction stream, allocating new registers for split pseudos
338 FOR_BB_INSNS (bb, insn)
340 unsigned int uid = INSN_UID (insn);
343 struct df_ref **use_rec;
344 struct df_ref **def_rec;
345 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
347 struct df_ref *use = *use_rec;
348 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
349 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
351 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
353 struct df_ref *use = *use_rec;
354 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
355 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
357 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
359 struct df_ref *def = *def_rec;
360 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
361 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
372 struct rtl_opt_pass pass_web =
377 gate_handle_web, /* gate */
378 web_main, /* execute */
381 0, /* static_pass_number */
383 0, /* properties_required */
384 0, /* properties_provided */
385 0, /* properties_destroyed */
386 0, /* todo_flags_start */
387 TODO_df_finish | TODO_verify_rtl_sharing |
388 TODO_dump_func /* todo_flags_finish */