]>
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 | ||
64 | /* This entry is allocated for each reference in the insn stream. */ | |
65 | struct web_entry | |
66 | { | |
2426d8dd | 67 | /* Pointer to the parent in the union/find tree. */ |
62551c66 | 68 | struct web_entry *pred; |
2426d8dd | 69 | /* Newly assigned register to the entry. Set only for roots. */ |
62551c66 JH |
70 | rtx reg; |
71 | }; | |
72 | ||
9373164a KC |
73 | static struct web_entry *unionfind_root (struct web_entry *); |
74 | static void unionfind_union (struct web_entry *, struct web_entry *); | |
4d779342 | 75 | static void union_defs (struct df *, struct df_ref *, struct web_entry *, |
9373164a | 76 | struct web_entry *); |
4d779342 DB |
77 | static rtx entry_register (struct web_entry *, struct df_ref *, char *); |
78 | static void replace_ref (struct df_ref *, rtx); | |
62551c66 | 79 | |
2426d8dd | 80 | /* Find the root of unionfind tree (the representative of set). */ |
62551c66 JH |
81 | |
82 | static struct web_entry * | |
9373164a | 83 | unionfind_root (struct web_entry *element) |
62551c66 JH |
84 | { |
85 | struct web_entry *element1 = element, *element2; | |
86 | ||
87 | while (element->pred) | |
88 | element = element->pred; | |
89 | while (element1->pred) | |
90 | { | |
91 | element2 = element1->pred; | |
92 | element1->pred = element; | |
93 | element1 = element2; | |
94 | } | |
95 | return element; | |
96 | } | |
97 | ||
98 | /* Union sets. */ | |
99 | ||
100 | static void | |
9373164a | 101 | unionfind_union (struct web_entry *first, struct web_entry *second) |
62551c66 JH |
102 | { |
103 | first = unionfind_root (first); | |
104 | second = unionfind_root (second); | |
105 | if (first == second) | |
106 | return; | |
107 | second->pred = first; | |
108 | } | |
109 | ||
2426d8dd EB |
110 | /* For each use, all possible defs reaching it must come in the same |
111 | register, union them. */ | |
62551c66 JH |
112 | |
113 | static void | |
4d779342 | 114 | union_defs (struct df *df, struct df_ref *use, struct web_entry *def_entry, |
9373164a | 115 | struct web_entry *use_entry) |
62551c66 JH |
116 | { |
117 | rtx insn = DF_REF_INSN (use); | |
118 | struct df_link *link = DF_REF_CHAIN (use); | |
4d779342 DB |
119 | struct df_ref *use_link = DF_INSN_USES (df, insn); |
120 | struct df_ref *def_link = DF_INSN_DEFS (df, insn); | |
62551c66 JH |
121 | rtx set = single_set (insn); |
122 | ||
2426d8dd EB |
123 | /* Some instructions may use match_dup for their operands. In case the |
124 | operands are dead, we will assign them different pseudos, creating | |
125 | invalid instructions, so union all uses of the same operand for each | |
62551c66 JH |
126 | insn. */ |
127 | ||
128 | while (use_link) | |
129 | { | |
4d779342 DB |
130 | if (use != use_link |
131 | && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link)) | |
62551c66 | 132 | unionfind_union (use_entry + DF_REF_ID (use), |
4d779342 DB |
133 | use_entry + DF_REF_ID (use_link)); |
134 | use_link = use_link->next_ref; | |
62551c66 JH |
135 | } |
136 | ||
2426d8dd EB |
137 | /* Recognize trivial noop moves and attempt to keep them as noop. |
138 | While most of noop moves should be removed, we still keep some | |
139 | of them at libcall boundaries and such. */ | |
62551c66 JH |
140 | |
141 | if (set | |
142 | && SET_SRC (set) == DF_REF_REG (use) | |
143 | && SET_SRC (set) == SET_DEST (set)) | |
144 | { | |
145 | while (def_link) | |
146 | { | |
4d779342 | 147 | if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link)) |
62551c66 | 148 | unionfind_union (use_entry + DF_REF_ID (use), |
4d779342 DB |
149 | def_entry + DF_REF_ID (def_link)); |
150 | def_link = def_link->next_ref; | |
62551c66 JH |
151 | } |
152 | } | |
153 | while (link) | |
154 | { | |
155 | unionfind_union (use_entry + DF_REF_ID (use), | |
156 | def_entry + DF_REF_ID (link->ref)); | |
157 | link = link->next; | |
158 | } | |
159 | ||
2426d8dd | 160 | /* A READ_WRITE use requires the corresponding def to be in the same |
62551c66 JH |
161 | register. Find it and union. */ |
162 | if (use->flags & DF_REF_READ_WRITE) | |
163 | { | |
4d779342 | 164 | struct df_ref *link = DF_INSN_DEFS (df, DF_REF_INSN (use)); |
62551c66 | 165 | |
909b7f16 RZ |
166 | while (link) |
167 | { | |
4d779342 | 168 | if (DF_REF_REAL_REG (link) == DF_REF_REAL_REG (use)) |
909b7f16 | 169 | unionfind_union (use_entry + DF_REF_ID (use), |
4d779342 DB |
170 | def_entry + DF_REF_ID (link)); |
171 | link = link->next_ref; | |
909b7f16 | 172 | } |
62551c66 JH |
173 | } |
174 | } | |
175 | ||
2426d8dd | 176 | /* Find the corresponding register for the given entry. */ |
62551c66 JH |
177 | |
178 | static rtx | |
4d779342 | 179 | entry_register (struct web_entry *entry, struct df_ref *ref, char *used) |
62551c66 JH |
180 | { |
181 | struct web_entry *root; | |
182 | rtx reg, newreg; | |
183 | ||
2426d8dd | 184 | /* Find the corresponding web and see if it has been visited. */ |
62551c66 JH |
185 | root = unionfind_root (entry); |
186 | if (root->reg) | |
187 | return root->reg; | |
188 | ||
2426d8dd | 189 | /* We are seeing this web for the first time, do the assignment. */ |
62551c66 JH |
190 | reg = DF_REF_REAL_REG (ref); |
191 | ||
192 | /* In case the original register is already assigned, generate new one. */ | |
193 | if (!used[REGNO (reg)]) | |
194 | newreg = reg, used[REGNO (reg)] = 1; | |
195 | else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/) | |
196 | { | |
197 | newreg = reg; | |
c263766c RH |
198 | if (dump_file) |
199 | fprintf (dump_file, | |
62551c66 JH |
200 | "New web forced to keep reg=%i (user variable)\n", |
201 | REGNO (reg)); | |
202 | } | |
62551c66 JH |
203 | else |
204 | { | |
205 | newreg = gen_reg_rtx (GET_MODE (reg)); | |
206 | REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); | |
207 | REG_POINTER (newreg) = REG_POINTER (reg); | |
62551c66 | 208 | REG_ATTRS (newreg) = REG_ATTRS (reg); |
c263766c RH |
209 | if (dump_file) |
210 | fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), | |
62551c66 JH |
211 | REGNO (newreg)); |
212 | } | |
213 | ||
214 | root->reg = newreg; | |
215 | return newreg; | |
216 | } | |
217 | ||
218 | /* Replace the reference by REG. */ | |
219 | ||
220 | static void | |
4d779342 | 221 | replace_ref (struct df_ref *ref, rtx reg) |
62551c66 JH |
222 | { |
223 | rtx oldreg = DF_REF_REAL_REG (ref); | |
224 | rtx *loc = DF_REF_REAL_LOC (ref); | |
225 | ||
226 | if (oldreg == reg) | |
227 | return; | |
c263766c RH |
228 | if (dump_file) |
229 | fprintf (dump_file, "Updating insn %i (%i->%i)\n", | |
62551c66 JH |
230 | INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg)); |
231 | *loc = reg; | |
232 | } | |
233 | ||
62551c66 JH |
234 | /* Main entry point. */ |
235 | ||
65727068 | 236 | static void |
9373164a | 237 | web_main (void) |
62551c66 JH |
238 | { |
239 | struct df *df; | |
240 | struct web_entry *def_entry; | |
241 | struct web_entry *use_entry; | |
242 | unsigned int i; | |
243 | int max = max_reg_num (); | |
244 | char *used; | |
62551c66 | 245 | |
4d779342 DB |
246 | df = df_init (DF_EQUIV_NOTES); |
247 | df_chain_add_problem (df, DF_UD_CHAIN); | |
248 | df_analyze (df); | |
249 | df_reorganize_refs (&df->def_info); | |
250 | df_reorganize_refs (&df->use_info); | |
62551c66 | 251 | |
5ed6ace5 MD |
252 | def_entry = XCNEWVEC (struct web_entry, DF_DEFS_SIZE (df)); |
253 | use_entry = XCNEWVEC (struct web_entry, DF_USES_SIZE (df)); | |
254 | used = XCNEWVEC (char, max); | |
62551c66 | 255 | |
c263766c | 256 | if (dump_file) |
4d779342 | 257 | df_dump (df, dump_file); |
62551c66 JH |
258 | |
259 | /* Produce the web. */ | |
4d779342 DB |
260 | for (i = 0; i < DF_USES_SIZE (df); i++) |
261 | union_defs (df, DF_USES_GET (df, i), def_entry, use_entry); | |
62551c66 | 262 | |
62551c66 JH |
263 | /* Update the instruction stream, allocating new registers for split pseudos |
264 | in progress. */ | |
4d779342 DB |
265 | for (i = 0; i < DF_USES_SIZE (df); i++) |
266 | replace_ref (DF_USES_GET (df, i), | |
267 | entry_register (use_entry + i, DF_USES_GET (df, i), used)); | |
268 | for (i = 0; i < DF_DEFS_SIZE (df); i++) | |
269 | replace_ref (DF_DEFS_GET (df, i), | |
270 | entry_register (def_entry + i, DF_DEFS_GET (df, i), used)); | |
62551c66 | 271 | |
2426d8dd EB |
272 | /* Dataflow information is corrupt here, but it can be easily updated |
273 | by creating new entries for new registers and updates or calling | |
62551c66 JH |
274 | df_insns_modify. */ |
275 | free (def_entry); | |
276 | free (use_entry); | |
277 | free (used); | |
62551c66 | 278 | df_finish (df); |
4d779342 | 279 | df = NULL; |
62551c66 | 280 | } |
ef330312 PB |
281 | \f |
282 | static bool | |
283 | gate_handle_web (void) | |
284 | { | |
285 | return (optimize > 0 && flag_web); | |
286 | } | |
287 | ||
c2924966 | 288 | static unsigned int |
ef330312 PB |
289 | rest_of_handle_web (void) |
290 | { | |
291 | web_main (); | |
292 | delete_trivially_dead_insns (get_insns (), max_reg_num ()); | |
293 | cleanup_cfg (CLEANUP_EXPENSIVE); | |
294 | reg_scan (get_insns (), max_reg_num ()); | |
c2924966 | 295 | return 0; |
ef330312 PB |
296 | } |
297 | ||
298 | struct tree_opt_pass pass_web = | |
299 | { | |
300 | "web", /* name */ | |
301 | gate_handle_web, /* gate */ | |
302 | rest_of_handle_web, /* execute */ | |
303 | NULL, /* sub */ | |
304 | NULL, /* next */ | |
305 | 0, /* static_pass_number */ | |
306 | TV_WEB, /* tv_id */ | |
307 | 0, /* properties_required */ | |
308 | 0, /* properties_provided */ | |
309 | 0, /* properties_destroyed */ | |
310 | 0, /* todo_flags_start */ | |
311 | TODO_dump_func, /* todo_flags_finish */ | |
312 | 'Z' /* letter */ | |
313 | }; | |
314 |