1 /* Definitions for computing resource usage of specific insns.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
3 2009, 2010 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "diagnostic-core.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "function.h"
30 #include "regs.h"
31 #include "flags.h"
32 #include "output.h"
33 #include "resource.h"
34 #include "except.h"
35 #include "insn-attr.h"
36 #include "params.h"
37 #include "df.h"
38
39 /* This structure is used to record liveness information at the targets or
40 fallthrough insns of branches. We will most likely need the information
41 at targets again, so save them in a hash table rather than recomputing them
42 each time. */
43
44 struct target_info
45 {
46 int uid; /* INSN_UID of target. */
47 struct target_info *next; /* Next info for same hash bucket. */
48 HARD_REG_SET live_regs; /* Registers live at target. */
49 int block; /* Basic block number containing target. */
50 int bb_tick; /* Generation count of basic block info. */
51 };
52
53 #define TARGET_HASH_PRIME 257
54
55 /* Indicates what resources are required at the beginning of the epilogue. */
56 static struct resources start_of_epilogue_needs;
57
58 /* Indicates what resources are required at function end. */
59 static struct resources end_of_function_needs;
60
61 /* Define the hash table itself. */
62 static struct target_info **target_hash_table = NULL;
63
64 /* For each basic block, we maintain a generation number of its basic
65 block info, which is updated each time we move an insn from the
66 target of a jump. This is the generation number indexed by block
67 number. */
68
69 static int *bb_ticks;
70
71 /* Marks registers possibly live at the current place being scanned by
72 mark_target_live_regs. Also used by update_live_status. */
73
74 static HARD_REG_SET current_live_regs;
75
76 /* Marks registers for which we have seen a REG_DEAD note but no assignment.
77 Also only used by the next two functions. */
78
79 static HARD_REG_SET pending_dead_regs;
80
81 static void update_live_status (rtx, const_rtx, void *);
82 static int find_basic_block (rtx, int);
83 static rtx next_insn_no_annul (rtx);
84 static rtx find_dead_or_set_registers (rtx, struct resources*,
85 rtx*, int, struct resources,
86 struct resources);
87
88 /* Utility function called from mark_target_live_regs via note_stores.
89 It deadens any CLOBBERed registers and livens any SET registers. */
90
91 static void
update_live_status(rtx dest,const_rtx x,void * data ATTRIBUTE_UNUSED)92 update_live_status (rtx dest, const_rtx x, void *data ATTRIBUTE_UNUSED)
93 {
94 int first_regno, last_regno;
95 int i;
96
97 if (!REG_P (dest)
98 && (GET_CODE (dest) != SUBREG || !REG_P (SUBREG_REG (dest))))
99 return;
100
101 if (GET_CODE (dest) == SUBREG)
102 {
103 first_regno = subreg_regno (dest);
104 last_regno = first_regno + subreg_nregs (dest);
105
106 }
107 else
108 {
109 first_regno = REGNO (dest);
110 last_regno = END_HARD_REGNO (dest);
111 }
112
113 if (GET_CODE (x) == CLOBBER)
114 for (i = first_regno; i < last_regno; i++)
115 CLEAR_HARD_REG_BIT (current_live_regs, i);
116 else
117 for (i = first_regno; i < last_regno; i++)
118 {
119 SET_HARD_REG_BIT (current_live_regs, i);
120 CLEAR_HARD_REG_BIT (pending_dead_regs, i);
121 }
122 }
123
124 /* Find the number of the basic block with correct live register
125 information that starts closest to INSN. Return -1 if we couldn't
126 find such a basic block or the beginning is more than
127 SEARCH_LIMIT instructions before INSN. Use SEARCH_LIMIT = -1 for
128 an unlimited search.
129
130 The delay slot filling code destroys the control-flow graph so,
131 instead of finding the basic block containing INSN, we search
132 backwards toward a BARRIER where the live register information is
133 correct. */
134
135 static int
find_basic_block(rtx insn,int search_limit)136 find_basic_block (rtx insn, int search_limit)
137 {
138 /* Scan backwards to the previous BARRIER. Then see if we can find a
139 label that starts a basic block. Return the basic block number. */
140 for (insn = prev_nonnote_insn (insn);
141 insn && !BARRIER_P (insn) && search_limit != 0;
142 insn = prev_nonnote_insn (insn), --search_limit)
143 ;
144
145 /* The closest BARRIER is too far away. */
146 if (search_limit == 0)
147 return -1;
148
149 /* The start of the function. */
150 else if (insn == 0)
151 return ENTRY_BLOCK_PTR->next_bb->index;
152
153 /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
154 anything other than a CODE_LABEL or note, we can't find this code. */
155 for (insn = next_nonnote_insn (insn);
156 insn && LABEL_P (insn);
157 insn = next_nonnote_insn (insn))
158 if (BLOCK_FOR_INSN (insn))
159 return BLOCK_FOR_INSN (insn)->index;
160
161 return -1;
162 }
163
164 /* Similar to next_insn, but ignores insns in the delay slots of
165 an annulled branch. */
166
167 static rtx
next_insn_no_annul(rtx insn)168 next_insn_no_annul (rtx insn)
169 {
170 if (insn)
171 {
172 /* If INSN is an annulled branch, skip any insns from the target
173 of the branch. */
174 if (JUMP_P (insn)
175 && INSN_ANNULLED_BRANCH_P (insn)
176 && NEXT_INSN (PREV_INSN (insn)) != insn)
177 {
178 rtx next = NEXT_INSN (insn);
179 enum rtx_code code = GET_CODE (next);
180
181 while ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
182 && INSN_FROM_TARGET_P (next))
183 {
184 insn = next;
185 next = NEXT_INSN (insn);
186 code = GET_CODE (next);
187 }
188 }
189
190 insn = NEXT_INSN (insn);
191 if (insn && NONJUMP_INSN_P (insn)
192 && GET_CODE (PATTERN (insn)) == SEQUENCE)
193 insn = XVECEXP (PATTERN (insn), 0, 0);
194 }
195
196 return insn;
197 }
198
199 /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
200 which resources are referenced by the insn. If INCLUDE_DELAYED_EFFECTS
201 is TRUE, resources used by the called routine will be included for
202 CALL_INSNs. */
203
204 void
mark_referenced_resources(rtx x,struct resources * res,bool include_delayed_effects)205 mark_referenced_resources (rtx x, struct resources *res,
206 bool include_delayed_effects)
207 {
208 enum rtx_code code = GET_CODE (x);
209 int i, j;
210 unsigned int r;
211 const char *format_ptr;
212
213 /* Handle leaf items for which we set resource flags. Also, special-case
214 CALL, SET and CLOBBER operators. */
215 switch (code)
216 {
217 case CONST:
218 case CONST_INT:
219 case CONST_DOUBLE:
220 case CONST_FIXED:
221 case CONST_VECTOR:
222 case PC:
223 case SYMBOL_REF:
224 case LABEL_REF:
225 return;
226
227 case SUBREG:
228 if (!REG_P (SUBREG_REG (x)))
229 mark_referenced_resources (SUBREG_REG (x), res, false);
230 else
231 {
232 unsigned int regno = subreg_regno (x);
233 unsigned int last_regno = regno + subreg_nregs (x);
234
235 gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER);
236 for (r = regno; r < last_regno; r++)
237 SET_HARD_REG_BIT (res->regs, r);
238 }
239 return;
240
241 case REG:
242 gcc_assert (HARD_REGISTER_P (x));
243 add_to_hard_reg_set (&res->regs, GET_MODE (x), REGNO (x));
244 return;
245
246 case MEM:
247 /* If this memory shouldn't change, it really isn't referencing
248 memory. */
249 if (MEM_READONLY_P (x))
250 res->unch_memory = 1;
251 else
252 res->memory = 1;
253 res->volatil |= MEM_VOLATILE_P (x);
254
255 /* Mark registers used to access memory. */
256 mark_referenced_resources (XEXP (x, 0), res, false);
257 return;
258
259 case CC0:
260 res->cc = 1;
261 return;
262
263 case UNSPEC_VOLATILE:
264 case TRAP_IF:
265 case ASM_INPUT:
266 /* Traditional asm's are always volatile. */
267 res->volatil = 1;
268 break;
269
270 case ASM_OPERANDS:
271 res->volatil |= MEM_VOLATILE_P (x);
272
273 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
274 We can not just fall through here since then we would be confused
275 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
276 traditional asms unlike their normal usage. */
277
278 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
279 mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, false);
280 return;
281
282 case CALL:
283 /* The first operand will be a (MEM (xxx)) but doesn't really reference
284 memory. The second operand may be referenced, though. */
285 mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, false);
286 mark_referenced_resources (XEXP (x, 1), res, false);
287 return;
288
289 case SET:
290 /* Usually, the first operand of SET is set, not referenced. But
291 registers used to access memory are referenced. SET_DEST is
292 also referenced if it is a ZERO_EXTRACT. */
293
294 mark_referenced_resources (SET_SRC (x), res, false);
295
296 x = SET_DEST (x);
297 if (GET_CODE (x) == ZERO_EXTRACT
298 || GET_CODE (x) == STRICT_LOW_PART)
299 mark_referenced_resources (x, res, false);
300 else if (GET_CODE (x) == SUBREG)
301 x = SUBREG_REG (x);
302 if (MEM_P (x))
303 mark_referenced_resources (XEXP (x, 0), res, false);
304 return;
305
306 case CLOBBER:
307 return;
308
309 case CALL_INSN:
310 if (include_delayed_effects)
311 {
312 /* A CALL references memory, the frame pointer if it exists, the
313 stack pointer, any global registers and any registers given in
314 USE insns immediately in front of the CALL.
315
316 However, we may have moved some of the parameter loading insns
317 into the delay slot of this CALL. If so, the USE's for them
318 don't count and should be skipped. */
319 rtx insn = PREV_INSN (x);
320 rtx sequence = 0;
321 int seq_size = 0;
322 int i;
323
324 /* If we are part of a delay slot sequence, point at the SEQUENCE. */
325 if (NEXT_INSN (insn) != x)
326 {
327 sequence = PATTERN (NEXT_INSN (insn));
328 seq_size = XVECLEN (sequence, 0);
329 gcc_assert (GET_CODE (sequence) == SEQUENCE);
330 }
331
332 res->memory = 1;
333 SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
334 if (frame_pointer_needed)
335 {
336 SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
337 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
338 SET_HARD_REG_BIT (res->regs, HARD_FRAME_POINTER_REGNUM);
339 #endif
340 }
341
342 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
343 if (global_regs[i])
344 SET_HARD_REG_BIT (res->regs, i);
345
346 /* Check for a REG_SETJMP. If it exists, then we must
347 assume that this call can need any register.
348
349 This is done to be more conservative about how we handle setjmp.
350 We assume that they both use and set all registers. Using all
351 registers ensures that a register will not be considered dead
352 just because it crosses a setjmp call. A register should be
353 considered dead only if the setjmp call returns nonzero. */
354 if (find_reg_note (x, REG_SETJMP, NULL))
355 SET_HARD_REG_SET (res->regs);
356
357 {
358 rtx link;
359
360 for (link = CALL_INSN_FUNCTION_USAGE (x);
361 link;
362 link = XEXP (link, 1))
363 if (GET_CODE (XEXP (link, 0)) == USE)
364 {
365 for (i = 1; i < seq_size; i++)
366 {
367 rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
368 if (GET_CODE (slot_pat) == SET
369 && rtx_equal_p (SET_DEST (slot_pat),
370 XEXP (XEXP (link, 0), 0)))
371 break;
372 }
373 if (i >= seq_size)
374 mark_referenced_resources (XEXP (XEXP (link, 0), 0),
375 res, false);
376 }
377 }
378 }
379
380 /* ... fall through to other INSN processing ... */
381
382 case INSN:
383 case JUMP_INSN:
384
385 #ifdef INSN_REFERENCES_ARE_DELAYED
386 if (! include_delayed_effects
387 && INSN_REFERENCES_ARE_DELAYED (x))
388 return;
389 #endif
390
391 /* No special processing, just speed up. */
392 mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
393 return;
394
395 default:
396 break;
397 }
398
399 /* Process each sub-expression and flag what it needs. */
400 format_ptr = GET_RTX_FORMAT (code);
401 for (i = 0; i < GET_RTX_LENGTH (code); i++)
402 switch (*format_ptr++)
403 {
404 case 'e':
405 mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
406 break;
407
408 case 'E':
409 for (j = 0; j < XVECLEN (x, i); j++)
410 mark_referenced_resources (XVECEXP (x, i, j), res,
411 include_delayed_effects);
412 break;
413 }
414 }
415
416 /* A subroutine of mark_target_live_regs. Search forward from TARGET
417 looking for registers that are set before they are used. These are dead.
418 Stop after passing a few conditional jumps, and/or a small
419 number of unconditional branches. */
420
421 static rtx
find_dead_or_set_registers(rtx target,struct resources * res,rtx * jump_target,int jump_count,struct resources set,struct resources needed)422 find_dead_or_set_registers (rtx target, struct resources *res,
423 rtx *jump_target, int jump_count,
424 struct resources set, struct resources needed)
425 {
426 HARD_REG_SET scratch;
427 rtx insn, next;
428 rtx jump_insn = 0;
429 int i;
430
431 for (insn = target; insn; insn = next)
432 {
433 rtx this_jump_insn = insn;
434
435 next = NEXT_INSN (insn);
436
437 /* If this instruction can throw an exception, then we don't
438 know where we might end up next. That means that we have to
439 assume that whatever we have already marked as live really is
440 live. */
441 if (can_throw_internal (insn))
442 break;
443
444 switch (GET_CODE (insn))
445 {
446 case CODE_LABEL:
447 /* After a label, any pending dead registers that weren't yet
448 used can be made dead. */
449 AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
450 AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
451 CLEAR_HARD_REG_SET (pending_dead_regs);
452
453 continue;
454
455 case BARRIER:
456 case NOTE:
457 continue;
458
459 case INSN:
460 if (GET_CODE (PATTERN (insn)) == USE)
461 {
462 /* If INSN is a USE made by update_block, we care about the
463 underlying insn. Any registers set by the underlying insn
464 are live since the insn is being done somewhere else. */
465 if (INSN_P (XEXP (PATTERN (insn), 0)))
466 mark_set_resources (XEXP (PATTERN (insn), 0), res, 0,
467 MARK_SRC_DEST_CALL);
468
469 /* All other USE insns are to be ignored. */
470 continue;
471 }
472 else if (GET_CODE (PATTERN (insn)) == CLOBBER)
473 continue;
474 else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
475 {
476 /* An unconditional jump can be used to fill the delay slot
477 of a call, so search for a JUMP_INSN in any position. */
478 for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
479 {
480 this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
481 if (JUMP_P (this_jump_insn))
482 break;
483 }
484 }
485
486 default:
487 break;
488 }
489
490 if (JUMP_P (this_jump_insn))
491 {
492 if (jump_count++ < 10)
493 {
494 if (any_uncondjump_p (this_jump_insn)
495 || ANY_RETURN_P (PATTERN (this_jump_insn)))
496 {
497 next = JUMP_LABEL (this_jump_insn);
498 if (ANY_RETURN_P (next))
499 next = NULL_RTX;
500 if (jump_insn == 0)
501 {
502 jump_insn = insn;
503 if (jump_target)
504 *jump_target = JUMP_LABEL (this_jump_insn);
505 }
506 }
507 else if (any_condjump_p (this_jump_insn))
508 {
509 struct resources target_set, target_res;
510 struct resources fallthrough_res;
511
512 /* We can handle conditional branches here by following
513 both paths, and then IOR the results of the two paths
514 together, which will give us registers that are dead
515 on both paths. Since this is expensive, we give it
516 a much higher cost than unconditional branches. The
517 cost was chosen so that we will follow at most 1
518 conditional branch. */
519
520 jump_count += 4;
521 if (jump_count >= 10)
522 break;
523
524 mark_referenced_resources (insn, &needed, true);
525
526 /* For an annulled branch, mark_set_resources ignores slots
527 filled by instructions from the target. This is correct
528 if the branch is not taken. Since we are following both
529 paths from the branch, we must also compute correct info
530 if the branch is taken. We do this by inverting all of
531 the INSN_FROM_TARGET_P bits, calling mark_set_resources,
532 and then inverting the INSN_FROM_TARGET_P bits again. */
533
534 if (GET_CODE (PATTERN (insn)) == SEQUENCE
535 && INSN_ANNULLED_BRANCH_P (this_jump_insn))
536 {
537 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
538 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
539 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
540
541 target_set = set;
542 mark_set_resources (insn, &target_set, 0,
543 MARK_SRC_DEST_CALL);
544
545 for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
546 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
547 = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
548
549 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
550 }
551 else
552 {
553 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
554 target_set = set;
555 }
556
557 target_res = *res;
558 COPY_HARD_REG_SET (scratch, target_set.regs);
559 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
560 AND_COMPL_HARD_REG_SET (target_res.regs, scratch);
561
562 fallthrough_res = *res;
563 COPY_HARD_REG_SET (scratch, set.regs);
564 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
565 AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch);
566
567 if (!ANY_RETURN_P (JUMP_LABEL (this_jump_insn)))
568 find_dead_or_set_registers (JUMP_LABEL (this_jump_insn),
569 &target_res, 0, jump_count,
570 target_set, needed);
571 find_dead_or_set_registers (next,
572 &fallthrough_res, 0, jump_count,
573 set, needed);
574 IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs);
575 AND_HARD_REG_SET (res->regs, fallthrough_res.regs);
576 break;
577 }
578 else
579 break;
580 }
581 else
582 {
583 /* Don't try this optimization if we expired our jump count
584 above, since that would mean there may be an infinite loop
585 in the function being compiled. */
586 jump_insn = 0;
587 break;
588 }
589 }
590
591 mark_referenced_resources (insn, &needed, true);
592 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
593
594 COPY_HARD_REG_SET (scratch, set.regs);
595 AND_COMPL_HARD_REG_SET (scratch, needed.regs);
596 AND_COMPL_HARD_REG_SET (res->regs, scratch);
597 }
598
599 return jump_insn;
600 }
601
602 /* Given X, a part of an insn, and a pointer to a `struct resource',
603 RES, indicate which resources are modified by the insn. If
604 MARK_TYPE is MARK_SRC_DEST_CALL, also mark resources potentially
605 set by the called routine.
606
607 If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
608 objects are being referenced instead of set.
609
610 We never mark the insn as modifying the condition code unless it explicitly
611 SETs CC0 even though this is not totally correct. The reason for this is
612 that we require a SET of CC0 to immediately precede the reference to CC0.
613 So if some other insn sets CC0 as a side-effect, we know it cannot affect
614 our computation and thus may be placed in a delay slot. */
615
616 void
mark_set_resources(rtx x,struct resources * res,int in_dest,enum mark_resource_type mark_type)617 mark_set_resources (rtx x, struct resources *res, int in_dest,
618 enum mark_resource_type mark_type)
619 {
620 enum rtx_code code;
621 int i, j;
622 unsigned int r;
623 const char *format_ptr;
624
625 restart:
626
627 code = GET_CODE (x);
628
629 switch (code)
630 {
631 case NOTE:
632 case BARRIER:
633 case CODE_LABEL:
634 case USE:
635 case CONST_INT:
636 case CONST_DOUBLE:
637 case CONST_FIXED:
638 case CONST_VECTOR:
639 case LABEL_REF:
640 case SYMBOL_REF:
641 case CONST:
642 case PC:
643 /* These don't set any resources. */
644 return;
645
646 case CC0:
647 if (in_dest)
648 res->cc = 1;
649 return;
650
651 case CALL_INSN:
652 /* Called routine modifies the condition code, memory, any registers
653 that aren't saved across calls, global registers and anything
654 explicitly CLOBBERed immediately after the CALL_INSN. */
655
656 if (mark_type == MARK_SRC_DEST_CALL)
657 {
658 rtx link;
659
660 res->cc = res->memory = 1;
661
662 IOR_HARD_REG_SET (res->regs, regs_invalidated_by_call);
663
664 for (link = CALL_INSN_FUNCTION_USAGE (x);
665 link; link = XEXP (link, 1))
666 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
667 mark_set_resources (SET_DEST (XEXP (link, 0)), res, 1,
668 MARK_SRC_DEST);
669
670 /* Check for a REG_SETJMP. If it exists, then we must
671 assume that this call can clobber any register. */
672 if (find_reg_note (x, REG_SETJMP, NULL))
673 SET_HARD_REG_SET (res->regs);
674 }
675
676 /* ... and also what its RTL says it modifies, if anything. */
677
678 case JUMP_INSN:
679 case INSN:
680
681 /* An insn consisting of just a CLOBBER (or USE) is just for flow
682 and doesn't actually do anything, so we ignore it. */
683
684 #ifdef INSN_SETS_ARE_DELAYED
685 if (mark_type != MARK_SRC_DEST_CALL
686 && INSN_SETS_ARE_DELAYED (x))
687 return;
688 #endif
689
690 x = PATTERN (x);
691 if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
692 goto restart;
693 return;
694
695 case SET:
696 /* If the source of a SET is a CALL, this is actually done by
697 the called routine. So only include it if we are to include the
698 effects of the calling routine. */
699
700 mark_set_resources (SET_DEST (x), res,
701 (mark_type == MARK_SRC_DEST_CALL
702 || GET_CODE (SET_SRC (x)) != CALL),
703 mark_type);
704
705 mark_set_resources (SET_SRC (x), res, 0, MARK_SRC_DEST);
706 return;
707
708 case CLOBBER:
709 mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST);
710 return;
711
712 case SEQUENCE:
713 {
714 rtx control = XVECEXP (x, 0, 0);
715 bool annul_p = JUMP_P (control) && INSN_ANNULLED_BRANCH_P (control);
716
717 mark_set_resources (control, res, 0, mark_type);
718 for (i = XVECLEN (x, 0) - 1; i >= 0; --i)
719 {
720 rtx elt = XVECEXP (x, 0, i);
721 if (!annul_p && INSN_FROM_TARGET_P (elt))
722 mark_set_resources (elt, res, 0, mark_type);
723 }
724 }
725 return;
726
727 case POST_INC:
728 case PRE_INC:
729 case POST_DEC:
730 case PRE_DEC:
731 mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST);
732 return;
733
734 case PRE_MODIFY:
735 case POST_MODIFY:
736 mark_set_resources (XEXP (x, 0), res, 1, MARK_SRC_DEST);
737 mark_set_resources (XEXP (XEXP (x, 1), 0), res, 0, MARK_SRC_DEST);
738 mark_set_resources (XEXP (XEXP (x, 1), 1), res, 0, MARK_SRC_DEST);
739 return;
740
741 case SIGN_EXTRACT:
742 case ZERO_EXTRACT:
743 mark_set_resources (XEXP (x, 0), res, in_dest, MARK_SRC_DEST);
744 mark_set_resources (XEXP (x, 1), res, 0, MARK_SRC_DEST);
745 mark_set_resources (XEXP (x, 2), res, 0, MARK_SRC_DEST);
746 return;
747
748 case MEM:
749 if (in_dest)
750 {
751 res->memory = 1;
752 res->unch_memory |= MEM_READONLY_P (x);
753 res->volatil |= MEM_VOLATILE_P (x);
754 }
755
756 mark_set_resources (XEXP (x, 0), res, 0, MARK_SRC_DEST);
757 return;
758
759 case SUBREG:
760 if (in_dest)
761 {
762 if (!REG_P (SUBREG_REG (x)))
763 mark_set_resources (SUBREG_REG (x), res, in_dest, mark_type);
764 else
765 {
766 unsigned int regno = subreg_regno (x);
767 unsigned int last_regno = regno + subreg_nregs (x);
768
769 gcc_assert (last_regno <= FIRST_PSEUDO_REGISTER);
770 for (r = regno; r < last_regno; r++)
771 SET_HARD_REG_BIT (res->regs, r);
772 }
773 }
774 return;
775
776 case REG:
777 if (in_dest)
778 {
779 gcc_assert (HARD_REGISTER_P (x));
780 add_to_hard_reg_set (&res->regs, GET_MODE (x), REGNO (x));
781 }
782 return;
783
784 case UNSPEC_VOLATILE:
785 case ASM_INPUT:
786 /* Traditional asm's are always volatile. */
787 res->volatil = 1;
788 return;
789
790 case TRAP_IF:
791 res->volatil = 1;
792 break;
793
794 case ASM_OPERANDS:
795 res->volatil |= MEM_VOLATILE_P (x);
796
797 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
798 We can not just fall through here since then we would be confused
799 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
800 traditional asms unlike their normal usage. */
801
802 for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
803 mark_set_resources (ASM_OPERANDS_INPUT (x, i), res, in_dest,
804 MARK_SRC_DEST);
805 return;
806
807 default:
808 break;
809 }
810
811 /* Process each sub-expression and flag what it needs. */
812 format_ptr = GET_RTX_FORMAT (code);
813 for (i = 0; i < GET_RTX_LENGTH (code); i++)
814 switch (*format_ptr++)
815 {
816 case 'e':
817 mark_set_resources (XEXP (x, i), res, in_dest, mark_type);
818 break;
819
820 case 'E':
821 for (j = 0; j < XVECLEN (x, i); j++)
822 mark_set_resources (XVECEXP (x, i, j), res, in_dest, mark_type);
823 break;
824 }
825 }
826
827 /* Return TRUE if INSN is a return, possibly with a filled delay slot. */
828
829 static bool
return_insn_p(const_rtx insn)830 return_insn_p (const_rtx insn)
831 {
832 if (JUMP_P (insn) && ANY_RETURN_P (PATTERN (insn)))
833 return true;
834
835 if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
836 return return_insn_p (XVECEXP (PATTERN (insn), 0, 0));
837
838 return false;
839 }
840
841 /* Set the resources that are live at TARGET.
842
843 If TARGET is zero, we refer to the end of the current function and can
844 return our precomputed value.
845
846 Otherwise, we try to find out what is live by consulting the basic block
847 information. This is tricky, because we must consider the actions of
848 reload and jump optimization, which occur after the basic block information
849 has been computed.
850
851 Accordingly, we proceed as follows::
852
853 We find the previous BARRIER and look at all immediately following labels
854 (with no intervening active insns) to see if any of them start a basic
855 block. If we hit the start of the function first, we use block 0.
856
857 Once we have found a basic block and a corresponding first insn, we can
858 accurately compute the live status (by starting at a label following a
859 BARRIER, we are immune to actions taken by reload and jump.) Then we
860 scan all insns between that point and our target. For each CLOBBER (or
861 for call-clobbered regs when we pass a CALL_INSN), mark the appropriate
862 registers are dead. For a SET, mark them as live.
863
864 We have to be careful when using REG_DEAD notes because they are not
865 updated by such things as find_equiv_reg. So keep track of registers
866 marked as dead that haven't been assigned to, and mark them dead at the
867 next CODE_LABEL since reload and jump won't propagate values across labels.
868
869 If we cannot find the start of a basic block (should be a very rare
870 case, if it can happen at all), mark everything as potentially live.
871
872 Next, scan forward from TARGET looking for things set or clobbered
873 before they are used. These are not live.
874
875 Because we can be called many times on the same target, save our results
876 in a hash table indexed by INSN_UID. This is only done if the function
877 init_resource_info () was invoked before we are called. */
878
879 void
mark_target_live_regs(rtx insns,rtx target,struct resources * res)880 mark_target_live_regs (rtx insns, rtx target, struct resources *res)
881 {
882 int b = -1;
883 unsigned int i;
884 struct target_info *tinfo = NULL;
885 rtx insn;
886 rtx jump_insn = 0;
887 rtx jump_target;
888 HARD_REG_SET scratch;
889 struct resources set, needed;
890
891 /* Handle end of function. */
892 if (target == 0 || ANY_RETURN_P (target))
893 {
894 *res = end_of_function_needs;
895 return;
896 }
897
898 /* Handle return insn. */
899 else if (return_insn_p (target))
900 {
901 *res = end_of_function_needs;
902 mark_referenced_resources (target, res, false);
903 return;
904 }
905
906 /* We have to assume memory is needed, but the CC isn't. */
907 res->memory = 1;
908 res->volatil = res->unch_memory = 0;
909 res->cc = 0;
910
911 /* See if we have computed this value already. */
912 if (target_hash_table != NULL)
913 {
914 for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
915 tinfo; tinfo = tinfo->next)
916 if (tinfo->uid == INSN_UID (target))
917 break;
918
919 /* Start by getting the basic block number. If we have saved
920 information, we can get it from there unless the insn at the
921 start of the basic block has been deleted. */
922 if (tinfo && tinfo->block != -1
923 && ! INSN_DELETED_P (BB_HEAD (BASIC_BLOCK (tinfo->block))))
924 b = tinfo->block;
925 }
926
927 if (b == -1)
928 b = find_basic_block (target, MAX_DELAY_SLOT_LIVE_SEARCH);
929
930 if (target_hash_table != NULL)
931 {
932 if (tinfo)
933 {
934 /* If the information is up-to-date, use it. Otherwise, we will
935 update it below. */
936 if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
937 {
938 COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
939 return;
940 }
941 }
942 else
943 {
944 /* Allocate a place to put our results and chain it into the
945 hash table. */
946 tinfo = XNEW (struct target_info);
947 tinfo->uid = INSN_UID (target);
948 tinfo->block = b;
949 tinfo->next
950 = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
951 target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
952 }
953 }
954
955 CLEAR_HARD_REG_SET (pending_dead_regs);
956
957 /* If we found a basic block, get the live registers from it and update
958 them with anything set or killed between its start and the insn before
959 TARGET; this custom life analysis is really about registers so we need
960 to use the LR problem. Otherwise, we must assume everything is live. */
961 if (b != -1)
962 {
963 regset regs_live = DF_LR_IN (BASIC_BLOCK (b));
964 rtx start_insn, stop_insn;
965
966 /* Compute hard regs live at start of block. */
967 REG_SET_TO_HARD_REG_SET (current_live_regs, regs_live);
968
969 /* Get starting and ending insn, handling the case where each might
970 be a SEQUENCE. */
971 start_insn = (b == ENTRY_BLOCK_PTR->next_bb->index ?
972 insns : BB_HEAD (BASIC_BLOCK (b)));
973 stop_insn = target;
974
975 if (NONJUMP_INSN_P (start_insn)
976 && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
977 start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
978
979 if (NONJUMP_INSN_P (stop_insn)
980 && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
981 stop_insn = next_insn (PREV_INSN (stop_insn));
982
983 for (insn = start_insn; insn != stop_insn;
984 insn = next_insn_no_annul (insn))
985 {
986 rtx link;
987 rtx real_insn = insn;
988 enum rtx_code code = GET_CODE (insn);
989
990 if (DEBUG_INSN_P (insn))
991 continue;
992
993 /* If this insn is from the target of a branch, it isn't going to
994 be used in the sequel. If it is used in both cases, this
995 test will not be true. */
996 if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
997 && INSN_FROM_TARGET_P (insn))
998 continue;
999
1000 /* If this insn is a USE made by update_block, we care about the
1001 underlying insn. */
1002 if (code == INSN && GET_CODE (PATTERN (insn)) == USE
1003 && INSN_P (XEXP (PATTERN (insn), 0)))
1004 real_insn = XEXP (PATTERN (insn), 0);
1005
1006 if (CALL_P (real_insn))
1007 {
1008 /* CALL clobbers all call-used regs that aren't fixed except
1009 sp, ap, and fp. Do this before setting the result of the
1010 call live. */
1011 AND_COMPL_HARD_REG_SET (current_live_regs,
1012 regs_invalidated_by_call);
1013
1014 /* A CALL_INSN sets any global register live, since it may
1015 have been modified by the call. */
1016 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1017 if (global_regs[i])
1018 SET_HARD_REG_BIT (current_live_regs, i);
1019 }
1020
1021 /* Mark anything killed in an insn to be deadened at the next
1022 label. Ignore USE insns; the only REG_DEAD notes will be for
1023 parameters. But they might be early. A CALL_INSN will usually
1024 clobber registers used for parameters. It isn't worth bothering
1025 with the unlikely case when it won't. */
1026 if ((NONJUMP_INSN_P (real_insn)
1027 && GET_CODE (PATTERN (real_insn)) != USE
1028 && GET_CODE (PATTERN (real_insn)) != CLOBBER)
1029 || JUMP_P (real_insn)
1030 || CALL_P (real_insn))
1031 {
1032 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
1033 if (REG_NOTE_KIND (link) == REG_DEAD
1034 && REG_P (XEXP (link, 0))
1035 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
1036 add_to_hard_reg_set (&pending_dead_regs,
1037 GET_MODE (XEXP (link, 0)),
1038 REGNO (XEXP (link, 0)));
1039
1040 note_stores (PATTERN (real_insn), update_live_status, NULL);
1041
1042 /* If any registers were unused after this insn, kill them.
1043 These notes will always be accurate. */
1044 for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
1045 if (REG_NOTE_KIND (link) == REG_UNUSED
1046 && REG_P (XEXP (link, 0))
1047 && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
1048 remove_from_hard_reg_set (¤t_live_regs,
1049 GET_MODE (XEXP (link, 0)),
1050 REGNO (XEXP (link, 0)));
1051 }
1052
1053 else if (LABEL_P (real_insn))
1054 {
1055 basic_block bb;
1056
1057 /* A label clobbers the pending dead registers since neither
1058 reload nor jump will propagate a value across a label. */
1059 AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
1060 CLEAR_HARD_REG_SET (pending_dead_regs);
1061
1062 /* We must conservatively assume that all registers that used
1063 to be live here still are. The fallthrough edge may have
1064 left a live register uninitialized. */
1065 bb = BLOCK_FOR_INSN (real_insn);
1066 if (bb)
1067 {
1068 HARD_REG_SET extra_live;
1069
1070 REG_SET_TO_HARD_REG_SET (extra_live, DF_LR_IN (bb));
1071 IOR_HARD_REG_SET (current_live_regs, extra_live);
1072 }
1073 }
1074
1075 /* The beginning of the epilogue corresponds to the end of the
1076 RTL chain when there are no epilogue insns. Certain resources
1077 are implicitly required at that point. */
1078 else if (NOTE_P (real_insn)
1079 && NOTE_KIND (real_insn) == NOTE_INSN_EPILOGUE_BEG)
1080 IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
1081 }
1082
1083 COPY_HARD_REG_SET (res->regs, current_live_regs);
1084 if (tinfo != NULL)
1085 {
1086 tinfo->block = b;
1087 tinfo->bb_tick = bb_ticks[b];
1088 }
1089 }
1090 else
1091 /* We didn't find the start of a basic block. Assume everything
1092 in use. This should happen only extremely rarely. */
1093 SET_HARD_REG_SET (res->regs);
1094
1095 CLEAR_RESOURCE (&set);
1096 CLEAR_RESOURCE (&needed);
1097
1098 jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0,
1099 set, needed);
1100
1101 /* If we hit an unconditional branch, we have another way of finding out
1102 what is live: we can see what is live at the branch target and include
1103 anything used but not set before the branch. We add the live
1104 resources found using the test below to those found until now. */
1105
1106 if (jump_insn)
1107 {
1108 struct resources new_resources;
1109 rtx stop_insn = next_active_insn (jump_insn);
1110
1111 if (!ANY_RETURN_P (jump_target))
1112 jump_target = next_active_insn (jump_target);
1113 mark_target_live_regs (insns, jump_target, &new_resources);
1114 CLEAR_RESOURCE (&set);
1115 CLEAR_RESOURCE (&needed);
1116
1117 /* Include JUMP_INSN in the needed registers. */
1118 for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
1119 {
1120 mark_referenced_resources (insn, &needed, true);
1121
1122 COPY_HARD_REG_SET (scratch, needed.regs);
1123 AND_COMPL_HARD_REG_SET (scratch, set.regs);
1124 IOR_HARD_REG_SET (new_resources.regs, scratch);
1125
1126 mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
1127 }
1128
1129 IOR_HARD_REG_SET (res->regs, new_resources.regs);
1130 }
1131
1132 if (tinfo != NULL)
1133 {
1134 COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
1135 }
1136 }
1137
1138 /* Initialize the resources required by mark_target_live_regs ().
1139 This should be invoked before the first call to mark_target_live_regs. */
1140
1141 void
init_resource_info(rtx epilogue_insn)1142 init_resource_info (rtx epilogue_insn)
1143 {
1144 int i;
1145 basic_block bb;
1146
1147 /* Indicate what resources are required to be valid at the end of the current
1148 function. The condition code never is and memory always is.
1149 The stack pointer is needed unless EXIT_IGNORE_STACK is true
1150 and there is an epilogue that restores the original stack pointer
1151 from the frame pointer. Registers used to return the function value
1152 are needed. Registers holding global variables are needed. */
1153
1154 end_of_function_needs.cc = 0;
1155 end_of_function_needs.memory = 1;
1156 end_of_function_needs.unch_memory = 0;
1157 CLEAR_HARD_REG_SET (end_of_function_needs.regs);
1158
1159 if (frame_pointer_needed)
1160 {
1161 SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
1162 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1163 SET_HARD_REG_BIT (end_of_function_needs.regs, HARD_FRAME_POINTER_REGNUM);
1164 #endif
1165 }
1166 if (!(frame_pointer_needed
1167 && EXIT_IGNORE_STACK
1168 && epilogue_insn
1169 && !current_function_sp_is_unchanging))
1170 SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
1171
1172 if (crtl->return_rtx != 0)
1173 mark_referenced_resources (crtl->return_rtx,
1174 &end_of_function_needs, true);
1175
1176 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1177 if (global_regs[i]
1178 #ifdef EPILOGUE_USES
1179 || EPILOGUE_USES (i)
1180 #endif
1181 )
1182 SET_HARD_REG_BIT (end_of_function_needs.regs, i);
1183
1184 /* The registers required to be live at the end of the function are
1185 represented in the flow information as being dead just prior to
1186 reaching the end of the function. For example, the return of a value
1187 might be represented by a USE of the return register immediately
1188 followed by an unconditional jump to the return label where the
1189 return label is the end of the RTL chain. The end of the RTL chain
1190 is then taken to mean that the return register is live.
1191
1192 This sequence is no longer maintained when epilogue instructions are
1193 added to the RTL chain. To reconstruct the original meaning, the
1194 start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
1195 point where these registers become live (start_of_epilogue_needs).
1196 If epilogue instructions are present, the registers set by those
1197 instructions won't have been processed by flow. Thus, those
1198 registers are additionally required at the end of the RTL chain
1199 (end_of_function_needs). */
1200
1201 start_of_epilogue_needs = end_of_function_needs;
1202
1203 while ((epilogue_insn = next_nonnote_insn (epilogue_insn)))
1204 {
1205 mark_set_resources (epilogue_insn, &end_of_function_needs, 0,
1206 MARK_SRC_DEST_CALL);
1207 if (return_insn_p (epilogue_insn))
1208 break;
1209 }
1210
1211 /* Allocate and initialize the tables used by mark_target_live_regs. */
1212 target_hash_table = XCNEWVEC (struct target_info *, TARGET_HASH_PRIME);
1213 bb_ticks = XCNEWVEC (int, last_basic_block);
1214
1215 /* Set the BLOCK_FOR_INSN of each label that starts a basic block. */
1216 FOR_EACH_BB (bb)
1217 if (LABEL_P (BB_HEAD (bb)))
1218 BLOCK_FOR_INSN (BB_HEAD (bb)) = bb;
1219 }
1220
1221 /* Free up the resources allocated to mark_target_live_regs (). This
1222 should be invoked after the last call to mark_target_live_regs (). */
1223
1224 void
free_resource_info(void)1225 free_resource_info (void)
1226 {
1227 basic_block bb;
1228
1229 if (target_hash_table != NULL)
1230 {
1231 int i;
1232
1233 for (i = 0; i < TARGET_HASH_PRIME; ++i)
1234 {
1235 struct target_info *ti = target_hash_table[i];
1236
1237 while (ti)
1238 {
1239 struct target_info *next = ti->next;
1240 free (ti);
1241 ti = next;
1242 }
1243 }
1244
1245 free (target_hash_table);
1246 target_hash_table = NULL;
1247 }
1248
1249 if (bb_ticks != NULL)
1250 {
1251 free (bb_ticks);
1252 bb_ticks = NULL;
1253 }
1254
1255 FOR_EACH_BB (bb)
1256 if (LABEL_P (BB_HEAD (bb)))
1257 BLOCK_FOR_INSN (BB_HEAD (bb)) = NULL;
1258 }
1259
1260 /* Clear any hashed information that we have stored for INSN. */
1261
1262 void
clear_hashed_info_for_insn(rtx insn)1263 clear_hashed_info_for_insn (rtx insn)
1264 {
1265 struct target_info *tinfo;
1266
1267 if (target_hash_table != NULL)
1268 {
1269 for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
1270 tinfo; tinfo = tinfo->next)
1271 if (tinfo->uid == INSN_UID (insn))
1272 break;
1273
1274 if (tinfo)
1275 tinfo->block = -1;
1276 }
1277 }
1278
1279 /* Increment the tick count for the basic block that contains INSN. */
1280
1281 void
incr_ticks_for_insn(rtx insn)1282 incr_ticks_for_insn (rtx insn)
1283 {
1284 int b = find_basic_block (insn, MAX_DELAY_SLOT_LIVE_SEARCH);
1285
1286 if (b != -1)
1287 bb_ticks[b]++;
1288 }
1289
1290 /* Add TRIAL to the set of resources used at the end of the current
1291 function. */
1292 void
mark_end_of_function_resources(rtx trial,bool include_delayed_effects)1293 mark_end_of_function_resources (rtx trial, bool include_delayed_effects)
1294 {
1295 mark_referenced_resources (trial, &end_of_function_needs,
1296 include_delayed_effects);
1297 }
1298