Mercurial > hg > CbC > CbC_gcc
annotate gcc/web.c @ 59:5b5b9ea5b220
fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 15 Feb 2010 17:22:24 +0900 |
parents | 77e2b8dfacca |
children | b7f97abdc517 |
rev | line source |
---|---|
0 | 1 /* Web construction code for GNU compiler. |
2 Contributed by Jan Hubicka. | |
3 Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008 | |
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 - 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. | |
36 | |
37 Other optimization passes can benefit from the infrastructure too. | |
38 | |
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). */ | |
44 | |
45 #include "config.h" | |
46 #include "system.h" | |
47 #include "coretypes.h" | |
48 #include "tm.h" | |
49 #include "toplev.h" | |
50 | |
51 #include "rtl.h" | |
52 #include "hard-reg-set.h" | |
53 #include "flags.h" | |
54 #include "obstack.h" | |
55 #include "basic-block.h" | |
56 #include "output.h" | |
57 #include "df.h" | |
58 #include "function.h" | |
59 #include "timevar.h" | |
60 #include "tree-pass.h" | |
61 | |
62 | |
63 static rtx entry_register (struct web_entry *, df_ref, char *); | |
64 static void replace_ref (df_ref, rtx); | |
65 | |
66 /* Find the root of unionfind tree (the representative of set). */ | |
67 | |
68 struct web_entry * | |
69 unionfind_root (struct web_entry *element) | |
70 { | |
71 struct web_entry *element1 = element, *element2; | |
72 | |
73 while (element->pred) | |
74 element = element->pred; | |
75 while (element1->pred) | |
76 { | |
77 element2 = element1->pred; | |
78 element1->pred = element; | |
79 element1 = element2; | |
80 } | |
81 return element; | |
82 } | |
83 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
84 /* Union sets. |
0 | 85 Return true if FIRST and SECOND points to the same web entry structure and |
86 nothing is done. Otherwise, return false. */ | |
87 | |
88 bool | |
89 unionfind_union (struct web_entry *first, struct web_entry *second) | |
90 { | |
91 first = unionfind_root (first); | |
92 second = unionfind_root (second); | |
93 if (first == second) | |
94 return true; | |
95 second->pred = first; | |
96 return false; | |
97 } | |
98 | |
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. */ | |
102 | |
103 void | |
104 union_defs (df_ref use, struct web_entry *def_entry, | |
105 struct web_entry *use_entry, | |
106 bool (*fun) (struct web_entry *, struct web_entry *)) | |
107 { | |
108 struct df_insn_info *insn_info = DF_REF_INSN_INFO (use); | |
109 struct df_link *link = DF_REF_CHAIN (use); | |
110 df_ref *use_link; | |
111 df_ref *eq_use_link; | |
112 df_ref *def_link; | |
113 rtx set; | |
114 | |
115 if (insn_info) | |
116 { | |
117 rtx insn = insn_info->insn; | |
118 use_link = DF_INSN_INFO_USES (insn_info); | |
119 eq_use_link = DF_INSN_INFO_EQ_USES (insn_info); | |
120 def_link = DF_INSN_INFO_DEFS (insn_info); | |
121 set = single_set (insn); | |
122 } | |
123 else | |
124 { | |
125 /* An artificial use. It links up with nothing. */ | |
126 use_link = NULL; | |
127 eq_use_link = NULL; | |
128 def_link = NULL; | |
129 set = NULL; | |
130 } | |
131 | |
132 /* Some instructions may use match_dup for their operands. In case the | |
133 operands are dead, we will assign them different pseudos, creating | |
134 invalid instructions, so union all uses of the same operand for each | |
135 insn. */ | |
136 | |
137 if (use_link) | |
138 while (*use_link) | |
139 { | |
140 if (use != *use_link | |
141 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link)) | |
142 (*fun) (use_entry + DF_REF_ID (use), | |
143 use_entry + DF_REF_ID (*use_link)); | |
144 use_link++; | |
145 } | |
146 | |
147 if (eq_use_link) | |
148 while (*eq_use_link) | |
149 { | |
150 if (use != *eq_use_link | |
151 && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link)) | |
152 (*fun) (use_entry + DF_REF_ID (use), | |
153 use_entry + DF_REF_ID (*eq_use_link)); | |
154 eq_use_link++; | |
155 } | |
156 | |
157 /* Recognize trivial noop moves and attempt to keep them as noop. */ | |
158 | |
159 if (set | |
160 && SET_SRC (set) == DF_REF_REG (use) | |
161 && SET_SRC (set) == SET_DEST (set)) | |
162 { | |
163 if (def_link) | |
164 while (*def_link) | |
165 { | |
166 if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link)) | |
167 (*fun) (use_entry + DF_REF_ID (use), | |
168 def_entry + DF_REF_ID (*def_link)); | |
169 def_link++; | |
170 } | |
171 } | |
172 while (link) | |
173 { | |
174 (*fun) (use_entry + DF_REF_ID (use), | |
175 def_entry + DF_REF_ID (link->ref)); | |
176 link = link->next; | |
177 } | |
178 | |
179 /* A READ_WRITE use requires the corresponding def to be in the same | |
180 register. Find it and union. */ | |
181 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) | |
182 { | |
183 df_ref *link; | |
184 | |
185 if (insn_info) | |
186 link = DF_INSN_INFO_DEFS (insn_info); | |
187 else | |
188 link = NULL; | |
189 | |
190 if (link) | |
191 while (*link) | |
192 { | |
193 if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use)) | |
194 (*fun) (use_entry + DF_REF_ID (use), | |
195 def_entry + DF_REF_ID (*link)); | |
196 link++; | |
197 } | |
198 } | |
199 } | |
200 | |
201 /* Find the corresponding register for the given entry. */ | |
202 | |
203 static rtx | |
204 entry_register (struct web_entry *entry, df_ref ref, char *used) | |
205 { | |
206 struct web_entry *root; | |
207 rtx reg, newreg; | |
208 | |
209 /* Find the corresponding web and see if it has been visited. */ | |
210 root = unionfind_root (entry); | |
211 if (root->reg) | |
212 return root->reg; | |
213 | |
214 /* We are seeing this web for the first time, do the assignment. */ | |
215 reg = DF_REF_REAL_REG (ref); | |
216 | |
217 /* In case the original register is already assigned, generate new one. */ | |
218 if (!used[REGNO (reg)]) | |
219 newreg = reg, used[REGNO (reg)] = 1; | |
220 else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/) | |
221 { | |
222 newreg = reg; | |
223 if (dump_file) | |
224 fprintf (dump_file, | |
225 "New web forced to keep reg=%i (user variable)\n", | |
226 REGNO (reg)); | |
227 } | |
228 else | |
229 { | |
230 newreg = gen_reg_rtx (GET_MODE (reg)); | |
231 REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); | |
232 REG_POINTER (newreg) = REG_POINTER (reg); | |
233 REG_ATTRS (newreg) = REG_ATTRS (reg); | |
234 if (dump_file) | |
235 fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), | |
236 REGNO (newreg)); | |
237 } | |
238 | |
239 root->reg = newreg; | |
240 return newreg; | |
241 } | |
242 | |
243 /* Replace the reference by REG. */ | |
244 | |
245 static void | |
246 replace_ref (df_ref ref, rtx reg) | |
247 { | |
248 rtx oldreg = DF_REF_REAL_REG (ref); | |
249 rtx *loc = DF_REF_REAL_LOC (ref); | |
250 unsigned int uid = DF_REF_INSN_UID (ref); | |
251 | |
252 if (oldreg == reg) | |
253 return; | |
254 if (dump_file) | |
255 fprintf (dump_file, "Updating insn %i (%i->%i)\n", | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
256 uid, REGNO (oldreg), REGNO (reg)); |
0 | 257 *loc = reg; |
258 df_insn_rescan (DF_REF_INSN (ref)); | |
259 } | |
260 | |
261 | |
262 static bool | |
263 gate_handle_web (void) | |
264 { | |
265 return (optimize > 0 && flag_web); | |
266 } | |
267 | |
268 /* Main entry point. */ | |
269 | |
270 static unsigned int | |
271 web_main (void) | |
272 { | |
273 struct web_entry *def_entry; | |
274 struct web_entry *use_entry; | |
275 unsigned int max = max_reg_num (); | |
276 char *used; | |
277 basic_block bb; | |
278 unsigned int uses_num = 0; | |
279 rtx insn; | |
280 | |
281 df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES); | |
282 df_chain_add_problem (DF_UD_CHAIN); | |
283 df_analyze (); | |
284 df_set_flags (DF_DEFER_INSN_RESCAN); | |
285 | |
286 /* Assign ids to the uses. */ | |
287 FOR_ALL_BB (bb) | |
288 FOR_BB_INSNS (bb, insn) | |
289 { | |
290 unsigned int uid = INSN_UID (insn); | |
291 if (INSN_P (insn)) | |
292 { | |
293 df_ref *use_rec; | |
294 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) | |
295 { | |
296 df_ref use = *use_rec; | |
297 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
298 DF_REF_ID (use) = uses_num++; | |
299 } | |
300 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) | |
301 { | |
302 df_ref use = *use_rec; | |
303 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
304 DF_REF_ID (use) = uses_num++; | |
305 } | |
306 } | |
307 } | |
308 | |
309 /* Record the number of uses and defs at the beginning of the optimization. */ | |
310 def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE()); | |
311 used = XCNEWVEC (char, max); | |
312 use_entry = XCNEWVEC (struct web_entry, uses_num); | |
313 | |
314 /* Produce the web. */ | |
315 FOR_ALL_BB (bb) | |
316 FOR_BB_INSNS (bb, insn) | |
317 { | |
318 unsigned int uid = INSN_UID (insn); | |
319 if (INSN_P (insn)) | |
320 { | |
321 df_ref *use_rec; | |
322 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) | |
323 { | |
324 df_ref use = *use_rec; | |
325 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
326 union_defs (use, def_entry, use_entry, unionfind_union); | |
327 } | |
328 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) | |
329 { | |
330 df_ref use = *use_rec; | |
331 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
332 union_defs (use, def_entry, use_entry, unionfind_union); | |
333 } | |
334 } | |
335 } | |
336 | |
337 /* Update the instruction stream, allocating new registers for split pseudos | |
338 in progress. */ | |
339 FOR_ALL_BB (bb) | |
340 FOR_BB_INSNS (bb, insn) | |
341 { | |
342 unsigned int uid = INSN_UID (insn); | |
343 if (INSN_P (insn)) | |
344 { | |
345 df_ref *use_rec; | |
346 df_ref *def_rec; | |
347 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) | |
348 { | |
349 df_ref use = *use_rec; | |
350 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
351 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); | |
352 } | |
353 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) | |
354 { | |
355 df_ref use = *use_rec; | |
356 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) | |
357 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); | |
358 } | |
359 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) | |
360 { | |
361 df_ref def = *def_rec; | |
362 if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER) | |
363 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used)); | |
364 } | |
365 } | |
366 } | |
367 | |
368 free (def_entry); | |
369 free (use_entry); | |
370 free (used); | |
371 return 0; | |
372 } | |
373 | |
374 struct rtl_opt_pass pass_web = | |
375 { | |
376 { | |
377 RTL_PASS, | |
378 "web", /* name */ | |
379 gate_handle_web, /* gate */ | |
380 web_main, /* execute */ | |
381 NULL, /* sub */ | |
382 NULL, /* next */ | |
383 0, /* static_pass_number */ | |
384 TV_WEB, /* tv_id */ | |
385 0, /* properties_required */ | |
386 0, /* properties_provided */ | |
387 0, /* properties_destroyed */ | |
388 0, /* todo_flags_start */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
389 TODO_df_finish | TODO_verify_rtl_sharing | |
0 | 390 TODO_dump_func /* todo_flags_finish */ |
391 } | |
392 }; | |
393 |