1 /* Web construction code for GNU compiler.
2 Contributed by Jan Hubicka.
3 Copyright (C) 2001-2013 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
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.
24
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.
28
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). */
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "diagnostic-core.h"
41
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"
52
53
54 /* Find the root of unionfind tree (the representative of set). */
55
56 web_entry_base *
unionfind_root()57 web_entry_base::unionfind_root ()
58 {
59 web_entry_base *element = this, *element1 = this, *element2;
60
61 while (element->pred ())
62 element = element->pred ();
63 while (element1->pred ())
64 {
65 element2 = element1->pred ();
66 element1->set_pred (element);
67 element1 = element2;
68 }
69 return element;
70 }
71
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. */
75
76 bool
unionfind_union(web_entry_base * first,web_entry_base * second)77 unionfind_union (web_entry_base *first, web_entry_base *second)
78 {
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;
85 }
86
87 class web_entry : public web_entry_base
88 {
89 private:
90 rtx reg_pvt;
91
92 public:
reg()93 rtx reg () { return reg_pvt; }
set_reg(rtx r)94 void set_reg (rtx r) { reg_pvt = r; }
95 };
96
97 /* For INSN, union all defs and uses that are linked by match_dup.
98 FUN is the function that does the union. */
99
100 static void
union_match_dups(rtx insn,web_entry * def_entry,web_entry * use_entry,bool (* fun)(web_entry_base *,web_entry_base *))101 union_match_dups (rtx insn, web_entry *def_entry, web_entry *use_entry,
102 bool (*fun) (web_entry_base *, web_entry_base *))
103 {
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;
109
110 extract_insn (insn);
111
112 for (i = 0; i < recog_data.n_dups; i++)
113 {
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;
118
119 for (dup_entry = use_entry, dupref = use_link; *dupref; dupref++)
120 if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
121 break;
122
123 if (*dupref == NULL && type == OP_INOUT)
124 {
125
126 for (dup_entry = def_entry, dupref = def_link; *dupref; dupref++)
127 if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
128 break;
129 }
130 /* ??? *DUPREF can still be zero, because when an operand matches
131 a memory, DF_REF_LOC (use_link[n]) points to the register part
132 of the address, whereas recog_data.dup_loc[m] points to the
133 entire memory ref, thus we fail to find the duplicate entry,
134 even though it is there.
135 Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
136 -O3 -fomit-frame-pointer -funroll-loops */
137 if (*dupref == NULL
138 || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
139 continue;
140
141 ref = type == OP_IN ? use_link : def_link;
142 entry = type == OP_IN ? use_entry : def_entry;
143 for (; *ref; ref++)
144 if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
145 break;
146
147 if (!*ref && type == OP_INOUT)
148 {
149 for (ref = use_link, entry = use_entry; *ref; ref++)
150 if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
151 break;
152 }
153
154 gcc_assert (*ref);
155 (*fun) (dup_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
156 }
157 }
158
159 /* For each use, all possible defs reaching it must come in the same
160 register, union them.
161 FUN is the function that does the union.
162
163 In USED, we keep the DF_REF_ID of the first uninitialized uses of a
164 register, so that all uninitialized uses of the register can be
165 combined into a single web. We actually offset it by 2, because
166 the values 0 and 1 are reserved for use by entry_register. */
167
168 void
union_defs(df_ref use,web_entry * def_entry,unsigned int * used,web_entry * use_entry,bool (* fun)(web_entry_base *,web_entry_base *))169 union_defs (df_ref use, web_entry *def_entry,
170 unsigned int *used, web_entry *use_entry,
171 bool (*fun) (web_entry_base *, web_entry_base *))
172 {
173 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
174 struct df_link *link = DF_REF_CHAIN (use);
175 df_ref *eq_use_link;
176 df_ref *def_link;
177 rtx set;
178
179 if (insn_info)
180 {
181 rtx insn = insn_info->insn;
182 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
183 def_link = DF_INSN_INFO_DEFS (insn_info);
184 set = single_set (insn);
185 }
186 else
187 {
188 /* An artificial use. It links up with nothing. */
189 eq_use_link = NULL;
190 def_link = NULL;
191 set = NULL;
192 }
193
194 /* Union all occurrences of the same register in reg notes. */
195
196 if (eq_use_link)
197 while (*eq_use_link)
198 {
199 if (use != *eq_use_link
200 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
201 (*fun) (use_entry + DF_REF_ID (use),
202 use_entry + DF_REF_ID (*eq_use_link));
203 eq_use_link++;
204 }
205
206 /* Recognize trivial noop moves and attempt to keep them as noop. */
207
208 if (set
209 && SET_SRC (set) == DF_REF_REG (use)
210 && SET_SRC (set) == SET_DEST (set))
211 {
212 if (def_link)
213 while (*def_link)
214 {
215 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
216 (*fun) (use_entry + DF_REF_ID (use),
217 def_entry + DF_REF_ID (*def_link));
218 def_link++;
219 }
220 }
221
222 /* UD chains of uninitialized REGs are empty. Keeping all uses of
223 the same uninitialized REG in a single web is not necessary for
224 correctness, since the uses are undefined, but it's wasteful to
225 allocate one register or slot for each reference. Furthermore,
226 creating new pseudos for uninitialized references in debug insns
227 (see PR 42631) causes -fcompare-debug failures. We record the
228 number of the first uninitialized reference we found, and merge
229 with it any other uninitialized references to the same
230 register. */
231 if (!link)
232 {
233 int regno = REGNO (DF_REF_REAL_REG (use));
234 if (used[regno])
235 (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
236 else
237 used[regno] = DF_REF_ID (use) + 2;
238 }
239
240 while (link)
241 {
242 (*fun) (use_entry + DF_REF_ID (use),
243 def_entry + DF_REF_ID (link->ref));
244 link = link->next;
245 }
246
247 /* A READ_WRITE use requires the corresponding def to be in the same
248 register. Find it and union. */
249 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
250 {
251 df_ref *link;
252
253 if (insn_info)
254 link = DF_INSN_INFO_DEFS (insn_info);
255 else
256 link = NULL;
257
258 if (link)
259 while (*link)
260 {
261 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
262 (*fun) (use_entry + DF_REF_ID (use),
263 def_entry + DF_REF_ID (*link));
264 link++;
265 }
266 }
267 }
268
269 /* Find the corresponding register for the given entry. */
270
271 static rtx
entry_register(web_entry * entry,df_ref ref,unsigned int * used)272 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
273 {
274 web_entry *root;
275 rtx reg, newreg;
276
277 /* Find the corresponding web and see if it has been visited. */
278 root = (web_entry *)entry->unionfind_root ();
279 if (root->reg ())
280 return root->reg ();
281
282 /* We are seeing this web for the first time, do the assignment. */
283 reg = DF_REF_REAL_REG (ref);
284
285 /* In case the original register is already assigned, generate new
286 one. Since we use USED to merge uninitialized refs into a single
287 web, we might found an element to be nonzero without our having
288 used it. Test for 1, because union_defs saves it for our use,
289 and there won't be any use for the other values when we get to
290 this point. */
291 if (used[REGNO (reg)] != 1)
292 newreg = reg, used[REGNO (reg)] = 1;
293 else
294 {
295 newreg = gen_reg_rtx (GET_MODE (reg));
296 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
297 REG_POINTER (newreg) = REG_POINTER (reg);
298 REG_ATTRS (newreg) = REG_ATTRS (reg);
299 if (dump_file)
300 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
301 REGNO (newreg));
302 }
303
304 root->set_reg (newreg);
305 return newreg;
306 }
307
308 /* Replace the reference by REG. */
309
310 static void
replace_ref(df_ref ref,rtx reg)311 replace_ref (df_ref ref, rtx reg)
312 {
313 rtx oldreg = DF_REF_REAL_REG (ref);
314 rtx *loc = DF_REF_REAL_LOC (ref);
315 unsigned int uid = DF_REF_INSN_UID (ref);
316
317 if (oldreg == reg)
318 return;
319 if (dump_file)
320 fprintf (dump_file, "Updating insn %i (%i->%i)\n",
321 uid, REGNO (oldreg), REGNO (reg));
322 *loc = reg;
323 df_insn_rescan (DF_REF_INSN (ref));
324 }
325
326
327 static bool
gate_handle_web(void)328 gate_handle_web (void)
329 {
330 return (optimize > 0 && flag_web);
331 }
332
333 /* Main entry point. */
334
335 static unsigned int
web_main(void)336 web_main (void)
337 {
338 web_entry *def_entry;
339 web_entry *use_entry;
340 unsigned int max = max_reg_num ();
341 unsigned int *used;
342 basic_block bb;
343 unsigned int uses_num = 0;
344 rtx insn;
345
346 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
347 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
348 df_chain_add_problem (DF_UD_CHAIN);
349 df_analyze ();
350 df_set_flags (DF_DEFER_INSN_RESCAN);
351
352 /* Assign ids to the uses. */
353 FOR_ALL_BB (bb)
354 FOR_BB_INSNS (bb, insn)
355 {
356 unsigned int uid = INSN_UID (insn);
357 if (NONDEBUG_INSN_P (insn))
358 {
359 df_ref *use_rec;
360 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
361 {
362 df_ref use = *use_rec;
363 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
364 DF_REF_ID (use) = uses_num++;
365 }
366 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
367 {
368 df_ref use = *use_rec;
369 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
370 DF_REF_ID (use) = uses_num++;
371 }
372 }
373 }
374
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);
379
380 /* Produce the web. */
381 FOR_ALL_BB (bb)
382 FOR_BB_INSNS (bb, insn)
383 {
384 unsigned int uid = INSN_UID (insn);
385 if (NONDEBUG_INSN_P (insn))
386 {
387 df_ref *use_rec;
388 union_match_dups (insn, def_entry, use_entry, unionfind_union);
389 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
390 {
391 df_ref use = *use_rec;
392 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
393 union_defs (use, def_entry, used, use_entry, unionfind_union);
394 }
395 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
396 {
397 df_ref use = *use_rec;
398 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
399 union_defs (use, def_entry, used, use_entry, unionfind_union);
400 }
401 }
402 }
403
404 /* Update the instruction stream, allocating new registers for split pseudos
405 in progress. */
406 FOR_ALL_BB (bb)
407 FOR_BB_INSNS (bb, insn)
408 {
409 unsigned int uid = INSN_UID (insn);
410
411 if (NONDEBUG_INSN_P (insn)
412 /* Ignore naked clobber. For example, reg 134 in the second insn
413 of the following sequence will not be replaced.
414
415 (insn (clobber (reg:SI 134)))
416
417 (insn (set (reg:SI 0 r0) (reg:SI 134)))
418
419 Thus the later passes can optimize them away. */
420 && GET_CODE (PATTERN (insn)) != CLOBBER)
421 {
422 df_ref *use_rec;
423 df_ref *def_rec;
424 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
425 {
426 df_ref use = *use_rec;
427 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
428 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
429 }
430 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
431 {
432 df_ref use = *use_rec;
433 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
434 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
435 }
436 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
437 {
438 df_ref def = *def_rec;
439 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
440 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
441 }
442 }
443 }
444
445 free (def_entry);
446 free (use_entry);
447 free (used);
448 return 0;
449 }
450
451 struct rtl_opt_pass pass_web =
452 {
453 {
454 RTL_PASS,
455 "web", /* name */
456 OPTGROUP_NONE, /* optinfo_flags */
457 gate_handle_web, /* gate */
458 web_main, /* execute */
459 NULL, /* sub */
460 NULL, /* next */
461 0, /* static_pass_number */
462 TV_WEB, /* tv_id */
463 0, /* properties_required */
464 0, /* properties_provided */
465 0, /* properties_destroyed */
466 0, /* todo_flags_start */
467 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */
468 }
469 };
470