]>
Commit | Line | Data |
---|---|---|
7b82b5da | 1 | /* Register renaming for the GNU compiler. |
684bcee5 | 2 | Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
7b82b5da | 3 | |
1322177d | 4 | This file is part of GCC. |
7b82b5da | 5 | |
1322177d LB |
6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by | |
7b82b5da SC |
8 | the Free Software Foundation; either version 2, or (at your option) |
9 | any later version. | |
10 | ||
1322177d LB |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
13 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
14 | License for more details. | |
7b82b5da SC |
15 | |
16 | You should have received a copy of the GNU General Public License | |
1322177d LB |
17 | along with GCC; see the file COPYING. If not, write to the Free |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
7b82b5da | 20 | |
541f7d56 BS |
21 | #define REG_OK_STRICT |
22 | ||
7b82b5da SC |
23 | #include "config.h" |
24 | #include "system.h" | |
4977bab6 ZW |
25 | #include "coretypes.h" |
26 | #include "tm.h" | |
7b82b5da | 27 | #include "rtl.h" |
541f7d56 | 28 | #include "tm_p.h" |
7b82b5da SC |
29 | #include "insn-config.h" |
30 | #include "regs.h" | |
541f7d56 BS |
31 | #include "hard-reg-set.h" |
32 | #include "basic-block.h" | |
33 | #include "reload.h" | |
7b82b5da SC |
34 | #include "output.h" |
35 | #include "function.h" | |
36 | #include "recog.h" | |
541f7d56 | 37 | #include "flags.h" |
8582c27b | 38 | #include "toplev.h" |
541f7d56 BS |
39 | #include "obstack.h" |
40 | ||
541f7d56 BS |
41 | #ifndef REG_MODE_OK_FOR_BASE_P |
42 | #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO) | |
43 | #endif | |
7b82b5da SC |
44 | |
45 | static const char *const reg_class_names[] = REG_CLASS_NAMES; | |
46 | ||
541f7d56 | 47 | struct du_chain |
7b82b5da | 48 | { |
541f7d56 BS |
49 | struct du_chain *next_chain; |
50 | struct du_chain *next_use; | |
7b82b5da | 51 | |
541f7d56 BS |
52 | rtx insn; |
53 | rtx *loc; | |
496324d0 | 54 | ENUM_BITFIELD(reg_class) class : 16; |
541f7d56 | 55 | unsigned int need_caller_save_reg:1; |
fe08a886 | 56 | unsigned int earlyclobber:1; |
541f7d56 | 57 | }; |
7b82b5da | 58 | |
541f7d56 BS |
59 | enum scan_actions |
60 | { | |
541f7d56 BS |
61 | terminate_all_read, |
62 | terminate_overlapping_read, | |
63 | terminate_write, | |
64 | terminate_dead, | |
65 | mark_read, | |
66 | mark_write | |
67 | }; | |
68 | ||
69 | static const char * const scan_actions_name[] = | |
70 | { | |
541f7d56 BS |
71 | "terminate_all_read", |
72 | "terminate_overlapping_read", | |
73 | "terminate_write", | |
74 | "terminate_dead", | |
75 | "mark_read", | |
76 | "mark_write" | |
77 | }; | |
78 | ||
79 | static struct obstack rename_obstack; | |
80 | ||
0c20a65f AJ |
81 | static void do_replace (struct du_chain *, int); |
82 | static void scan_rtx_reg (rtx, rtx *, enum reg_class, | |
83 | enum scan_actions, enum op_type, int); | |
84 | static void scan_rtx_address (rtx, rtx *, enum reg_class, | |
85 | enum scan_actions, enum machine_mode); | |
86 | static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions, | |
87 | enum op_type, int); | |
88 | static struct du_chain *build_def_use (basic_block); | |
89 | static void dump_def_use_chain (struct du_chain *); | |
90 | static void note_sets (rtx, rtx, void *); | |
91 | static void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx); | |
92 | static void merge_overlapping_regs (basic_block, HARD_REG_SET *, | |
93 | struct du_chain *); | |
fe08a886 BS |
94 | |
95 | /* Called through note_stores from update_life. Find sets of registers, and | |
96 | record them in *DATA (which is actually a HARD_REG_SET *). */ | |
97 | ||
98 | static void | |
0c20a65f | 99 | note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data) |
fe08a886 BS |
100 | { |
101 | HARD_REG_SET *pset = (HARD_REG_SET *) data; | |
102 | unsigned int regno; | |
103 | int nregs; | |
104 | if (GET_CODE (x) != REG) | |
105 | return; | |
106 | regno = REGNO (x); | |
107 | nregs = HARD_REGNO_NREGS (regno, GET_MODE (x)); | |
3d17d93d AO |
108 | |
109 | /* There must not be pseudos at this point. */ | |
110 | if (regno + nregs > FIRST_PSEUDO_REGISTER) | |
111 | abort (); | |
112 | ||
fe08a886 BS |
113 | while (nregs-- > 0) |
114 | SET_HARD_REG_BIT (*pset, regno + nregs); | |
115 | } | |
116 | ||
117 | /* Clear all registers from *PSET for which a note of kind KIND can be found | |
118 | in the list NOTES. */ | |
119 | ||
120 | static void | |
0c20a65f | 121 | clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes) |
fe08a886 BS |
122 | { |
123 | rtx note; | |
124 | for (note = notes; note; note = XEXP (note, 1)) | |
125 | if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0))) | |
126 | { | |
127 | rtx reg = XEXP (note, 0); | |
128 | unsigned int regno = REGNO (reg); | |
129 | int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); | |
3d17d93d AO |
130 | |
131 | /* There must not be pseudos at this point. */ | |
132 | if (regno + nregs > FIRST_PSEUDO_REGISTER) | |
133 | abort (); | |
134 | ||
fe08a886 BS |
135 | while (nregs-- > 0) |
136 | CLEAR_HARD_REG_BIT (*pset, regno + nregs); | |
137 | } | |
138 | } | |
139 | ||
140 | /* For a def-use chain CHAIN in basic block B, find which registers overlap | |
141 | its lifetime and set the corresponding bits in *PSET. */ | |
142 | ||
143 | static void | |
0c20a65f AJ |
144 | merge_overlapping_regs (basic_block b, HARD_REG_SET *pset, |
145 | struct du_chain *chain) | |
fe08a886 BS |
146 | { |
147 | struct du_chain *t = chain; | |
148 | rtx insn; | |
149 | HARD_REG_SET live; | |
150 | ||
151 | REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start); | |
a813c111 | 152 | insn = BB_HEAD (b); |
fe08a886 BS |
153 | while (t) |
154 | { | |
155 | /* Search forward until the next reference to the register to be | |
156 | renamed. */ | |
157 | while (insn != t->insn) | |
158 | { | |
159 | if (INSN_P (insn)) | |
160 | { | |
161 | clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn)); | |
162 | note_stores (PATTERN (insn), note_sets, (void *) &live); | |
163 | /* Only record currently live regs if we are inside the | |
164 | reg's live range. */ | |
165 | if (t != chain) | |
166 | IOR_HARD_REG_SET (*pset, live); | |
3b03c671 | 167 | clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn)); |
fe08a886 BS |
168 | } |
169 | insn = NEXT_INSN (insn); | |
170 | } | |
171 | ||
172 | IOR_HARD_REG_SET (*pset, live); | |
173 | ||
174 | /* For the last reference, also merge in all registers set in the | |
175 | same insn. | |
176 | @@@ We only have take earlyclobbered sets into account. */ | |
177 | if (! t->next_use) | |
178 | note_stores (PATTERN (insn), note_sets, (void *) pset); | |
179 | ||
180 | t = t->next_use; | |
181 | } | |
182 | } | |
183 | ||
184 | /* Perform register renaming on the current function. */ | |
7b82b5da | 185 | |
541f7d56 | 186 | void |
0c20a65f | 187 | regrename_optimize (void) |
541f7d56 | 188 | { |
fe08a886 BS |
189 | int tick[FIRST_PSEUDO_REGISTER]; |
190 | int this_tick = 0; | |
e0082a72 | 191 | basic_block bb; |
541f7d56 | 192 | char *first_obj; |
7b82b5da | 193 | |
fe08a886 BS |
194 | memset (tick, 0, sizeof tick); |
195 | ||
541f7d56 | 196 | gcc_obstack_init (&rename_obstack); |
703ad42b | 197 | first_obj = obstack_alloc (&rename_obstack, 0); |
7b82b5da | 198 | |
e0082a72 | 199 | FOR_EACH_BB (bb) |
541f7d56 | 200 | { |
541f7d56 | 201 | struct du_chain *all_chains = 0; |
541f7d56 BS |
202 | HARD_REG_SET unavailable; |
203 | HARD_REG_SET regs_seen; | |
7b82b5da | 204 | |
541f7d56 | 205 | CLEAR_HARD_REG_SET (unavailable); |
7b82b5da | 206 | |
541f7d56 | 207 | if (rtl_dump_file) |
e0082a72 | 208 | fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index); |
7b82b5da | 209 | |
fe08a886 | 210 | all_chains = build_def_use (bb); |
7b82b5da | 211 | |
541f7d56 BS |
212 | if (rtl_dump_file) |
213 | dump_def_use_chain (all_chains); | |
7b82b5da | 214 | |
fe08a886 | 215 | CLEAR_HARD_REG_SET (unavailable); |
541f7d56 BS |
216 | /* Don't clobber traceback for noreturn functions. */ |
217 | if (frame_pointer_needed) | |
218 | { | |
65599eb4 | 219 | int i; |
3b03c671 | 220 | |
65599eb4 DC |
221 | for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;) |
222 | SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i); | |
3b03c671 | 223 | |
541f7d56 | 224 | #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM |
65599eb4 DC |
225 | for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;) |
226 | SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i); | |
541f7d56 BS |
227 | #endif |
228 | } | |
7b82b5da | 229 | |
541f7d56 BS |
230 | CLEAR_HARD_REG_SET (regs_seen); |
231 | while (all_chains) | |
232 | { | |
62551c66 | 233 | int new_reg, best_new_reg; |
541f7d56 BS |
234 | int n_uses; |
235 | struct du_chain *this = all_chains; | |
236 | struct du_chain *tmp, *last; | |
237 | HARD_REG_SET this_unavailable; | |
4e812700 | 238 | int reg = REGNO (*this->loc); |
85941a0a | 239 | int i; |
7b82b5da | 240 | |
541f7d56 | 241 | all_chains = this->next_chain; |
3b03c671 | 242 | |
62551c66 JH |
243 | best_new_reg = reg; |
244 | ||
fe08a886 | 245 | #if 0 /* This just disables optimization opportunities. */ |
541f7d56 BS |
246 | /* Only rename once we've seen the reg more than once. */ |
247 | if (! TEST_HARD_REG_BIT (regs_seen, reg)) | |
1a43c33f | 248 | { |
541f7d56 BS |
249 | SET_HARD_REG_BIT (regs_seen, reg); |
250 | continue; | |
251 | } | |
fe08a886 | 252 | #endif |
1a43c33f | 253 | |
f4d578da BS |
254 | if (fixed_regs[reg] || global_regs[reg] |
255 | #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM | |
256 | || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) | |
257 | #else | |
258 | || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) | |
259 | #endif | |
260 | ) | |
541f7d56 | 261 | continue; |
1a43c33f | 262 | |
541f7d56 | 263 | COPY_HARD_REG_SET (this_unavailable, unavailable); |
1a43c33f | 264 | |
541f7d56 BS |
265 | /* Find last entry on chain (which has the need_caller_save bit), |
266 | count number of uses, and narrow the set of registers we can | |
267 | use for renaming. */ | |
268 | n_uses = 0; | |
269 | for (last = this; last->next_use; last = last->next_use) | |
270 | { | |
271 | n_uses++; | |
272 | IOR_COMPL_HARD_REG_SET (this_unavailable, | |
273 | reg_class_contents[last->class]); | |
1a43c33f | 274 | } |
541f7d56 BS |
275 | if (n_uses < 1) |
276 | continue; | |
7b82b5da | 277 | |
541f7d56 BS |
278 | IOR_COMPL_HARD_REG_SET (this_unavailable, |
279 | reg_class_contents[last->class]); | |
7b82b5da | 280 | |
fe08a886 | 281 | if (this->need_caller_save_reg) |
541f7d56 BS |
282 | IOR_HARD_REG_SET (this_unavailable, call_used_reg_set); |
283 | ||
fe08a886 BS |
284 | merge_overlapping_regs (bb, &this_unavailable, this); |
285 | ||
541f7d56 BS |
286 | /* Now potential_regs is a reasonable approximation, let's |
287 | have a closer look at each register still in there. */ | |
4e812700 | 288 | for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) |
1a43c33f | 289 | { |
4e812700 RH |
290 | int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc)); |
291 | ||
85941a0a | 292 | for (i = nregs - 1; i >= 0; --i) |
fe08a886 BS |
293 | if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) |
294 | || fixed_regs[new_reg + i] | |
295 | || global_regs[new_reg + i] | |
85941a0a | 296 | /* Can't use regs which aren't saved by the prologue. */ |
fe08a886 BS |
297 | || (! regs_ever_live[new_reg + i] |
298 | && ! call_used_regs[new_reg + i]) | |
b2a8b026 | 299 | #ifdef LEAF_REGISTERS |
3b03c671 | 300 | /* We can't use a non-leaf register if we're in a |
b2a8b026 | 301 | leaf function. */ |
3b03c671 | 302 | || (current_function_is_leaf |
b2a8b026 MM |
303 | && !LEAF_REGISTERS[new_reg + i]) |
304 | #endif | |
541f7d56 | 305 | #ifdef HARD_REGNO_RENAME_OK |
fe08a886 | 306 | || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) |
541f7d56 | 307 | #endif |
85941a0a RH |
308 | ) |
309 | break; | |
310 | if (i >= 0) | |
541f7d56 | 311 | continue; |
1a43c33f | 312 | |
85941a0a RH |
313 | /* See whether it accepts all modes that occur in |
314 | definition and uses. */ | |
541f7d56 | 315 | for (tmp = this; tmp; tmp = tmp->next_use) |
66df7a98 AO |
316 | if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)) |
317 | || (tmp->need_caller_save_reg | |
318 | && ! (HARD_REGNO_CALL_PART_CLOBBERED | |
319 | (reg, GET_MODE (*tmp->loc))) | |
320 | && (HARD_REGNO_CALL_PART_CLOBBERED | |
321 | (new_reg, GET_MODE (*tmp->loc))))) | |
541f7d56 BS |
322 | break; |
323 | if (! tmp) | |
fe08a886 | 324 | { |
62551c66 | 325 | if (tick[best_new_reg] > tick[new_reg]) |
fe08a886 BS |
326 | best_new_reg = new_reg; |
327 | } | |
1a43c33f | 328 | } |
7b82b5da | 329 | |
541f7d56 BS |
330 | if (rtl_dump_file) |
331 | { | |
332 | fprintf (rtl_dump_file, "Register %s in insn %d", | |
333 | reg_names[reg], INSN_UID (last->insn)); | |
334 | if (last->need_caller_save_reg) | |
335 | fprintf (rtl_dump_file, " crosses a call"); | |
3b03c671 | 336 | } |
1a43c33f | 337 | |
62551c66 | 338 | if (best_new_reg == reg) |
541f7d56 | 339 | { |
62551c66 | 340 | tick[reg] = ++this_tick; |
541f7d56 | 341 | if (rtl_dump_file) |
62551c66 | 342 | fprintf (rtl_dump_file, "; no available better choice\n"); |
7b82b5da | 343 | continue; |
541f7d56 | 344 | } |
7b82b5da | 345 | |
fe08a886 | 346 | do_replace (this, best_new_reg); |
62551c66 | 347 | tick[best_new_reg] = ++this_tick; |
1a43c33f | 348 | |
541f7d56 | 349 | if (rtl_dump_file) |
fe08a886 | 350 | fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]); |
541f7d56 | 351 | } |
1a43c33f | 352 | |
541f7d56 BS |
353 | obstack_free (&rename_obstack, first_obj); |
354 | } | |
1a43c33f | 355 | |
541f7d56 | 356 | obstack_free (&rename_obstack, NULL); |
7b82b5da | 357 | |
541f7d56 BS |
358 | if (rtl_dump_file) |
359 | fputc ('\n', rtl_dump_file); | |
7b82b5da | 360 | |
541f7d56 BS |
361 | count_or_remove_death_notes (NULL, 1); |
362 | update_life_info (NULL, UPDATE_LIFE_LOCAL, | |
363 | PROP_REG_INFO | PROP_DEATH_NOTES); | |
7b82b5da SC |
364 | } |
365 | ||
7b82b5da | 366 | static void |
0c20a65f | 367 | do_replace (struct du_chain *chain, int reg) |
7b82b5da | 368 | { |
541f7d56 | 369 | while (chain) |
7b82b5da | 370 | { |
08394eef | 371 | unsigned int regno = ORIGINAL_REGNO (*chain->loc); |
d1d3c9a6 JH |
372 | struct reg_attrs * attr = REG_ATTRS (*chain->loc); |
373 | ||
08394eef | 374 | *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); |
f4d578da BS |
375 | if (regno >= FIRST_PSEUDO_REGISTER) |
376 | ORIGINAL_REGNO (*chain->loc) = regno; | |
d1d3c9a6 | 377 | REG_ATTRS (*chain->loc) = attr; |
541f7d56 | 378 | chain = chain->next_use; |
7b82b5da | 379 | } |
7b82b5da SC |
380 | } |
381 | ||
7b82b5da | 382 | |
541f7d56 BS |
383 | static struct du_chain *open_chains; |
384 | static struct du_chain *closed_chains; | |
385 | ||
386 | static void | |
0c20a65f AJ |
387 | scan_rtx_reg (rtx insn, rtx *loc, enum reg_class class, |
388 | enum scan_actions action, enum op_type type, int earlyclobber) | |
7b82b5da | 389 | { |
541f7d56 BS |
390 | struct du_chain **p; |
391 | rtx x = *loc; | |
392 | enum machine_mode mode = GET_MODE (x); | |
393 | int this_regno = REGNO (x); | |
394 | int this_nregs = HARD_REGNO_NREGS (this_regno, mode); | |
395 | ||
541f7d56 | 396 | if (action == mark_write) |
7b82b5da | 397 | { |
541f7d56 | 398 | if (type == OP_OUT) |
7b82b5da | 399 | { |
703ad42b KG |
400 | struct du_chain *this |
401 | = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); | |
541f7d56 BS |
402 | this->next_use = 0; |
403 | this->next_chain = open_chains; | |
404 | this->loc = loc; | |
405 | this->insn = insn; | |
406 | this->class = class; | |
407 | this->need_caller_save_reg = 0; | |
fe08a886 | 408 | this->earlyclobber = earlyclobber; |
541f7d56 | 409 | open_chains = this; |
7b82b5da | 410 | } |
541f7d56 | 411 | return; |
7b82b5da | 412 | } |
1a43c33f | 413 | |
541f7d56 BS |
414 | if ((type == OP_OUT && action != terminate_write) |
415 | || (type != OP_OUT && action == terminate_write)) | |
416 | return; | |
5fa41e13 | 417 | |
541f7d56 | 418 | for (p = &open_chains; *p;) |
5fa41e13 | 419 | { |
541f7d56 | 420 | struct du_chain *this = *p; |
541f7d56 | 421 | |
695e4773 GS |
422 | /* Check if the chain has been terminated if it has then skip to |
423 | the next chain. | |
541f7d56 | 424 | |
695e4773 GS |
425 | This can happen when we've already appended the location to |
426 | the chain in Step 3, but are trying to hide in-out operands | |
427 | from terminate_write in Step 5. */ | |
5fa41e13 | 428 | |
695e4773 GS |
429 | if (*this->loc == cc0_rtx) |
430 | p = &this->next_chain; | |
431 | else | |
3b03c671 | 432 | { |
695e4773 GS |
433 | int regno = REGNO (*this->loc); |
434 | int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc)); | |
435 | int exact_match = (regno == this_regno && nregs == this_nregs); | |
436 | ||
437 | if (regno + nregs <= this_regno | |
438 | || this_regno + this_nregs <= regno) | |
a125d855 RH |
439 | { |
440 | p = &this->next_chain; | |
441 | continue; | |
442 | } | |
443 | ||
444 | if (action == mark_read) | |
541f7d56 | 445 | { |
695e4773 GS |
446 | if (! exact_match) |
447 | abort (); | |
695e4773 | 448 | |
3b03c671 | 449 | /* ??? Class NO_REGS can happen if the md file makes use of |
a125d855 RH |
450 | EXTRA_CONSTRAINTS to match registers. Which is arguably |
451 | wrong, but there we are. Since we know not what this may | |
452 | be replaced with, terminate the chain. */ | |
453 | if (class != NO_REGS) | |
454 | { | |
703ad42b | 455 | this = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); |
fe08a886 | 456 | this->next_use = 0; |
a125d855 RH |
457 | this->next_chain = (*p)->next_chain; |
458 | this->loc = loc; | |
459 | this->insn = insn; | |
460 | this->class = class; | |
461 | this->need_caller_save_reg = 0; | |
fe08a886 BS |
462 | while (*p) |
463 | p = &(*p)->next_use; | |
a125d855 RH |
464 | *p = this; |
465 | return; | |
466 | } | |
541f7d56 | 467 | } |
a125d855 RH |
468 | |
469 | if (action != terminate_overlapping_read || ! exact_match) | |
541f7d56 | 470 | { |
695e4773 GS |
471 | struct du_chain *next = this->next_chain; |
472 | ||
473 | /* Whether the terminated chain can be used for renaming | |
474 | depends on the action and this being an exact match. | |
475 | In either case, we remove this element from open_chains. */ | |
476 | ||
477 | if ((action == terminate_dead || action == terminate_write) | |
478 | && exact_match) | |
479 | { | |
480 | this->next_chain = closed_chains; | |
481 | closed_chains = this; | |
482 | if (rtl_dump_file) | |
483 | fprintf (rtl_dump_file, | |
484 | "Closing chain %s at insn %d (%s)\n", | |
485 | reg_names[REGNO (*this->loc)], INSN_UID (insn), | |
486 | scan_actions_name[(int) action]); | |
487 | } | |
488 | else | |
489 | { | |
490 | if (rtl_dump_file) | |
491 | fprintf (rtl_dump_file, | |
492 | "Discarding chain %s at insn %d (%s)\n", | |
493 | reg_names[REGNO (*this->loc)], INSN_UID (insn), | |
494 | scan_actions_name[(int) action]); | |
495 | } | |
496 | *p = next; | |
541f7d56 | 497 | } |
695e4773 GS |
498 | else |
499 | p = &this->next_chain; | |
541f7d56 | 500 | } |
541f7d56 | 501 | } |
7b82b5da SC |
502 | } |
503 | ||
541f7d56 BS |
504 | /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or |
505 | BASE_REG_CLASS depending on how the register is being considered. */ | |
7b82b5da | 506 | |
4ca0f257 | 507 | static void |
0c20a65f AJ |
508 | scan_rtx_address (rtx insn, rtx *loc, enum reg_class class, |
509 | enum scan_actions action, enum machine_mode mode) | |
7b82b5da | 510 | { |
541f7d56 BS |
511 | rtx x = *loc; |
512 | RTX_CODE code = GET_CODE (x); | |
513 | const char *fmt; | |
514 | int i, j; | |
7b82b5da | 515 | |
541f7d56 BS |
516 | if (action == mark_write) |
517 | return; | |
7b82b5da | 518 | |
541f7d56 | 519 | switch (code) |
7b82b5da | 520 | { |
541f7d56 BS |
521 | case PLUS: |
522 | { | |
523 | rtx orig_op0 = XEXP (x, 0); | |
524 | rtx orig_op1 = XEXP (x, 1); | |
525 | RTX_CODE code0 = GET_CODE (orig_op0); | |
526 | RTX_CODE code1 = GET_CODE (orig_op1); | |
527 | rtx op0 = orig_op0; | |
528 | rtx op1 = orig_op1; | |
529 | rtx *locI = NULL; | |
530 | rtx *locB = NULL; | |
531 | ||
532 | if (GET_CODE (op0) == SUBREG) | |
533 | { | |
534 | op0 = SUBREG_REG (op0); | |
535 | code0 = GET_CODE (op0); | |
536 | } | |
7b82b5da | 537 | |
541f7d56 BS |
538 | if (GET_CODE (op1) == SUBREG) |
539 | { | |
540 | op1 = SUBREG_REG (op1); | |
541 | code1 = GET_CODE (op1); | |
542 | } | |
7b82b5da | 543 | |
541f7d56 BS |
544 | if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE |
545 | || code0 == ZERO_EXTEND || code1 == MEM) | |
546 | { | |
547 | locI = &XEXP (x, 0); | |
548 | locB = &XEXP (x, 1); | |
549 | } | |
550 | else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE | |
551 | || code1 == ZERO_EXTEND || code0 == MEM) | |
552 | { | |
553 | locI = &XEXP (x, 1); | |
554 | locB = &XEXP (x, 0); | |
555 | } | |
556 | else if (code0 == CONST_INT || code0 == CONST | |
557 | || code0 == SYMBOL_REF || code0 == LABEL_REF) | |
558 | locB = &XEXP (x, 1); | |
559 | else if (code1 == CONST_INT || code1 == CONST | |
560 | || code1 == SYMBOL_REF || code1 == LABEL_REF) | |
561 | locB = &XEXP (x, 0); | |
562 | else if (code0 == REG && code1 == REG) | |
563 | { | |
564 | int index_op; | |
565 | ||
566 | if (REG_OK_FOR_INDEX_P (op0) | |
567 | && REG_MODE_OK_FOR_BASE_P (op1, mode)) | |
568 | index_op = 0; | |
569 | else if (REG_OK_FOR_INDEX_P (op1) | |
570 | && REG_MODE_OK_FOR_BASE_P (op0, mode)) | |
571 | index_op = 1; | |
572 | else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) | |
573 | index_op = 0; | |
574 | else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) | |
575 | index_op = 1; | |
576 | else if (REG_OK_FOR_INDEX_P (op1)) | |
577 | index_op = 1; | |
578 | else | |
579 | index_op = 0; | |
580 | ||
581 | locI = &XEXP (x, index_op); | |
582 | locB = &XEXP (x, !index_op); | |
583 | } | |
584 | else if (code0 == REG) | |
585 | { | |
586 | locI = &XEXP (x, 0); | |
587 | locB = &XEXP (x, 1); | |
588 | } | |
589 | else if (code1 == REG) | |
590 | { | |
591 | locI = &XEXP (x, 1); | |
592 | locB = &XEXP (x, 0); | |
593 | } | |
7b82b5da | 594 | |
541f7d56 | 595 | if (locI) |
85941a0a | 596 | scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode); |
541f7d56 | 597 | if (locB) |
3dcc68a4 | 598 | scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode); |
541f7d56 BS |
599 | return; |
600 | } | |
7b82b5da | 601 | |
541f7d56 BS |
602 | case POST_INC: |
603 | case POST_DEC: | |
604 | case POST_MODIFY: | |
605 | case PRE_INC: | |
606 | case PRE_DEC: | |
607 | case PRE_MODIFY: | |
608 | #ifndef AUTO_INC_DEC | |
ce73761f RH |
609 | /* If the target doesn't claim to handle autoinc, this must be |
610 | something special, like a stack push. Kill this chain. */ | |
611 | action = terminate_all_read; | |
541f7d56 BS |
612 | #endif |
613 | break; | |
7b82b5da | 614 | |
541f7d56 | 615 | case MEM: |
3dcc68a4 NC |
616 | scan_rtx_address (insn, &XEXP (x, 0), |
617 | MODE_BASE_REG_CLASS (GET_MODE (x)), action, | |
85941a0a | 618 | GET_MODE (x)); |
541f7d56 | 619 | return; |
1a43c33f | 620 | |
541f7d56 | 621 | case REG: |
fe08a886 | 622 | scan_rtx_reg (insn, loc, class, action, OP_IN, 0); |
4ca0f257 | 623 | return; |
1a43c33f | 624 | |
541f7d56 BS |
625 | default: |
626 | break; | |
4ca0f257 | 627 | } |
541f7d56 BS |
628 | |
629 | fmt = GET_RTX_FORMAT (code); | |
630 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
4ca0f257 | 631 | { |
541f7d56 | 632 | if (fmt[i] == 'e') |
85941a0a | 633 | scan_rtx_address (insn, &XEXP (x, i), class, action, mode); |
541f7d56 BS |
634 | else if (fmt[i] == 'E') |
635 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
85941a0a | 636 | scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode); |
4ca0f257 | 637 | } |
7b82b5da SC |
638 | } |
639 | ||
541f7d56 | 640 | static void |
0c20a65f AJ |
641 | scan_rtx (rtx insn, rtx *loc, enum reg_class class, |
642 | enum scan_actions action, enum op_type type, int earlyclobber) | |
7b82b5da | 643 | { |
541f7d56 BS |
644 | const char *fmt; |
645 | rtx x = *loc; | |
646 | enum rtx_code code = GET_CODE (x); | |
647 | int i, j; | |
7b82b5da | 648 | |
541f7d56 BS |
649 | code = GET_CODE (x); |
650 | switch (code) | |
7b82b5da | 651 | { |
541f7d56 BS |
652 | case CONST: |
653 | case CONST_INT: | |
654 | case CONST_DOUBLE: | |
69ef87e2 | 655 | case CONST_VECTOR: |
541f7d56 BS |
656 | case SYMBOL_REF: |
657 | case LABEL_REF: | |
658 | case CC0: | |
659 | case PC: | |
660 | return; | |
055be976 | 661 | |
541f7d56 | 662 | case REG: |
fe08a886 | 663 | scan_rtx_reg (insn, loc, class, action, type, earlyclobber); |
541f7d56 | 664 | return; |
7b82b5da | 665 | |
541f7d56 | 666 | case MEM: |
3dcc68a4 NC |
667 | scan_rtx_address (insn, &XEXP (x, 0), |
668 | MODE_BASE_REG_CLASS (GET_MODE (x)), action, | |
85941a0a | 669 | GET_MODE (x)); |
541f7d56 | 670 | return; |
7b82b5da | 671 | |
541f7d56 | 672 | case SET: |
fe08a886 BS |
673 | scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0); |
674 | scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0); | |
541f7d56 | 675 | return; |
7b82b5da | 676 | |
541f7d56 | 677 | case STRICT_LOW_PART: |
fe08a886 | 678 | scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber); |
541f7d56 | 679 | return; |
7b82b5da | 680 | |
541f7d56 | 681 | case ZERO_EXTRACT: |
3b03c671 | 682 | case SIGN_EXTRACT: |
541f7d56 | 683 | scan_rtx (insn, &XEXP (x, 0), class, action, |
fe08a886 BS |
684 | type == OP_IN ? OP_IN : OP_INOUT, earlyclobber); |
685 | scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0); | |
686 | scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0); | |
541f7d56 | 687 | return; |
7b82b5da | 688 | |
541f7d56 BS |
689 | case POST_INC: |
690 | case PRE_INC: | |
691 | case POST_DEC: | |
692 | case PRE_DEC: | |
693 | case POST_MODIFY: | |
694 | case PRE_MODIFY: | |
695 | /* Should only happen inside MEM. */ | |
696 | abort (); | |
697 | ||
698 | case CLOBBER: | |
fe08a886 | 699 | scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1); |
541f7d56 | 700 | return; |
7b82b5da | 701 | |
541f7d56 | 702 | case EXPR_LIST: |
fe08a886 | 703 | scan_rtx (insn, &XEXP (x, 0), class, action, type, 0); |
541f7d56 | 704 | if (XEXP (x, 1)) |
fe08a886 | 705 | scan_rtx (insn, &XEXP (x, 1), class, action, type, 0); |
541f7d56 | 706 | return; |
7b82b5da | 707 | |
541f7d56 BS |
708 | default: |
709 | break; | |
710 | } | |
7b82b5da | 711 | |
541f7d56 BS |
712 | fmt = GET_RTX_FORMAT (code); |
713 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
7b82b5da SC |
714 | { |
715 | if (fmt[i] == 'e') | |
fe08a886 | 716 | scan_rtx (insn, &XEXP (x, i), class, action, type, 0); |
7b82b5da SC |
717 | else if (fmt[i] == 'E') |
718 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
fe08a886 | 719 | scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0); |
7b82b5da | 720 | } |
7b82b5da SC |
721 | } |
722 | ||
3eae4643 | 723 | /* Build def/use chain. */ |
7b82b5da | 724 | |
541f7d56 | 725 | static struct du_chain * |
0c20a65f | 726 | build_def_use (basic_block bb) |
7b82b5da | 727 | { |
541f7d56 | 728 | rtx insn; |
1a43c33f | 729 | |
541f7d56 | 730 | open_chains = closed_chains = NULL; |
1a43c33f | 731 | |
a813c111 | 732 | for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) |
541f7d56 BS |
733 | { |
734 | if (INSN_P (insn)) | |
735 | { | |
736 | int n_ops; | |
737 | rtx note; | |
738 | rtx old_operands[MAX_RECOG_OPERANDS]; | |
739 | rtx old_dups[MAX_DUP_OPERANDS]; | |
ea475b23 | 740 | int i, icode; |
541f7d56 BS |
741 | int alt; |
742 | int predicated; | |
743 | ||
541f7d56 BS |
744 | /* Process the insn, determining its effect on the def-use |
745 | chains. We perform the following steps with the register | |
746 | references in the insn: | |
747 | (1) Any read that overlaps an open chain, but doesn't exactly | |
748 | match, causes that chain to be closed. We can't deal | |
749 | with overlaps yet. | |
750 | (2) Any read outside an operand causes any chain it overlaps | |
751 | with to be closed, since we can't replace it. | |
752 | (3) Any read inside an operand is added if there's already | |
753 | an open chain for it. | |
754 | (4) For any REG_DEAD note we find, close open chains that | |
755 | overlap it. | |
756 | (5) For any write we find, close open chains that overlap it. | |
757 | (6) For any write we find in an operand, make a new chain. | |
758 | (7) For any REG_UNUSED, close any chains we just opened. */ | |
759 | ||
2ed1f154 | 760 | icode = recog_memoized (insn); |
541f7d56 | 761 | extract_insn (insn); |
4be9e9cb | 762 | if (! constrain_operands (1)) |
3b03c671 | 763 | fatal_insn_not_found (insn); |
541f7d56 BS |
764 | preprocess_constraints (); |
765 | alt = which_alternative; | |
766 | n_ops = recog_data.n_operands; | |
767 | ||
768 | /* Simplify the code below by rewriting things to reflect | |
769 | matching constraints. Also promote OP_OUT to OP_INOUT | |
770 | in predicated instructions. */ | |
771 | ||
772 | predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; | |
773 | for (i = 0; i < n_ops; ++i) | |
7b82b5da | 774 | { |
541f7d56 BS |
775 | int matches = recog_op_alt[i][alt].matches; |
776 | if (matches >= 0) | |
777 | recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; | |
778 | if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 | |
779 | || (predicated && recog_data.operand_type[i] == OP_OUT)) | |
780 | recog_data.operand_type[i] = OP_INOUT; | |
7b82b5da | 781 | } |
1a43c33f | 782 | |
541f7d56 BS |
783 | /* Step 1: Close chains for which we have overlapping reads. */ |
784 | for (i = 0; i < n_ops; i++) | |
785 | scan_rtx (insn, recog_data.operand_loc[i], | |
786 | NO_REGS, terminate_overlapping_read, | |
fe08a886 | 787 | recog_data.operand_type[i], 0); |
1a43c33f | 788 | |
541f7d56 | 789 | /* Step 2: Close chains for which we have reads outside operands. |
3b03c671 | 790 | We do this by munging all operands into CC0, and closing |
541f7d56 | 791 | everything remaining. */ |
7b82b5da | 792 | |
541f7d56 | 793 | for (i = 0; i < n_ops; i++) |
1a43c33f | 794 | { |
541f7d56 BS |
795 | old_operands[i] = recog_data.operand[i]; |
796 | /* Don't squash match_operator or match_parallel here, since | |
3b03c671 | 797 | we don't know that all of the contained registers are |
541f7d56 BS |
798 | reachable by proper operands. */ |
799 | if (recog_data.constraints[i][0] == '\0') | |
800 | continue; | |
801 | *recog_data.operand_loc[i] = cc0_rtx; | |
802 | } | |
803 | for (i = 0; i < recog_data.n_dups; i++) | |
804 | { | |
ea475b23 JJ |
805 | int dup_num = recog_data.dup_num[i]; |
806 | ||
541f7d56 BS |
807 | old_dups[i] = *recog_data.dup_loc[i]; |
808 | *recog_data.dup_loc[i] = cc0_rtx; | |
ea475b23 JJ |
809 | |
810 | /* For match_dup of match_operator or match_parallel, share | |
811 | them, so that we don't miss changes in the dup. */ | |
812 | if (icode >= 0 | |
813 | && insn_data[icode].operand[dup_num].eliminable == 0) | |
814 | old_dups[i] = recog_data.operand[dup_num]; | |
1a43c33f | 815 | } |
1a43c33f | 816 | |
fe08a886 BS |
817 | scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, |
818 | OP_IN, 0); | |
1a43c33f | 819 | |
541f7d56 BS |
820 | for (i = 0; i < recog_data.n_dups; i++) |
821 | *recog_data.dup_loc[i] = old_dups[i]; | |
822 | for (i = 0; i < n_ops; i++) | |
823 | *recog_data.operand_loc[i] = old_operands[i]; | |
7b82b5da | 824 | |
541f7d56 BS |
825 | /* Step 2B: Can't rename function call argument registers. */ |
826 | if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn)) | |
827 | scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), | |
fe08a886 | 828 | NO_REGS, terminate_all_read, OP_IN, 0); |
7b82b5da | 829 | |
3ada20ee RH |
830 | /* Step 2C: Can't rename asm operands that were originally |
831 | hard registers. */ | |
832 | if (asm_noperands (PATTERN (insn)) > 0) | |
833 | for (i = 0; i < n_ops; i++) | |
834 | { | |
835 | rtx *loc = recog_data.operand_loc[i]; | |
836 | rtx op = *loc; | |
837 | ||
838 | if (GET_CODE (op) == REG | |
839 | && REGNO (op) == ORIGINAL_REGNO (op) | |
840 | && (recog_data.operand_type[i] == OP_IN | |
841 | || recog_data.operand_type[i] == OP_INOUT)) | |
842 | scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0); | |
843 | } | |
844 | ||
541f7d56 BS |
845 | /* Step 3: Append to chains for reads inside operands. */ |
846 | for (i = 0; i < n_ops + recog_data.n_dups; i++) | |
847 | { | |
848 | int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; | |
849 | rtx *loc = (i < n_ops | |
850 | ? recog_data.operand_loc[opn] | |
851 | : recog_data.dup_loc[i - n_ops]); | |
852 | enum reg_class class = recog_op_alt[opn][alt].class; | |
853 | enum op_type type = recog_data.operand_type[opn]; | |
854 | ||
855 | /* Don't scan match_operand here, since we've no reg class | |
856 | information to pass down. Any operands that we could | |
857 | substitute in will be represented elsewhere. */ | |
858 | if (recog_data.constraints[opn][0] == '\0') | |
859 | continue; | |
7b82b5da | 860 | |
541f7d56 | 861 | if (recog_op_alt[opn][alt].is_address) |
85941a0a | 862 | scan_rtx_address (insn, loc, class, mark_read, VOIDmode); |
541f7d56 | 863 | else |
fe08a886 | 864 | scan_rtx (insn, loc, class, mark_read, type, 0); |
541f7d56 | 865 | } |
7b82b5da | 866 | |
6fb85418 BS |
867 | /* Step 4: Close chains for registers that die here. |
868 | Also record updates for REG_INC notes. */ | |
541f7d56 | 869 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) |
6fb85418 BS |
870 | { |
871 | if (REG_NOTE_KIND (note) == REG_DEAD) | |
fe08a886 BS |
872 | scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, |
873 | OP_IN, 0); | |
6fb85418 | 874 | else if (REG_NOTE_KIND (note) == REG_INC) |
fe08a886 BS |
875 | scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, |
876 | OP_INOUT, 0); | |
6fb85418 | 877 | } |
1a43c33f | 878 | |
541f7d56 BS |
879 | /* Step 4B: If this is a call, any chain live at this point |
880 | requires a caller-saved reg. */ | |
881 | if (GET_CODE (insn) == CALL_INSN) | |
882 | { | |
883 | struct du_chain *p; | |
884 | for (p = open_chains; p; p = p->next_chain) | |
fe08a886 | 885 | p->need_caller_save_reg = 1; |
541f7d56 | 886 | } |
7b82b5da | 887 | |
541f7d56 BS |
888 | /* Step 5: Close open chains that overlap writes. Similar to |
889 | step 2, we hide in-out operands, since we do not want to | |
890 | close these chains. */ | |
7b82b5da | 891 | |
541f7d56 BS |
892 | for (i = 0; i < n_ops; i++) |
893 | { | |
894 | old_operands[i] = recog_data.operand[i]; | |
895 | if (recog_data.operand_type[i] == OP_INOUT) | |
896 | *recog_data.operand_loc[i] = cc0_rtx; | |
897 | } | |
898 | for (i = 0; i < recog_data.n_dups; i++) | |
899 | { | |
900 | int opn = recog_data.dup_num[i]; | |
901 | old_dups[i] = *recog_data.dup_loc[i]; | |
902 | if (recog_data.operand_type[opn] == OP_INOUT) | |
903 | *recog_data.dup_loc[i] = cc0_rtx; | |
904 | } | |
7b82b5da | 905 | |
fe08a886 | 906 | scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0); |
7b82b5da | 907 | |
541f7d56 BS |
908 | for (i = 0; i < recog_data.n_dups; i++) |
909 | *recog_data.dup_loc[i] = old_dups[i]; | |
910 | for (i = 0; i < n_ops; i++) | |
911 | *recog_data.operand_loc[i] = old_operands[i]; | |
7b82b5da | 912 | |
541f7d56 BS |
913 | /* Step 6: Begin new chains for writes inside operands. */ |
914 | /* ??? Many targets have output constraints on the SET_DEST | |
915 | of a call insn, which is stupid, since these are certainly | |
3ada20ee RH |
916 | ABI defined hard registers. Don't change calls at all. |
917 | Similarly take special care for asm statement that originally | |
918 | referenced hard registers. */ | |
919 | if (asm_noperands (PATTERN (insn)) > 0) | |
920 | { | |
921 | for (i = 0; i < n_ops; i++) | |
922 | if (recog_data.operand_type[i] == OP_OUT) | |
923 | { | |
924 | rtx *loc = recog_data.operand_loc[i]; | |
925 | rtx op = *loc; | |
926 | enum reg_class class = recog_op_alt[i][alt].class; | |
927 | ||
928 | if (GET_CODE (op) == REG | |
3b03c671 | 929 | && REGNO (op) == ORIGINAL_REGNO (op)) |
3ada20ee RH |
930 | continue; |
931 | ||
932 | scan_rtx (insn, loc, class, mark_write, OP_OUT, | |
933 | recog_op_alt[i][alt].earlyclobber); | |
934 | } | |
935 | } | |
936 | else if (GET_CODE (insn) != CALL_INSN) | |
541f7d56 BS |
937 | for (i = 0; i < n_ops + recog_data.n_dups; i++) |
938 | { | |
939 | int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; | |
940 | rtx *loc = (i < n_ops | |
941 | ? recog_data.operand_loc[opn] | |
942 | : recog_data.dup_loc[i - n_ops]); | |
943 | enum reg_class class = recog_op_alt[opn][alt].class; | |
944 | ||
945 | if (recog_data.operand_type[opn] == OP_OUT) | |
fe08a886 BS |
946 | scan_rtx (insn, loc, class, mark_write, OP_OUT, |
947 | recog_op_alt[opn][alt].earlyclobber); | |
541f7d56 | 948 | } |
7b82b5da | 949 | |
541f7d56 BS |
950 | /* Step 7: Close chains for registers that were never |
951 | really used here. */ | |
952 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
953 | if (REG_NOTE_KIND (note) == REG_UNUSED) | |
fe08a886 BS |
954 | scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, |
955 | OP_IN, 0); | |
541f7d56 | 956 | } |
a813c111 | 957 | if (insn == BB_END (bb)) |
541f7d56 BS |
958 | break; |
959 | } | |
7b82b5da | 960 | |
541f7d56 BS |
961 | /* Since we close every chain when we find a REG_DEAD note, anything that |
962 | is still open lives past the basic block, so it can't be renamed. */ | |
963 | return closed_chains; | |
964 | } | |
7b82b5da | 965 | |
541f7d56 BS |
966 | /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are |
967 | printed in reverse order as that's how we build them. */ | |
7b82b5da | 968 | |
541f7d56 | 969 | static void |
0c20a65f | 970 | dump_def_use_chain (struct du_chain *chains) |
541f7d56 BS |
971 | { |
972 | while (chains) | |
1a43c33f | 973 | { |
541f7d56 BS |
974 | struct du_chain *this = chains; |
975 | int r = REGNO (*this->loc); | |
976 | int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc)); | |
977 | fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs); | |
978 | while (this) | |
979 | { | |
980 | fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn), | |
981 | reg_class_names[this->class]); | |
982 | this = this->next_use; | |
983 | } | |
984 | fprintf (rtl_dump_file, "\n"); | |
985 | chains = chains->next_chain; | |
1a43c33f | 986 | } |
7b82b5da | 987 | } |
8582c27b RH |
988 | \f |
989 | /* The following code does forward propagation of hard register copies. | |
990 | The object is to eliminate as many dependencies as possible, so that | |
991 | we have the most scheduling freedom. As a side effect, we also clean | |
3b03c671 | 992 | up some silly register allocation decisions made by reload. This |
8582c27b RH |
993 | code may be obsoleted by a new register allocator. */ |
994 | ||
995 | /* For each register, we have a list of registers that contain the same | |
3b03c671 | 996 | value. The OLDEST_REGNO field points to the head of the list, and |
8582c27b RH |
997 | the NEXT_REGNO field runs through the list. The MODE field indicates |
998 | what mode the data is known to be in; this field is VOIDmode when the | |
999 | register is not known to contain valid data. */ | |
1000 | ||
1001 | struct value_data_entry | |
1002 | { | |
1003 | enum machine_mode mode; | |
1004 | unsigned int oldest_regno; | |
1005 | unsigned int next_regno; | |
1006 | }; | |
1007 | ||
1008 | struct value_data | |
1009 | { | |
1010 | struct value_data_entry e[FIRST_PSEUDO_REGISTER]; | |
752ae914 | 1011 | unsigned int max_value_regs; |
8582c27b RH |
1012 | }; |
1013 | ||
0c20a65f AJ |
1014 | static void kill_value_regno (unsigned, struct value_data *); |
1015 | static void kill_value (rtx, struct value_data *); | |
1016 | static void set_value_regno (unsigned, enum machine_mode, struct value_data *); | |
1017 | static void init_value_data (struct value_data *); | |
1018 | static void kill_clobbered_value (rtx, rtx, void *); | |
1019 | static void kill_set_value (rtx, rtx, void *); | |
1020 | static int kill_autoinc_value (rtx *, void *); | |
1021 | static void copy_value (rtx, rtx, struct value_data *); | |
1022 | static bool mode_change_ok (enum machine_mode, enum machine_mode, | |
1023 | unsigned int); | |
1024 | static rtx maybe_mode_change (enum machine_mode, enum machine_mode, | |
1025 | enum machine_mode, unsigned int, unsigned int); | |
1026 | static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *); | |
1027 | static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx, | |
1028 | struct value_data *); | |
1029 | static bool replace_oldest_value_addr (rtx *, enum reg_class, | |
1030 | enum machine_mode, rtx, | |
1031 | struct value_data *); | |
1032 | static bool replace_oldest_value_mem (rtx, rtx, struct value_data *); | |
1033 | static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *); | |
1034 | extern void debug_value_data (struct value_data *); | |
8582c27b | 1035 | #ifdef ENABLE_CHECKING |
0c20a65f | 1036 | static void validate_value_data (struct value_data *); |
8582c27b RH |
1037 | #endif |
1038 | ||
1039 | /* Kill register REGNO. This involves removing it from any value lists, | |
1040 | and resetting the value mode to VOIDmode. */ | |
1041 | ||
1042 | static void | |
0c20a65f | 1043 | kill_value_regno (unsigned int regno, struct value_data *vd) |
8582c27b RH |
1044 | { |
1045 | unsigned int i, next; | |
1046 | ||
1047 | if (vd->e[regno].oldest_regno != regno) | |
1048 | { | |
1049 | for (i = vd->e[regno].oldest_regno; | |
1050 | vd->e[i].next_regno != regno; | |
1051 | i = vd->e[i].next_regno) | |
1052 | continue; | |
3de23727 | 1053 | vd->e[i].next_regno = vd->e[regno].next_regno; |
8582c27b RH |
1054 | } |
1055 | else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) | |
1056 | { | |
1057 | for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) | |
3b03c671 | 1058 | vd->e[i].oldest_regno = next; |
8582c27b RH |
1059 | } |
1060 | ||
1061 | vd->e[regno].mode = VOIDmode; | |
1062 | vd->e[regno].oldest_regno = regno; | |
1063 | vd->e[regno].next_regno = INVALID_REGNUM; | |
1064 | ||
1065 | #ifdef ENABLE_CHECKING | |
1066 | validate_value_data (vd); | |
1067 | #endif | |
1068 | } | |
1069 | ||
1070 | /* Kill X. This is a convenience function for kill_value_regno | |
3de23727 | 1071 | so that we mind the mode the register is in. */ |
8582c27b RH |
1072 | |
1073 | static void | |
0c20a65f | 1074 | kill_value (rtx x, struct value_data *vd) |
8582c27b | 1075 | { |
8686336f JH |
1076 | /* SUBREGS are supposed to have been eliminated by now. But some |
1077 | ports, e.g. i386 sse, use them to smuggle vector type information | |
1078 | through to instruction selection. Each such SUBREG should simplify, | |
1eeeb6a4 | 1079 | so if we get a NULL we've done something wrong elsewhere. */ |
8686336f JH |
1080 | |
1081 | if (GET_CODE (x) == SUBREG) | |
1082 | x = simplify_subreg (GET_MODE (x), SUBREG_REG (x), | |
1083 | GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); | |
8582c27b | 1084 | if (REG_P (x)) |
3de23727 RH |
1085 | { |
1086 | unsigned int regno = REGNO (x); | |
1087 | unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); | |
752ae914 | 1088 | unsigned int i, j; |
3de23727 | 1089 | |
752ae914 | 1090 | /* Kill the value we're told to kill. */ |
3de23727 RH |
1091 | for (i = 0; i < n; ++i) |
1092 | kill_value_regno (regno + i, vd); | |
752ae914 RH |
1093 | |
1094 | /* Kill everything that overlapped what we're told to kill. */ | |
1095 | if (regno < vd->max_value_regs) | |
1096 | j = 0; | |
1097 | else | |
1098 | j = regno - vd->max_value_regs; | |
1099 | for (; j < regno; ++j) | |
1100 | { | |
1101 | if (vd->e[j].mode == VOIDmode) | |
1102 | continue; | |
2b672c08 | 1103 | n = HARD_REGNO_NREGS (j, vd->e[j].mode); |
752ae914 RH |
1104 | if (j + n > regno) |
1105 | for (i = 0; i < n; ++i) | |
1106 | kill_value_regno (j + i, vd); | |
1107 | } | |
3de23727 | 1108 | } |
8582c27b RH |
1109 | } |
1110 | ||
752ae914 RH |
1111 | /* Remember that REGNO is valid in MODE. */ |
1112 | ||
1113 | static void | |
0c20a65f AJ |
1114 | set_value_regno (unsigned int regno, enum machine_mode mode, |
1115 | struct value_data *vd) | |
752ae914 RH |
1116 | { |
1117 | unsigned int nregs; | |
1118 | ||
1119 | vd->e[regno].mode = mode; | |
1120 | ||
1121 | nregs = HARD_REGNO_NREGS (regno, mode); | |
1122 | if (nregs > vd->max_value_regs) | |
1123 | vd->max_value_regs = nregs; | |
1124 | } | |
1125 | ||
8582c27b RH |
1126 | /* Initialize VD such that there are no known relationships between regs. */ |
1127 | ||
1128 | static void | |
0c20a65f | 1129 | init_value_data (struct value_data *vd) |
8582c27b RH |
1130 | { |
1131 | int i; | |
1132 | for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) | |
1133 | { | |
1134 | vd->e[i].mode = VOIDmode; | |
1135 | vd->e[i].oldest_regno = i; | |
1136 | vd->e[i].next_regno = INVALID_REGNUM; | |
1137 | } | |
752ae914 | 1138 | vd->max_value_regs = 0; |
8582c27b RH |
1139 | } |
1140 | ||
1141 | /* Called through note_stores. If X is clobbered, kill its value. */ | |
1142 | ||
1143 | static void | |
0c20a65f | 1144 | kill_clobbered_value (rtx x, rtx set, void *data) |
8582c27b RH |
1145 | { |
1146 | struct value_data *vd = data; | |
1147 | if (GET_CODE (set) == CLOBBER) | |
1148 | kill_value (x, vd); | |
1149 | } | |
1150 | ||
3b03c671 | 1151 | /* Called through note_stores. If X is set, not clobbered, kill its |
8582c27b RH |
1152 | current value and install it as the root of its own value list. */ |
1153 | ||
1154 | static void | |
0c20a65f | 1155 | kill_set_value (rtx x, rtx set, void *data) |
8582c27b RH |
1156 | { |
1157 | struct value_data *vd = data; | |
c43a12b5 | 1158 | if (GET_CODE (set) != CLOBBER) |
8582c27b | 1159 | { |
3de23727 | 1160 | kill_value (x, vd); |
c43a12b5 | 1161 | if (REG_P (x)) |
3b03c671 | 1162 | set_value_regno (REGNO (x), GET_MODE (x), vd); |
8582c27b RH |
1163 | } |
1164 | } | |
1165 | ||
1166 | /* Called through for_each_rtx. Kill any register used as the base of an | |
1167 | auto-increment expression, and install that register as the root of its | |
1168 | own value list. */ | |
1169 | ||
1170 | static int | |
0c20a65f | 1171 | kill_autoinc_value (rtx *px, void *data) |
8582c27b RH |
1172 | { |
1173 | rtx x = *px; | |
1174 | struct value_data *vd = data; | |
1175 | ||
1176 | if (GET_RTX_CLASS (GET_CODE (x)) == 'a') | |
1177 | { | |
3de23727 RH |
1178 | x = XEXP (x, 0); |
1179 | kill_value (x, vd); | |
752ae914 | 1180 | set_value_regno (REGNO (x), Pmode, vd); |
8582c27b RH |
1181 | return -1; |
1182 | } | |
1183 | ||
1184 | return 0; | |
1185 | } | |
1186 | ||
1187 | /* Assert that SRC has been copied to DEST. Adjust the data structures | |
1188 | to reflect that SRC contains an older copy of the shared value. */ | |
1189 | ||
1190 | static void | |
0c20a65f | 1191 | copy_value (rtx dest, rtx src, struct value_data *vd) |
8582c27b RH |
1192 | { |
1193 | unsigned int dr = REGNO (dest); | |
1194 | unsigned int sr = REGNO (src); | |
21e16bd6 | 1195 | unsigned int dn, sn; |
8582c27b RH |
1196 | unsigned int i; |
1197 | ||
1198 | /* ??? At present, it's possible to see noop sets. It'd be nice if | |
1199 | this were cleaned up beforehand... */ | |
1200 | if (sr == dr) | |
1201 | return; | |
1202 | ||
1203 | /* Do not propagate copies to the stack pointer, as that can leave | |
88cad84b | 1204 | memory accesses with no scheduling dependency on the stack update. */ |
8582c27b RH |
1205 | if (dr == STACK_POINTER_REGNUM) |
1206 | return; | |
1207 | ||
1208 | /* Likewise with the frame pointer, if we're using one. */ | |
1209 | if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) | |
1210 | return; | |
1211 | ||
21e16bd6 RH |
1212 | /* If SRC and DEST overlap, don't record anything. */ |
1213 | dn = HARD_REGNO_NREGS (dr, GET_MODE (dest)); | |
1214 | sn = HARD_REGNO_NREGS (sr, GET_MODE (dest)); | |
1215 | if ((dr > sr && dr < sr + sn) | |
1216 | || (sr > dr && sr < dr + dn)) | |
1217 | return; | |
1218 | ||
8582c27b RH |
1219 | /* If SRC had no assigned mode (i.e. we didn't know it was live) |
1220 | assign it now and assume the value came from an input argument | |
1221 | or somesuch. */ | |
1222 | if (vd->e[sr].mode == VOIDmode) | |
752ae914 | 1223 | set_value_regno (sr, vd->e[dr].mode, vd); |
8582c27b | 1224 | |
27d30956 | 1225 | /* If we are narrowing the input to a smaller number of hard regs, |
dbf65c2f R |
1226 | and it is in big endian, we are really extracting a high part. |
1227 | Since we generally associate a low part of a value with the value itself, | |
1228 | we must not do the same for the high part. | |
1229 | Note we can still get low parts for the same mode combination through | |
1230 | a two-step copy involving differently sized hard regs. | |
1231 | Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each: | |
1232 | (set (reg:DI r0) (reg:DI fr0)) | |
1233 | (set (reg:SI fr2) (reg:SI r0)) | |
1234 | loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while: | |
1235 | (set (reg:SI fr2) (reg:SI fr0)) | |
1236 | loads the high part of (reg:DI fr0) into fr2. | |
1237 | ||
1238 | We can't properly represent the latter case in our tables, so don't | |
1239 | record anything then. */ | |
1240 | else if (sn < (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode) | |
1241 | && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD | |
1242 | ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) | |
1243 | return; | |
1244 | ||
42bd17b7 RH |
1245 | /* If SRC had been assigned a mode narrower than the copy, we can't |
1246 | link DEST into the chain, because not all of the pieces of the | |
1247 | copy came from oldest_regno. */ | |
1248 | else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)) | |
1249 | return; | |
1250 | ||
8582c27b RH |
1251 | /* Link DR at the end of the value chain used by SR. */ |
1252 | ||
1253 | vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; | |
1254 | ||
1255 | for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) | |
1256 | continue; | |
1257 | vd->e[i].next_regno = dr; | |
1258 | ||
1259 | #ifdef ENABLE_CHECKING | |
1260 | validate_value_data (vd); | |
1261 | #endif | |
1262 | } | |
1263 | ||
8610ba70 RH |
1264 | /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ |
1265 | ||
1266 | static bool | |
0c20a65f AJ |
1267 | mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode, |
1268 | unsigned int regno ATTRIBUTE_UNUSED) | |
8610ba70 RH |
1269 | { |
1270 | if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) | |
1271 | return false; | |
1272 | ||
cff9f8d5 AH |
1273 | #ifdef CANNOT_CHANGE_MODE_CLASS |
1274 | return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode); | |
8610ba70 RH |
1275 | #endif |
1276 | ||
1277 | return true; | |
1278 | } | |
1279 | ||
61dde664 R |
1280 | /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it - |
1281 | was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed | |
1282 | in NEW_MODE. | |
1283 | Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */ | |
1284 | ||
1285 | static rtx | |
0c20a65f AJ |
1286 | maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode, |
1287 | enum machine_mode new_mode, unsigned int regno, | |
1288 | unsigned int copy_regno ATTRIBUTE_UNUSED) | |
61dde664 R |
1289 | { |
1290 | if (orig_mode == new_mode) | |
1291 | return gen_rtx_raw_REG (new_mode, regno); | |
1292 | else if (mode_change_ok (orig_mode, new_mode, regno)) | |
1293 | { | |
1294 | int copy_nregs = HARD_REGNO_NREGS (copy_regno, copy_mode); | |
1295 | int use_nregs = HARD_REGNO_NREGS (copy_regno, new_mode); | |
1296 | int copy_offset | |
1297 | = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs); | |
1298 | int offset | |
1299 | = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset; | |
1300 | int byteoffset = offset % UNITS_PER_WORD; | |
1301 | int wordoffset = offset - byteoffset; | |
1302 | ||
1303 | offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0) | |
1304 | + (BYTES_BIG_ENDIAN ? byteoffset : 0)); | |
1305 | return gen_rtx_raw_REG (new_mode, | |
1306 | regno + subreg_regno_offset (regno, orig_mode, | |
1307 | offset, | |
1308 | new_mode)); | |
1309 | } | |
1310 | return NULL_RTX; | |
1311 | } | |
1312 | ||
8582c27b RH |
1313 | /* Find the oldest copy of the value contained in REGNO that is in |
1314 | register class CLASS and has mode MODE. If found, return an rtx | |
1315 | of that oldest register, otherwise return NULL. */ | |
1316 | ||
1317 | static rtx | |
0c20a65f | 1318 | find_oldest_value_reg (enum reg_class class, rtx reg, struct value_data *vd) |
8582c27b | 1319 | { |
3ada20ee RH |
1320 | unsigned int regno = REGNO (reg); |
1321 | enum machine_mode mode = GET_MODE (reg); | |
8582c27b RH |
1322 | unsigned int i; |
1323 | ||
57d1019b RH |
1324 | /* If we are accessing REG in some mode other that what we set it in, |
1325 | make sure that the replacement is valid. In particular, consider | |
1326 | (set (reg:DI r11) (...)) | |
1327 | (set (reg:SI r9) (reg:SI r11)) | |
1328 | (set (reg:SI r10) (...)) | |
1329 | (set (...) (reg:DI r9)) | |
1330 | Replacing r9 with r11 is invalid. */ | |
1331 | if (mode != vd->e[regno].mode) | |
1332 | { | |
1333 | if (HARD_REGNO_NREGS (regno, mode) | |
1334 | > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) | |
1335 | return NULL_RTX; | |
1336 | } | |
1337 | ||
8582c27b | 1338 | for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) |
cffa2189 R |
1339 | { |
1340 | enum machine_mode oldmode = vd->e[i].mode; | |
61dde664 | 1341 | rtx new; |
684bcee5 | 1342 | unsigned int last; |
cffa2189 | 1343 | |
684bcee5 RE |
1344 | for (last = i; last < i + HARD_REGNO_NREGS (i, mode); last++) |
1345 | if (!TEST_HARD_REG_BIT (reg_class_contents[class], last)) | |
1346 | return NULL_RTX; | |
1347 | ||
1348 | if (new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, | |
1349 | regno)) | |
1350 | { | |
1351 | ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg); | |
1352 | REG_ATTRS (new) = REG_ATTRS (reg); | |
1353 | return new; | |
1354 | } | |
cffa2189 | 1355 | } |
8582c27b RH |
1356 | |
1357 | return NULL_RTX; | |
1358 | } | |
1359 | ||
1360 | /* If possible, replace the register at *LOC with the oldest register | |
1361 | in register class CLASS. Return true if successfully replaced. */ | |
1362 | ||
1363 | static bool | |
0c20a65f AJ |
1364 | replace_oldest_value_reg (rtx *loc, enum reg_class class, rtx insn, |
1365 | struct value_data *vd) | |
8582c27b | 1366 | { |
3ada20ee | 1367 | rtx new = find_oldest_value_reg (class, *loc, vd); |
8582c27b RH |
1368 | if (new) |
1369 | { | |
1370 | if (rtl_dump_file) | |
1371 | fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n", | |
1372 | INSN_UID (insn), REGNO (*loc), REGNO (new)); | |
1373 | ||
1374 | *loc = new; | |
1375 | return true; | |
1376 | } | |
1377 | return false; | |
1378 | } | |
1379 | ||
1380 | /* Similar to replace_oldest_value_reg, but *LOC contains an address. | |
1381 | Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or | |
1382 | BASE_REG_CLASS depending on how the register is being considered. */ | |
1383 | ||
1384 | static bool | |
0c20a65f AJ |
1385 | replace_oldest_value_addr (rtx *loc, enum reg_class class, |
1386 | enum machine_mode mode, rtx insn, | |
1387 | struct value_data *vd) | |
8582c27b RH |
1388 | { |
1389 | rtx x = *loc; | |
1390 | RTX_CODE code = GET_CODE (x); | |
1391 | const char *fmt; | |
1392 | int i, j; | |
1393 | bool changed = false; | |
1394 | ||
1395 | switch (code) | |
1396 | { | |
1397 | case PLUS: | |
1398 | { | |
1399 | rtx orig_op0 = XEXP (x, 0); | |
1400 | rtx orig_op1 = XEXP (x, 1); | |
1401 | RTX_CODE code0 = GET_CODE (orig_op0); | |
1402 | RTX_CODE code1 = GET_CODE (orig_op1); | |
1403 | rtx op0 = orig_op0; | |
1404 | rtx op1 = orig_op1; | |
1405 | rtx *locI = NULL; | |
1406 | rtx *locB = NULL; | |
1407 | ||
1408 | if (GET_CODE (op0) == SUBREG) | |
1409 | { | |
1410 | op0 = SUBREG_REG (op0); | |
1411 | code0 = GET_CODE (op0); | |
1412 | } | |
1413 | ||
1414 | if (GET_CODE (op1) == SUBREG) | |
1415 | { | |
1416 | op1 = SUBREG_REG (op1); | |
1417 | code1 = GET_CODE (op1); | |
1418 | } | |
1419 | ||
1420 | if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE | |
1421 | || code0 == ZERO_EXTEND || code1 == MEM) | |
1422 | { | |
1423 | locI = &XEXP (x, 0); | |
1424 | locB = &XEXP (x, 1); | |
1425 | } | |
1426 | else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE | |
1427 | || code1 == ZERO_EXTEND || code0 == MEM) | |
1428 | { | |
1429 | locI = &XEXP (x, 1); | |
1430 | locB = &XEXP (x, 0); | |
1431 | } | |
1432 | else if (code0 == CONST_INT || code0 == CONST | |
1433 | || code0 == SYMBOL_REF || code0 == LABEL_REF) | |
1434 | locB = &XEXP (x, 1); | |
1435 | else if (code1 == CONST_INT || code1 == CONST | |
1436 | || code1 == SYMBOL_REF || code1 == LABEL_REF) | |
1437 | locB = &XEXP (x, 0); | |
1438 | else if (code0 == REG && code1 == REG) | |
1439 | { | |
1440 | int index_op; | |
1441 | ||
1442 | if (REG_OK_FOR_INDEX_P (op0) | |
1443 | && REG_MODE_OK_FOR_BASE_P (op1, mode)) | |
1444 | index_op = 0; | |
1445 | else if (REG_OK_FOR_INDEX_P (op1) | |
1446 | && REG_MODE_OK_FOR_BASE_P (op0, mode)) | |
1447 | index_op = 1; | |
1448 | else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) | |
1449 | index_op = 0; | |
1450 | else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) | |
1451 | index_op = 1; | |
1452 | else if (REG_OK_FOR_INDEX_P (op1)) | |
1453 | index_op = 1; | |
1454 | else | |
1455 | index_op = 0; | |
1456 | ||
1457 | locI = &XEXP (x, index_op); | |
1458 | locB = &XEXP (x, !index_op); | |
1459 | } | |
1460 | else if (code0 == REG) | |
1461 | { | |
1462 | locI = &XEXP (x, 0); | |
1463 | locB = &XEXP (x, 1); | |
1464 | } | |
1465 | else if (code1 == REG) | |
1466 | { | |
1467 | locI = &XEXP (x, 1); | |
1468 | locB = &XEXP (x, 0); | |
1469 | } | |
1470 | ||
1471 | if (locI) | |
1472 | changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode, | |
3b03c671 | 1473 | insn, vd); |
8582c27b | 1474 | if (locB) |
3dcc68a4 NC |
1475 | changed |= replace_oldest_value_addr (locB, |
1476 | MODE_BASE_REG_CLASS (mode), | |
1477 | mode, insn, vd); | |
8582c27b RH |
1478 | return changed; |
1479 | } | |
1480 | ||
1481 | case POST_INC: | |
1482 | case POST_DEC: | |
1483 | case POST_MODIFY: | |
1484 | case PRE_INC: | |
1485 | case PRE_DEC: | |
1486 | case PRE_MODIFY: | |
1487 | return false; | |
1488 | ||
1489 | case MEM: | |
1490 | return replace_oldest_value_mem (x, insn, vd); | |
1491 | ||
1492 | case REG: | |
1493 | return replace_oldest_value_reg (loc, class, insn, vd); | |
1494 | ||
1495 | default: | |
1496 | break; | |
1497 | } | |
1498 | ||
1499 | fmt = GET_RTX_FORMAT (code); | |
1500 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1501 | { | |
1502 | if (fmt[i] == 'e') | |
1503 | changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode, | |
1504 | insn, vd); | |
1505 | else if (fmt[i] == 'E') | |
1506 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
1507 | changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class, | |
3b03c671 | 1508 | mode, insn, vd); |
8582c27b RH |
1509 | } |
1510 | ||
1511 | return changed; | |
1512 | } | |
1513 | ||
1514 | /* Similar to replace_oldest_value_reg, but X contains a memory. */ | |
1515 | ||
1516 | static bool | |
0c20a65f | 1517 | replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd) |
8582c27b | 1518 | { |
3dcc68a4 NC |
1519 | return replace_oldest_value_addr (&XEXP (x, 0), |
1520 | MODE_BASE_REG_CLASS (GET_MODE (x)), | |
8582c27b RH |
1521 | GET_MODE (x), insn, vd); |
1522 | } | |
1523 | ||
1524 | /* Perform the forward copy propagation on basic block BB. */ | |
1525 | ||
1526 | static bool | |
0c20a65f | 1527 | copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd) |
8582c27b RH |
1528 | { |
1529 | bool changed = false; | |
1530 | rtx insn; | |
1531 | ||
a813c111 | 1532 | for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) |
8582c27b RH |
1533 | { |
1534 | int n_ops, i, alt, predicated; | |
3ada20ee | 1535 | bool is_asm; |
8582c27b RH |
1536 | rtx set; |
1537 | ||
1538 | if (! INSN_P (insn)) | |
1539 | { | |
a813c111 | 1540 | if (insn == BB_END (bb)) |
8582c27b RH |
1541 | break; |
1542 | else | |
1543 | continue; | |
1544 | } | |
1545 | ||
1546 | set = single_set (insn); | |
1547 | extract_insn (insn); | |
4be9e9cb | 1548 | if (! constrain_operands (1)) |
3b03c671 | 1549 | fatal_insn_not_found (insn); |
8582c27b RH |
1550 | preprocess_constraints (); |
1551 | alt = which_alternative; | |
1552 | n_ops = recog_data.n_operands; | |
3ada20ee | 1553 | is_asm = asm_noperands (PATTERN (insn)) >= 0; |
8582c27b RH |
1554 | |
1555 | /* Simplify the code below by rewriting things to reflect | |
1556 | matching constraints. Also promote OP_OUT to OP_INOUT | |
1557 | in predicated instructions. */ | |
1558 | ||
1559 | predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; | |
1560 | for (i = 0; i < n_ops; ++i) | |
1561 | { | |
1562 | int matches = recog_op_alt[i][alt].matches; | |
1563 | if (matches >= 0) | |
1564 | recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; | |
1565 | if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 | |
1566 | || (predicated && recog_data.operand_type[i] == OP_OUT)) | |
1567 | recog_data.operand_type[i] = OP_INOUT; | |
1568 | } | |
1569 | ||
1570 | /* For each earlyclobber operand, zap the value data. */ | |
1571 | for (i = 0; i < n_ops; i++) | |
1572 | if (recog_op_alt[i][alt].earlyclobber) | |
1573 | kill_value (recog_data.operand[i], vd); | |
1574 | ||
1575 | /* Within asms, a clobber cannot overlap inputs or outputs. | |
1576 | I wouldn't think this were true for regular insns, but | |
1577 | scan_rtx treats them like that... */ | |
1578 | note_stores (PATTERN (insn), kill_clobbered_value, vd); | |
1579 | ||
1580 | /* Kill all auto-incremented values. */ | |
1581 | /* ??? REG_INC is useless, since stack pushes aren't done that way. */ | |
1582 | for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); | |
1583 | ||
752ae914 RH |
1584 | /* Kill all early-clobbered operands. */ |
1585 | for (i = 0; i < n_ops; i++) | |
1586 | if (recog_op_alt[i][alt].earlyclobber) | |
1587 | kill_value (recog_data.operand[i], vd); | |
1588 | ||
8582c27b RH |
1589 | /* Special-case plain move instructions, since we may well |
1590 | be able to do the move from a different register class. */ | |
1591 | if (set && REG_P (SET_SRC (set))) | |
1592 | { | |
3ada20ee RH |
1593 | rtx src = SET_SRC (set); |
1594 | unsigned int regno = REGNO (src); | |
1595 | enum machine_mode mode = GET_MODE (src); | |
8582c27b RH |
1596 | unsigned int i; |
1597 | rtx new; | |
1598 | ||
57d1019b RH |
1599 | /* If we are accessing SRC in some mode other that what we |
1600 | set it in, make sure that the replacement is valid. */ | |
1601 | if (mode != vd->e[regno].mode) | |
1602 | { | |
1603 | if (HARD_REGNO_NREGS (regno, mode) | |
1604 | > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) | |
1605 | goto no_move_special_case; | |
1606 | } | |
1607 | ||
8582c27b RH |
1608 | /* If the destination is also a register, try to find a source |
1609 | register in the same class. */ | |
1610 | if (REG_P (SET_DEST (set))) | |
1611 | { | |
3ada20ee | 1612 | new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); |
8582c27b RH |
1613 | if (new && validate_change (insn, &SET_SRC (set), new, 0)) |
1614 | { | |
1615 | if (rtl_dump_file) | |
1616 | fprintf (rtl_dump_file, | |
1617 | "insn %u: replaced reg %u with %u\n", | |
1618 | INSN_UID (insn), regno, REGNO (new)); | |
3b03c671 | 1619 | changed = true; |
8582c27b RH |
1620 | goto did_replacement; |
1621 | } | |
1622 | } | |
1623 | ||
1624 | /* Otherwise, try all valid registers and see if its valid. */ | |
1625 | for (i = vd->e[regno].oldest_regno; i != regno; | |
1626 | i = vd->e[i].next_regno) | |
61dde664 R |
1627 | { |
1628 | new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode, | |
1629 | mode, i, regno); | |
1630 | if (new != NULL_RTX) | |
1631 | { | |
1632 | if (validate_change (insn, &SET_SRC (set), new, 0)) | |
1633 | { | |
1634 | ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src); | |
d1d3c9a6 | 1635 | REG_ATTRS (new) = REG_ATTRS (src); |
61dde664 R |
1636 | if (rtl_dump_file) |
1637 | fprintf (rtl_dump_file, | |
1638 | "insn %u: replaced reg %u with %u\n", | |
1639 | INSN_UID (insn), regno, REGNO (new)); | |
1640 | changed = true; | |
1641 | goto did_replacement; | |
1642 | } | |
1643 | } | |
1644 | } | |
8582c27b | 1645 | } |
57d1019b | 1646 | no_move_special_case: |
8582c27b RH |
1647 | |
1648 | /* For each input operand, replace a hard register with the | |
1649 | eldest live copy that's in an appropriate register class. */ | |
1650 | for (i = 0; i < n_ops; i++) | |
1651 | { | |
1652 | bool replaced = false; | |
1653 | ||
1654 | /* Don't scan match_operand here, since we've no reg class | |
1655 | information to pass down. Any operands that we could | |
1656 | substitute in will be represented elsewhere. */ | |
1657 | if (recog_data.constraints[i][0] == '\0') | |
1658 | continue; | |
1659 | ||
3ada20ee RH |
1660 | /* Don't replace in asms intentionally referencing hard regs. */ |
1661 | if (is_asm && GET_CODE (recog_data.operand[i]) == REG | |
1662 | && (REGNO (recog_data.operand[i]) | |
1663 | == ORIGINAL_REGNO (recog_data.operand[i]))) | |
1664 | continue; | |
1665 | ||
8582c27b RH |
1666 | if (recog_data.operand_type[i] == OP_IN) |
1667 | { | |
1668 | if (recog_op_alt[i][alt].is_address) | |
1669 | replaced | |
1670 | = replace_oldest_value_addr (recog_data.operand_loc[i], | |
1671 | recog_op_alt[i][alt].class, | |
1672 | VOIDmode, insn, vd); | |
1673 | else if (REG_P (recog_data.operand[i])) | |
1674 | replaced | |
1675 | = replace_oldest_value_reg (recog_data.operand_loc[i], | |
1676 | recog_op_alt[i][alt].class, | |
1677 | insn, vd); | |
1678 | else if (GET_CODE (recog_data.operand[i]) == MEM) | |
1679 | replaced = replace_oldest_value_mem (recog_data.operand[i], | |
1680 | insn, vd); | |
1681 | } | |
1682 | else if (GET_CODE (recog_data.operand[i]) == MEM) | |
1683 | replaced = replace_oldest_value_mem (recog_data.operand[i], | |
3b03c671 | 1684 | insn, vd); |
8582c27b RH |
1685 | |
1686 | /* If we performed any replacement, update match_dups. */ | |
1687 | if (replaced) | |
1688 | { | |
1689 | int j; | |
1690 | rtx new; | |
1691 | ||
1692 | changed = true; | |
1693 | ||
1694 | new = *recog_data.operand_loc[i]; | |
1695 | recog_data.operand[i] = new; | |
1696 | for (j = 0; j < recog_data.n_dups; j++) | |
1697 | if (recog_data.dup_num[j] == i) | |
1698 | *recog_data.dup_loc[j] = new; | |
1699 | } | |
1700 | } | |
1701 | ||
1702 | did_replacement: | |
1703 | /* Clobber call-clobbered registers. */ | |
1704 | if (GET_CODE (insn) == CALL_INSN) | |
1705 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
1706 | if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) | |
1707 | kill_value_regno (i, vd); | |
1708 | ||
1709 | /* Notice stores. */ | |
1710 | note_stores (PATTERN (insn), kill_set_value, vd); | |
1711 | ||
1712 | /* Notice copies. */ | |
1713 | if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) | |
1714 | copy_value (SET_DEST (set), SET_SRC (set), vd); | |
1715 | ||
a813c111 | 1716 | if (insn == BB_END (bb)) |
8582c27b RH |
1717 | break; |
1718 | } | |
1719 | ||
1720 | return changed; | |
1721 | } | |
1722 | ||
1723 | /* Main entry point for the forward copy propagation optimization. */ | |
1724 | ||
1725 | void | |
0c20a65f | 1726 | copyprop_hardreg_forward (void) |
8582c27b | 1727 | { |
8582c27b | 1728 | struct value_data *all_vd; |
3de23727 | 1729 | bool need_refresh; |
d950dee3 | 1730 | basic_block bb, bbp = 0; |
8582c27b | 1731 | |
3de23727 | 1732 | need_refresh = false; |
8582c27b | 1733 | |
d55bc081 | 1734 | all_vd = xmalloc (sizeof (struct value_data) * last_basic_block); |
8582c27b | 1735 | |
e0082a72 | 1736 | FOR_EACH_BB (bb) |
8582c27b | 1737 | { |
8582c27b RH |
1738 | /* If a block has a single predecessor, that we've already |
1739 | processed, begin with the value data that was live at | |
1740 | the end of the predecessor block. */ | |
d91edf86 | 1741 | /* ??? Ought to use more intelligent queuing of blocks. */ |
e0082a72 ZD |
1742 | if (bb->pred) |
1743 | for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb); | |
8582c27b | 1744 | if (bb->pred |
3b03c671 | 1745 | && ! bb->pred->pred_next |
22c56562 | 1746 | && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) |
e0082a72 ZD |
1747 | && bb->pred->src != ENTRY_BLOCK_PTR |
1748 | && bbp) | |
1749 | all_vd[bb->index] = all_vd[bb->pred->src->index]; | |
8582c27b | 1750 | else |
e0082a72 | 1751 | init_value_data (all_vd + bb->index); |
8582c27b | 1752 | |
e0082a72 | 1753 | if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index)) |
3de23727 | 1754 | need_refresh = true; |
8582c27b RH |
1755 | } |
1756 | ||
1757 | if (need_refresh) | |
1758 | { | |
1759 | if (rtl_dump_file) | |
1760 | fputs ("\n\n", rtl_dump_file); | |
1761 | ||
3de23727 RH |
1762 | /* ??? Irritatingly, delete_noop_moves does not take a set of blocks |
1763 | to scan, so we have to do a life update with no initial set of | |
1764 | blocks Just In Case. */ | |
1765 | delete_noop_moves (get_insns ()); | |
1766 | update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, | |
8582c27b RH |
1767 | PROP_DEATH_NOTES |
1768 | | PROP_SCAN_DEAD_CODE | |
1769 | | PROP_KILL_DEAD_CODE); | |
1770 | } | |
1771 | ||
8582c27b RH |
1772 | free (all_vd); |
1773 | } | |
1774 | ||
1775 | /* Dump the value chain data to stderr. */ | |
1776 | ||
1777 | void | |
0c20a65f | 1778 | debug_value_data (struct value_data *vd) |
8582c27b RH |
1779 | { |
1780 | HARD_REG_SET set; | |
1781 | unsigned int i, j; | |
1782 | ||
1783 | CLEAR_HARD_REG_SET (set); | |
1784 | ||
1785 | for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) | |
1786 | if (vd->e[i].oldest_regno == i) | |
1787 | { | |
1788 | if (vd->e[i].mode == VOIDmode) | |
1789 | { | |
1790 | if (vd->e[i].next_regno != INVALID_REGNUM) | |
1791 | fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", | |
1792 | i, vd->e[i].next_regno); | |
1793 | continue; | |
1794 | } | |
1795 | ||
1796 | SET_HARD_REG_BIT (set, i); | |
1797 | fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); | |
1798 | ||
1799 | for (j = vd->e[i].next_regno; | |
1800 | j != INVALID_REGNUM; | |
1801 | j = vd->e[j].next_regno) | |
1802 | { | |
57d1019b | 1803 | if (TEST_HARD_REG_BIT (set, j)) |
8582c27b RH |
1804 | { |
1805 | fprintf (stderr, "[%u] Loop in regno chain\n", j); | |
1806 | return; | |
1807 | } | |
1808 | ||
1809 | if (vd->e[j].oldest_regno != i) | |
1810 | { | |
1811 | fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", | |
1812 | j, vd->e[j].oldest_regno); | |
1813 | return; | |
1814 | } | |
1815 | SET_HARD_REG_BIT (set, j); | |
1816 | fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); | |
1817 | } | |
1818 | fputc ('\n', stderr); | |
1819 | } | |
1820 | ||
1821 | for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) | |
1822 | if (! TEST_HARD_REG_BIT (set, i) | |
1823 | && (vd->e[i].mode != VOIDmode | |
1824 | || vd->e[i].oldest_regno != i | |
1825 | || vd->e[i].next_regno != INVALID_REGNUM)) | |
1826 | fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", | |
1827 | i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, | |
1828 | vd->e[i].next_regno); | |
1829 | } | |
1830 | ||
1831 | #ifdef ENABLE_CHECKING | |
1832 | static void | |
0c20a65f | 1833 | validate_value_data (struct value_data *vd) |
8582c27b RH |
1834 | { |
1835 | HARD_REG_SET set; | |
1836 | unsigned int i, j; | |
1837 | ||
1838 | CLEAR_HARD_REG_SET (set); | |
1839 | ||
1840 | for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) | |
1841 | if (vd->e[i].oldest_regno == i) | |
1842 | { | |
1843 | if (vd->e[i].mode == VOIDmode) | |
1844 | { | |
1845 | if (vd->e[i].next_regno != INVALID_REGNUM) | |
1846 | internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", | |
1847 | i, vd->e[i].next_regno); | |
1848 | continue; | |
1849 | } | |
1850 | ||
1851 | SET_HARD_REG_BIT (set, i); | |
1852 | ||
1853 | for (j = vd->e[i].next_regno; | |
1854 | j != INVALID_REGNUM; | |
1855 | j = vd->e[j].next_regno) | |
1856 | { | |
1857 | if (TEST_HARD_REG_BIT (set, j)) | |
1858 | internal_error ("validate_value_data: Loop in regno chain (%u)", | |
1859 | j); | |
1860 | if (vd->e[j].oldest_regno != i) | |
1861 | internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", | |
1862 | j, vd->e[j].oldest_regno); | |
1863 | ||
1864 | SET_HARD_REG_BIT (set, j); | |
1865 | } | |
1866 | } | |
1867 | ||
1868 | for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) | |
1869 | if (! TEST_HARD_REG_BIT (set, i) | |
1870 | && (vd->e[i].mode != VOIDmode | |
1871 | || vd->e[i].oldest_regno != i | |
1872 | || vd->e[i].next_regno != INVALID_REGNUM)) | |
1873 | internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", | |
1874 | i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, | |
1875 | vd->e[i].next_regno); | |
1876 | } | |
1877 | #endif |