1/* Analyze RTL for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "target.h"
26#include "rtl.h"
27#include "tree.h"
28#include "predict.h"
29#include "df.h"
30#include "memmodel.h"
31#include "tm_p.h"
32#include "insn-config.h"
33#include "regs.h"
34#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
35#include "recog.h"
36#include "addresses.h"
37#include "rtl-iter.h"
38
39/* Forward declarations */
40static void set_of_1 (rtx, const_rtx, void *);
41static bool covers_regno_p (const_rtx, unsigned int);
42static bool covers_regno_no_parallel_p (const_rtx, unsigned int);
43static int computed_jump_p_1 (const_rtx);
44static void parms_set (rtx, const_rtx, void *);
45
46static unsigned HOST_WIDE_INT cached_nonzero_bits (const_rtx, scalar_int_mode,
47 const_rtx, machine_mode,
48 unsigned HOST_WIDE_INT);
49static unsigned HOST_WIDE_INT nonzero_bits1 (const_rtx, scalar_int_mode,
50 const_rtx, machine_mode,
51 unsigned HOST_WIDE_INT);
52static unsigned int cached_num_sign_bit_copies (const_rtx, scalar_int_mode,
53 const_rtx, machine_mode,
54 unsigned int);
55static unsigned int num_sign_bit_copies1 (const_rtx, scalar_int_mode,
56 const_rtx, machine_mode,
57 unsigned int);
58
59rtx_subrtx_bound_info rtx_all_subrtx_bounds[NUM_RTX_CODE];
60rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[NUM_RTX_CODE];
61
62/* Truncation narrows the mode from SOURCE mode to DESTINATION mode.
63 If TARGET_MODE_REP_EXTENDED (DESTINATION, DESTINATION_REP) is
64 SIGN_EXTEND then while narrowing we also have to enforce the
65 representation and sign-extend the value to mode DESTINATION_REP.
66
67 If the value is already sign-extended to DESTINATION_REP mode we
68 can just switch to DESTINATION mode on it. For each pair of
69 integral modes SOURCE and DESTINATION, when truncating from SOURCE
70 to DESTINATION, NUM_SIGN_BIT_COPIES_IN_REP[SOURCE][DESTINATION]
71 contains the number of high-order bits in SOURCE that have to be
72 copies of the sign-bit so that we can do this mode-switch to
73 DESTINATION. */
74
75static unsigned int
76num_sign_bit_copies_in_rep[MAX_MODE_INT + 1][MAX_MODE_INT + 1];
77
78/* Store X into index I of ARRAY. ARRAY is known to have at least I
79 elements. Return the new base of ARRAY. */
80
81template <typename T>
82typename T::value_type *
83generic_subrtx_iterator <T>::add_single_to_queue (array_type &array,
84 value_type *base,
85 size_t i, value_type x)
86{
87 if (base == array.stack)
88 {
89 if (i < LOCAL_ELEMS)
90 {
91 base[i] = x;
92 return base;
93 }
94 gcc_checking_assert (i == LOCAL_ELEMS);
95 /* A previous iteration might also have moved from the stack to the
96 heap, in which case the heap array will already be big enough. */
97 if (vec_safe_length (array.heap) <= i)
98 vec_safe_grow (array.heap, i + 1);
99 base = array.heap->address ();
100 memcpy (base, array.stack, sizeof (array.stack));
101 base[LOCAL_ELEMS] = x;
102 return base;
103 }
104 unsigned int length = array.heap->length ();
105 if (length > i)
106 {
107 gcc_checking_assert (base == array.heap->address ());
108 base[i] = x;
109 return base;
110 }
111 else
112 {
113 gcc_checking_assert (i == length);
114 vec_safe_push (array.heap, x);
115 return array.heap->address ();
116 }
117}
118
119/* Add the subrtxes of X to worklist ARRAY, starting at END. Return the
120 number of elements added to the worklist. */
121
122template <typename T>
123size_t
124generic_subrtx_iterator <T>::add_subrtxes_to_queue (array_type &array,
125 value_type *base,
126 size_t end, rtx_type x)
127{
128 enum rtx_code code = GET_CODE (x);
129 const char *format = GET_RTX_FORMAT (code);
130 size_t orig_end = end;
131 if (__builtin_expect (INSN_P (x), false))
132 {
133 /* Put the pattern at the top of the queue, since that's what
134 we're likely to want most. It also allows for the SEQUENCE
135 code below. */
136 for (int i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; --i)
137 if (format[i] == 'e')
138 {
139 value_type subx = T::get_value (x->u.fld[i].rt_rtx);
140 if (__builtin_expect (end < LOCAL_ELEMS, true))
141 base[end++] = subx;
142 else
143 base = add_single_to_queue (array, base, end++, subx);
144 }
145 }
146 else
147 for (int i = 0; format[i]; ++i)
148 if (format[i] == 'e')
149 {
150 value_type subx = T::get_value (x->u.fld[i].rt_rtx);
151 if (__builtin_expect (end < LOCAL_ELEMS, true))
152 base[end++] = subx;
153 else
154 base = add_single_to_queue (array, base, end++, subx);
155 }
156 else if (format[i] == 'E')
157 {
158 unsigned int length = GET_NUM_ELEM (x->u.fld[i].rt_rtvec);
159 rtx *vec = x->u.fld[i].rt_rtvec->elem;
160 if (__builtin_expect (end + length <= LOCAL_ELEMS, true))
161 for (unsigned int j = 0; j < length; j++)
162 base[end++] = T::get_value (vec[j]);
163 else
164 for (unsigned int j = 0; j < length; j++)
165 base = add_single_to_queue (array, base, end++,
166 T::get_value (vec[j]));
167 if (code == SEQUENCE && end == length)
168 /* If the subrtxes of the sequence fill the entire array then
169 we know that no other parts of a containing insn are queued.
170 The caller is therefore iterating over the sequence as a
171 PATTERN (...), so we also want the patterns of the
172 subinstructions. */
173 for (unsigned int j = 0; j < length; j++)
174 {
175 typename T::rtx_type x = T::get_rtx (base[j]);
176 if (INSN_P (x))
177 base[j] = T::get_value (PATTERN (x));
178 }
179 }
180 return end - orig_end;
181}
182
183template <typename T>
184void
185generic_subrtx_iterator <T>::free_array (array_type &array)
186{
187 vec_free (array.heap);
188}
189
190template <typename T>
191const size_t generic_subrtx_iterator <T>::LOCAL_ELEMS;
192
193template class generic_subrtx_iterator <const_rtx_accessor>;
194template class generic_subrtx_iterator <rtx_var_accessor>;
195template class generic_subrtx_iterator <rtx_ptr_accessor>;
196
197/* Return 1 if the value of X is unstable
198 (would be different at a different point in the program).
199 The frame pointer, arg pointer, etc. are considered stable
200 (within one function) and so is anything marked `unchanging'. */
201
202int
203rtx_unstable_p (const_rtx x)
204{
205 const RTX_CODE code = GET_CODE (x);
206 int i;
207 const char *fmt;
208
209 switch (code)
210 {
211 case MEM:
212 return !MEM_READONLY_P (x) || rtx_unstable_p (XEXP (x, 0));
213
214 case CONST:
215 CASE_CONST_ANY:
216 case SYMBOL_REF:
217 case LABEL_REF:
218 return 0;
219
220 case REG:
221 /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */
222 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
223 /* The arg pointer varies if it is not a fixed register. */
224 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
225 return 0;
226 /* ??? When call-clobbered, the value is stable modulo the restore
227 that must happen after a call. This currently screws up local-alloc
228 into believing that the restore is not needed. */
229 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED && x == pic_offset_table_rtx)
230 return 0;
231 return 1;
232
233 case ASM_OPERANDS:
234 if (MEM_VOLATILE_P (x))
235 return 1;
236
237 /* Fall through. */
238
239 default:
240 break;
241 }
242
243 fmt = GET_RTX_FORMAT (code);
244 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
245 if (fmt[i] == 'e')
246 {
247 if (rtx_unstable_p (XEXP (x, i)))
248 return 1;
249 }
250 else if (fmt[i] == 'E')
251 {
252 int j;
253 for (j = 0; j < XVECLEN (x, i); j++)
254 if (rtx_unstable_p (XVECEXP (x, i, j)))
255 return 1;
256 }
257
258 return 0;
259}
260
261/* Return 1 if X has a value that can vary even between two
262 executions of the program. 0 means X can be compared reliably
263 against certain constants or near-constants.
264 FOR_ALIAS is nonzero if we are called from alias analysis; if it is
265 zero, we are slightly more conservative.
266 The frame pointer and the arg pointer are considered constant. */
267
268bool
269rtx_varies_p (const_rtx x, bool for_alias)
270{
271 RTX_CODE code;
272 int i;
273 const char *fmt;
274
275 if (!x)
276 return 0;
277
278 code = GET_CODE (x);
279 switch (code)
280 {
281 case MEM:
282 return !MEM_READONLY_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
283
284 case CONST:
285 CASE_CONST_ANY:
286 case SYMBOL_REF:
287 case LABEL_REF:
288 return 0;
289
290 case REG:
291 /* Note that we have to test for the actual rtx used for the frame
292 and arg pointers and not just the register number in case we have
293 eliminated the frame and/or arg pointer and are using it
294 for pseudos. */
295 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
296 /* The arg pointer varies if it is not a fixed register. */
297 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
298 return 0;
299 if (x == pic_offset_table_rtx
300 /* ??? When call-clobbered, the value is stable modulo the restore
301 that must happen after a call. This currently screws up
302 local-alloc into believing that the restore is not needed, so we
303 must return 0 only if we are called from alias analysis. */
304 && (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED || for_alias))
305 return 0;
306 return 1;
307
308 case LO_SUM:
309 /* The operand 0 of a LO_SUM is considered constant
310 (in fact it is related specifically to operand 1)
311 during alias analysis. */
312 return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
313 || rtx_varies_p (XEXP (x, 1), for_alias);
314
315 case ASM_OPERANDS:
316 if (MEM_VOLATILE_P (x))
317 return 1;
318
319 /* Fall through. */
320
321 default:
322 break;
323 }
324
325 fmt = GET_RTX_FORMAT (code);
326 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
327 if (fmt[i] == 'e')
328 {
329 if (rtx_varies_p (XEXP (x, i), for_alias))
330 return 1;
331 }
332 else if (fmt[i] == 'E')
333 {
334 int j;
335 for (j = 0; j < XVECLEN (x, i); j++)
336 if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
337 return 1;
338 }
339
340 return 0;
341}
342
343/* Compute an approximation for the offset between the register
344 FROM and TO for the current function, as it was at the start
345 of the routine. */
346
347static HOST_WIDE_INT
348get_initial_register_offset (int from, int to)
349{
350 static const struct elim_table_t
351 {
352 const int from;
353 const int to;
354 } table[] = ELIMINABLE_REGS;
355 HOST_WIDE_INT offset1, offset2;
356 unsigned int i, j;
357
358 if (to == from)
359 return 0;
360
361 /* It is not safe to call INITIAL_ELIMINATION_OFFSET
362 before the reload pass. We need to give at least
363 an estimation for the resulting frame size. */
364 if (! reload_completed)
365 {
366 offset1 = crtl->outgoing_args_size + get_frame_size ();
367#if !STACK_GROWS_DOWNWARD
368 offset1 = - offset1;
369#endif
370 if (to == STACK_POINTER_REGNUM)
371 return offset1;
372 else if (from == STACK_POINTER_REGNUM)
373 return - offset1;
374 else
375 return 0;
376 }
377
378 for (i = 0; i < ARRAY_SIZE (table); i++)
379 if (table[i].from == from)
380 {
381 if (table[i].to == to)
382 {
383 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
384 offset1);
385 return offset1;
386 }
387 for (j = 0; j < ARRAY_SIZE (table); j++)
388 {
389 if (table[j].to == to
390 && table[j].from == table[i].to)
391 {
392 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
393 offset1);
394 INITIAL_ELIMINATION_OFFSET (table[j].from, table[j].to,
395 offset2);
396 return offset1 + offset2;
397 }
398 if (table[j].from == to
399 && table[j].to == table[i].to)
400 {
401 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
402 offset1);
403 INITIAL_ELIMINATION_OFFSET (table[j].from, table[j].to,
404 offset2);
405 return offset1 - offset2;
406 }
407 }
408 }
409 else if (table[i].to == from)
410 {
411 if (table[i].from == to)
412 {
413 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
414 offset1);
415 return - offset1;
416 }
417 for (j = 0; j < ARRAY_SIZE (table); j++)
418 {
419 if (table[j].to == to
420 && table[j].from == table[i].from)
421 {
422 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
423 offset1);
424 INITIAL_ELIMINATION_OFFSET (table[j].from, table[j].to,
425 offset2);
426 return - offset1 + offset2;
427 }
428 if (table[j].from == to
429 && table[j].to == table[i].from)
430 {
431 INITIAL_ELIMINATION_OFFSET (table[i].from, table[i].to,
432 offset1);
433 INITIAL_ELIMINATION_OFFSET (table[j].from, table[j].to,
434 offset2);
435 return - offset1 - offset2;
436 }
437 }
438 }
439
440 /* If the requested register combination was not found,
441 try a different more simple combination. */
442 if (from == ARG_POINTER_REGNUM)
443 return get_initial_register_offset (HARD_FRAME_POINTER_REGNUM, to);
444 else if (to == ARG_POINTER_REGNUM)
445 return get_initial_register_offset (from, HARD_FRAME_POINTER_REGNUM);
446 else if (from == HARD_FRAME_POINTER_REGNUM)
447 return get_initial_register_offset (FRAME_POINTER_REGNUM, to);
448 else if (to == HARD_FRAME_POINTER_REGNUM)
449 return get_initial_register_offset (from, FRAME_POINTER_REGNUM);
450 else
451 return 0;
452}
453
454/* Return nonzero if the use of X+OFFSET as an address in a MEM with SIZE
455 bytes can cause a trap. MODE is the mode of the MEM (not that of X) and
456 UNALIGNED_MEMS controls whether nonzero is returned for unaligned memory
457 references on strict alignment machines. */
458
459static int
460rtx_addr_can_trap_p_1 (const_rtx x, HOST_WIDE_INT offset, HOST_WIDE_INT size,
461 machine_mode mode, bool unaligned_mems)
462{
463 enum rtx_code code = GET_CODE (x);
464
465 /* The offset must be a multiple of the mode size if we are considering
466 unaligned memory references on strict alignment machines. */
467 if (STRICT_ALIGNMENT && unaligned_mems && GET_MODE_SIZE (mode) != 0)
468 {
469 HOST_WIDE_INT actual_offset = offset;
470
471#ifdef SPARC_STACK_BOUNDARY_HACK
472 /* ??? The SPARC port may claim a STACK_BOUNDARY higher than
473 the real alignment of %sp. However, when it does this, the
474 alignment of %sp+STACK_POINTER_OFFSET is STACK_BOUNDARY. */
475 if (SPARC_STACK_BOUNDARY_HACK
476 && (x == stack_pointer_rtx || x == hard_frame_pointer_rtx))
477 actual_offset -= STACK_POINTER_OFFSET;
478#endif
479
480 if (actual_offset % GET_MODE_SIZE (mode) != 0)
481 return 1;
482 }
483
484 switch (code)
485 {
486 case SYMBOL_REF:
487 if (SYMBOL_REF_WEAK (x))
488 return 1;
489 if (!CONSTANT_POOL_ADDRESS_P (x) && !SYMBOL_REF_FUNCTION_P (x))
490 {
491 tree decl;
492 HOST_WIDE_INT decl_size;
493
494 if (offset < 0)
495 return 1;
496 if (size == 0)
497 size = GET_MODE_SIZE (mode);
498 if (size == 0)
499 return offset != 0;
500
501 /* If the size of the access or of the symbol is unknown,
502 assume the worst. */
503 decl = SYMBOL_REF_DECL (x);
504
505 /* Else check that the access is in bounds. TODO: restructure
506 expr_size/tree_expr_size/int_expr_size and just use the latter. */
507 if (!decl)
508 decl_size = -1;
509 else if (DECL_P (decl) && DECL_SIZE_UNIT (decl))
510 decl_size = (tree_fits_shwi_p (DECL_SIZE_UNIT (decl))
511 ? tree_to_shwi (DECL_SIZE_UNIT (decl))
512 : -1);
513 else if (TREE_CODE (decl) == STRING_CST)
514 decl_size = TREE_STRING_LENGTH (decl);
515 else if (TYPE_SIZE_UNIT (TREE_TYPE (decl)))
516 decl_size = int_size_in_bytes (TREE_TYPE (decl));
517 else
518 decl_size = -1;
519
520 return (decl_size <= 0 ? offset != 0 : offset + size > decl_size);
521 }
522
523 return 0;
524
525 case LABEL_REF:
526 return 0;
527
528 case REG:
529 /* Stack references are assumed not to trap, but we need to deal with
530 nonsensical offsets. */
531 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
532 || x == stack_pointer_rtx
533 /* The arg pointer varies if it is not a fixed register. */
534 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
535 {
536#ifdef RED_ZONE_SIZE
537 HOST_WIDE_INT red_zone_size = RED_ZONE_SIZE;
538#else
539 HOST_WIDE_INT red_zone_size = 0;
540#endif
541 HOST_WIDE_INT stack_boundary = PREFERRED_STACK_BOUNDARY
542 / BITS_PER_UNIT;
543 HOST_WIDE_INT low_bound, high_bound;
544
545 if (size == 0)
546 size = GET_MODE_SIZE (mode);
547 if (size == 0)
548 return 1;
549
550 if (x == frame_pointer_rtx)
551 {
552 if (FRAME_GROWS_DOWNWARD)
553 {
554 high_bound = targetm.starting_frame_offset ();
555 low_bound = high_bound - get_frame_size ();
556 }
557 else
558 {
559 low_bound = targetm.starting_frame_offset ();
560 high_bound = low_bound + get_frame_size ();
561 }
562 }
563 else if (x == hard_frame_pointer_rtx)
564 {
565 HOST_WIDE_INT sp_offset
566 = get_initial_register_offset (STACK_POINTER_REGNUM,
567 HARD_FRAME_POINTER_REGNUM);
568 HOST_WIDE_INT ap_offset
569 = get_initial_register_offset (ARG_POINTER_REGNUM,
570 HARD_FRAME_POINTER_REGNUM);
571
572#if STACK_GROWS_DOWNWARD
573 low_bound = sp_offset - red_zone_size - stack_boundary;
574 high_bound = ap_offset
575 + FIRST_PARM_OFFSET (current_function_decl)
576#if !ARGS_GROW_DOWNWARD
577 + crtl->args.size
578#endif
579 + stack_boundary;
580#else
581 high_bound = sp_offset + red_zone_size + stack_boundary;
582 low_bound = ap_offset
583 + FIRST_PARM_OFFSET (current_function_decl)
584#if ARGS_GROW_DOWNWARD
585 - crtl->args.size
586#endif
587 - stack_boundary;
588#endif
589 }
590 else if (x == stack_pointer_rtx)
591 {
592 HOST_WIDE_INT ap_offset
593 = get_initial_register_offset (ARG_POINTER_REGNUM,
594 STACK_POINTER_REGNUM);
595
596#if STACK_GROWS_DOWNWARD
597 low_bound = - red_zone_size - stack_boundary;
598 high_bound = ap_offset
599 + FIRST_PARM_OFFSET (current_function_decl)
600#if !ARGS_GROW_DOWNWARD
601 + crtl->args.size
602#endif
603 + stack_boundary;
604#else
605 high_bound = red_zone_size + stack_boundary;
606 low_bound = ap_offset
607 + FIRST_PARM_OFFSET (current_function_decl)
608#if ARGS_GROW_DOWNWARD
609 - crtl->args.size
610#endif
611 - stack_boundary;
612#endif
613 }
614 else
615 {
616 /* We assume that accesses are safe to at least the
617 next stack boundary.
618 Examples are varargs and __builtin_return_address. */
619#if ARGS_GROW_DOWNWARD
620 high_bound = FIRST_PARM_OFFSET (current_function_decl)
621 + stack_boundary;
622 low_bound = FIRST_PARM_OFFSET (current_function_decl)
623 - crtl->args.size - stack_boundary;
624#else
625 low_bound = FIRST_PARM_OFFSET (current_function_decl)
626 - stack_boundary;
627 high_bound = FIRST_PARM_OFFSET (current_function_decl)
628 + crtl->args.size + stack_boundary;
629#endif
630 }
631
632 if (offset >= low_bound && offset <= high_bound - size)
633 return 0;
634 return 1;
635 }
636 /* All of the virtual frame registers are stack references. */
637 if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
638 && REGNO (x) <= LAST_VIRTUAL_REGISTER)
639 return 0;
640 return 1;
641
642 case CONST:
643 return rtx_addr_can_trap_p_1 (XEXP (x, 0), offset, size,
644 mode, unaligned_mems);
645
646 case PLUS:
647 /* An address is assumed not to trap if:
648 - it is the pic register plus a const unspec without offset. */
649 if (XEXP (x, 0) == pic_offset_table_rtx
650 && GET_CODE (XEXP (x, 1)) == CONST
651 && GET_CODE (XEXP (XEXP (x, 1), 0)) == UNSPEC
652 && offset == 0)
653 return 0;
654
655 /* - or it is an address that can't trap plus a constant integer. */
656 if (CONST_INT_P (XEXP (x, 1))
657 && !rtx_addr_can_trap_p_1 (XEXP (x, 0), offset + INTVAL (XEXP (x, 1)),
658 size, mode, unaligned_mems))
659 return 0;
660
661 return 1;
662
663 case LO_SUM:
664 case PRE_MODIFY:
665 return rtx_addr_can_trap_p_1 (XEXP (x, 1), offset, size,
666 mode, unaligned_mems);
667
668 case PRE_DEC:
669 case PRE_INC:
670 case POST_DEC:
671 case POST_INC:
672 case POST_MODIFY:
673 return rtx_addr_can_trap_p_1 (XEXP (x, 0), offset, size,
674 mode, unaligned_mems);
675
676 default:
677 break;
678 }
679
680 /* If it isn't one of the case above, it can cause a trap. */
681 return 1;
682}
683
684/* Return nonzero if the use of X as an address in a MEM can cause a trap. */
685
686int
687rtx_addr_can_trap_p (const_rtx x)
688{
689 return rtx_addr_can_trap_p_1 (x, 0, 0, VOIDmode, false);
690}
691
692/* Return true if X contains a MEM subrtx. */
693
694bool
695contains_mem_rtx_p (rtx x)
696{
697 subrtx_iterator::array_type array;
698 FOR_EACH_SUBRTX (iter, array, x, ALL)
699 if (MEM_P (*iter))
700 return true;
701
702 return false;
703}
704
705/* Return true if X is an address that is known to not be zero. */
706
707bool
708nonzero_address_p (const_rtx x)
709{
710 const enum rtx_code code = GET_CODE (x);
711
712 switch (code)
713 {
714 case SYMBOL_REF:
715 return flag_delete_null_pointer_checks && !SYMBOL_REF_WEAK (x);
716
717 case LABEL_REF:
718 return true;
719
720 case REG:
721 /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */
722 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
723 || x == stack_pointer_rtx
724 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
725 return true;
726 /* All of the virtual frame registers are stack references. */
727 if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
728 && REGNO (x) <= LAST_VIRTUAL_REGISTER)
729 return true;
730 return false;
731
732 case CONST:
733 return nonzero_address_p (XEXP (x, 0));
734
735 case PLUS:
736 /* Handle PIC references. */
737 if (XEXP (x, 0) == pic_offset_table_rtx
738 && CONSTANT_P (XEXP (x, 1)))
739 return true;
740 return false;
741
742 case PRE_MODIFY:
743 /* Similar to the above; allow positive offsets. Further, since
744 auto-inc is only allowed in memories, the register must be a
745 pointer. */
746 if (CONST_INT_P (XEXP (x, 1))
747 && INTVAL (XEXP (x, 1)) > 0)
748 return true;
749 return nonzero_address_p (XEXP (x, 0));
750
751 case PRE_INC:
752 /* Similarly. Further, the offset is always positive. */
753 return true;
754
755 case PRE_DEC:
756 case POST_DEC:
757 case POST_INC:
758 case POST_MODIFY:
759 return nonzero_address_p (XEXP (x, 0));
760
761 case LO_SUM:
762 return nonzero_address_p (XEXP (x, 1));
763
764 default:
765 break;
766 }
767
768 /* If it isn't one of the case above, might be zero. */
769 return false;
770}
771
772/* Return 1 if X refers to a memory location whose address
773 cannot be compared reliably with constant addresses,
774 or if X refers to a BLKmode memory object.
775 FOR_ALIAS is nonzero if we are called from alias analysis; if it is
776 zero, we are slightly more conservative. */
777
778bool
779rtx_addr_varies_p (const_rtx x, bool for_alias)
780{
781 enum rtx_code code;
782 int i;
783 const char *fmt;
784
785 if (x == 0)
786 return 0;
787
788 code = GET_CODE (x);
789 if (code == MEM)
790 return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
791
792 fmt = GET_RTX_FORMAT (code);
793 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
794 if (fmt[i] == 'e')
795 {
796 if (rtx_addr_varies_p (XEXP (x, i), for_alias))
797 return 1;
798 }
799 else if (fmt[i] == 'E')
800 {
801 int j;
802 for (j = 0; j < XVECLEN (x, i); j++)
803 if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
804 return 1;
805 }
806 return 0;
807}
808
809/* Return the CALL in X if there is one. */
810
811rtx
812get_call_rtx_from (rtx x)
813{
814 if (INSN_P (x))
815 x = PATTERN (x);
816 if (GET_CODE (x) == PARALLEL)
817 x = XVECEXP (x, 0, 0);
818 if (GET_CODE (x) == SET)
819 x = SET_SRC (x);
820 if (GET_CODE (x) == CALL && MEM_P (XEXP (x, 0)))
821 return x;
822 return NULL_RTX;
823}
824
825/* Return the value of the integer term in X, if one is apparent;
826 otherwise return 0.
827 Only obvious integer terms are detected.
828 This is used in cse.c with the `related_value' field. */
829
830HOST_WIDE_INT
831get_integer_term (const_rtx x)
832{
833 if (GET_CODE (x) == CONST)
834 x = XEXP (x, 0);
835
836 if (GET_CODE (x) == MINUS
837 && CONST_INT_P (XEXP (x, 1)))
838 return - INTVAL (XEXP (x, 1));
839 if (GET_CODE (x) == PLUS
840 && CONST_INT_P (XEXP (x, 1)))
841 return INTVAL (XEXP (x, 1));
842 return 0;
843}
844
845/* If X is a constant, return the value sans apparent integer term;
846 otherwise return 0.
847 Only obvious integer terms are detected. */
848
849rtx
850get_related_value (const_rtx x)
851{
852 if (GET_CODE (x) != CONST)
853 return 0;
854 x = XEXP (x, 0);
855 if (GET_CODE (x) == PLUS
856 && CONST_INT_P (XEXP (x, 1)))
857 return XEXP (x, 0);
858 else if (GET_CODE (x) == MINUS
859 && CONST_INT_P (XEXP (x, 1)))
860 return XEXP (x, 0);
861 return 0;
862}
863
864/* Return true if SYMBOL is a SYMBOL_REF and OFFSET + SYMBOL points
865 to somewhere in the same object or object_block as SYMBOL. */
866
867bool
868offset_within_block_p (const_rtx symbol, HOST_WIDE_INT offset)
869{
870 tree decl;
871
872 if (GET_CODE (symbol) != SYMBOL_REF)
873 return false;
874
875 if (offset == 0)
876 return true;
877
878 if (offset > 0)
879 {
880 if (CONSTANT_POOL_ADDRESS_P (symbol)
881 && offset < (int) GET_MODE_SIZE (get_pool_mode (symbol)))
882 return true;
883
884 decl = SYMBOL_REF_DECL (symbol);
885 if (decl && offset < int_size_in_bytes (TREE_TYPE (decl)))
886 return true;
887 }
888
889 if (SYMBOL_REF_HAS_BLOCK_INFO_P (symbol)
890 && SYMBOL_REF_BLOCK (symbol)
891 && SYMBOL_REF_BLOCK_OFFSET (symbol) >= 0
892 && ((unsigned HOST_WIDE_INT) offset + SYMBOL_REF_BLOCK_OFFSET (symbol)
893 < (unsigned HOST_WIDE_INT) SYMBOL_REF_BLOCK (symbol)->size))
894 return true;
895
896 return false;
897}
898
899/* Split X into a base and a constant offset, storing them in *BASE_OUT
900 and *OFFSET_OUT respectively. */
901
902void
903split_const (rtx x, rtx *base_out, rtx *offset_out)
904{
905 if (GET_CODE (x) == CONST)
906 {
907 x = XEXP (x, 0);
908 if (GET_CODE (x) == PLUS && CONST_INT_P (XEXP (x, 1)))
909 {
910 *base_out = XEXP (x, 0);
911 *offset_out = XEXP (x, 1);
912 return;
913 }
914 }
915 *base_out = x;
916 *offset_out = const0_rtx;
917}
918
919/* Return the number of places FIND appears within X. If COUNT_DEST is
920 zero, we do not count occurrences inside the destination of a SET. */
921
922int
923count_occurrences (const_rtx x, const_rtx find, int count_dest)
924{
925 int i, j;
926 enum rtx_code code;
927 const char *format_ptr;
928 int count;
929
930 if (x == find)
931 return 1;
932
933 code = GET_CODE (x);
934
935 switch (code)
936 {
937 case REG:
938 CASE_CONST_ANY:
939 case SYMBOL_REF:
940 case CODE_LABEL:
941 case PC:
942 case CC0:
943 return 0;
944
945 case EXPR_LIST:
946 count = count_occurrences (XEXP (x, 0), find, count_dest);
947 if (XEXP (x, 1))
948 count += count_occurrences (XEXP (x, 1), find, count_dest);
949 return count;
950
951 case MEM:
952 if (MEM_P (find) && rtx_equal_p (x, find))
953 return 1;
954 break;
955
956 case SET:
957 if (SET_DEST (x) == find && ! count_dest)
958 return count_occurrences (SET_SRC (x), find, count_dest);
959 break;
960
961 default:
962 break;
963 }
964
965 format_ptr = GET_RTX_FORMAT (code);
966 count = 0;
967
968 for (i = 0; i < GET_RTX_LENGTH (code); i++)
969 {
970 switch (*format_ptr++)
971 {
972 case 'e':
973 count += count_occurrences (XEXP (x, i), find, count_dest);
974 break;
975
976 case 'E':
977 for (j = 0; j < XVECLEN (x, i); j++)
978 count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
979 break;
980 }
981 }
982 return count;
983}
984
985
986/* Return TRUE if OP is a register or subreg of a register that
987 holds an unsigned quantity. Otherwise, return FALSE. */
988
989bool
990unsigned_reg_p (rtx op)
991{
992 if (REG_P (op)
993 && REG_EXPR (op)
994 && TYPE_UNSIGNED (TREE_TYPE (REG_EXPR (op))))
995 return true;
996
997 if (GET_CODE (op) == SUBREG
998 && SUBREG_PROMOTED_SIGN (op))
999 return true;
1000
1001 return false;
1002}
1003
1004
1005/* Nonzero if register REG appears somewhere within IN.
1006 Also works if REG is not a register; in this case it checks
1007 for a subexpression of IN that is Lisp "equal" to REG. */
1008
1009int
1010reg_mentioned_p (const_rtx reg, const_rtx in)
1011{
1012 const char *fmt;
1013 int i;
1014 enum rtx_code code;
1015
1016 if (in == 0)
1017 return 0;
1018
1019 if (reg == in)
1020 return 1;
1021
1022 if (GET_CODE (in) == LABEL_REF)
1023 return reg == label_ref_label (in);
1024
1025 code = GET_CODE (in);
1026
1027 switch (code)
1028 {
1029 /* Compare registers by number. */
1030 case REG:
1031 return REG_P (reg) && REGNO (in) == REGNO (reg);
1032
1033 /* These codes have no constituent expressions
1034 and are unique. */
1035 case SCRATCH:
1036 case CC0:
1037 case PC:
1038 return 0;
1039
1040 CASE_CONST_ANY:
1041 /* These are kept unique for a given value. */
1042 return 0;
1043
1044 default:
1045 break;
1046 }
1047
1048 if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
1049 return 1;
1050
1051 fmt = GET_RTX_FORMAT (code);
1052
1053 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1054 {
1055 if (fmt[i] == 'E')
1056 {
1057 int j;
1058 for (j = XVECLEN (in, i) - 1; j >= 0; j--)
1059 if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
1060 return 1;
1061 }
1062 else if (fmt[i] == 'e'
1063 && reg_mentioned_p (reg, XEXP (in, i)))
1064 return 1;
1065 }
1066 return 0;
1067}
1068
1069/* Return 1 if in between BEG and END, exclusive of BEG and END, there is
1070 no CODE_LABEL insn. */
1071
1072int
1073no_labels_between_p (const rtx_insn *beg, const rtx_insn *end)
1074{
1075 rtx_insn *p;
1076 if (beg == end)
1077 return 0;
1078 for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
1079 if (LABEL_P (p))
1080 return 0;
1081 return 1;
1082}
1083
1084/* Nonzero if register REG is used in an insn between
1085 FROM_INSN and TO_INSN (exclusive of those two). */
1086
1087int
1088reg_used_between_p (const_rtx reg, const rtx_insn *from_insn,
1089 const rtx_insn *to_insn)
1090{
1091 rtx_insn *insn;
1092
1093 if (from_insn == to_insn)
1094 return 0;
1095
1096 for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
1097 if (NONDEBUG_INSN_P (insn)
1098 && (reg_overlap_mentioned_p (reg, PATTERN (insn))
1099 || (CALL_P (insn) && find_reg_fusage (insn, USE, reg))))
1100 return 1;
1101 return 0;
1102}
1103
1104/* Nonzero if the old value of X, a register, is referenced in BODY. If X
1105 is entirely replaced by a new value and the only use is as a SET_DEST,
1106 we do not consider it a reference. */
1107
1108int
1109reg_referenced_p (const_rtx x, const_rtx body)
1110{
1111 int i;
1112
1113 switch (GET_CODE (body))
1114 {
1115 case SET:
1116 if (reg_overlap_mentioned_p (x, SET_SRC (body)))
1117 return 1;
1118
1119 /* If the destination is anything other than CC0, PC, a REG or a SUBREG
1120 of a REG that occupies all of the REG, the insn references X if
1121 it is mentioned in the destination. */
1122 if (GET_CODE (SET_DEST (body)) != CC0
1123 && GET_CODE (SET_DEST (body)) != PC
1124 && !REG_P (SET_DEST (body))
1125 && ! (GET_CODE (SET_DEST (body)) == SUBREG
1126 && REG_P (SUBREG_REG (SET_DEST (body)))
1127 && !read_modify_subreg_p (SET_DEST (body)))
1128 && reg_overlap_mentioned_p (x, SET_DEST (body)))
1129 return 1;
1130 return 0;
1131
1132 case ASM_OPERANDS:
1133 for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1134 if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
1135 return 1;
1136 return 0;
1137
1138 case CALL:
1139 case USE:
1140 case IF_THEN_ELSE:
1141 return reg_overlap_mentioned_p (x, body);
1142
1143 case TRAP_IF:
1144 return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
1145
1146 case PREFETCH:
1147 return reg_overlap_mentioned_p (x, XEXP (body, 0));
1148
1149 case UNSPEC:
1150 case UNSPEC_VOLATILE:
1151 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1152 if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
1153 return 1;
1154 return 0;
1155
1156 case PARALLEL:
1157 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1158 if (reg_referenced_p (x, XVECEXP (body, 0, i)))
1159 return 1;
1160 return 0;
1161
1162 case CLOBBER:
1163 if (MEM_P (XEXP (body, 0)))
1164 if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
1165 return 1;
1166 return 0;
1167
1168 case COND_EXEC:
1169 if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
1170 return 1;
1171 return reg_referenced_p (x, COND_EXEC_CODE (body));
1172
1173 default:
1174 return 0;
1175 }
1176}
1177
1178/* Nonzero if register REG is set or clobbered in an insn between
1179 FROM_INSN and TO_INSN (exclusive of those two). */
1180
1181int
1182reg_set_between_p (const_rtx reg, const rtx_insn *from_insn,
1183 const rtx_insn *to_insn)
1184{
1185 const rtx_insn *insn;
1186
1187 if (from_insn == to_insn)
1188 return 0;
1189
1190 for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
1191 if (INSN_P (insn) && reg_set_p (reg, insn))
1192 return 1;
1193 return 0;
1194}
1195
1196/* Return true if REG is set or clobbered inside INSN. */
1197
1198int
1199reg_set_p (const_rtx reg, const_rtx insn)
1200{
1201 /* After delay slot handling, call and branch insns might be in a
1202 sequence. Check all the elements there. */
1203 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
1204 {
1205 for (int i = 0; i < XVECLEN (PATTERN (insn), 0); ++i)
1206 if (reg_set_p (reg, XVECEXP (PATTERN (insn), 0, i)))
1207 return true;
1208
1209 return false;
1210 }
1211
1212 /* We can be passed an insn or part of one. If we are passed an insn,
1213 check if a side-effect of the insn clobbers REG. */
1214 if (INSN_P (insn)
1215 && (FIND_REG_INC_NOTE (insn, reg)
1216 || (CALL_P (insn)
1217 && ((REG_P (reg)
1218 && REGNO (reg) < FIRST_PSEUDO_REGISTER
1219 && overlaps_hard_reg_set_p (regs_invalidated_by_call,
1220 GET_MODE (reg), REGNO (reg)))
1221 || MEM_P (reg)
1222 || find_reg_fusage (insn, CLOBBER, reg)))))
1223 return true;
1224
1225 /* There are no REG_INC notes for SP autoinc. */
1226 if (reg == stack_pointer_rtx && INSN_P (insn))
1227 {
1228 subrtx_var_iterator::array_type array;
1229 FOR_EACH_SUBRTX_VAR (iter, array, PATTERN (insn), NONCONST)
1230 {
1231 rtx mem = *iter;
1232 if (mem
1233 && MEM_P (mem)
1234 && GET_RTX_CLASS (GET_CODE (XEXP (mem, 0))) == RTX_AUTOINC)
1235 {
1236 if (XEXP (XEXP (mem, 0), 0) == stack_pointer_rtx)
1237 return true;
1238 iter.skip_subrtxes ();
1239 }
1240 }
1241 }
1242
1243 return set_of (reg, insn) != NULL_RTX;
1244}
1245
1246/* Similar to reg_set_between_p, but check all registers in X. Return 0
1247 only if none of them are modified between START and END. Return 1 if
1248 X contains a MEM; this routine does use memory aliasing. */
1249
1250int
1251modified_between_p (const_rtx x, const rtx_insn *start, const rtx_insn *end)
1252{
1253 const enum rtx_code code = GET_CODE (x);
1254 const char *fmt;
1255 int i, j;
1256 rtx_insn *insn;
1257
1258 if (start == end)
1259 return 0;
1260
1261 switch (code)
1262 {
1263 CASE_CONST_ANY:
1264 case CONST:
1265 case SYMBOL_REF:
1266 case LABEL_REF:
1267 return 0;
1268
1269 case PC:
1270 case CC0:
1271 return 1;
1272
1273 case MEM:
1274 if (modified_between_p (XEXP (x, 0), start, end))
1275 return 1;
1276 if (MEM_READONLY_P (x))
1277 return 0;
1278 for (insn = NEXT_INSN (start); insn != end; insn = NEXT_INSN (insn))
1279 if (memory_modified_in_insn_p (x, insn))
1280 return 1;
1281 return 0;
1282
1283 case REG:
1284 return reg_set_between_p (x, start, end);
1285
1286 default:
1287 break;
1288 }
1289
1290 fmt = GET_RTX_FORMAT (code);
1291 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1292 {
1293 if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
1294 return 1;
1295
1296 else if (fmt[i] == 'E')
1297 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1298 if (modified_between_p (XVECEXP (x, i, j), start, end))
1299 return 1;
1300 }
1301
1302 return 0;
1303}
1304
1305/* Similar to reg_set_p, but check all registers in X. Return 0 only if none
1306 of them are modified in INSN. Return 1 if X contains a MEM; this routine
1307 does use memory aliasing. */
1308
1309int
1310modified_in_p (const_rtx x, const_rtx insn)
1311{
1312 const enum rtx_code code = GET_CODE (x);
1313 const char *fmt;
1314 int i, j;
1315
1316 switch (code)
1317 {
1318 CASE_CONST_ANY:
1319 case CONST:
1320 case SYMBOL_REF:
1321 case LABEL_REF:
1322 return 0;
1323
1324 case PC:
1325 case CC0:
1326 return 1;
1327
1328 case MEM:
1329 if (modified_in_p (XEXP (x, 0), insn))
1330 return 1;
1331 if (MEM_READONLY_P (x))
1332 return 0;
1333 if (memory_modified_in_insn_p (x, insn))
1334 return 1;
1335 return 0;
1336
1337 case REG:
1338 return reg_set_p (x, insn);
1339
1340 default:
1341 break;
1342 }
1343
1344 fmt = GET_RTX_FORMAT (code);
1345 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1346 {
1347 if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
1348 return 1;
1349
1350 else if (fmt[i] == 'E')
1351 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1352 if (modified_in_p (XVECEXP (x, i, j), insn))
1353 return 1;
1354 }
1355
1356 return 0;
1357}
1358
1359/* Return true if X is a SUBREG and if storing a value to X would
1360 preserve some of its SUBREG_REG. For example, on a normal 32-bit
1361 target, using a SUBREG to store to one half of a DImode REG would
1362 preserve the other half. */
1363
1364bool
1365read_modify_subreg_p (const_rtx x)
1366{
1367 unsigned int isize, osize;
1368 if (GET_CODE (x) != SUBREG)
1369 return false;
1370 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
1371 osize = GET_MODE_SIZE (GET_MODE (x));
1372 return isize > osize
1373 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x)));
1374}
1375
1376/* Helper function for set_of. */
1377struct set_of_data
1378 {
1379 const_rtx found;
1380 const_rtx pat;
1381 };
1382
1383static void
1384set_of_1 (rtx x, const_rtx pat, void *data1)
1385{
1386 struct set_of_data *const data = (struct set_of_data *) (data1);
1387 if (rtx_equal_p (x, data->pat)
1388 || (!MEM_P (x) && reg_overlap_mentioned_p (data->pat, x)))
1389 data->found = pat;
1390}
1391
1392/* Give an INSN, return a SET or CLOBBER expression that does modify PAT
1393 (either directly or via STRICT_LOW_PART and similar modifiers). */
1394const_rtx
1395set_of (const_rtx pat, const_rtx insn)
1396{
1397 struct set_of_data data;
1398 data.found = NULL_RTX;
1399 data.pat = pat;
1400 note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
1401 return data.found;
1402}
1403
1404/* Add all hard register in X to *PSET. */
1405void
1406find_all_hard_regs (const_rtx x, HARD_REG_SET *pset)
1407{
1408 subrtx_iterator::array_type array;
1409 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
1410 {
1411 const_rtx x = *iter;
1412 if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
1413 add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
1414 }
1415}
1416
1417/* This function, called through note_stores, collects sets and
1418 clobbers of hard registers in a HARD_REG_SET, which is pointed to
1419 by DATA. */
1420void
1421record_hard_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1422{
1423 HARD_REG_SET *pset = (HARD_REG_SET *)data;
1424 if (REG_P (x) && HARD_REGISTER_P (x))
1425 add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
1426}
1427
1428/* Examine INSN, and compute the set of hard registers written by it.
1429 Store it in *PSET. Should only be called after reload. */
1430void
1431find_all_hard_reg_sets (const rtx_insn *insn, HARD_REG_SET *pset, bool implicit)
1432{
1433 rtx link;
1434
1435 CLEAR_HARD_REG_SET (*pset);
1436 note_stores (PATTERN (insn), record_hard_reg_sets, pset);
1437 if (CALL_P (insn))
1438 {
1439 if (implicit)
1440 IOR_HARD_REG_SET (*pset, call_used_reg_set);
1441
1442 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1443 record_hard_reg_sets (XEXP (link, 0), NULL, pset);
1444 }
1445 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1446 if (REG_NOTE_KIND (link) == REG_INC)
1447 record_hard_reg_sets (XEXP (link, 0), NULL, pset);
1448}
1449
1450/* Like record_hard_reg_sets, but called through note_uses. */
1451void
1452record_hard_reg_uses (rtx *px, void *data)
1453{
1454 find_all_hard_regs (*px, (HARD_REG_SET *) data);
1455}
1456
1457/* Given an INSN, return a SET expression if this insn has only a single SET.
1458 It may also have CLOBBERs, USEs, or SET whose output
1459 will not be used, which we ignore. */
1460
1461rtx
1462single_set_2 (const rtx_insn *insn, const_rtx pat)
1463{
1464 rtx set = NULL;
1465 int set_verified = 1;
1466 int i;
1467
1468 if (GET_CODE (pat) == PARALLEL)
1469 {
1470 for (i = 0; i < XVECLEN (pat, 0); i++)
1471 {
1472 rtx sub = XVECEXP (pat, 0, i);
1473 switch (GET_CODE (sub))
1474 {
1475 case USE:
1476 case CLOBBER:
1477 break;
1478
1479 case SET:
1480 /* We can consider insns having multiple sets, where all
1481 but one are dead as single set insns. In common case
1482 only single set is present in the pattern so we want
1483 to avoid checking for REG_UNUSED notes unless necessary.
1484
1485 When we reach set first time, we just expect this is
1486 the single set we are looking for and only when more
1487 sets are found in the insn, we check them. */
1488 if (!set_verified)
1489 {
1490 if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
1491 && !side_effects_p (set))
1492 set = NULL;
1493 else
1494 set_verified = 1;
1495 }
1496 if (!set)
1497 set = sub, set_verified = 0;
1498 else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
1499 || side_effects_p (sub))
1500 return NULL_RTX;
1501 break;
1502
1503 default:
1504 return NULL_RTX;
1505 }
1506 }
1507 }
1508 return set;
1509}
1510
1511/* Given an INSN, return nonzero if it has more than one SET, else return
1512 zero. */
1513
1514int
1515multiple_sets (const_rtx insn)
1516{
1517 int found;
1518 int i;
1519
1520 /* INSN must be an insn. */
1521 if (! INSN_P (insn))
1522 return 0;
1523
1524 /* Only a PARALLEL can have multiple SETs. */
1525 if (GET_CODE (PATTERN (insn)) == PARALLEL)
1526 {
1527 for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1528 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
1529 {
1530 /* If we have already found a SET, then return now. */
1531 if (found)
1532 return 1;
1533 else
1534 found = 1;
1535 }
1536 }
1537
1538 /* Either zero or one SET. */
1539 return 0;
1540}
1541
1542/* Return nonzero if the destination of SET equals the source
1543 and there are no side effects. */
1544
1545int
1546set_noop_p (const_rtx set)
1547{
1548 rtx src = SET_SRC (set);
1549 rtx dst = SET_DEST (set);
1550
1551 if (dst == pc_rtx && src == pc_rtx)
1552 return 1;
1553
1554 if (MEM_P (dst) && MEM_P (src))
1555 return rtx_equal_p (dst, src) && !side_effects_p (dst);
1556
1557 if (GET_CODE (dst) == ZERO_EXTRACT)
1558 return rtx_equal_p (XEXP (dst, 0), src)
1559 && !BITS_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx
1560 && !side_effects_p (src);
1561
1562 if (GET_CODE (dst) == STRICT_LOW_PART)
1563 dst = XEXP (dst, 0);
1564
1565 if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1566 {
1567 if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1568 return 0;
1569 src = SUBREG_REG (src);
1570 dst = SUBREG_REG (dst);
1571 }
1572
1573 /* It is a NOOP if destination overlaps with selected src vector
1574 elements. */
1575 if (GET_CODE (src) == VEC_SELECT
1576 && REG_P (XEXP (src, 0)) && REG_P (dst)
1577 && HARD_REGISTER_P (XEXP (src, 0))
1578 && HARD_REGISTER_P (dst))
1579 {
1580 int i;
1581 rtx par = XEXP (src, 1);
1582 rtx src0 = XEXP (src, 0);
1583 int c0 = INTVAL (XVECEXP (par, 0, 0));
1584 HOST_WIDE_INT offset = GET_MODE_UNIT_SIZE (GET_MODE (src0)) * c0;
1585
1586 for (i = 1; i < XVECLEN (par, 0); i++)
1587 if (INTVAL (XVECEXP (par, 0, i)) != c0 + i)
1588 return 0;
1589 return
1590 simplify_subreg_regno (REGNO (src0), GET_MODE (src0),
1591 offset, GET_MODE (dst)) == (int) REGNO (dst);
1592 }
1593
1594 return (REG_P (src) && REG_P (dst)
1595 && REGNO (src) == REGNO (dst));
1596}
1597
1598/* Return nonzero if an insn consists only of SETs, each of which only sets a
1599 value to itself. */
1600
1601int
1602noop_move_p (const rtx_insn *insn)
1603{
1604 rtx pat = PATTERN (insn);
1605
1606 if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
1607 return 1;
1608
1609 /* Insns carrying these notes are useful later on. */
1610 if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
1611 return 0;
1612
1613 /* Check the code to be executed for COND_EXEC. */
1614 if (GET_CODE (pat) == COND_EXEC)
1615 pat = COND_EXEC_CODE (pat);
1616
1617 if (GET_CODE (pat) == SET && set_noop_p (pat))
1618 return 1;
1619
1620 if (GET_CODE (pat) == PARALLEL)
1621 {
1622 int i;
1623 /* If nothing but SETs of registers to themselves,
1624 this insn can also be deleted. */
1625 for (i = 0; i < XVECLEN (pat, 0); i++)
1626 {
1627 rtx tem = XVECEXP (pat, 0, i);
1628
1629 if (GET_CODE (tem) == USE
1630 || GET_CODE (tem) == CLOBBER)
1631 continue;
1632
1633 if (GET_CODE (tem) != SET || ! set_noop_p (tem))
1634 return 0;
1635 }
1636
1637 return 1;
1638 }
1639 return 0;
1640}
1641
1642
1643/* Return nonzero if register in range [REGNO, ENDREGNO)
1644 appears either explicitly or implicitly in X
1645 other than being stored into.
1646
1647 References contained within the substructure at LOC do not count.
1648 LOC may be zero, meaning don't ignore anything. */
1649
1650bool
1651refers_to_regno_p (unsigned int regno, unsigned int endregno, const_rtx x,
1652 rtx *loc)
1653{
1654 int i;
1655 unsigned int x_regno;
1656 RTX_CODE code;
1657 const char *fmt;
1658
1659 repeat:
1660 /* The contents of a REG_NONNEG note is always zero, so we must come here
1661 upon repeat in case the last REG_NOTE is a REG_NONNEG note. */
1662 if (x == 0)
1663 return false;
1664
1665 code = GET_CODE (x);
1666
1667 switch (code)
1668 {
1669 case REG:
1670 x_regno = REGNO (x);
1671
1672 /* If we modifying the stack, frame, or argument pointer, it will
1673 clobber a virtual register. In fact, we could be more precise,
1674 but it isn't worth it. */
1675 if ((x_regno == STACK_POINTER_REGNUM
1676 || (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1677 && x_regno == ARG_POINTER_REGNUM)
1678 || x_regno == FRAME_POINTER_REGNUM)
1679 && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1680 return true;
1681
1682 return endregno > x_regno && regno < END_REGNO (x);
1683
1684 case SUBREG:
1685 /* If this is a SUBREG of a hard reg, we can see exactly which
1686 registers are being modified. Otherwise, handle normally. */
1687 if (REG_P (SUBREG_REG (x))
1688 && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1689 {
1690 unsigned int inner_regno = subreg_regno (x);
1691 unsigned int inner_endregno
1692 = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1693 ? subreg_nregs (x) : 1);
1694
1695 return endregno > inner_regno && regno < inner_endregno;
1696 }
1697 break;
1698
1699 case CLOBBER:
1700 case SET:
1701 if (&SET_DEST (x) != loc
1702 /* Note setting a SUBREG counts as referring to the REG it is in for
1703 a pseudo but not for hard registers since we can
1704 treat each word individually. */
1705 && ((GET_CODE (SET_DEST (x)) == SUBREG
1706 && loc != &SUBREG_REG (SET_DEST (x))
1707 && REG_P (SUBREG_REG (SET_DEST (x)))
1708 && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1709 && refers_to_regno_p (regno, endregno,
1710 SUBREG_REG (SET_DEST (x)), loc))
1711 || (!REG_P (SET_DEST (x))
1712 && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1713 return true;
1714
1715 if (code == CLOBBER || loc == &SET_SRC (x))
1716 return false;
1717 x = SET_SRC (x);
1718 goto repeat;
1719
1720 default:
1721 break;
1722 }
1723
1724 /* X does not match, so try its subexpressions. */
1725
1726 fmt = GET_RTX_FORMAT (code);
1727 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1728 {
1729 if (fmt[i] == 'e' && loc != &XEXP (x, i))
1730 {
1731 if (i == 0)
1732 {
1733 x = XEXP (x, 0);
1734 goto repeat;
1735 }
1736 else
1737 if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1738 return true;
1739 }
1740 else if (fmt[i] == 'E')
1741 {
1742 int j;
1743 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1744 if (loc != &XVECEXP (x, i, j)
1745 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1746 return true;
1747 }
1748 }
1749 return false;
1750}
1751
1752/* Nonzero if modifying X will affect IN. If X is a register or a SUBREG,
1753 we check if any register number in X conflicts with the relevant register
1754 numbers. If X is a constant, return 0. If X is a MEM, return 1 iff IN
1755 contains a MEM (we don't bother checking for memory addresses that can't
1756 conflict because we expect this to be a rare case. */
1757
1758int
1759reg_overlap_mentioned_p (const_rtx x, const_rtx in)
1760{
1761 unsigned int regno, endregno;
1762
1763 /* If either argument is a constant, then modifying X can not
1764 affect IN. Here we look at IN, we can profitably combine
1765 CONSTANT_P (x) with the switch statement below. */
1766 if (CONSTANT_P (in))
1767 return 0;
1768
1769 recurse:
1770 switch (GET_CODE (x))
1771 {
1772 case STRICT_LOW_PART:
1773 case ZERO_EXTRACT:
1774 case SIGN_EXTRACT:
1775 /* Overly conservative. */
1776 x = XEXP (x, 0);
1777 goto recurse;
1778
1779 case SUBREG:
1780 regno = REGNO (SUBREG_REG (x));
1781 if (regno < FIRST_PSEUDO_REGISTER)
1782 regno = subreg_regno (x);
1783 endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1784 ? subreg_nregs (x) : 1);
1785 goto do_reg;
1786
1787 case REG:
1788 regno = REGNO (x);
1789 endregno = END_REGNO (x);
1790 do_reg:
1791 return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
1792
1793 case MEM:
1794 {
1795 const char *fmt;
1796 int i;
1797
1798 if (MEM_P (in))
1799 return 1;
1800
1801 fmt = GET_RTX_FORMAT (GET_CODE (in));
1802 for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1803 if (fmt[i] == 'e')
1804 {
1805 if (reg_overlap_mentioned_p (x, XEXP (in, i)))
1806 return 1;
1807 }
1808 else if (fmt[i] == 'E')
1809 {
1810 int j;
1811 for (j = XVECLEN (in, i) - 1; j >= 0; --j)
1812 if (reg_overlap_mentioned_p (x, XVECEXP (in, i, j)))
1813 return 1;
1814 }
1815
1816 return 0;
1817 }
1818
1819 case SCRATCH:
1820 case PC:
1821 case CC0:
1822 return reg_mentioned_p (x, in);
1823
1824 case PARALLEL:
1825 {
1826 int i;
1827
1828 /* If any register in here refers to it we return true. */
1829 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1830 if (XEXP (XVECEXP (x, 0, i), 0) != 0
1831 && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1832 return 1;
1833 return 0;
1834 }
1835
1836 default:
1837 gcc_assert (CONSTANT_P (x));
1838 return 0;
1839 }
1840}
1841
1842/* Call FUN on each register or MEM that is stored into or clobbered by X.
1843 (X would be the pattern of an insn). DATA is an arbitrary pointer,
1844 ignored by note_stores, but passed to FUN.
1845
1846 FUN receives three arguments:
1847 1. the REG, MEM, CC0 or PC being stored in or clobbered,
1848 2. the SET or CLOBBER rtx that does the store,
1849 3. the pointer DATA provided to note_stores.
1850
1851 If the item being stored in or clobbered is a SUBREG of a hard register,
1852 the SUBREG will be passed. */
1853
1854void
1855note_stores (const_rtx x, void (*fun) (rtx, const_rtx, void *), void *data)
1856{
1857 int i;
1858
1859 if (GET_CODE (x) == COND_EXEC)
1860 x = COND_EXEC_CODE (x);
1861
1862 if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1863 {
1864 rtx dest = SET_DEST (x);
1865
1866 while ((GET_CODE (dest) == SUBREG
1867 && (!REG_P (SUBREG_REG (dest))
1868 || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1869 || GET_CODE (dest) == ZERO_EXTRACT
1870 || GET_CODE (dest) == STRICT_LOW_PART)
1871 dest = XEXP (dest, 0);
1872
1873 /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1874 each of whose first operand is a register. */
1875 if (GET_CODE (dest) == PARALLEL)
1876 {
1877 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1878 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1879 (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
1880 }
1881 else
1882 (*fun) (dest, x, data);
1883 }
1884
1885 else if (GET_CODE (x) == PARALLEL)
1886 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1887 note_stores (XVECEXP (x, 0, i), fun, data);
1888}
1889
1890/* Like notes_stores, but call FUN for each expression that is being
1891 referenced in PBODY, a pointer to the PATTERN of an insn. We only call
1892 FUN for each expression, not any interior subexpressions. FUN receives a
1893 pointer to the expression and the DATA passed to this function.
1894
1895 Note that this is not quite the same test as that done in reg_referenced_p
1896 since that considers something as being referenced if it is being
1897 partially set, while we do not. */
1898
1899void
1900note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data)
1901{
1902 rtx body = *pbody;
1903 int i;
1904
1905 switch (GET_CODE (body))
1906 {
1907 case COND_EXEC:
1908 (*fun) (&COND_EXEC_TEST (body), data);
1909 note_uses (&COND_EXEC_CODE (body), fun, data);
1910 return;
1911
1912 case PARALLEL:
1913 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1914 note_uses (&XVECEXP (body, 0, i), fun, data);
1915 return;
1916
1917 case SEQUENCE:
1918 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1919 note_uses (&PATTERN (XVECEXP (body, 0, i)), fun, data);
1920 return;
1921
1922 case USE:
1923 (*fun) (&XEXP (body, 0), data);
1924 return;
1925
1926 case ASM_OPERANDS:
1927 for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1928 (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1929 return;
1930
1931 case TRAP_IF:
1932 (*fun) (&TRAP_CONDITION (body), data);
1933 return;
1934
1935 case PREFETCH:
1936 (*fun) (&XEXP (body, 0), data);
1937 return;
1938
1939 case UNSPEC:
1940 case UNSPEC_VOLATILE:
1941 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1942 (*fun) (&XVECEXP (body, 0, i), data);
1943 return;
1944
1945 case CLOBBER:
1946 if (MEM_P (XEXP (body, 0)))
1947 (*fun) (&XEXP (XEXP (body, 0), 0), data);
1948 return;
1949
1950 case SET:
1951 {
1952 rtx dest = SET_DEST (body);
1953
1954 /* For sets we replace everything in source plus registers in memory
1955 expression in store and operands of a ZERO_EXTRACT. */
1956 (*fun) (&SET_SRC (body), data);
1957
1958 if (GET_CODE (dest) == ZERO_EXTRACT)
1959 {
1960 (*fun) (&XEXP (dest, 1), data);
1961 (*fun) (&XEXP (dest, 2), data);
1962 }
1963
1964 while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1965 dest = XEXP (dest, 0);
1966
1967 if (MEM_P (dest))
1968 (*fun) (&XEXP (dest, 0), data);
1969 }
1970 return;
1971
1972 default:
1973 /* All the other possibilities never store. */
1974 (*fun) (pbody, data);
1975 return;
1976 }
1977}
1978
1979/* Return nonzero if X's old contents don't survive after INSN.
1980 This will be true if X is (cc0) or if X is a register and
1981 X dies in INSN or because INSN entirely sets X.
1982
1983 "Entirely set" means set directly and not through a SUBREG, or
1984 ZERO_EXTRACT, so no trace of the old contents remains.
1985 Likewise, REG_INC does not count.
1986
1987 REG may be a hard or pseudo reg. Renumbering is not taken into account,
1988 but for this use that makes no difference, since regs don't overlap
1989 during their lifetimes. Therefore, this function may be used
1990 at any time after deaths have been computed.
1991
1992 If REG is a hard reg that occupies multiple machine registers, this
1993 function will only return 1 if each of those registers will be replaced
1994 by INSN. */
1995
1996int
1997dead_or_set_p (const rtx_insn *insn, const_rtx x)
1998{
1999 unsigned int regno, end_regno;
2000 unsigned int i;
2001
2002 /* Can't use cc0_rtx below since this file is used by genattrtab.c. */
2003 if (GET_CODE (x) == CC0)
2004 return 1;
2005
2006 gcc_assert (REG_P (x));
2007
2008 regno = REGNO (x);
2009 end_regno = END_REGNO (x);
2010 for (i = regno; i < end_regno; i++)
2011 if (! dead_or_set_regno_p (insn, i))
2012 return 0;
2013
2014 return 1;
2015}
2016
2017/* Return TRUE iff DEST is a register or subreg of a register, is a
2018 complete rather than read-modify-write destination, and contains
2019 register TEST_REGNO. */
2020
2021static bool
2022covers_regno_no_parallel_p (const_rtx dest, unsigned int test_regno)
2023{
2024 unsigned int regno, endregno;
2025
2026 if (GET_CODE (dest) == SUBREG && !read_modify_subreg_p (dest))
2027 dest = SUBREG_REG (dest);
2028
2029 if (!REG_P (dest))
2030 return false;
2031
2032 regno = REGNO (dest);
2033 endregno = END_REGNO (dest);
2034 return (test_regno >= regno && test_regno < endregno);
2035}
2036
2037/* Like covers_regno_no_parallel_p, but also handles PARALLELs where
2038 any member matches the covers_regno_no_parallel_p criteria. */
2039
2040static bool
2041covers_regno_p (const_rtx dest, unsigned int test_regno)
2042{
2043 if (GET_CODE (dest) == PARALLEL)
2044 {
2045 /* Some targets place small structures in registers for return
2046 values of functions, and those registers are wrapped in
2047 PARALLELs that we may see as the destination of a SET. */
2048 int i;
2049
2050 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2051 {
2052 rtx inner = XEXP (XVECEXP (dest, 0, i), 0);
2053 if (inner != NULL_RTX
2054 && covers_regno_no_parallel_p (inner, test_regno))
2055 return true;
2056 }
2057
2058 return false;
2059 }
2060 else
2061 return covers_regno_no_parallel_p (dest, test_regno);
2062}
2063
2064/* Utility function for dead_or_set_p to check an individual register. */
2065
2066int
2067dead_or_set_regno_p (const rtx_insn *insn, unsigned int test_regno)
2068{
2069 const_rtx pattern;
2070
2071 /* See if there is a death note for something that includes TEST_REGNO. */
2072 if (find_regno_note (insn, REG_DEAD, test_regno))
2073 return 1;
2074
2075 if (CALL_P (insn)
2076 && find_regno_fusage (insn, CLOBBER, test_regno))
2077 return 1;
2078
2079 pattern = PATTERN (insn);
2080
2081 /* If a COND_EXEC is not executed, the value survives. */
2082 if (GET_CODE (pattern) == COND_EXEC)
2083 return 0;
2084
2085 if (GET_CODE (pattern) == SET)
2086 return covers_regno_p (SET_DEST (pattern), test_regno);
2087 else if (GET_CODE (pattern) == PARALLEL)
2088 {
2089 int i;
2090
2091 for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
2092 {
2093 rtx body = XVECEXP (pattern, 0, i);
2094
2095 if (GET_CODE (body) == COND_EXEC)
2096 body = COND_EXEC_CODE (body);
2097
2098 if ((GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
2099 && covers_regno_p (SET_DEST (body), test_regno))
2100 return 1;
2101 }
2102 }
2103
2104 return 0;
2105}
2106
2107/* Return the reg-note of kind KIND in insn INSN, if there is one.
2108 If DATUM is nonzero, look for one whose datum is DATUM. */
2109
2110rtx
2111find_reg_note (const_rtx insn, enum reg_note kind, const_rtx datum)
2112{
2113 rtx link;
2114
2115 gcc_checking_assert (insn);
2116
2117 /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
2118 if (! INSN_P (insn))
2119 return 0;
2120 if (datum == 0)
2121 {
2122 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2123 if (REG_NOTE_KIND (link) == kind)
2124 return link;
2125 return 0;
2126 }
2127
2128 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2129 if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0))
2130 return link;
2131 return 0;
2132}
2133
2134/* Return the reg-note of kind KIND in insn INSN which applies to register
2135 number REGNO, if any. Return 0 if there is no such reg-note. Note that
2136 the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
2137 it might be the case that the note overlaps REGNO. */
2138
2139rtx
2140find_regno_note (const_rtx insn, enum reg_note kind, unsigned int regno)
2141{
2142 rtx link;
2143
2144 /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
2145 if (! INSN_P (insn))
2146 return 0;
2147
2148 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2149 if (REG_NOTE_KIND (link) == kind
2150 /* Verify that it is a register, so that scratch and MEM won't cause a
2151 problem here. */
2152 && REG_P (XEXP (link, 0))
2153 && REGNO (XEXP (link, 0)) <= regno
2154 && END_REGNO (XEXP (link, 0)) > regno)
2155 return link;
2156 return 0;
2157}
2158
2159/* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
2160 has such a note. */
2161
2162rtx
2163find_reg_equal_equiv_note (const_rtx insn)
2164{
2165 rtx link;
2166
2167 if (!INSN_P (insn))
2168 return 0;
2169
2170 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2171 if (REG_NOTE_KIND (link) == REG_EQUAL
2172 || REG_NOTE_KIND (link) == REG_EQUIV)
2173 {
2174 /* FIXME: We should never have REG_EQUAL/REG_EQUIV notes on
2175 insns that have multiple sets. Checking single_set to
2176 make sure of this is not the proper check, as explained
2177 in the comment in set_unique_reg_note.
2178
2179 This should be changed into an assert. */
2180 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
2181 return 0;
2182 return link;
2183 }
2184 return NULL;
2185}
2186
2187/* Check whether INSN is a single_set whose source is known to be
2188 equivalent to a constant. Return that constant if so, otherwise
2189 return null. */
2190
2191rtx
2192find_constant_src (const rtx_insn *insn)
2193{
2194 rtx note, set, x;
2195
2196 set = single_set (insn);
2197 if (set)
2198 {
2199 x = avoid_constant_pool_reference (SET_SRC (set));
2200 if (CONSTANT_P (x))
2201 return x;
2202 }
2203
2204 note = find_reg_equal_equiv_note (insn);
2205 if (note && CONSTANT_P (XEXP (note, 0)))
2206 return XEXP (note, 0);
2207
2208 return NULL_RTX;
2209}
2210
2211/* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
2212 in the CALL_INSN_FUNCTION_USAGE information of INSN. */
2213
2214int
2215find_reg_fusage (const_rtx insn, enum rtx_code code, const_rtx datum)
2216{
2217 /* If it's not a CALL_INSN, it can't possibly have a
2218 CALL_INSN_FUNCTION_USAGE field, so don't bother checking. */
2219 if (!CALL_P (insn))
2220 return 0;
2221
2222 gcc_assert (datum);
2223
2224 if (!REG_P (datum))
2225 {
2226 rtx link;
2227
2228 for (link = CALL_INSN_FUNCTION_USAGE (insn);
2229 link;
2230 link = XEXP (link, 1))
2231 if (GET_CODE (XEXP (link, 0)) == code
2232 && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
2233 return 1;
2234 }
2235 else
2236 {
2237 unsigned int regno = REGNO (datum);
2238
2239 /* CALL_INSN_FUNCTION_USAGE information cannot contain references
2240 to pseudo registers, so don't bother checking. */
2241
2242 if (regno < FIRST_PSEUDO_REGISTER)
2243 {
2244 unsigned int end_regno = END_REGNO (datum);
2245 unsigned int i;
2246
2247 for (i = regno; i < end_regno; i++)
2248 if (find_regno_fusage (insn, code, i))
2249 return 1;
2250 }
2251 }
2252
2253 return 0;
2254}
2255
2256/* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
2257 in the CALL_INSN_FUNCTION_USAGE information of INSN. */
2258
2259int
2260find_regno_fusage (const_rtx insn, enum rtx_code code, unsigned int regno)
2261{
2262 rtx link;
2263
2264 /* CALL_INSN_FUNCTION_USAGE information cannot contain references
2265 to pseudo registers, so don't bother checking. */
2266
2267 if (regno >= FIRST_PSEUDO_REGISTER
2268 || !CALL_P (insn) )
2269 return 0;
2270
2271 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2272 {
2273 rtx op, reg;
2274
2275 if (GET_CODE (op = XEXP (link, 0)) == code
2276 && REG_P (reg = XEXP (op, 0))
2277 && REGNO (reg) <= regno
2278 && END_REGNO (reg) > regno)
2279 return 1;
2280 }
2281
2282 return 0;
2283}
2284
2285
2286/* Return true if KIND is an integer REG_NOTE. */
2287
2288static bool
2289int_reg_note_p (enum reg_note kind)
2290{
2291 return kind == REG_BR_PROB;
2292}
2293
2294/* Allocate a register note with kind KIND and datum DATUM. LIST is
2295 stored as the pointer to the next register note. */
2296
2297rtx
2298alloc_reg_note (enum reg_note kind, rtx datum, rtx list)
2299{
2300 rtx note;
2301
2302 gcc_checking_assert (!int_reg_note_p (kind));
2303 switch (kind)
2304 {
2305 case REG_CC_SETTER:
2306 case REG_CC_USER:
2307 case REG_LABEL_TARGET:
2308 case REG_LABEL_OPERAND:
2309 case REG_TM:
2310 /* These types of register notes use an INSN_LIST rather than an
2311 EXPR_LIST, so that copying is done right and dumps look
2312 better. */
2313 note = alloc_INSN_LIST (datum, list);
2314 PUT_REG_NOTE_KIND (note, kind);
2315 break;
2316
2317 default:
2318 note = alloc_EXPR_LIST (kind, datum, list);
2319 break;
2320 }
2321
2322 return note;
2323}
2324
2325/* Add register note with kind KIND and datum DATUM to INSN. */
2326
2327void
2328add_reg_note (rtx insn, enum reg_note kind, rtx datum)
2329{
2330 REG_NOTES (insn) = alloc_reg_note (kind, datum, REG_NOTES (insn));
2331}
2332
2333/* Add an integer register note with kind KIND and datum DATUM to INSN. */
2334
2335void
2336add_int_reg_note (rtx_insn *insn, enum reg_note kind, int datum)
2337{
2338 gcc_checking_assert (int_reg_note_p (kind));
2339 REG_NOTES (insn) = gen_rtx_INT_LIST ((machine_mode) kind,
2340 datum, REG_NOTES (insn));
2341}
2342
2343/* Add a register note like NOTE to INSN. */
2344
2345void
2346add_shallow_copy_of_reg_note (rtx_insn *insn, rtx note)
2347{
2348 if (GET_CODE (note) == INT_LIST)
2349 add_int_reg_note (insn, REG_NOTE_KIND (note), XINT (note, 0));
2350 else
2351 add_reg_note (insn, REG_NOTE_KIND (note), XEXP (note, 0));
2352}
2353
2354/* Duplicate NOTE and return the copy. */
2355rtx
2356duplicate_reg_note (rtx note)
2357{
2358 reg_note kind = REG_NOTE_KIND (note);
2359
2360 if (GET_CODE (note) == INT_LIST)
2361 return gen_rtx_INT_LIST ((machine_mode) kind, XINT (note, 0), NULL_RTX);
2362 else if (GET_CODE (note) == EXPR_LIST)
2363 return alloc_reg_note (kind, copy_insn_1 (XEXP (note, 0)), NULL_RTX);
2364 else
2365 return alloc_reg_note (kind, XEXP (note, 0), NULL_RTX);
2366}
2367
2368/* Remove register note NOTE from the REG_NOTES of INSN. */
2369
2370void
2371remove_note (rtx_insn *insn, const_rtx note)
2372{
2373 rtx link;
2374
2375 if (note == NULL_RTX)
2376 return;
2377
2378 if (REG_NOTES (insn) == note)
2379 REG_NOTES (insn) = XEXP (note, 1);
2380 else
2381 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2382 if (XEXP (link, 1) == note)
2383 {
2384 XEXP (link, 1) = XEXP (note, 1);
2385 break;
2386 }
2387
2388 switch (REG_NOTE_KIND (note))
2389 {
2390 case REG_EQUAL:
2391 case REG_EQUIV:
2392 df_notes_rescan (insn);
2393 break;
2394 default:
2395 break;
2396 }
2397}
2398
2399/* Remove REG_EQUAL and/or REG_EQUIV notes if INSN has such notes.
2400 Return true if any note has been removed. */
2401
2402bool
2403remove_reg_equal_equiv_notes (rtx_insn *insn)
2404{
2405 rtx *loc;
2406 bool ret = false;
2407
2408 loc = &REG_NOTES (insn);
2409 while (*loc)
2410 {
2411 enum reg_note kind = REG_NOTE_KIND (*loc);
2412 if (kind == REG_EQUAL || kind == REG_EQUIV)
2413 {
2414 *loc = XEXP (*loc, 1);
2415 ret = true;
2416 }
2417 else
2418 loc = &XEXP (*loc, 1);
2419 }
2420 return ret;
2421}
2422
2423/* Remove all REG_EQUAL and REG_EQUIV notes referring to REGNO. */
2424
2425void
2426remove_reg_equal_equiv_notes_for_regno (unsigned int regno)
2427{
2428 df_ref eq_use;
2429
2430 if (!df)
2431 return;
2432
2433 /* This loop is a little tricky. We cannot just go down the chain because
2434 it is being modified by some actions in the loop. So we just iterate
2435 over the head. We plan to drain the list anyway. */
2436 while ((eq_use = DF_REG_EQ_USE_CHAIN (regno)) != NULL)
2437 {
2438 rtx_insn *insn = DF_REF_INSN (eq_use);
2439 rtx note = find_reg_equal_equiv_note (insn);
2440
2441 /* This assert is generally triggered when someone deletes a REG_EQUAL
2442 or REG_EQUIV note by hacking the list manually rather than calling
2443 remove_note. */
2444 gcc_assert (note);
2445
2446 remove_note (insn, note);
2447 }
2448}
2449
2450/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
2451 return 1 if it is found. A simple equality test is used to determine if
2452 NODE matches. */
2453
2454bool
2455in_insn_list_p (const rtx_insn_list *listp, const rtx_insn *node)
2456{
2457 const_rtx x;
2458
2459 for (x = listp; x; x = XEXP (x, 1))
2460 if (node == XEXP (x, 0))
2461 return true;
2462
2463 return false;
2464}
2465
2466/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
2467 remove that entry from the list if it is found.
2468
2469 A simple equality test is used to determine if NODE matches. */
2470
2471void
2472remove_node_from_expr_list (const_rtx node, rtx_expr_list **listp)
2473{
2474 rtx_expr_list *temp = *listp;
2475 rtx_expr_list *prev = NULL;
2476
2477 while (temp)
2478 {
2479 if (node == temp->element ())
2480 {
2481 /* Splice the node out of the list. */
2482 if (prev)
2483 XEXP (prev, 1) = temp->next ();
2484 else
2485 *listp = temp->next ();
2486
2487 return;
2488 }
2489
2490 prev = temp;
2491 temp = temp->next ();
2492 }
2493}
2494
2495/* Search LISTP (an INSN_LIST) for an entry whose first operand is NODE and
2496 remove that entry from the list if it is found.
2497
2498 A simple equality test is used to determine if NODE matches. */
2499
2500void
2501remove_node_from_insn_list (const rtx_insn *node, rtx_insn_list **listp)
2502{
2503 rtx_insn_list *temp = *listp;
2504 rtx_insn_list *prev = NULL;
2505
2506 while (temp)
2507 {
2508 if (node == temp->insn ())
2509 {
2510 /* Splice the node out of the list. */
2511 if (prev)
2512 XEXP (prev, 1) = temp->next ();
2513 else
2514 *listp = temp->next ();
2515
2516 return;
2517 }
2518
2519 prev = temp;
2520 temp = temp->next ();
2521 }
2522}
2523
2524/* Nonzero if X contains any volatile instructions. These are instructions
2525 which may cause unpredictable machine state instructions, and thus no
2526 instructions or register uses should be moved or combined across them.
2527 This includes only volatile asms and UNSPEC_VOLATILE instructions. */
2528
2529int
2530volatile_insn_p (const_rtx x)
2531{
2532 const RTX_CODE code = GET_CODE (x);
2533 switch (code)
2534 {
2535 case LABEL_REF:
2536 case SYMBOL_REF:
2537 case CONST:
2538 CASE_CONST_ANY:
2539 case CC0:
2540 case PC:
2541 case REG:
2542 case SCRATCH:
2543 case CLOBBER:
2544 case ADDR_VEC:
2545 case ADDR_DIFF_VEC:
2546 case CALL:
2547 case MEM:
2548 return 0;
2549
2550 case UNSPEC_VOLATILE:
2551 return 1;
2552
2553 case ASM_INPUT:
2554 case ASM_OPERANDS:
2555 if (MEM_VOLATILE_P (x))
2556 return 1;
2557
2558 default:
2559 break;
2560 }
2561
2562 /* Recursively scan the operands of this expression. */
2563
2564 {
2565 const char *const fmt = GET_RTX_FORMAT (code);
2566 int i;
2567
2568 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2569 {
2570 if (fmt[i] == 'e')
2571 {
2572 if (volatile_insn_p (XEXP (x, i)))
2573 return 1;
2574 }
2575 else if (fmt[i] == 'E')
2576 {
2577 int j;
2578 for (j = 0; j < XVECLEN (x, i); j++)
2579 if (volatile_insn_p (XVECEXP (x, i, j)))
2580 return 1;
2581 }
2582 }
2583 }
2584 return 0;
2585}
2586
2587/* Nonzero if X contains any volatile memory references
2588 UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions. */
2589
2590int
2591volatile_refs_p (const_rtx x)
2592{
2593 const RTX_CODE code = GET_CODE (x);
2594 switch (code)
2595 {
2596 case LABEL_REF:
2597 case SYMBOL_REF:
2598 case CONST:
2599 CASE_CONST_ANY:
2600 case CC0:
2601 case PC:
2602 case REG:
2603 case SCRATCH:
2604 case CLOBBER:
2605 case ADDR_VEC:
2606 case ADDR_DIFF_VEC:
2607 return 0;
2608
2609 case UNSPEC_VOLATILE:
2610 return 1;
2611
2612 case MEM:
2613 case ASM_INPUT:
2614 case ASM_OPERANDS:
2615 if (MEM_VOLATILE_P (x))
2616 return 1;
2617
2618 default:
2619 break;
2620 }
2621
2622 /* Recursively scan the operands of this expression. */
2623
2624 {
2625 const char *const fmt = GET_RTX_FORMAT (code);
2626 int i;
2627
2628 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2629 {
2630 if (fmt[i] == 'e')
2631 {
2632 if (volatile_refs_p (XEXP (x, i)))
2633 return 1;
2634 }
2635 else if (fmt[i] == 'E')
2636 {
2637 int j;
2638 for (j = 0; j < XVECLEN (x, i); j++)
2639 if (volatile_refs_p (XVECEXP (x, i, j)))
2640 return 1;
2641 }
2642 }
2643 }
2644 return 0;
2645}
2646
2647/* Similar to above, except that it also rejects register pre- and post-
2648 incrementing. */
2649
2650int
2651side_effects_p (const_rtx x)
2652{
2653 const RTX_CODE code = GET_CODE (x);
2654 switch (code)
2655 {
2656 case LABEL_REF:
2657 case SYMBOL_REF:
2658 case CONST:
2659 CASE_CONST_ANY:
2660 case CC0:
2661 case PC:
2662 case REG:
2663 case SCRATCH:
2664 case ADDR_VEC:
2665 case ADDR_DIFF_VEC:
2666 case VAR_LOCATION:
2667 return 0;
2668
2669 case CLOBBER:
2670 /* Reject CLOBBER with a non-VOID mode. These are made by combine.c
2671 when some combination can't be done. If we see one, don't think
2672 that we can simplify the expression. */
2673 return (GET_MODE (x) != VOIDmode);
2674
2675 case PRE_INC:
2676 case PRE_DEC:
2677 case POST_INC:
2678 case POST_DEC:
2679 case PRE_MODIFY:
2680 case POST_MODIFY:
2681 case CALL:
2682 case UNSPEC_VOLATILE:
2683 return 1;
2684
2685 case MEM:
2686 case ASM_INPUT:
2687 case ASM_OPERANDS:
2688 if (MEM_VOLATILE_P (x))
2689 return 1;
2690
2691 default:
2692 break;
2693 }
2694
2695 /* Recursively scan the operands of this expression. */
2696
2697 {
2698 const char *fmt = GET_RTX_FORMAT (code);
2699 int i;
2700
2701 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2702 {
2703 if (fmt[i] == 'e')
2704 {
2705 if (side_effects_p (XEXP (x, i)))
2706 return 1;
2707 }
2708 else if (fmt[i] == 'E')
2709 {
2710 int j;
2711 for (j = 0; j < XVECLEN (x, i); j++)
2712 if (side_effects_p (XVECEXP (x, i, j)))
2713 return 1;
2714 }
2715 }
2716 }
2717 return 0;
2718}
2719
2720/* Return nonzero if evaluating rtx X might cause a trap.
2721 FLAGS controls how to consider MEMs. A nonzero means the context
2722 of the access may have changed from the original, such that the
2723 address may have become invalid. */
2724
2725int
2726may_trap_p_1 (const_rtx x, unsigned flags)
2727{
2728 int i;
2729 enum rtx_code code;
2730 const char *fmt;
2731
2732 /* We make no distinction currently, but this function is part of
2733 the internal target-hooks ABI so we keep the parameter as
2734 "unsigned flags". */
2735 bool code_changed = flags != 0;
2736
2737 if (x == 0)
2738 return 0;
2739 code = GET_CODE (x);
2740 switch (code)
2741 {
2742 /* Handle these cases quickly. */
2743 CASE_CONST_ANY:
2744 case SYMBOL_REF:
2745 case LABEL_REF:
2746 case CONST:
2747 case PC:
2748 case CC0:
2749 case REG:
2750 case SCRATCH:
2751 return 0;
2752
2753 case UNSPEC:
2754 return targetm.unspec_may_trap_p (x, flags);
2755
2756 case UNSPEC_VOLATILE:
2757 case ASM_INPUT:
2758 case TRAP_IF:
2759 return 1;
2760
2761 case ASM_OPERANDS:
2762 return MEM_VOLATILE_P (x);
2763
2764 /* Memory ref can trap unless it's a static var or a stack slot. */
2765 case MEM:
2766 /* Recognize specific pattern of stack checking probes. */
2767 if (flag_stack_check
2768 && MEM_VOLATILE_P (x)
2769 && XEXP (x, 0) == stack_pointer_rtx)
2770 return 1;
2771 if (/* MEM_NOTRAP_P only relates to the actual position of the memory
2772 reference; moving it out of context such as when moving code
2773 when optimizing, might cause its address to become invalid. */
2774 code_changed
2775 || !MEM_NOTRAP_P (x))
2776 {
2777 HOST_WIDE_INT size = MEM_SIZE_KNOWN_P (x) ? MEM_SIZE (x) : 0;
2778 return rtx_addr_can_trap_p_1 (XEXP (x, 0), 0, size,
2779 GET_MODE (x), code_changed);
2780 }
2781
2782 return 0;
2783
2784 /* Division by a non-constant might trap. */
2785 case DIV:
2786 case MOD:
2787 case UDIV:
2788 case UMOD:
2789 if (HONOR_SNANS (x))
2790 return 1;
2791 if (SCALAR_FLOAT_MODE_P (GET_MODE (x)))
2792 return flag_trapping_math;
2793 if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2794 return 1;
2795 break;
2796
2797 case EXPR_LIST:
2798 /* An EXPR_LIST is used to represent a function call. This
2799 certainly may trap. */
2800 return 1;
2801
2802 case GE:
2803 case GT:
2804 case LE:
2805 case LT:
2806 case LTGT:
2807 case COMPARE:
2808 /* Some floating point comparisons may trap. */
2809 if (!flag_trapping_math)
2810 break;
2811 /* ??? There is no machine independent way to check for tests that trap
2812 when COMPARE is used, though many targets do make this distinction.
2813 For instance, sparc uses CCFPE for compares which generate exceptions
2814 and CCFP for compares which do not generate exceptions. */
2815 if (HONOR_NANS (x))
2816 return 1;
2817 /* But often the compare has some CC mode, so check operand
2818 modes as well. */
2819 if (HONOR_NANS (XEXP (x, 0))
2820 || HONOR_NANS (XEXP (x, 1)))
2821 return 1;
2822 break;
2823
2824 case EQ:
2825 case NE:
2826 if (HONOR_SNANS (x))
2827 return 1;
2828 /* Often comparison is CC mode, so check operand modes. */
2829 if (HONOR_SNANS (XEXP (x, 0))
2830 || HONOR_SNANS (XEXP (x, 1)))
2831 return 1;
2832 break;
2833
2834 case FIX:
2835 /* Conversion of floating point might trap. */
2836 if (flag_trapping_math && HONOR_NANS (XEXP (x, 0)))
2837 return 1;
2838 break;
2839
2840 case NEG:
2841 case ABS:
2842 case SUBREG:
2843 /* These operations don't trap even with floating point. */
2844 break;
2845
2846 default:
2847 /* Any floating arithmetic may trap. */
2848 if (SCALAR_FLOAT_MODE_P (GET_MODE (x)) && flag_trapping_math)
2849 return 1;
2850 }
2851
2852 fmt = GET_RTX_FORMAT (code);
2853 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2854 {
2855 if (fmt[i] == 'e')
2856 {
2857 if (may_trap_p_1 (XEXP (x, i), flags))
2858 return 1;
2859 }
2860 else if (fmt[i] == 'E')
2861 {
2862 int j;
2863 for (j = 0; j < XVECLEN (x, i); j++)
2864 if (may_trap_p_1 (XVECEXP (x, i, j), flags))
2865 return 1;
2866 }
2867 }
2868 return 0;
2869}
2870
2871/* Return nonzero if evaluating rtx X might cause a trap. */
2872
2873int
2874may_trap_p (const_rtx x)
2875{
2876 return may_trap_p_1 (x, 0);
2877}
2878
2879/* Same as above, but additionally return nonzero if evaluating rtx X might
2880 cause a fault. We define a fault for the purpose of this function as a
2881 erroneous execution condition that cannot be encountered during the normal
2882 execution of a valid program; the typical example is an unaligned memory
2883 access on a strict alignment machine. The compiler guarantees that it
2884 doesn't generate code that will fault from a valid program, but this
2885 guarantee doesn't mean anything for individual instructions. Consider
2886 the following example:
2887
2888 struct S { int d; union { char *cp; int *ip; }; };
2889
2890 int foo(struct S *s)
2891 {
2892 if (s->d == 1)
2893 return *s->ip;
2894 else
2895 return *s->cp;
2896 }
2897
2898 on a strict alignment machine. In a valid program, foo will never be
2899 invoked on a structure for which d is equal to 1 and the underlying
2900 unique field of the union not aligned on a 4-byte boundary, but the
2901 expression *s->ip might cause a fault if considered individually.
2902
2903 At the RTL level, potentially problematic expressions will almost always
2904 verify may_trap_p; for example, the above dereference can be emitted as
2905 (mem:SI (reg:P)) and this expression is may_trap_p for a generic register.
2906 However, suppose that foo is inlined in a caller that causes s->cp to
2907 point to a local character variable and guarantees that s->d is not set
2908 to 1; foo may have been effectively translated into pseudo-RTL as:
2909
2910 if ((reg:SI) == 1)
2911 (set (reg:SI) (mem:SI (%fp - 7)))
2912 else
2913 (set (reg:QI) (mem:QI (%fp - 7)))
2914
2915 Now (mem:SI (%fp - 7)) is considered as not may_trap_p since it is a
2916 memory reference to a stack slot, but it will certainly cause a fault
2917 on a strict alignment machine. */
2918
2919int
2920may_trap_or_fault_p (const_rtx x)
2921{
2922 return may_trap_p_1 (x, 1);
2923}
2924
2925/* Return nonzero if X contains a comparison that is not either EQ or NE,
2926 i.e., an inequality. */
2927
2928int
2929inequality_comparisons_p (const_rtx x)
2930{
2931 const char *fmt;
2932 int len, i;
2933 const enum rtx_code code = GET_CODE (x);
2934
2935 switch (code)
2936 {
2937 case REG:
2938 case SCRATCH:
2939 case PC:
2940 case CC0:
2941 CASE_CONST_ANY:
2942 case CONST:
2943 case LABEL_REF:
2944 case SYMBOL_REF:
2945 return 0;
2946
2947 case LT:
2948 case LTU:
2949 case GT:
2950 case GTU:
2951 case LE:
2952 case LEU:
2953 case GE:
2954 case GEU:
2955 return 1;
2956
2957 default:
2958 break;
2959 }
2960
2961 len = GET_RTX_LENGTH (code);
2962 fmt = GET_RTX_FORMAT (code);
2963
2964 for (i = 0; i < len; i++)
2965 {
2966 if (fmt[i] == 'e')
2967 {
2968 if (inequality_comparisons_p (XEXP (x, i)))
2969 return 1;
2970 }
2971 else if (fmt[i] == 'E')
2972 {
2973 int j;
2974 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2975 if (inequality_comparisons_p (XVECEXP (x, i, j)))
2976 return 1;
2977 }
2978 }
2979
2980 return 0;
2981}
2982
2983/* Replace any occurrence of FROM in X with TO. The function does
2984 not enter into CONST_DOUBLE for the replace.
2985
2986 Note that copying is not done so X must not be shared unless all copies
2987 are to be modified.
2988
2989 ALL_REGS is true if we want to replace all REGs equal to FROM, not just
2990 those pointer-equal ones. */
2991
2992rtx
2993replace_rtx (rtx x, rtx from, rtx to, bool all_regs)
2994{
2995 int i, j;
2996 const char *fmt;
2997
2998 if (x == from)
2999 return to;
3000
3001 /* Allow this function to make replacements in EXPR_LISTs. */
3002 if (x == 0)
3003 return 0;
3004
3005 if (all_regs
3006 && REG_P (x)
3007 && REG_P (from)
3008 && REGNO (x) == REGNO (from))
3009 {
3010 gcc_assert (GET_MODE (x) == GET_MODE (from));
3011 return to;
3012 }
3013 else if (GET_CODE (x) == SUBREG)
3014 {
3015 rtx new_rtx = replace_rtx (SUBREG_REG (x), from, to, all_regs);
3016
3017 if (CONST_INT_P (new_rtx))
3018 {
3019 x = simplify_subreg (GET_MODE (x), new_rtx,
3020 GET_MODE (SUBREG_REG (x)),
3021 SUBREG_BYTE (x));
3022 gcc_assert (x);
3023 }
3024 else
3025 SUBREG_REG (x) = new_rtx;
3026
3027 return x;
3028 }
3029 else if (GET_CODE (x) == ZERO_EXTEND)
3030 {
3031 rtx new_rtx = replace_rtx (XEXP (x, 0), from, to, all_regs);
3032
3033 if (CONST_INT_P (new_rtx))
3034 {
3035 x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
3036 new_rtx, GET_MODE (XEXP (x, 0)));
3037 gcc_assert (x);
3038 }
3039 else
3040 XEXP (x, 0) = new_rtx;
3041
3042 return x;
3043 }
3044
3045 fmt = GET_RTX_FORMAT (GET_CODE (x));
3046 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3047 {
3048 if (fmt[i] == 'e')
3049 XEXP (x, i) = replace_rtx (XEXP (x, i), from, to, all_regs);
3050 else if (fmt[i] == 'E')
3051 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3052 XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j),
3053 from, to, all_regs);
3054 }
3055
3056 return x;
3057}
3058
3059/* Replace occurrences of the OLD_LABEL in *LOC with NEW_LABEL. Also track
3060 the change in LABEL_NUSES if UPDATE_LABEL_NUSES. */
3061
3062void
3063replace_label (rtx *loc, rtx old_label, rtx new_label, bool update_label_nuses)
3064{
3065 /* Handle jump tables specially, since ADDR_{DIFF_,}VECs can be long. */
3066 rtx x = *loc;
3067 if (JUMP_TABLE_DATA_P (x))
3068 {
3069 x = PATTERN (x);
3070 rtvec vec = XVEC (x, GET_CODE (x) == ADDR_DIFF_VEC);
3071 int len = GET_NUM_ELEM (vec);
3072 for (int i = 0; i < len; ++i)
3073 {
3074 rtx ref = RTVEC_ELT (vec, i);
3075 if (XEXP (ref, 0) == old_label)
3076 {
3077 XEXP (ref, 0) = new_label;
3078 if (update_label_nuses)
3079 {
3080 ++LABEL_NUSES (new_label);
3081 --LABEL_NUSES (old_label);
3082 }
3083 }
3084 }
3085 return;
3086 }
3087
3088 /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
3089 field. This is not handled by the iterator because it doesn't
3090 handle unprinted ('0') fields. */
3091 if (JUMP_P (x) && JUMP_LABEL (x) == old_label)
3092 JUMP_LABEL (x) = new_label;
3093
3094 subrtx_ptr_iterator::array_type array;
3095 FOR_EACH_SUBRTX_PTR (iter, array, loc, ALL)
3096 {
3097 rtx *loc = *iter;
3098 if (rtx x = *loc)
3099 {
3100 if (GET_CODE (x) == SYMBOL_REF
3101 && CONSTANT_POOL_ADDRESS_P (x))
3102 {
3103 rtx c = get_pool_constant (x);
3104 if (rtx_referenced_p (old_label, c))
3105 {
3106 /* Create a copy of constant C; replace the label inside
3107 but do not update LABEL_NUSES because uses in constant pool
3108 are not counted. */
3109 rtx new_c = copy_rtx (c);
3110 replace_label (&new_c, old_label, new_label, false);
3111
3112 /* Add the new constant NEW_C to constant pool and replace
3113 the old reference to constant by new reference. */
3114 rtx new_mem = force_const_mem (get_pool_mode (x), new_c);
3115 *loc = replace_rtx (x, x, XEXP (new_mem, 0));
3116 }
3117 }
3118
3119 if ((GET_CODE (x) == LABEL_REF
3120 || GET_CODE (x) == INSN_LIST)
3121 && XEXP (x, 0) == old_label)
3122 {
3123 XEXP (x, 0) = new_label;
3124 if (update_label_nuses)
3125 {
3126 ++LABEL_NUSES (new_label);
3127 --LABEL_NUSES (old_label);
3128 }
3129 }
3130 }
3131 }
3132}
3133
3134void
3135replace_label_in_insn (rtx_insn *insn, rtx_insn *old_label,
3136 rtx_insn *new_label, bool update_label_nuses)
3137{
3138 rtx insn_as_rtx = insn;
3139 replace_label (&insn_as_rtx, old_label, new_label, update_label_nuses);
3140 gcc_checking_assert (insn_as_rtx == insn);
3141}
3142
3143/* Return true if X is referenced in BODY. */
3144
3145bool
3146rtx_referenced_p (const_rtx x, const_rtx body)
3147{
3148 subrtx_iterator::array_type array;
3149 FOR_EACH_SUBRTX (iter, array, body, ALL)
3150 if (const_rtx y = *iter)
3151 {
3152 /* Check if a label_ref Y refers to label X. */
3153 if (GET_CODE (y) == LABEL_REF
3154 && LABEL_P (x)
3155 && label_ref_label (y) == x)
3156 return true;
3157
3158 if (rtx_equal_p (x, y))
3159 return true;
3160
3161 /* If Y is a reference to pool constant traverse the constant. */
3162 if (GET_CODE (y) == SYMBOL_REF
3163 && CONSTANT_POOL_ADDRESS_P (y))
3164 iter.substitute (get_pool_constant (y));
3165 }
3166 return false;
3167}
3168
3169/* If INSN is a tablejump return true and store the label (before jump table) to
3170 *LABELP and the jump table to *TABLEP. LABELP and TABLEP may be NULL. */
3171
3172bool
3173tablejump_p (const rtx_insn *insn, rtx_insn **labelp,
3174 rtx_jump_table_data **tablep)
3175{
3176 if (!JUMP_P (insn))
3177 return false;
3178
3179 rtx target = JUMP_LABEL (insn);
3180 if (target == NULL_RTX || ANY_RETURN_P (target))
3181 return false;
3182
3183 rtx_insn *label = as_a<rtx_insn *> (target);
3184 rtx_insn *table = next_insn (label);
3185 if (table == NULL_RTX || !JUMP_TABLE_DATA_P (table))
3186 return false;
3187
3188 if (labelp)
3189 *labelp = label;
3190 if (tablep)
3191 *tablep = as_a <rtx_jump_table_data *> (table);
3192 return true;
3193}
3194
3195/* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
3196 constant that is not in the constant pool and not in the condition
3197 of an IF_THEN_ELSE. */
3198
3199static int
3200computed_jump_p_1 (const_rtx x)
3201{
3202 const enum rtx_code code = GET_CODE (x);
3203 int i, j;
3204 const char *fmt;
3205
3206 switch (code)
3207 {
3208 case LABEL_REF:
3209 case PC:
3210 return 0;
3211
3212 case CONST:
3213 CASE_CONST_ANY:
3214 case SYMBOL_REF:
3215 case REG:
3216 return 1;
3217
3218 case MEM:
3219 return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
3220 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
3221
3222 case IF_THEN_ELSE:
3223 return (computed_jump_p_1 (XEXP (x, 1))
3224 || computed_jump_p_1 (XEXP (x, 2)));
3225
3226 default:
3227 break;
3228 }
3229
3230 fmt = GET_RTX_FORMAT (code);
3231 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3232 {
3233 if (fmt[i] == 'e'
3234 && computed_jump_p_1 (XEXP (x, i)))
3235 return 1;
3236
3237 else if (fmt[i] == 'E')
3238 for (j = 0; j < XVECLEN (x, i); j++)
3239 if (computed_jump_p_1 (XVECEXP (x, i, j)))
3240 return 1;
3241 }
3242
3243 return 0;
3244}
3245
3246/* Return nonzero if INSN is an indirect jump (aka computed jump).
3247
3248 Tablejumps and casesi insns are not considered indirect jumps;
3249 we can recognize them by a (use (label_ref)). */
3250
3251int
3252computed_jump_p (const rtx_insn *insn)
3253{
3254 int i;
3255 if (JUMP_P (insn))
3256 {
3257 rtx pat = PATTERN (insn);
3258
3259 /* If we have a JUMP_LABEL set, we're not a computed jump. */
3260 if (JUMP_LABEL (insn) != NULL)
3261 return 0;
3262
3263 if (GET_CODE (pat) == PARALLEL)
3264 {
3265 int len = XVECLEN (pat, 0);
3266 int has_use_labelref = 0;
3267
3268 for (i = len - 1; i >= 0; i--)
3269 if (GET_CODE (XVECEXP (pat, 0, i)) == USE
3270 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
3271 == LABEL_REF))
3272 {
3273 has_use_labelref = 1;
3274 break;
3275 }
3276
3277 if (! has_use_labelref)
3278 for (i = len - 1; i >= 0; i--)
3279 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
3280 && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
3281 && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
3282 return 1;
3283 }
3284 else if (GET_CODE (pat) == SET
3285 && SET_DEST (pat) == pc_rtx
3286 && computed_jump_p_1 (SET_SRC (pat)))
3287 return 1;
3288 }
3289 return 0;
3290}
3291
3292
3293
3294/* MEM has a PRE/POST-INC/DEC/MODIFY address X. Extract the operands of
3295 the equivalent add insn and pass the result to FN, using DATA as the
3296 final argument. */
3297
3298static int
3299for_each_inc_dec_find_inc_dec (rtx mem, for_each_inc_dec_fn fn, void *data)
3300{
3301 rtx x = XEXP (mem, 0);
3302 switch (GET_CODE (x))
3303 {
3304 case PRE_INC:
3305 case POST_INC:
3306 {
3307 int size = GET_MODE_SIZE (GET_MODE (mem));
3308 rtx r1 = XEXP (x, 0);
3309 rtx c = gen_int_mode (size, GET_MODE (r1));
3310 return fn (mem, x, r1, r1, c, data);
3311 }
3312
3313 case PRE_DEC:
3314 case POST_DEC:
3315 {
3316 int size = GET_MODE_SIZE (GET_MODE (mem));
3317 rtx r1 = XEXP (x, 0);
3318 rtx c = gen_int_mode (-size, GET_MODE (r1));
3319 return fn (mem, x, r1, r1, c, data);
3320 }
3321
3322 case PRE_MODIFY:
3323 case POST_MODIFY:
3324 {
3325 rtx r1 = XEXP (x, 0);
3326 rtx add = XEXP (x, 1);
3327 return fn (mem, x, r1, add, NULL, data);
3328 }
3329
3330 default:
3331 gcc_unreachable ();
3332 }
3333}
3334
3335/* Traverse *LOC looking for MEMs that have autoinc addresses.
3336 For each such autoinc operation found, call FN, passing it
3337 the innermost enclosing MEM, the operation itself, the RTX modified
3338 by the operation, two RTXs (the second may be NULL) that, once
3339 added, represent the value to be held by the modified RTX
3340 afterwards, and DATA. FN is to return 0 to continue the
3341 traversal or any other value to have it returned to the caller of
3342 for_each_inc_dec. */
3343
3344int
3345for_each_inc_dec (rtx x,
3346 for_each_inc_dec_fn fn,
3347 void *data)
3348{
3349 subrtx_var_iterator::array_type array;
3350 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
3351 {
3352 rtx mem = *iter;
3353 if (mem
3354 && MEM_P (mem)
3355 && GET_RTX_CLASS (GET_CODE (XEXP (mem, 0))) == RTX_AUTOINC)
3356 {
3357 int res = for_each_inc_dec_find_inc_dec (mem, fn, data);
3358 if (res != 0)
3359 return res;
3360 iter.skip_subrtxes ();
3361 }
3362 }
3363 return 0;
3364}
3365
3366
3367/* Searches X for any reference to REGNO, returning the rtx of the
3368 reference found if any. Otherwise, returns NULL_RTX. */
3369
3370rtx
3371regno_use_in (unsigned int regno, rtx x)
3372{
3373 const char *fmt;
3374 int i, j;
3375 rtx tem;
3376
3377 if (REG_P (x) && REGNO (x) == regno)
3378 return x;
3379
3380 fmt = GET_RTX_FORMAT (GET_CODE (x));
3381 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3382 {
3383 if (fmt[i] == 'e')
3384 {
3385 if ((tem = regno_use_in (regno, XEXP (x, i))))
3386 return tem;
3387 }
3388 else if (fmt[i] == 'E')
3389 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3390 if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
3391 return tem;
3392 }
3393
3394 return NULL_RTX;
3395}
3396
3397/* Return a value indicating whether OP, an operand of a commutative
3398 operation, is preferred as the first or second operand. The more
3399 positive the value, the stronger the preference for being the first
3400 operand. */
3401
3402int
3403commutative_operand_precedence (rtx op)
3404{
3405 enum rtx_code code = GET_CODE (op);
3406
3407 /* Constants always become the second operand. Prefer "nice" constants. */
3408 if (code == CONST_INT)
3409 return -8;
3410 if (code == CONST_WIDE_INT)
3411 return -7;
3412 if (code == CONST_DOUBLE)
3413 return -7;
3414 if (code == CONST_FIXED)
3415 return -7;
3416 op = avoid_constant_pool_reference (op);
3417 code = GET_CODE (op);
3418
3419 switch (GET_RTX_CLASS (code))
3420 {
3421 case RTX_CONST_OBJ:
3422 if (code == CONST_INT)
3423 return -6;
3424 if (code == CONST_WIDE_INT)
3425 return -6;
3426 if (code == CONST_DOUBLE)
3427 return -5;
3428 if (code == CONST_FIXED)
3429 return -5;
3430 return -4;
3431
3432 case RTX_EXTRA:
3433 /* SUBREGs of objects should come second. */
3434 if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
3435 return -3;
3436 return 0;
3437
3438 case RTX_OBJ:
3439 /* Complex expressions should be the first, so decrease priority
3440 of objects. Prefer pointer objects over non pointer objects. */
3441 if ((REG_P (op) && REG_POINTER (op))
3442 || (MEM_P (op) && MEM_POINTER (op)))
3443 return -1;
3444 return -2;
3445
3446 case RTX_COMM_ARITH:
3447 /* Prefer operands that are themselves commutative to be first.
3448 This helps to make things linear. In particular,
3449 (and (and (reg) (reg)) (not (reg))) is canonical. */
3450 return 4;
3451
3452 case RTX_BIN_ARITH:
3453 /* If only one operand is a binary expression, it will be the first
3454 operand. In particular, (plus (minus (reg) (reg)) (neg (reg)))
3455 is canonical, although it will usually be further simplified. */
3456 return 2;
3457
3458 case RTX_UNARY:
3459 /* Then prefer NEG and NOT. */
3460 if (code == NEG || code == NOT)
3461 return 1;
3462 /* FALLTHRU */
3463
3464 default:
3465 return 0;
3466 }
3467}
3468
3469/* Return 1 iff it is necessary to swap operands of commutative operation
3470 in order to canonicalize expression. */
3471
3472bool
3473swap_commutative_operands_p (rtx x, rtx y)
3474{
3475 return (commutative_operand_precedence (x)
3476 < commutative_operand_precedence (y));
3477}
3478
3479/* Return 1 if X is an autoincrement side effect and the register is
3480 not the stack pointer. */
3481int
3482auto_inc_p (const_rtx x)
3483{
3484 switch (GET_CODE (x))
3485 {
3486 case PRE_INC:
3487 case POST_INC:
3488 case PRE_DEC:
3489 case POST_DEC:
3490 case PRE_MODIFY:
3491 case POST_MODIFY:
3492 /* There are no REG_INC notes for SP. */
3493 if (XEXP (x, 0) != stack_pointer_rtx)
3494 return 1;
3495 default:
3496 break;
3497 }
3498 return 0;
3499}
3500
3501/* Return nonzero if IN contains a piece of rtl that has the address LOC. */
3502int
3503loc_mentioned_in_p (rtx *loc, const_rtx in)
3504{
3505 enum rtx_code code;
3506 const char *fmt;
3507 int i, j;
3508
3509 if (!in)
3510 return 0;
3511
3512 code = GET_CODE (in);
3513 fmt = GET_RTX_FORMAT (code);
3514 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3515 {
3516 if (fmt[i] == 'e')
3517 {
3518 if (loc == &XEXP (in, i) || loc_mentioned_in_p (loc, XEXP (in, i)))
3519 return 1;
3520 }
3521 else if (fmt[i] == 'E')
3522 for (j = XVECLEN (in, i) - 1; j >= 0; j--)
3523 if (loc == &XVECEXP (in, i, j)
3524 || loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3525 return 1;
3526 }
3527 return 0;
3528}
3529
3530/* Helper function for subreg_lsb. Given a subreg's OUTER_MODE, INNER_MODE,
3531 and SUBREG_BYTE, return the bit offset where the subreg begins
3532 (counting from the least significant bit of the operand). */
3533
3534unsigned int
3535subreg_lsb_1 (machine_mode outer_mode,
3536 machine_mode inner_mode,
3537 unsigned int subreg_byte)
3538{
3539 unsigned int bitpos;
3540 unsigned int byte;
3541 unsigned int word;
3542
3543 /* A paradoxical subreg begins at bit position 0. */
3544 if (paradoxical_subreg_p (outer_mode, inner_mode))
3545 return 0;
3546
3547 if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3548 /* If the subreg crosses a word boundary ensure that
3549 it also begins and ends on a word boundary. */
3550 gcc_assert (!((subreg_byte % UNITS_PER_WORD
3551 + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
3552 && (subreg_byte % UNITS_PER_WORD
3553 || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
3554
3555 if (WORDS_BIG_ENDIAN)
3556 word = (GET_MODE_SIZE (inner_mode)
3557 - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3558 else
3559 word = subreg_byte / UNITS_PER_WORD;
3560 bitpos = word * BITS_PER_WORD;
3561
3562 if (BYTES_BIG_ENDIAN)
3563 byte = (GET_MODE_SIZE (inner_mode)
3564 - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3565 else
3566 byte = subreg_byte % UNITS_PER_WORD;
3567 bitpos += byte * BITS_PER_UNIT;
3568
3569 return bitpos;
3570}
3571
3572/* Given a subreg X, return the bit offset where the subreg begins
3573 (counting from the least significant bit of the reg). */
3574
3575unsigned int
3576subreg_lsb (const_rtx x)
3577{
3578 return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3579 SUBREG_BYTE (x));
3580}
3581
3582/* Return the subreg byte offset for a subreg whose outer value has
3583 OUTER_BYTES bytes, whose inner value has INNER_BYTES bytes, and where
3584 there are LSB_SHIFT *bits* between the lsb of the outer value and the
3585 lsb of the inner value. This is the inverse of the calculation
3586 performed by subreg_lsb_1 (which converts byte offsets to bit shifts). */
3587
3588unsigned int
3589subreg_size_offset_from_lsb (unsigned int outer_bytes,
3590 unsigned int inner_bytes,
3591 unsigned int lsb_shift)
3592{
3593 /* A paradoxical subreg begins at bit position 0. */
3594 if (outer_bytes > inner_bytes)
3595 {
3596 gcc_checking_assert (lsb_shift == 0);
3597 return 0;
3598 }
3599
3600 gcc_assert (lsb_shift % BITS_PER_UNIT == 0);
3601 unsigned int lower_bytes = lsb_shift / BITS_PER_UNIT;
3602 unsigned int upper_bytes = inner_bytes - (lower_bytes + outer_bytes);
3603 if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
3604 return upper_bytes;
3605 else if (!WORDS_BIG_ENDIAN && !BYTES_BIG_ENDIAN)
3606 return lower_bytes;
3607 else
3608 {
3609 unsigned int lower_word_part = lower_bytes & -UNITS_PER_WORD;
3610 unsigned int upper_word_part = upper_bytes & -UNITS_PER_WORD;
3611 if (WORDS_BIG_ENDIAN)
3612 return upper_word_part + (lower_bytes - lower_word_part);
3613 else
3614 return lower_word_part + (upper_bytes - upper_word_part);
3615 }
3616}
3617
3618/* Fill in information about a subreg of a hard register.
3619 xregno - A regno of an inner hard subreg_reg (or what will become one).
3620 xmode - The mode of xregno.
3621 offset - The byte offset.
3622 ymode - The mode of a top level SUBREG (or what may become one).
3623 info - Pointer to structure to fill in.
3624
3625 Rather than considering one particular inner register (and thus one
3626 particular "outer" register) in isolation, this function really uses
3627 XREGNO as a model for a sequence of isomorphic hard registers. Thus the
3628 function does not check whether adding INFO->offset to XREGNO gives
3629 a valid hard register; even if INFO->offset + XREGNO is out of range,
3630 there might be another register of the same type that is in range.
3631 Likewise it doesn't check whether targetm.hard_regno_mode_ok accepts
3632 the new register, since that can depend on things like whether the final
3633 register number is even or odd. Callers that want to check whether
3634 this particular subreg can be replaced by a simple (reg ...) should
3635 use simplify_subreg_regno. */
3636
3637void
3638subreg_get_info (unsigned int xregno, machine_mode xmode,
3639 unsigned int offset, machine_mode ymode,
3640 struct subreg_info *info)
3641{
3642 unsigned int nregs_xmode, nregs_ymode;
3643
3644 gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3645
3646 unsigned int xsize = GET_MODE_SIZE (xmode);
3647 unsigned int ysize = GET_MODE_SIZE (ymode);
3648 bool rknown = false;
3649
3650 /* If the register representation of a non-scalar mode has holes in it,
3651 we expect the scalar units to be concatenated together, with the holes
3652 distributed evenly among the scalar units. Each scalar unit must occupy
3653 at least one register. */
3654 if (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode))
3655 {
3656 nregs_xmode = HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode);
3657 unsigned int nunits = GET_MODE_NUNITS (xmode);
3658 scalar_mode xmode_unit = GET_MODE_INNER (xmode);
3659 gcc_assert (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode_unit));
3660 gcc_assert (nregs_xmode
3661 == (nunits
3662 * HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode_unit)));
3663 gcc_assert (hard_regno_nregs (xregno, xmode)
3664 == hard_regno_nregs (xregno, xmode_unit) * nunits);
3665
3666 /* You can only ask for a SUBREG of a value with holes in the middle
3667 if you don't cross the holes. (Such a SUBREG should be done by
3668 picking a different register class, or doing it in memory if
3669 necessary.) An example of a value with holes is XCmode on 32-bit
3670 x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
3671 3 for each part, but in memory it's two 128-bit parts.
3672 Padding is assumed to be at the end (not necessarily the 'high part')
3673 of each unit. */
3674 if ((offset / GET_MODE_SIZE (xmode_unit) + 1 < nunits)
3675 && (offset / GET_MODE_SIZE (xmode_unit)
3676 != ((offset + ysize - 1) / GET_MODE_SIZE (xmode_unit))))
3677 {
3678 info->representable_p = false;
3679 rknown = true;
3680 }
3681 }
3682 else
3683 nregs_xmode = hard_regno_nregs (xregno, xmode);
3684
3685 nregs_ymode = hard_regno_nregs (xregno, ymode);
3686
3687 /* Paradoxical subregs are otherwise valid. */
3688 if (!rknown && offset == 0 && ysize > xsize)
3689 {
3690 info->representable_p = true;
3691 /* If this is a big endian paradoxical subreg, which uses more
3692 actual hard registers than the original register, we must
3693 return a negative offset so that we find the proper highpart
3694 of the register.
3695
3696 We assume that the ordering of registers within a multi-register
3697 value has a consistent endianness: if bytes and register words
3698 have different endianness, the hard registers that make up a
3699 multi-register value must be at least word-sized. */
3700 if (REG_WORDS_BIG_ENDIAN)
3701 info->offset = (int) nregs_xmode - (int) nregs_ymode;
3702 else
3703 info->offset = 0;
3704 info->nregs = nregs_ymode;
3705 return;
3706 }
3707
3708 /* If registers store different numbers of bits in the different
3709 modes, we cannot generally form this subreg. */
3710 if (!HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode)
3711 && !HARD_REGNO_NREGS_HAS_PADDING (xregno, ymode)
3712 && (xsize % nregs_xmode) == 0
3713 && (ysize % nregs_ymode) == 0)
3714 {
3715 int regsize_xmode = xsize / nregs_xmode;
3716 int regsize_ymode = ysize / nregs_ymode;
3717 if (!rknown
3718 && ((nregs_ymode > 1 && regsize_xmode > regsize_ymode)
3719 || (nregs_xmode > 1 && regsize_ymode > regsize_xmode)))
3720 {
3721 info->representable_p = false;
3722 info->nregs = CEIL (ysize, regsize_xmode);
3723 info->offset = offset / regsize_xmode;
3724 return;
3725 }
3726 /* It's not valid to extract a subreg of mode YMODE at OFFSET that
3727 would go outside of XMODE. */
3728 if (!rknown && ysize + offset > xsize)
3729 {
3730 info->representable_p = false;
3731 info->nregs = nregs_ymode;
3732 info->offset = offset / regsize_xmode;
3733 return;
3734 }
3735 /* Quick exit for the simple and common case of extracting whole
3736 subregisters from a multiregister value. */
3737 /* ??? It would be better to integrate this into the code below,
3738 if we can generalize the concept enough and figure out how
3739 odd-sized modes can coexist with the other weird cases we support. */
3740 if (!rknown
3741 && WORDS_BIG_ENDIAN == REG_WORDS_BIG_ENDIAN
3742 && regsize_xmode == regsize_ymode
3743 && (offset % regsize_ymode) == 0)
3744 {
3745 info->representable_p = true;
3746 info->nregs = nregs_ymode;
3747 info->offset = offset / regsize_ymode;
3748 gcc_assert (info->offset + info->nregs <= (int) nregs_xmode);
3749 return;
3750 }
3751 }
3752
3753 /* Lowpart subregs are otherwise valid. */
3754 if (!rknown && offset == subreg_lowpart_offset (ymode, xmode))
3755 {
3756 info->representable_p = true;
3757 rknown = true;
3758
3759 if (offset == 0 || nregs_xmode == nregs_ymode)
3760 {
3761 info->offset = 0;
3762 info->nregs = nregs_ymode;
3763 return;
3764 }
3765 }
3766
3767 /* Set NUM_BLOCKS to the number of independently-representable YMODE
3768 values there are in (reg:XMODE XREGNO). We can view the register
3769 as consisting of this number of independent "blocks", where each
3770 block occupies NREGS_YMODE registers and contains exactly one
3771 representable YMODE value. */
3772 gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3773 unsigned int num_blocks = nregs_xmode / nregs_ymode;
3774
3775 /* Calculate the number of bytes in each block. This must always
3776 be exact, otherwise we don't know how to verify the constraint.
3777 These conditions may be relaxed but subreg_regno_offset would
3778 need to be redesigned. */
3779 gcc_assert ((xsize % num_blocks) == 0);
3780 unsigned int bytes_per_block = xsize / num_blocks;
3781
3782 /* Get the number of the first block that contains the subreg and the byte
3783 offset of the subreg from the start of that block. */
3784 unsigned int block_number = offset / bytes_per_block;
3785 unsigned int subblock_offset = offset % bytes_per_block;
3786
3787 if (!rknown)
3788 {
3789 /* Only the lowpart of each block is representable. */
3790 info->representable_p
3791 = (subblock_offset
3792 == subreg_size_lowpart_offset (ysize, bytes_per_block));
3793 rknown = true;
3794 }
3795
3796 /* We assume that the ordering of registers within a multi-register
3797 value has a consistent endianness: if bytes and register words
3798 have different endianness, the hard registers that make up a
3799 multi-register value must be at least word-sized. */
3800 if (WORDS_BIG_ENDIAN != REG_WORDS_BIG_ENDIAN)
3801 /* The block number we calculated above followed memory endianness.
3802 Convert it to register endianness by counting back from the end.
3803 (Note that, because of the assumption above, each block must be
3804 at least word-sized.) */
3805 info->offset = (num_blocks - block_number - 1) * nregs_ymode;
3806 else
3807 info->offset = block_number * nregs_ymode;
3808 info->nregs = nregs_ymode;
3809}
3810
3811/* This function returns the regno offset of a subreg expression.
3812 xregno - A regno of an inner hard subreg_reg (or what will become one).
3813 xmode - The mode of xregno.
3814 offset - The byte offset.
3815 ymode - The mode of a top level SUBREG (or what may become one).
3816 RETURN - The regno offset which would be used. */
3817unsigned int
3818subreg_regno_offset (unsigned int xregno, machine_mode xmode,
3819 unsigned int offset, machine_mode ymode)
3820{
3821 struct subreg_info info;
3822 subreg_get_info (xregno, xmode, offset, ymode, &info);
3823 return info.offset;
3824}
3825
3826/* This function returns true when the offset is representable via
3827 subreg_offset in the given regno.
3828 xregno - A regno of an inner hard subreg_reg (or what will become one).
3829 xmode - The mode of xregno.
3830 offset - The byte offset.
3831 ymode - The mode of a top level SUBREG (or what may become one).
3832 RETURN - Whether the offset is representable. */
3833bool
3834subreg_offset_representable_p (unsigned int xregno, machine_mode xmode,
3835 unsigned int offset, machine_mode ymode)
3836{
3837 struct subreg_info info;
3838 subreg_get_info (xregno, xmode, offset, ymode, &info);
3839 return info.representable_p;
3840}
3841
3842/* Return the number of a YMODE register to which
3843
3844 (subreg:YMODE (reg:XMODE XREGNO) OFFSET)
3845
3846 can be simplified. Return -1 if the subreg can't be simplified.
3847
3848 XREGNO is a hard register number. */
3849
3850int
3851simplify_subreg_regno (unsigned int xregno, machine_mode xmode,
3852 unsigned int offset, machine_mode ymode)
3853{
3854 struct subreg_info info;
3855 unsigned int yregno;
3856
3857 /* Give the backend a chance to disallow the mode change. */
3858 if (GET_MODE_CLASS (xmode) != MODE_COMPLEX_INT
3859 && GET_MODE_CLASS (xmode) != MODE_COMPLEX_FLOAT
3860 && !REG_CAN_CHANGE_MODE_P (xregno, xmode, ymode)
3861 /* We can use mode change in LRA for some transformations. */
3862 && ! lra_in_progress)
3863 return -1;
3864
3865 /* We shouldn't simplify stack-related registers. */
3866 if ((!reload_completed || frame_pointer_needed)
3867 && xregno == FRAME_POINTER_REGNUM)
3868 return -1;
3869
3870 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3871 && xregno == ARG_POINTER_REGNUM)
3872 return -1;
3873
3874 if (xregno == STACK_POINTER_REGNUM
3875 /* We should convert hard stack register in LRA if it is
3876 possible. */
3877 && ! lra_in_progress)
3878 return -1;
3879
3880 /* Try to get the register offset. */
3881 subreg_get_info (xregno, xmode, offset, ymode, &info);
3882 if (!info.representable_p)
3883 return -1;
3884
3885 /* Make sure that the offsetted register value is in range. */
3886 yregno = xregno + info.offset;
3887 if (!HARD_REGISTER_NUM_P (yregno))
3888 return -1;
3889
3890 /* See whether (reg:YMODE YREGNO) is valid.
3891
3892 ??? We allow invalid registers if (reg:XMODE XREGNO) is also invalid.
3893 This is a kludge to work around how complex FP arguments are passed
3894 on IA-64 and should be fixed. See PR target/49226. */
3895 if (!targetm.hard_regno_mode_ok (yregno, ymode)
3896 && targetm.hard_regno_mode_ok (xregno, xmode))
3897 return -1;
3898
3899 return (int) yregno;
3900}
3901
3902/* Return the final regno that a subreg expression refers to. */
3903unsigned int
3904subreg_regno (const_rtx x)
3905{
3906 unsigned int ret;
3907 rtx subreg = SUBREG_REG (x);
3908 int regno = REGNO (subreg);
3909
3910 ret = regno + subreg_regno_offset (regno,
3911 GET_MODE (subreg),
3912 SUBREG_BYTE (x),
3913 GET_MODE (x));
3914 return ret;
3915
3916}
3917
3918/* Return the number of registers that a subreg expression refers
3919 to. */
3920unsigned int
3921subreg_nregs (const_rtx x)
3922{
3923 return subreg_nregs_with_regno (REGNO (SUBREG_REG (x)), x);
3924}
3925
3926/* Return the number of registers that a subreg REG with REGNO
3927 expression refers to. This is a copy of the rtlanal.c:subreg_nregs
3928 changed so that the regno can be passed in. */
3929
3930unsigned int
3931subreg_nregs_with_regno (unsigned int regno, const_rtx x)
3932{
3933 struct subreg_info info;
3934 rtx subreg = SUBREG_REG (x);
3935
3936 subreg_get_info (regno, GET_MODE (subreg), SUBREG_BYTE (x), GET_MODE (x),
3937 &info);
3938 return info.nregs;
3939}
3940
3941struct parms_set_data
3942{
3943 int nregs;
3944 HARD_REG_SET regs;
3945};
3946
3947/* Helper function for noticing stores to parameter registers. */
3948static void
3949parms_set (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3950{
3951 struct parms_set_data *const d = (struct parms_set_data *) data;
3952 if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3953 && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3954 {
3955 CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3956 d->nregs--;
3957 }
3958}
3959
3960/* Look backward for first parameter to be loaded.
3961 Note that loads of all parameters will not necessarily be
3962 found if CSE has eliminated some of them (e.g., an argument
3963 to the outer function is passed down as a parameter).
3964 Do not skip BOUNDARY. */
3965rtx_insn *
3966find_first_parameter_load (rtx_insn *call_insn, rtx_insn *boundary)
3967{
3968 struct parms_set_data parm;
3969 rtx p;
3970 rtx_insn *before, *first_set;
3971
3972 /* Since different machines initialize their parameter registers
3973 in different orders, assume nothing. Collect the set of all
3974 parameter registers. */
3975 CLEAR_HARD_REG_SET (parm.regs);
3976 parm.nregs = 0;
3977 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3978 if (GET_CODE (XEXP (p, 0)) == USE
3979 && REG_P (XEXP (XEXP (p, 0), 0))
3980 && !STATIC_CHAIN_REG_P (XEXP (XEXP (p, 0), 0)))
3981 {
3982 gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3983
3984 /* We only care about registers which can hold function
3985 arguments. */
3986 if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3987 continue;
3988
3989 SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3990 parm.nregs++;
3991 }
3992 before = call_insn;
3993 first_set = call_insn;
3994
3995 /* Search backward for the first set of a register in this set. */
3996 while (parm.nregs && before != boundary)
3997 {
3998 before = PREV_INSN (before);
3999
4000 /* It is possible that some loads got CSEed from one call to
4001 another. Stop in that case. */
4002 if (CALL_P (before))
4003 break;
4004
4005 /* Our caller needs either ensure that we will find all sets
4006 (in case code has not been optimized yet), or take care
4007 for possible labels in a way by setting boundary to preceding
4008 CODE_LABEL. */
4009 if (LABEL_P (before))
4010 {
4011 gcc_assert (before == boundary);
4012 break;
4013 }
4014
4015 if (INSN_P (before))
4016 {
4017 int nregs_old = parm.nregs;
4018 note_stores (PATTERN (before), parms_set, &parm);
4019 /* If we found something that did not set a parameter reg,
4020 we're done. Do not keep going, as that might result
4021 in hoisting an insn before the setting of a pseudo
4022 that is used by the hoisted insn. */
4023 if (nregs_old != parm.nregs)
4024 first_set = before;
4025 else
4026 break;
4027 }
4028 }
4029 return first_set;
4030}
4031
4032/* Return true if we should avoid inserting code between INSN and preceding
4033 call instruction. */
4034
4035bool
4036keep_with_call_p (const rtx_insn *insn)
4037{
4038 rtx set;
4039
4040 if (INSN_P (insn) && (set = single_set (insn)) != NULL)
4041 {
4042 if (REG_P (SET_DEST (set))
4043 && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
4044 && fixed_regs[REGNO (SET_DEST (set))]
4045 && general_operand (SET_SRC (set), VOIDmode))
4046 return true;
4047 if (REG_P (SET_SRC (set))
4048 && targetm.calls.function_value_regno_p (REGNO (SET_SRC (set)))
4049 && REG_P (SET_DEST (set))
4050 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
4051 return true;
4052 /* There may be a stack pop just after the call and before the store
4053 of the return register. Search for the actual store when deciding
4054 if we can break or not. */
4055 if (SET_DEST (set) == stack_pointer_rtx)
4056 {
4057 /* This CONST_CAST is okay because next_nonnote_insn just
4058 returns its argument and we assign it to a const_rtx
4059 variable. */
4060 const rtx_insn *i2
4061 = next_nonnote_insn (const_cast<rtx_insn *> (insn));
4062 if (i2 && keep_with_call_p (i2))
4063 return true;
4064 }
4065 }
4066 return false;
4067}
4068
4069/* Return true if LABEL is a target of JUMP_INSN. This applies only
4070 to non-complex jumps. That is, direct unconditional, conditional,
4071 and tablejumps, but not computed jumps or returns. It also does
4072 not apply to the fallthru case of a conditional jump. */
4073
4074bool
4075label_is_jump_target_p (const_rtx label, const rtx_insn *jump_insn)
4076{
4077 rtx tmp = JUMP_LABEL (jump_insn);
4078 rtx_jump_table_data *table;
4079
4080 if (label == tmp)
4081 return true;
4082
4083 if (tablejump_p (jump_insn, NULL, &table))
4084 {
4085 rtvec vec = table->get_labels ();
4086 int i, veclen = GET_NUM_ELEM (vec);
4087
4088 for (i = 0; i < veclen; ++i)
4089 if (XEXP (RTVEC_ELT (vec, i), 0) == label)
4090 return true;
4091 }
4092
4093 if (find_reg_note (jump_insn, REG_LABEL_TARGET, label))
4094 return true;
4095
4096 return false;
4097}
4098
4099
4100/* Return an estimate of the cost of computing rtx X.
4101 One use is in cse, to decide which expression to keep in the hash table.
4102 Another is in rtl generation, to pick the cheapest way to multiply.
4103 Other uses like the latter are expected in the future.
4104
4105 X appears as operand OPNO in an expression with code OUTER_CODE.
4106 SPEED specifies whether costs optimized for speed or size should
4107 be returned. */
4108
4109int
4110rtx_cost (rtx x, machine_mode mode, enum rtx_code outer_code,
4111 int opno, bool speed)
4112{
4113 int i, j;
4114 enum rtx_code code;
4115 const char *fmt;
4116 int total;
4117 int factor;
4118
4119 if (x == 0)
4120 return 0;
4121
4122 if (GET_MODE (x) != VOIDmode)
4123 mode = GET_MODE (x);
4124
4125 /* A size N times larger than UNITS_PER_WORD likely needs N times as
4126 many insns, taking N times as long. */
4127 factor = GET_MODE_SIZE (mode) / UNITS_PER_WORD;
4128 if (factor == 0)
4129 factor = 1;
4130
4131 /* Compute the default costs of certain things.
4132 Note that targetm.rtx_costs can override the defaults. */
4133
4134 code = GET_CODE (x);
4135 switch (code)
4136 {
4137 case MULT:
4138 /* Multiplication has time-complexity O(N*N), where N is the
4139 number of units (translated from digits) when using
4140 schoolbook long multiplication. */
4141 total = factor * factor * COSTS_N_INSNS (5);
4142 break;
4143 case DIV:
4144 case UDIV:
4145 case MOD:
4146 case UMOD:
4147 /* Similarly, complexity for schoolbook long division. */
4148 total = factor * factor * COSTS_N_INSNS (7);
4149 break;
4150 case USE:
4151 /* Used in combine.c as a marker. */
4152 total = 0;
4153 break;
4154 case SET:
4155 /* A SET doesn't have a mode, so let's look at the SET_DEST to get
4156 the mode for the factor. */
4157 mode = GET_MODE (SET_DEST (x));
4158 factor = GET_MODE_SIZE (mode) / UNITS_PER_WORD;
4159 if (factor == 0)
4160 factor = 1;
4161 /* FALLTHRU */
4162 default:
4163 total = factor * COSTS_N_INSNS (1);
4164 }
4165
4166 switch (code)
4167 {
4168 case REG:
4169 return 0;
4170
4171 case SUBREG:
4172 total = 0;
4173 /* If we can't tie these modes, make this expensive. The larger
4174 the mode, the more expensive it is. */
4175 if (!targetm.modes_tieable_p (mode, GET_MODE (SUBREG_REG (x))))
4176 return COSTS_N_INSNS (2 + factor);
4177 break;
4178
4179 case TRUNCATE:
4180 if (targetm.modes_tieable_p (mode, GET_MODE (XEXP (x, 0))))
4181 {
4182 total = 0;
4183 break;
4184 }
4185 /* FALLTHRU */
4186 default:
4187 if (targetm.rtx_costs (x, mode, outer_code, opno, &total, speed))
4188 return total;
4189 break;
4190 }
4191
4192 /* Sum the costs of the sub-rtx's, plus cost of this operation,
4193 which is already in total. */
4194
4195 fmt = GET_RTX_FORMAT (code);
4196 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4197 if (fmt[i] == 'e')
4198 total += rtx_cost (XEXP (x, i), mode, code, i, speed);
4199 else if (fmt[i] == 'E')
4200 for (j = 0; j < XVECLEN (x, i); j++)
4201 total += rtx_cost (XVECEXP (x, i, j), mode, code, i, speed);
4202
4203 return total;
4204}
4205
4206/* Fill in the structure C with information about both speed and size rtx
4207 costs for X, which is operand OPNO in an expression with code OUTER. */
4208
4209void
4210get_full_rtx_cost (rtx x, machine_mode mode, enum rtx_code outer, int opno,
4211 struct full_rtx_costs *c)
4212{
4213 c->speed = rtx_cost (x, mode, outer, opno, true);
4214 c->size = rtx_cost (x, mode, outer, opno, false);
4215}
4216
4217
4218/* Return cost of address expression X.
4219 Expect that X is properly formed address reference.
4220
4221 SPEED parameter specify whether costs optimized for speed or size should
4222 be returned. */
4223
4224int
4225address_cost (rtx x, machine_mode mode, addr_space_t as, bool speed)
4226{
4227 /* We may be asked for cost of various unusual addresses, such as operands
4228 of push instruction. It is not worthwhile to complicate writing
4229 of the target hook by such cases. */
4230
4231 if (!memory_address_addr_space_p (mode, x, as))
4232 return 1000;
4233
4234 return targetm.address_cost (x, mode, as, speed);
4235}
4236
4237/* If the target doesn't override, compute the cost as with arithmetic. */
4238
4239int
4240default_address_cost (rtx x, machine_mode, addr_space_t, bool speed)
4241{
4242 return rtx_cost (x, Pmode, MEM, 0, speed);
4243}
4244
4245
4246unsigned HOST_WIDE_INT
4247nonzero_bits (const_rtx x, machine_mode mode)
4248{
4249 if (mode == VOIDmode)
4250 mode = GET_MODE (x);
4251 scalar_int_mode int_mode;
4252 if (!is_a <scalar_int_mode> (mode, &int_mode))
4253 return GET_MODE_MASK (mode);
4254 return cached_nonzero_bits (x, int_mode, NULL_RTX, VOIDmode, 0);
4255}
4256
4257unsigned int
4258num_sign_bit_copies (const_rtx x, machine_mode mode)
4259{
4260 if (mode == VOIDmode)
4261 mode = GET_MODE (x);
4262 scalar_int_mode int_mode;
4263 if (!is_a <scalar_int_mode> (mode, &int_mode))
4264 return 1;
4265 return cached_num_sign_bit_copies (x, int_mode, NULL_RTX, VOIDmode, 0);
4266}
4267
4268/* Return true if nonzero_bits1 might recurse into both operands
4269 of X. */
4270
4271static inline bool
4272nonzero_bits_binary_arith_p (const_rtx x)
4273{
4274 if (!ARITHMETIC_P (x))
4275 return false;
4276 switch (GET_CODE (x))
4277 {
4278 case AND:
4279 case XOR:
4280 case IOR:
4281 case UMIN:
4282 case UMAX:
4283 case SMIN:
4284 case SMAX:
4285 case PLUS:
4286 case MINUS:
4287 case MULT:
4288 case DIV:
4289 case UDIV:
4290 case MOD:
4291 case UMOD:
4292 return true;
4293 default:
4294 return false;
4295 }
4296}
4297
4298/* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
4299 It avoids exponential behavior in nonzero_bits1 when X has
4300 identical subexpressions on the first or the second level. */
4301
4302static unsigned HOST_WIDE_INT
4303cached_nonzero_bits (const_rtx x, scalar_int_mode mode, const_rtx known_x,
4304 machine_mode known_mode,
4305 unsigned HOST_WIDE_INT known_ret)
4306{
4307 if (x == known_x && mode == known_mode)
4308 return known_ret;
4309
4310 /* Try to find identical subexpressions. If found call
4311 nonzero_bits1 on X with the subexpressions as KNOWN_X and the
4312 precomputed value for the subexpression as KNOWN_RET. */
4313
4314 if (nonzero_bits_binary_arith_p (x))
4315 {
4316 rtx x0 = XEXP (x, 0);
4317 rtx x1 = XEXP (x, 1);
4318
4319 /* Check the first level. */
4320 if (x0 == x1)
4321 return nonzero_bits1 (x, mode, x0, mode,
4322 cached_nonzero_bits (x0, mode, known_x,
4323 known_mode, known_ret));
4324
4325 /* Check the second level. */
4326 if (nonzero_bits_binary_arith_p (x0)
4327 && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
4328 return nonzero_bits1 (x, mode, x1, mode,
4329 cached_nonzero_bits (x1, mode, known_x,
4330 known_mode, known_ret));
4331
4332 if (nonzero_bits_binary_arith_p (x1)
4333 && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
4334 return nonzero_bits1 (x, mode, x0, mode,
4335 cached_nonzero_bits (x0, mode, known_x,
4336 known_mode, known_ret));
4337 }
4338
4339 return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
4340}
4341
4342/* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
4343 We don't let nonzero_bits recur into num_sign_bit_copies, because that
4344 is less useful. We can't allow both, because that results in exponential
4345 run time recursion. There is a nullstone testcase that triggered
4346 this. This macro avoids accidental uses of num_sign_bit_copies. */
4347#define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
4348
4349/* Given an expression, X, compute which bits in X can be nonzero.
4350 We don't care about bits outside of those defined in MODE.
4351
4352 For most X this is simply GET_MODE_MASK (GET_MODE (X)), but if X is
4353 an arithmetic operation, we can do better. */
4354
4355static unsigned HOST_WIDE_INT
4356nonzero_bits1 (const_rtx x, scalar_int_mode mode, const_rtx known_x,
4357 machine_mode known_mode,
4358 unsigned HOST_WIDE_INT known_ret)
4359{
4360 unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
4361 unsigned HOST_WIDE_INT inner_nz;
4362 enum rtx_code code;
4363 machine_mode inner_mode;
4364 scalar_int_mode xmode;
4365
4366 unsigned int mode_width = GET_MODE_PRECISION (mode);
4367
4368 if (CONST_INT_P (x))
4369 {
4370 if (SHORT_IMMEDIATES_SIGN_EXTEND
4371 && INTVAL (x) > 0
4372 && mode_width < BITS_PER_WORD
4373 && (UINTVAL (x) & (HOST_WIDE_INT_1U << (mode_width - 1))) != 0)
4374 return UINTVAL (x) | (HOST_WIDE_INT_M1U << mode_width);
4375
4376 return UINTVAL (x);
4377 }
4378
4379 if (!is_a <scalar_int_mode> (GET_MODE (x), &xmode))
4380 return nonzero;
4381 unsigned int xmode_width = GET_MODE_PRECISION (xmode);
4382
4383 /* If X is wider than MODE, use its mode instead. */
4384 if (xmode_width > mode_width)
4385 {
4386 mode = xmode;
4387 nonzero = GET_MODE_MASK (mode);
4388 mode_width = xmode_width;
4389 }
4390
4391 if (mode_width > HOST_BITS_PER_WIDE_INT)
4392 /* Our only callers in this case look for single bit values. So
4393 just return the mode mask. Those tests will then be false. */
4394 return nonzero;
4395
4396 /* If MODE is wider than X, but both are a single word for both the host
4397 and target machines, we can compute this from which bits of the
4398 object might be nonzero in its own mode, taking into account the fact
4399 that on many CISC machines, accessing an object in a wider mode
4400 causes the high-order bits to become undefined. So they are
4401 not known to be zero. */
4402
4403 if (!WORD_REGISTER_OPERATIONS
4404 && mode_width > xmode_width
4405 && xmode_width <= BITS_PER_WORD
4406 && xmode_width <= HOST_BITS_PER_WIDE_INT)
4407 {
4408 nonzero &= cached_nonzero_bits (x, xmode,
4409 known_x, known_mode, known_ret);
4410 nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (xmode);
4411 return nonzero;
4412 }
4413
4414 /* Please keep nonzero_bits_binary_arith_p above in sync with
4415 the code in the switch below. */
4416 code = GET_CODE (x);
4417 switch (code)
4418 {
4419 case REG:
4420#if defined(POINTERS_EXTEND_UNSIGNED)
4421 /* If pointers extend unsigned and this is a pointer in Pmode, say that
4422 all the bits above ptr_mode are known to be zero. */
4423 /* As we do not know which address space the pointer is referring to,
4424 we can do this only if the target does not support different pointer
4425 or address modes depending on the address space. */
4426 if (target_default_pointer_address_modes_p ()
4427 && POINTERS_EXTEND_UNSIGNED
4428 && xmode == Pmode
4429 && REG_POINTER (x)
4430 && !targetm.have_ptr_extend ())
4431 nonzero &= GET_MODE_MASK (ptr_mode);
4432#endif
4433
4434 /* Include declared information about alignment of pointers. */
4435 /* ??? We don't properly preserve REG_POINTER changes across
4436 pointer-to-integer casts, so we can't trust it except for
4437 things that we know must be pointers. See execute/960116-1.c. */
4438 if ((x == stack_pointer_rtx
4439 || x == frame_pointer_rtx
4440 || x == arg_pointer_rtx)
4441 && REGNO_POINTER_ALIGN (REGNO (x)))
4442 {
4443 unsigned HOST_WIDE_INT alignment
4444 = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
4445
4446#ifdef PUSH_ROUNDING
4447 /* If PUSH_ROUNDING is defined, it is possible for the
4448 stack to be momentarily aligned only to that amount,
4449 so we pick the least alignment. */
4450 if (x == stack_pointer_rtx && PUSH_ARGS)
4451 alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
4452 alignment);
4453#endif
4454
4455 nonzero &= ~(alignment - 1);
4456 }
4457
4458 {
4459 unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
4460 rtx new_rtx = rtl_hooks.reg_nonzero_bits (x, xmode, mode,
4461 &nonzero_for_hook);
4462
4463 if (new_rtx)
4464 nonzero_for_hook &= cached_nonzero_bits (new_rtx, mode, known_x,
4465 known_mode, known_ret);
4466
4467 return nonzero_for_hook;
4468 }
4469
4470 case MEM:
4471 /* In many, if not most, RISC machines, reading a byte from memory
4472 zeros the rest of the register. Noticing that fact saves a lot
4473 of extra zero-extends. */
4474 if (load_extend_op (xmode) == ZERO_EXTEND)
4475 nonzero &= GET_MODE_MASK (xmode);
4476 break;
4477
4478 case EQ: case NE:
4479 case UNEQ: case LTGT:
4480 case GT: case GTU: case UNGT:
4481 case LT: case LTU: case UNLT:
4482 case GE: case GEU: case UNGE:
4483 case LE: case LEU: case UNLE:
4484 case UNORDERED: case ORDERED:
4485 /* If this produces an integer result, we know which bits are set.
4486 Code here used to clear bits outside the mode of X, but that is
4487 now done above. */
4488 /* Mind that MODE is the mode the caller wants to look at this
4489 operation in, and not the actual operation mode. We can wind
4490 up with (subreg:DI (gt:V4HI x y)), and we don't have anything
4491 that describes the results of a vector compare. */
4492 if (GET_MODE_CLASS (xmode) == MODE_INT
4493 && mode_width <= HOST_BITS_PER_WIDE_INT)
4494 nonzero = STORE_FLAG_VALUE;
4495 break;
4496
4497 case NEG:
4498#if 0
4499 /* Disabled to avoid exponential mutual recursion between nonzero_bits
4500 and num_sign_bit_copies. */
4501 if (num_sign_bit_copies (XEXP (x, 0), xmode) == xmode_width)
4502 nonzero = 1;
4503#endif
4504
4505 if (xmode_width < mode_width)
4506 nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (xmode));
4507 break;
4508
4509 case ABS:
4510#if 0
4511 /* Disabled to avoid exponential mutual recursion between nonzero_bits
4512 and num_sign_bit_copies. */
4513 if (num_sign_bit_copies (XEXP (x, 0), xmode) == xmode_width)
4514 nonzero = 1;
4515#endif
4516 break;
4517
4518 case TRUNCATE:
4519 nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
4520 known_x, known_mode, known_ret)
4521 & GET_MODE_MASK (mode));
4522 break;
4523
4524 case ZERO_EXTEND:
4525 nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
4526 known_x, known_mode, known_ret);
4527 if (GET_MODE (XEXP (x, 0)) != VOIDmode)
4528 nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
4529 break;
4530
4531 case SIGN_EXTEND:
4532 /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
4533 Otherwise, show all the bits in the outer mode but not the inner
4534 may be nonzero. */
4535 inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
4536 known_x, known_mode, known_ret);
4537 if (GET_MODE (XEXP (x, 0)) != VOIDmode)
4538 {
4539 inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
4540 if (val_signbit_known_set_p (GET_MODE (XEXP (x, 0)), inner_nz))
4541 inner_nz |= (GET_MODE_MASK (mode)
4542 & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
4543 }
4544
4545 nonzero &= inner_nz;
4546 break;
4547
4548 case AND:
4549 nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
4550 known_x, known_mode, known_ret)
4551 & cached_nonzero_bits (XEXP (x, 1), mode,
4552 known_x, known_mode, known_ret);
4553 break;
4554
4555 case XOR: case IOR:
4556 case UMIN: case UMAX: case SMIN: case SMAX:
4557 {
4558 unsigned HOST_WIDE_INT nonzero0
4559 = cached_nonzero_bits (XEXP (x, 0), mode,
4560 known_x, known_mode, known_ret);
4561
4562 /* Don't call nonzero_bits for the second time if it cannot change
4563 anything. */
4564 if ((nonzero & nonzero0) != nonzero)
4565 nonzero &= nonzero0
4566 | cached_nonzero_bits (XEXP (x, 1), mode,
4567 known_x, known_mode, known_ret);
4568 }
4569 break;
4570
4571 case PLUS: case MINUS:
4572 case MULT:
4573 case DIV: case UDIV:
4574 case MOD: case UMOD:
4575 /* We can apply the rules of arithmetic to compute the number of
4576 high- and low-order zero bits of these operations. We start by
4577 computing the width (position of the highest-order nonzero bit)
4578 and the number of low-order zero bits for each value. */
4579 {
4580 unsigned HOST_WIDE_INT nz0
4581 = cached_nonzero_bits (XEXP (x, 0), mode,
4582 known_x, known_mode, known_ret);
4583 unsigned HOST_WIDE_INT nz1
4584 = cached_nonzero_bits (XEXP (x, 1), mode,
4585 known_x, known_mode, known_ret);
4586 int sign_index = xmode_width - 1;
4587 int width0 = floor_log2 (nz0) + 1;
4588 int width1 = floor_log2 (nz1) + 1;
4589 int low0 = ctz_or_zero (nz0);
4590 int low1 = ctz_or_zero (nz1);
4591 unsigned HOST_WIDE_INT op0_maybe_minusp
4592 = nz0 & (HOST_WIDE_INT_1U << sign_index);
4593 unsigned HOST_WIDE_INT op1_maybe_minusp
4594 = nz1 & (HOST_WIDE_INT_1U << sign_index);
4595 unsigned int result_width = mode_width;
4596 int result_low = 0;
4597
4598 switch (code)
4599 {
4600 case PLUS:
4601 result_width = MAX (width0, width1) + 1;
4602 result_low = MIN (low0, low1);
4603 break;
4604 case MINUS:
4605 result_low = MIN (low0, low1);
4606 break;
4607 case MULT:
4608 result_width = width0 + width1;
4609 result_low = low0 + low1;
4610 break;
4611 case DIV:
4612 if (width1 == 0)
4613 break;
4614 if (!op0_maybe_minusp && !op1_maybe_minusp)
4615 result_width = width0;
4616 break;
4617 case UDIV:
4618 if (width1 == 0)
4619 break;
4620 result_width = width0;
4621 break;
4622 case MOD:
4623 if (width1 == 0)
4624 break;
4625 if (!op0_maybe_minusp && !op1_maybe_minusp)
4626 result_width = MIN (width0, width1);
4627 result_low = MIN (low0, low1);
4628 break;
4629 case UMOD:
4630 if (width1 == 0)
4631 break;
4632 result_width = MIN (width0, width1);
4633 result_low = MIN (low0, low1);
4634 break;
4635 default:
4636 gcc_unreachable ();
4637 }
4638
4639 if (result_width < mode_width)
4640 nonzero &= (HOST_WIDE_INT_1U << result_width) - 1;
4641
4642 if (result_low > 0)
4643 nonzero &= ~((HOST_WIDE_INT_1U << result_low) - 1);
4644 }
4645 break;
4646
4647 case ZERO_EXTRACT:
4648 if (CONST_INT_P (XEXP (x, 1))
4649 && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
4650 nonzero &= (HOST_WIDE_INT_1U << INTVAL (XEXP (x, 1))) - 1;
4651 break;
4652
4653 case SUBREG:
4654 /* If this is a SUBREG formed for a promoted variable that has
4655 been zero-extended, we know that at least the high-order bits
4656 are zero, though others might be too. */
4657 if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x))
4658 nonzero = GET_MODE_MASK (xmode)
4659 & cached_nonzero_bits (SUBREG_REG (x), xmode,
4660 known_x, known_mode, known_ret);
4661
4662 /* If the inner mode is a single word for both the host and target
4663 machines, we can compute this from which bits of the inner
4664 object might be nonzero. */
4665 inner_mode = GET_MODE (SUBREG_REG (x));
4666 if (GET_MODE_PRECISION (inner_mode) <= BITS_PER_WORD
4667 && GET_MODE_PRECISION (inner_mode) <= HOST_BITS_PER_WIDE_INT)
4668 {
4669 nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
4670 known_x, known_mode, known_ret);
4671
4672 /* On many CISC machines, accessing an object in a wider mode
4673 causes the high-order bits to become undefined. So they are
4674 not known to be zero. */
4675 rtx_code extend_op;
4676 if ((!WORD_REGISTER_OPERATIONS
4677 /* If this is a typical RISC machine, we only have to worry
4678 about the way loads are extended. */
4679 || ((extend_op = load_extend_op (inner_mode)) == SIGN_EXTEND
4680 ? val_signbit_known_set_p (inner_mode, nonzero)
4681 : extend_op != ZERO_EXTEND)
4682 || (!MEM_P (SUBREG_REG (x)) && !REG_P (SUBREG_REG (x))))
4683 && xmode_width > GET_MODE_PRECISION (inner_mode))
4684 nonzero |= (GET_MODE_MASK (xmode) & ~GET_MODE_MASK (inner_mode));
4685 }
4686 break;
4687
4688 case ASHIFTRT:
4689 case LSHIFTRT:
4690 case ASHIFT:
4691 case ROTATE:
4692 /* The nonzero bits are in two classes: any bits within MODE
4693 that aren't in xmode are always significant. The rest of the
4694 nonzero bits are those that are significant in the operand of
4695 the shift when shifted the appropriate number of bits. This
4696 shows that high-order bits are cleared by the right shift and
4697 low-order bits by left shifts. */
4698 if (CONST_INT_P (XEXP (x, 1))
4699 && INTVAL (XEXP (x, 1)) >= 0
4700 && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT
4701 && INTVAL (XEXP (x, 1)) < xmode_width)
4702 {
4703 int count = INTVAL (XEXP (x, 1));
4704 unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (xmode);
4705 unsigned HOST_WIDE_INT op_nonzero
4706 = cached_nonzero_bits (XEXP (x, 0), mode,
4707 known_x, known_mode, known_ret);
4708 unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
4709 unsigned HOST_WIDE_INT outer = 0;
4710
4711 if (mode_width > xmode_width)
4712 outer = (op_nonzero & nonzero & ~mode_mask);
4713
4714 if (code == LSHIFTRT)
4715 inner >>= count;
4716 else if (code == ASHIFTRT)
4717 {
4718 inner >>= count;
4719
4720 /* If the sign bit may have been nonzero before the shift, we
4721 need to mark all the places it could have been copied to
4722 by the shift as possibly nonzero. */
4723 if (inner & (HOST_WIDE_INT_1U << (xmode_width - 1 - count)))
4724 inner |= (((HOST_WIDE_INT_1U << count) - 1)
4725 << (xmode_width - count));
4726 }
4727 else if (code == ASHIFT)
4728 inner <<= count;
4729 else
4730 inner = ((inner << (count % xmode_width)
4731 | (inner >> (xmode_width - (count % xmode_width))))
4732 & mode_mask);
4733
4734 nonzero &= (outer | inner);
4735 }
4736 break;
4737
4738 case FFS:
4739 case POPCOUNT:
4740 /* This is at most the number of bits in the mode. */
4741 nonzero = ((unsigned HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
4742 break;
4743
4744 case CLZ:
4745 /* If CLZ has a known value at zero, then the nonzero bits are
4746 that value, plus the number of bits in the mode minus one. */
4747 if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
4748 nonzero
4749 |= (HOST_WIDE_INT_1U << (floor_log2 (mode_width))) - 1;
4750 else
4751 nonzero = -1;
4752 break;
4753
4754 case CTZ:
4755 /* If CTZ has a known value at zero, then the nonzero bits are
4756 that value, plus the number of bits in the mode minus one. */
4757 if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
4758 nonzero
4759 |= (HOST_WIDE_INT_1U << (floor_log2 (mode_width))) - 1;
4760 else
4761 nonzero = -1;
4762 break;
4763
4764 case CLRSB:
4765 /* This is at most the number of bits in the mode minus 1. */
4766 nonzero = (HOST_WIDE_INT_1U << (floor_log2 (mode_width))) - 1;
4767 break;
4768
4769 case PARITY:
4770 nonzero = 1;
4771 break;
4772
4773 case IF_THEN_ELSE:
4774 {
4775 unsigned HOST_WIDE_INT nonzero_true
4776 = cached_nonzero_bits (XEXP (x, 1), mode,
4777 known_x, known_mode, known_ret);
4778
4779 /* Don't call nonzero_bits for the second time if it cannot change
4780 anything. */
4781 if ((nonzero & nonzero_true) != nonzero)
4782 nonzero &= nonzero_true
4783 | cached_nonzero_bits (XEXP (x, 2), mode,
4784 known_x, known_mode, known_ret);
4785 }
4786 break;
4787
4788 default:
4789 break;
4790 }
4791
4792 return nonzero;
4793}
4794
4795/* See the macro definition above. */
4796#undef cached_num_sign_bit_copies
4797
4798
4799/* Return true if num_sign_bit_copies1 might recurse into both operands
4800 of X. */
4801
4802static inline bool
4803num_sign_bit_copies_binary_arith_p (const_rtx x)
4804{
4805 if (!ARITHMETIC_P (x))
4806 return false;
4807 switch (GET_CODE (x))
4808 {
4809 case IOR:
4810 case AND:
4811 case XOR:
4812 case SMIN:
4813 case SMAX:
4814 case UMIN:
4815 case UMAX:
4816 case PLUS:
4817 case MINUS:
4818 case MULT:
4819 return true;
4820 default:
4821 return false;
4822 }
4823}
4824
4825/* The function cached_num_sign_bit_copies is a wrapper around
4826 num_sign_bit_copies1. It avoids exponential behavior in
4827 num_sign_bit_copies1 when X has identical subexpressions on the
4828 first or the second level. */
4829
4830static unsigned int
4831cached_num_sign_bit_copies (const_rtx x, scalar_int_mode mode,
4832 const_rtx known_x, machine_mode known_mode,
4833 unsigned int known_ret)
4834{
4835 if (x == known_x && mode == known_mode)
4836 return known_ret;
4837
4838 /* Try to find identical subexpressions. If found call
4839 num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
4840 the precomputed value for the subexpression as KNOWN_RET. */
4841
4842 if (num_sign_bit_copies_binary_arith_p (x))
4843 {
4844 rtx x0 = XEXP (x, 0);
4845 rtx x1 = XEXP (x, 1);
4846
4847 /* Check the first level. */
4848 if (x0 == x1)
4849 return
4850 num_sign_bit_copies1 (x, mode, x0, mode,
4851 cached_num_sign_bit_copies (x0, mode, known_x,
4852 known_mode,
4853 known_ret));
4854
4855 /* Check the second level. */
4856 if (num_sign_bit_copies_binary_arith_p (x0)
4857 && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
4858 return
4859 num_sign_bit_copies1 (x, mode, x1, mode,
4860 cached_num_sign_bit_copies (x1, mode, known_x,
4861 known_mode,
4862 known_ret));
4863
4864 if (num_sign_bit_copies_binary_arith_p (x1)
4865 && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
4866 return
4867 num_sign_bit_copies1 (x, mode, x0, mode,
4868 cached_num_sign_bit_copies (x0, mode, known_x,
4869 known_mode,
4870 known_ret));
4871 }
4872
4873 return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
4874}
4875
4876/* Return the number of bits at the high-order end of X that are known to
4877 be equal to the sign bit. X will be used in mode MODE. The returned
4878 value will always be between 1 and the number of bits in MODE. */
4879
4880static unsigned int
4881num_sign_bit_copies1 (const_rtx x, scalar_int_mode mode, const_rtx known_x,
4882 machine_mode known_mode,
4883 unsigned int known_ret)
4884{
4885 enum rtx_code code = GET_CODE (x);
4886 unsigned int bitwidth = GET_MODE_PRECISION (mode);
4887 int num0, num1, result;
4888 unsigned HOST_WIDE_INT nonzero;
4889
4890 if (CONST_INT_P (x))
4891 {
4892 /* If the constant is negative, take its 1's complement and remask.
4893 Then see how many zero bits we have. */
4894 nonzero = UINTVAL (x) & GET_MODE_MASK (mode);
4895 if (bitwidth <= HOST_BITS_PER_WIDE_INT
4896 && (nonzero & (HOST_WIDE_INT_1U << (bitwidth - 1))) != 0)
4897 nonzero = (~nonzero) & GET_MODE_MASK (mode);
4898
4899 return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4900 }
4901
4902 scalar_int_mode xmode, inner_mode;
4903 if (!is_a <scalar_int_mode> (GET_MODE (x), &xmode))
4904 return 1;
4905
4906 unsigned int xmode_width = GET_MODE_PRECISION (xmode);
4907
4908 /* For a smaller mode, just ignore the high bits. */
4909 if (bitwidth < xmode_width)
4910 {
4911 num0 = cached_num_sign_bit_copies (x, xmode,
4912 known_x, known_mode, known_ret);
4913 return MAX (1, num0 - (int) (xmode_width - bitwidth));
4914 }
4915
4916 if (bitwidth > xmode_width)
4917 {
4918 /* If this machine does not do all register operations on the entire
4919 register and MODE is wider than the mode of X, we can say nothing
4920 at all about the high-order bits. */
4921 if (!WORD_REGISTER_OPERATIONS)
4922 return 1;
4923
4924 /* Likewise on machines that do, if the mode of the object is smaller
4925 than a word and loads of that size don't sign extend, we can say
4926 nothing about the high order bits. */
4927 if (xmode_width < BITS_PER_WORD
4928 && load_extend_op (xmode) != SIGN_EXTEND)
4929 return 1;
4930 }
4931
4932 /* Please keep num_sign_bit_copies_binary_arith_p above in sync with
4933 the code in the switch below. */
4934 switch (code)
4935 {
4936 case REG:
4937
4938#if defined(POINTERS_EXTEND_UNSIGNED)
4939 /* If pointers extend signed and this is a pointer in Pmode, say that
4940 all the bits above ptr_mode are known to be sign bit copies. */
4941 /* As we do not know which address space the pointer is referring to,
4942 we can do this only if the target does not support different pointer
4943 or address modes depending on the address space. */
4944 if (target_default_pointer_address_modes_p ()
4945 && ! POINTERS_EXTEND_UNSIGNED && xmode == Pmode
4946 && mode == Pmode && REG_POINTER (x)
4947 && !targetm.have_ptr_extend ())
4948 return GET_MODE_PRECISION (Pmode) - GET_MODE_PRECISION (ptr_mode) + 1;
4949#endif
4950
4951 {
4952 unsigned int copies_for_hook = 1, copies = 1;
4953 rtx new_rtx = rtl_hooks.reg_num_sign_bit_copies (x, xmode, mode,
4954 &copies_for_hook);
4955
4956 if (new_rtx)
4957 copies = cached_num_sign_bit_copies (new_rtx, mode, known_x,
4958 known_mode, known_ret);
4959
4960 if (copies > 1 || copies_for_hook > 1)
4961 return MAX (copies, copies_for_hook);
4962
4963 /* Else, use nonzero_bits to guess num_sign_bit_copies (see below). */
4964 }
4965 break;
4966
4967 case MEM:
4968 /* Some RISC machines sign-extend all loads of smaller than a word. */
4969 if (load_extend_op (xmode) == SIGN_EXTEND)
4970 return MAX (1, ((int) bitwidth - (int) xmode_width + 1));
4971 break;
4972
4973 case SUBREG:
4974 /* If this is a SUBREG for a promoted object that is sign-extended
4975 and we are looking at it in a wider mode, we know that at least the
4976 high-order bits are known to be sign bit copies. */
4977
4978 if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_SIGNED_P (x))
4979 {
4980 num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4981 known_x, known_mode, known_ret);
4982 return MAX ((int) bitwidth - (int) xmode_width + 1, num0);
4983 }
4984
4985 if (is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (x)), &inner_mode))
4986 {
4987 /* For a smaller object, just ignore the high bits. */
4988 if (bitwidth <= GET_MODE_PRECISION (inner_mode))
4989 {
4990 num0 = cached_num_sign_bit_copies (SUBREG_REG (x), inner_mode,
4991 known_x, known_mode,
4992 known_ret);
4993 return MAX (1, num0 - (int) (GET_MODE_PRECISION (inner_mode)
4994 - bitwidth));
4995 }
4996
4997 /* For paradoxical SUBREGs on machines where all register operations
4998 affect the entire register, just look inside. Note that we are
4999 passing MODE to the recursive call, so the number of sign bit
5000 copies will remain relative to that mode, not the inner mode. */
5001
5002 /* This works only if loads sign extend. Otherwise, if we get a
5003 reload for the inner part, it may be loaded from the stack, and
5004 then we lose all sign bit copies that existed before the store
5005 to the stack. */
5006
5007 if (WORD_REGISTER_OPERATIONS
5008 && load_extend_op (inner_mode) == SIGN_EXTEND
5009 && paradoxical_subreg_p (x)
5010 && (MEM_P (SUBREG_REG (x)) || REG_P (SUBREG_REG (x))))
5011 return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
5012 known_x, known_mode, known_ret);
5013 }
5014 break;
5015
5016 case SIGN_EXTRACT:
5017 if (CONST_INT_P (XEXP (x, 1)))
5018 return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
5019 break;
5020
5021 case SIGN_EXTEND:
5022 if (is_a <scalar_int_mode> (GET_MODE (XEXP (x, 0)), &inner_mode))
5023 return (bitwidth - GET_MODE_PRECISION (inner_mode)
5024 + cached_num_sign_bit_copies (XEXP (x, 0), inner_mode,
5025 known_x, known_mode, known_ret));
5026 break;
5027
5028 case TRUNCATE:
5029 /* For a smaller object, just ignore the high bits. */