1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010
4 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
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
11 version.
12
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
16 for more details.
17
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/>. */
21
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.
25
26 We don't split registers with REG_USERVAR set unless -fmessy-debugging
27 is specified, because debugging information about such split variables
28 is almost unusable.
29
30 TODO
31 - We may use profile information and ignore infrequent use for the
32 purpose of web unifying, inserting the compensation code later to
33 implement full induction variable expansion for loops (currently
34 we expand only if the induction variable is dead afterward, which
35 is often the case). */
36
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "tm.h"
41 #include "diagnostic-core.h"
42
43 #include "rtl.h"
44 #include "hard-reg-set.h"
45 #include "flags.h"
46 #include "obstack.h"
47 #include "basic-block.h"
48 #include "output.h"
49 #include "df.h"
50 #include "function.h"
51 #include "insn-config.h"
52 #include "recog.h"
53 #include "timevar.h"
54 #include "tree-pass.h"
55
56
57 /* Find the root of unionfind tree (the representative of set). */
58
59 struct web_entry *
unionfind_root(struct web_entry * element)60 unionfind_root (struct web_entry *element)
61 {
62 struct web_entry *element1 = element, *element2;
63
64 while (element->pred)
65 element = element->pred;
66 while (element1->pred)
67 {
68 element2 = element1->pred;
69 element1->pred = element;
70 element1 = element2;
71 }
72 return element;
73 }
74
75 /* Union sets.
76 Return true if FIRST and SECOND points to the same web entry structure and
77 nothing is done. Otherwise, return false. */
78
79 bool
unionfind_union(struct web_entry * first,struct web_entry * second)80 unionfind_union (struct web_entry *first, struct web_entry *second)
81 {
82 first = unionfind_root (first);
83 second = unionfind_root (second);
84 if (first == second)
85 return true;
86 second->pred = first;
87 return false;
88 }
89
90 /* For INSN, union all defs and uses that are linked by match_dup.
91 FUN is the function that does the union. */
92
93 static void
union_match_dups(rtx insn,struct web_entry * def_entry,struct web_entry * use_entry,bool (* fun)(struct web_entry *,struct web_entry *))94 union_match_dups (rtx insn, struct web_entry *def_entry,
95 struct web_entry *use_entry,
96 bool (*fun) (struct web_entry *, struct web_entry *))
97 {
98 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
99 df_ref *use_link = DF_INSN_INFO_USES (insn_info);
100 df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
101 int i;
102
103 extract_insn (insn);
104
105 for (i = 0; i < recog_data.n_dups; i++)
106 {
107 int op = recog_data.dup_num[i];
108 enum op_type type = recog_data.operand_type[op];
109 df_ref *ref, *dupref;
110 struct web_entry *entry;
111
112 for (dupref = use_link; *dupref; dupref++)
113 if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
114 break;
115
116 if (*dupref == NULL
117 || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
118 continue;
119
120 ref = type == OP_IN ? use_link : def_link;
121 entry = type == OP_IN ? use_entry : def_entry;
122 for (; *ref; ref++)
123 if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
124 break;
125
126 (*fun) (use_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
127 }
128 }
129
130 /* For each use, all possible defs reaching it must come in the same
131 register, union them.
132 FUN is the function that does the union.
133
134 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
135 register, so that all uninitialized uses of the register can be
136 combined into a single web. We actually offset it by 2, because
137 the values 0 and 1 are reserved for use by entry_register. */
138
139 void
union_defs(df_ref use,struct web_entry * def_entry,unsigned int * used,struct web_entry * use_entry,bool (* fun)(struct web_entry *,struct web_entry *))140 union_defs (df_ref use, struct web_entry *def_entry,
141 unsigned int *used, struct web_entry *use_entry,
142 bool (*fun) (struct web_entry *, struct web_entry *))
143 {
144 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
145 struct df_link *link = DF_REF_CHAIN (use);
146 df_ref *eq_use_link;
147 df_ref *def_link;
148 rtx set;
149
150 if (insn_info)
151 {
152 rtx insn = insn_info->insn;
153 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
154 def_link = DF_INSN_INFO_DEFS (insn_info);
155 set = single_set (insn);
156 }
157 else
158 {
159 /* An artificial use. It links up with nothing. */
160 eq_use_link = NULL;
161 def_link = NULL;
162 set = NULL;
163 }
164
165 /* Union all occurrences of the same register in reg notes. */
166
167 if (eq_use_link)
168 while (*eq_use_link)
169 {
170 if (use != *eq_use_link
171 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
172 (*fun) (use_entry + DF_REF_ID (use),
173 use_entry + DF_REF_ID (*eq_use_link));
174 eq_use_link++;
175 }
176
177 /* Recognize trivial noop moves and attempt to keep them as noop. */
178
179 if (set
180 && SET_SRC (set) == DF_REF_REG (use)
181 && SET_SRC (set) == SET_DEST (set))
182 {
183 if (def_link)
184 while (*def_link)
185 {
186 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
187 (*fun) (use_entry + DF_REF_ID (use),
188 def_entry + DF_REF_ID (*def_link));
189 def_link++;
190 }
191 }
192
193 /* UD chains of uninitialized REGs are empty. Keeping all uses of
194 the same uninitialized REG in a single web is not necessary for
195 correctness, since the uses are undefined, but it's wasteful to
196 allocate one register or slot for each reference. Furthermore,
197 creating new pseudos for uninitialized references in debug insns
198 (see PR 42631) causes -fcompare-debug failures. We record the
199 number of the first uninitialized reference we found, and merge
200 with it any other uninitialized references to the same
201 register. */
202 if (!link)
203 {
204 int regno = REGNO (DF_REF_REAL_REG (use));
205 if (used[regno])
206 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
207 else
208 used[regno] = DF_REF_ID (use) + 2;
209 }
210
211 while (link)
212 {
213 (*fun) (use_entry + DF_REF_ID (use),
214 def_entry + DF_REF_ID (link->ref));
215 link = link->next;
216 }
217
218 /* A READ_WRITE use requires the corresponding def to be in the same
219 register. Find it and union. */
220 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
221 {
222 df_ref *link;
223
224 if (insn_info)
225 link = DF_INSN_INFO_DEFS (insn_info);
226 else
227 link = NULL;
228
229 if (link)
230 while (*link)
231 {
232 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
233 (*fun) (use_entry + DF_REF_ID (use),
234 def_entry + DF_REF_ID (*link));
235 link++;
236 }
237 }
238 }
239
240 /* Find the corresponding register for the given entry. */
241
242 static rtx
entry_register(struct web_entry * entry,df_ref ref,unsigned int * used)243 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
244 {
245 struct web_entry *root;
246 rtx reg, newreg;
247
248 /* Find the corresponding web and see if it has been visited. */
249 root = unionfind_root (entry);
250 if (root->reg)
251 return root->reg;
252
253 /* We are seeing this web for the first time, do the assignment. */
254 reg = DF_REF_REAL_REG (ref);
255
256 /* In case the original register is already assigned, generate new
257 one. Since we use USED to merge uninitialized refs into a single
258 web, we might found an element to be nonzero without our having
259 used it. Test for 1, because union_defs saves it for our use,
260 and there won't be any use for the other values when we get to
261 this point. */
262 if (used[REGNO (reg)] != 1)
263 newreg = reg, used[REGNO (reg)] = 1;
264 else
265 {
266 newreg = gen_reg_rtx (GET_MODE (reg));
267 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
268 REG_POINTER (newreg) = REG_POINTER (reg);
269 REG_ATTRS (newreg) = REG_ATTRS (reg);
270 if (dump_file)
271 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
272 REGNO (newreg));
273 }
274
275 root->reg = newreg;
276 return newreg;
277 }
278
279 /* Replace the reference by REG. */
280
281 static void
replace_ref(df_ref ref,rtx reg)282 replace_ref (df_ref ref, rtx reg)
283 {
284 rtx oldreg = DF_REF_REAL_REG (ref);
285 rtx *loc = DF_REF_REAL_LOC (ref);
286 unsigned int uid = DF_REF_INSN_UID (ref);
287
288 if (oldreg == reg)
289 return;
290 if (dump_file)
291 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
292 uid, REGNO (oldreg), REGNO (reg));
293 *loc = reg;
294 df_insn_rescan (DF_REF_INSN (ref));
295 }
296
297
298 static bool
gate_handle_web(void)299 gate_handle_web (void)
300 {
301 return (optimize > 0 && flag_web);
302 }
303
304 /* Main entry point. */
305
306 static unsigned int
web_main(void)307 web_main (void)
308 {
309 struct web_entry *def_entry;
310 struct web_entry *use_entry;
311 unsigned int max = max_reg_num ();
312 unsigned int *used;
313 basic_block bb;
314 unsigned int uses_num = 0;
315 rtx insn;
316
317 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
318 df_chain_add_problem (DF_UD_CHAIN);
319 df_analyze ();
320 df_set_flags (DF_DEFER_INSN_RESCAN);
321
322 /* Assign ids to the uses. */
323 FOR_ALL_BB (bb)
324 FOR_BB_INSNS (bb, insn)
325 {
326 unsigned int uid = INSN_UID (insn);
327 if (NONDEBUG_INSN_P (insn))
328 {
329 df_ref *use_rec;
330 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
331 {
332 df_ref use = *use_rec;
333 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
334 DF_REF_ID (use) = uses_num++;
335 }
336 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
337 {
338 df_ref use = *use_rec;
339 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
340 DF_REF_ID (use) = uses_num++;
341 }
342 }
343 }
344
345 /* Record the number of uses and defs at the beginning of the optimization. */
346 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
347 used = XCNEWVEC (unsigned, max);
348 use_entry = XCNEWVEC (struct web_entry, uses_num);
349
350 /* Produce the web. */
351 FOR_ALL_BB (bb)
352 FOR_BB_INSNS (bb, insn)
353 {
354 unsigned int uid = INSN_UID (insn);
355 if (NONDEBUG_INSN_P (insn))
356 {
357 df_ref *use_rec;
358 union_match_dups (insn, def_entry, use_entry, unionfind_union);
359 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
360 {
361 df_ref use = *use_rec;
362 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
363 union_defs (use, def_entry, used, use_entry, unionfind_union);
364 }
365 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
366 {
367 df_ref use = *use_rec;
368 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
369 union_defs (use, def_entry, used, use_entry, unionfind_union);
370 }
371 }
372 }
373
374 /* Update the instruction stream, allocating new registers for split pseudos
375 in progress. */
376 FOR_ALL_BB (bb)
377 FOR_BB_INSNS (bb, insn)
378 {
379 unsigned int uid = INSN_UID (insn);
380
381 if (NONDEBUG_INSN_P (insn)
382 /* Ignore naked clobber. For example, reg 134 in the second insn
383 of the following sequence will not be replaced.
384
385 (insn (clobber (reg:SI 134)))
386
387 (insn (set (reg:SI 0 r0) (reg:SI 134)))
388
389 Thus the later passes can optimize them away. */
390 && GET_CODE (PATTERN (insn)) != CLOBBER)
391 {
392 df_ref *use_rec;
393 df_ref *def_rec;
394 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
395 {
396 df_ref use = *use_rec;
397 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
398 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
399 }
400 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
401 {
402 df_ref use = *use_rec;
403 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
404 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
405 }
406 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
407 {
408 df_ref def = *def_rec;
409 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
410 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
411 }
412 }
413 }
414
415 free (def_entry);
416 free (use_entry);
417 free (used);
418 return 0;
419 }
420
421 struct rtl_opt_pass pass_web =
422 {
423 {
424 RTL_PASS,
425 "web", /* name */
426 gate_handle_web, /* gate */
427 web_main, /* execute */
428 NULL, /* sub */
429 NULL, /* next */
430 0, /* static_pass_number */
431 TV_WEB, /* tv_id */
432 0, /* properties_required */
433 0, /* properties_provided */
434 0, /* properties_destroyed */
435 0, /* todo_flags_start */
436 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */
437 }
438 };
439