2014-04-15 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / web.c
blobd67151c7139a10acebd98a5a67d3214c3b13e21a
1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2014 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 "tm.h"
40 #include "diagnostic-core.h"
42 #include "rtl.h"
43 #include "hard-reg-set.h"
44 #include "flags.h"
45 #include "obstack.h"
46 #include "basic-block.h"
47 #include "df.h"
48 #include "function.h"
49 #include "insn-config.h"
50 #include "recog.h"
51 #include "tree-pass.h"
54 /* Find the root of unionfind tree (the representative of set). */
56 struct web_entry *
57 unionfind_root (struct web_entry *element)
59 struct web_entry *element1 = element, *element2;
61 while (element->pred)
62 element = element->pred;
63 while (element1->pred)
65 element2 = element1->pred;
66 element1->pred = element;
67 element1 = element2;
69 return element;
72 /* Union sets.
73 Return true if FIRST and SECOND points to the same web entry structure and
74 nothing is done. Otherwise, return false. */
76 bool
77 unionfind_union (struct web_entry *first, struct web_entry *second)
79 first = unionfind_root (first);
80 second = unionfind_root (second);
81 if (first == second)
82 return true;
83 second->pred = first;
84 return false;
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, 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;
99 int i;
101 extract_insn (insn);
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])
112 break;
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])
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++)
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 for (ref = use_link, entry = use_entry; *ref; ref++)
147 rtx *l = DF_REF_LOC (*ref);
148 if (l == recog_data.operand_loc[op])
149 break;
150 if (l && DF_REF_REAL_LOC (*ref) == recog_data.operand_loc[op])
151 break;
155 gcc_assert (*ref);
156 (*fun) (dup_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
160 /* For each use, all possible defs reaching it must come in the same
161 register, union them.
162 FUN is the function that does the union.
164 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
165 register, so that all uninitialized uses of the register can be
166 combined into a single web. We actually offset it by 2, because
167 the values 0 and 1 are reserved for use by entry_register. */
169 void
170 union_defs (df_ref use, struct web_entry *def_entry,
171 unsigned int *used, struct web_entry *use_entry,
172 bool (*fun) (struct web_entry *, struct web_entry *))
174 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
175 struct df_link *link = DF_REF_CHAIN (use);
176 df_ref *eq_use_link;
177 df_ref *def_link;
178 rtx set;
180 if (insn_info)
182 rtx insn = insn_info->insn;
183 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
184 def_link = DF_INSN_INFO_DEFS (insn_info);
185 set = single_set (insn);
187 else
189 /* An artificial use. It links up with nothing. */
190 eq_use_link = NULL;
191 def_link = NULL;
192 set = NULL;
195 /* Union all occurrences of the same register in reg notes. */
197 if (eq_use_link)
198 while (*eq_use_link)
200 if (use != *eq_use_link
201 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
202 (*fun) (use_entry + DF_REF_ID (use),
203 use_entry + DF_REF_ID (*eq_use_link));
204 eq_use_link++;
207 /* Recognize trivial noop moves and attempt to keep them as noop. */
209 if (set
210 && SET_SRC (set) == DF_REF_REG (use)
211 && SET_SRC (set) == SET_DEST (set))
213 if (def_link)
214 while (*def_link)
216 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
217 (*fun) (use_entry + DF_REF_ID (use),
218 def_entry + DF_REF_ID (*def_link));
219 def_link++;
223 /* UD chains of uninitialized REGs are empty. Keeping all uses of
224 the same uninitialized REG in a single web is not necessary for
225 correctness, since the uses are undefined, but it's wasteful to
226 allocate one register or slot for each reference. Furthermore,
227 creating new pseudos for uninitialized references in debug insns
228 (see PR 42631) causes -fcompare-debug failures. We record the
229 number of the first uninitialized reference we found, and merge
230 with it any other uninitialized references to the same
231 register. */
232 if (!link)
234 int regno = REGNO (DF_REF_REAL_REG (use));
235 if (used[regno])
236 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
237 else
238 used[regno] = DF_REF_ID (use) + 2;
241 while (link)
243 (*fun) (use_entry + DF_REF_ID (use),
244 def_entry + DF_REF_ID (link->ref));
245 link = link->next;
248 /* A READ_WRITE use requires the corresponding def to be in the same
249 register. Find it and union. */
250 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
252 df_ref *link;
254 if (insn_info)
255 link = DF_INSN_INFO_DEFS (insn_info);
256 else
257 link = NULL;
259 if (link)
260 while (*link)
262 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
263 (*fun) (use_entry + DF_REF_ID (use),
264 def_entry + DF_REF_ID (*link));
265 link++;
270 /* Find the corresponding register for the given entry. */
272 static rtx
273 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
275 struct web_entry *root;
276 rtx reg, newreg;
278 /* Find the corresponding web and see if it has been visited. */
279 root = unionfind_root (entry);
280 if (root->reg)
281 return root->reg;
283 /* We are seeing this web for the first time, do the assignment. */
284 reg = DF_REF_REAL_REG (ref);
286 /* In case the original register is already assigned, generate new
287 one. Since we use USED to merge uninitialized refs into a single
288 web, we might found an element to be nonzero without our having
289 used it. Test for 1, because union_defs saves it for our use,
290 and there won't be any use for the other values when we get to
291 this point. */
292 if (used[REGNO (reg)] != 1)
293 newreg = reg, used[REGNO (reg)] = 1;
294 else
296 newreg = gen_reg_rtx (GET_MODE (reg));
297 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
298 REG_POINTER (newreg) = REG_POINTER (reg);
299 REG_ATTRS (newreg) = REG_ATTRS (reg);
300 if (dump_file)
301 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
302 REGNO (newreg));
305 root->reg = newreg;
306 return newreg;
309 /* Replace the reference by REG. */
311 static void
312 replace_ref (df_ref ref, rtx reg)
314 rtx oldreg = DF_REF_REAL_REG (ref);
315 rtx *loc = DF_REF_REAL_LOC (ref);
316 unsigned int uid = DF_REF_INSN_UID (ref);
318 if (oldreg == reg)
319 return;
320 if (dump_file)
321 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
322 uid, REGNO (oldreg), REGNO (reg));
323 *loc = reg;
324 df_insn_rescan (DF_REF_INSN (ref));
328 static bool
329 gate_handle_web (void)
331 return (optimize > 0 && flag_web);
334 /* Main entry point. */
336 static unsigned int
337 web_main (void)
339 struct web_entry *def_entry;
340 struct web_entry *use_entry;
341 unsigned int max = max_reg_num ();
342 unsigned int *used;
343 basic_block bb;
344 unsigned int uses_num = 0;
345 rtx insn;
347 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
348 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
349 df_chain_add_problem (DF_UD_CHAIN);
350 df_analyze ();
351 df_set_flags (DF_DEFER_INSN_RESCAN);
353 /* Assign ids to the uses. */
354 FOR_ALL_BB_FN (bb, cfun)
355 FOR_BB_INSNS (bb, insn)
357 unsigned int uid = INSN_UID (insn);
358 if (NONDEBUG_INSN_P (insn))
360 df_ref *use_rec;
361 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
363 df_ref use = *use_rec;
364 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
365 DF_REF_ID (use) = uses_num++;
367 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
369 df_ref use = *use_rec;
370 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
371 DF_REF_ID (use) = uses_num++;
376 /* Record the number of uses and defs at the beginning of the optimization. */
377 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE ());
378 used = XCNEWVEC (unsigned, max);
379 use_entry = XCNEWVEC (struct web_entry, uses_num);
381 /* Produce the web. */
382 FOR_ALL_BB_FN (bb, cfun)
383 FOR_BB_INSNS (bb, insn)
385 unsigned int uid = INSN_UID (insn);
386 if (NONDEBUG_INSN_P (insn))
388 df_ref *use_rec;
389 union_match_dups (insn, def_entry, use_entry, unionfind_union);
390 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
392 df_ref use = *use_rec;
393 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
394 union_defs (use, def_entry, used, use_entry, unionfind_union);
396 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
398 df_ref use = *use_rec;
399 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
400 union_defs (use, def_entry, used, use_entry, unionfind_union);
405 /* Update the instruction stream, allocating new registers for split pseudos
406 in progress. */
407 FOR_ALL_BB_FN (bb, cfun)
408 FOR_BB_INSNS (bb, insn)
410 unsigned int uid = INSN_UID (insn);
412 if (NONDEBUG_INSN_P (insn)
413 /* Ignore naked clobber. For example, reg 134 in the second insn
414 of the following sequence will not be replaced.
416 (insn (clobber (reg:SI 134)))
418 (insn (set (reg:SI 0 r0) (reg:SI 134)))
420 Thus the later passes can optimize them away. */
421 && GET_CODE (PATTERN (insn)) != CLOBBER)
423 df_ref *use_rec;
424 df_ref *def_rec;
425 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
427 df_ref use = *use_rec;
428 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
429 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
431 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
433 df_ref use = *use_rec;
434 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
435 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
437 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
439 df_ref def = *def_rec;
440 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
441 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
446 free (def_entry);
447 free (use_entry);
448 free (used);
449 return 0;
452 namespace {
454 const pass_data pass_data_web =
456 RTL_PASS, /* type */
457 "web", /* name */
458 OPTGROUP_NONE, /* optinfo_flags */
459 true, /* has_gate */
460 true, /* has_execute */
461 TV_WEB, /* tv_id */
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 */
469 class pass_web : public rtl_opt_pass
471 public:
472 pass_web (gcc::context *ctxt)
473 : rtl_opt_pass (pass_data_web, ctxt)
476 /* opt_pass methods: */
477 bool gate () { return gate_handle_web (); }
478 unsigned int execute () { return web_main (); }
480 }; // class pass_web
482 } // anon namespace
484 rtl_opt_pass *
485 make_pass_web (gcc::context *ctxt)
487 return new pass_web (ctxt);