Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | /* Optimize jump instructions, for GNU compiler. |
2 | Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GNU CC. | |
5 | ||
6 | GNU CC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 1, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GNU CC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GNU CC; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ | |
19 | ||
20 | ||
21 | /* This is the jump-optimization pass of the compiler. | |
22 | It is run two or three times: once before cse, sometimes once after cse, | |
23 | and once after reload (before final). | |
24 | ||
25 | jump_optimize deletes unreachable code and labels that are not used. | |
26 | It also deletes jumps that jump to the following insn, | |
27 | and simplifies jumps around unconditional jumps and jumps | |
28 | to unconditional jumps. | |
29 | ||
30 | Each CODE_LABEL has a count of the times it is used | |
31 | stored in the LABEL_NUSES internal field, and each JUMP_INSN | |
32 | has one label that it refers to stored in the | |
33 | JUMP_LABEL internal field. With this we can detect labels that | |
34 | become unused because of the deletion of all the jumps that | |
35 | formerly used them. The JUMP_LABEL info is sometimes looked | |
36 | at by later passes. | |
37 | ||
38 | Optionally, cross-jumping can be done. Currently it is done | |
39 | only the last time (when after reload and before final). | |
40 | In fact, the code for cross-jumping now assumes that register | |
41 | allocation has been done, since it uses `rtx_renumbered_equal_p'. | |
42 | ||
43 | Jump optimization is done after cse when cse's constant-propagation | |
44 | causes jumps to become unconditional or to be deleted. | |
45 | ||
46 | Unreachable loops are not detected here, because the labels | |
47 | have references and the insns appear reachable from the labels. | |
48 | find_basic_blocks in flow.c finds and deletes such loops. | |
49 | ||
50 | The subroutines delete_insn, redirect_jump, invert_jump, next_real_insn | |
51 | and prev_real_insn are used from other passes as well. */ | |
52 | ||
53 | #include "config.h" | |
54 | #include "rtl.h" | |
55 | #include "flags.h" | |
56 | #include "regs.h" | |
57 | ||
58 | /* ??? Eventually must record somehow the labels used by jumps | |
59 | from nested functions. */ | |
60 | /* Pre-record the next or previous real insn for each label? | |
61 | No, this pass is very fast anyway. */ | |
62 | /* Condense consecutive labels? | |
63 | This would make life analysis faster, maybe. */ | |
64 | /* Optimize jump y; x: ... y: jumpif... x? | |
65 | Don't know if it is worth bothering with. */ | |
66 | /* Optimize two cases of conditional jump to conditional jump? | |
67 | This can never delete any instruction or make anything dead, | |
68 | or even change what is live at any point. | |
69 | So perhaps let combiner do it. */ | |
70 | ||
71 | /* Vector indexed by uid. | |
72 | For each CODE_LABEL, index by its uid to get first unconditional jump | |
73 | that jumps to the label. | |
74 | For each JUMP_INSN, index by its uid to get the next unconditional jump | |
75 | that jumps to the same label. | |
76 | Element 0 is the start of a chain of all return insns. | |
77 | (It is safe to use element 0 because insn uid 0 is not used. */ | |
78 | ||
79 | rtx *jump_chain; | |
80 | ||
81 | rtx delete_insn (); | |
82 | void redirect_jump (); | |
83 | void invert_jump (); | |
84 | rtx next_real_insn (); | |
85 | rtx prev_real_insn (); | |
86 | rtx next_label (); | |
87 | ||
88 | static void mark_jump_label (); | |
89 | static void delete_jump (); | |
90 | static void squeeze_block_notes (); | |
91 | void invert_exp (); | |
92 | static void redirect_exp (); | |
93 | static rtx follow_jumps (); | |
94 | static int tension_vector_labels (); | |
95 | static void find_cross_jump (); | |
96 | static void do_cross_jump (); | |
97 | static enum rtx_code reverse_condition (); | |
98 | static int jump_back_p (); | |
99 | int condjump_p (); | |
100 | \f | |
101 | /* Delete no-op jumps and optimize jumps to jumps | |
102 | and jumps around jumps. | |
103 | Delete unused labels and unreachable code. | |
104 | If CROSS_JUMP is nonzero, detect matching code | |
105 | before a jump and its destination and unify them. | |
106 | If NOOP_MOVES is nonzero, also delete no-op move insns. | |
107 | ||
108 | If `optimize' is zero, don't change any code, | |
109 | just determine whether control drops off the end of the function. | |
110 | This case occurs when we have -W and not -O. | |
111 | It works because `delete_insn' checks the value of `optimize' | |
112 | and refrains from actually deleting when that is 0. */ | |
113 | ||
114 | void | |
115 | jump_optimize (f, cross_jump, noop_moves) | |
116 | rtx f; | |
117 | { | |
118 | register rtx insn; | |
119 | int changed; | |
120 | int first = 1; | |
121 | int max_uid = 0; | |
122 | rtx last_insn; | |
123 | ||
124 | /* Initialize LABEL_NUSES and JUMP_LABEL fields. */ | |
125 | ||
126 | for (insn = f; insn; insn = NEXT_INSN (insn)) | |
127 | { | |
128 | if (GET_CODE (insn) == CODE_LABEL) | |
129 | LABEL_NUSES (insn) = 0; | |
130 | if (GET_CODE (insn) == JUMP_INSN) | |
131 | JUMP_LABEL (insn) = 0; | |
132 | if (INSN_UID (insn) > max_uid) | |
133 | max_uid = INSN_UID (insn); | |
134 | } | |
135 | ||
136 | max_uid++; | |
137 | ||
138 | jump_chain = (rtx *) alloca (max_uid * sizeof (rtx)); | |
139 | bzero (jump_chain, max_uid * sizeof (rtx)); | |
140 | ||
141 | /* Delete insns following barriers, up to next label. */ | |
142 | ||
143 | for (insn = f; insn;) | |
144 | { | |
145 | if (GET_CODE (insn) == BARRIER) | |
146 | { | |
147 | insn = NEXT_INSN (insn); | |
148 | while (insn != 0 && GET_CODE (insn) != CODE_LABEL) | |
149 | { | |
150 | if (GET_CODE (insn) == NOTE | |
151 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END) | |
152 | insn = NEXT_INSN (insn); | |
153 | else | |
154 | insn = delete_insn (insn); | |
155 | } | |
156 | /* INSN is now the code_label. */ | |
157 | } | |
158 | else | |
159 | insn = NEXT_INSN (insn); | |
160 | } | |
161 | ||
162 | /* Mark the label each jump jumps to. | |
163 | Combine consecutive labels, and count uses of labels. | |
164 | ||
165 | For each label, make a chain (using `jump_chain') | |
166 | of all the *unconditional* jumps that jump to it; | |
167 | also make a chain of all returns. */ | |
168 | ||
169 | for (insn = f; insn; insn = NEXT_INSN (insn)) | |
170 | if (GET_CODE (insn) == JUMP_INSN && ! INSN_DELETED_P (insn)) | |
171 | { | |
172 | mark_jump_label (PATTERN (insn), insn, cross_jump); | |
173 | if (JUMP_LABEL (insn) != 0 && simplejump_p (insn)) | |
174 | { | |
175 | jump_chain[INSN_UID (insn)] | |
176 | = jump_chain[INSN_UID (JUMP_LABEL (insn))]; | |
177 | jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn; | |
178 | } | |
179 | if (GET_CODE (PATTERN (insn)) == RETURN) | |
180 | { | |
181 | jump_chain[INSN_UID (insn)] = jump_chain[0]; | |
182 | jump_chain[0] = insn; | |
183 | } | |
184 | } | |
185 | ||
186 | /* Delete all labels already not referenced. | |
187 | Also find the last insn. */ | |
188 | ||
189 | last_insn = 0; | |
190 | for (insn = f; insn; ) | |
191 | { | |
192 | if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0) | |
193 | insn = delete_insn (insn); | |
194 | else | |
195 | { | |
196 | last_insn = insn; | |
197 | insn = NEXT_INSN (insn); | |
198 | } | |
199 | } | |
200 | ||
201 | if (!optimize) | |
202 | { | |
203 | /* See if there is still a NOTE_INSN_FUNCTION_END in this function. | |
204 | If so record that this function can drop off the end. */ | |
205 | ||
206 | insn = last_insn; | |
207 | { | |
208 | int n_labels = 1; | |
209 | while (insn | |
210 | /* One label can follow the end-note: the return label. */ | |
211 | && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0) | |
212 | /* Ordinary insns can follow it if returning a structure. */ | |
213 | || GET_CODE (insn) == INSN | |
214 | /* If machine uses explicit RETURN insns, no epilogue, | |
215 | then one of them follows the note. */ | |
216 | || (GET_CODE (insn) == JUMP_INSN | |
217 | && GET_CODE (PATTERN (insn)) == RETURN) | |
218 | /* Other kinds of notes can follow also. */ | |
219 | || (GET_CODE (insn) == NOTE | |
220 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END))) | |
221 | insn = PREV_INSN (insn); | |
222 | } | |
223 | ||
224 | if (insn && GET_CODE (insn) == NOTE | |
225 | && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END | |
226 | && ! INSN_DELETED_P (insn)) | |
227 | { | |
228 | extern int current_function_returns_null; | |
229 | current_function_returns_null = 1; | |
230 | } | |
231 | /* Zero the "deleted" flag of all the "deleted" insns. */ | |
232 | for (insn = f; insn; insn = NEXT_INSN (insn)) | |
233 | INSN_DELETED_P (insn) = 0; | |
234 | return; | |
235 | } | |
236 | ||
237 | if (noop_moves) | |
238 | for (insn = f; insn; ) | |
239 | { | |
240 | register rtx next = NEXT_INSN (insn); | |
241 | ||
242 | if (GET_CODE (insn) == INSN) | |
243 | { | |
244 | register rtx body = PATTERN (insn); | |
245 | ||
246 | #if 0 /* Keep these insns, since they are used for conditional branch | |
247 | scheduling peepholes on the sparc. */ | |
248 | #endif | |
249 | /* Delete insns that existed just to advise flow-analysis. */ | |
250 | ||
251 | if (GET_CODE (body) == USE | |
252 | || GET_CODE (body) == CLOBBER) | |
253 | delete_insn (insn); | |
254 | else | |
255 | ||
256 | /* Detect and delete no-op move instructions | |
257 | resulting from not allocating a parameter in a register. */ | |
258 | ||
259 | if (GET_CODE (body) == SET | |
260 | && (SET_DEST (body) == SET_SRC (body) | |
261 | || (GET_CODE (SET_DEST (body)) == MEM | |
262 | && GET_CODE (SET_SRC (body)) == MEM | |
263 | && rtx_equal_p (SET_SRC (body), SET_DEST (body)))) | |
264 | && ! (GET_CODE (SET_DEST (body)) == MEM | |
265 | && MEM_VOLATILE_P (SET_DEST (body))) | |
266 | && ! (GET_CODE (SET_SRC (body)) == MEM | |
267 | && MEM_VOLATILE_P (SET_SRC (body)))) | |
268 | delete_insn (insn); | |
269 | ||
270 | /* Detect and ignore no-op move instructions | |
271 | resulting from smart or fortuitous register allocation. */ | |
272 | ||
273 | else if (GET_CODE (body) == SET) | |
274 | { | |
275 | int sreg = true_regnum (SET_SRC (body)); | |
276 | int dreg = true_regnum (SET_DEST (body)); | |
277 | ||
278 | if (sreg == dreg && sreg >= 0) | |
279 | delete_insn (insn); | |
280 | else if (sreg >= 0 && dreg >= 0) | |
281 | { | |
282 | rtx tem = find_equiv_reg (0, insn, 0, | |
283 | sreg, 0, dreg, | |
284 | GET_MODE (SET_SRC (body))); | |
285 | ||
286 | #ifdef PRESERVE_DEATH_INFO_REGNO_P | |
287 | /* Deleting insn could lose a death-note for SREG or DREG | |
288 | so don't do it if final needs accurate death-notes. */ | |
289 | if (! PRESERVE_DEATH_INFO_REGNO_P (sreg) | |
290 | && ! PRESERVE_DEATH_INFO_REGNO_P (dreg)) | |
291 | #endif | |
292 | if (tem != 0 | |
293 | && GET_MODE (tem) == GET_MODE (SET_DEST (body))) | |
294 | delete_insn (insn); | |
295 | } | |
296 | } | |
297 | } | |
298 | insn = next; | |
299 | } | |
300 | ||
301 | /* Now iterate optimizing jumps until nothing changes over one pass. */ | |
302 | changed = 1; | |
303 | while (changed) | |
304 | { | |
305 | register rtx next; | |
306 | changed = 0; | |
307 | ||
308 | for (insn = f; insn; insn = next) | |
309 | { | |
310 | #if 0 | |
311 | /* If NOT the first iteration, if this is the last jump pass | |
312 | (just before final), do the special peephole optimizations. | |
313 | Avoiding the first iteration gives ordinary jump opts | |
314 | a chance to work before peephole opts. */ | |
315 | ||
316 | if (noop_moves && !first && !flag_no_peephole) | |
317 | if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) | |
318 | peephole (insn); | |
319 | #endif | |
320 | ||
321 | /* That could have deleted some insns after INSN, so check now | |
322 | what the following insn is. */ | |
323 | ||
324 | next = NEXT_INSN (insn); | |
325 | ||
326 | /* Tension the labels in dispatch tables. */ | |
327 | ||
328 | if (GET_CODE (insn) == JUMP_INSN) | |
329 | { | |
330 | if (GET_CODE (PATTERN (insn)) == ADDR_VEC) | |
331 | changed |= tension_vector_labels (PATTERN (insn), 0, noop_moves); | |
332 | if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) | |
333 | changed |= tension_vector_labels (PATTERN (insn), 1, noop_moves); | |
334 | } | |
335 | ||
336 | /* Don't allow dropping through into a dispatch table. | |
337 | That means the dispatch insn itself was deleted, | |
338 | so delete the table too. */ | |
339 | ||
340 | if (GET_CODE (insn) == JUMP_INSN) | |
341 | { | |
342 | /* Note: the corresponding job for ADDR_VEC is done | |
343 | in delete_insn. */ | |
344 | ||
345 | /* A vector of offsets is unused if its label | |
346 | is used only once (i.e., from the vector). */ | |
347 | if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC | |
348 | && LABEL_NUSES (XEXP (XEXP (PATTERN (insn), 0), 0)) == 1) | |
349 | { | |
350 | /* So delete both label and vector. */ | |
351 | delete_insn (PREV_INSN (insn)); | |
352 | delete_insn (insn); | |
353 | changed = 1; | |
354 | } | |
355 | } | |
356 | ||
357 | if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn)) | |
358 | { | |
359 | register rtx reallabelprev = prev_real_insn (JUMP_LABEL (insn)); | |
360 | rtx temp; | |
361 | ||
362 | /* Detect jump to following insn. */ | |
363 | if (reallabelprev == insn && condjump_p (insn)) | |
364 | { | |
365 | delete_jump (insn); | |
366 | changed = 1; | |
367 | } | |
368 | /* Detect worthless conditional jump. */ | |
369 | else if ((temp = next_real_insn (insn)) | |
370 | && GET_CODE (temp) == JUMP_INSN | |
371 | && condjump_p (insn) | |
372 | && simplejump_p (temp) | |
373 | && JUMP_LABEL (insn) == JUMP_LABEL (temp)) | |
374 | { | |
375 | delete_jump (insn); | |
376 | changed = 1; | |
377 | next = NEXT_INSN (insn); | |
378 | } | |
379 | /* A jump to a return becomes a return. */ | |
380 | else if (simplejump_p (insn) | |
381 | && (temp = next_real_insn (JUMP_LABEL (insn))) != 0 | |
382 | && GET_CODE (PATTERN (temp)) == RETURN) | |
383 | { | |
384 | PATTERN (insn) = PATTERN (temp); | |
385 | /* Re-recognize this insn. */ | |
386 | INSN_CODE (insn) = -1; | |
387 | } | |
388 | /* Detect jumping over an unconditional jump. */ | |
389 | else if (reallabelprev != 0 | |
390 | && GET_CODE (reallabelprev) == JUMP_INSN | |
391 | && prev_real_insn (reallabelprev) == insn | |
392 | && no_labels_between_p (insn, reallabelprev) | |
393 | && simplejump_p (reallabelprev) | |
394 | /* Ignore this if INSN is a hairy kind of jump, | |
395 | since they may not be invertible. | |
396 | This is conservative; could instead construct | |
397 | the inverted insn and try recognizing it. */ | |
398 | && condjump_p (insn)) | |
399 | { | |
400 | /* Delete the original unconditional jump (and barrier). */ | |
401 | /* But don't let its destination go with it. */ | |
402 | ++LABEL_NUSES (JUMP_LABEL (reallabelprev)); | |
403 | delete_insn (reallabelprev); | |
404 | /* Now change the condition, and make it go to the | |
405 | place the deleted jump went to. | |
406 | This may cause the label after the deletion to go away. | |
407 | But now that the unconditional jump and its barrier | |
408 | are gone, that is ok. */ | |
409 | invert_jump (insn, JUMP_LABEL (reallabelprev)); | |
410 | --LABEL_NUSES (JUMP_LABEL (reallabelprev)); | |
411 | next = insn; | |
412 | changed = 1; | |
413 | } | |
414 | else | |
415 | { | |
416 | /* Detect a jump to a jump. */ | |
417 | { | |
418 | register rtx nlabel | |
419 | = follow_jumps (JUMP_LABEL (insn), noop_moves); | |
420 | if (nlabel != JUMP_LABEL (insn)) | |
421 | { | |
422 | redirect_jump (insn, nlabel); | |
423 | changed = 1; | |
424 | next = insn; | |
425 | } | |
426 | } | |
427 | ||
428 | /* Look for if (foo) bar; else break; */ | |
429 | /* The insns look like this: | |
430 | insn = condjump label1; | |
431 | ...range1 (some insns)... | |
432 | jump label2; | |
433 | label1: | |
434 | ...range2 (some insns)... | |
435 | jump somewhere unconditionally | |
436 | label2: */ | |
437 | { | |
438 | rtx label1 = next_label (insn); | |
439 | rtx range1end = label1 ? prev_real_insn (label1) : 0; | |
440 | /* Don't do this optimization on the first round, so that | |
441 | jump-around-a-jump gets simplified before we ask here | |
442 | whether a jump is unconditional. */ | |
443 | if (! first | |
444 | /* Make sure INSN is something we can invert. */ | |
445 | && condjump_p (insn) | |
446 | && JUMP_LABEL (insn) == label1 | |
447 | && LABEL_NUSES (label1) == 1 | |
448 | && GET_CODE (range1end) == JUMP_INSN | |
449 | && simplejump_p (range1end)) | |
450 | { | |
451 | rtx label2 = next_label (label1); | |
452 | rtx range2end = label2 ? prev_real_insn (label2) : 0; | |
453 | if (range1end != range2end | |
454 | && JUMP_LABEL (range1end) == label2 | |
455 | && GET_CODE (range2end) == JUMP_INSN | |
456 | && GET_CODE (NEXT_INSN (range2end)) == BARRIER) | |
457 | { | |
458 | rtx range1beg = next_real_insn (insn); | |
459 | rtx range2beg = next_real_insn (label1); | |
460 | rtx range1after, range2after; | |
461 | rtx range1before, range2before; | |
462 | ||
463 | /* Don't move NOTEs for blocks; shift them | |
464 | outside the ranges, where they'll stay put. */ | |
465 | squeeze_block_notes (range1beg, range1end); | |
466 | squeeze_block_notes (range2beg, range2end); | |
467 | ||
468 | /* Get current surrounds of the 2 ranges. */ | |
469 | range1before = PREV_INSN (range1beg); | |
470 | range2before = PREV_INSN (range2beg); | |
471 | range1after = NEXT_INSN (range1end); | |
472 | range2after = NEXT_INSN (range2end); | |
473 | ||
474 | /* Splice range2 where range1 was. */ | |
475 | NEXT_INSN (range1before) = range2beg; | |
476 | PREV_INSN (range2beg) = range1before; | |
477 | NEXT_INSN (range2end) = range1after; | |
478 | PREV_INSN (range1after) = range2end; | |
479 | /* Splice range1 where range2 was. */ | |
480 | NEXT_INSN (range2before) = range1beg; | |
481 | PREV_INSN (range1beg) = range2before; | |
482 | NEXT_INSN (range1end) = range2after; | |
483 | PREV_INSN (range2after) = range1end; | |
484 | /* Invert the jump condition, so we | |
485 | still execute the same insns in each case. */ | |
486 | invert_jump (insn, label1); | |
487 | changed = 1; | |
488 | continue; | |
489 | } | |
490 | } | |
491 | } | |
492 | ||
493 | /* Now that the jump has been tensioned, | |
494 | try cross jumping: check for identical code | |
495 | before the jump and before its target label. */ | |
496 | ||
497 | /* First, cross jumping of conditional jumps: */ | |
498 | ||
499 | if (cross_jump && condjump_p (insn)) | |
500 | { | |
501 | rtx newjpos, newlpos; | |
502 | rtx x = prev_real_insn (JUMP_LABEL (insn)); | |
503 | ||
504 | /* A conditional jump may be crossjumped | |
505 | only if the place it jumps to follows | |
506 | an opposing jump that comes back here. */ | |
507 | ||
508 | if (x != 0 && ! jump_back_p (x, insn)) | |
509 | /* We have no opposing jump; | |
510 | cannot cross jump this insn. */ | |
511 | x = 0; | |
512 | ||
513 | newjpos = 0; | |
514 | /* TARGET is nonzero if it is ok to cross jump | |
515 | to code before TARGET. If so, see if matches. */ | |
516 | if (x != 0) | |
517 | find_cross_jump (insn, x, 2, | |
518 | &newjpos, &newlpos); | |
519 | ||
520 | if (newjpos != 0) | |
521 | { | |
522 | do_cross_jump (insn, newjpos, newlpos); | |
523 | /* Make the old conditional jump | |
524 | into an unconditional one. */ | |
525 | SET_SRC (PATTERN (insn)) | |
526 | = gen_rtx (LABEL_REF, VOIDmode, JUMP_LABEL (insn)); | |
527 | emit_barrier_after (insn); | |
528 | changed = 1; | |
529 | next = insn; | |
530 | } | |
531 | } | |
532 | ||
533 | /* Cross jumping of unconditional jumps: | |
534 | a few differences. */ | |
535 | ||
536 | if (cross_jump && simplejump_p (insn)) | |
537 | { | |
538 | rtx newjpos, newlpos; | |
539 | rtx target; | |
540 | ||
541 | newjpos = 0; | |
542 | ||
543 | /* TARGET is nonzero if it is ok to cross jump | |
544 | to code before TARGET. If so, see if matches. */ | |
545 | find_cross_jump (insn, JUMP_LABEL (insn), 1, | |
546 | &newjpos, &newlpos); | |
547 | ||
548 | /* If cannot cross jump to code before the label, | |
549 | see if we can cross jump to another jump to | |
550 | the same label. */ | |
551 | /* Try each other jump to this label. */ | |
552 | if (INSN_UID (JUMP_LABEL (insn)) < max_uid) | |
553 | for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))]; | |
554 | target != 0 && newjpos == 0; | |
555 | target = jump_chain[INSN_UID (target)]) | |
556 | if (target != insn | |
557 | && JUMP_LABEL (target) == JUMP_LABEL (insn) | |
558 | /* Ignore TARGET if it's deleted. */ | |
559 | && ! INSN_DELETED_P (target)) | |
560 | find_cross_jump (insn, target, 2, | |
561 | &newjpos, &newlpos); | |
562 | ||
563 | if (newjpos != 0) | |
564 | { | |
565 | do_cross_jump (insn, newjpos, newlpos); | |
566 | changed = 1; | |
567 | next = insn; | |
568 | } | |
569 | } | |
570 | } | |
571 | } | |
572 | else if (GET_CODE (insn) == JUMP_INSN | |
573 | && GET_CODE (PATTERN (insn)) == RETURN) | |
574 | { | |
575 | /* Return insns all "jump to the same place" | |
576 | so we can cross-jump between any two of them. */ | |
577 | if (cross_jump) | |
578 | { | |
579 | rtx newjpos, newlpos, target; | |
580 | ||
581 | newjpos = 0; | |
582 | ||
583 | /* If cannot cross jump to code before the label, | |
584 | see if we can cross jump to another jump to | |
585 | the same label. */ | |
586 | /* Try each other jump to this label. */ | |
587 | for (target = jump_chain[0]; | |
588 | target != 0 && newjpos == 0; | |
589 | target = jump_chain[INSN_UID (target)]) | |
590 | if (target != insn | |
591 | && ! INSN_DELETED_P (target) | |
592 | && GET_CODE (PATTERN (target)) == RETURN) | |
593 | find_cross_jump (insn, target, 2, | |
594 | &newjpos, &newlpos); | |
595 | ||
596 | if (newjpos != 0) | |
597 | { | |
598 | do_cross_jump (insn, newjpos, newlpos); | |
599 | changed = 1; | |
600 | next = insn; | |
601 | } | |
602 | } | |
603 | } | |
604 | ||
605 | } | |
606 | ||
607 | first = 0; | |
608 | } | |
609 | ||
610 | /* See if there is still a NOTE_INSN_FUNCTION_END in this function. | |
611 | If so, delete it, and record that this function can drop off the end. */ | |
612 | ||
613 | insn = last_insn; | |
614 | { | |
615 | int n_labels = 1; | |
616 | while (insn | |
617 | /* One label can follow the end-note: the return label. */ | |
618 | && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0) | |
619 | /* Ordinary insns can follow it if returning a structure. */ | |
620 | || GET_CODE (insn) == INSN | |
621 | /* If machine uses explicit RETURN insns, no epilogue, | |
622 | then one of them follows the note. */ | |
623 | || (GET_CODE (insn) == JUMP_INSN | |
624 | && GET_CODE (PATTERN (insn)) == RETURN) | |
625 | /* Other kinds of notes can follow also. */ | |
626 | || (GET_CODE (insn) == NOTE | |
627 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END))) | |
628 | insn = PREV_INSN (insn); | |
629 | } | |
630 | if (insn && GET_CODE (insn) == NOTE | |
631 | && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END) | |
632 | { | |
633 | extern int current_function_returns_null; | |
634 | current_function_returns_null = 1; | |
635 | delete_insn (insn); | |
636 | } | |
637 | } | |
638 | \f | |
639 | /* Compare the instructions before insn E1 with those before E2. | |
640 | Assume E1 is a jump that jumps to label E2 | |
641 | (that is not always true but it might as well be). | |
642 | Find the longest possible equivalent sequences | |
643 | and store the first insns of those sequences into *F1 and *F2. | |
644 | Store zero there if no equivalent preceding instructions are found. | |
645 | ||
646 | We give up if we find a label in stream 1. | |
647 | Actually we could transfer that label into stream 2. */ | |
648 | ||
649 | static void | |
650 | find_cross_jump (e1, e2, minimum, f1, f2) | |
651 | rtx e1, e2; | |
652 | int minimum; | |
653 | rtx *f1, *f2; | |
654 | { | |
655 | register rtx i1 = e1, i2 = e2; | |
656 | register rtx p1, p2; | |
657 | ||
658 | rtx last1 = 0, last2 = 0; | |
659 | rtx afterlast1 = 0, afterlast2 = 0; | |
660 | ||
661 | *f1 = 0; | |
662 | *f2 = 0; | |
663 | ||
664 | while (1) | |
665 | { | |
666 | i1 = PREV_INSN (i1); | |
667 | while (i1 && GET_CODE (i1) == NOTE) | |
668 | i1 = PREV_INSN (i1); | |
669 | ||
670 | i2 = PREV_INSN (i2); | |
671 | while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL)) | |
672 | i2 = PREV_INSN (i2); | |
673 | ||
674 | if (i1 == 0) | |
675 | break; | |
676 | ||
677 | /* Don't allow the range of insns preceding E1 or E2 | |
678 | to include the other (E2 or E1). */ | |
679 | if (i2 == e1 || i1 == e2) | |
680 | break; | |
681 | ||
682 | /* If we will get to this code by jumping, those jumps will be | |
683 | tensioned to go directly to the new label (before I2), | |
684 | so this cross-jumping won't cost extra. So reduce the minimum. */ | |
685 | if (GET_CODE (i1) == CODE_LABEL) | |
686 | { | |
687 | --minimum; | |
688 | break; | |
689 | } | |
690 | ||
691 | if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2)) | |
692 | break; | |
693 | ||
694 | p1 = PATTERN (i1); | |
695 | p2 = PATTERN (i2); | |
696 | ||
697 | if (GET_CODE (p1) != GET_CODE (p2) | |
698 | || !rtx_renumbered_equal_p (p1, p2)) | |
699 | { | |
700 | /* Insns fail to match; cross jumping is limited to the following | |
701 | insns. */ | |
702 | ||
703 | /* Don't allow the insn after a compare to be shared by cross-jumping | |
704 | unless the compare is also shared. | |
705 | Here, if either of these non-matching insns is a compare, | |
706 | exclude the following insn from possible cross-jumping. */ | |
707 | if (sets_cc0_p (p1) || sets_cc0_p (p2)) | |
708 | last1 = afterlast1, last2 = afterlast2, ++minimum; | |
709 | ||
710 | /* If cross-jumping here will feed a jump-around-jump optimization, | |
711 | this jump won't cost extra, so reduce the minimum. */ | |
712 | if (GET_CODE (i1) == JUMP_INSN | |
713 | && JUMP_LABEL (i1) | |
714 | && prev_real_insn (JUMP_LABEL (i1)) == e1) | |
715 | --minimum; | |
716 | break; | |
717 | } | |
718 | ||
719 | if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER) | |
720 | { | |
721 | /* Ok, this insn is potentially includable in a cross-jump here. */ | |
722 | afterlast1 = last1, afterlast2 = last2; | |
723 | last1 = i1, last2 = i2, --minimum; | |
724 | } | |
725 | } | |
726 | ||
727 | if (minimum <= 0 && last1 != 0) | |
728 | *f1 = last1, *f2 = last2; | |
729 | } | |
730 | ||
731 | static void | |
732 | do_cross_jump (insn, newjpos, newlpos) | |
733 | rtx insn, newjpos, newlpos; | |
734 | { | |
735 | register rtx label; | |
736 | /* Find an existing label at this point | |
737 | or make a new one if there is none. */ | |
738 | label = PREV_INSN (newlpos); | |
739 | while (label && GET_CODE (label) == NOTE) | |
740 | label = PREV_INSN (label); | |
741 | ||
742 | if (label == 0 || GET_CODE (label) != CODE_LABEL) | |
743 | { | |
744 | label = gen_label_rtx (); | |
745 | emit_label_after (label, PREV_INSN (newlpos)); | |
746 | LABEL_NUSES (label) = 0; | |
747 | } | |
748 | /* Make the same jump insn jump to the new point. */ | |
749 | if (GET_CODE (PATTERN (insn)) == RETURN) | |
750 | { | |
751 | extern rtx gen_jump (); | |
752 | PATTERN (insn) = gen_jump (label); | |
753 | INSN_CODE (insn) = -1; | |
754 | JUMP_LABEL (insn) = label; | |
755 | LABEL_NUSES (label)++; | |
756 | } | |
757 | else | |
758 | redirect_jump (insn, label); | |
759 | /* Delete the matching insns before the jump. */ | |
760 | newjpos = PREV_INSN (newjpos); | |
761 | while (NEXT_INSN (newjpos) != insn) | |
762 | /* Don't delete line numbers. */ | |
763 | if (GET_CODE (NEXT_INSN (newjpos)) != NOTE) | |
764 | delete_insn (NEXT_INSN (newjpos)); | |
765 | else | |
766 | newjpos = NEXT_INSN (newjpos); | |
767 | } | |
768 | \f | |
769 | /* Move all block-beg and block-end notes between START and END | |
770 | out before START. Assume neither START nor END is such a note. */ | |
771 | ||
772 | static void | |
773 | squeeze_block_notes (start, end) | |
774 | rtx start, end; | |
775 | { | |
776 | rtx insn; | |
777 | rtx next; | |
778 | ||
779 | for (insn = start; insn != end; insn = next) | |
780 | { | |
781 | next = NEXT_INSN (insn); | |
782 | if (GET_CODE (insn) == NOTE | |
783 | && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END | |
784 | || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)) | |
785 | { | |
786 | rtx prev = PREV_INSN (insn); | |
787 | PREV_INSN (insn) = PREV_INSN (start); | |
788 | NEXT_INSN (insn) = start; | |
789 | NEXT_INSN (PREV_INSN (insn)) = insn; | |
790 | PREV_INSN (NEXT_INSN (insn)) = insn; | |
791 | NEXT_INSN (prev) = next; | |
792 | PREV_INSN (next) = prev; | |
793 | } | |
794 | } | |
795 | } | |
796 | ||
797 | /* Return 1 if INSN is a jump that jumps to right after TARGET | |
798 | only on the condition that TARGET itself would drop through. | |
799 | Assumes that TARGET is a conditional jump. */ | |
800 | ||
801 | static int | |
802 | jump_back_p (insn, target) | |
803 | rtx insn, target; | |
804 | { | |
805 | rtx cinsn, ctarget, prev; | |
806 | enum rtx_code codei, codet; | |
807 | ||
808 | if (simplejump_p (insn) || ! condjump_p (insn) | |
809 | || simplejump_p (target)) | |
810 | return 0; | |
811 | if (target != prev_real_insn (JUMP_LABEL (insn))) | |
812 | return 0; | |
813 | ||
814 | /* Verify that the condition code was based on a fixed-point computation. | |
815 | Using reverse_condition is invalid for IEEE floating point with nans. */ | |
816 | prev = prev_real_insn (insn); | |
817 | if (! (prev != 0 | |
818 | && GET_CODE (prev) == INSN | |
819 | && GET_CODE (PATTERN (prev)) == SET | |
820 | && SET_DEST (PATTERN (prev)) == cc0_rtx | |
821 | && (GET_MODE_CLASS (GET_MODE (SET_SRC (PATTERN (prev)))) == MODE_INT | |
822 | || (GET_CODE (SET_SRC (PATTERN (prev))) == COMPARE | |
823 | && (GET_MODE_CLASS (GET_MODE (XEXP (SET_SRC (PATTERN (prev)), 0))) | |
824 | == MODE_INT))))) | |
825 | return 0; | |
826 | ||
827 | cinsn = XEXP (SET_SRC (PATTERN (insn)), 0); | |
828 | ctarget = XEXP (SET_SRC (PATTERN (target)), 0); | |
829 | ||
830 | codei = GET_CODE (cinsn); | |
831 | codet = GET_CODE (ctarget); | |
832 | if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx) | |
833 | ||
834 | codei = reverse_condition (codei); | |
835 | if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx) | |
836 | codet = reverse_condition (codet); | |
837 | return (codei == codet | |
838 | && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0)) | |
839 | && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1))); | |
840 | } | |
841 | ||
842 | /* Given an rtx-code for a comparison, return the code | |
843 | for the negated comparison. | |
844 | WATCH OUT! reverse_condition is not safe to use on a jump | |
845 | that might be acting on the results of an IEEE floating point comparison, | |
846 | because of the special treatment of non-signaling nans in comparisons. */ | |
847 | ||
848 | static enum rtx_code | |
849 | reverse_condition (code) | |
850 | enum rtx_code code; | |
851 | { | |
852 | switch (code) | |
853 | { | |
854 | case EQ: | |
855 | return NE; | |
856 | ||
857 | case NE: | |
858 | return EQ; | |
859 | ||
860 | case GT: | |
861 | return LE; | |
862 | ||
863 | case GE: | |
864 | return LT; | |
865 | ||
866 | case LT: | |
867 | return GE; | |
868 | ||
869 | case LE: | |
870 | return GT; | |
871 | ||
872 | case GTU: | |
873 | return LEU; | |
874 | ||
875 | case GEU: | |
876 | return LTU; | |
877 | ||
878 | case LTU: | |
879 | return GEU; | |
880 | ||
881 | case LEU: | |
882 | return GTU; | |
883 | ||
884 | default: | |
885 | abort (); | |
886 | return UNKNOWN; | |
887 | } | |
888 | } | |
889 | \f | |
890 | /* Return 1 if INSN is an unconditional jump and nothing else. */ | |
891 | ||
892 | int | |
893 | simplejump_p (insn) | |
894 | rtx insn; | |
895 | { | |
896 | register rtx x = PATTERN (insn); | |
897 | if (GET_CODE (x) != SET) | |
898 | return 0; | |
899 | if (GET_CODE (SET_DEST (x)) != PC) | |
900 | return 0; | |
901 | if (GET_CODE (SET_SRC (x)) != LABEL_REF) | |
902 | return 0; | |
903 | return 1; | |
904 | } | |
905 | ||
906 | /* Return nonzero if INSN is a (possibly) conditional jump | |
907 | and nothing more. */ | |
908 | ||
909 | int | |
910 | condjump_p (insn) | |
911 | rtx insn; | |
912 | { | |
913 | register rtx x = PATTERN (insn); | |
914 | if (GET_CODE (x) != SET) | |
915 | return 0; | |
916 | if (GET_CODE (SET_DEST (x)) != PC) | |
917 | return 0; | |
918 | if (GET_CODE (SET_SRC (x)) == LABEL_REF) | |
919 | return 1; | |
920 | if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE) | |
921 | return 0; | |
922 | if (XEXP (SET_SRC (x), 2) == pc_rtx | |
923 | && GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF) | |
924 | return 1; | |
925 | if (XEXP (SET_SRC (x), 1) == pc_rtx | |
926 | && GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF) | |
927 | return 1; | |
928 | return 0; | |
929 | } | |
930 | ||
931 | /* Return 1 if X is an RTX that does nothing but set the condition codes | |
932 | and CLOBBER or USE registers. | |
933 | Return -1 if X does explicitly set the condition codes, | |
934 | but also does other things. */ | |
935 | ||
936 | int | |
937 | sets_cc0_p (x) | |
938 | rtx x; | |
939 | { | |
940 | if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx) | |
941 | return 1; | |
942 | if (GET_CODE (x) == PARALLEL) | |
943 | { | |
944 | int i; | |
945 | int sets_cc0 = 0; | |
946 | int other_things = 0; | |
947 | for (i = XVECLEN (x, 0) - 1; i >= 0; i--) | |
948 | { | |
949 | if (GET_CODE (XVECEXP (x, 0, i)) == SET | |
950 | && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx) | |
951 | sets_cc0 = 1; | |
952 | else if (GET_CODE (XVECEXP (x, 0, i)) == SET) | |
953 | other_things = 1; | |
954 | } | |
955 | return ! sets_cc0 ? 0 : other_things ? -1 : 1; | |
956 | } | |
957 | return 0; | |
958 | } | |
959 | ||
960 | /* Return 1 if in between BEG and END there is no CODE_LABEL insn. */ | |
961 | ||
962 | int | |
963 | no_labels_between_p (beg, end) | |
964 | rtx beg, end; | |
965 | { | |
966 | register rtx p; | |
967 | for (p = beg; p != end; p = NEXT_INSN (p)) | |
968 | if (GET_CODE (p) == CODE_LABEL) | |
969 | return 0; | |
970 | return 1; | |
971 | } | |
972 | \f | |
973 | /* Return the last INSN, CALL_INSN or JUMP_INSN before LABEL; | |
974 | or 0, if there is none. */ | |
975 | ||
976 | rtx | |
977 | prev_real_insn (label) | |
978 | rtx label; | |
979 | { | |
980 | register rtx insn = PREV_INSN (label); | |
981 | register RTX_CODE code; | |
982 | ||
983 | while (1) | |
984 | { | |
985 | if (insn == 0) | |
986 | return 0; | |
987 | code = GET_CODE (insn); | |
988 | if (code == INSN || code == CALL_INSN || code == JUMP_INSN) | |
989 | break; | |
990 | insn = PREV_INSN (insn); | |
991 | } | |
992 | ||
993 | return insn; | |
994 | } | |
995 | ||
996 | /* Return the next INSN, CALL_INSN or JUMP_INSN after LABEL; | |
997 | or 0, if there is none. */ | |
998 | ||
999 | rtx | |
1000 | next_real_insn (label) | |
1001 | rtx label; | |
1002 | { | |
1003 | register rtx insn = NEXT_INSN (label); | |
1004 | register RTX_CODE code; | |
1005 | ||
1006 | while (1) | |
1007 | { | |
1008 | if (insn == 0) | |
1009 | return insn; | |
1010 | code = GET_CODE (insn); | |
1011 | if (code == INSN || code == CALL_INSN || code == JUMP_INSN) | |
1012 | break; | |
1013 | insn = NEXT_INSN (insn); | |
1014 | } | |
1015 | ||
1016 | return insn; | |
1017 | } | |
1018 | ||
1019 | /* Return the next CODE_LABEL after the insn INSN, or 0 if there is none. */ | |
1020 | ||
1021 | rtx | |
1022 | next_label (insn) | |
1023 | rtx insn; | |
1024 | { | |
1025 | do insn = NEXT_INSN (insn); | |
1026 | while (insn != 0 && GET_CODE (insn) != CODE_LABEL); | |
1027 | return insn; | |
1028 | } | |
1029 | \f | |
1030 | /* Follow any unconditional jump at LABEL; | |
1031 | return the ultimate label reached by any such chain of jumps. | |
1032 | If LABEL is not followed by a jump, return LABEL. | |
1033 | If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG. */ | |
1034 | ||
1035 | static rtx | |
1036 | follow_jumps (label, ignore_loops) | |
1037 | rtx label; | |
1038 | int ignore_loops; | |
1039 | { | |
1040 | register rtx insn; | |
1041 | register rtx next; | |
1042 | register rtx value = label; | |
1043 | register int depth; | |
1044 | ||
1045 | for (depth = 0; | |
1046 | (depth < 10 | |
1047 | && (insn = next_real_insn (value)) != 0 | |
1048 | && GET_CODE (insn) == JUMP_INSN | |
1049 | && JUMP_LABEL (insn) != 0 | |
1050 | && (next = NEXT_INSN (insn)) | |
1051 | && GET_CODE (next) == BARRIER); | |
1052 | depth++) | |
1053 | { | |
1054 | /* Don't chain through the insn that jumps into a loop | |
1055 | from outside the loop, | |
1056 | since that would create multiple loop entry jumps | |
1057 | and prevent loop optimization. */ | |
1058 | rtx tem; | |
1059 | if (!ignore_loops) | |
1060 | for (tem = value; tem != insn; tem = NEXT_INSN (tem)) | |
1061 | if (GET_CODE (tem) == NOTE | |
1062 | && NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG) | |
1063 | return value; | |
1064 | ||
1065 | /* If we have found a cycle, make the insn jump to itself. */ | |
1066 | if (JUMP_LABEL (insn) == label) | |
1067 | break; | |
1068 | value = JUMP_LABEL (insn); | |
1069 | } | |
1070 | return value; | |
1071 | } | |
1072 | ||
1073 | /* Assuming that field IDX of X is a vector of label_refs, | |
1074 | replace each of them by the ultimate label reached by it. | |
1075 | Return nonzero if a change is made. | |
1076 | If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG. */ | |
1077 | ||
1078 | static int | |
1079 | tension_vector_labels (x, idx, ignore_loops) | |
1080 | register rtx x; | |
1081 | register int idx; | |
1082 | int ignore_loops; | |
1083 | { | |
1084 | int changed = 0; | |
1085 | register int i; | |
1086 | for (i = XVECLEN (x, idx) - 1; i >= 0; i--) | |
1087 | { | |
1088 | register rtx olabel = XEXP (XVECEXP (x, idx, i), 0); | |
1089 | register rtx nlabel = follow_jumps (olabel, ignore_loops); | |
1090 | if (nlabel != olabel) | |
1091 | { | |
1092 | XEXP (XVECEXP (x, idx, i), 0) = nlabel; | |
1093 | ++LABEL_NUSES (nlabel); | |
1094 | if (--LABEL_NUSES (olabel) == 0) | |
1095 | delete_insn (olabel); | |
1096 | changed = 1; | |
1097 | } | |
1098 | } | |
1099 | return changed; | |
1100 | } | |
1101 | \f | |
1102 | /* Find all CODE_LABELs referred to in X, | |
1103 | and increment their use counts. | |
1104 | Also store one of them in JUMP_LABEL (INSN) if INSN is nonzero. | |
1105 | Also, when there are consecutive labels, | |
1106 | canonicalize on the last of them. | |
1107 | ||
1108 | Note that two labels separated by a loop-beginning note | |
1109 | must be kept distinct if we have not yet done loop-optimization, | |
1110 | because the gap between them is where loop-optimize | |
1111 | will want to move invariant code to. CROSS_JUMP tells us | |
1112 | that loop-optimization is done with. */ | |
1113 | ||
1114 | static void | |
1115 | mark_jump_label (x, insn, cross_jump) | |
1116 | register rtx x; | |
1117 | rtx insn; | |
1118 | int cross_jump; | |
1119 | { | |
1120 | register RTX_CODE code = GET_CODE (x); | |
1121 | register int i; | |
1122 | register char *fmt; | |
1123 | ||
1124 | if (code == LABEL_REF) | |
1125 | { | |
1126 | register rtx label = XEXP (x, 0); | |
1127 | register rtx next; | |
1128 | if (GET_CODE (label) != CODE_LABEL) | |
1129 | return; | |
1130 | /* If there are other labels following this one, | |
1131 | replace it with the last of the consecutive labels. */ | |
1132 | for (next = NEXT_INSN (label); next; next = NEXT_INSN (next)) | |
1133 | { | |
1134 | if (GET_CODE (next) == CODE_LABEL) | |
1135 | label = next; | |
1136 | else if (GET_CODE (next) != NOTE | |
1137 | || NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG | |
1138 | || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END) | |
1139 | break; | |
1140 | } | |
1141 | XEXP (x, 0) = label; | |
1142 | ++LABEL_NUSES (label); | |
1143 | if (insn) | |
1144 | JUMP_LABEL (insn) = label; | |
1145 | return; | |
1146 | } | |
1147 | ||
1148 | /* Do walk the labels in a vector, | |
1149 | but don't set its JUMP_LABEL. */ | |
1150 | if (code == ADDR_VEC || code == ADDR_DIFF_VEC) | |
1151 | insn = 0; | |
1152 | ||
1153 | fmt = GET_RTX_FORMAT (code); | |
1154 | for (i = GET_RTX_LENGTH (code); i >= 0; i--) | |
1155 | { | |
1156 | if (fmt[i] == 'e') | |
1157 | mark_jump_label (XEXP (x, i), insn, cross_jump); | |
1158 | else if (fmt[i] == 'E') | |
1159 | { | |
1160 | register int j; | |
1161 | for (j = 0; j < XVECLEN (x, i); j++) | |
1162 | mark_jump_label (XVECEXP (x, i, j), insn, cross_jump); | |
1163 | } | |
1164 | } | |
1165 | } | |
1166 | \f | |
1167 | /* If all INSN does is set the pc, delete it, | |
1168 | and delete the insn that set the condition codes for it | |
1169 | if that's what the previous thing was. */ | |
1170 | ||
1171 | static void | |
1172 | delete_jump (insn) | |
1173 | rtx insn; | |
1174 | { | |
1175 | register rtx x = PATTERN (insn); | |
1176 | register rtx prev; | |
1177 | ||
1178 | if (GET_CODE (x) == SET | |
1179 | && GET_CODE (SET_DEST (x)) == PC) | |
1180 | { | |
1181 | prev = PREV_INSN (insn); | |
1182 | delete_insn (insn); | |
1183 | /* We assume that at this stage | |
1184 | CC's are always set explicitly | |
1185 | and always immediately before the jump that | |
1186 | will use them. So if the previous insn | |
1187 | exists to set the CC's, delete it | |
1188 | (unless it performs auto-increments, etc.). */ | |
1189 | while (prev && GET_CODE (prev) == NOTE) | |
1190 | prev = PREV_INSN (prev); | |
1191 | if (prev && GET_CODE (prev) == INSN | |
1192 | && sets_cc0_p (PATTERN (prev)) > 0 | |
1193 | && !find_reg_note (prev, REG_INC, 0)) | |
1194 | delete_insn (prev); | |
1195 | } | |
1196 | } | |
1197 | \f | |
1198 | /* Delete insn INSN from the chain of insns and update label ref counts. | |
1199 | May delete some following insns as a consequence; may even delete | |
1200 | a label elsewhere and insns that follow it. | |
1201 | ||
1202 | Returns the first insn after INSN that was not deleted. */ | |
1203 | ||
1204 | rtx | |
1205 | delete_insn (insn) | |
1206 | register rtx insn; | |
1207 | { | |
1208 | register rtx next = NEXT_INSN (insn); | |
1209 | register rtx prev = PREV_INSN (insn); | |
1210 | ||
1211 | while (next && INSN_DELETED_P (next)) | |
1212 | next = NEXT_INSN (next); | |
1213 | ||
1214 | /* This insn is already deleted => return first following nondeleted. */ | |
1215 | if (INSN_DELETED_P (insn)) | |
1216 | return next; | |
1217 | ||
1218 | /* Mark this insn as deleted. */ | |
1219 | ||
1220 | INSN_DELETED_P (insn) = 1; | |
1221 | ||
1222 | /* If instruction is followed by a barrier, | |
1223 | delete the barrier too. */ | |
1224 | ||
1225 | if (next != 0 && GET_CODE (next) == BARRIER) | |
1226 | { | |
1227 | INSN_DELETED_P (next) = 1; | |
1228 | next = NEXT_INSN (next); | |
1229 | } | |
1230 | ||
1231 | /* Patch out INSN (and the barrier if any) */ | |
1232 | ||
1233 | if (optimize) | |
1234 | { | |
1235 | if (prev) | |
1236 | NEXT_INSN (prev) = next; | |
1237 | ||
1238 | if (next) | |
1239 | PREV_INSN (next)= prev; | |
1240 | ||
1241 | if (prev && NEXT_INSN (prev) == 0) | |
1242 | set_last_insn (prev); | |
1243 | } | |
1244 | ||
1245 | /* If deleting a jump, decrement the count of the label, | |
1246 | and delete the label if it is now unused. */ | |
1247 | ||
1248 | if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn)) | |
1249 | if (--LABEL_NUSES (JUMP_LABEL (insn)) == 0) | |
1250 | { | |
1251 | /* This can delete NEXT or PREV, | |
1252 | either directly if NEXT is JUMP_LABEL (INSN), | |
1253 | or indirectly through more levels of jumps. */ | |
1254 | delete_insn (JUMP_LABEL (insn)); | |
1255 | /* I feel a little doubtful about this loop, | |
1256 | but I see no clean and sure alternative way | |
1257 | to find the first insn after INSN that is not now deleted. | |
1258 | I hope this works. */ | |
1259 | while (next && INSN_DELETED_P (next)) | |
1260 | next = NEXT_INSN (next); | |
1261 | return next; | |
1262 | } | |
1263 | ||
1264 | while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE)) | |
1265 | prev = PREV_INSN (prev); | |
1266 | ||
1267 | /* If INSN was a label and a dispatch table follows it, | |
1268 | delete the dispatch table. The tablejump must have gone already. | |
1269 | It isn't useful to fall through into a table. */ | |
1270 | ||
1271 | if (GET_CODE (insn) == CODE_LABEL | |
1272 | && NEXT_INSN (insn) != 0 | |
1273 | && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN | |
1274 | && GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC) | |
1275 | next = delete_insn (NEXT_INSN (insn)); | |
1276 | ||
1277 | /* If INSN was a label, delete insns following it if now unreachable. */ | |
1278 | ||
1279 | if (GET_CODE (insn) == CODE_LABEL && prev | |
1280 | && GET_CODE (prev) == BARRIER) | |
1281 | { | |
1282 | register RTX_CODE code; | |
1283 | while (next != 0 | |
1284 | && ((code = GET_CODE (next)) == INSN | |
1285 | || code == JUMP_INSN || code == CALL_INSN | |
1286 | || code == NOTE)) | |
1287 | { | |
1288 | if (code == NOTE | |
1289 | && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END) | |
1290 | next = NEXT_INSN (next); | |
1291 | else | |
1292 | /* Note: if this deletes a jump, it can cause more | |
1293 | deletion of unreachable code, after a different label. | |
1294 | As long as the value from this recursive call is correct, | |
1295 | this invocation functions correctly. */ | |
1296 | next = delete_insn (next); | |
1297 | } | |
1298 | } | |
1299 | ||
1300 | return next; | |
1301 | } | |
1302 | ||
1303 | /* Advance from INSN till reaching something not deleted | |
1304 | then return that. May return INSN itself. */ | |
1305 | ||
1306 | rtx | |
1307 | next_nondeleted_insn (insn) | |
1308 | rtx insn; | |
1309 | { | |
1310 | while (INSN_DELETED_P (insn)) | |
1311 | insn = NEXT_INSN (insn); | |
1312 | return insn; | |
1313 | } | |
1314 | \f | |
1315 | /* Delete a range of insns from FROM to TO, inclusive. | |
1316 | This is for the sake of peephole optimization, so assume | |
1317 | that whatever these insns do will still be done by a new | |
1318 | peephole insn that will replace them. */ | |
1319 | ||
1320 | void | |
1321 | delete_for_peephole (from, to) | |
1322 | register rtx from, to; | |
1323 | { | |
1324 | register rtx insn = from; | |
1325 | ||
1326 | while (1) | |
1327 | { | |
1328 | register rtx next = NEXT_INSN (insn); | |
1329 | register rtx prev = PREV_INSN (insn); | |
1330 | ||
1331 | if (GET_CODE (insn) != NOTE) | |
1332 | { | |
1333 | INSN_DELETED_P (insn) = 1; | |
1334 | ||
1335 | /* Patch this insn out of the chain. */ | |
1336 | /* We don't do this all at once, because we | |
1337 | must preserve all NOTEs. */ | |
1338 | if (prev) | |
1339 | NEXT_INSN (prev) = next; | |
1340 | ||
1341 | if (next) | |
1342 | PREV_INSN (next) = prev; | |
1343 | } | |
1344 | ||
1345 | if (insn == to) | |
1346 | break; | |
1347 | insn = next; | |
1348 | } | |
1349 | ||
1350 | /* Note that if TO is an unconditional jump | |
1351 | we *do not* delete the BARRIER that follows, | |
1352 | since the peephole that replaces this sequence | |
1353 | is also an unconditional jump in that case. */ | |
1354 | } | |
1355 | \f | |
1356 | /* Invert the condition of the jump JUMP, and make it jump | |
1357 | to label NLABEL instead of where it jumps now. */ | |
1358 | ||
1359 | void | |
1360 | invert_jump (jump, nlabel) | |
1361 | rtx jump, nlabel; | |
1362 | { | |
1363 | register rtx olabel = JUMP_LABEL (jump); | |
1364 | invert_exp (PATTERN (jump), olabel, nlabel); | |
1365 | JUMP_LABEL (jump) = nlabel; | |
1366 | ++LABEL_NUSES (nlabel); | |
1367 | INSN_CODE (jump) = -1; | |
1368 | ||
1369 | if (--LABEL_NUSES (olabel) == 0) | |
1370 | delete_insn (olabel); | |
1371 | } | |
1372 | ||
1373 | /* Invert the jump condition of rtx X, | |
1374 | and replace OLABEL with NLABEL throughout. | |
1375 | This is used in do_jump as well as in this file. */ | |
1376 | ||
1377 | void | |
1378 | invert_exp (x, olabel, nlabel) | |
1379 | rtx x; | |
1380 | rtx olabel, nlabel; | |
1381 | { | |
1382 | register RTX_CODE code; | |
1383 | register int i; | |
1384 | register char *fmt; | |
1385 | ||
1386 | if (x == 0) | |
1387 | return; | |
1388 | ||
1389 | code = GET_CODE (x); | |
1390 | if (code == IF_THEN_ELSE) | |
1391 | { | |
1392 | /* Inverting the jump condition of an IF_THEN_ELSE | |
1393 | means exchanging the THEN-part with the ELSE-part. */ | |
1394 | register rtx tem = XEXP (x, 1); | |
1395 | XEXP (x, 1) = XEXP (x, 2); | |
1396 | XEXP (x, 2) = tem; | |
1397 | } | |
1398 | ||
1399 | if (code == LABEL_REF) | |
1400 | { | |
1401 | if (XEXP (x, 0) == olabel) | |
1402 | XEXP (x, 0) = nlabel; | |
1403 | return; | |
1404 | } | |
1405 | ||
1406 | fmt = GET_RTX_FORMAT (code); | |
1407 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1408 | { | |
1409 | if (fmt[i] == 'e') | |
1410 | invert_exp (XEXP (x, i), olabel, nlabel); | |
1411 | if (fmt[i] == 'E') | |
1412 | { | |
1413 | register int j; | |
1414 | for (j = 0; j < XVECLEN (x, i); j++) | |
1415 | invert_exp (XVECEXP (x, i, j), olabel, nlabel); | |
1416 | } | |
1417 | } | |
1418 | } | |
1419 | \f | |
1420 | /* Make jump JUMP jump to label NLABEL instead of where it jumps now. | |
1421 | If the old jump target label is unused as a result, | |
1422 | it and the code following it may be deleted. */ | |
1423 | ||
1424 | void | |
1425 | redirect_jump (jump, nlabel) | |
1426 | rtx jump, nlabel; | |
1427 | { | |
1428 | register rtx olabel = JUMP_LABEL (jump); | |
1429 | ||
1430 | if (nlabel == olabel) | |
1431 | return; | |
1432 | ||
1433 | redirect_exp (PATTERN (jump), olabel, nlabel); | |
1434 | JUMP_LABEL (jump) = nlabel; | |
1435 | ++LABEL_NUSES (nlabel); | |
1436 | INSN_CODE (jump) = -1; | |
1437 | ||
1438 | if (--LABEL_NUSES (olabel) == 0) | |
1439 | delete_insn (olabel); | |
1440 | } | |
1441 | ||
1442 | /* Throughout the rtx X, | |
1443 | alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL). */ | |
1444 | ||
1445 | static void | |
1446 | redirect_exp (x, olabel, nlabel) | |
1447 | rtx x; | |
1448 | rtx olabel, nlabel; | |
1449 | { | |
1450 | register RTX_CODE code = GET_CODE (x); | |
1451 | register int i; | |
1452 | register char *fmt; | |
1453 | ||
1454 | if (code == LABEL_REF) | |
1455 | { | |
1456 | if (XEXP (x, 0) == olabel) | |
1457 | XEXP (x, 0) = nlabel; | |
1458 | return; | |
1459 | } | |
1460 | ||
1461 | fmt = GET_RTX_FORMAT (code); | |
1462 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1463 | { | |
1464 | if (fmt[i] == 'e') | |
1465 | redirect_exp (XEXP (x, i), olabel, nlabel); | |
1466 | if (fmt[i] == 'E') | |
1467 | { | |
1468 | register int j; | |
1469 | for (j = 0; j < XVECLEN (x, i); j++) | |
1470 | redirect_exp (XVECEXP (x, i, j), olabel, nlabel); | |
1471 | } | |
1472 | } | |
1473 | } | |
1474 | \f | |
1475 | /* Like rtx_equal_p except that it considers two REGs as equal | |
1476 | if they renumber to the same value. */ | |
1477 | ||
1478 | int | |
1479 | rtx_renumbered_equal_p (x, y) | |
1480 | rtx x, y; | |
1481 | { | |
1482 | register int i; | |
1483 | register RTX_CODE code = GET_CODE (x); | |
1484 | register char *fmt; | |
1485 | ||
1486 | if (x == y) | |
1487 | return 1; | |
1488 | if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG)) | |
1489 | && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG | |
1490 | && GET_CODE (SUBREG_REG (y)) == REG))) | |
1491 | { | |
1492 | register int j; | |
1493 | ||
1494 | if (GET_MODE (x) != GET_MODE (y)) | |
1495 | return 0; | |
1496 | ||
1497 | if (code == SUBREG) | |
1498 | { | |
1499 | i = REGNO (SUBREG_REG (x)); | |
1500 | if (reg_renumber[i] >= 0) | |
1501 | i = reg_renumber[i]; | |
1502 | i += SUBREG_WORD (x); | |
1503 | } | |
1504 | else | |
1505 | { | |
1506 | i = REGNO (x); | |
1507 | if (reg_renumber[i] >= 0) | |
1508 | i = reg_renumber[i]; | |
1509 | } | |
1510 | if (GET_CODE (y) == SUBREG) | |
1511 | { | |
1512 | j = REGNO (SUBREG_REG (y)); | |
1513 | if (reg_renumber[j] >= 0) | |
1514 | j = reg_renumber[j]; | |
1515 | j += SUBREG_WORD (y); | |
1516 | } | |
1517 | else | |
1518 | { | |
1519 | j = REGNO (y); | |
1520 | if (reg_renumber[j] >= 0) | |
1521 | j = reg_renumber[j]; | |
1522 | } | |
1523 | return i == j; | |
1524 | } | |
1525 | /* Now we have disposed of all the cases | |
1526 | in which different rtx codes can match. */ | |
1527 | if (code != GET_CODE (y)) | |
1528 | return 0; | |
1529 | switch (code) | |
1530 | { | |
1531 | case PC: | |
1532 | case CC0: | |
1533 | case ADDR_VEC: | |
1534 | case ADDR_DIFF_VEC: | |
1535 | return 0; | |
1536 | ||
1537 | case CONST_INT: | |
1538 | return XINT (x, 0) == XINT (y, 0); | |
1539 | ||
1540 | case LABEL_REF: | |
1541 | /* Two label-refs are equivalent if they point at labels | |
1542 | in the same position in the instruction stream. */ | |
1543 | return (next_real_insn (XEXP (x, 0)) | |
1544 | == next_real_insn (XEXP (y, 0))); | |
1545 | ||
1546 | case SYMBOL_REF: | |
1547 | return XSTR (x, 0) == XSTR (y, 0); | |
1548 | } | |
1549 | ||
1550 | /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */ | |
1551 | ||
1552 | if (GET_MODE (x) != GET_MODE (y)) | |
1553 | return 0; | |
1554 | ||
1555 | /* Compare the elements. If any pair of corresponding elements | |
1556 | fail to match, return 0 for the whole things. */ | |
1557 | ||
1558 | fmt = GET_RTX_FORMAT (code); | |
1559 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1560 | { | |
1561 | register int j; | |
1562 | switch (fmt[i]) | |
1563 | { | |
1564 | case 'i': | |
1565 | if (XINT (x, i) != XINT (y, i)) | |
1566 | return 0; | |
1567 | break; | |
1568 | ||
1569 | case 's': | |
1570 | if (strcmp (XSTR (x, i), XSTR (y, i))) | |
1571 | return 0; | |
1572 | break; | |
1573 | ||
1574 | case 'e': | |
1575 | if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i))) | |
1576 | return 0; | |
1577 | break; | |
1578 | ||
1579 | case '0': | |
1580 | break; | |
1581 | ||
1582 | case 'E': | |
1583 | if (XVECLEN (x, i) != XVECLEN (y, i)) | |
1584 | return 0; | |
1585 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
1586 | if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j))) | |
1587 | return 0; | |
1588 | break; | |
1589 | ||
1590 | default: | |
1591 | abort (); | |
1592 | } | |
1593 | } | |
1594 | return 1; | |
1595 | } | |
1596 | \f | |
1597 | /* If X is a hard register or equivalent to one or a subregister of one, | |
1598 | return the hard register number. Otherwise, return -1. | |
1599 | Any rtx is valid for X. */ | |
1600 | ||
1601 | int | |
1602 | true_regnum (x) | |
1603 | rtx x; | |
1604 | { | |
1605 | if (GET_CODE (x) == REG) | |
1606 | { | |
1607 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER) | |
1608 | return reg_renumber[REGNO (x)]; | |
1609 | return REGNO (x); | |
1610 | } | |
1611 | if (GET_CODE (x) == SUBREG) | |
1612 | { | |
1613 | int base = true_regnum (SUBREG_REG (x)); | |
1614 | if (base >= 0 && base < FIRST_PSEUDO_REGISTER) | |
1615 | return SUBREG_WORD (x) + base; | |
1616 | } | |
1617 | return -1; | |
1618 | } |