gcc/
[official-gcc.git] / gcc / web.c
blob58f38318542ac4eb4ac1b01840d0e9316a175924
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 web_entry_base *
57 web_entry_base::unionfind_root ()
59 web_entry_base *element = this, *element1 = this, *element2;
61 while (element->pred ())
62 element = element->pred ();
63 while (element1->pred ())
65 element2 = element1->pred ();
66 element1->set_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 (web_entry_base *first, web_entry_base *second)
79 first = first->unionfind_root ();
80 second = second->unionfind_root ();
81 if (first == second)
82 return true;
83 second->set_pred (first);
84 return false;
87 class web_entry : public web_entry_base
89 private:
90 rtx reg_pvt;
92 public:
93 rtx reg () { return reg_pvt; }
94 void set_reg (rtx r) { reg_pvt = r; }
97 /* For INSN, union all defs and uses that are linked by match_dup.
98 FUN is the function that does the union. */
100 static void
101 union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
102 bool (*fun) (web_entry_base *, web_entry_base *))
104 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
105 df_ref use_link = DF_INSN_INFO_USES (insn_info);
106 df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
107 struct web_entry *dup_entry;
108 int i;
110 extract_insn (insn);
112 for (i = 0; i < recog_data.n_dups; i++)
114 int op = recog_data.dup_num[i];
115 enum op_type type = recog_data.operand_type[op];
116 df_ref ref, dupref;
117 struct web_entry *entry;
119 dup_entry = use_entry;
120 for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
121 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
122 break;
124 if (dupref == NULL && type == OP_INOUT)
126 dup_entry = def_entry;
127 for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
128 if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
129 break;
131 /* ??? *DUPREF can still be zero, because when an operand matches
132 a memory, DF_REF_LOC (use_link[n]) points to the register part
133 of the address, whereas recog_data.dup_loc[m] points to the
134 entire memory ref, thus we fail to find the duplicate entry,
135 even though it is there.
136 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
137 -O3 -fomit-frame-pointer -funroll-loops */
138 if (dupref == NULL
139 || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
140 continue;
142 ref = type == OP_IN ? use_link : def_link;
143 entry = type == OP_IN ? use_entry : def_entry;
144 for (; ref; ref = DF_REF_NEXT_LOC (ref))
146 rtx *l = DF_REF_LOC (ref);
147 if (l == recog_data.operand_loc[op])
148 break;
149 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
150 break;
153 if (!ref && type == OP_INOUT)
155 entry = use_entry;
156 for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
158 rtx *l = DF_REF_LOC (ref);
159 if (l == recog_data.operand_loc[op])
160 break;
161 if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
162 break;
166 gcc_assert (ref);
167 (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
171 /* For each use, all possible defs reaching it must come in the same
172 register, union them.
173 FUN is the function that does the union.
175 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
176 register, so that all uninitialized uses of the register can be
177 combined into a single web. We actually offset it by 2, because
178 the values 0 and 1 are reserved for use by entry_register. */
180 void
181 union_defs (df_ref use, web_entry *def_entry,
182 unsigned int *used, web_entry *use_entry,
183 bool (*fun) (web_entry_base *, web_entry_base *))
185 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
186 struct df_link *link = DF_REF_CHAIN (use);
187 rtx set;
189 if (insn_info)
191 df_ref eq_use;
193 set = single_set (insn_info->insn);
194 FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
195 if (use != eq_use
196 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
197 (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
199 else
200 set = NULL;
202 /* Union all occurrences of the same register in reg notes. */
204 /* Recognize trivial noop moves and attempt to keep them as noop. */
206 if (set
207 && SET_SRC (set) == DF_REF_REG (use)
208 && SET_SRC (set) == SET_DEST (set))
210 df_ref def;
212 FOR_EACH_INSN_INFO_DEF (def, insn_info)
213 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
214 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
217 /* UD chains of uninitialized REGs are empty. Keeping all uses of
218 the same uninitialized REG in a single web is not necessary for
219 correctness, since the uses are undefined, but it's wasteful to
220 allocate one register or slot for each reference. Furthermore,
221 creating new pseudos for uninitialized references in debug insns
222 (see PR 42631) causes -fcompare-debug failures. We record the
223 number of the first uninitialized reference we found, and merge
224 with it any other uninitialized references to the same
225 register. */
226 if (!link)
228 int regno = REGNO (DF_REF_REAL_REG (use));
229 if (used[regno])
230 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
231 else
232 used[regno] = DF_REF_ID (use) + 2;
235 while (link)
237 (*fun) (use_entry + DF_REF_ID (use),
238 def_entry + DF_REF_ID (link->ref));
239 link = link->next;
242 /* A READ_WRITE use requires the corresponding def to be in the same
243 register. Find it and union. */
244 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
245 if (insn_info)
247 df_ref def;
249 FOR_EACH_INSN_INFO_DEF (def, insn_info)
250 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
251 (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
255 /* Find the corresponding register for the given entry. */
257 static rtx
258 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
260 web_entry *root;
261 rtx reg, newreg;
263 /* Find the corresponding web and see if it has been visited. */
264 root = (web_entry *)entry->unionfind_root ();
265 if (root->reg ())
266 return root->reg ();
268 /* We are seeing this web for the first time, do the assignment. */
269 reg = DF_REF_REAL_REG (ref);
271 /* In case the original register is already assigned, generate new
272 one. Since we use USED to merge uninitialized refs into a single
273 web, we might found an element to be nonzero without our having
274 used it. Test for 1, because union_defs saves it for our use,
275 and there won't be any use for the other values when we get to
276 this point. */
277 if (used[REGNO (reg)] != 1)
278 newreg = reg, used[REGNO (reg)] = 1;
279 else
281 newreg = gen_reg_rtx (GET_MODE (reg));
282 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
283 REG_POINTER (newreg) = REG_POINTER (reg);
284 REG_ATTRS (newreg) = REG_ATTRS (reg);
285 if (dump_file)
286 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
287 REGNO (newreg));
290 root->set_reg (newreg);
291 return newreg;
294 /* Replace the reference by REG. */
296 static void
297 replace_ref (df_ref ref, rtx reg)
299 rtx oldreg = DF_REF_REAL_REG (ref);
300 rtx *loc = DF_REF_REAL_LOC (ref);
301 unsigned int uid = DF_REF_INSN_UID (ref);
303 if (oldreg == reg)
304 return;
305 if (dump_file)
306 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
307 uid, REGNO (oldreg), REGNO (reg));
308 *loc = reg;
309 df_insn_rescan (DF_REF_INSN (ref));
313 namespace {
315 const pass_data pass_data_web =
317 RTL_PASS, /* type */
318 "web", /* name */
319 OPTGROUP_NONE, /* optinfo_flags */
320 TV_WEB, /* tv_id */
321 0, /* properties_required */
322 0, /* properties_provided */
323 0, /* properties_destroyed */
324 0, /* todo_flags_start */
325 TODO_df_finish, /* todo_flags_finish */
328 class pass_web : public rtl_opt_pass
330 public:
331 pass_web (gcc::context *ctxt)
332 : rtl_opt_pass (pass_data_web, ctxt)
335 /* opt_pass methods: */
336 virtual bool gate (function *) { return (optimize > 0 && flag_web); }
337 virtual unsigned int execute (function *);
339 }; // class pass_web
341 unsigned int
342 pass_web::execute (function *fun)
344 web_entry *def_entry;
345 web_entry *use_entry;
346 unsigned int max = max_reg_num ();
347 unsigned int *used;
348 basic_block bb;
349 unsigned int uses_num = 0;
350 rtx_insn *insn;
352 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
353 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
354 df_chain_add_problem (DF_UD_CHAIN);
355 df_analyze ();
356 df_set_flags (DF_DEFER_INSN_RESCAN);
358 /* Assign ids to the uses. */
359 FOR_ALL_BB_FN (bb, fun)
360 FOR_BB_INSNS (bb, insn)
362 if (NONDEBUG_INSN_P (insn))
364 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
365 df_ref use;
366 FOR_EACH_INSN_INFO_USE (use, insn_info)
367 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
368 DF_REF_ID (use) = uses_num++;
369 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
370 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
371 DF_REF_ID (use) = uses_num++;
375 /* Record the number of uses and defs at the beginning of the optimization. */
376 def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
377 used = XCNEWVEC (unsigned, max);
378 use_entry = XCNEWVEC (web_entry, uses_num);
380 /* Produce the web. */
381 FOR_ALL_BB_FN (bb, fun)
382 FOR_BB_INSNS (bb, insn)
383 if (NONDEBUG_INSN_P (insn))
385 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
386 df_ref use;
387 union_match_dups (insn, def_entry, use_entry, unionfind_union);
388 FOR_EACH_INSN_INFO_USE (use, insn_info)
389 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
390 union_defs (use, def_entry, used, use_entry, unionfind_union);
391 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
392 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
393 union_defs (use, def_entry, used, use_entry, unionfind_union);
396 /* Update the instruction stream, allocating new registers for split pseudos
397 in progress. */
398 FOR_ALL_BB_FN (bb, fun)
399 FOR_BB_INSNS (bb, insn)
400 if (NONDEBUG_INSN_P (insn)
401 /* Ignore naked clobber. For example, reg 134 in the second insn
402 of the following sequence will not be replaced.
404 (insn (clobber (reg:SI 134)))
406 (insn (set (reg:SI 0 r0) (reg:SI 134)))
408 Thus the later passes can optimize them away. */
409 && GET_CODE (PATTERN (insn)) != CLOBBER)
411 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
412 df_ref def, use;
413 FOR_EACH_INSN_INFO_USE (use, insn_info)
414 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
415 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
416 use, used));
417 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
418 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
419 replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
420 use, used));
421 FOR_EACH_INSN_INFO_DEF (def, insn_info)
422 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
423 replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
424 def, used));
427 free (def_entry);
428 free (use_entry);
429 free (used);
430 return 0;
433 } // anon namespace
435 rtl_opt_pass *
436 make_pass_web (gcc::context *ctxt)
438 return new pass_web (ctxt);