]>
Commit | Line | Data |
---|---|---|
62551c66 | 1 | /* Web construction code for GNU compiler. |
2426d8dd | 2 | Contributed by Jan Hubicka. |
4d779342 DB |
3 | Copyright (C) 2001, 2002, 2004, 2006 |
4 | Free Software Foundation, Inc. | |
62551c66 JH |
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 2, 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 COPYING. If not, write to the Free | |
366ccddb KC |
20 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
21 | 02110-1301, USA. */ | |
62551c66 | 22 | |
2426d8dd | 23 | /* Simple optimization pass that splits independent uses of each pseudo, |
d91edf86 | 24 | increasing effectiveness of other optimizations. The optimization can |
2426d8dd | 25 | serve as an example of use for the dataflow module. |
62551c66 | 26 | |
2426d8dd EB |
27 | We don't split registers with REG_USERVAR set unless -fmessy-debugging |
28 | is specified, because debugging information about such split variables | |
29 | is almost unusable. | |
62551c66 JH |
30 | |
31 | TODO | |
2426d8dd EB |
32 | - Add code to keep debugging up-to-date after splitting user variable |
33 | pseudos. This can be done by keeping track of all the pseudos used | |
34 | for the variable and using life analysis information before reload | |
35 | to determine which one is live and, in case more than one are live, | |
36 | choose the one with the latest definition. | |
62551c66 | 37 | |
2426d8dd | 38 | Other optimization passes can benefit from the infrastructure too. |
62551c66 | 39 | |
2426d8dd EB |
40 | - We may use profile information and ignore infrequent use for the |
41 | purpose of web unifying, inserting the compensation code later to | |
42 | implement full induction variable expansion for loops (currently | |
43 | we expand only if the induction variable is dead afterward, which | |
44 | is often the case). */ | |
62551c66 JH |
45 | |
46 | #include "config.h" | |
47 | #include "system.h" | |
48 | #include "coretypes.h" | |
49 | #include "tm.h" | |
50 | #include "toplev.h" | |
51 | ||
52 | #include "rtl.h" | |
53 | #include "hard-reg-set.h" | |
54 | #include "flags.h" | |
7932a3db | 55 | #include "obstack.h" |
62551c66 JH |
56 | #include "basic-block.h" |
57 | #include "output.h" | |
58 | #include "df.h" | |
59 | #include "function.h" | |
ef330312 PB |
60 | #include "timevar.h" |
61 | #include "tree-pass.h" | |
62551c66 JH |
62 | |
63 | ||
4d779342 DB |
64 | static rtx entry_register (struct web_entry *, struct df_ref *, char *); |
65 | static void replace_ref (struct df_ref *, rtx); | |
62551c66 | 66 | |
2426d8dd | 67 | /* Find the root of unionfind tree (the representative of set). */ |
62551c66 | 68 | |
8cd37d0b | 69 | struct web_entry * |
9373164a | 70 | unionfind_root (struct web_entry *element) |
62551c66 JH |
71 | { |
72 | struct web_entry *element1 = element, *element2; | |
73 | ||
74 | while (element->pred) | |
75 | element = element->pred; | |
76 | while (element1->pred) | |
77 | { | |
78 | element2 = element1->pred; | |
79 | element1->pred = element; | |
80 | element1 = element2; | |
81 | } | |
82 | return element; | |
83 | } | |
84 | ||
8cd37d0b RL |
85 | /* Union sets. |
86 | Return true if FIRST and SECOND points to the same web entry structure and | |
87 | nothing is done. Otherwise, return false. */ | |
62551c66 | 88 | |
8cd37d0b | 89 | bool |
9373164a | 90 | unionfind_union (struct web_entry *first, struct web_entry *second) |
62551c66 JH |
91 | { |
92 | first = unionfind_root (first); | |
93 | second = unionfind_root (second); | |
94 | if (first == second) | |
8cd37d0b | 95 | return true; |
62551c66 | 96 | second->pred = first; |
8cd37d0b | 97 | return false; |
62551c66 JH |
98 | } |
99 | ||
2426d8dd | 100 | /* For each use, all possible defs reaching it must come in the same |
8cd37d0b RL |
101 | register, union them. |
102 | FUN is the function that does the union. */ | |
62551c66 | 103 | |
8cd37d0b | 104 | void |
4d779342 | 105 | union_defs (struct df *df, struct df_ref *use, struct web_entry *def_entry, |
8cd37d0b RL |
106 | struct web_entry *use_entry, |
107 | bool (*fun) (struct web_entry *, struct web_entry *)) | |
62551c66 JH |
108 | { |
109 | rtx insn = DF_REF_INSN (use); | |
110 | struct df_link *link = DF_REF_CHAIN (use); | |
8cd37d0b RL |
111 | struct df_ref *use_link; |
112 | struct df_ref *def_link; | |
113 | rtx set; | |
114 | ||
115 | if (insn) | |
116 | { | |
117 | use_link = DF_INSN_USES (df, insn); | |
118 | def_link = DF_INSN_DEFS (df, insn); | |
119 | set = single_set (insn); | |
120 | } | |
121 | else | |
122 | { | |
123 | use_link = NULL; | |
124 | def_link = NULL; | |
125 | set = NULL; | |
126 | } | |
62551c66 | 127 | |
2426d8dd EB |
128 | /* Some instructions may use match_dup for their operands. In case the |
129 | operands are dead, we will assign them different pseudos, creating | |
130 | invalid instructions, so union all uses of the same operand for each | |
62551c66 JH |
131 | insn. */ |
132 | ||
133 | while (use_link) | |
134 | { | |
4d779342 DB |
135 | if (use != use_link |
136 | && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link)) | |
8cd37d0b RL |
137 | (*fun) (use_entry + DF_REF_ID (use), |
138 | use_entry + DF_REF_ID (use_link)); | |
4d779342 | 139 | use_link = use_link->next_ref; |
62551c66 JH |
140 | } |
141 | ||
2426d8dd EB |
142 | /* Recognize trivial noop moves and attempt to keep them as noop. |
143 | While most of noop moves should be removed, we still keep some | |
144 | of them at libcall boundaries and such. */ | |
62551c66 JH |
145 | |
146 | if (set | |
147 | && SET_SRC (set) == DF_REF_REG (use) | |
148 | && SET_SRC (set) == SET_DEST (set)) | |
149 | { | |
150 | while (def_link) | |
151 | { | |
4d779342 | 152 | if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link)) |
8cd37d0b RL |
153 | (*fun) (use_entry + DF_REF_ID (use), |
154 | def_entry + DF_REF_ID (def_link)); | |
4d779342 | 155 | def_link = def_link->next_ref; |
62551c66 JH |
156 | } |
157 | } | |
158 | while (link) | |
159 | { | |
8cd37d0b RL |
160 | (*fun) (use_entry + DF_REF_ID (use), |
161 | def_entry + DF_REF_ID (link->ref)); | |
62551c66 JH |
162 | link = link->next; |
163 | } | |
164 | ||
2426d8dd | 165 | /* A READ_WRITE use requires the corresponding def to be in the same |
62551c66 JH |
166 | register. Find it and union. */ |
167 | if (use->flags & DF_REF_READ_WRITE) | |
168 | { | |
8cd37d0b RL |
169 | struct df_ref *link; |
170 | ||
171 | if (DF_REF_INSN (use)) | |
172 | link = DF_INSN_DEFS (df, DF_REF_INSN (use)); | |
173 | else | |
174 | link = NULL; | |
62551c66 | 175 | |
909b7f16 RZ |
176 | while (link) |
177 | { | |
4d779342 | 178 | if (DF_REF_REAL_REG (link) == DF_REF_REAL_REG (use)) |
8cd37d0b RL |
179 | (*fun) (use_entry + DF_REF_ID (use), |
180 | def_entry + DF_REF_ID (link)); | |
4d779342 | 181 | link = link->next_ref; |
909b7f16 | 182 | } |
62551c66 JH |
183 | } |
184 | } | |
185 | ||
2426d8dd | 186 | /* Find the corresponding register for the given entry. */ |
62551c66 JH |
187 | |
188 | static rtx | |
4d779342 | 189 | entry_register (struct web_entry *entry, struct df_ref *ref, char *used) |
62551c66 JH |
190 | { |
191 | struct web_entry *root; | |
192 | rtx reg, newreg; | |
193 | ||
2426d8dd | 194 | /* Find the corresponding web and see if it has been visited. */ |
62551c66 JH |
195 | root = unionfind_root (entry); |
196 | if (root->reg) | |
197 | return root->reg; | |
198 | ||
2426d8dd | 199 | /* We are seeing this web for the first time, do the assignment. */ |
62551c66 JH |
200 | reg = DF_REF_REAL_REG (ref); |
201 | ||
202 | /* In case the original register is already assigned, generate new one. */ | |
203 | if (!used[REGNO (reg)]) | |
204 | newreg = reg, used[REGNO (reg)] = 1; | |
205 | else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/) | |
206 | { | |
207 | newreg = reg; | |
c263766c RH |
208 | if (dump_file) |
209 | fprintf (dump_file, | |
62551c66 JH |
210 | "New web forced to keep reg=%i (user variable)\n", |
211 | REGNO (reg)); | |
212 | } | |
62551c66 JH |
213 | else |
214 | { | |
215 | newreg = gen_reg_rtx (GET_MODE (reg)); | |
216 | REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); | |
217 | REG_POINTER (newreg) = REG_POINTER (reg); | |
62551c66 | 218 | REG_ATTRS (newreg) = REG_ATTRS (reg); |
c263766c RH |
219 | if (dump_file) |
220 | fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), | |
62551c66 JH |
221 | REGNO (newreg)); |
222 | } | |
223 | ||
224 | root->reg = newreg; | |
225 | return newreg; | |
226 | } | |
227 | ||
228 | /* Replace the reference by REG. */ | |
229 | ||
230 | static void | |
4d779342 | 231 | replace_ref (struct df_ref *ref, rtx reg) |
62551c66 JH |
232 | { |
233 | rtx oldreg = DF_REF_REAL_REG (ref); | |
234 | rtx *loc = DF_REF_REAL_LOC (ref); | |
235 | ||
236 | if (oldreg == reg) | |
237 | return; | |
c263766c RH |
238 | if (dump_file) |
239 | fprintf (dump_file, "Updating insn %i (%i->%i)\n", | |
62551c66 JH |
240 | INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg)); |
241 | *loc = reg; | |
242 | } | |
243 | ||
62551c66 JH |
244 | /* Main entry point. */ |
245 | ||
65727068 | 246 | static void |
9373164a | 247 | web_main (void) |
62551c66 JH |
248 | { |
249 | struct df *df; | |
250 | struct web_entry *def_entry; | |
251 | struct web_entry *use_entry; | |
252 | unsigned int i; | |
253 | int max = max_reg_num (); | |
254 | char *used; | |
62551c66 | 255 | |
4d779342 DB |
256 | df = df_init (DF_EQUIV_NOTES); |
257 | df_chain_add_problem (df, DF_UD_CHAIN); | |
258 | df_analyze (df); | |
259 | df_reorganize_refs (&df->def_info); | |
260 | df_reorganize_refs (&df->use_info); | |
62551c66 | 261 | |
5ed6ace5 MD |
262 | def_entry = XCNEWVEC (struct web_entry, DF_DEFS_SIZE (df)); |
263 | use_entry = XCNEWVEC (struct web_entry, DF_USES_SIZE (df)); | |
264 | used = XCNEWVEC (char, max); | |
62551c66 | 265 | |
c263766c | 266 | if (dump_file) |
4d779342 | 267 | df_dump (df, dump_file); |
62551c66 JH |
268 | |
269 | /* Produce the web. */ | |
4d779342 | 270 | for (i = 0; i < DF_USES_SIZE (df); i++) |
8cd37d0b | 271 | union_defs (df, DF_USES_GET (df, i), def_entry, use_entry, unionfind_union); |
62551c66 | 272 | |
62551c66 JH |
273 | /* Update the instruction stream, allocating new registers for split pseudos |
274 | in progress. */ | |
4d779342 DB |
275 | for (i = 0; i < DF_USES_SIZE (df); i++) |
276 | replace_ref (DF_USES_GET (df, i), | |
277 | entry_register (use_entry + i, DF_USES_GET (df, i), used)); | |
278 | for (i = 0; i < DF_DEFS_SIZE (df); i++) | |
279 | replace_ref (DF_DEFS_GET (df, i), | |
280 | entry_register (def_entry + i, DF_DEFS_GET (df, i), used)); | |
62551c66 | 281 | |
2426d8dd EB |
282 | /* Dataflow information is corrupt here, but it can be easily updated |
283 | by creating new entries for new registers and updates or calling | |
62551c66 JH |
284 | df_insns_modify. */ |
285 | free (def_entry); | |
286 | free (use_entry); | |
287 | free (used); | |
62551c66 | 288 | df_finish (df); |
4d779342 | 289 | df = NULL; |
62551c66 | 290 | } |
ef330312 PB |
291 | \f |
292 | static bool | |
293 | gate_handle_web (void) | |
294 | { | |
295 | return (optimize > 0 && flag_web); | |
296 | } | |
297 | ||
c2924966 | 298 | static unsigned int |
ef330312 PB |
299 | rest_of_handle_web (void) |
300 | { | |
301 | web_main (); | |
302 | delete_trivially_dead_insns (get_insns (), max_reg_num ()); | |
303 | cleanup_cfg (CLEANUP_EXPENSIVE); | |
304 | reg_scan (get_insns (), max_reg_num ()); | |
c2924966 | 305 | return 0; |
ef330312 PB |
306 | } |
307 | ||
308 | struct tree_opt_pass pass_web = | |
309 | { | |
310 | "web", /* name */ | |
311 | gate_handle_web, /* gate */ | |
312 | rest_of_handle_web, /* execute */ | |
313 | NULL, /* sub */ | |
314 | NULL, /* next */ | |
315 | 0, /* static_pass_number */ | |
316 | TV_WEB, /* tv_id */ | |
317 | 0, /* properties_required */ | |
318 | 0, /* properties_provided */ | |
319 | 0, /* properties_destroyed */ | |
320 | 0, /* todo_flags_start */ | |
321 | TODO_dump_func, /* todo_flags_finish */ | |
322 | 'Z' /* letter */ | |
323 | }; | |
324 |